Linked Structures

• 60 points
• Assigned 2012 Sep 26, due 2012 Oct 15

This is version 5.2, revised 2012 Sep 25.¹

Problem 1

Extend Drake's LinkedList class, available on merlin in /home/info/share/c243/drake-examples—check out with darcs—or from Peter Drake's Research page. (A version of the program is shown on pages 168–174; but you must use the code from one of the above sources, which is slightly different than shown in the chapter.) In the subclass, define two iterative methods:

1. public int count (E target) returns the number of elements in the list that are equals() to target.

   Example: if list is ["a", "b", "c", "a"], then list.count("a") returns 2.

2. Select one from the following:

   1. public void insertAt (E target, int index) inserts target into the list as its indexth element, if index is not greater than the length of the list; otherwise, the list is unchanged. Index positions are numbered starting at zero.
   2. public void insertBefore (E target, E successor) inserts target into the list just before the first element which is equals() to successor, if any; otherwise, the list is unchanged.
   3. public void insertAfter (E target, E predecessor) inserts target into the list just after the first element which is equals() to predecessor, if any; otherwise, the list is unchanged.

   In all three cases, the method preserves existing elements of the list, so that, if anything is inserted, the length of the list increases by 1.

   Examples: If list is ["cut", "the", "pie", "ice", "cream"], then:

   1. After list.insertAt("apple", 2), list is ["cut", "the", "apple", "pie", "ice", "cream"].
   2. After list.insertAt("apple", 5), list is ["cut", "the", "pie", "ice", "cream", "apple"].
   3. After list.insertAt("apple", 6), list is ["cut", "the" "pie", "ice", "cream"], unchanged.
   4. After list.insertBefore("please", "cut"), list is ["please", "cut", "the", "pie", "ice", "cream"],
   5. After list.insertAfter("thanks", "cream"), list is ["cut", "the", "pie", "ice", "cream", "thanks"],

"Extend" means to define a subclass. Identify yourself as the author of the subclass.

Problem 2

Define corresponding Haskell functions. For this problem, the functions must be recursive, and the insert function must perform list reconstruction, not list surgery.

The type declarations for the function are:

-- count xs x (list argument first, target argument second)
count :: (Eq a) => [a] -> a -> Int
-- or count x xs (target argument first, list argument second)
count :: (Eq a) => a -> [a] -> Int

-- (Choose one of the next three)

-- insertAt xs newX index
insertAt :: [a] -> a -> Int -> [a]

-- insertBefore xs newX successor
insertBefore :: (Eq a) => [a] -> a -> a -> [a]

-- insertAfter xs newX predecessor
insertAfter :: (Eq a) => [a] -> a -> a -> [a]

Problem 3

Similarly, define Java methods for a functional list class. As in Problem 2, the methods must be recursive, and the insert method must perform list reconstruction, not list surgery. You may use either of the Java functional list data types developed in class—

1. Version 1: List.java, ListOps.java
2. Version 2: List.java, Nil.java, Cons.java

—or Functional Java or Open Quark or any similar functional programming library for Java.

Depending on which Java list type you choose to use, you may either extend the class(es) (define subclasses) or add new methods to the existing class(es), and your methods may be either static methods with a list argument or non-static methods in which a list is the "receiver" of the message (method call). For example:

// For Lists version 1:
public static int count (List list, Object target);
public static List insertAt (List list, Object target, int index)
public static List insertBefore (List list, Object target, Object successor)
public static List insertAfter (List list, Object target, Object predecessor)

// For lists version 2:
public int count (Object target);
public List insertAt(Object target, int index);
public List insertBefore(Object target, Object successor);
public List insertAfter(Object target, Object predecessor);

Testing

Test your Java methods and Haskell functions. Save a copy of the test input and output. Tests for the list insert methods should include insertion at the beginning of the list, at the end of the list, and in between.

Writeup

Answer these questions:

1. Which problem (1, 2, or 3), if any, was easiest for you? What made it so?
2. Did you notice any differences in efficiency (program running time) between the three versions (problems 1, 2, 3)? If so, can you explain them?
3. What were the results of your testing? I.e., did the programs pass all tests? If not, which tests failed?

Checklist: What to Turn in

1. The writeup.
2. All source files that you authored or edited for Problems 1, 2, and
   3. Do not turn in provided code (from the textbook, instructor, or libraries such as Functional Java)—unless you have modified it.
3. Test input and output for Problems 1, 2, and 3 (one file per problem, three files total).

Grading

• Writeup, 6 points
• Testing, 6 points
• Six methods and functions, 42 points (7 points each)
• Style, 6 points

TOTAL, 60 points