CS 3500 Assignment #7 solution

Description

For this assignment, you will improve the average-case performance of the FMap ADT that was specified in Assignments 4 and 5. These improvements are expected only

for FMap values that are built out of an empty FMap for which a Comparator 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 11:59 pm on the due date by following instructions on the course’s main assignments web page, https://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 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. 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 given in Assignments 4 and 5. A test program (/course/cs3500sp13/Assignments/A7/TestFMap.java) will be provided.

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

Specification of the FMap ADT.

The FMap ADT remains as specified in Assignment 4 and 5, (a) without the removeKey and removeValue and (b) with this additional specification of its performance:

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

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.empty(c).equals(FMap.empty()) and FMap.empty().equals(FMap.empty(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.