All these tasks will be described in greater detail below. Instead of starting with empty project folders, download and unzip the Start A Project Folders and Start B Project Folders which contains appropriately named folders. Write your code in these project folders, and when you are finished, zip each and submit it via Checkmate to the appropriate Part (A or B).

There are no executables with this assignment. For the the collection classes, you can use my testing code to test your classes (you should understand the correct behavior). For the recursive methods, I have supplied tests (via JUnit) that your methods should pass.

• A Queue with a regular linear linked list
• A Queue with a circular linked list.
• A Stack with a regular linear linked list, and Generics (so that no compiler warnings appear in the code).
• A PriorityQueue with a header linked list.
• A Set with a trailer linked list.
• A Map with a regular linear linked list.

Test your code to ensure the right exceptions are thrown too: my driver with catch the exception, print it, and keep testing your code. Here are the details.

• A Queue with a regular linear linked list. Unlike the standard collection classes, this simplified one uses void for many of its methods. All operations should be O(1). You must write the following methods, using/updating front, rear, and size as appropriate.
  • public void clear()
  • public void enqueue (Object o)
  • public Object peek () throws NoSuchElementException
  • public Object dequeue () throws NoSuchElementException

• A Queue with a circular linked list. Unlike the standard collection classes, this simplified one uses void for many of its methods. All operations should be O(1). You must write the following methods, using/updating rear and size as appropriate. Recall that rear refers to the most recently enqueued value; its next refers to the first enqueued value. Even single value lists should be circular.
  • public void clear()
  • public void enqueue (Object o)
  • public Object peek () throws NoSuchElementException
  • public Object dequeue () throws NoSuchElementException

• A Stack with a regular linear linked list, and Generics (so that no compiler warnings appear in the code). Unlike the standard collection classes, this simplified one uses void for many of its methods. All operations should be O(1). You must write the following methods, using/updating top and size as appropriate. You must make the local LN class generic, and ultimately get this file to compile without any warnings.
  • public void clear()
  • public void push (E o)
  • public E peek () throws NoSuchElementException
  • public E dequeue () throws NoSuchElementException

• A PriorityQueue with a header linked list. Unlike the standard collection classes, this simplified one uses void for many of its methods. All operations should be O(1), except for enqueue: keep the linear linked list sorted, from highest to lowest priority, so this operation is O(N). You must write the following methods, using/updating size and c as appropriate. Because this linked list has a header node, you should be able to simplify some code, because you will never have to update front, only the next instance variables of nodes in the list.
  • public void clear()
  • public void enqueue (Object o)
  • public Object peek () throws NoSuchElementException
  • public Object dequeue () throws NoSuchElementException

• A Set with a trailer linked list. Recall duplicates are not present in Sets, so we must add values carefully (and recall add and remove return a boolean value: whether or not the Set was changed). For this reason, all operations should be O(N), except for clear, which should still be O<1). You must write the following methods, using/updating front and size as appropriate. I wrote a private method named locate that returns a reference to the unique node storing its parameter's value (or null if that value is not in the Set). This is the only method that you should write with a loop: all other methods can call this one and then process the result, without looping, INCLUDING remove because of the trailer list.
  • public void clear()
  • public boolean add (Object o)
  • public boolean contains (Object o)
  • public boolean remove (Object o)
  • private LN locate(Object o)

• A Map with a regular linear linked list. Recall that when you put an association in the Map, if the key is already present, it changes the value associated with that key and returns the "old" value associated with that key (if the key is not already present, it returns null). Likewise, when a key is removed, if it is in the Map its associated value is returned (if the key is not currently in the Map, it returns null). All operations should be O(N), except for clear, which should still be O<1). You must write the following methods, using/updating front and size as appropriate.
  • public void clear()
  • public Object put (Object key, Object value)
  • public Object contains (Object key)
  • public Object get (Object key)
  • public Object remove (Object key)

The start folder for this part is an Ecliplse project with four classes First, the LN and TN (list node and tree node) classes contain the instance variables and a few utility methods (mostly called in the JUnit testing code) for representing lists and trees. The Solution class is where students write their solutions to all the required static methods; it contains comments about and headers for each of the methods that you must write. Finally, the TestSolution class is a JUnit testing class for all the methods that you must write in Solution. Part of this assignment will allow you to become more familiar with JUnit test, and learn how to use and debug with JUnit tests.

Note, that in TestSolution, each test method (e.g., testInsertAtRear, testInsertInOrder, etc.) will be called regardless of whether any other tests fail; to JUnit will test every method. Once in such a test method, its tests will either run to completion, with the method passing all its tests, or some test fail an "assertion": execution of the method stops after failing the first assertion, and leaves a record of the failure (by clicking you can find the nature of the failure, and on which line the assertion failed. The one exception to this rule is that if any method has infinite looping or recursion, no subsequent tests are done (and you can see the offending code as the last one tested -with the test not complete). Note that you can put System.out.println debugging statements in your code; its information will be printed on the console. I will state here unequivocally that the best way to debug your code is to do hand-simulations; the best thing you can do during this assignment is become proficient at hand simulating linked list code.

Here are the general instructions for this part (in the Solution class).

List Problems: In these problems you must return a list specified by the semantics of the method. You can mutate a parameter list, or construct a completely new list -whichever is simpler. You can write these methods iteratively or recursively, whichever is simpler. You may write helper methods, when appropriate.

Tree Problems: In these problems you must return an int, String, or tree list specified by the semantics of the method. You must not change the parameter tree You must write these methods recursively. You may write helper methods, when appropriate.

Here is a list of the methods with some hints about solutions. Generally, if there is a recursive solution, it is simpler than the iterative one.

• public static LN insertAtRear (LN l, Comparable o):
  
• public static LN insertInOrder (LN l, Comparable o):
  
• public static LN append (LN l1, LN l2):
  
• public static LN interleave (LN l1, LN l2) :
  
• public static LN merge (LN l1, LN l2) :
  
• public static LN removeAll (LN l, Comparable o):
  
• public static LN keepEven (LN l):
  
• public static LN reverse (LN l):
  Return a copy of the list (don't mutate it).
• public static LN intersect (LN l1, LN l2):
  Iterative solution is best; write a boolean contains helper method. Don't add any values to the result list, if they are already there.
• public static LN xOr (LN l1, LN l2):
  Iterative solution is best; write a boolean contains helper method. Don't add any values to the result list, if they are already there.
• public static LN union (LN l1, LN l2):
  Iterative solution is best; write a boolean contains helper method. Don't add any values to the result list, if they are already there.

• public static int height (TN t):
  
• public static int size (TN t):
  
• public static int leafCount (TN t):
  
• public static int internalCount (TN t):
  
• public static int nodesAtDepthCount (TN t, int depth):
  
• public static TN copyToDepth (TN t, int depth):
  A simple variant of the copy method.
• public static int minLeafDepth(TN t):
  Write a helper method, called by this one, whose header is private static int minLeafDepth(TN t, int level) It works nicely to have the minLeafDepth of an empty tree be Integer.MAX_VALUE, because it has no leaves.
• public static String pathTo (TN t, Comparable o):
  My solution recurs down both sides, with one guaranteed to return ""; if a recursive call returns a non-empty String then the current node is on the path to the required node.