COM 1205 Assignment #3.
Due: Thursday, 9 February 2000

Working in small teams that are assigned by the instructor,
you will design and code an implementation in Java of the
SearchTree ADT that is specified below.  Your implementation
of this module will be used by other students in a future
assignment.

Collaboration between members of different teams is forbidden.
Each team is responsible for keeping its design and code hidden
from other teams.  Part of each team's grade will be determined
by how well the team hides its code, and part of the grade will
depend upon the quality of the implementation.  A team that
resolves the security issues and submits an implementation of
the specified module that the instructor considers acceptable
for use in a large software project will earn an A.

The instructor will designate one member of each team as the
lead programmer for that team.  The lead programmer is
responsible for submitting the team's work, and has the final
say concerning all design, coding, and testing decisions.  The
lead programmer is also responsible for dividing the team's work
among its members, and for scheduling team meetings at times
that are convenient for the team.  The other members of the team
are responsible for advising the lead programmer, for reviewing
the team's design, code, and tests, and for any other teamwork
that may be assigned by the lead programmer.

All members of a team will receive the same grade.  Every
student will serve as lead programmer for some assignment during
the term.  The teams will change at the whim of the instructor.

The lead programmer is responsible for turning in the team's
work before 4 pm on the due date by sending electronic mail to

    will@ccs.neu.edu

with subject

    assignment #3

and a body that consists of the following, in the order shown:

    1.  The names of the team members.
    2.  Any remarks that the lead programmer wishes to make to
        the instructor concerning the team's work.
    3.  A line consisting of exactly 50 hyphens.
    4.  The code for SearchTree.java.

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

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

Specification of the SearchTree ADT.

SearchTree is an immutable abstract data type.  Its operations
shall have no side effects.  The SearchTree ADT shall be
implemented in Java using JDK 1.2.  The code for this
implementation shall be in the words package, and shall
consist of a single file named SearchTree.java.  This file shall
define a public class named SearchTree that defines the
following public static methods, which are specified below.

Signature:

    empty:                              -> SearchTree
    insert:   SearchTree x String       -> SearchTree
    contains: SearchTree x String       -> boolean
    isViable: SearchTree x String       -> boolean
    contains: SearchTree x StringBuffer -> boolean
    isViable: SearchTree x StringBuffer -> boolean

The algebraic specification of the SearchTree ADT relies upon an
additional operation, newTree, which is not visible to clients
of the ADT, and may not even exist as an identifiable operation
within any given implementation of the ADT.  If the newTree
operation does exist within an implementation, then it should be
hidden from client code.

    newTree: String x SearchTree x SearchTree -> SearchTree

Restrictions:  The String and StringBuffer arguments to these
operations shall not be null.

Algebraic specification:

Notation:
    t, t1, and t2 range over values of type SearchTree.
    s and s0 range over values of type String, and are not null.
    b ranges over values of type StringBuffer, and is not null.

    insert (empty(), s)
        =  newTree (s, empty(), empty())

If s.compareTo(s0) < 0, then
    insert (newTree (s0, t1, t2), s)
        =  newTree (s0, insert (t1, s), t2)

If s.compareTo(s0) == 0, then
    insert (newTree (s0, t1, t2), s)
        =  newTree (s0, t1, t2)

If s.compareTo(s0) > 0, then
    insert (newTree (s0, t1, t2), s)
        =  newTree (s0, t1, insert (t2, s))

    contains (empty(), s)
        =  false

If s.compareTo(s0) < 0, then
    contains (newTree (s0, t1, t2), s)  =  contains (t1, s)

If s.compareTo(s0) == 0, then
    contains (newTree (s0, t1, t2), s)  =  true

If s.compareTo(s0) > 0, then
    contains (newTree (s0, t1, t2), s)  =  contains (t2, s)

    contains (t, b)  =  contains (t, b.toString())

    isViable (empty(), s)
        =  false

If s.compareTo(s0) < 0 && s0.startsWith(s), then
    isViable (newTree (s0, t1, t2), s)  =  true

If s.compareTo(s0) < 0 && ! s0.startsWith(s), then
    isViable (newTree (s0, t1, t2), s)  =  isViable (t1, s)

If s.compareTo(s0) == 0, then
    isViable (newTree (s0, t1, t2), s)  =  true

If s.compareTo(s0) > 0, then
    isViable (newTree (s0, t1, t2), s)  =  isViable (t2, s)

    isViable (t, b)  =  isViable (t, b.toString())