9. Incremental Development
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
At the end of the last lecture, we noted that there were several ways we could go about creating output from our model. We could make the print routine do all the work, we could add a printme() method to each class, or (the preferred alternative) we could use the Java convention that each class can have a toString() method used to create a string containing the printable representation of the class. Using the latter, our writeNetwork() routine will look like the following:
private static void writeNetwork() {
for (Intersection i: inters) {
System.out.println( i.toString() );
}
for (Road r: roads) {
System.out.println( r.toString() );
}
}
This creates a challenge. How do we go about building and testing this code. We could try to write complete, polished versions of everything, but that's a big job, and in general, small incremental steps are easier to work with.
Let's get something working that we can test before we worry about making it fully functional. Consider this version of toString() for the class Road:
String toString() {
return "road"
}
We'll make a similar routine for intersections, of course. With this, we can now do some real testing! Consider this input file:
intersection a intersection b road a b 45 road b a 72
When we try this, running the code as it stands so far, it fails in a rather unexpected way:
[HawkID@serv15 ~/project]$ java RoadNetwork input 'intersection' not a road or intersection
This is the output from the following code in RoadNetwork.readNetwork():
String command = sc.next();
if ((command == "intersection")
// Bug: Something about an intersection
inters.add( new Intersection( sc, inters ) );
} else if ((command == "road")
// Bug: Something about a road
roads.add( new Road( sc, inters ) );
} else {
Errors.fatal(
"'"
+ command
+ "' not a road or intersection"
);
}
Evidently, when command is the string "intersection" as read from the input file, it is not the same as the literal string "intersection" tested by the if statement.
In fact, it is not, because when the java == operator is applied to comparing two objects, it returns true only if they are the exact same object. This is not the same thing as returning true if the two objects have the same value.
An aside: This is a problem in every programming language that has pointers, also called object handles or references to objects. In every such language, comparing two pointers is different from comparing whether the objects referenced by those pointers have the same value. Here are some examples from various languages:
| Language | Pointer Comparison | Value Comparison |
|---|---|---|
| C | a == b | *a == *b |
| Pascal | a = b | a^ = b^ |
| Ada | a = b | a.all = b.all |
| Java | a == b | a.equals(b) |
The point of this aside is simple: This problem won't go away. Regardless of the language, you're stuck writing something ugly. (The second difference you might note between the above examples is unrelated - Ada and Pascal use a single equals sign for comparison, while C and Java double it. That is because Ada and Pascal use := for assignment. This is another ugly issue that won't go away; assignment and comparison are not the same thing.)
After we fix this bug, the program runs producing the expected output!
[HawkID@serv15 ~/project]$ java RoadNetwork input intersection intersection road road
Digging around in the code we've accumulated to this point, we have the following code in class Intersection:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
sc.nextLine();
// Bug: Check that remainder of line was blank?
}
public String toString() {
return "intersection";
}
Intersections have just one attribute, a name, and we could have returned that. Also, we can easily deal with the bug notice if we can figure out how to identify an empty string. There are several ways to do this:
a: if (s.equals( "" )) ...
b: if ("".equals( s )) ...
c: if (s.isEmpty()) ...
c: if (s.length() == 0) ...
d: if ((s == null) || s.isEmpty()) ...
Whis is best? Options a and c will fail if the the object s is a null object. That's a different thing from an empty string; a null string reference does not refer to any object.
Options b and d are bullet proof code! They always work. On the other hand, if you know that the string is not null, s.isEmpty() is and s.length()==0 are the fastest. These two should be expected to take exactly the same time, since s.isEmpty simply checks the length inside the String class, and the sequence of instructions "check length and then return" should be just the same speed as "return length and then check." This means we can rewrite the code as follows:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
if (!s.isEmpty()) {
Errors.fatal(
"Intersection '"
+ name
+ "' has non-empty line end '"
+ s
+ "'"
);
}
}
public String toString() {
return "intersection " + name;
}
This code is servicable, but note one problem: The code to handle end-of-line is long-winded and likely to be duplicated. We will need to do exactly the same check at the end of each line describing a road.
Duplicating this code would not cause problems unless someone decided to add a new feature such as end-of-line comments. At that point, it would be nice to put the end-of-line code in a single place. We could, for example, make a global method to deal with this, for example:
class SyntaxCheck {
/** Syntax checking support
*/
static void lineEnd( Scanner sc, String c ) {
/** Check for end of line on sc,
* Use c to provide context in any error message
*/
String s = sc.nextLine();
if (!s.isEmpty()) {
Errors.fatal(
c
+ " '"
+ name
+ "' has non-empty line end '"
+ s
+ "'"
);
}
}
}
With this we can rewrite our initializer for intersections as:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
// Bug: What if this intersection already exists
SyntaxCheck.lineEnd( sc, "Intersection" );
}
That's not too bad, but there is always an alternative way of solving the problem. In this case, we could have done the line-end check in the readNetwork() method. In this case, it fits naturally into the end of that method:
private static void readNetwork( Scanner sc ) {
while (sc.hasNext()) {
// until the input file is finished
String command = sc.next();
if (command.equals( "intersection" )
|| command.equals( "i" ) ) {
// Bug: Something about an intersection
inters.add( new Intersection( sc, inters ) );
} else if (command.equals( "road" )
|| command.equals( "r" ) ) {
// Bug: Something about a road
roads.add( new Road( sc, inters ) );
} else {
Errors.fatal(
"'"
+ command
+ "' not a road or intersection"
);
}
String s = sc.nextLine();
if (!s.isEmpty()) {
Errors.fatal(
command
+ " has non-empty line end '"
+ s
+ "'"
);
}
}
}
Note that we lost something here! Specifically, we no longer have easy access to identifying information for the interseciton. This is most likely the deal killer for this alternative.
The next problem we face shows up in several bug notices in our code. Here are the fragments that contain these comments:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
// Bug: What if this intersection already exists
// initializer
public Road( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
String sourceName = sc.next();
String dstName = sc.next();
// Bug: Must look up sourceName to find source object
// Bug: Must look up dstName to find destination object
In one case, we want to complain if an intersection definition contains an intersection that was already defined. In the other case, we want to look up the intersections a road connects and complain if they were not already defined. In the latter case, we almost certainly want to remember the identity of the intersection objects, and once we have that, we probably don't need to keep the strings sourceName and dstName, since each intersection knows its own name.
It turns out that Java has some built-in classes that can handle the problem of looking up a string and finding the object associated with it, classes HashMap and HashTable. We might well elect to use these later, but for two reasons, we will put this off: First, while there are a huge number of programming problems that you can solve by finding the appropriate pre-existing class, not all can be solved this way, and this particular problem is at just the right level to illustrate several important alternatives in program design. Second, as the universe of pre-defined library routines expands, it sometimes becomes faster to build from scratch instead of first learning a powerful library class and then figuring out how to customize it to solve your problem.
Ignoring the Java library's hash functions, note that there are at least three ways we could handle the string search problem:
First, we could simply make the list of all intersections globally visible. Many programming languages allow global variables to be declared at the outermost level, but in Java, the outermost level is reserved for classes, so global variables are created as public static components. As currently declared, the intersectin list, the inters field of RoadNetwork is static and not private. Therefore, any time we want to look up an interseciton, we have the option of doing the search directly:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
// check to see if the intersection already exists
for (Intersection i: RoadNetwork.inters) {
if (i.name.equals( name )) {
Errors.fatal(
"Intersection '"
+ name
+ "' is declared twice"
);
}
...
This code can be made to work, following this coding philosophy, each place in the code where the intersection list is searched involves duplicating or reinventing this code. Furthermore, each method that incorporates this code now ends up depending on internal knowledge of the existence of a List named inters that is a static component of the RoadNetwork class and on internal knowledge of the existence of a name field in every intersection. This kind of broad information sharing between classes is not generally a good idea.
The obvious improvement to this code is to package the search loop in its own method, so that only that method needs to know the internal details.
One way to reduce the information sharing is to pass the needed information around as parameters. This is the solution we actually set out to use in the skeleton code we wrote several weeks ago. The parameters are already there, so instead of referencing RoadNetwork.inters, we can write this code:
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the road definition
name = sc.next();
// check to see if the intersection already exists
for (Intersection i: inters) {
if (i.name.equals( name )) {
...
Of course, this code is just as bad as the previous example because it still does the search locally at each point where a search is needed, and because it still peeks into the class Intersection to look at the interseciton name. Those issues can be dealt with as above, by packaging the search in a new search method.
By passing the list of intersections as a parameter, we eliminate local knowledge of where the list is to be found. The customer, however, still knows that it is a list that can be iterated through.
Above, we've mentioned twice that the search can be packaged as a method. For example, we can put the search in the RoadNetwork class:
public class RoadNetwork {
static LinkedList inters
= new LinkedList ();
static LinkedList roads
= new LinkedList ();
static Intersection findIntersection( String s ) {
// return the intersection named s, or null if no such
for (Intersection i: RoadNetwork.inters) {
if (i.name.equals( s )) {
return i;
);
}
return null;
}
...
This allows us to write the initializaer for Interseciton like this:
// initializer
public Intersection( Scanner sc ) {
// code here must scan & process the road definition
name = sc.next();
// check to see if the intersection already exists
if (RoadNetwork.findIntersection( name ) != null) {
Errors.fatal(
"Intersection '"
+ name
+ "' is declared twice"
);
}
...
Now, nobody outside of class RoadNetwork needs to know how intersections are organized. The parameter list for the initializer has been cut short above because there is never a need to tell the new intersection where the list of intersections is stored, or even to tell it that there is a list.
This solution lends itself immediately to use of one of Java's hash mechanisms, since the new mechanism can be slipped into the RoadNetwork class without making any changes to the Intersection or Road classes. For this reason, we opt to use this approach in the code we are developing.
A complete executable java program containing all the code we have discussed to date for the road network example is given on line here.