|
10/7 Recitation 5
- Where AF and RI Appear in Your Code
- When to Call checkRep()
- How to Call checkRep()
- My DirectedMultiGraph ADT (A Blast From the Past)
The abstraction function and rep invariant should appear at the top of your class
in a block-style Javadoc comment that starts with a single asterisk. It does not use
the double asterisk because it talks about your representation and therefore has
no business in the public Javadoc.
The implementation for the test of your RI should follow directly after the spec for the RI.
Like all code, keeping the spec near the implementation helps a programmer remember to update
one when he or she updates the other. The signature for checkRep() should always
be:
private void checkRep()
because it should not be part of the public API for your ADT. No return type is needed
because it will only signal a failure by throwing an unchecked exception.
It should be an unchecked exception because this is an avoidable condition
that should never happen through ordinary use of the ADT. Further, from a more pragmatic standpoint,
it would be extremely irritating for the client to deal with a checked exception
from every method in your ADT that calls checkRep(). Finally, be sure to include a
helpful error message with your unchecked exception, as this message will help you use
checkRep() to debug your ADT.
Here is a template for your code, using an abstraction function and a rep invariant:
public class MyClass {
/*
* AF(r) =
* description of your abstraction function appears here
*
* RI =
* description of your rep invariant appears here
*/
/** determines if the RI is tested when checkRep() is called */
private static final boolean CHECK_REP_ENABLED = true;
private void checkRep() {
if (!CHECK_REP_ENABLED) { return; }
// an implementation of the RI that
// throws a RuntimeException with a descriptive
// error message if the RI has been violated
}
// the fields, constructors, and methods of your class
}
Note the use of CHECK_REP_ENABLED to toggle whether checkRep() is "on" or "off."
Your checkRep() method may be computationally expensive, so you may need to disable it
when your ADT is used in production. However, while you are developing your ADT, checkRep()
should always be enabled. Using this template allows you to control the use of checkRep()
from a single point in your code.
This is far better than littering your code with lines like this:
if (CHECK_REP_ENABLED) { checkRep(); }
Preferring the above template for its use of CHECK_REP_ENABLED
is a good example of how to eliminate duplicate code.
Whenever you are writing duplicate code, you should think about how to generalize
the duplicate information, and then how you can abstract it out and write it in only one place.
This is almost always possible, and it reduces bugs and makes your code maintainable,
so be conscious of eliminating duplicate (aka "copy-and-paste") code.
As you remember, you should call checkRep() when:
- you exit a constructor
- you enter a public method
- you exit a public method
- you enter an observer method
- you exit an observer method that has side-effects
Some people seemed to feel that their lives were incomplete because it's not a rule to
always call checkRep() before leaving a public observer method,
but consider the following accessor method:
public int getX() {
return x;
}
Where can we put checkRep()? The only way to put checkRep()
in here twice would be overkill:
public int getX() {
checkRep();
int theX = x;
checkRep();
return theX;
}
As you can see, this is a bit silly (and wasteful), so the following is sufficient:
public int getX() {
checkRep();
return x;
}
When you have a method that can exit from multiple points in the code,
it may be difficult to be sure that there is a checkRep
that goes with every return statement.
The proposed solution to this problem is to use the finally keyword.
In Java, finally is used to delimit a block of code that gets
executed regardless of the results of the try block that precedes it.
Thus, instead of this method that has checkRep in five places:
public int compareTo(Object obj) {
checkRep();
if (!(obj instanceof Card)) {
if (obj == null); {
checkRep();
throw new NullPointerException("obj is null in Card.compreTo()");
} else {
checkRep();
throw new ClassCastException("obj is not a Card in Card.compareTo()");
}
}
Card c = (Card)obj;
int valComp = getValue().compareTo(c.getValue());
if (valComp != 0) {
checkRep();
return valComp;
} else {
int suitComp = getSuit().compareTo(c.getSuit());
checkRep();
return suitComp;
}
}
Use try and finally to use checkRep in two places:
public int compareTo(Object obj) {
checkRep();
try {
Card c = (Card)obj; // may throw ClassCastException
int valComp = getValue().compareTo(c.getValue()); // may throw NullPointerException
if (valComp != 0) return valComp;
return getSuit().compareTo(c.getSuit());
} finally {
checkRep();
}
}
This makes the code more readable as well as more maintainable.
I wrote the following was spec for DirectedMultiGraph when I did this problem set
as a 6.170 student back in the Spring of 2002:
public interface DirectedMultiGraph {
public Node createNodeInGraph(Object obj);
public Edge createEdgeInGraph(Node from, Node to);
public boolean removeNode(Node n);
public boolean removeEdge(Edge e);
public Iterator getNodes();
public int numberOfNodes();
public int numberOfEdges();
public boolean inGraph(Node n);
public boolean inGraph(Edge e);
}
Think about some [reasonable] operations that someone would want to perform on a directed multigraph.
With this specification, which operations would a client have to perform to do the following tasks:
- Determine if a particular object is a node in the graph.
- Get a list of edges in the graph.
- Add labels to the edges in the graph.
These are simple tasks that a client should expect to be able to accomplish easily; however,
this specification makes them unreasonably difficult.
Further, these are only a few of the things that clients of your ADT will want to do.
Think of other common tasks that clients may need to do and make sure that
the asymptotic runtime of the necessary operations is reasonable.
You can help yourself avoid these problems by writing your tests after you write your specs.
When you write tests, you write the type of code that a client of your ADT would write.
Thus, if there is a bug in your spec, then you will discover it before you have
started to implement your ADT if you write your tests first.
It is much cheaper to change the spec before the ADT is
implemented than afterwards. As an added bonus, writing your tests first will allow you
to take advantage of David Saff's Continuous
Testing Plugin for Eclipse (3.0 and later) when you are implementing your ADT.
This has been shown to help 6.170 students develop code faster because it helps them stay
focused and discover errors sooner.
Also, the names of these methods in my ADT are awkward and long. Look at Sun's API to get an idea of
what conventional method names are in Java.
Finally, this ADT introduces "helper" ADTs such as Node and Edge.
When designing an ADT, these additional ADTs often prove useful, but they are not always
exposed to the user. For example, LinkedHashMap uses Map.Entry; however,
Map.Entry is only visible to those who extend LinkedHashMap, so clients
of LinkedHashMap need not know about it. Sometimes exposing these helper ADTs to
the user may be necessary, but their use should be minimized to reduce the number of things
that client has to learn. Think carefully about what is necessary to expose to the client
in your DirectedMultiGraph ADT.
|