SE450: Lecture 7 (Simulation, Null Objects, Proxies)

Contents [0/13]

Proxy: Unmodifiable Collection [1/13]
Proxy: Another Example [2/13]
Simulation: Active and Passive Objects [3/13]
Simulation: Example 1 [4/13]
Simulation: Example 2 [5/13]
Simulation: Example 3 [6/13]
Simulation: Example 4 [7/13]
Simulation: TimeServer Implementation [8/13]
Simulation: Random numbers [9/13]
Project: Car Movement [10/13]
Project: Lights [11/13]
Project: Creating the road graph [12/13]
Project: Notes [13/13]

Proxy: Unmodifiable Collection [1/13]

file:UnmodifiableCollection.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package proxy;
import java.util.Collection;
import java.util.Iterator;
import java.io.Serializable;

@SuppressWarnings("serial")
class UnmodifiableCollection<E> implements Collection<E>, Serializable {
  Collection<E> c;

  UnmodifiableCollection(Collection<E> c) {
    if (c==null)
      throw new NullPointerException();
    this.c = c;
  }

  public int      size()                       {return c.size();}
  public boolean  isEmpty()                    {return c.isEmpty();}
  public boolean  contains(Object o)           {return c.contains(o);}
  public Object[] toArray()                    {return c.toArray();}
  public <T> T[]  toArray(T[] a)               {return c.toArray(a);}
  public String   toString()                   {return c.toString();}
  public boolean  containsAll(Collection<?> d) {return c.containsAll(d);}

  public Iterator<E> iterator() {
    return new Iterator<E>() {
      Iterator<E> i = UnmodifiableCollection.this.c.iterator();

      public boolean hasNext() {return i.hasNext();}
      public E next()          {return i.next();}
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }

  public boolean add(Object o){
    throw new UnsupportedOperationException();
  }
  public boolean remove(Object o) {
    throw new UnsupportedOperationException();
  }
  public boolean addAll(Collection<? extends E> c) {
    throw new UnsupportedOperationException();
  }
  public boolean removeAll(Collection<?> c) {
    throw new UnsupportedOperationException();
  }
  public boolean retainAll(Collection<?> c) {
    throw new UnsupportedOperationException();
  }
  public void clear() {
    throw new UnsupportedOperationException();
  }
}

Proxy: Another Example [2/13]

From Head first Design Patterns

file:ImageProxy.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package headfirst.proxy.virtualproxy;

import java.awt.Component;
import java.awt.Graphics;
import java.net.URL;

import javax.swing.Icon;
import javax.swing.ImageIcon;

class ImageProxy implements Icon {
  ImageIcon imageIcon;
  URL imageURL;
  Thread retrievalThread;
  boolean retrieving = false;

  public ImageProxy(URL url) { imageURL = url; }

  public int getIconWidth() {
    if (imageIcon != null) {
      return imageIcon.getIconWidth();
    } else {
      return 800;
    }
  }

  public int getIconHeight() {
    if (imageIcon != null) {
      return imageIcon.getIconHeight();
    } else {
      return 600;
    }
  }

  public void paintIcon(final Component c, Graphics  g, int x,  int y) {
    if (imageIcon != null) {
      imageIcon.paintIcon(c, g, x, y);
    } else {
      g.drawString("Loading CD cover, please wait...", x+300, y+190);
      if (!retrieving) {
        retrieving = true;

        retrievalThread = new Thread(() -> {
          try {
            imageIcon = new ImageIcon(imageURL, "CD Cover");
            c.repaint();
          } catch (Exception e) {
            e.printStackTrace();
          }
        });
        retrievalThread.start();
      }
    }
  }
}

file:ImageProxyTestDrive.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package headfirst.proxy.virtualproxy;

import java.net.MalformedURLException;
import java.net.URL;
import java.util.Enumeration;
import java.util.Hashtable;

import javax.swing.Icon;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;

public class ImageProxyTestDrive {
  ImageComponent imageComponent;
  JFrame frame = new JFrame("CD Cover Viewer");
  JMenuBar menuBar;
  JMenu menu;
  Hashtable<String,String> cds = new Hashtable<String,String>();

  public static void main (String[] args) throws Exception {
    ImageProxyTestDrive testDrive = new ImageProxyTestDrive();
  }

