CS 3500 Assignment #9
Assigned:  Wednesday, 7 November 2012
Due:  Tuesday, 20 November 2012

The purposes of this assignment are:

 * To implement the FMap<K,V> ADT with good worst-case efficiency
 * To give you an opportunity to implement red-black trees
 * To give you more design responsibility

You will modify your implementation of the FMap<K,V> ADT that
was specified in assignment 8 to make it efficient even in the
worst case.

Collaboration between students is forbidden on this assignment.
You are responsible for keeping your code hidden from all other
students.  Turn in your work on this assignment before 10 pm on
the due date by using the submit script as documented on the
course's main assignments web page,
http://www.ccs.neu.edu/course/cs3500wc/assignments.html

Your file of Java code should begin with a block comment that lists
    1.  The names of both students on the team, you want the
        instructor to write them.
    2.  The email addresses of both students.
    3.  Any remarks your team wishes to make to the instructor.

Part of your grade will depend on the quality, correctness, and
efficiency of your code, part will depend on your adherence to
object-oriented programming style and idioms as taught in this
course, part will depend on the readability of your code (comments
and indentation), and part will depend on how well you follow the
procedure above for submitting your work.  Late assignments may
be discounted, and very late assignments may be discarded.

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

Your assignment is to write the code for a single file,
FMap.java, that implements the specification below
as well as the specification of assignment 4, 5, 7, and 8.

You are given two files in /course/cs3500wc/Assignments/A9:

    Visitor.java
    TestFMap.java

The Visitor.java file defines the Visitor<K,V> interface.
The TestFMap.java file contains a simple test program.

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

Specification of the FMap<K,V> ADT.

The FMap<K,V> ADT remains as specified in assignment 8,
but several of its operations are now required to be
efficient even in the worst case.

Performance requirements:

    Suppose c is a comparator that runs in O(1) time, m is an
    FMap<K,V> that has been created by adding random key-value
    pairs to FMap.emptyMap(c), iter is an iterator obtained by
    evaluating m.iterator(), n is m.size(), and v is a Visitor<K,V>
    such that v.visit(K,V) runs in constant time.  Then

        m.add(k,v)            should run in O(lg n) time
        m.isEmpty()           should run in O(1) time
        m.size()              should run in O(1) time
        m.containsKey(k)      should run in O(lg n) time
        m.get(k)              should run in O(lg n) time
        m.iterator()          should run in O(n) time
        iter.hasNext()        should run in O(1) time
        iter.next()           should run in O(1) time
        m.accept(v)           should run in O(n) time                         !

    where all of those times are for the worst case.

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

Hint:  The most reasonable way to achieve that worst-case
efficiency is to implement (functional) red-black trees.

Hint:  Correct programs that achieve the above efficiency
for the average case but not for the worst case are likely
to earn substantially more partial credit than programs
that try to achieve the above efficiency for the worst case
but don't actually work.

Hint:  Correct programs that don't even try to be efficient
are likely to earn substantially more partial credit than
programs that try to be efficient but don't actually work.

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

The specification of hashCode() from assignment 8 is strengthened
as follows.

    If m1 and m2 are values of the FMap ADT, and

        m1.equals(m2)

    then m1.hashCode() == m2.hashCode().

    If f1 and f2 are values of the FMap<K,V> ADT, and

        !(f1.equals(f2))

    then f1.hashCode() is unlikely to be equal to f2.hashCode().

Note:  The word "unlikely" will be interpreted as follows.
For every type K and V, if both f1 and f2 are selected at
random from a set of FMap<K,V> values such that for every
non-negative integer n and int value h the probability
of a randomly selected f having n == f.size() is

    P(n) = 1/(2^(n+1))

and for each key k such that f.containsKey(k) the
probability that h == k.hashCode() is at most 1/5

and for each value v such that v.equals(f.get(k)) the
probability that h == v.hashCode() is at most 1/5

and the three probabilities above are independent

then the probability of f1.hashCode() == f2.hashCode() when
f1 and f2 are not equal is less than 2%.

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