Safe Intersections

Question

Code Review's April 2017 Community Challenge has us simulating a multi-way intersection. My emphasis was around safety (don't want cars crashing) and ease of use. I plan on adding "smart intersections" (can detect when a car is/isn't there and change the signals accordingly) and a GUI later on.

The sample intersection:

Time | EastWest | NorthSouth
-----+----------+-------------
0s | Red | Green
1s | Red | Green
2s | Red | Green
3s | Red | Green
4s | Red | Yellow
5s | Green | Red
6s | Green | Red
7s | Green | Red
8s | Green | Red
9s | Yellow | Red

Can be created via:

Intersection intersection = Intersection.builder()
 .addLights(2, () -> new Light(4, 1, 0)) // greenDuration, yellowDuration, redPause
 .setActivationRules((rules, lights) -> {
 // These rules specify when to activate a light. This allows for
 // more complex intersections.
 rules.after(lights.get(0)).thenActivate(lights.get(1));
 rules.after(lights.get(1)).thenActivate(lights.get(0));
 // One more type of rule can be defined:
 // rules.afterAll(lights.get(0), lights.get(1)).thenActivate(lights.get(2));
 }).activate(0)
 .build();

There are quite a few files, so the code is available on github. I use Google's Guava library.

---

Light.java

package trafficlights.intersection;
import com.google.common.collect.ImmutableMap;
import java.util.EnumMap;
import java.util.OptionalDouble;
import static com.google.common.base.Preconditions.checkState;
public class Light {
 public enum Color {
 RED, GREEN, YELLOW
 }
 private enum State {
 GREEN, YELLOW, WAITING, OFF;
 Color getColor() {
 switch (this) {
 case GREEN:
 return Color.GREEN;
 case YELLOW:
 return Color.YELLOW;
 case WAITING:
 case OFF:
 return Color.RED;
 }
 throw new InternalError();
 }
 }
 private State state = State.OFF;
 private final EnumMap<State, Double> durations;
 private double elapsedTime;
 @SuppressWarnings("OptionalUsedAsFieldOrParameterType") private OptionalDouble goal;
 private boolean requestOff;
 public Light(double greenDuration, double yellowDuration, double redPause) {
 durations = new EnumMap<>(ImmutableMap.<State, Double>builder()
 .put(State.GREEN, greenDuration)
 .put(State.YELLOW, yellowDuration)
 .put(State.WAITING, redPause)
 .build());
 this.elapsedTime = 0;
 this.goal = OptionalDouble.empty();
 this.requestOff = false;
 }
 public Color getColor() {
 return state.getColor();
 }
 private OptionalDouble getDurationIfPresent(State state) {
 if (durations.containsKey(state)) return OptionalDouble.of(durations.get(state));
 return OptionalDouble.empty();
 }
 public void turnOff() {
 requestOff = true;
 }
 public void tick(double duration) {
 checkState(isActive());
 performActions(duration);
 updateState(duration);
 }
 public void activate() {
 state = State.GREEN;
 goal = OptionalDouble.of(durations.get(state));
 requestOff = false;
 this.elapsedTime = 0;
 }
 public boolean isActive() {
 return state != State.OFF;
 }
 private void performActions(double duration) {
 switch (state) {
 case GREEN:
 case YELLOW:
 case WAITING:
 elapsedTime += duration;
 break;
 case OFF:
 elapsedTime = 0;
 break;
 }
 }
 private void updateState(double duration) {
 switch (state) {
 case GREEN:
 if (requestOff) {
 requestOff = false;
 incrementState();
 elapsedTime = 0;
 }
 //noinspection ConstantConditions
 while (goal.isPresent() && elapsedTime >= goal.getAsDouble()) {
 incrementState();
 }
 break;
 case YELLOW:
 case WAITING:
 //noinspection ConstantConditions
 while (goal.isPresent() && elapsedTime >= goal.getAsDouble()) {
 incrementState();
 }
 break;
 case OFF:
 break;
 }
 }
 private void incrementState() {
 //noinspection ConstantConditions
 elapsedTime -= goal.getAsDouble();
 state = modularIncrementEnum(state.ordinal(), State.values());
 goal = getDurationIfPresent(state);
 }
 private static <T> T modularIncrementEnum(int index, T[] values) {
 return values[(index + 1) % values.length];
 }
}

Intersection.java

package trafficlights.intersection;
import com.google.common.collect.ImmutableList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.stream.Stream;
/**
 * Handles the state of a 4-way intersection
 */
public class Intersection {
 private final List<Light> lights;
 private final ActivationRules activationRules;
 Intersection(List<Light> lights,
 ActivationRules activationRules) {
 this.lights = ImmutableList.copyOf(lights);
 this.activationRules = activationRules;
 }
 public void tick(double duration) {
 List<Light> deactivated = new ArrayList<>();
 lights.stream()
 .filter(Light::isActive)
 .forEach(light -> {
 light.tick(duration);
 // Note: do not handle activating lights here; that is concurrent modification and
 // will cause bugs (if a light is activated that is further in the list, it will have its tick
 // function run immediately, whereas if it was prior to this light, the activated light won't have
 // its tick function run).
 if (!light.isActive()) {
 deactivated.add(light);
 }
 });
 activateTriggered(deactivated);
 }
 private void activateTriggered(List<Light> deactivated) {
 // Follow simple activation rules
 deactivated.stream()
 .filter(activationRules.getSimpleRules()::containsKey)
 .map(activationRules.getSimpleRules()::get)
 .flatMap(Collection::stream)
 .forEach(Light::activate);
 // Follow complex activation rules
 deactivated.stream()
 .filter(activationRules.getComplexRules()::containsKey)
 .map(activationRules.getComplexRules()::get)
 .flatMap(Collection::stream)
 .filter(rule -> rule.getTriggers().stream()
 .noneMatch(Light::isActive))
 .map(ComplexActivationRule::getToActivate)
 .flatMap(Collection::stream)
 .forEach(Light::activate);
 }
 public Light.Color getColor(int i) {
 return lights.get(i).getColor();
 }
 public Stream<Light.Color> getLightColors() {
 return lights.stream()
 .map(Light::getColor);
 }
 public static IntersectionBuilder builder() {
 return new IntersectionBuilder();
 }
}

ActivationRules.java

package trafficlights.intersection;
import java.util.Collection;
import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.Map;
class ActivationRules {
 private Map<Light, Collection<Light>> simpleRules;
 private Map<Light, Collection<ComplexActivationRule>> complexRules; // The keys are the triggers.
 public ActivationRules(IdentityHashMap<Light, Collection<Light>> simpleRules,
 IdentityHashMap<Light, Collection<ComplexActivationRule>> complexRules) {
 this.simpleRules = simpleRules;
 this.complexRules = complexRules;
 }
 Map<Light, Collection<Light>> getSimpleRules() {
 return Collections.unmodifiableMap(simpleRules);
 }
 Map<Light, Collection<ComplexActivationRule>> getComplexRules() {
 return Collections.unmodifiableMap(complexRules);
 }
}

ComplexActivationRule.java

package trafficlights.intersection;
import java.util.Collection;
import java.util.Collections;
import static com.google.common.base.Preconditions.checkArgument;
class ComplexActivationRule {
 private Collection<Light> triggers;
 private Collection<Light> toActivate;
 public ComplexActivationRule(Collection<Light> triggers,
 Collection<Light> toActivate) {
 checkArgument(!triggers.isEmpty());
 checkArgument(!toActivate.isEmpty());
 this.triggers = triggers;
 this.toActivate = toActivate;
 }
 public Collection<Light> getTriggers() {
 return Collections.unmodifiableCollection(triggers);
 }
 public Collection<Light> getToActivate() {
 return Collections.unmodifiableCollection(toActivate);
 }
}

IntersectionBuilder.java

package trafficlights.intersection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.Supplier;
import java.util.stream.IntStream;
public class IntersectionBuilder {
 private final List<Light> lights = new ArrayList<>();
 private final RuleBuilder activationRules = new RuleBuilder();
 IntersectionBuilder() {
 }
 public IntersectionBuilder addLight(Light light) {
 lights.add(light);
 return this;
 }
 public IntersectionBuilder addLights(Light... lights) {
 return addAllLights(Arrays.asList(lights));
 }
 public IntersectionBuilder addLights(int n, Supplier<Light> lightSupplier) {
 IntStream.range(0, n)
 .mapToObj(i -> lightSupplier.get())
 .forEach(lights::add);
 return this;
 }
 public IntersectionBuilder addAllLights(List<? extends Light> lights) {
 this.lights.addAll(lights);
 return this;
 }
 public IntersectionBuilder2 setActivationRules(BiConsumer<RuleBuilder, List<Light>> ruleBuilder) {
 ruleBuilder.accept(activationRules, lights);
 return new IntersectionBuilder2();
 }
 public class IntersectionBuilder2 {
 public IntersectionBuilder3 activate(int... lightIndices) {
 Arrays.stream(lightIndices)
 .mapToObj(lights::get)
 .forEach(Light::activate);
 return new IntersectionBuilder3();
 }
 }
 public class IntersectionBuilder3 {
 public Intersection build() {
 return new Intersection(lights, activationRules.build());
 }
 }
}

RuleBuilder.java

package trafficlights.intersection;
import java.util.*;
public class RuleBuilder {
 private final IdentityHashMap<Light, Collection<Light>> simpleRules = new IdentityHashMap<>();
 private final IdentityHashMap<Light, Collection<ComplexActivationRule>> complexRules = new IdentityHashMap<>();
 RuleBuilder() {
 }
 public RuleBuilder2 after(Light light) {
 return new RuleBuilder2(light);
 }
 public RuleBuilder2 afterAll(Light... lights) {
 return new RuleBuilder2(lights);
 }
 ActivationRules build() {
 return new ActivationRules(simpleRules, complexRules);
 }
 public class RuleBuilder2 {
 private final Collection<Light> triggers;
 private RuleBuilder2(Light... triggers) {
 this.triggers = new ArrayList<>(Arrays.asList(triggers));
 }
 public void thenActivate(Light... lights) {
 thenActivate(Arrays.asList(lights));
 }
 public void thenActivate(Collection<Light> lights) {
 lights = new ArrayList<>(lights);
 if (triggers.size() == 1) {
 // simple rule
 simpleRules.merge(triggers.iterator().next(), lights, (existing, toAdd) -> {
 existing.addAll(toAdd);
 return existing;
 });
 } else {
 // complex rule
 ComplexActivationRule rule = new ComplexActivationRule(triggers, lights);
 for (Light trigger : triggers) {
 List<ComplexActivationRule> newRule = new ArrayList<>();
 newRule.add(rule);
 complexRules.merge(trigger, newRule, (oldRules, newRules) -> {
 oldRules.addAll(newRules);
 return oldRules;
 });
 }
 }
 }
 }
}

---

I compiled a few simple tests, but I have no desire for this code to be critiqued:

package trafficlights;
import trafficlights.intersection.Intersection;
import trafficlights.intersection.Light;
public class Runner {
 public static void main(String[] args) {
 runSimpleFourWay();
 System.out.println();
 runSimpleFourWayWithLeftTurns();
 System.out.println();
 runComplexFourWay();
 }
 private static void runSimpleFourWay() {
 Intersection intersection = Intersection.builder()
 .addLights(2, () -> new Light(4, 1, 0))
 .setActivationRules((rules, lights) -> {
 rules.after(lights.get(0)).thenActivate(lights.get(1));
 rules.after(lights.get(1)).thenActivate(lights.get(0));
 }).activate(0)
 .build();
 System.out.println(" Time | EW ^ | NS ^ ");
 System.out.println("------------------------");
 runIntersection(intersection, 1, 20);
 }
 private static void runSimpleFourWayWithLeftTurns() {
 Intersection intersection = Intersection.builder()
 .addLights(4, () -> new Light(4, 1, 0))
 .setActivationRules((rules, lights) -> {
 for (int i = 0; i < lights.size(); i++) {
 rules.after(lights.get(i)).thenActivate(lights.get((i + 1) % lights.size()));
 }
 }).activate(0)
 .build();
 System.out.println(" Time | EW ^ | NS < | NS ^ | EW < ");
 System.out.println("-------------------------------------------");
 runIntersection(intersection, 1, 40);
 }
 private static void runComplexFourWay() {
 Intersection intersection = Intersection.builder()
 .addLight(new Light(3, 1, 1))
 .addLight(new Light(4, 2, 1))
 .addLights(6, () -> new Light(4, 1, 1))
 .setActivationRules((rules, lights) -> {
 rules.after(lights.get(0)).thenActivate(lights.get(3));
 rules.after(lights.get(1)).thenActivate(lights.get(2));
 rules.afterAll(lights.get(2), lights.get(3))
 .thenActivate(lights.get(4), lights.get(5));
 rules.after(lights.get(4)).thenActivate(lights.get(7));
 rules.after(lights.get(5)).thenActivate(lights.get(6));
 rules.afterAll(lights.get(6), lights.get(7))
 .thenActivate(lights.get(0), lights.get(1));
 }).activate(0, 1)
 .build();
 System.out.println(" Time | N < | S < | N ^ | S ^ | E < | W < | E ^ | W ^ ");
 System.out.println("-----------------------------------------------------------------------------");
 runIntersection(intersection, 1, 48);
 }
 private static void runIntersection(Intersection intersection, int tick, int duration) {
 for (int seconds = 0; seconds < duration; seconds++) {
 System.out.printf(" %3ds", seconds);
 intersection.getLightColors()
 .forEach(color -> System.out.printf(" | %6s", color));
 System.out.println();
 intersection.tick(tick);
 }
 }
}

When run, it produces this output:

 Time | EW ^ | NS ^ 
------------------------
 0s | GREEN | RED
 1s | GREEN | RED
 2s | GREEN | RED
 3s | GREEN | RED
 4s | YELLOW | RED
 5s | RED | GREEN
 6s | RED | GREEN
 7s | RED | GREEN
 8s | RED | GREEN
 9s | RED | YELLOW
 10s | GREEN | RED
 11s | GREEN | RED
 12s | GREEN | RED
 13s | GREEN | RED
 14s | YELLOW | RED
 15s | RED | GREEN
 16s | RED | GREEN
 17s | RED | GREEN
 18s | RED | GREEN
 19s | RED | YELLOW
 Time | EW ^ | NS < | NS ^ | EW < 
-------------------------------------------
 0s | GREEN | RED | RED | RED
 1s | GREEN | RED | RED | RED
 2s | GREEN | RED | RED | RED
 3s | GREEN | RED | RED | RED
 4s | YELLOW | RED | RED | RED
 5s | RED | GREEN | RED | RED
 6s | RED | GREEN | RED | RED
 7s | RED | GREEN | RED | RED
 8s | RED | GREEN | RED | RED
 9s | RED | YELLOW | RED | RED
 10s | RED | RED | GREEN | RED
 11s | RED | RED | GREEN | RED
 12s | RED | RED | GREEN | RED
 13s | RED | RED | GREEN | RED
 14s | RED | RED | YELLOW | RED
 15s | RED | RED | RED | GREEN
 16s | RED | RED | RED | GREEN
 17s | RED | RED | RED | GREEN
 18s | RED | RED | RED | GREEN
 19s | RED | RED | RED | YELLOW
 20s | GREEN | RED | RED | RED
 21s | GREEN | RED | RED | RED
 22s | GREEN | RED | RED | RED
 23s | GREEN | RED | RED | RED
 24s | YELLOW | RED | RED | RED
 25s | RED | GREEN | RED | RED
 26s | RED | GREEN | RED | RED
 27s | RED | GREEN | RED | RED
 28s | RED | GREEN | RED | RED
 29s | RED | YELLOW | RED | RED
 30s | RED | RED | GREEN | RED
 31s | RED | RED | GREEN | RED
 32s | RED | RED | GREEN | RED
 33s | RED | RED | GREEN | RED
 34s | RED | RED | YELLOW | RED
 35s | RED | RED | RED | GREEN
 36s | RED | RED | RED | GREEN
 37s | RED | RED | RED | GREEN
 38s | RED | RED | RED | GREEN
 39s | RED | RED | RED | YELLOW
 Time | N < | S < | N ^ | S ^ | E < | W < | E ^ | W ^ 
-----------------------------------------------------------------------------
 0s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 1s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 2s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 3s | YELLOW | GREEN | RED | RED | RED | RED | RED | RED
 4s | RED | YELLOW | RED | RED | RED | RED | RED | RED
 5s | RED | YELLOW | RED | GREEN | RED | RED | RED | RED
 6s | RED | RED | RED | GREEN | RED | RED | RED | RED
 7s | RED | RED | GREEN | GREEN | RED | RED | RED | RED
 8s | RED | RED | GREEN | GREEN | RED | RED | RED | RED
 9s | RED | RED | GREEN | YELLOW | RED | RED | RED | RED
 10s | RED | RED | GREEN | RED | RED | RED | RED | RED
 11s | RED | RED | YELLOW | RED | RED | RED | RED | RED
 12s | RED | RED | RED | RED | RED | RED | RED | RED
 13s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 14s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 15s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 16s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 17s | RED | RED | RED | RED | YELLOW | YELLOW | RED | RED
 18s | RED | RED | RED | RED | RED | RED | RED | RED
 19s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 20s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 21s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 22s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 23s | RED | RED | RED | RED | RED | RED | YELLOW | YELLOW
 24s | RED | RED | RED | RED | RED | RED | RED | RED
 25s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 26s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 27s | GREEN | GREEN | RED | RED | RED | RED | RED | RED
 28s | YELLOW | GREEN | RED | RED | RED | RED | RED | RED
 29s | RED | YELLOW | RED | RED | RED | RED | RED | RED
 30s | RED | YELLOW | RED | GREEN | RED | RED | RED | RED
 31s | RED | RED | RED | GREEN | RED | RED | RED | RED
 32s | RED | RED | GREEN | GREEN | RED | RED | RED | RED
 33s | RED | RED | GREEN | GREEN | RED | RED | RED | RED
 34s | RED | RED | GREEN | YELLOW | RED | RED | RED | RED
 35s | RED | RED | GREEN | RED | RED | RED | RED | RED
 36s | RED | RED | YELLOW | RED | RED | RED | RED | RED
 37s | RED | RED | RED | RED | RED | RED | RED | RED
 38s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 39s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 40s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 41s | RED | RED | RED | RED | GREEN | GREEN | RED | RED
 42s | RED | RED | RED | RED | YELLOW | YELLOW | RED | RED
 43s | RED | RED | RED | RED | RED | RED | RED | RED
 44s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 45s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 46s | RED | RED | RED | RED | RED | RED | GREEN | GREEN
 47s | RED | RED | RED | RED | RED | RED | GREEN | GREEN

• Justin: Ahh, well I just found one thing that can be improved: lights should specify more like a minimum time alive, so that my intersection can automatically extend the length of a green light if it can.

Answer 1

First pass reading:

if (durations.containsKey(state)) return OptionalDouble.of(durations.get(state));
return OptionalDouble.empty();

1. The indentation is unconventional. Additionally I strongly recommend always putting curly braces where possible. This helps avoid issues when editing the code.
2. What you have here is a Double with null being signified as OptionalDouble.empty().
3. You could use durations.getOrDefault(state, OptionalDouble.empty()) to do all the messy work for you :)