  public ImageProxyTestDrive() throws Exception{
    cds.put("Ambient: Music for Airports","http://images.amazon.com/images/P/B000003S2K.01.LZZZZZZZ.jpg");
    cds.put("Buddha Bar","http://images.amazon.com/images/P/B00009XBYK.01.LZZZZZZZ.jpg");
    cds.put("Ima","http://images.amazon.com/images/P/B000005IRM.01.LZZZZZZZ.jpg");
    cds.put("Karma","http://images.amazon.com/images/P/B000005DCB.01.LZZZZZZZ.gif");
    cds.put("MCMXC A.D.","http://images.amazon.com/images/P/B000002URV.01.LZZZZZZZ.jpg");
    cds.put("Northern Exposure","http://images.amazon.com/images/P/B000003SFN.01.LZZZZZZZ.jpg");
    cds.put("Selected Ambient Works, Vol. 2","http://images.amazon.com/images/P/B000002MNZ.01.LZZZZZZZ.jpg");

    URL initialURL = new URL(cds.get("Selected Ambient Works, Vol. 2"));
    menuBar = new JMenuBar();
    menu = new JMenu("Favorite CDs");
    menuBar.add(menu);
    frame.setJMenuBar(menuBar);

    for(Enumeration<String> e = cds.keys(); e.hasMoreElements();) {
      String name = e.nextElement();
      JMenuItem menuItem = new JMenuItem(name);
      menu.add(menuItem);
      menuItem.addActionListener(event -> {
        imageComponent.setIcon(new ImageProxy(getCDUrl(event.getActionCommand())));
        frame.repaint();
      });
    }

    // set up frame and menus

    Icon icon = new ImageProxy(initialURL);
    imageComponent = new ImageComponent(icon);
    frame.getContentPane().add(imageComponent);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(800,600);
    frame.setVisible(true);

  }

  URL getCDUrl(String name) {
    try {
      return new URL(cds.get(name));
    } catch (MalformedURLException e) {
      e.printStackTrace();
      return null;
    }
  }
}

file:ImageComponent.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package headfirst.proxy.virtualproxy;

import java.awt.Graphics;

import javax.swing.Icon;
import javax.swing.JComponent;

@SuppressWarnings("serial")
class ImageComponent extends JComponent {
  private Icon icon;

  public ImageComponent(Icon icon) {
    this.icon = icon;
  }

  public void setIcon(Icon icon) {
    this.icon = icon;
  }

  public void paintComponent(Graphics g) {
    super.paintComponent(g);
    int w = icon.getIconWidth();
    int h = icon.getIconHeight();
    int x = (800 - w)/2;
    int y = (600 - h)/2;
    icon.paintIcon(this, g, x, y);
  }
}

Simulation: Active and Passive Objects [3/13]

Agents act.

Agents know what they want to do.

One can model agents as finite automata.

Let's say I am implementing an airline reservation system. How do I do a simulation?

A passive view of a customer:

interface Customer {
  void addFlight(Flight f);
  void removeFlight(Flight f);
}

A more active view:

public interface Agent {
  public void run();
} 
class Main {
  List<Agent> q = new List<Agent>();
  for (i=0; i<numSimulated; i++)
    q.add(new SimulatedCustomer());
  for (i=0; i<numHuman; i++)
    q.add(new HumanCustomer());
  for (currentTime=0; currentTime<endTime; currentTime+=timeStep)
    for (Agent a : q)
      a.run();
}

If we think of customers as "subscribing" to a time service:

public interface Agent {
  public void run();
} 
public interface TimeServer {
  public long currentTime();
  public void add(Agent thing);
  public void run(int duration); 
}
class Main {
  TimeService q = TimeService ();
  for (i=0; i<numSimulated; i++)
    q.add(new SimulatedCustomer());
  for (i=0; i<numHuman; i++)
    q.add(new HumanCustomer());
  q.run(duration);
}

With "sparse" time you use a priority queue:

class Main {
  TimeServer q = new TimeServer();
  for (i=0; i<numSimulated; i++)
    q.enqueue(q.currentTime, new SimulatedCustomer());
  for (i=0; i<numHuman; i++)
    q.enqueue(q.currentTime, new HumanCustomer());
  q.run(duration); 
}
public interface TimeServer {
  public long currentTime();
  public void enqueue(long time, Agent thing);
  public void run(int duration); 
}
public interface Agent {
  public void run();
} 
class SimulatedCustomer implements Agent {
  int state;
  SimulatedCustomer(TimeServer q) { ... }
  public void run() {
    switch (state) {
      case ...
        ...
        q.enqueue(q.currentTime + 500, this);
        break;
      ...
    }
  }
}
class HumanCustomer implements Agent {
  HumanCustomer(TimeServer q, UI ui) { ... }
  public void run() {
    // create a menu whose options end with:
    // q.enqueue(q.currentTime + 500, this);
    ...
    ui.displayMenu(menu);
  }
}

Simulation: Example 1 [4/13]

file:Main.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
package agent.one;
import agent.Agent;
import agent.TimeServer;
import agent.TimeServerLinked;

public class Main {
  public static void main (String[] args) {
    TimeServer time = new TimeServerLinked();
    Agent a = new Tiger(time);
    time.enqueue(0,a);
    time.run(100);
  }
}

class Tiger implements Agent {
  private TimeServer time;
  public Tiger(TimeServer time) { this.time = time; }
  public void run() {
    System.out.println("It's " + time.currentTime() + " and I'm alive!");
    time.enqueue(10+time.currentTime(), this);
  }
}

Simulation: Example 2 [5/13]

file:Main.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package agent.two;
import agent.Agent;
import agent.TimeServer;
import agent.TimeServerLinked;

public class Main {
  public static void main (String[] args) {
    World w = World.instance;
    Agent a = new Tiger();
    w.time().enqueue(0,a);
    w.time().run(100);
  }
}

interface World {
  public static final World instance = new WorldObj();
  public TimeServer time();
  public Object[][] space();
}

class WorldObj implements World {
  private TimeServer time = new TimeServerLinked();
  private Object[][] space = new Object[100][100];
  public TimeServer time()  { return time; }
  public Object[][] space() { return space; }
}

class Tiger implements Agent {
  public void run() {
    World w = World.instance;
    System.out.println("It's " + w.time().currentTime() + " and I'm alive!");
    w.time().enqueue(10+w.time().currentTime(), this);
  }
}

Simulation: Example 3 [6/13]

file:Main.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package agent.three;
import agent.Agent;
import agent.TimeServer;
import agent.TimeServerLinked;
import java.util.Observer;

public class Main {
  public static void main (String[] args) {
    World w = World.instance;
    Agent a = new Tiger();
    w.enqueue(0,a);
    w.set(0,0,a);
    w.run(100);
  }
}

class Util {
  private Util() {}
  private final static long SEED = 2497;
  private final static java.util.Random r = new java.util.Random(SEED);
  static int random(int n) { return r.nextInt(n); }
  static boolean randomBoolean() { return r.nextBoolean(); }
}

interface World extends TimeServer {
  public static final World instance = new WorldObj();
  public int maxx();
  public int maxy();
  public Object get(int i, int j);
  public void set(int i, int j, Object a);
}

class WorldObj implements World {
  private final static int MAXX = 100;
  private final static int MAXY = 100;
  private TimeServer time = new TimeServerLinked();
  private Object[][] space = new Object[MAXX][MAXY];

