In this lab you will finish a partially written Java GUI application that demonstrates the basic functions of an ordered list. This project is similar to your earlier Stack and Queue labs, but it involves yet another type of list with new rules for inserting and removing data. In this case there is some underlying ordering scheme imposed on the list, say for example alphabetical 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 a value 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 value at that position, moving other list components as necessary to make room for the new value.
• To remove an item from the list, 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, shifting other items as necessary to maintain the proper order. Note that the specified value might not occur in the list, so the method must provide a way to indicate whether the item was actually removed.

These rules, and the underlying list structure, should be refined slightly to allow for the possibility of multiple insertions of a particular value into the list. In particular, you should be able to invoke the insertion method repeatedly with the same value, in such a way that the list can keep track of all insertions of that value. In other words, the list should be able to report the number of occurrences of each value in the list. Also, each invocation of the removal method should only remove one occurrence of the named value.

In this lab you will implement a class OList as an example of an ordered list. The OList class will use an internal array implementation, similar to those used in your previous labs for the Stack and Queue classes. As in those labs, the GUI application will store String values in an OList object.

By this time you probably know the drill: the GUI test framework for this lab has already been created and tested, and a partially written source file for the OList class is also provided to you. Your task is to implement two essential OList methods, namely the ones which insert and remove data. The application will need both of these methods to work properly.

After you have completed the OList class implementation as described below, you should be able to compile all the files and run the project. Initially, the application should display the following window:

As in the previous labs, the GUI framework already includes event handlers that respond to user clicks on each of the buttons at the bottom of the window. These buttons are used to update a graphical display of an OList object in the middle of the window.

The internal OList array appears as the vertical pile of boxes, with the zeroth component on the bottom. But in constrast to the Stack and Queue displays, there are no arrows for special indexes such as top for a Stack or front and rear for a Queue. Also, for an OList the array components are not simply the String values themselves. Rather they are so-called Item objects, each of which stores a single unique String value and its associated occurrence count. This count represents the total number of times this particular String value has been inserted into the list.

The text boxes at the top of the window are used to indicate both the current number of items which have been inserted onto the list and its current capacity. In the array implementation used here, this means just the total size of the array.

To insert a String value into the OList, first enter the value in the text box to the left of the button labeled Insert. Then click the Insert button, or press Enter while the insertion text box has the focus. If this is a new value, it will appear as a new Item object inserted at the proper location within the list, with an initial occurrence count of 1. If an Item with this value is already in the list, the insertion merely increments its occurrence counter.

For example, the following image was taken after inserting the name "Mary" as the first item in the list:

The integer 1 that appears to the right of Mary indicates that one occurrence of that name has been inserted into the list. After inserting "Mary" a second time, you should see

After inserting several more names in any order, with some names inserted multiple times, the display should show an alphabetized list similar to the example below:

You might note that the array length has increased since the previous figure, which shows that the OList array will be automatically resized whenever it becomes full. As usual, the insert() method will quietly invoke setCapacity() as necessary. Since the Stack version of setCapacity() that you first implemented in Lab 03 will also work for an OList, this method has already been written for you in this lab.

To remove an occurrence of a particular value, enter that value into the text box to the left of the Remove button. Then either click the Remove button, or press Enter (which again will work if the removal text box has the focus). If the value is in the list, its occurrence count will be decremented. If this makes the count go to zero, the entire Item containing that value will be removed from the array. If the value is not in the list, you should see a dialog box appear with a message stating that the value was not found.

After removing one occurrence of "Charles" from the list in the figure above, you would see

If you kept on removing occurrences of "Charles" until there were none left, the entire array component containing "Charles" would be removed:

