CS 3500 Assignment #8

Description

You will extend the implementation in Java of the FMap ADT that was specified in assignments 4, 5, and 7 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 11:59 pm on the due date by following instructions on the course’s main assignments web page, http://www.ccs.neu.edu/course/cs3500sp13/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. Assignments submitted between 12:00 am and 11:59 pm the day after the due date will receive a 20 percentage point penalty on the assignment.

—————————————————————————————————————————

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

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

Visitor.java

TestFMap.java

The Visitor.java file defines the Visitor 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 ADT.

The FMap ADT remains as specified in assignments 4, 5, and 7, except that it must now provide the public accept(Visitor) 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 class shall provide the following public dynamic method:

Signature:

accept: Visitor -> FMap

Specification:

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

FMap m2 = FMap.empty();

for (K k : m) {

V v = visitor.visit (k, m.get (k));

m2 = m2.put (k, v);

}

If m is an FMap created using the 1-argument version of FMap.empty, 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 that has been created by adding random key-value pairs to FMap.empty(c), iter is an iterator obtained by evaluating m.iterator(), n is m.size(), and v is a Visitor such that v.visit(K,V) runs in constant time. Then

m.put(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.containsValue(k) should run in O(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*lg 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) 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 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 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 10%.