Thursday, March 18, 2004
Contents:Lab 2 is today in W20!
PS6 is due on Tuesday, April 6th:
PS6 checkpoint: CANCELED!
Overview (summarized from the PS6 instructions). In this problem set you will assemble the modules you developed in problem sets 3 through 5, as well as some additional modules, to build Traffick, a traffic simulator for Boston and Cambridge. The main components of the assignment are:
/mit/6.170/traffickdb)
ps6.TrafficSourceReader, that reads this format.
ps6.Traffick, that allows
Traffick to be executed from another program. The staff will use that class to test your
simulator. The staff has provided a skeletal implementation for you
to fill in.
Review the suggested schedule. PS6 is even longer than the other problem sets.
Be confident, though. You already implemented many pieces that you need and the staff has provided some utility classes to help you with ps6.
Checkpoint: Deadline CANCELED.
The main challenge is to get started. You must show a TA or LA that your code can load the smallest of the databases of road segments and intersections (the tiny database).
ps6.RoadSystemReader
class that reads a database and provides access to the information it
represents: road segments, intersections, and speed limits.
The second challenge is to read the whole assignment and think about it:
ps6 has some performance requirements. If you find that your implementation performs badly, don't start optimizing all over the place. If you do so, you're unlikely to improve the performance dramatically, and you'll probably introduce bugs into your code. Instead:
Routes,
instead of ArrayLists you might want to use the immutable queue data structure
described at the end of lecture 7. For BipartiteGraph, you
should prefer hashtables to lists. Also, the objects that you use
as keys must have reasonable hash functions. If you just return 1, your
hashtables will degenerate from constant to linear time.
TimeProfiler.java class to be useful. It is a simple abstraction that
attempts to model a stopwatch in your code. You can tell the profiler to start
timing and stop timing at any point, and it can print you some detailed statistics
using toString().
For the provided code, the place to start is the
ps6.reader package. This package contains utilities for
reading Traffick data out of XML files as well as utilities for
reading RoadSegment data out of the Tiger database compiled by the US
Census Bureau.
In the ps6.reader package, there is a
ps6.reder.RoadSystemReader class. This class reads
information about roads and intersections. This class will let you
construct the topology of roads to simulate. When you create an
instance of that class, you must specify a directory location. The
class will look for three files in that directory:
Once created, the RoadSystemReader provides two
methods that allow you to iterate through all the lanes and
intersections that were read. Below is the object model of all objects
reachable from the RoadSystemReader:
After creating the topology, you need to create traffic sources
that will inject cars into the simulation. In the reader package,
class TrafficSourceReader reads information about traffic
sources. In its constructor, TrafficSourceReader takes as
parameter a file with the xml description of all the traffic
sources. Once it read the file, the TrafficSourceReader
allows a client to iterate through a list of
TrafficSourceDescriptors.
Finally, class RouteGenerator helps you generate Routes
for TrafficSources manually.
In the graphics package, class TraffickPalette is
designed to help you develop the GUI for the Traffick simulator. It
contains methods such as drawCar and
drawLane.
Class TraffickSample, in the top level package, shows
examples of using the TraffickPalette. Take a look at
these classes after doing Lab 2.
At the top level, class Traffick is the main entry
point for the traffick simulator. It contains the programmatic
interface and the main method starts the traffick
GUI. The class already has a skeleton ready for you to fill out!
Finally, class TimeProfiler is a utility class. It can
be used to instrument your code and understand where your system
spends most of its time. To use TimeProfiler, you should
call the start and stop methods at the entry
and exit to some code fragment. You can then periodically call
stats to print the statistics gathered so far by each
timer instance.
Note: material and examples in this section come from the GOF book, from lecture notes, and from Bloch.
A design pattern is:
The third point above is worth stressing. You may feel that some of the design patterns seem obvious or simple and also that you have used design patterns without realizing you were doing so. That is the whole point! Design patterns are nice when they are simple and most people can think of them on their own if needed. It is still important to study design patterns so that you have a common vocabulary that you can use to quickly convey your ideas to other engineers when discussing software design.
As a nice analogy, think of Economics. The best economists in the world disagree with each other on lots of points; however, it is still important for economics students to learn about all the different viewpoints. That way, when they debate over Keynsian multipliers, supply-side economics, monetary policy stimulated demand, and all the other models that exist, everyone speaks the same language and can successfully debate with each other about their views rather than having to restate each model every time.
You shouldn't go through the Gang Of Four book and try to cram every single design pattern possible into your PS6 or final project in hopes of winning the best design prize. It won't work!
Design patterns are not free! A design with a pattern is not necessarily better than a design without a pattern. Usually a pattern can solve one nagging problem but sacrifices some other convenience. A static factory method allows interning, but then makes subclassing more difficult! A singleton may seem nice and cool, but what if you really could use more than one instance of the object? A visitor may allow double-dispatch, but sometimes operations are context-sensitive and makes writing each visitor much more difficult.
Design patterns should only be introduced into your design or implementation after you have noticed a problem (hence the advantage of prototyping). After you have determined that there is a problem, and investigated the source of the problem, looking at a design patterns reference will often help you to solve your problem without having to reinvent the wheel.
We will cover the following design patterns today:
An IDE, for example, may want to ensure that at most one instance of the debugger exists at any time.
public class Debugger {
private static final Debugger INSTANCE = new Debugger();
private Debugger() { ... }
public static Debugger getInstance() {
return INSTANCE;
}
}
Additionally, many development sessions do not involve the use
of the debugger, so the instance doesn't have to be created until
the first time it is used:
public class Debugger {
private static Debugger INSTANCE;
private Debugger() { ... }
public static Debugger getInstance() {
if ( INSTANCE == null )
INSTANCE = new Debugger();
return INSTANCE;
}
}
Some other advantages of the singleton pattern are:
getInstance()
method and return subtypes.
Provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation. An iterator exposes a generic interface.
Key idea: decouple the functionality of the collection from the traversal functionality.
public interface Aggregate {
public Iterator iterator();
}
public interface Iterator {
public boolean hasNext();
public Object next();
public void remove();
}
Below is the resulting MDD:
Example: In Java, all collections can return an
Iterator that allows a client to iterate through the
elements of the collection without knowing the concrete collection
class. Some collections support different kinds of iterators:
unidirectional, bi-directional.
The Iterator pattern is generally applicable to all kinds of data structures.
Consider a class Maze that represents the maze for your
favorite video game.
class Maze {
Maze() { ... }
void addRoom(Room r) { ... }
Room roomNb(int nb) { ... }
...
}
Now let's write a class MazeGame that creates a maze.
One straightforward way to create a maze is with a series of
operations that add components to a maze and then interconnects
them. For example, let's create a maze consisting of two rooms with a
door between them:
class MazeGame {
...
Maze createMaze() {
Maze aMaze = new Maze();
Room r1 = new Room(1);
Room r2 = new Room(2);
Door theDoor = new Door(r1,r2);
aMaze.addRoom(r1);
aMaze.addRoom(r2);
r1.setSide(NORTH, new Wall());
r1.setSide(EAST, theDoor);
r1.setSide(SOUTH, new Wall());
r1.setSide(WEST, new Wall());
r2.setSide(NORTH, new Wall());
r2.setSide(EAST, new Wall());
r2.setSide(SOUTH, new Wall());
r2.setSide(WEST, theDoor);
return aMaze;
}
...
}
Q: What is the problem with this method?
A: It hard-codes the classes of maze, rooms, doors, and walls.
What if we wanted to create a
BombedMazeGame or an EnchantedMazeGame?
We'll introduce factory methods to let subclasses choose these components.
First we'll define factory methods in MazeGame for creating
the maze, room, wall, and door objects:
class MazeGame {
Maze createMaze() { ... }
// Factory methods
Maze makeMaze() {
return new Maze();
}
Room makeRoom(int n) {
return new Room(n);
}
Wall makeWall() {
return new Wall();
}
Door makeDoor(Room r1, Room r2) {
return new Door(r1,r2);
}
}
Each factory method returns a maze component of a given
type. MazeGame provides default implementations that
return the simplest kinds of maze, rooms, walls, and doors.
Now we can rewrite CreateMaze to use these factory
methods:
class MazeGame {
...
Maze createMaze() {
Maze aMaze = makeMaze();
Room r1 = makeRoom(1);
Room r2 = makeRoom(2);
Door theDoor = makeDoor(r1,r2);
aMaze.addRoom(r1);
aMaze.addRoom(r2);
r1.setSide(NORTH, makeWall());
r1.setSide(EAST, theDoor);
r1.setSide(SOUTH, makeWall());
r1.setSide(WEST, makeWall());
r2.setSide(NORTH, makeWall());
r2.setSide(EAST, makeWall());
r2.setSide(SOUTH, makeWall());
r2.setSide(WEST, theDoor);
return aMaze;
}
...
}
To create the BombedMazeGame and EnchantedMazeGame,
all we have to do is:
class BombedMazeGame extends MazedGame {
BombedMazeGame() {}
Room makeRoom(int n) {
return new RoomWithABomb(n);
}
Wall makeWall() {
return new BombedWall();
}
}
class EnchantedMazeGame extends MazedGame {
EnchantedMazeGame() {}
Room makeRoom(int n) {
return new EnchantedRoom(n,CastSpell());
}
Door makeDoor(Room r1, Room r2) {
return new DoorNeedingSpell(r1,r2);
}
private Spell castSpell() { ... }
}
Below is the partial MDD:
Factory methods have several additional advantages compared to constructors:
When there are many objects to construct, we might want to group them all into a single factory object. Factory objects also allow sibling classes to share the same factory methods.
class MazeFactory {
Maze makeMaze() { return new Maze(); }
Room makeRoom(int n) { return new Room(n); }
Wall makeWall() { return new Wall(); }
Door makeDoor(Room r1, Room r2) {
return new Door(r1,r2);
}
}
class BombedMazeFactory extends MazedFactory {
Room makeRoom(int n) { return new RoomWithABomb(n); }
Wall makeWall() { return new BombedWall(); }
}
class EnchantedMazeFactory extends MazedFactory {
Room makeRoom(int n) { return new EnchantedRoom(n,CastSpell()); }
Door makeDoor(Room r1, Room r2) {
return new DoorNeedingSpell(r1,r2);
}
private Spell castSpell() { ... }
}
The MazeGame class can then be instantiated with the
appropriate type of factory or can take a factory as parameter to
the createMaze method.
class MazeGame {
Maze createMaze(MazeFactory mfactory) {
Maze aMaze = mfactory.makeMaze();
Room r1 = mfactory.makeRoom(1);
Room r2 = mfactory.makeRoom(2);
Door theDoor = mfactory.makeDoor(r1,r2);
aMaze.addRoom(r1);
aMaze.addRoom(r2);
r1.setSide(NORTH, mfactory.makeWall());
r1.setSide(EAST, theDoor);
r1.setSide(SOUTH, mfactory.makeWall());
r1.setSide(WEST, mfactory.makeWall());
r2.setSide(NORTH, mfactory.makeWall());
r2.setSide(EAST, mfactory.makeWall());
r2.setSide(SOUTH, mfactory.makeWall());
r2.setSide(WEST, mfactory.theDoor);
return aMaze;
}
}
This pattern is also called Abstract Factory.
Consider a spreadsheet system that includes embedded graphs that view the data contained in the cells. In this system, as a user changes the data in the cells, the graphs should be notified of the changes and they should update their diagrams appropriately. The subject is the data model and the observers are the embedded graphs.
The benefit of the Observer pattern is that it decouples the observer from the subject. The subject doesn't need to know anything special about its observers. Instead, the subject simply allows observers to subscribe. When the subject generates an event, it simply passes it to each of its observers.
public interface Subject {
public void addObserver(Observer o);
public void removeObserver(Observer o);
}
public interface Observer {
public void receiveUpdate(Subject s);
}
In the code above, the Subject interface defines the methods that a Subject must implement in order for Observers to add and remove themselves from the Subject. The Observer interface (above) lists the methods that an Observer must implement so that a Subject can send an update notification to the Observer.
So how would we go about coding the spread sheet example?
public class SpreadSheetData implements Subject {
...
public void addObserver( Observer o ) { observers.add(o); }
public void removeObserver( Observer o ) { observers.remove(o); }
private Set observers = new HashSet();
private void notify() {
for ( Iterator i = observers.iterator(); i.hasNext(); ) {
Observer o = (Observer)i.next();
o.receiveUpdate();
}
}
}
public class SpreadSheetGraph implements Observer {
...
public void receiveUpdate(Subject s) {
...
}
}
Even better, we could also have a GenericSubject
class take care of the notifications:
public class GenericSubject implements Subject {
public void addObserver( Observer o ) { observers.add(o); }
public void removeObserver( Observer o ) { observers.remove(o); }
private Set observers = new HashSet();
protected void notify() {
for ( Iterator i = observers.iterator(); i.hasNext(); ) {
Observer o = (Observer)i.next();
o.update();
}
}
...
}
public class Subject extends GenericSubject {
...
}
Below is the resulting MDD:
Java provides support for the Observer pattern:
public Interface Observer {
public void update(Observable o, Object arg);
}
public class Observable {
public void addObserver(Observer o) { ... }
public void deleteObserver(Observer o) { ... }
public void notifyObservers(Observable o) { ... }
...
}
public interface Rectangle {
/** @effects grow or shrink this by the given factor **/
public void scale(float factor);
// other operations
public float area();
public float getWidth();
public float getHeight();
...
}
Suppose that you have an already implemented class
NonScaleableRectangle, which does not have the scale
method, but has setHeight and setWidth methods, and
has all of the other methods in Rectangle. If we want to use
NonScaleableRectangle to satisfy the Rectangle
interface, we can write an adapter. We can do this using either
subclassing or delegation. The solution using subclassing would look
like:
public class AdaptingRectangle extends NonScaleableRectangle implements Rectangle {
public void scale(float factor) {
setWidth(factor*getWidth());
setHeight(factor*getHeight());
}
}
A solution using delegation would look like:
public class AdaptingRectangle implements Rectangle {
private NonScaleableRectangle r;
public AdaptingRectangle(width w, height h) {
r = new NonScaleableRectangle(w,h);
}
public void scale(float factor) {
r.setWidth(factor*getWidth());
r.setHeight(factor*getHeight());
}
public float area() {
return r.area();
}
public float getHeight() {
return r.getHeight();
}
...
}
Below are the resulting MDDs:
To summarize, the Adapter pattern is useful when you want to use an existing class, but its interface does not match the interface that you need.