As in your earlier labs, the Trim button resizes the internal array to match exactly the number of stored items, or to a capacity of 1 if the list is empty. The Clear button removes all items from the list without changing its current capacity. Finally, the Reset button removes all items and resets the array to its initial capacity.

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 Lab06. Define the project to be a General Java Application, and accept all the default settings so that NetBeans will automatically write a class lab06.Main for you. You should find the source file for this class in the folder Lab06/src/lab06.
3. Download the following files and import them into your Lab06/src/lab06 folder, which will automatically include them all in your Lab06 project:

   DisplayFrame.java

   DisplayPanel.java

   ErrorDialog.java

   List.java

   OList.java

   Item.java

   Paintable.java

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

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

5. Once you have assembled all these files, you should immediately be able to generate a set of Javadoc pages for the classes they define. But for a quick overview, the only task of the main() method in lab06.Main is to create a DisplayFrame, which is the toplevel application window for this project. One special feature of the DisplayFrame 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.

   As you may already have noticed, the generic List class that first appeared in Lab 05 will also be used in this project. As before, List will serve as the abstract superclass of OList. This approach will enable the Olist class to inherit the same data and methods that made it easier for you to define array-based Stack and Queue classes. Also, the OList class will implement the same Paintable interface that was used in Lab 05 to simplify the GUI framework.

   The Item class is a new feature. Item defines the actual data type stored within each OList array location. Each Item object contains a String instance variable that represents the value of the object, and an int variable occurrences which is incremented each time an existing value is inserted. Thus a new Item is created and inserted into the OList array only if no other Item with the same value is found in the list. All later insertions of that value merely increment the occurrence counter in the existing Item. In other words, each Item stores a unique value within the OList array.

   Similarly, each removal of a particular value simply decrements the occurrence counter for the Item containing that value. However, in the special case when the item count drops to zero, the Item itself must be removed from the array.

6. The version of the OList class as defined in OList.java contains only stubs of the following methods, both of which are essential for the application to work correctly:
   1. public void insert (String value)
   2. public boolean remove (String value)

   Before proceeding, you should look over the prewritten contents of OList.java. Note in particular that the class definition already contains a complete setCapacity() method, which your insert() method will need to invoke whenever it must resize the array. The file also contains a complete paint() method, which enables the OList to render itself in the display window. If you implement all the methods listed above according to the following specifications, paint() will display the listas shown in the example figures in the Introduction.

   You should also glance through the file Item.java, to familiarize yourself with the Item class and its methods. If you have any questions about either of these files, please consult with your lab instructor.

   You should next proceed to write the bodies of the OList methods listed above, so that they perform the following tasks:

1. insert() must first search the array from index 0 upwards, to find the proper location to insert an Item containing its value parameter into the array. But as described in the Introduction, if the search reveals that the specified String value is already in the list, insert() merely increments the occurrence count for that value and returns.

   If this turns out that this is the first occurrence of this value, insert() must next check whether the current array is full, and if necessary invoke setCapacity() to make at least one available location. Then it must create a new Item containing that value, and insert the Item into the array at the proper location. Note that this step will first require you to shift all array components at and above this location upwards. In other words, each of these components moves one index higher in the array. This step creates the "hole" in the array at the point where the new Item must be inserted.

   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 return value is positive. If the two String objects 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 scans the array from index 0 upwards, to determine the correct position for the input value in the array. Of course you must allow for the possibility that the input value is greater than anything currently in the list...

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

2. remove() must first scan the array for the Item that contains the String value specified by its input parameter. If the matching Item is found, its occurrence count must be decremented.

   If (and only if) the decremented value becomes zero, the Item itself must be removed from the array. Of course this involves the business of filling in the "hole" left by the deleted Item. In this case, remove() must also decrement the array item counter (which counts the number of distinct values in the array, not the occurrences of a given value).

   Finally, remove() must return true if it actually removed an occurrence of the specified value, or 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 Lab06 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 list changes in the way you would expect.

When your project is complete and working correctly, demonstrate it to your lab instructor. Then, before you exit NetBeans, clean your Lab06 project. Finally, before you logout, open a terminal window and use the cd command to enter your csci/202/labs directory. Then create a JAR file of your Lab06 project folder, using the command

jar cf Lab06.jar Lab06