Handout P5

Quick links:

• Writing Abstraction Functions and Rep Invariants
• Problem Set Guidelines
• A Guide to Specifications
• HTML specifications for this problem set
• Starter code

Contents:

• Purpose
• Preamble
• Getting Started
• Lanes
  • Problem 1: Lane (20 points)
• Intersections
  • Cloverleaf Intersections
  • Problem 2: CloverLeaf (20 points)
  • Traffic Light Intersections
  • Problem 3: TrafficLight (25 points)
• The Traffic Simulator
  • Problem 4: Testing the Traffic Simulator (15 points)
  • Problem 5: Module Dependency Diagram (20 points)
• What to Turn In
• Hints
• Errata
• Q & A

Warning: This is a long assignment, so we suggest starting early. Also, we recommend that you read the entire problem set before you begin working.

Important notices

If your Problem Set 3 and 4 classes do not work correctly, you should fix them before going any further; this problem set depends on them. You are allowed to collaborate with other students in fixing classes from previous problem sets; as a special exception, you may share test cases for Problem Sets 3 and 4 only, but not specs or implementations, and you may not share any part of your Problem Set 5 solution. All other parts of the collaboration policy still hold, and the names of your collaborators must appear prominently in your documentation. If in doubt about following the policy, ask a staff member (TA or lecturer).

When you complete the assignment, be sure to log onto Athena and run:

athena% validate6170 ps5

Read the output message carefully!

Purpose

This assignment gives you additional practice in choosing designs, specifying them, writing tests to verify your specifications, and implementing classes to pass your tests. In addition, you will learn the advantages of well-chosen interfaces when you reuse your generic graph and simulator code with different kinds of pipes and filters that are specific to a traffic simulator.

Preamble

To review, Problem Sets 3, 4, 5, and 6 address different aspects of the design, implementation, documentation, and testing of Traffick, a traffic simulator for Boston and Cambridge. In Problem Set 3, you built basic data abstractions such as Car, Route, RoadSegment, and GeoPoint. In Problem Set 4, you designed and implemented ADTs for a generic BipartiteGraph and Simulator using pipes and filters, which were used to build real-time simulations.

In this problem set, you will design and implement abstract data types using your classes from previous problem sets to represent parts of a traffic simulator: a street with cars moving along it (Lane) and intersections of various kinds (CloverLeaf and TrafficLight). You will also implement an integration test called TrafficTest along with helper methods in TrafficTestDriver to verify that your solution works. When you finish this problem set, you will have a complete, albeit rudimentary, traffic simulator and a client that uses it. In Problem Set 6, you will augment this traffic simulator to construct a street graph from the US Census Bureau database, to add traffic monitors that measure traffic flow statistics, and to provide a user interface.

Like Problem Set 4, this problem set will give you lots of design practice. Follow the advice in Problem Set 4's preamble about considering different designs and the tradeoffs between them.

Getting Started

Since you will be designing your own specifications in this assignment, we will only provide you with HTML documentation for your Problem Set 3 classes and TrafficTestDriver, along with the skeleton source files TrafficTestDriver.java and TrafficTest.java to write your unit test. Since you designed your own specifications in Problem Set 4 for BipartiteGraph and Simulator, you will have to rely on your own generated HTML documentation for those classes; they will be useful in completing this problem set.

In the first three problems, your job is to transform English-language requirements for a driving lane, a cloverleaf intersection, and a traffic light intersection into Javadoc-comment specifications such as the staff-provided ones in past problem sets. In the fourth problem you will implement a test driver that will allow the staff to exercise your classes according to the problem set requirements and your specifications. In the last problem you will draw a module dependency diagram (MDD) of all the classes you have designed and/or implemented in Problem Sets 3, 4, and 5.

You can get the starter files for Problem Set 5 by using CVS. Follow the problem set checkout instructions and checkout the ps5 module from your repository. You must have your ps3 and ps4 projects checked out, since the ps5 project depends on them.

Your code MUST work on Athena, so if you choose to work on a non-Athena machine, please take a few minutes before submitting your solution to ensure that it runs correctly on Athena. Once everything is in order, read the Problem Set Submission instructions for how to run a final check of your code and turn it in.

Lanes

Recall from Problem Set 4 that a pipe-and-filter system consists of work objects flowing along pipes that are connected together by filters. In Traffick, the work objects are Cars, a class you implemented in Problem Set 3. The pipes are lanes, and the filters are intersections, where two or more road segments come together. In this problem set, you have to design and implement the pipes and the filters for Traffick.

