18. Abuse of Class Hierarchy

Part of CS:2820 Object Oriented Software Development Notes, Spring 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

An Aside?

A student approached me offering code sort of like this: 

class Basic {
    void someMethod() {
        if (this instanceof SubClassOne) {
            SubclassOne thisOne = (SubclassOne)this;
            operateOn( thisOne.somefield );
        } else {
            SubclassTwo thisTwo = (SubclassTwo)this;
            fiddleWith( thisTwo.otherfield );
        }
    }
}

class SubClassOne extends Basic {
    SomeClass somefield;
}

class SubClassTwo extends Basic {
    OtherClass otherfield;
}

The student was having problems with this. My observation was that, of course this code could be made to work, but this code is also significantly inefficient and it abuses the spirit of object oriented programming with class hierarchies.

Also, the above code is historically importat. Before the invention of objects, programmers in languages such as C and Pascal would write code like this in order to handle the kinds of problems that motivated the development of object-oriented languages.

Object-oriented languages allow us to replace this with something better better: 

abstract class Basic {
    abstract void someMethod();
        // a concrete class could be used here too
}

class SubClassOne extends Basic {
    SomeClass somefield;
    void someMethod() { // overrides the basic version of SomeMethod
        operateOn( thisOne.somefield );
    }
}

class SubClassTwo extends Basic {
    OtherClass otherfield;
    void someMethod() { // overrides the basic version of SomeMethod
        fiddleWith( thisTwo.otherfield );
    }
}

Why is this better?

This puts all the code that deals with fields of each subclass in that subclass instead of making the superclass aware of those fields. It might even allow us to make the fields of the subclass private where the original scheme forces the fields to be public or as good as public.

It is worth noting that this is not always the most sensible way to do things. Specifically, if we had a factory method that allocated either an instance of SubclassOne or SubclassTwo the sensible place for this factory method will likely be in class Basic, since it always returns an instance of a subclass of Basic. If part of the initialization of the subclass instance by the factory method is specific to the type of that instance, it could be done in a method of the instance, but if that method simply sets a public field of the new instance, it would be just as easy to set that directly in the factory method.

Back to the Road Network

In the previous lectures, we built stoplights where the time it takes for a vehicle to pass through the intersection was negligable. Following on this path, the code for uncontrolled intersections is trivial but also uninteresting: 

/** Intersection with no control, neither stopsign nor stoplight
 */
class NoStop extends Intersection {
    NoStop( Scanner sc, String name ) {
	super( name );
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

    public String toString() {
	return  super.toString() + " nostop";
    }

    // simulation methods
    public void arrivalEvent( float time, int dir ) {} // Bug: must write this;
    public void departureEvent( float time ) {}        // Bug: must write this;
}

All vehicles arriving at this intersection will be forgotten by the simulation model, dissapearing off of the face of the (simulated) earth. We can fix this by rewriting the arrival event code as folows: 

    public void arrivalEvent( float time, int dir ) {
        Simulator.schedule( time, (float t)->pickRoad().entryEvent( t ) );
    }
}

The above code simply passes each vehicle through the intersection instantly. Because the passage is instantaneous, there will never be any collisions or congestion at this intersection. This is hardly realistic. To make things interesting, we need to add delay at each intersection. At the very least, this means that each intersection now has an attribute, the time it takes to pass through: 

/** Intersection with no control, neither stopsign nor stoplight
 */
class NoStop extends Intersection {

    private Float delay; // how long a vehicle occupies this intersection

