CS 3500 Assignment #7
Assigned:  Tuesday, 23 October 2012
Due:  Tuesday, 30 October 2012

The purposes of this assignment are:

 * To implement the FMap<K,V> ADT more efficiently
 * To give you more design responsibility

For this assignment, you will improve the average-case
performance of the FMap<K,V> ADT that was specified in
assignments 4 and 5.  These improvements are expected only
for FMap<K,V> values that are built out of an empty FMap<K,V>
for which a Comparator<? super K> was provided.

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.  Your name, as you want the instructor to write it.
    2.  Your email address.
    3.  Any remarks that you wish to make to the instructor.

Part of your grade will depend on the quality and correctness
of your code, part will depend on the readability of your code
(including comments and indentation), part will depend on the
efficiency of your code, 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 will
be discarded.

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

Your assignment is to write the code for a single file,
FMap.java, that implements the specification given in
assignments 4 and 5 together.  A test program
(/course/cs3500wc/Assignments/A7/TestFMap.java) is provided.

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

Specification of the FMap<K,V> ADT.

The FMap<K,V> ADT remains as specified in assignment 4 and 5,
with this additional specification of its performance:

    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(), and n is m.size().  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

    where all of those times are for the average case.

    The average efficiency will be evaluated probabilistically
    by drawing keys and values at random from very large finite
    sets of keys and values.

Note on the equals(Object) method:

    FMap.emptyMap(c).equals(FMap.emptyMap()) and
    FMap.emptyMap().equals(FMap.emptyMap(c)).

    More generally, the specification of equals(Object) remains
    as in assignment 4, so whether a Comparator was supplied for
    FMap values m1 or m2 has no bearing on whether m1 and m2
    are considered to be equal.  To make that even clearer, it
    is possible for m1.equals(m2) to be true even if m1 has a
    Comparator and m2 does not, and vice versa.

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