A lane is a pipe with cars moving along it. An important property of a lane is the RoadSegment (from Problem Set 3) that it represents in the real world. A Lane represents a single lane of cars, and its direction/orientation is the same as its underlying RoadSegment. A two-way road in the real world will be represented by two Lanes, one for each direction. (For simplicity, we won't simulate roads with more than one lane in each direction.)

A lane has a speed limit, measured in miles per hour. When a car enters a lane, its speed is set to the lane's speed limit. Cars always travel at one of two speeds: their current lane's speed limit if they are free to move, or zero if they are forced to stop (e.g. while waiting at the end of a lane). For simplicity, we won't worry about time to accelerate or decelerate; the change in speed happens instantly. We also won't model speeders or slowpokes who don't drive the speed limit.

When a lane is simulated for a time slice, it tells each of the cars in the lane to drive for the time slice duration. For simplicity, if a car reaches the end of the road segment before the time slice expires (i.e., Car.drive() returns a nonzero time remaining), we'll assume that it wastes the rest of the time slice stopped there.

Since cars cannot occupy the same space, every pair of cars in the lane must be separated by a space cushion of at least 30 feet. Thus, after a car enters the lane, it must travel at least 30 feet before another car is permitted to enter the lane. Similarly, if a car is stopped at the end of the lane (waiting to get through an intersection), then the car behind it must stop 30 feet back. However, you can treat the cars as single points in terms of measuring their position or distances between them.

When a car reaches the end of the road segment represented by the lane, there are two possibilities. If the car has reached the end of its route (i.e., Car.hasArrived() returns true), then it simply parks, disappearing from the system immediately. Otherwise, if the car wants to continue onto another road segment, then it must wait at the end of the lane until the intersection there allows it to turn.

Problem 1: Lane (20 points)

Design and implement the Lane class as described below. Place the requested documentation in the file ps5/doc/problem1.txt.

• Specify. Write a complete specification for Lane as Javadoc comments in the source file by following the format used in previous problem sets and the guide to specifications. Use the requirements given above; document any ambiguities, how you chose to resolve them, and your rationale.
• Test. Write test cases for your specification; concentrate more on testing typical uses of your class rather than exhausting all possible inputs. You should use JUnit for your test framework. Be sure to justify, in a concisely written explanation, your testing strategy and why you believe that your test cases are adequate but not excessive.
• Choose the rep. Decide upon a representation for your implementation. Write down the corresponding abstraction function and a representation invariant; detailed examples can be found in the guide to writing AFs and RIs. Your documentation should discuss your choice of representation, including comparisons against other representations you considered.
• Implement. Implement your specification and test it against your test suite. Include your abstraction function and representation invariant in a comment in your code. Also include a checkRep() method that confirms that the representation invariant is satisfied, and call this method at appropriate points in your code. After testing, you may disable (e.g., comment out) any checkRep() calls if they create a severe and measurable performance hit. We still need to be able to see where you would have placed your calls, but if your program is unbearably slow, you may disable the checks. (If your ADT does not call checkRep() for certain methods, then the test driver should call checkRep() while testing those methods because during testing, correctness is generally more important than speed.)

You are free to design any additional classes you need to complete this problem, but you will need to follow the same procedure: specify, test, choose the rep, and then implement. Also be sure to check in these additional source files into your CVS repository and include their documentation in your ps5/doc/problem1.txt file.

Your documentation should follow the format we have used in previous problem sets and in our guidelines for documenting a software system, including sections for Requirements, Design, Testing, and Analysis. Be sure to address the following questions in your ps5/doc/problem1.txt file:

• How does the design of your Lane class incorporate RoadSegment -- by inheritance or by composition? Why did you make that decision, and what are the tradeoffs between the two approaches in this case?
• Do you need any intersections to unit test your Lane class? Why or why not?

Intersections

An intersection is a filter that transfers cars from its incoming lanes to its outgoing lanes. Although each car chooses where it wants to turn (Car.getNextTurn()), the intersection decides when a car may turn. Different kinds of intersections have different rules for moving cars through. For example, a TrafficLight intersection will only transfer cars from incoming lanes that currently have a green light.

Assume that a car can cross an intersection instantaneously. When you simulate an intersection for a timeslice, it should transfer a car only if it can make a legal turn according to the following conditions: it has reached the end of the incoming lane, the desired outgoing lane allows it to enter (i.e., there is a big enough space cushion at the start of the outgoing lane), and the car meets any special rules of the intersection. If multiple cars meet these conditions, the intersection should transfer all of them as long as there are no conflicts. If cars from two or more incoming lanes are allowed to turn into the same outgoing lane, the intersection should choose one of them and block the others; the specific decision algorithm can be chosen by the implementor. Intersections should not stall by holding back any car that can make a legal turn.

An important property of an intersection is its location in the world, which should be represented by a GeoPoint.

Here is the graph for a typical four-way intersection:

Note that the labels in this picture (e.g. Memorial Drive 1-Westbound and its equivalent abbreviation MD1-W) represent RoadSegments, not Strings.

You only need to implement two kinds of intersections in this problem set (CloverLeaf and TrafficLight), but other kinds of intersections are easy to imagine (stop signs, yields, rotaries, etc.)

Cloverleaf Intersections

A cloverleaf is a kind of intersection that allows cars to flow smoothly from one road to another as long as there is room to drive. In the American road system, cloverleaf intersections are typically found at intersections of major highways (e.g. yields or merges).

In contrast, our traffic simulator will allow cloverleaf intersections to connect any roads together with arbitrary numbers of incoming and outgoing lanes. Furthermore, if two or more cars from different incoming lanes wish to turn onto the same outgoing lane, you are free to decide how your cloverleaf chooses which car it allows to pass; the waiting car will have to come to a complete stop and block its incoming lane.

When a cloverleaf is simulated for a time slice, all the cars that are ready and able to make a turn at the cloverleaf are allowed to make their turns, in an unspecified order.

Problem 2: CloverLeaf (20 points)

Specify, test, choose the rep, and implement the CloverLeaf class using the same procedure as for Lane. Document your design in a file called ps5/doc/problem2.txt. Be sure to address the following design questions in your documentation:

• Does your design define an Intersection base class shared by CloverLeaf and TrafficLight? Why did you make that decision, and what are the advantages of making the decision the other way?
• At most how many cars can be ready to turn from any given input lane at any given moment? What part of the requirements (i.e., this problem set description) guarantees this fact? Does your implementation of CloverLeaf depend on this fact? Should it depend on it, i.e., what are the tradeoffs of relying on this fact in your implementation?
• One problem that a simulator may suffer from is starvation. Look at the example below, a cloverleaf with two incoming lanes and only one outgoing lane. In one time slice, only one car can turn into the outgoing lane. (Why?) Let's say it's car A1. Assuming the speed limit on the lanes is high enough (or the time slices are long enough), the next time slice will bring up car A2 in its place. If the cloverleaf behaves exactly the same way, then it will allow car A2 to turn. If lane A is packed with cars, as at rush hour, the cars in lane B will never be allowed to turn -- lane B will be starved. Does your design suffer from starvation? How could you modify the requirements to forbid starvation? (Be specific!) How could you modify your implementation to implement this stronger requirement? (You don't have to actually implement it; just describe it.)

Traffic Light Intersections

A traffic light is an intersection that uses red lights to stop some of its incoming lanes of traffic, while presenting a green light to other incoming lanes and allowing them to proceed through the intersection. (For simplicity, we don't model yellow lights. The yellow light is just the last part of the green light, anyway.)

For example, a traffic light at a typical four-way intersection will give green lights to two incoming lanes (which face each other across the intersection) while giving red lights to the other two incoming lanes.

The incoming lanes are partitioned into green groups. Each green group is a set of one or at most two lanes that have a green light at the same time. A green group can be either a pair of incoming lanes or a single incoming lane. The two lanes in a green group pair are not necessarily directly opposite each other; at some intersections in the real world, they may even be at right angles, because the main road curves through the intersection. Every incoming lane must belong to exactly one green group and starts out in its own 1-lane green group by default.

At any given moment, only one green group has a green light, and all the other green groups have a red light. Each green group has a duration, which is the length of time in seconds that its green light lasts.

Green groups have an ordering defined as follows. Each incoming lane is associated with a RoadSegment that has a compass heading (RoadSegment.getHeading()). Green group G1 is less than green group G2 if the smallest compass heading of the lanes in G1 is less than the smallest compass heading of the lanes in G2. The example below shows a traffic light with 5 incoming lanes arranged in 3 green groups. (Outgoing lanes are not shown for simplicity.) Group G1 is less than G2, which is less than G3:

The ordering of green groups is used as the order to cycle through the green lights. Initially, the lowest green group has the green light. After its duration expires, the next green group is given the green light, and so on. After the highest green group gets the green light for its duration, the traffic light cycles back to the lowest green group again.

When a traffic light is simulated for one time slice, all the cars that are ready to make a turn and have a green light are allowed to make their turns, in an unspecified order. Only one green group may be active during a given time slice. If the current green group's duration elapses during or at the end of the time slice, then the next green group will be activated for the next time slice. Thus, durations will effectively be rounded up to the nearest whole time slice. An incoming lane in its own default green group has some unspecified default duration time. These default green groups can have their durations changed, and they can also be merged into one 2-lane green group with a new duration.

Problem 3: TrafficLight (25 points)

Specify, test, choose the rep, and implement the TrafficLight class. Document your design decisions in a file called ps5/doc/problem3.txt. Be sure to address the following design question in your documentation:

• Can a traffic light suffer from starvation, given the requirements above? Why or why not?

The Traffic Simulator

Now that you have classes for lanes, two different kinds of intersections, and cars, you are ready to construct and test a complete simulator for Traffick. It should use your ps4.BipartiteGraph to represent the configuration of lanes and intersections. There is an edge from a lane to an intersection if the lane comes into the intersection (i.e., if the lane's road segment ends at the intersection's location); similarly, there is an edge from an intersection to a lane if the lane leaves the intersection. Each edge should be labeled with the RoadSegment associated with the lane. Your traffic simulator should also allow cars to be inserted at the beginning of any lane and use your ps4.Simulator class to simulate timeslices alternately on all the lanes and all the intersections.

Problem 4: Testing the Traffic Simulator (15 points)

You will have to provide a test driver, TrafficTestDriver, that allows the staff tests to construct and use traffic simulations. We have provided a specification and a skeleton implementation of the test driver. You should fill in this file with your own code that constructs and uses instances of Lane, CloverLeaf, TrafficLight, and any other classes you may have included in your design.

We have also provided a skeleton JUnit test suite, TrafficTest, that uses TrafficTestDriver to construct a few simple simulations. You should make sure these tests work. The automated, private staff tests will also use your TrafficTestDriver, and you may choose to add more complicated tests to verify that your traffic simulator actually meets its specifications.

Problem 5: Module Dependency Diagram (20 points)

Draw an MDD for all the classes you have written for Problem Set 3, Problem Set 4, and this problem set. You can consult Lecture 9 notes or Liskov, sections 13.1-13.3, for references on MDDs.

Submit your diagram as a graphic file, with a filename like problem5.png or problem5.jpg. You can produce it using the Athena program dia or any software of your choice, or you many neatly draw it with pen and paper and use a scanner. We will accept the following formats: PNG, GIF, JPG, PS, and PDF. Please mail your TA before Tuesday if this is a problem.

What to Turn In

You should check in at least the following files to CVS, in the directories indicated below.

ps5/
   doc/
      problem1.txt
      problem2.txt
      problem3.txt
      problem5.ps (or whatever name you gave to the image)
   src/
      ps5/
         Lane.java
         LaneTest.java
         CloverLeaf.java
         CloverLeafTest.java
         TrafficLight.java
         TrafficLightTest.java
         TrafficTestDriver.java
         TrafficTest.java

Hints

We recommend that you design all the classes first, rather than going class-by-class doing design, specification, testing, documentation, and implementation. Similarly, you should write all the specifications before doing any testing or implementation, because you may find while writing the specifications that you need to make changes to your design.

You should not need to modify your BipartiteGraph or Simulator implementations (except to fix bugs). In particular, they should not mention Lane, CloverLeaf, TrafficLight, or the like. If you made an implementation error by including such references, remove them, but ensure that your BipartiteGraph and Simulator classes continue to work for Problem Set 4 as well as for Problem Set 5; both problem sets should use the same version of those classes.

Errata

The updates to the problem set files below are simply spec changes, which you view online, or one-line changes which you can make manually.

In the file TrafficTestDriver.java, the following specs were updated. You can copy and paste the new specs into your file, or you can just consult the online specs exclusively. None of the method signatures were changed. If in doubt, the online HTML specs are authoritative.

• You can assume that all Cars passed into injectCar(...) will have a valid Route; that is:
  

  • a corresponding lane has been added to the traffic simulator for every road segment in a car's full route
  • intersections have been added in between these lanes
  • appropriate edges have been added from incoming lanes to their intersections and from intersections to their outgoing lanes

• the timeslice in createSimulator(...) and the duration in both defineGreenGroup(...) methods should be in seconds.
• addEdge(...) can only be called once with the same simulator name, parent name, and child name, to guarantee the uniqueness of edges.

In the Ant buildfile, build.xml,

• The line
  

  <property name="java.api" value="http://java.sun.com/j2se/1.4.2/docs/api/index.html" />

  should read

  <property name="java.api" value="http://web.mit.edu/6.170/www/javadoc/j2sdk1.4.1-docs-api/" />

  If you were having problems generating Javadocs with Ant before, this should fix them.

Q & A

This section will list clarifications and answers to common questions about problem sets. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully rereading the problem set handout and the specifications) when you have a problem.

Back to the Problem sets page.

For problems or questions regarding this page, contact: 6.170-webmaster@mit.edu.