# problem2.txt
# Dan R. K. Ports <drkp@mit.edu>
# 6.170 PS5, 2004/03/16
# $Id: problem2.txt,v 1.2 2004/03/17 00:30:49 dan Exp $

REQUIREMENTS

We assume that at most one car will be able to make a turn from any
particular lane in a given time slice. This is enforced by the
requirement for a 30-foot cushion between cars. This implementation
relies on this fact, though it would not be difficult to change the
implementation (just process as many cars from each Lane's output
queue as are available and able to make their turn).


DESIGN

The CloverLeaf class extends the Filter abstract base class. An
Intersection base class was not used, because the Filter base class
already provides the interface and implementation necessary to
represent a generic filter in a pipe-and-filter simulator. As the
CloverLeaf and TrafficLight classes did not share any particular
interfaces that generic Filters do not, defining an Intersection
class did not provide any apparent advantage.

Each time simulate() is called and the intersection is simulated for
a timeslice, the CloverLeaf iterates through the list of incoming
lanes, and checks whether a car is waiting to make a turn. If so, it
identifies the destination lane, and checks whether that lane can
accept another car (due to the space cushion requirement). If so, it
moves the car from one lane to the other, and calls the makeTurn
function.

This design does not prevent starvation. It could be modified to do
so by changing the order in which incoming lanes are checked for cars
waiting to make turns; rather than starting at the same incoming lane
each time, it could rotate through them. This would prevent the same
lane from always being serviced first and starving out the other
lanes each time.

 
TESTING

The CloverLeaf class was tested using a subset of the test world from
TrafficTest. A CloverLeaf intersection with two incoming lanes and two
outgoing lanes was generated, along with a few Cars, and all the
necessary GeoPoints and RoadSegments and Routes. The getLocation
method was tested first. The next test consisted of a single car
traveling through the intersection. This was followed by two cars
traveling through the intersection at the same time without
interfering with each other, and two cars traveling through the
intersection at the same time, trying to reach the same destination
lane.

All tests were passed.


ANALYSIS

The CloverLeaf class was successfully designed and implemented, and
all tests were passed.

The design correctly implements a cloverleaf intersection simulator,
but some improvements could be made:
  - starvation could be dealt with, as detailed above
  - The design would be more elegant if it could eliminate dependency
    on the BipartiteGraph passed as an argument to
    simulate(). Ideally, the CloverLeaf class should not even need to
    know about the BipartiteGraph, if the Filter abstract base class
    provided an appropriate interface (in the style of the emit() and
    receive() methods) for querying the input pipes. Failing that, it
    would at least be better for the CloverLeaf to query its
    associated Simulator for its BipartiteGraph rather than requiring
    it to be passed as an argument to simulate().
  - The implementation should be more resilient to calls that violate
    the @requires contract, throwing exceptions.