Lab 3   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 lab3.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.  You may use the original version using head and tail pointers introduced in class or the circular list version you wrote for lab 2.

The recursive list implementation should use inheritance; that is, write a RecursiveSortedList class which is a subclass of RecursiveList.  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.  (Note:  Don't use any loops in your implementation, and don't use the get or set methods.  Write a recursive version of the add method.)

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 commas, and enclosed in brackets.

Put a simple main program in each class for testing, similar to what you wrote for lab 2.

Part Two.    Write an application 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
  

When you have the program working, try running it with the other SortedList implementation.  The only thing you should have to change is the name of the list class you instantiate when you create the SortedList.

The correct output for the sample input shown above is:


The jar file for lab 3 contains this sample input file (lab3a.txt) and a second, longer input file (lab3b.txt).

Note:  Test your application program with both of your implementations of sorted list.