# 19. More simulation: stop lights

## Stoplights

Adding stop lights to the model adds complexity we have ignored up to this point. With uncontrolled intersections, each intersection had just one logical queue, so that vehicles went through the intersection in first-come-first-served order. This is not strictly realistic, because in a real intersection, when things get congested, separate queues build up on each incoming road, but we can get away with it because most uncontrolled intersections rarely have this much traffic in real life.

With stop lights, on the other hand, we definitely need separate queues for each incoming road. To do this, the connections between roads and intersections need to be more elaborate, and we face a design decision. If vehicles have to wait, do they queue up in the intersection or on the road leading to the intersection. This is not a question about the physical geometry of real intersections, it is a question about the structure of our code: Are the queues of waiting cars part of the road object or are the queues of waiting cars part of the intersection object? Both of these schemes can be made to work.

• If queues are part of the road then the leave method of each road must know whether the intersection is blocking that road or not, and it must only call the enter method of the intersection if the intersection permits it. One way to do this would be for the intersection to communicate with each incoming road, effectively telling the road "green light" or "red light."

• If queues are part of the intersection then the leave method of roads can remain simple because the queues within the intersection are hidden from the road. This seems like it will reduce the amount of communication needed between roads and intersections.

But, we still have a problem: Stop lights have a direction, and our basic road network description does not have a concept of direction. Whichever of the approaches we take above, we need to add directions to the roads entering an intersection, and we need to add rules to the stop light that indicate which directions it turns green in what order. This has an impact on both the model description language we use and on the internals of the simulator.

Most intersections in the American midwest are 4-way intersections, but in older regions, the US east coast and most of Europe, there are large numbers of three-way and occasional 5 and even occasional 6-way intersections. 4-way stoplights, though, have a unique property: When the light is red in the east-west direction, it is green in the north-south direction, and visa versa. 3 and 5-way intersections do not have this convenient property.

We could build a very complex model, but for the time being, we will simplify. Each stoplight will have a cycle length: 2-way stop lights will adequately model both one-lane roads with a light at each end, so the road is either westbound or eastbound at any given time, and 4-way intersections, where the light alternates between east-west and north-south. 3-way and 5-way lights model intersections with that many incoming roads where only one incoming road has a green light at any time. So, a stop light could be declared as follows:

```intersection B 1.0 source 20.0 3
```
For this light, it takes 1 time unit for each vehicle to cross the intersection, The light changes every 19 time units, and there are 3 incoming roads, or to be more accurate, there are 3 incoming queues. The obvious numbering would be from 0 to 2, and if a stop-light intersection does not have roads in to all of its directions, there is a problem.

To make this work, we add an optional field to every road, a queue number. If that road is connected to a stoplight, it indicates which queue at that stoplight this road feeds. The field is optional because it doesn't matter for roads that connect to uncontrolled intersections. If the number is missing when a road connects to a stoplight, there should be an error message.

```road A B 3.0 1
```

The above road connects to incoming road number 1 of stop-light B.

## Building the Model

Stop light intersections need an incoming queue of vehicles for each incoming road. We can substitute an integer for each queue, just counting the vehicles until such time as we think about giving vehicle an individual identity. If we want to detect and report the fact that some incoming queue of a stop light has no road connected to it, we need to have an array of booleans, one per stop-light direction, to track which connections are unused.

Our constructor for a new road now needs to read the destination intersection incoming road number, we'll call this dstNumber, and if no value is given, we can make a default of -1. Where we used to call

```destination.addIncoming( this );
```

We now need to call:

```destination.addIncoming( this, dstNumber );
```

The addIncoming method needs to do several things: First, check that the road number is acceptable. And then not that that incoming queue has a road connected to it. The rules for an acceptible incoming road number depend on whether the intersection is a stop light or not.

## At Simulation Time

In the simulation, when a vehicle exits a road, our event-service routine currently does this:

