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

The purposes of this assignment are:

 * To implement the Visitor pattern.
 * To illustrate function objects.
 * To implement better hashCode() methods.

You will extend the implementation in Java of the FMap<K,V>
ADT that was specified in assignments 4 and 5 by adding the
public dynamic method specified below, and by improving the
hashCode() method so it satisfies the probabilistic specification
given below.

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, 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, and 7.

You will be given two files in /course/cs3500wc/Assignments/A8:

    Visitor.java
    TestFMap.java

The Visitor.java file defines the Visitor<K,V> interface,
so that file is essential for this assignment.  The
TestFMap.java file contains a simple test program; you
will undoubtedly want to supplement that test program with
further tests.

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

Specification of the FMap<K,V> ADT.

The FMap<K,V> ADT remains as specified in assignments 4, 5,
and 7, except that it must now provide the public accept<K,V>
operation specified below and must satisfy the augmented
performance specification given below.

In addition to the methods specified in assignments 4, 5, and 7,
the FMap<K,V> class shall provide the following public dynamic
method:

Signature:

    accept:  Visitor<K,V>  ->  FMap<K,V>

Specification:

    If m is an FMap<K,V> and visitor is a Visitor<K,V>, then
    m.accept(visitor).equals(m2) where m2 is the FMap<K,V>
    computed by

        FMap<K,V> m2 = FMap.emptyMap();
        for (K k : m) {
            V v = visitor.visit (k, m.get (k));
            m2 = m2.add (k, v);
        }

    If m is an FMap<K,V> created using the 1-argument version
    of FMap.emptyMap, then both m and m2 must satisfy the
    average-case efficiency requirements stated below.

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(K,V)         should run in O(n) 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:

    If m.containsKey(k), then there shall exist exactly one v
    such that m.accept(visitor) results in a call to
    visitor.visit(k,v).  That v shall be m.get(k).

    If m.containsKey(k) and m.get(k) is v, then m.accept(visitor)
    shall result in exactly one call to visitor.visit(k,v).

    If a comparator was provided for the empty FMap from which
    an FMap m was built up, then the visitor shall visit keys
    in the order specified by the comparator (with lesser keys
    being visited before greater keys).

    If no comparator was provided, then the ordering of the calls
    to visitor.visit(k,v) is unspecified.  In particular, some of
    those calls to visitor.visit(k,v) may be concurrent.  Clients
    who use the accept(Visitor<K,V>) method are responsible for
    any synchronization that may be necessary.

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

The specification of hashCode() from assignment 4 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/4

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

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 10%.

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