Exam 3: Data Structures

import Comparator;

/**
 * An object that knows how to search.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of November 1999
 */
public class BinarySearcher {
  /**
   * Search for an object u sing binary search.
   */
  public boolean binarySearch(BinarySearchable stuff, 
                              Object findMe,
                              Comparator compare) 
    throws Exception
  {
    if (stuff.isEmpty())
      return false;
    else if (compare.equals(findMe, stuff.middle()))
      return true;
    else if (compare.lessThan(findMe, stuff.middle()))
      return binarySearch(stuff.smaller(), findMe, compare);
    else
      return binarySearch(stuff.larger(), findMe, compare);
  } // binarySearch(BinarySearchable, Object, Comparator)
} // BinarySearcher

/**
 * Collections of objects amenable to search with binary search.
 * 
 * @author Samuel A. Rebelsky
 * @version 1.0 of November 1999
 */
public interface BinarySearchable 
{
  /** 
   * Get the ``middle'' key in the collection. 
   * Pre: The collection is nonempty.
   * Post: Returns some designated element in the collection.
   */
  public Object middle();

  /** 
   * Get elements in the collection that are smaller than the
   * middle element.
   * Pre: The collection is nonempty.
   * Pre: The collection has not been modified since the last call
   *   to middle.
   * Post: Returns the smaller elements.
   */
  public BinarySearchable smaller();

  /** 
   * Get elements in the collection that are larger than the
   * middle element.
   * Pre: The collection is nonempty.
   * Pre: The collection has not been modified since the last call
   *   to middle.
   * Post: Returns the larger elements.
   */
  public BinarySearchable larger();

  /**
   * Determine if the collection is empty.
   */
  public boolean isEmpty();
} // BinarySearchable

/**
 * An implementation of BinarySearchable using an array
 * along with bounds that determine the portion of the array
 * under consideration.  An attempt to turn some of the trickiness
 * in array-based binary search into something more general.
 *
 * At any point, we care only about the subarray of contents given
 * by lowerBound .. upperBound.
 *
 * @author Samuel A. Rebelsky
 * @author Your Name Here
 */
public class ProblemB
  implements BinarySearchable
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The array under consideration.  */
  private Object[] contents;

  /** The lower bound of the subarray under consideration. */
  private int lowerBound;

  /** The upper bound of the subarray under consideration. */
  private int upperBound;

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

  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

} // Problem B

import CursoredLinkedList;
import Pair;

/**
 * A simple implementation of dictionaries, using a list of
 * key/value pairs.
 *
 * @author Samuel A. Rebelsky
 * @author Your Name Here
 */
public class AssociationList
  implements Dictionary
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The pairs in the dictionary. */
  private CursoredLinkedList pairs;

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

  /** Create a new association list. */
  public AssociationList() {
    this.pairs = new CursoredLinkedList();
    // Because the find method skips the starting node,
    // we make sure the association list begins with an
    // unused pair.  It should always have this pair at the
    // front.
    pairs.addToFront(new Pair("FRONT",""));
  } // AssociationList()

  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Populate the association list with some sample pairs.
   * Intended primarily for testing.
   */
  public void populate() {
    pairs.addToEnd(new Pair("Joshua Vickery", "Undecided"));
    pairs.addToEnd(new Pair("Sierra Soleil", "Philosophy"));
    pairs.addToEnd(new Pair("Kate Ducey", "Theatre"));
    pairs.addToEnd(new Pair("Wanlin Liu", "Economics"));
  } // populate()

  /**
   * Get the value associated with a key.  See the interface
   * for more information.
   */
  public Object get(Object key)
    throws Exception
  {
    try {
      // Find the first pair with the appropriate key.
      pairs.front();
      pairs.find(new Pair(key, null));
      // If we got this far, find succeeded.
      return ((Pair) pairs.getCurrent()).getValue();
    }
    // Whoops!  Not found
    catch (Exception e) {
      throw new Exception(key.toString() + " not found");
    }
  } // get(Object)

  /**
   * Set the value associated with a particular key.  See the
   * interface for more information.
   */
  public void put(Object key, Object value) 
    throws Exception
  {
    // STUB
  } // put(Object,Object)

  /**
   * Convert to a string.
   */
  public String toString() {
    String result = "";
    pairs.front(); 
    try {
      while (true) {
        Pair p = (Pair) pairs.getCurrent();
        result = result + p + " ";
        pairs.advance();
      }
    }
    catch (Exception e) {
      // Hit the end of the list.
    }
    return result;
  } // toString
} // AssociationList

