[revised 22 April 2002]

COM 1204 Assignment #3.
Due: Friday, 26 April 2002

You will implement the SearchTable ADT specified below.
Class files compiled from your code may be used by other
students in a future assignment.

Collaboration between students is forbidden on this assignment.
You are responsible for keeping your code hidden from all other
students.  Part of your grade will be determined by

    how well you hide your code
    how well you follow instructions for submitting your code
    the correctness of your code
    the readability of your code

Turn in your work on this assignment before 4 pm on the due
date by sending electronic mail to

    will@ccs.neu.edu

with subject

    COM 1204 assignment #3

and a body that consists of nothing but your SearchTable.java
file.  That file must begin with a Java block comment that lists

    1.  Your name, as you want the instructor to write it.
    2.  Any remarks that you wish to make to the instructor.

Late assignments may be discounted, and very late assignments
may be discarded.

Your email must be sent as plain text, with no MIME or HTML
encoding, and must not include any signature lines or other
stray characters that would prevent your code from compiling
and running.  Furthermore your code should follow the other
guidelines announced in class.

--------------------------------------------------

Your assignment is to write the code for a single file,
SearchTable.java, that defines SearchTable as a class in the
default (top-level) package.  Class files for an implementation
of the SeqInt ADT and a Java file of sample test code is in

    /course/com1204/.www/will/Assignments/A3/

Your definition must work not only with this test code, but
with any other correct implementations of the SeqInt ADT and
with any other correct tests.  In short, your implementation
must behave as specified below.

--------------------------------------------------

Specification of the SearchTable ADT.

SearchTable is an immutable abstract data type.  Its operations
shall have no side effects.  The SearchTable ADT shall be
implemented in Java, and will be tested using Sun's Java 2
Runtime Environment, Standard Edition.  The code for this
implementation shall be in the default package, and shall
consist of a single file that defines a public class named
SearchTable that defines the following public static methods,
which are specified below.

Signature:

    empty:                                -->  SearchTable
    insert:      SearchTable x int x int  -->  SearchTable
    containsKey: SearchTable x int        -->  boolean
    lookupKey:   SearchTable x int        -->  int
    keys:        SearchTable              -->  SeqInt

Algebraic specification:

    containsKey (empty (), k0)  =  false
    containsKey (insert (t, k, n), k0)  =  true        if k = k0
    containsKey (insert (t, k, n), k0)
        =  containsKey (t, k0)                         otherwise

    lookupKey (insert (t, k, n), k0)  =  n             if k = k0
    lookupKey (insert (t, k, n), k0)
        =  lookupKey (t, k0)                           otherwise

    keys (t)  =  specSort (specKeys (t))

where

    specKeys:  SearchTable  -->  <set of int>
    specSort:  <set of int>  -->  SeqInt

    specKeys (empty())  =  { }
    specKeys (insert (t, k, n))  =  { k } \union specKeys (t)

    specSort ({ })  =  SeqInt.empty()
    specSort ({ k })  =  SeqInt.singleton()
    specSort (S1 \union S2)
        =  SeqInt.concat (specSort (S1), specSort (S2))
                    if forall s1 \in S1 forall s2 \in S2 s1 < s2

--------------------------------------------------