| 6.170 | Laboratory in Software Engineering
Spring 2000 Problem Set 3: Implementing Data Abstractions Due: February 24, 2000 Handout 7 |
Each assignment should be handed in as hardcopy to your TA or to the course secretary (Kincade Dunn, NE43-529) by 4:30 PM on its due date. It is usually most convenient to give the assignment to your TA at the end of class on that day. Additionally, the source and compiled code for each problem set should be made available on Athena so your TA can test your program.
You should put your solution to this problem set in ~/6.170/ps3.
See the general information sheet (handout 1) for more detail
You will also be required to rigorously test all of the operations for the data abstractions you implement. You will be required to hand in your tests together with a together with a justification of why your set of test cases gives a reasonable assurance that your implementation is correct.
A table is another widely used data structure. A table contains zero or more pairs, each containing a key and a value. The table's primary function is to implement a lookup operation which returns the value corresponding to a given key. Each key can only occur once in a given table.
|
|
| To check that there is no modification to a mutable object after you perform some operation on it, you should use the similar operation provided by the data abstractions. Note that you should therefore make it a priority to test your implementation of similar before testing any of the mutation operations, since the tests themselves will rely on having a correct implementation of similar. See Appendix D for more details. |
In this problem you will implement the DiGraph abstraction.
In this problem you will construct test cases sufficient to convince the client that your implementation of the DiGraph abstraction is valid.
public Table()
// effects: Initializes this to
be an empty table
public boolean similar(Object o)
public Object lookup(Object key) throws NotFoundException
/* effects: If <this> contains some
association (key, x), returns x.
*
Else, NotFoundException
*/
public void insert(Object key, Object value) throws
DuplicateException
/* modifies: <this>
* effects: adds the association
(key, value) to <this>
*
with no additional modification to <this>, unless:
*
Some association (key, x) already present in <this>
*
=> DuplicateException, no modification to <this>
*/
public void change(Object key, Object newValue) throws
NotFoundException
/* modifies: <this>
* effects: replaces the association
(key, x) in <this> with
*
(key, newValue), with no additional modification to
*
<this>, unless:
*
No entry for <key> exists in <this>
*
=> NotFoundException
*/
public void delete(Object key) throws NotFoundException
/* modifies: <this>
* effects: removes the association
(key, x) from <this>, unless:
*
No entry for <key> exists in <this>
*
=> NotFoundException, no modification to <this>
*/
public boolean isEmpty()
/* effects: If <this> contains no
associations, returns true
*
Else returns false
*/
public Iterator keys()
/* effects: returns a generator
that will produce each key stored
*
in <this> exactly once, in arbitrary order.
* requires: <this> not modified
while the returned generator is
*
in use.
*/
Appendix B: DiGraph Specification
/* Overview:
* A DiGraph is a mutable directed graph.
* It is a pair <N, E>, where
* N is the set of nodes in the graph and
* E is the set of edges between nodes in N.
* Each node is an immutable Object.
* Each edge is a pair <from-node, to-node>, where
from-node and
* to-node are in N. The is at most one edge
from any node to
* another node.
*/
public DiGraph()
// effects: Initializes <this> to
be an empty directed graph
public boolean similar(Object o)
public void addNode(Object node) throws DuplicateNodeException
/* modifies: the node set N for <this>
* effects: adds <node>
to N, with no further modifications to N,
*
unless:
*
<node> is already in N,
*
=> DuplicateNodeException, no modification to <this>
*
*/
public void addEdge(Object initialNode, Object finalNode)
throws NoNodeException, DuplicateEdgeException
/* modifies: the edge set E for <this>
* effects: adds an edge from
<initialNode> to <finalNode> to E,
*
with no further modifications to E,
*
unless:
*
<initialNode> or <finalNode> is not in the node set
*
for <this>
*
=> NoNodeException, no modification to <this>
*
some edge already exists from <initialNode> to
*
<finalNode> in E
*
=> DuplicateEdgeException, no modification to <this>
*/
public void addNodeAndEdge(Object initialNode, Object
newNode)
throws NoNodeException, DuplicateNodeException
/* modifies: the node set N for <this>,
the edge set E for <this>
* effects: adds <newNode>
to N, and adds an
*
edge from <initialNode> to <newNode> to E, with no
*
further modification to <this>,
*
unless:
*
<newNode> is already in N
*
=> DuplicateNodeException
*
<initialNode> not in N
*
=> NoNodeException, no modification to <this>
*/
public void removeEdge(Object initialNode, Object
finalNode)
throws NoEdgeException
/* modifies: the edge set E for <this>
* effects: removes the edge
from <initialNode> to <finalNode>
*
from E, with no further modification to <this>,
*
unless:
*
Either of the nodes <initialNode> or <finalNode> is
*
not in the node set for <this>, or no edge from
*
<initialNode> to <finalNode> exists in E
*
=> NoEdgeException, no modification to <this>
*/
public boolean hasEdge(Object initialNode, Object
finalNode)
throws NoNodeException
/* effects: If <initialNode>
or <finalNode> are not in the node
*
set for <this>, throws NoNodeException.
*
Else If an edge exists from <initialNode> to
*
<finalNode> in the edge set for <this>, returns
*
True.
*
Else returns False.
*
*/
public Iterator nodes()
/* effects: returns an Iterator
that will produce each node in
*
the node set for <this> exactly once, in arbitrary order.
* requires: <this> not be modified
while the returned Iterator is
*
in use.
*/
public Iterator successors(Object initialNode) throws
NoNodeException
/* effects: returns an Iterator
that will produce each node
*
that is
*
(1) in the node set N for <this>
*
and (2) a direct successor of <initialNode>,
*
exactly once, in arbitrary order. Unless:
*
<initialNode> is not in N
*
=> NoNodeException
* requires: <this> not be modified
while the returned Iterator is
*
in use.
*/
Appendix C: UnmodifiableIterator
UnmodifiableIterator is provided as a convenience class so that you do not need to implement the extra methods defined by the JDK's java.util.Iterator interface.
public abstract class UnmodifiableIterator implements Iterator {
public abstract boolean hasNext();
// effects: returns true if there are more elements
to yield
//
else returns false
public abstract Object next() throws NoSuchElementException;
// modifies: this
// effects: If there are more results to yield,
returns the next
//
result and modifies the state of this to record the
//
yield. Otherwise, throws NoSuchElementException
public final void remove() throws UnsupportedOperationException
// effects: throws UnsupportedOperationException
}
UnmodifableIterator is an abstract class; it provides partial implementation of a specification, but cannot be instantiated directly. Instead, you can subclass UnmodifableIterator and implement only the hasNext() and next() operations to make concrete implementations of Iterators, which can then be used anywhere that normal Iterators can be. We will go over subtyping and subclassing in detail in later lectures; we are not providing UnmodifiableIterator as an example of good use of subclassing, but rather as a way to implement your Iterator abstractions in almost exactly the same manner defined in the text. Here is an example use of UnmodifiableIterator, adapted from the text, pg. 132. Note that the only necessary change to the code given in the text has been highlighted.
public class Poly {
private int[] trms;
private int deg;
public Iterator terms() { return new PolyGen(this); }
// inner class
private static class PolyGen extends UnmodifiableIterator
{ // was "implements Iterator"
private Poly p; // the
Poly being iterated
private int n;
// the next term to consider
// constructor:
PolyGen(Poly it) {
// requires: it != null
p = it;
if (p.trms[0] == 0) n = 1; else n = 0; }
// methods
public boolean hasNext()
{ return n <= p.deg; }
public Object next()
throws NoSuchElementException {
for(int e = n; e <= p.deg; e++)
if (p.trms[e] != 0) { n = e + 1; return new Integer(e); }
throw new NoSuchElementException("Poly.terms");
} // end PolyGen
}
}
Appendix D: Similarity
Some of the operations on Table and Graph guarantee that (sometimes under certain conditions) that there is no modification to the object being operated on. For the Table case, the intuitive way to test this guarantee is to
Thus, to work around this, we introduce the notion of similarity, and require that you implement the similar operation on the two specifications we have given you. Note that it is standard practice not to included a written specification of similar, because its specification should be the same on any class for which it is defined (see the text for more details). Two objects are similar if it is not possible to distinguish among them using any observers of their type. Note that similarity of two objects does not necessarily hold throughout the entire execution of a program, because two objects that are similar at one point may be mutated in some way during execution and lose their similarity, or vice versa. Note also that just because performing some observer operation on two objects results in different return values does not always imply that two objects are not similar. For example, the keys() method of table returns an Iterator that traverses the keys in arbitrary order, and so just because two tables' Iterators return different keys on the first call to Iterator.next() does not imply that the two tables have a different set of keys; the same table is allowed to return two differently ordered Iterators on successive calls to keys, so having differing first keys does not necessarily distinguish the two tables. Instead, we must run both Iterators until they have finished traversing their respective set of keys; we call this a complete traversal.
To help you in implementing the similar operation, we explain here the ways to evaluate the conditions for similarity solely in terms of the observer operations for Table and DiGraph. This way your implementations of similar do not have to know anything about the internal representations you used for your data abstractions. You are not required to implement similar using the conditions given here, but we recommend it, at least for your first pass at an implementation.
For two tables t1 and t2, there are two conditions
for similarity (for there are two observers that we must ensure cannot
distinguish between t1 and t2).
Let s1 be the set of keys returned by a complete traversal by
t1.keys(),
and
s2 be the set of keys returned by a complete traversal by t2.keys().
Then
In implementing the similar operation (and only the similar operation), you may use two java.util.HashSet objects (or some other implementation of the java.util.Set interface) to store the intermediate values returned by the Iterators that your objects produce, and then compare the two sets for equality using the equals() operation. (Yes, this use of equals completely contradicts the notions of equality given in the text and in this appendix; the designers of the JDK used a much looser definition of object equality than 6.170 does)