```private void leave( double time ) {
this.destination.enter( time );
}
```
We need to change this to the following:
```private void leave( double time ) {
this.destination.enter( time, dstNumber );
}
```
This allows the destination intersection to know which queue of waiting vehicles the arriving vehicle should enter. For non-stop-light intersections, the dstNumber parameter can be simply ignored (it should be -1 and this fact should already have been checked addIncoming, but for stop lights, we use this.

The fun part of this exercise occurs at stop-lights, in the enter routine and its interaction with the light-change routine. Recall the code for entry to a NoStop intersection:

```public void enter( double time, int road ) {
waiting = waiting + 1;  // enqueue this car
if (waiting <= 1) {     // am I the only one in the queue, send me on
Simulator.schedule(
time + travelTime,
(double t)-> this.leave( t )
);
}
}
```
In the above, we have added a new parameter, the incoming road number, but this plays no role when entering an uncontrolled intersection.

What we will do for stop-lights is modify this code by having not one variable waiting that represents the length of the one queue, but an array, one for each queue. We also add a variable to indicate the current "green light" direction:

```public void enter( double time, int road ) {
if (!occupied && (road == greenLight)) {
// am I the only one in the queue at a green light? send me on!
occupied = true;
Simulator.schedule(
time + travelTime,
(double t)-> this.leave( t )
);
} else {
}
}
```

We made one big change above. In the original code, the count waiting included the vehicle that was actually in the intersection. Here, we have split the count so that waiting[road] counts only the vehicles waiting to enter the intersection, and occupied counts the vehicles in the intersection (never more than one in this version of the code).

At an uncontrolled intersection, the enter and leave methods had a strong relationship, verging on symmetry. The same is true here:

```private void leave( double time ) {
assert occupied == true;
if (waiting[greenLight] > 0) {   // can a new car enter the intersection?
waiting[greenLight] = waiting[greenLight] - 1;  // dequeue that car
Simulator.schedule(          // schedule its departure
time + travelTime,
(double t)-> this.leave( t )
);
// that car now occupies the intersection, so occupied is still true
} else {
occupied = false;
}

this.pickOutgoing().enter( time );
}
```

There is something subtle above: When a vehicle leaves the intersection, we don't care what incoming road it came from or how many vehicles are waiting there. We care only about the queue of waiting cars in the direction that the current green light faces.

As a result, if the light changes while a car is in the intersecton, the cars facing the newly green light should be waiting until the intersection is vacant before they begin to move. Making that happen also depends on logic in the light-change method, where we had this code:

```private void lightChange( double time ) {
Simulator.schedule(
time + period,
(double t)-> this.lightChange( t )
);
// BUG -- light changes should change which roads are blocked
// BUG -- light changes should unblock any waiting vehicles
}
```

It is time to fix the bug notices above. The light change has no impact on any vehicle already in the intersection, that vehicle continues to drive onward, onto some outgoing road. However, if no vehicle is in the interseciton, any waiting vehicles in the newly green direction may start:

```private void lightChange( double time ) {
Simulator.schedule(
time + period,
(double t)-> this.lightChange( t )
);

// change which way the green light faces
this.greenLight = (this.greenLight + 1) % incomingRoads;

// is there a car waiting in the new green direction that can go?
if (!occupied && (waiting[greenLight] > 0)) {
waiting[greenLight] = waiting[greenLight] - 1;  // dequeue that car
Simulator.schedule(          // schedule its departure
time + travelTime,
(double t)-> this.leave( t )
);
occupied = true; // that car now occupies the intersection
}
}
```

Of course, we can add lots of debugging output to trace what is happening.

## Small Efficiency Questions

Note above the use of the following code framework to update the direction:

```this.greenLight = (this.greenLight + 1) % incomingRoads;
```

We could just as easily have written this:

```this.greenLight = this.greenLight + 1;
if (this.greenLight >= incomingRoads) this.greenLight = 0;
```

Why pick one or the other of these? The second one is long winded, but it uses intellectually trivial code, just assignment, increment and comparison. Any beginning programmer understands these.

The second is considerably shorter, using just the % operator instead of an if statement. The problem is, this operator that is understood by a smaller fraction of the population. In fact, one way to divide computer scientists from mere "coders" is that a computer scientist should understand the mod operator, including the fact that % is not really mod in languages like C and Java, but rather integer remainder, and the result is almost always wrong for negative numbers if what you really wanted is mod.

Run-time efficiency also matters. The mod operator is typically computed by division, although if the dividend is a constant power of two, faster operations can be used. Division, on a typical CPU, is 10 to 20 times slower than simple operations such as addition and comparison. The net result is that the version of the code with the if statement may well be faster than the version of the code using division.

But recall that low-performance implementations of Java do not compile to machine code, they compile to J-code, the instruction set of a virtual machine that is then interpreted by code written in machine code. This can easily slow programs down by a factor of ten, making division and addition much closer in speed and making the penalty for using an if statement considerably higher.

There is a second issue hiding here: We could have used incoming.size() to count the number of incoming roads instead of using an extra instance variable initialized from the input file. We do not have access to how incoming.size() is implemented. For linked lists, it might iterate down the list counting list elements, or there might be an instance variable in each object of class list used to keep a running count of the size. Counting the list elements is not fast, even though we suspect that most intersections will have just 4 incoming roads.

In fact, we would be completely wrong to use incoming.size() when we change the stop light. Recall that one way to get a 4-way stop light intersection is do declare the number of incoming queues to be just 2, and to have both the northbound and southbound incoming roads use one queue, while the eastbound and westbound roads use the other. This means that we must use the count that came from the road description file, not the count of roads that actually enter this intersection.