11. Search, Definition Errors

Where were we?

As the last class ended, we were just starting to develop code to look up intersections by name. We presented this skeleton:

public class RoadNetwork {
        static LinkedList  inters
                = new LinkedList  ();

        ...

        static Intersection findIntersection( String s ) {
                // return the intersection named s, or null if no such
                // Bug:  flesh this out!
        }

        ...
}

The obvious (even rather stupid) implementation we suggested was a linear search of inters for an intersection with the right name. We noted that Java provides much better tools.

The Linear Search Solution

Here is the stupid code we had in mind:

        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 code is almost inexcusably simple, but it works and it takes very little thought to write it. The fact is, linear searches are awful, and the Java standard library provides some far better tools. The Java Map interface is the gateway to improved performance here. Java maps, when given a key, return the associated value. What we've done above is implement a mapping using a linear search, close to the worst possible implementation.

Why did we opt to do this? There are two reasons:

First: There is a general rule in software development. Part a) Don't optimize. Part b) If you must optimize, do it later, and Part c) Only optimize those parts of the program that actually matter to performance. The point is, you should get the function right first, and only after you are sure that the program actually does something useful and worth optimizing should you worry about optimizing it. Time spent optimizing code that does something that turns out to be wrong is wasted time, and time spent optimizing code that turns out to have little impact on performance is almost as bad.

Second: The time it takes to figure out the complexities of the Map interface and figure out how to apply that interface to this problem is significantly longer than the time it takes to cobble together a quick and dirty solution such as the above. This strongly argues that the quick and dirty solution is the right way to get started.

String Comparison

In the code above, we wrote this code for string comparison:

                        if (i.name.equals( s )) {

In contrast, in the code we wrote for the initializeNetwork() method last week, we wrote:

                        if ((command == "intersection")

Why? The answer is, the code we wrote last week is wrong! The code used in our linear search is the best way to compare two strings. Let's go through a list of alternative ways of comparing strings a and b:

• if (a == b)
  This is true of the variables a and b refer to the same object. It is quite possible that two different string objects contain the same text. For example, the strings "ab" and "a"+"b" are extremely likely to be different objects.

• if (a.equals(b))
  This is true of the string variables a and b contain the same text, and it is safe if b is null, but it will raise an exception if a is null.

• if ((a |= null) && a.equals(b)))
  This is true only if both string variables are non-null and contain the same string. It is therefore the safest code unless you know that one of the variables is not null.

As a result, when comparing a string variable to a string constant:

• if (a.equals("constant")))
  This is unsafe unless you know for certain that a will never be null.

• if ("constant".equals(a)))
  This is safe and will return true only when a is not null and has the same text as the string constant. It may look awkward to put the constant first, but this is the preferred idiom in Java.

We'd better rewrite initializeNetwork() to take this into account:

static void initializeNetwork( Scanner sc ) {
	while (sc.hasNext()) { 
		String command = sc.next(); 
		if (("intersection".equals( command ))
		||  ("i".equals( command ))) {
			inters.add( new Intersection( sc, inters ) );
		} else if (("road".equals( command ))
		||         ("r".equals( command ))) {
			roads.add( new Road( sc, inters ) );
		} else {
			Errors.warning( "unknown command" );
			// Bug:  should we allow comments?
		}
	}
}

Using findIntersection

There were two places in our code with bug notices that we can now attack, in the initializers for the road and intersection classes. Consider class Intersection:

        public Intersection( Scanner sc, LinkedList  inters ) {
		// scan and process one intersection
		name = sc.next();
		// Bug: look up name!
		String skip = sc.nextLine();
		// Bug:  What if more junk at end of line (skip not empty)
	}

We need to look up the name of the intersection because our source file format only allows one definition of each named intersection. If an intersection has already been defined with this name, we ought to complain. Here is an initial suggestion for how to do this:

        public Intersection( Scanner sc, LinkedList  inters ) {
                // scan and process one intersection
                name = sc.next();
		// Bug:  What if at end of file?  What does sc.next do?
                if (RoadNetwork.findIntersection( name ) != null) {
                        Errors.warning( "Intersection "
                                      + name
                                      + " redefined."
                        );
			// Bug:  Should we prevent creation of this object?
                }
                String skip = sc.nextLine();
                // Bug:  What if more junk at end of line (skip not empty)
        }

At this point, our initializer complains with a useful error message when an attempt is made to declare a second (or third) intersection with the same name as a pre-existing intersection, but there may be a little bug here. The new intersection is still created and added to the list of all intersections. Should we prevent this? Also, what if there is no next symbol for the scanner to scan? Does it return null? Does it return an empty string? Our code is not prepared for either possible outcome, so we have inserted yet another bug notice.

The second initializer we have to worry about is for roads. In this case, we want to guarantee that both intersections that the road connects are well defined. Here is the old code:

	public Road( Scanner sc, LinkedList  inters ) {
		// scan and process one road
		String sourceName = sc.next();
		String dstName = sc.next();
		// Bug: look up source and dest names!
		travelTime = sc.nextFloat();
		// Bug:  What if no next float?
		String skip = sc.nextLine();
		// Bug:  What if more junk at end of line (skip not empty)
	}

What we need to do is look up both the source and destination roads and complain if either are undefined. Reasonable error messages should identify the road that caused the problem and also explain the error, so our improved code gets a bit long-winded:

                // scan and process one road
                String sourceName = sc.next();
                String dstName = sc.next();
                // Bug: What if at end of file?  What does sc.next do?
                source = RoadNetwork.findIntersection( sourceName );
                destination = RoadNetwork.findIntersection( dstName );
                if (source == null) {
                        Errors.warning(
                                "In road " + sourceName + " " + dstName +
                                ", Intersection " + sourceName + " undefined"
                        );
			// Bug:  Should we prevent creation of this object?
                }
                if (destination == null) {
                        Errors.warning(
                                "In road " + sourceName + " " + dstName +
                                ", Intersection " + dstName + " undefined"
                        );
			// Bug:  Should we prevent creation of this object?
                }

As with the previous example, we have not addressed what should be done if the object declaration contains an error, we have merely detected and reported the error. And again, we have not dealt with the possiblity that there might not be a source or destination intersection name.

The duplicated code above suggests that we might want to package the test for undefined names in a subroutine of some kind, perhaps a utility method for syntax checking that gets a name and checks to see if it is defined.