Exam 3: Data Structures

For each position in the list
  Swap the smallest remaining element into that position

import CursoredList;
import ListCursor;

/**
 * Strange static stuff from question A on exam 3 of CSC152 2000S.
 *
 * @author Hermione Hacker
 * @author Herman Hacker
 * @author Herr Doktor Professor Rebelsky
 * @version 1.0 of April 2000.
 */
public class CursoredListSorter 
{
  /**
   * Sort a cursored list, comparing things as strings.
   * Uses the selection sort algorithm.
   */
  public static void sort(CursoredList list) 
  {
    // Create a cursor.  This is the destination of each swap.
    ListCursor current = list.newCursor();
    // A second cursor identifies the smallest known element
    // of the list.
    ListCursor smallest;
    // Start at the beginning
    current.reset();
    // For each position in the list ...
    while (current.inList()) {
      // Find the smallest element in the sublist.
      smallest = findSmallest(list,current);
      // Swap the contents at the two positions.
      list.swap(current,smallest);
      // And move on.
      current.advance();
    } // while still in the list
  } // sort(CursoredList)

  /**
   * Put a cursor on the location of the smallest element
   * in a sublist that starts at a particular cursor.  Uses
   * string comparison to identify the proper place for an
   * element.
   * Pre: The sublist is nonempty.
   * Post: Does not move the starting cursor.
   */
  public static ListCursor findSmallest(CursoredList list, 
                                        ListCursor start)
  {
    // Our guess as to the smallest.
    ListCursor guess = start.makeCopy();
    // The string that corresponds to that guess.
    String guessString = 
      list.valueAt(guess).toString().toLowerCase();
    // A cursor we can use to iterate through the list.  Start
    // it at the next element.
    ListCursor temp = start.makeCopy();
    temp.advance();
    // For each remaining position in the list 
    while (temp.inList()) {
      // Get the contents.
      String tempString = 
        list.valueAt(guess).toString().toLowerCase();
      // If it's smaller, update our guess.
      if (tempString.compareTo(guessString) < 0) {
        guess.moveTo(guess);
        guessString = tempString;
      } // if it's smaller.
    } // while
    // That's it, we're done.
    return guess;
  } // findSmallest
} // class CursoredListSorted 

import CursoredList;
import ListCursor;
import SimpleOutput;

/**
 * A simple test of node-based cursored lists.
 *
 * @author Samuel A. Rebelsky
 * @author Carla Caffeinated
 * @author Carl Caffeinated 
 * @version 1.1 of May 2000
 */
public class CursoredListPrinter 
{
    public static void print(SimpleOutput out,
                             CursoredList list)
    {
        ListCursor printMe = list.newCursor();
        printMe.reset();
        while (printMe.inList()) {
          out.print(list.valueAt(printMe) + " ");
          printMe.advance();
        } // while
        out.println();
    } // print(SimpleOutput, CursoredList)
} // class CursoredListPrinter

    /**
     * Build a new cursored list containing the objects in
     * the given array (in the same order as in that array).
     */
    public NodeBasedCursoredList(Object[] initialValues) {
      // STUB
    } // NodeBasedCursoredList(Object[])

/**
 * A simple test program taken from section A of exam 3.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2000
 */
public class Exam3A {
     public static void main(String[] args) {
         NodeBasedCursoredList stuff =
             new NodeBasedCursoredList(args);
         CursoredListSorter.sort(stuff);
         CursoredListPrinter.print(stuff);
     }
} // Exam3A

import Dictionary;
import Entry;

/**
 * Hash tables that use the "shift into an empty space" strategy.
 *
 * @author Herman Hacker
 * @author Hermione Hacker
 * @author Thelma Thinker
 * @author Thomas Thinker
 * @author Samuel A. Rebelsky
 * @version 1.1 of April 2000
 */
public class ShiftyHashTable
    implements Dictionary
{

    // +--------+----------------------------------------
    // | Fields |
    // +--------+

    /** 
     * An array that contains all the elements in the
     * hash table.  An entry might be stored at location
     *    entry.getKey().hashCode() % entries.length
     * (or after, if that cell is full).  If null is stored 
     * in a particular cell, that cell is empty.
     */
    protected Entry[] entries;

    /**
     * The number of entries in the hash table.  Not
     * the same as entries.length, since some (hopefully
     * many) of the cells in entries will be null.
     */
    protected int numEntries;

    /**
     * The last place the findKey operation looked.  Useful
     * for the add routine.
     */
    protected int curLoc;

    // +--------------+----------------------------------
    // | Constructors |
    // +--------------+

    /**
     * Build a new hash table that should work relatively
     * well for up to maxEntries entries.
     */
    public ShiftyHashTable(int maxEntries) {
        this.numEntries = 0;
        this.entries = new Entry[maxEntries*2];
    } // ShiftyHashTable(int)

    // +------------+------------------------------------
    // | Extractors |
    // +------------+

    /**
     * Determine if a particular key is in the dictionary.
     */
    public boolean contains(Object key) {
        // Find the key.
        try {
            findKey(key);
            return true;
        }
        // If the key wasn't there, return false.
        catch (Exception e) {
            return false;
        }
    } // contains(Object)

    /**
     * Look up an entry in the dictionary.
     */
    public Object lookup(Object key)
          throws Exception
    {
        // Find the index for the key and return the
        // corresponding entry.  Since findKey throws
        // an exception if the key is not found, we don't
        // need to.
        return entries[findKey(key)].getValue();
    } // lookup(Object)

    // +-----------+-------------------------------------
    // | Modifiers |
    // +-----------+

    /**
     * Add an entry to the dictionary.
     */
    public void add(Object key, Object value)
          throws Exception
    {
        try {
            findKey(key);
            // Hmm ... it's there.  Can't re-add.
            throw new Exception("Already there");
        }
        catch (Exception e) {
            // It's not there.  Use curLoc.
            if (entries[curLoc] == null) {
                ++numEntries;
                entries[curLoc] = new Entry(key,value);
            }
            else {
                throw new Exception("No room");
            }
        } // catch (Exception)
    } // add(Object, Object)

    /**
     * Delete an entry in the dictionary.
     */
    public void delete(Object key)
        throws Exception
    {
        throw new Exception("STUB");
    } // delete(Object)

    // +---------+---------------------------------------
    // | Helpers |
    // +---------+

    /**
     * Determine the index of a particular key.  
     * @exception Exception
     *    If the key is not in the table.
     */
    protected int findKey(Object key) 
        throws Exception
    {
        // Determine the first place to look.
        int startLoc = key.hashCode() % entries.length;
        curLoc = startLoc;
        // Step through until we (1) find the desired
        // key; (2) find an empty space; or (3) return 
        // to where we started.
        do {
            // Is there no entry at the appropriate index?
            if (entries[curLoc] == null) {
                throw new Exception("Not found");
            }
            // Is an equal entry at the appropriate index?
            if (key.equals(entries[curLoc].getKey())) {
                return curLoc;
            }
            // Advance to the next index.
            curLoc = (curLoc + 1) % entries.length;
        } while (curLoc != startLoc);
        // We've wrapped around or hit null.  Give up.
        throw new Exception("Not found");
    } // findKey(Object)

} // class ShiftyHashTable

        // If the hash table is too full
        if (2*numEntries > entries.length) {
            // Then expand the hash table
            // STUB
        }