Description
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 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. (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<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 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<K,V>
empty : java.util.Comparator<? super K> -> FMap<K,V>
Dynamic methods (for which the receiver is an FMap<K,V>):
put : K x V -> FMap<K,V>
isEmpty : -> boolean
size : -> int
containsKey : K -> boolean
containsValue: V -> boolean
get : K -> V
removeKey : K -> FMap<K,V>
removeValue : V -> FMap<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.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<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%.
