Assignment 9, due Mar 31

On every assignment, write your name and section number. Write your name as it appears on your university ID card! Use the section number as it appears in your current registration! We will not do detective work to figure out who did what. Homework is due on paper at the start of your discussion section. Exceptions will be made only by advance arrangement with your TA (excepting "acts of God"). Never push homework under someone's door!

1. Background: In the code distributed on March 22, in class Intersection, two new "getter" methods have been added, outgoingSize() and outgoingGet(). There is also a public 'setter' method, addOutgoing(). These three methods operate on the final private list outgoing.

   a) This means that we have public 'setter' and 'getter' methods to operate on outgoing. That suggests that outgoing might as well be public. Give examples of operations on outgoing that are forbidden to the public as a result of forcing the public to use these methods. (0.5 points)

   We can only append new items to outgoing, so we cannot do any of the following operations, among many others: addFirst(), clear(), poll(), remove(), and set().

   b) But the list outgoing is already declared as final. This would seem to imply that outgoing is read-only. Give an example of an operation on outgoing that is forbidden by declaring it to be final, and give some examples of operations that change outgoing that are still permitted despite its being final. (0.5 points)

   Declaring it to be final makes it illegal to assign a new value. That is, we cannot write outgoing=x. We can, however, change the contents of the list, for example, using our setter method addOutgoing() which calls outgoing.add().

2. Background: Consider the following code to simulate the arrival of a vehicle at the entrance to a road:

   public void arrivalEvent( float time, Vehicle v ) {
           Simulation.schedule(
                   time + travelTime,
                   (float t)->this.departureEvent( t, v )
           );
   }
   

   A problem: Rewrite the above code so that it does not use a lambda expression. This will require defining an inner class that implements Simulation.Action and then passing an instance of that class. Do it with an explicitly named inner class. (0.5 points)

   public void arrivalEvent( float time, Vehicle v ) {
   	class A implements Simulation.Action {
   		void trigger( float t ) {
                   	departureEvent( t, v );
   		}
   	}
           Simulation.schedule( time + travelTime, new A() );
   }
   

   Alternatively, we could use an anonymous inner class:

   public void arrivalEvent( float time, Vehicle v ) {
           Simulation.schedule(
   		time + travelTime,
   		new Simulation.Action {
   			void trigger( float t ) {
   				departureEvent( t, v );
   			}
   		}
   	);
   }
   

3. Background: Consider the following alternative pieces of code for simulating the departure of a vehicle at the exit from a road. They both work.

   // version a
   public void departureEvent( float time, Vehicle v ) {
           Simulation.schedule(
                   time,
                   (float t)->destination.arrivalEvent( t, v )
           );
   }
   
   // version b
   public void departureEvent( float time, Vehicle v ) {
           destination.arrivalEvent( time, v )
   }
   

   a) Which solution will lead to more efficient code and why? (0.5 points)

   Version b simply calls destination.arrivalEvent() instead of scheduling it to happen now, that is, immediately after the return from the departureEvent().

   Note that these are equivalent because there is no code in departureEvent() between the time it schedules destination.arrivalEvent() and the time it returns. Had there been code there, it would have been harder to prove the equivalence of these two versions because we would have had to prove that none of that code interacted in any way with the code in destination.arrivalEvent().

   b) Consider the following actions during the execution of this code:

   1. entry to the intersection's arrival event service routine
   2. exit from the interesection's arrival event service routine
   3. entry to the road's departure event service routine
   4. exit from the road's departure event service routine

   Give the order of these actions as they occur with version a and with version b. (0.5 points)

   In version a: 3 4 1 2

   In version b: 3 1 2 4

4. Background: One of the most interesting problems with simulation is that sometimes, you schedule an event only to find that it shouldn't happen. This can occur in logic simulators when two input changes arrive in quick succession at a gate (perhaps on different inputs). When this happens with real hardware, the gate acts as a low pass filter, and any output change resulting from the first input change is never seen on the output. One way to simulate this would be to delete any pending output change event on a gate when a new output change is scheduled. This would require significant changes to our simulation framework.

   An alternative is to add a new field to each gate that indicates that is incremented every time an output change event is scheduled and decremented when that event occurs. Only when the output change event decrements the counter to zero does the event service routine actually change the output.

   A Question: What is the minimum time interval between successive output changes, as a function of gate characteristics defined by the input to the logic simulator. (0.5 points)

   The interval is the same as the gate delay.