CS 3500 Assignment #4

Description

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 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. (The submission command for Assignment 4 will be posted after the late submission deadline for Assignment 3.)

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. A test program (/course/cs3500sp13/Assignments/A4/TestFMap.java) is provided.

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

Specification of the FMap ADT.

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

The FMap ADT shall be implemented in Java and will be tested on CCIS Linux machines with only their standard software. 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:

empty : -> FMap

empty : java.util.Comparator -> FMap

Dynamic methods (for which the receiver is an FMap):

put : K x V -> FMap

isEmpty : -> boolean

size : -> int

containsKey : K -> boolean

containsValue: V -> boolean

get : K -> V

removeKey : K -> FMap

removeValue : V -> FMap

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

FMap.empty().isEmpty() = true

m0.put(k0, v0).isEmpty() = false

FMap.empty().size() = 0

m0.put(k0, v0).size()

= m0.size() if m0.containsKey(k0)

m0.put(k0, v0).size()

= 1 + m0.size() if ! (m0.containsKey(k0))

FMap.empty().containsKey(k) = false

m0.put(k0, v0).containsKey(k)

= true if k.equals(k0)

m0.put(k0, v0).containsKey(k)

= m0.containsKey(k) if ! k.equals(k0)

FMap.empty().containsValue(v) = false

m0.put(k0, v0).containsValue(v)

= true if v.equals(v0)

m0.put(k0, v0).containsValue(v)

= m0.removeKey(k0).containsValue(v) if ! v.equals(v0)

m0.put(k0, v0).get(k)

= m0.get(k) if m0.containsKey(k)

m0.put(k0, v0).get(k)

= v0 if ! m0.containsKey(k)

and k.equals(k0)

FMap.empty().removeKey(v) = FMap.empty()

m0.put(k0, v0).removeKey(k)

= m0.removeKey(k).put(k0, v0) if ! k.equals(k0)

m0.put(k0, v0).removeKey(k)

= m0.removeKey(k) if k.equals(k0)

FMap.empty().removeValue(v) = FMap.empty()

m0.put(k0, v0).removeValue(v)

= m0.removeValue(v).put(k0, v0) if ! v.equals(v0)

m0.put(k0, v0).removeValue(v)

= m0.removeValue(v) if v.equals(v0)

m.toString() = “{…(” + m.size() + ” entries)…}”

Values of the FMap 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 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%.