5.7 Implementing the SortedPrintTable

< Day Day Up >

The SortedPrintTable can now be written using the promises contained in the PrintableSortable interface. The printAll method does not need to be changed, and the delete method is left for an exercise, so only the add method is different from the PrintTable class. The PrintTable class is implemented in Exhibit 10 (Program5.4b).

Exhibit 10: Program5.4b: The PrintTable Class

 public class SortedPrintTable {   private PrintableSortable psArray[];   private int currentSize;   /**    *  Constructor method. Create the table and set the    *  currentSize to 0 to indicate the table is empty.    */   public SortedPrintTable(int size) {     psArray = new PrintableSortable[size];     currentSize = 0;   }   /**    *  Delete method. Remove an object from the table. Note that    *  implementing this has been left as an exercise.    */   public void delete(PrintableSortable p) {   }   /**    *  Add method. Add an object to the table. Note that the gt    *  method from the Sortable interface is used to find the    *  place to insert this object.    */   public void add(PrintableSortable p) {     //To handle an empty table     if (currentSize = = 0)     {       psArray[0] = p;       currentSize = 1;       return;     }     //To handle a full table     if (currentSize = = psArray.length) {       return;     }     //Start from the bottom of the table, and move items out     //of the way until we find the place to insert.     for (int i = currentSize-1 ; i > = 0; - i) {       if (psArray[i].gt(p)) {         psArray[i+1] = psArray[i];         //Special Case to handle insertion at the start         //of the table.         if (i = = 0)          psArray[0] = p;       }       else {         //We have the right spot, so insert and stop the loop.         psArray[i+1] = p;         break;       }     }     currentSize = currentSize + 1;   }   /**    * printTable method. Go through the array and call the print    * method for each object stored.    */   public void printTable(){     for (int i = 0; i < currentSize; ++i)       psArray[i].print();   } }

The code for the add method is as follows. Before looking to see where to insert the record, two special cases are handled: (1) when the table is empty and no comparisons need to be made, the record is simply put in the first place in the table; and (2) when the table is full, for now the method simply returns. Obviously, it is incorrect behavior not to do something when the table is full, but to define the proper behavior requires the use of exceptions, which are covered in Chapter 6; no errors or exceptions are handled in this chapter.

Once the special cases are handled, the add method starts to process the array from the end and moves each item one place forward until it finds the correct place to put the item (this assumes that duplicates are allowed in the table). The point at which to insert the record is found by using the gt method on the PrintableSortable object to be inserted and the object in the array at the current position. As long as the object to be inserted is greater than the current array object, the array object is moved down one space in the list. When the object to be inserted is no longer greater than the current array object, the spot at which to insert the object has been found and the object is placed in the list. The question now raised is where is the gt method implemented? The answer is that it is not yet implemented. The SortedPrintTable knows that an object stored in the table and the parameter to the add method will have a gt method, but it does not know what that method is. Until an actual object is in the table and its runtime data type tag can be queried to find out what method to call, all that is known is that any object used will have a gt method. Finally it might seem counterintuitive to start at the end of the list rather than at the beginning of the list to find the position at which to insert the item; however, on average this algorithm takes half as long, assuming that duplicates are allowed, so that the item will always be inserted.

< Day Day Up >