Lab 3   Sorted Lists

In this lab we will be working with the RecursiveList class which we studied in class.  We will be implementing two versions of a Sorted List class, one of which is  based on recursive lists.

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.  Add two additional methods to RecursiveList.  The following methods are defined in the java List interface (and in my SortedList interface)::

int indexOf(Object obj);  //  Search for obj in this list.  If it is found, return the index of the position of its first occurrence; otherwise return -1.

boolean remove(Object obj);  //  Search for obj in this list.  If it is found, delete it (its first occurrence) and return true; otherwise return false.

All of these methods should be written using recursion.  Don't use any loops or iterators.

Use the "equals" method (rather than ==) to test whether two Objects are equal.

Test them out using a simple main program in the RecursiveList class.

Part Two.  Choose one of the other linked list classes that you are familiar with.  You may use the circular list from last week's lab, the list with head and tail pointers from class, or the doubly-linked list from Monday's class.  (My version of DoublyLinkedList.java is found in the lab3.jar file.)

Add the indexOf and remove(Object) methods to this class.  This time, you'll want to use a loop.

Part Three.  Use inheritance to write two implementations of SortedList.  One should be a subclass of RecursiveList and the other should be a subclass of the list class you used in part two of this lab.  Both of your classes should implement the SortedList interface provided to you in the lab3.jar file.

Most of the methods can be inherited directly from the unsorted list superclass.  The main exception to this is that you need to write 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).  You also need to override the add(int,Object) and set(int,Object) methods with methods so that they throw an UnsupportedOperationException.

Important:  Remember that constructors are not inherited, so you need to write your own.  In some cases, it may be enough to call the superclass constructor.  For the recursive sorted list however, it is essential that every "rest" be instantiated as a SortedRecursiveList rather than simply as a RecursiveList.  Otherwise, your recursive calls to add in the add method will use the add method of RecursiveList, which just adds at the end of the list.  You want the recursive add calls to add in order, so rest must be a SortedRecursiveList.

The same issue occurs with the "prepend" method, since it creates a new "rest" for the list it is applied to.  You need to override prepend with a method which creates a new SortedRecursiveList instead of a RecursiveList.  Other than that, the logic of prepend is the same.

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

Part Four.    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'.

Get and remove may be followed by either a name or an index.  Your program can tell the difference by checking the first character of the argument with the charAt method of String.  If the user gets a number, display the name found at that index.  If the user gets a name, indicate where that name is found in the list.  If the name occurs more than once in the list, indicate the range of indices where it is found.

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, get, or remove) 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 number command, display the name at the given position
• For a get name command, display the position at which the name is found (or a message to indicate that the name was not found)
  
• For a remove number command, display the name at the given position, and remove it
• For a remove name command, remove the name and display a message indicating that it was removed
  
• You can use a switch statement on the first character in the command word to choose between the three command words.  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.