  public int maxx()                      { return MAXX; }
  public int maxy()                      { return MAXY; }
  public Object get(int x, int y)        { return space[x%MAXX][y%MAXY]; }
  public void set(int x, int y, Object a){ space[x%MAXX][y%MAXY] = a; }
  public double currentTime()            { return time.currentTime(); }
  public void enqueue(double t, Agent a) { time.enqueue(t,a); }
  public void run(double d)              { time.run(d); }
  public void addObserver(Observer o)    { time.addObserver(o); }
  public void deleteObserver(Observer o) { time.deleteObserver(o); }
}

/* BUGS HERE */
class Tiger implements Agent {
  private int x;
  private int y;
  private World w = World.instance;
  private void moveRandom() {
    w.set(x,y,null);
    if (Util.randomBoolean()) { x = (x+1)%w.maxx(); }
    if (Util.randomBoolean()) { y = (y+1)%w.maxy(); }
    w.set(x,y,this);
  }
  public void run() {
    moveRandom();
    System.out.println("It's " + w.currentTime() + " and I'm alive at (" + x + "," + y + ")!");
    w.enqueue(10+w.currentTime(), this);
  }

}

Simulation: Example 4 [7/13]

file:Main.java [source] [doc-public] [doc-private]
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package agent.four;

public class Main {
  public static void main (String[] args) {
    World w = WorldF.instance(100,100);
    int i = 0;
    while (i<20) {
      try {
        new Tiger
        (Integer.toString(i), Util.random(w.maxx()), Util.random(w.maxy()));
        i++;
      } catch (SpaceOccupiedException e) {
      }
    }
    w.run(1000);
  }
}

class Util {
  private Util() {}
  private final static long SEED = 2497;
  private final static java.util.Random r = new java.util.Random(SEED);
  static int random(int n) { return r.nextInt(n); }
  static boolean randomBoolean() { return r.nextBoolean(); }
}

interface World extends TimeServer {
  public int maxx();
  public int maxy();
  public Visible get(int i, int j);
  public boolean set(int i, int j, Visible a);
}

class WorldF {
  private static World W;
  public static World instance(int maxx, int maxy) {
    if (W != null)
      throw new IllegalStateException();
    W = new WorldObj(maxx, maxy);
    return W;
  }
  public static World instance() {
    if (W == null)
      throw new IllegalStateException();
    return W;
  }
}

class WorldObj implements World {
  private final int maxx;
  private final int maxy;
  private final TimeServer time;
  private final Visible[][] space;

