Lab 4   Sorted Lists

This lab is an exercise in the implementation of sorted lists.  One of the implementations will be based on the RecursiveList class which we studied in class.  You can download my version of RecursiveList.java from the jar file lab4.jar .  Notice that I've defined prepend and removeFirst as "protected", so that they are not part of the public interface to the class, but may be used by subclasses.  The jar file also contains SortedList.java, which defines the SortedList interface.

Part One.    Write two implementations of SortedList.

One of your implementations should be based on RecursiveList.java; the other should be based on one of the other linked list implementations we've studied:  the original version using head and tail pointers introduced in class, the circular list version you wrote for Lab 3, or the doubly-linked list implementation presented in class.

One of your implementations should use inheritance; that is, it should be a subclass of one of the list classes listed in the previous paragraph.  This version should contain a new version of add(Object) which adds the new object in the proper order (instead of adding it at the end of the list).  It should also override the add(int,Object) and set(int,Object) methods with methods which throw an UnsupportedOperationException.

The other implementation should be written as an Adapter; that is, it should contain an instance of one of the unsorted list classes as its only instance variable.  This version needs to include all the methods in the SortedList interface.  Most of them, however, are simply one-line stub methods which call the corresponding methods in the underlying unsorted list.  The add(Object) method is the important one which needs to add the new object in the proper order.

Both of your list classes should have a toString method, which creates a string containing every element of the list, separated by the newline character ('\n').

Use descriptive names for the classes you write, such as SortedRecursiveList, SortedCircularLinkedList, etc.

Part Two.    Write a program which uses a SortedList to manage a list of names.  The program will read from a text file containing a sequence of list operations (add, remove, and get), and apply each one to the list of names.  Each line of the file will contain an operation followed by a name or number, as follows:

The user may use lower-case or upper-case letters, and may abbreviate the add, get, and remove commands with the single letters 'a', 'g', and 'r'.

The name of the input file will be a command-line argument to the program.  The program does the following:

• Create an empty SortedList.  It should be created by instantiating one of the list classes that you wrote in part one.
• Create a BufferedReader to read the file:
  
  BufferedReader reader = new BufferedReader(new FileReader(/* insert name of file here */));
  
  
• Use a loop to read each line of the file.  Use the following loop sructure:
  
  String line = reader.readLine(); // read the first line
  while(line!=null){
      /*  process the line  */
      line = reader.readLine(); // read the next line
  }
  
  
• For each input line
• Split the line into words, using the split method of String:
  
  String[] words = line.split(" ");
  /*
     words[0] is the operation
     words[1] is the name (for add) or number (for get, remove)
  */
  
  
• Apply the requested operation to the list
• For an add command, simply add the name to the list
• For a get command, display the name at the given position
• For a remove command, display the name at the given position, and remove it
• You can use a switch statement on the first character in the command word to choose between these three cases.  If an invalid command is entered, display an error message and continue.
  
• When you reach the end of the input file, display the entire contents of the list