CS 3500 Assignment #4
Section:  Clinger
Assigned:  Tuesday, 25 September 2012
Due:  Tuesday, 2 October 2012

The purposes of this assignment are:

 * to review dynamic and static methods in Java
 * to review parametric polymorphism in Java
 * to continue our study of abstraction-based software design by
   implementing a third algebraic specification
 * to prepare for future assignments that will build upon this one

You will complete an implementation in Java of the FMap ADT
that is specified 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 following
instructions 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 (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.  A test
program (/course/cs3500wc/Assignments/A4/TestFMap.java) is
provided.

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

Specification of the FMap ADT.

FMap<K,V> is an immutable abstract data type whose values represent
finite functions from keys of type K to values of type V.

The FMap<K,V> ADT shall be implemented in Java, and will be tested
using Sun's Java 2 Runtime Environment, Standard Edition, version 1.6.0.
The code for this implementation shall be in the default package, and
shall define a public class named FMap.  The operations of the
FMap class shall be provided by the following public methods
of the FMap class:

Signature:

  Static methods:

    emptyMap     :                                  ->  FMap<K,V>
    emptyMap     : java.util.Comparator<? super K>  ->  FMap<K,V>

  Dynamic methods (for which the receiver is an FMap<K,V>):

    add          :  K x V                           ->  FMap<K,V>
    isEmpty      :                                  ->  boolean
    size         :                                  ->  int
    containsKey  :  K                               ->  boolean
    get          :  K                               ->  V
    toString     :                                  ->  String
    equals       :  Object                          ->  boolean
    hashCode     :                                  ->  int

Restrictions:

    Null arguments may not be passed to any of the above methods
    except for equals(Object).

Algebraic specification:

    FMap.emptyMap(c) = FMap.emptyMap()

    FMap.emptyMap().isEmpty()  =  true
    m0.add(k0, v0).isEmpty()  =  false

    FMap.emptyMap().size()  =  0
    m0.add(k0, v0).size()
        =  m0.size()                           if m0.containsKey(k0)
    m0.add(k0, v0).size()
        =  1 + m0.size()                       if ! (m0.containsKey(k0))

    FMap.emptyMap().containsKey(x)  =  false
    m0.add(k0, v0).containsKey(x)
        =  true                                if x.equals(k0)
    m0.add(k0, v0).containsKey(x)
        =  m0.containsKey(x)                   if ! x.equals(k0)

    m0.add(k0, v0).get(x)
        =  v0                                  if x.equals(k0)
    m0.add(k0, v0).get(x)
        =  m0.get(x)                           if ! x.equals(k0)

    m.toString() = "{...(" + m.size() + " entries)...}"

Values of the FMap<K,V> ADT shall also implement the public
dynamic methods equals(Object) and hashCode() such that

    If m1 is a value of the FMap ADT, then

        m1.equals(null) returns false.

    If m1 is a value of the FMap ADT, but x is not, then

        m1.equals(x) returns false.

    If m1 and m2 are values of the FMap ADT, then
    m1.equals(m2) if and only if

    for every non-null K k

            m1.containsKey(k) if and only if m2.containsKey(k)

    and for every non-null K k

            if m1.containsKey(k)
            then m1.get(k).equals(m2.get(k))

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

        m1.equals(m2)

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

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

        ! (m1.equals(m2))

    then m1.hashCode() is unlikely to be equal to m2.hashCode().

Note:  The word "unlikely" will be interpreted as follows.
For every type K and V, if both m1 and m2 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 FMap m having n == m.size() is

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

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

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

and the three probabilities above are independent

then the probability of m1.hashCode() == m2.hashCode() when
m1 and m2 are not equal is less than 40%.

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