  WorldObj(int maxx, int maxy) {
    this.maxx = maxx;
    this.maxy = maxy;
    time = new TimeServerLinked();
    space = new Visible[maxx][maxy];
    for (int x = 0; x < maxx; x++ )
      for (int y = 0; y < maxy; y++ )
        space[x][y] = NullVisible.instance;
  }
  public int maxx() { return maxx; }
  public int maxy() { return maxy; }
  public Visible get(int x, int y) {
    return space[(x+maxx)%maxx][(y+maxy)%maxy];
  }
  public boolean set(int x, int y, Visible a){
    if (a == null) {
      a = NullVisible.instance;
    } else if (get(x,y) != NullVisible.instance) {
      return false;
    }
    space[(x+maxx)%maxx][(y+maxy)%maxy] = a;
    return true;
  }
  public long currentTime()              { return time.currentTime(); }
  public void enqueue(long t, Agent a)   { time.enqueue(t,a); }
  public void run(int d)                 { time.run(d); }
}

interface Visible {
  public final static int NULL = 0;
  public final static int TIGER = 1;
  public int type();
}

class NullVisible implements Visible {
  private NullVisible() {}
  public final static Visible instance = new NullVisible();
  public int type() { return Visible.NULL; }
  public String toString() { return "Null"; }
}

class SpaceOccupiedException extends RuntimeException {
  private static final long serialVersionUID = 2008L;
};

class Tiger implements Agent, Visible {
  private String name;
  private int x;
  private int y;
  private World w = WorldF.instance();

  public Tiger(String name, int x, int y)
      throws SpaceOccupiedException
  {
    this.name = name;
    if (!w.set(x,y,this))
      throw new SpaceOccupiedException();
    this.x = x;
    this.y = y;
    w.enqueue(1+w.currentTime(), this);
  }

  public String toString() { return name + "@(" + x + "," + y + ")"; }

  public int type() { return Visible.TIGER; }
  public void check() {
    checkAjacent();
  }
  public void run() {
    //System.out.print(this + " moves to ");
    moveRandom();
    //System.out.println(this);
    w.enqueue(10+w.currentTime(), this);
  }

  private void checkAjacent() {
    for (int i=-1; i<=1; i++) {
      for (int j=-1; j<=1; j++) {
        if (i==0 && j==0)
          continue;
        if (w.get(x+i,y+j).type() == Visible.TIGER)
          System.out.println(this + " roars at " + w.get(x+i,y+j) + " at " + w.currentTime());
      }
    }
  }
  private void moveRandom() {
    w.set(x,y,null);
    int xNew, yNew;
    do {
      xNew = (w.maxx() + this.x -1 + Util.random(2)) % w.maxx();
      yNew = (w.maxy() + this.y -1 + Util.random(2)) % w.maxy();
      //System.out.println("Trying (" + x + "," + y + ")");
    } while (!w.set(xNew,yNew,this));
    this.x = xNew; this.y = yNew;
  }
}

Simulation: TimeServer Implementation [8/13]

file:Agent.java [source] [doc-public] [doc-private]
01
02
03
04
05
package agent;

public interface Agent {
  public void run();
}

file:TimeServer.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
package agent;

public interface TimeServer {
  public double currentTime();
  public void enqueue(double waketime, Agent thing);
  public void run(double duration);
  public void addObserver(java.util.Observer o);
  public void deleteObserver(java.util.Observer o);
}
If you want to use this for the project:

The idea is that whenever an agent adds itself to the timeserver, it
specifies its waketime.  The waketime must be greater than
currenttime, or the enqueue method should throw an exception.  The
timeserver orders agents by their waketime, so the one to wake first is
always at the front.  So in order to run the next agent, the first
agent is dequeued, and then the currenttime is set to its waketime,
then the agent is run.

For a car:
Start the car with waketime=currenttime.
When the car is run(), it should re-enqueue itself with
waketime=currenttime+timestep.

For a light:
Start the lightController with waketime=currenttime.
When the lightController is run(), it should re-enqueue itself with
waketime=currenttime+this._state.getDuration(), where the state
duration is whatever is appropriate for this state.

For a source:
Start the source with waketime=currenttime.
When the source is run(), it should re-enqueue itself with
waketime=currenttime+this._carCreationInterval, where the interval
indicates the time between car creations for this source.        

I implemented the TimeServer using a linked list with a dummy node.

file:TimeServerLinked.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package agent;

import java.util.Observable;

public final class TimeServerLinked extends Observable implements TimeServer {
  private static final class Node {
    final double waketime;
    final Agent agent;
    Node next;

    public Node(double waketime, Agent agent, Node next) {
      this.waketime = waketime;
      this.agent = agent;
      this.next = next;
    }
  }
  private double currentTime;
  private int size;
  private Node head;

  /*
   * Invariant: head != null
   * Invariant: head.agent == null
   * Invariant: (size == 0) iff (head.next == null)
   */
  public TimeServerLinked() {
    size = 0;
    head = new Node(0, null, null);
  }

  public String toString() {
    StringBuilder sb = new StringBuilder("[");
    Node node = head.next;
    String sep = "";
    while (node != null) {
      sb.append(sep).append("(").append(node.waketime).append(",")
      .append(node.agent).append(")");
      node = node.next;
      sep = ";";
    }
    sb.append("]");
    return (sb.toString());
  }

