CS 3500 Assignment #5 solution

Description

The purposes of this assignment are:
* to review Java interfaces

* to implement an iterator() method

* to prepare for future assignments

You will extend the implementation in Java of the FMap ADT that was specified in Assignment 4 by implementing the Iterable interface and by adding two public dynamic methods as 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 5 will be posted after the late submission deadline for Assignment 4.)

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 assignment 4. A test program (/course/cs3500sp13/Assignments/A5/TestFMap.java) will be provided.

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

Specification of the FMap ADT.

The FMap ADT remains as specified in assignment 4, except that it must now implement Iterable and must now provide the two new client-visible methods specified below.

The FMap ADT remains immutable.

The FMap class shall provide all of the methods specified in Assignment 4 with the exception that containsValue method should use the following algebraic specification.

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

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

= m0.containsValue(v) if m0.containsKey(k0)

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

= true if ! m0.containsKey(k0)

and v.equals(v0)

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

= m0.containsValue(v) if ! m0.containsKey(k0)

and ! v.equals(v0)

In addition, FMap class shall provide the following public methods:

Signature:

Dynamic methods (whose receiver is an FMap):

iterator: -> Iterator

iterator: java.util.Comparator -> Iterator

Specification of the iterator() method:

Returns an Iterator that generates every key k such that m.containsKey(k) is true, and generates each of those keys exactly once. The next() method of the Iterator returned by m.iterator() must throw a NoSuchElementException if it is called when no more keys remain to be generated, and the remove() method must throw an UnsupportedOperationException every time it is called.

Specification of the iterator(Comparator) method:

As above, with the additional constraint that the keys are generated in increasing order as determined by the argument passed to the iterator method.

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

Helpful Resources:

-Liskov – Chapter 6

-Sestoft Section 22.7

-Iterable API: https://docs.oracle.com/javase/6/docs/api/java/lang/Iterable.html

-Iterator API: https://docs.oracle.com/javase/6/docs/api/java/util/Iterator.html

-Collection Interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html