public ActivationRules(IdentityHashMap<Light, Collection<Light>> simpleRules,
 IdentityHashMap<Light, Collection<ComplexActivationRule>> complexRules) {

I understand why you're forcing IdentityHashMap here, but I don't like seeing it here. The problem is that you're not uniquely identifying Lights. The solution is to use a unique identifier for Lights. Consider keeping a String as identifier.

 simpleRules.merge(triggers.iterator().next(), lights, (existing, toAdd) -> {
 existing.addAll(toAdd);
 return existing;
 });

I found this hard to understand, mostly because I haven't encountered merge all that much in live code. I think I'd understand better if this was written as:

simpleRules.computeIfAbsent(triggers.get(0), k -> new ArrayList<>()).addAll(lights);

Note that I replaced .iterator().next() with get(0), which should be semantically equivalent. Also note that this separates the default value from the merging process, which merge doesn't do that explicitly.

---

Design review

From a design view it's a bit annoying that ComplexActivationRule and SimpleActivationRule do not follow a unified interface. Given these names, I'd have expected these classes to inherit from a shared interface ActivationRule.

public interface ActivationRule {
 boolean matchesTrigger(List<Light> freshDisabledLights);
 void performActivation();
}

This would simplify activateTriggered to:

private void activateTriggered(List<Light> deactivated) {
 activationRules.stream()
 .filter(rule -> rule.matchesTrigger(deactivated))
 .forEach(ActivationRule::performActivation);
}

It moves the knowledge of how triggers are matched from Intersection into the different rules. The problem here of course is that activating lights is maybe not any of ActivationRule's business. If you want to enforce that, what do you think of the following:

activationRules.stream()
 .filter(rule -> rule.matchesTrigger(deactivated))
 .flatMap(ActivationRule::triggeredLights)
 .distinct() // maybe unnecessary?
 .forEach(Light::activate);

The interface for ActivationRule directly follows :)

I like very much how you enforce a certain order when building an Intersection. I don't like quite as much that your RuleBuilder requires Light instances to work. It might be cleaner to wrap RuleBuilding as an implementation detail of the intersection. Instead of accessing the currently building intersections's lights you can then instead just pass integers to the IntersectionBuilder. Building an intersection could look as follows:

Intersection intersection = Intersection.builder()
 .addLights(2, () -> new Light(4, 1, 0))
 .addActivationRule(1, 0)
 .addActivationRule(0, 1)
 //.addActivationRule(2, 0, 1)
 .activate(0)
 .build();

^^ this would build the same intersection as your usage example. At the end of the day it's convention that you specify triggers before target, but it's not strictly necessary.

This design avoids a possibly complex lambda, as well as the necessity to access Builder internals during the building process.

---

Summarizing

This code looks pretty clean, but I think the design can be improved a bit. As soon as that happens, the high abstractions will also read more fluently. Good Job :)