    NoStop( Scanner sc, String name ) {
	super( name );
	try {
	    delay = ScanSupport.nextFloat(
		sc, ()->"Floating point delay expected: nostop " + name
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

Our preliminary approach to adding delay is to make just a small change to the code we've already given: 

    public void arrivalEvent( float time, int dir ) {
        Simulator.schedule(
            time + delay, (float t)->pickRoad().entryEvent( t )
        );
    }

All we did here is add delay. Nothing in this code caused vehicles to wait for other vehicles to clear the intersection. Making vehicles wait adds interesting complexity. We will do this by having the entry event schedule the exit event, tracking whether the intersection is occupied or not: 

    public void arrivalEvent( float time, int dir ) {
	if (occupants == 0) {
            Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
        }
	// regardless, add one to the count of vehicles in the intersection
        occupants = occupants + 1;
    }

    public void departureEvent( float time ) {
	// this vehicle departs the intersection
        pickRoad().entryEvent( t )
        occupants = occupants - 1;

	// were there any waiting vehicles, schedule the next departure
	if (occupants > 0) {
            Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
	}
    }

The logic of the above includes a new variable, occupants that counts the number of vehicles in the intersection. It is initially zero, and if the a vehicle arrives at an intersection with no occupants, that vehicle just zips through, incrementing occupants as it enters the intersection and decrementing it as it leaves.

If an intersection is occupied, the departure of a vehicle from the intersection allows the next waiting vehicle to continue through. This is done by scheduling a new departure event. Effectively, the intersection launches a short-lived process that launches successive vehicles out of the intersection until none are left.

We could make the model even more accurate by having the traversal time longer for vehicles that had to stop before continuing, but following that road leads us too far into the details of traffic modeling. Here, our primary concern is exercising the complexity of the simulation mechanism in order to explore what happens when large complex programs are written in an object-oriented language.

There is a strong relationship between the above code and the code used inside operating systems and other applications of parallel computing to handle shared resources. The code used to claim a shared resource strongly resembles the code given above for entry to an intersection, and the code used to release a shared resource strongly resembles the code used to depart from an intersection. This underscores the deep relationship between process scheduling in operating systems and event scheduling in discrete-event simulations.

Back to Stop Lights

In our initial development of stop lights, we ignored the time it takes a vehicle to cross an intersection. Let's add that in now. First, we'll add delay as a field of stoplights, the time it takes to drive through the intersection, and we'll initialize it as we did for non-stop intersections. We also need to track the number of occupants, although for stoplights, we only count, as occupants, vehicles that are not waiting for a green light. Here's the code we had for a stoplight arrival event: 

    public void arrivalEvent( float time, int dir ) {
	if (dir == lightDir) { // green
	    Road r = this.pickRoad();
	    Simulator.schedule( time, (float t)->r.entryEvent( t ) );
	} else { // red
	    // queue up the vehicle
	    queues[lightDir] = queues[lightDir] + 1;
	}
    }

Our first change will match what we did in class NoStop. Instead of directly scheduling the vehicle to enter the next road, we'll schedule a DepartureEvent, copying exactly the logic of an arrival event from the non-stop case into the code for arrival at a green light: 

    public void arrivalEvent( float time, int dir ) {
	if ((dir == lightDir) && (occupants == 0)) { // green and free
            Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
            occupants = occupants + 1;
	} else { // red or occupied
	    // queue up the vehicle
	    queues[lightDir] = queues[lightDir] + 1;
	}
    }

The next step is to change the code for a light change event. This code was: 

    private void lightChangeEvent( float time ) {
	if (queues == null) queues = new int[incoming.size()];

	// change the state of the light
	lightDir = lightDir + 1;
	if (lightDir > incoming.size()) lightDir = 0;

	// schedule the departures of waiting vehicles
	while (queues[lightDir] > 0) {
	    queues[lightDir] = queues[lightDir] - 1;
	    Road r = this.pickRoad();
	    Simulator.schedule( time, (float t)->r.entryEvent( t ) );
	}

	// schedule the next event in this light-change process
	Simulator.schedule(
	    time + greenLength, (float t)->lightChangeEvent( t )
	);
    }
Our changes here are confined to the middle section. The old code scheduled the departure of all of the waiting vehicles. Now, we can only schedule the departure of the first waiting vehicle, and we can only do that if the intersection is clear. So we rewrite the middle section of code as follows: 
	// schedule the departures of the first waiting vehicle, if possible
	if ((queues[lightDir] > 0) && (occupants == 0)) {
	    queues[lightDir] = queues[lightDir] - 1;
            Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
            occupants = occupants + 1;
	}

Note that when the light changes, vehicles are only allowed to continue if the intersection is clear. Just because the light changed does not give you permission to step down on the gas pedal! The logic of the above changes, taken together, means that the count of occupants is either zero or one.

Now, we look at the departure event. We have pushed considerable work here. 

    public void departureEvent( float time ) {
	// first schedule occupant (departing vehicle) to enter outgoing road
	Road r = this.pickRoad();
	Simulator.schedule( time, (float t)->r.entryEvent( t ) );
        occupants = occupants - 1;

	// schedule the departures of the next waiting vehicle, if possible
	if (queues[lightDir] > 0) {
	    queues[lightDir] = queues[lightDir] - 1;
            Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
            occupants = occupants + 1;
	}
    }

Note in the above that we scheduled one road entry event at the current time. So long as the road entry event service routine does not share any variables with the intersection's departure event, the order in which the statements of the departure event and the entry event are executed does not matter. Therefore, instead of scheduling the entry event, we can simply write this: 

	this.pickRoad().entryEvent( t );

There are a number of questions to ask about this code. We have already asserted that the count of occupants is confined to the range zero to one.

What about vehicles that were waiting at a red light, if that light turns green, and then back to red, do all the vehicles that were waiting at the red light get to go, even though the light changed back to red? Some places may well have that as their traffic law. Every vehicle that was stopped when the light turns green is permitted to go, even if it turns red again.

The alternative rule is that, if the light turns red, any vehicle not already in the intersection must wait for the next cycle of the light. That's how we drive in Iowa. Which of the above two alternatives does the code given above follow?