In this lab you will again finish a partially written Java GUI application that demonstrates the basic functions of an ordered list. This project is similar to Lab06, but it implements the OList class as a linked list instead of an array. Many features of the linked list itself are identical to those you encountered in Lab07 and Lab08, where you performed similar revisions of the Stack and Queue classes.

First you should recall the rules for manipulating an ordered list. In this case there is some underlying ordering scheme imposed on the list, as for example lexicographic ordering for String values. The rules for insertion and removal must both maintain this order, as must any other method that modifies the list contents. In particular, the rules for insertion and removal may be stated as follows:

• To insert an item into an empty list, no special rules apply. But for a nonempty list, the insertion method must first search through the current items to locate the position where the new value should be inserted to maintain the proper order. It must then insert the item at that position.
• To remove an item, you must identify it by its value rather than its location within the list (which you normally will not know). The removal method must then search through the list for this value and remove it if it is found, adjusting the list as necessary to maintain the proper order. Note that the specified value might not occur in the list, so the method should provide a way to indicate whether the item was actually removed.

As in Lab06, these rules and the underlying list structure will be refined to allow for the possibility of multiple occurrences of a specified data value in the list. In particular, you will be able to invoke the insertion method repeatedly with the same value, so that the list can contain multiple occurrences of that value. Also, each invocation of the removal method should only remove one occurrence of the specified value. At any time, the list will also be able to provide the net occurrence count (number of insertions minus number of removals) for any specified value.

As usual, the GUI test framework has already been created and tested, and source files for the framework classes are provided to you. Your main task is to complete a partially written source file named OList.java, which defines the instance variables and methods for an ordered list that stores its items in a linked list.

For this lab you will be given a complete source file for the Node class that represents the individual nodes in the linked list. The version of the Node class used in this lab is similar to those you encountered in Lab07 and Lab08, but this time the data stored in a node is an Item object rather than a String. You have already encountered the Item class in Lab06, in which you implemented an array-based ordered list. Recall that an Item stores both a String value and an associated occurrence count, indicating the number of times that value has been inserted into the list. Thus each node in the list contains a unique String along with its occurrence count. A complete source file for the Item class will also be provided for this lab.

After you have completed the OList class implementation as described below, you will be able to build and run the project. The paint() method provided for the OList class will explicitly display it as a linked list, similar to the way that Lab07 and Lab08 rendered linked-list Stack and Queue objects. Thus for an empty OList (with no nodes present), you will see only a null link labeled Start as shown below:

If you now inserted several names in any order, with some names repeated, say for example

the names would appear in lexicographical (alphabetic) order as shown below:

If you now entered John in the text box just to the left of the Remove button and then clicked the Remove button, you would remove one occurrence of John from the list:

If you went on to remove all occurrences of a value, the node containing that value will be removed from the linked list. Thus if you removed the one remaining occurrence of John, the list would appear as shown below:

The OList will also be provided with a peek() method that allows an application to determine the first data value (and its occurrence count) without removing it. If you clicked the Peek button when the list appeared as shown above, you should see the following:

Clicking the Print All button raises a dialog box showing all the values in the list, along with their associated occurrence counts:

To enable this feature, the OList class will be provided with a printAll() method similar to the ones you implemented in Lab07 and Lab08.

Finally, the list will have a reset() method that will be invoked whenever the user clicks the Reset button. Of course this method reinitializes the OList, so that it would again appear as in the first image above.

When you have built this project, you should test it using similar examples to make sure that all your OList methods are working correctly.

To complete this project, follow the steps listed below:

1. Login and enter the directory csci/202/labs. If this directory does not already exist, create it now.
2. Launch the NetBeans IDE, select the File/New Project... option in the toplevel menu bar, and create a new project named Lab09. Define the project to be a General Java Application, and accept all the default settings so that NetBeans will automatically write a class lab09.Main for you. You should find the source file for this class in Lab09/src/lab09.
3. Download the following files and import them into your Lab09/src/lab09 project folder, which will automatically included them all in your Lab09 project:

   DisplayFrame.java

   DisplayPanel.java

   InfoDialog.java

   ErrorDialog.java

   OList.java

   Node.java

   Item.java

   Paintable.java

4. Open the file lab09.Main and add the following lines of code into its main() method:

   	DisplayFrame frame = new DisplayFrame();
   	frame.setVisible(true);
   	frame.setInitialFocus();
   

5. Once you have assembled all these files, you should immediately be able to generate a set of Javadoc pages fpr the classes they define. But for a quick overview, the only task of the main() method in lab09.Main is to create a DisplayFrame, which is the toplevel application window for this project. The DisplayFrame includes a single OList object as part of its member data. The DisplayPanel class represents the central portion of the application window, which will graphically display the current state of the OList.

   Of course the Node class defines a single node, the basic building block for a linked list. Finally, the Item class represents the data item stored in each Node of an OList. Note that both the Node and Item classes are fully implemented and ready to use in this project.

6. Your primary task in this lab is to complete the partially written source file OList.java, by implementing the following two methods:
   1. public void insert (String value)
   2. public boolean remove (String value)

   You should now proceed to write these methods so that they perform the following tasks:

1. insert() must first search the list, to find the proper location to insert an Item containing the specified value. But if the search reveals that this value is already in the list, insert() merely increments the occurrence count for that value and returns. If it turns out that this is the first occurrence of this value, insert() must create a new Item containing the value, and then create a new Node to hold that Item. Finally it must insert the new node into the list at the proper location, increment the list item counter, and return.

   Recall from Lab 06 that the way to find the proper insertion point is provided by the String instance method

   public int compareTo (String anotherString)

   This method allows a String object to compare itself (in an alphabetical sense) to another String object. If it is "less than" (alphabetically earlier) than the other string, then the return value is negative. If it is "greater than" the other string, the return value is positive. If the two string values are identical, the return value is zero. As an example, if a String variable str contains "Fred", then the return value from str.compareTo ("Alice") would be a positive integer.

   You should use this method within a loop that traverses the linked list, to determine the correct insertion point for the input value. Of course you must allow for the possibility that the input value is greater than anything currently in the list. You must also be especially careful if it turns out that the new value belongs at the start of the list...

   Finally, insert() must increment the OList item counter if (and only if) a new Item was actually inserted.

2. remove() must first search the list for a Node containing an Item that itself contains the String value specified by the input parameter. If the matching Item is found, its occurrence count must be decremented. If (and only if) the decremented value then becomes zero, the node containing that Item must itself be removed from the list. In this case, remove() must also decrement the list item counter (which counts the number of distinct nodes in the list, not the occurrences of a given value).

   Finally, remove() must return true if it actually removes an occurrence of the specified value, and false if that value was not found in the list.

7. Once you have completed the implementation of the new OList class, try to compile your Lab09 project. Of course if you encounter any compiler errors, you will have to fix them all before you can proceed...
8. Run the project. You should now verify the application behavior as described in the Introduction. You should experiment with several sequences of inserting and removing data. Verify especially that the graphical representation of the OList changes in the way you would expect.

When your project is complete and working correctly, demonstrate it to your lab instructor. Before you leave, make sure that NetBeans has generated a JAR file for your project that contains all your source and bytecode files. You should find this JAR file in the directory csci/202/labs/Lab09/dist.