10. Iterators, Input Parsing
Part of
CS:2820 Object Oriented Software Development Notes, Spring 2019
|
In the last class, we used Java's for loop construct:
/** Print out the road network from the data structure
*/
static void printNetwork() {
for (Intersection i:inters) {
System.out.println( i.toString() );
}
for (Road r:roads) {
System.out.println( r.toString() );
}
}
Each of these for loops is actually an abbreviation for a rather complex bit of code. First, the for loop creates an iterator over the list and then it use that iterator to get successive list elements. The following far more long-winded bit of code is exactly equivalent to the first loop above:
for (
Iterator <Intersection> it = inters.iterator();
it.hasNext();
) {
Intersection i = it.next();
System.out.println( i.toString() );
}
An iterator is class that can be derived from any collection that will deliver successive members of that collection each time its next() method is called.
The above long-winded code expresses exactly the same computation as the original for loop, and in fact, the Java compiler generates exactly the same code from the original and this long-winded version of the code. Any for loop can be rewritten as a while loop, so we could further deconstruct this code as follows:
{
Iterator <Intersection> it = inters.iterator();
while ( it.hasNext() ) {
Intersection i = it.next();
System.out.println( i.toString() );
}
}
Why did we wrap the whole lump of code above in braces? The iterator it created by the for loop was local to the loop. When we converted the for loop to a while loop, we added the extra brackets to guarantee that the declaration of it would be local to the loop and not visible elsewhere in the program.
As a general rule, the for-loop construct in Java is always a shorthand. Every Java for loop can be rewritten as a while loop. Consider this elementary for loop that iterates over integers:
for(int i=0 ; i < 10 ; i++) {
doSomethingWith( i );
}
This can be rewritten as follows, and in fact, the Java compiler would generate exactly the same code from the above as it generates from this long-winded rewrite:
{
int i = 0;
while (i < 10) {
doSomethingWith( i );
i++;
}
}
Again, we wrapped the while loop in an extra set of braces in order to make the loop control variable i visible only inside the loop and not elsewhere in the program.
If we try to compile the code we had at the end of the previous class, we get these error messages:
[dwjones@serv15 ~/project]$ javac Road*java
RoadNetwork.java:47: error: cannot find symbol
sourceName + " " +
^
symbol: variable sourceName
location: class Road
RoadNetwork.java:48: error: cannot find symbol
dstName + " " +
^
symbol: variable dstName
location: class Road
2 errors
[dwjones@serv15 ~/project]$
Looking at the relevant code, we find:
class Road {
float travelTime; // measured in seconds
Intersection destination; // where road goes
Intersection source; // where road comes from
// name of road is source-destination
// 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
// Bug: Must look up dstName to find destination
// Bug: What if no next float?
travelTime = sc.nextFloat();
String skip = sc.nextLine();
}
// other methods
public String toString() {
return (
"Road " +
sourceName + " " +
dstName + " " +
travelTime
);
}
}
The code for the toString() method we have is trying to access local variables of the Road() initializer when it ought to be relying on the information available from the instance variables of class Road(). Obviously, our design is incomplete.
We could replace sourceName in the toString() method above with source.name. This assumes that we want the name() field of the object to be visible from outside, and this raises the question, what fields ought to be visible, and if visible, how can we protect them.
There is a rule of thumb in programming that comes from military security: The need to know rule. This states that no user of an object should be given more information about the internal state of that object than they need to know to get their job done.
Need to know security goes against the principle of transparency, that in an open society, secrets are bad. The primary reason that we keep secrets in object-oriented programming is to minimize the size of the public interface of each class, but keeping secrets also has genuine security consequences. In a large project, a rogue programmer working on one part of the program can harvest any information about the system that is public and export it. By only giving each programmer access to the bare minimum information needed to do the job, we limit the damage a rogue programmer could do and maximize the likelihood that rogues behavior will be detected.
In Java, each declaration can be marked as: public, private, or final. In general, marking declarations as private makes very good sense. It means that the variable is invisible to all code outside this class.
If a variable must be visible because outsiders need to know about it, you can minimize the damage they can do by marking it final. Final variables are not read-only, their values can be changed, but the binding of the variable name to the object is fixed for all time. Declare variables to be public only if outsiders have a natural need to not only see the variable but to make arbitrary changes to it.
Later, when we discuss clas hierarchies, we will discuss an additional attribute, protected. Protected variables are like private variables in programs that do not use class hierarchies. In a class hierarchy, one class may be a subclass of another. In programs that use class hierarchies, protected variables are visible not only in the class where they are declared, but also in all subclasses of that class. For the moment, we can ignore this marking.
In our running example road network code, the following declarations make sense:
class Road {
private float travelTime; // measured in seconds
private Intersection destination;// where road goes
private Intersection source; // where road comes from
...
}
class Intersection {
final String name;
private LinkedList outgoing = new LinkedList ();
private LinkedList incoming = new LinkedList ();
...
The markings above make all fields private except for the name of an intersection, which is final. Note that there must be exactly one assignment to a vinal variable in the constructor for a class. Java compilers enforce this rule conservatively, which means that there are cases where you, as a programmer, can assure that there is exactly one assignment to a variable but the Java compiler is not smart enough to figure this out. In such cases, the compiler will not permit that variable to be declared as final.
The next problem we face is that of looking up each intersection. The need for this is announced by bug notices in our code:
class Road {
...
// 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
// Bug: Must look up dstName to find destination
...
}
...
}
class Intersection {
...
// initializer
public Intersection( Scanner sc, LinkedList inters ) {
// code here must scan & process the intersection definition
name = sc.next();
// Bug: look up name!
...
}
...
}
Obviously, we need a way, given the name of an intersection, to find that intersection in the list of all intersections. Since this list is a static field of class RoadNetwork, one way to do the lookup is to have RoadNetwork export a public static method to look things up.
public class RoadNetwork {
static LinkedList <Intersection> inters
= new LinkedList <Intersection> ();
...
static Intersection findIntersection( String s ) {
// return the intersection named s, or null if no such
// Bug: flesh this out!
}
...
}
The obvious way to code this is with a rather stupid linear search through the list of roads to find the right one. Java includes some far more sophisticated tools for this search, but we'll ignore them here.