  public double currentTime() {
    return currentTime;
  }

  public void enqueue(double waketime, Agent agent)
      throws IllegalArgumentException
  {
    if (waketime < currentTime)
      throw new IllegalArgumentException();
    Node prevElement = head;
    while ((prevElement.next != null) &&
        (prevElement.next.waketime <= waketime)) {
      prevElement = prevElement.next;
    }
    Node newElement = new Node(waketime, agent, prevElement.next);
    prevElement.next = newElement;
    size++;
  }

  Agent dequeue()
  {
    if (size < 1)
      throw new java.util.NoSuchElementException();
    Agent rval = head.next.agent;
    head.next = head.next.next;
    size--;
    return rval;
  }

  int size() {
    return size;
  }

  boolean empty() {
    return size() == 0;
  }

  public void run(double duration) {
    double endtime = currentTime + duration;
    while ((!empty()) && (head.next.waketime <= endtime)) {
      if ((currentTime - head.next.waketime) < 1e-09) {
        super.setChanged();
        super.notifyObservers();
      }
      currentTime = head.next.waketime;
      dequeue().run();
    }
    currentTime = endtime;
  }
}

Note below how one tests TimeServer without any "real" agents. Instead we use Mock Objects. We also saw this in the tests for CommandHistoryObj. Tools such as easymock make this easy.

file:TimeServerTEST.java [source] [doc-public] [doc-private]
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package agent;
import static org.junit.Assert.*;
import org.junit.Test;

public class TimeServerTEST {
  TimeServerQueue q = new TimeServerQueue();
  // TimeServerLinked q = new TimeServerLinked();

  @Test
  public void testThatEmptySizeIsZero() {
    assertEquals(0, q.size());
  }

  @Test
  public void testThatDequeueOnEmptyThrowsIndexOutOfBoundsException() {
    boolean exceptionOccurred = false;

    try {
      q.dequeue();
    } catch (java.util.NoSuchElementException e) {
      exceptionOccurred = true;
    }

    assertTrue(exceptionOccurred);
  }

  @Test
  public void testThatEnqueueFollowedByDequeueReturnsSameReference() {
    class TestThatEnqueueFollowedByDequeueReturnsSameReference
    implements Agent
    {
      public void run() {}
    }

    Agent x1 = new TestThatEnqueueFollowedByDequeueReturnsSameReference();
    q.enqueue(0, x1);
    assertSame(x1, q.dequeue());
    assertEquals(0, q.size());
  }

  @Test
  public void testThatElementsAreInsertedInOrder() {
    class TestThatElementsAreInsertedInOrder implements Agent {
      public void run() {}
    }

    Agent x1 = new TestThatElementsAreInsertedInOrder();
    Agent x2 = new TestThatElementsAreInsertedInOrder();
    q.enqueue(0, x2);
    q.enqueue(1, x1);
    assertSame(x2, q.dequeue());
    assertSame(x1, q.dequeue());
    q.enqueue(1, x1);
    q.enqueue(0, x2);
    assertSame(x2, q.dequeue());
    assertSame(x1, q.dequeue());
    q.enqueue(0, x1);
    q.enqueue(0, x2);
    assertSame(x1, q.dequeue());
    assertSame(x2, q.dequeue());
    q.enqueue(0, x2);
    q.enqueue(0, x1);
    assertSame(x2, q.dequeue());
    assertSame(x1, q.dequeue());
  }

  @Test
  public void testToString() {
    class TestToString implements Agent {
      public void run() {}
      public String toString() { return "x"; }
    }

    q.enqueue(0, new TestToString());
    q.enqueue(1, new TestToString());
    assertEquals("[(0.0,x);(1.0,x)]", q.toString());
  }

  @Test
  public void testCurrentTime() {
    class TestCurrentTime implements Agent {
      public void run() {}
    }

    double expected = 1230;
    q.enqueue(expected, new TestCurrentTime());

    assertEquals(0.0, q.currentTime(), .1e-6);
    q.run(expected);

    assertEquals(expected, q.currentTime(), .1e-6);
  }

  private double scratch;
  @Test
  public void testDoActionsAtOrBefore() {
    class TestDoActionsAtOrBefore implements Agent {
      private double myScratch;
      TestDoActionsAtOrBefore(double myScratch) {
        this.myScratch = myScratch;
      }
      public void run() {
        scratch = myScratch;
      }
    }

    double time1 = 12;
    double time2 = 23;
    double value1 = 42;
    double value2 = 27;

    q.enqueue(time1, new TestDoActionsAtOrBefore(value1));

    scratch = 0;
    q.run(time1 - 1);
    assertEquals(0.0, scratch, .1e-6);

    scratch = 0;
    q.run(1);
    assertEquals(value1, scratch, .1e-6);

    q.enqueue(time2, new TestDoActionsAtOrBefore(value2));

    scratch = 0;
    q.run(time2);
    assertEquals(value2, scratch, .1e-6);
  }
}

Simulation: Random numbers [9/13]

To get predictable numbers, use Random(long seed). If you use the seed every time, you get the same series of random numbers.

java.util.Random

file:random/Util.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package random;
import java.util.Random;

public class Util {
  private Util() {}
  static private Random RANDOM = new Random();