import AssociationList;
import SimpleOutput;

/**
 * Test association lists.  Takes advantage of some prior knowledge
 * about the magical "populate" method.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of November 1999
 */
public class ALTester {
  
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The association list we're testing. */
  AssociationList testme;
  /** Something to generate output with. */
  SimpleOutput out;

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

  public ALTester() {
    // Prepare to generate output.
    out = new SimpleOutput();
    // Set up the associatoin list.
    testme = new AssociationList();
    // Set up a sample set of key/value pairs for testing.
    testme.populate();
    // Look up a few names that are already there.  We check all
    // of them so that we hit all the positions.
    lookup("Joshua Vickery");
    lookup("Sierra Soleil");
    lookup("Kate Ducey");
    lookup("Wanlin Liu");
    // Capitalization should matter.
    lookup("joshua vickery");
    // Here's a name that's not there.
    lookup("sam rebelsky");
    // Add it.
    add("sam rebelsky", "CS");
    // Now it should be there.
    lookup("sam rebelsky");
    // Change Josh
    add("Joshua Vickery", "CS");
    lookup("Joshua Vickery");
    out.println("Final list: " + testme.toString());
  } // ALTester()

  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /** Look up a name in the association list. */
  public void lookup(Object key) {
    out.print("Looking up '" + key + "': ");
    try {
      out.println(testme.get(key));
    }
    catch (Exception e) {
      out.println("FAILED");
    }
  } // lookup(Object)

  /** Add a key/value pair to the list. */
  public void add(Object key, Object value) {
    out.print("Adding key: '" + key + "', value: '" + value + "' ...");
    try { 
      testme.put(key,value); 
      out.println("OK");
    }
    catch (Exception e) {
      out.println("FAILED");
    }
  } // add(Object,Object)  

  // +------+----------------------------------------------------
  // | Main |
  // +------+

  /** Test away. */
  public static void main(String[] args) {
    new ALTester();
  } // main(String[])
} // class ALTester

/**
 * A simple way of looking a trees.  Uses a cursor to support
 * retrieval of information in the tree.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of November 1999
 */
public interface CursoredTree {

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

  /**
   * Set the value stored in the root of the tree.
   * Pre: (none)
   * Post: The root of the tree now contains newRoot.
   *   The tree is nonempty.
   */
  public void setRoot(Object newRoot);

  /**
   * Set one of the children of the current node (given by the
   * cursor).  Children are numbered from 0 to numChildren-1.
   * Pre: The cursor is at a known location.
   * Post: The number of children is at least childNum-1.
   *   The childNum'th child contains newChild.
   */
  public void setChild(Object newChild, int childNum);

  /**
   * Clear the subtree starting at the current node.
   * Pre: The cursor is at a known location.
   * Post: The cursor is at the parent of the current location
   *   (as long as the cursor was not at the root).
   *   There is now a "hole" where the subtree was.
   */
  public void clear();

  // +-----------------+-----------------------------------------
  // | Cursor Movement |
  // +-----------------+

  /**
   * Move the cursor to the root of the tree.
   * Pre: (none)
   * Post: The cursor is at the root of the tree.
   */
  public void root();

  /**
   * Move the cursor up one level in the tree.
   * Pre: The cursor is not at the root of the tree.
   * Post: The cursor is at the parent of the current node.
   */
  public void parent();

  /**
   * Move the cursor down to a child.
   * Pre: The current node has at least childNum-1 children.
   * Post: The cursor is on the node representing the specified child.
   */
  public void child(int childNum);
   
  // +-----------+-----------------------------------------------
  // | Accessors |
  // +-----------+

  /**
   * Get the value associated with the current node.
   * Pre: There is a current node.
   * Post: Returns the value associated with the current node.
   */
  public Object getValue();

  /**
   * Get the number of children of the current node.
   * Pre: There is a current node.
   * Post: Returns the number of children associated with the current node.
   */
  public int getNumChildren();
} // interface CursoredTree