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 Lab05 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 Lab06 and Lab07, 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 Lab05, 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 relevant application classes are provided to you. Your main task is to write a complete source file named OList.java, which defines both the member data and methods for an ordered list that stores its items in a linked list. You will have to make the OList API conform exactly to specifications given below. Otherwise, you only need to make sure that your OList does indeed store its data in a linked list (no arrays allowed this time).

However, 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 Lab06 and Lab07, 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 Lab05, in which you implemented an array-based ordered list. As you may recall, an Item object 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 to you for this lab.

In the same spirit of generosity, you will also be provided with the complete code for a paint() method which allows applications to render an OList graphically. You can just paste this code into your source file after you have implemented all the other OList methods.

After you have completed the OList class implementation as described below, you will be able to compile all the files and run the project. The paint() method provided to you for the OList class will explicitly display it as a linked list, similar to the way that Lab06 and Lab07 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 generates a console display of the complete list contents in the NetBeans IDE output window, as shown below:

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

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. Start the NetBeans IDE and mount a new filesystem named Lab08 (you will have to create this folder as part of the process). Then create a new project, also named Lab08.
2. Download the following files and import them into your Lab08 project folder:

   OListDisplayFrame.java

   DisplayPanel.java

   ControlPanel.java

   StatusPanel.java

   Node.java

   Item.java

   You have been provided with a complete set of javadoc pages fpr the classes defined in these files. For a quick overview, OListDisplayFrame is the class that contains the main() method for this project. The only task of main() is to create a toplevel application window, which is itself defined by this class. One special feature of this class is that it 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 object.

   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 a Node belonging to an OList. You should note that both the Node and Item classes are already implemented and ready to use in this project.

3. As noted in the introduction, you need to write your own complete version of a file OList.java that implements an OList as a linked list. This class should include a default constructor that creates an initially empty OList object. It must also contain the following methods, all of which are essential for the application to work correctly:
   1. public void insert (String value)
   2. public boolean remove (String value)
   3. public Item peek ()
   4. public boolean isEmpty ()
   5. public int getItemCount ()
   6. public void reset ()
   7. public void printAll()
   8. public void paint (java.awt.Graphics g, java.awt.Dimension winSize)

   You should now proceed to implement the bodies of the methods listed above, 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 as described in the Introduction, 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.

   The way to find the proper insertion point is provided by a standard 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.

3. peek() simply returns a reference to the Item contained in the first node in the list. If the list is currently empty, the return value is null.
4. isEmpty() must determine whether the list is currently empty and return the result.
5. getItemCount() must return the current number of Item objects stored in the list. Note that this is identical to the number of nodes in the list.
6. reset() must restore the OList to its original state, just as it was first constructed. This means that all items should be removed so that the list is again empty.
7. printAll() sets up a loop that traverses the list from the first to last nodes, using System.out.println() statements to print the data stored in each node. As described in the Introduction, the values are displayed in the output window of the NetBeans IDE. Note that this method is quite similar to the ones you implemented in Lab06 and Lab07, except that this time the complete Item is printed (using its toString() method).
8. paint() renders the complete OList in the application window as shown in the Introduction, using the specified Graphics object and the specified size of the display area. The size parameter is specified as a java.awt.Dimension object, which contains two public integer fields named width and height.

   Now if you did not already click the link above, it is time you did. This link contains the complete source code for paint(), so all you have to do here is download this text and paste it into your version of OList.java.

4. Once you have completed the implementation of the new OList class, try to compile your Lab08 project. Of course if you encounter any compiler errors, you will have to fix them all before you can proceed...
5. 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. Then package your final Lab08 project, including all your source files, into a JAR file. Upload this file to your dropoff directory.

Note: Be sure to set your FTP facility to binary mode to transfer a JAR file.