  /** doubles that differ by less than EPSILON should be considered equals */
  static public final double EPSILON = 1e-9;
  static public boolean isEquals(double x, double y) {
    return Math.abs(x-y) <= EPSILON;
  }
  static public boolean isLessOrEquals(double x, double y) {
    return (x-y) <= EPSILON;
  }
  static public boolean isLess(double x, double y) {
    return (x-y) < -EPSILON;
  }

  static public void setRandomSeed(long seed) {
    RANDOM.setSeed(seed);
  }
  static public double nextRandom(double min, double max) {
    if (Util.isLess(max,min))
      throw new IllegalArgumentException(max + " is smaller than " + min);
    return min + ((RANDOM.nextDouble()) * (max - min));
  }
}

file:random/UtilTEST.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package random;

import static org.junit.Assert.*;
import org.junit.Test;

public class UtilTEST {

  @Test
  public void testEquals() {
    assertTrue (Util.isEquals(0.3, 0.3+0.5*Util.EPSILON));
    assertFalse(Util.isEquals(0.3, 0.3+2.0*Util.EPSILON));
    assertFalse(Util.isLess(0.3, 0.3+0.5*Util.EPSILON));
    assertTrue (Util.isLess(0.3, 0.3+2.0*Util.EPSILON));
    assertTrue (Util.isLessOrEquals(0.3, 0.3+0.5*Util.EPSILON));
    assertTrue (Util.isLessOrEquals(0.3, 0.3+2.0*Util.EPSILON));

    assertTrue (Util.isEquals(0.3+0.5*Util.EPSILON, 0.3));
    assertFalse(Util.isEquals(0.3+2.0*Util.EPSILON, 0.3));
    assertFalse(Util.isLess(0.3+0.5*Util.EPSILON, 0.3));
    assertFalse(Util.isLess(0.3+2.0*Util.EPSILON, 0.3));
    assertTrue (Util.isLessOrEquals(0.3+0.5*Util.EPSILON, 0.3));
    assertFalse(Util.isLessOrEquals(0.3+2.0*Util.EPSILON, 0.3));
  }
  @Test
  public void testRandom() {
    for (int i=0; i<100; i++) {
      double x=Util.nextRandom(i,i*i);
      assertTrue (Util.isLessOrEquals(i,x));
      assertTrue (Util.isLessOrEquals(x,i*i));
    }
  }
}

Project: Car Movement [10/13]

How do cars move?

Here is a sketch of one solution to the problem of car movement.

interface CarAcceptor {
  public boolean accept(Car c, float frontPosition);
}
class Road implements CarAcceptor {
  Set cars;
  float endPosition;
  CarAcceptor nextRoad;
  public boolean accept(Car c, float frontPosition) {
    cars.remove(c);
    if(frontPosition>endPosition) {
      return nextRoad.accept(c,frontPosition-endPosition)
    } else {
      c.setCurrentRoad(this);
      c.setFrontPosition(frontPosition);
      cars.add(c);
      return true;
    }
  }
}

interface Agent {
  public void run ();
}
class Car implents Agent {
  private int sleepSeconds;
  private float frontPosition;
  private Road currentRoad;
  private TimeServer agents;
  public void run() {
    // calculate newFrontPosition
    if (currentRoad.accept(this, newFrontPosition))
       agents.add(this, Agents.currentTime+sleepSeconds);
  }
  void setCurrentRoad(...) ... // for Road
  void setFrontPosition(...) ... // for Road
}

Here is a sketch of how to compute the distance to the closest obstacle. A simple example:

r1 feeds into r2. Both are 100m long. c1 and c2 have frontPosition at 70m and 20m on the repspective roads. Both are 10m long. So distance from c1 to obstacle should be 40m.

c1 ---distanceToObstacle(70)---> r1
                                 r1 ---distanceToObstacle(-30)--> r2
                                                                  r2 ---backPosition()--> c2
                                                                  r2 < - - - - - - 10 - - c2
                                 r1 < - - - - - - - - - - - 40 -  r2
c1 < - - - - - - - - - - 40 - -  r1

The following code is not debugged, but that is what is intended to do:

interface CarAcceptor { ...
  public double distanceToObstacle(double fromPosition);
}
class Sink implements CarAcceptor {
  public double distanceToObstacle(double fromPosition) {
    return Double.POSITIVE_INFINITY;
  }
}
class Road implements CarAcceptor {
  Set cars;
  CarAcceptor nextRoad;
  double endPosition;
  private double distanceToCarBack(double fromPosition) {
    double carBackPosition = Double.POSITIVE_INFINITY;
    for (Car c : cars)
      if (c.backPosition() >= fromPosition &&
          c.backPosition() < carBackPosition)
         carBackPosition = c.backPosition();
    return carBackPosition;
  }
  public double distanceToObstacle(double fromPosition) {
    double obstaclePosition = this.distanceToCarBack(fromPosition);
    if (obstaclePosition == Double.POSITIVE_INFINITY) {
      double distanceToEnd = fromPosition-this.endPosition;
      obstaclePosition 
        = nextRoad.distanceToObstacle(fromPosition-this.endPosition);
    return obstaclePosition-fromPosition;
  }
}
class Car implements Agent {
  private double length;
  private double frontPosition;
  private double velocity;
  private Road currentRoad;
  public void run() {
    // find closest obstacle
    // calculate newVelocity
    // calculate newFrontPosition
  }
  double backPosition() {
    return frontPosition-length;
  }
}

Project: Lights [11/13]

Now, how do you add lights to this?

Think first about a stoplight that sits just between two road segments (no intersection).

One idea:

class Light implements CarAcceptor {
  {GREEN,RED} state;
  CarAcceptor nextRoad;
  public double distanceToObstacle(double fromPosition) {
    if state==GREEN
      return nextRoad.distanceToObstacle(fromPosition);
    else
      return 0;
  }
  void setState(...) // set the state
}

Then set up the objects as follows:

CarGenerator -> Road1 -> Light -> Road2 -> Sink

How do you coordinate two lights then?

One idea:

class TwoWayLightController implements Agent {
   Light[] lights;
   public void run() {
     // change the state of lights...
   }
}

Project: Creating the road graph [12/13]

The instructions call for an object graph like this:

          30     40
          |      |
          31     41
          |      |
  10--11--A--13--B--15--16
          |      |
          33     43
          |      |
  20--21--C--23--D--25--26
          |      |
          35     45
          |      |
          36     46

Here traffic goes left to right and top to bottom.

The object graph you build will look like this:

CarGen10 -> Road11 -> Light12 -> Road13 -> Light14 -> Road15 -> Sink16

CarGen20 -> Road21 -> Light22 -> Road23 -> Light24 -> Road25 -> Sink26

CarGen30 -> Road31 -> Light32 -> Road33 -> Light34 -> Road35 -> Sink36

CarGen40 -> Road41 -> Light42 -> Road43 -> Light44 -> Road45 -> Sink46

      Light12 <- LightControllerA -> Light32

      Light12 <- LightControllerB -> Light42

      Light22 <- LightControllerC -> Light35

      Light22 <- LightControllerD -> Light45

How do you put all this together?

Details will vary from person to person,
so you have to be able to think abstractly and adapt from someone
else's comments to see if anything applies to your own code.  

Suppose we have just two roads and no lights, then the object graph is
likely to look something like:

 r1 --> r3

that is, road 1 has a link to road 2.  In the code this will be a
field, perhaps called "next".  In r3, the next field will be null.
You can create this graph by doing something like this:

 Road r3 = new Road(null);
 Road r1 = new Road(r3);

where the code looks like:

 interface CarAcceptor { ... }
 class Road implements CarAcceptor { CarAcceptor next; ... }

Note that you create the segments "backwards".  Each road needs to
know about the road after it, so you create them in reverse order.

If we use a null object for the sink we get:

 r1 --> r3 --> k4

which you might create like this:

 Sink k4 = new Sink()
 Road r3 = new Road(k4)
 Road r1 = new Road(r3)

Finally, you might add a car generator, or Source:

 s0 --> r1 --> r3 --> k4

 Sink k4 = new Sink()
 Road r3 = new Road(k4)
 Road r1 = new Road(r3)
 Source s0 = new Source(r1)

You expect the code to be something like:

 interface CarAcceptor { ... }
 class Sink implements CarAcceptor { ... }
 class Road implements CarAcceptor { CarAcceptor next; ... }

 interface Agent { ... }
 class Source implements Agent { CarAcceptor first; ... }

If you add a light as I discussed in class, you might have:

 s0 --> r1 --> l2 --> r3 --> k4

 Sink k4 = new Sink()
 Road r3 = new Road(k4)
 Light l2 = new Light(r3)
 LightController c2 = new LightController(l2)
 Road r1 = new Road(r3)
 Source s0 = new Source(r1)

with code along the lines of:

 interface CarAcceptor { ... }
 class Sink implements CarAcceptor { ... }
 class Road implements CarAcceptor { CarAcceptor next; ... }
 class Light implements CarAcceptor { CarAcceptor next; ... }

 interface Agent { ... }
 class Source implements Agent { CarAcceptor first; ... }
 class LightController implements Agent { Light theLight; ... }

Having a LightController hooked up to two lights is an exercise, for
once you get this working.

Here is an example of code I put out last year.

In main.Main you are going to need to do all the wiring. Something like this should work (not debugged!).

CarGen makeSegment(LightController[] lc, Direction d) {
  CarAcceptor next = new Road(new Sink());
  for (int i = 0; i<lc.size; i++) {
     Light l = new Light(next);
     lc.setLight(l,d);
     next = new Road(l);
  }
  return new CarGen(next);
}
// rotate a 2D array
LightController[][] rotate (LightController[][] orig) {
  LightController[][] value = new LightController[orig[0].size][orig.size];
  for (i...)
    for (j...)
      value[i][j] = orig[j][i];
}
void makeSquareGrid(int size) {
  LightController[][] eastWest = new LightController[size][size];
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      eastWest[i][j] = new LightController();
      TimeServer.instance.add(eastWest[i][j]);
    }
  }
  LightController[][] northSouth = rotate(eastWest);
  for (int i = 0; i < size; i++) {
    TimeServer.instance.add(makeSegment(eastWest[i], Direction.EASTWEST));
    TimeServer.instance.add(makeSegment(northSouth[i], Direction.NORTHSOUTH));
  }
}

Project: Notes [13/13]

A ConcurrentModificationException happens when you modify a collection
while iterating through it.  For example:

for (Agent a : Model.agents) {
  GrimReaper.delete(c)
}

GrimReaper {
  delete(Agent a) { Model.agents.remove(a);
}

This will cause a problem, since the grim reaper modifies the
collection that is being iterated through.  You solve the problem by
iterating through a copy:

for (Agent a : Model.agents.copy()) {
  GrimReaper.delete(c)
}

Now the copy is being iterated through, not the original, so no problems.  

-----------------------------------------------------------------------

If I follow the lecture correctly, it seems we only need to modify
SwingAnimationPainterBuilder.java, is that correct?  I know we need to
use the builder to add model components to the model, but is there
other visualization code that we need to touch?

-----------------------------------------------------------------------

I had to edit a lot of things in the animation classes to get  
everything playing nice with the graphics.  The given graphics library  
does not take care of the following:

- Changing of colors (traffic lights)
- Proportionate lengths of roads and intersecitons (i.e., a road may  
look the same size but it's actually longer than the next)
- Drawing moving dots (cars) on the intersections

So I assumed that it was up to us to fix these issues.  I went ahead  
and added the above features as necessary.  The colors of the lights  
can be done through the same sate pattern that controls the traffic.

The lengths of roads can be taken care of by using an equation that  
"normalizes" position of cars so that no matter what the visual is  
drawn up to be the position is normalized to a 0 to 1 double where 0  
is the beginning of the segment or intersection (or whatever the next  
extension you decide to draw) and 1 is the end.

I also had to add builder functions to let the animation know about  
intersections since the cars were disappearing at each intersection.  
It took me a while to figure out that they were still being processed  
but not being drawn.  When the visual of the car goes away it's really  
confusing because it looks like it teleported even though it was still  
moving all along.

Another tip: increase the size of the traffic light dots so they are  
bigger than cars.  This way if there is a lot of gridlock action, you  
can still see the state of each light.  I've got a screenshot here.

-----------------------------------------------------------------------
Can you explain this a bit further?

"The lengths of roads can be taken care of by using an equation that
"normalizes" position of cars so that no matter what the visual is
drawn up to be the position is normalized to a 0 to 1 double where 0
is the beginning of the segment or intersection (or whatever the
next
extension you decide to draw) and 1 is the end."

I think maybe this is my problem with my cars being drawn stopped in
the middle of the next road when they are supposed to be stopped at
the intersection when the light is red.

Are you saying to do something like this...

double roadLength = e.x.getLength();
double normalizedPosition = pos/roadLength;
XGraphics.fillOval(g, e.t, normalizedPosition, 0, MP.dotLength,
VP.elementWidth);

When doing it that way my cars no longer go past a blocked
intersection, but they stay at the start of the line, instead of going
up to the intersection.  Hmmmm.

-----------------------------------------------------------------------

You are REAL close.  Now all you have to do is take care of the offset  
that the dot imposes.  The graphics engine draws the center of the dot  
at "position".  I think this will get you moving in the right  
direction.  Are you using the "frontPosition"?

Also, I just put the formula in the argument for the fillOval  
function.  Then you don't really need to create all the extra  
doubles.  To do this I also added a method to Car called  
GetRoadObjectLength() which returns a double that is the length of the  
road object that the car is currently on.

Oh! and I forgot one more thing.  You now have a position from 0 to  
1.  That wouldn't show much movement for you now would it?  That must  
be why your cars are staying at the front of the road.  Actually if  
you were to look REAL close you would see the car move 1 meter on a  
200 meter road!  You forgot to multiply the "normalized" distance with  
the graphical length of the road, MP.lineLength.

What's real cool about this equation? Go ahead and change the  
MP.lineLength value.  Make it 300 if you like and watch as the  
equation takes care of all your problems!

Revised: 2008/10/28 10:45