14. Events, Continued
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
In the last lecture, we left some items hanging. For example, we had the following code for entering an intersection:
// simulation methods for uncontrolled Intersection
public void enter( Vehicle v, float t ){
/** Simulate v entering this intersection at time t.
*/
if (occupied) {
// Bug: queue vehicle v on queue
} else {
...
We need to make queues. We could, of course, invent a queue mechanism from scratch, but the Java library includes a perfectly good solution to this problem in the class LinkedList. Looking in the official definition of the class, we find that if l is a linked list of some class of objects, l.addLast() will append an item to the end of the list, and l.removeFirst() will get and remove the first item from the list.
In effect, l.addLast() can be used to enqueue an item on the queue represented by the list, and In effect, l.removeFirst() can be used to dequeue an item from the queue represented by the list. We should substitute these everywhere that an enqueue and dequeue operation is required, and of course, we should declare each queue to be an object of class linkedList.
Note that these methods on a linked list are actually inhereted from the interface specification Deque pronounced deck. This specification is for a double-ended queue, and there are several other implementations. Two of them ConcurrentLinkedDequeue and ConcurrentBlockingDequeue have extensions that permit their use in multithreaded environments. The third additional implementation, the ArrayDequeue is may make more efficient use of memory, but it had difficulty dealing with queues with unpredictable and widely varying capacity because the entire queue needs to be rebuilt whenever the queue size exceeds the size of the array allocated to store it.
And, of course, the isEmpty() method applies, so the test for an empty queue is the same as the test for an empty string or any other collection.
public void exit( Vehicle v, float t ){
/** Simulate v entering this intersection at time t.
*/
if ( /* Bug: queue empty */ ) {
occupied = false;
} else {
// Bug: Vehicle v = dequeue from queue
Road d = v.pickRoad( outgoing );
// Bug: schedule d.enter( v, t + travelTime )
}
}
Like the enter method, the exit method offers two different behaviors, but in this case, the difference depends on whether or not other vehicles are awaiting entry to the intersection. If none are waiting, we simply reset the occupied flag. If some are waiting, we grab a waiting vehicle and let it through.
On questioning the class, it appears that an insufficient number of students are comfortable with the difference between the two principal implementations of lists and queues, the linked list and the array implementations. Here, we'll look briefly at this from the perspective of queues and then (very briefly) DEqueues (double-ended queues).
A FIFO (first-in first-out) queue can be implemented in two classic ways. We could use an array of elements in the queue, roughly as follows:
class ArrayQueue {
private Element array[capacity];
private int head = 0;
private int tail = 0;
public boolean empty() {
return head==tail;
}
public void enqueue( Element e ) {
array[tail] = e;
tail = (tail + 1) % capacity;
}
public Element dequeue() {
int h = head;
head = (head + 1) % capacity;
return array[h];
}
}
For the array implementaiton, the capacity is a strict upper bound on the number of items that may be enqueued. Java's default ArrayList avoids this limitation by the simple expedient of detecting a full array and replacing it with an array twice the size if it happens to fill. For reasons that are a bit strange, the designers of Java seem to have decided on an initial capacity of eleven items, although if you know the upper bound on your ArrayList object, you can specify a larger initial size.
The other common implementation of queues rests on a linked list. Here is the corresponding minimal code for that:
class ListQueue {
private class Node {
Node next = null;
Element e = null;
}
private Node head = null;
private Node tail = 0;
public boolean empty() {
return head==null;
}
public void enqueue( Element e ) {
Node n = new Node();
n.e = e;
n.next = tail;
tail = n;
if (head==null) head = n; // special case if list was empty
}
public Element dequeue() {
Node n = head;
head = n.next;
if (head==null) tail = null; // special case if list now empty
return n.e;
}
}
In general, if the list size stays relatively static, the array implementation will perform significantly better, but resizing the array that underlies an array queue is an expensive operation because it involves allocating a new array and then copying all the contents of the old array to a new one.
In general, if the list size varies eratically, the linked list is the better choice, even though it has the overhead of allocating a new list node for each enqueue.
The overhead of memory management depends on how well the memory manager can predict the sizes of the objects being allocated. Memory managers that are built to support languages like Java are very good at managing large numbers of small identical objects such as queue nodes, where the sizes of recently discarded objects predict the sizes of the objects likely to be used in the near future. Memory managers are generally significantly worse at dealing with variable-sized objects where the sizes of recently used objects do not predict the sizes of the objects likely to be needed in the near future.
Of course, double-ended queues, where items can be enqueued and dequeued at both ends of the queue are more difficult. In this case, the linked-list implementation needs to be doubly-linked so that each item in the queue points not only to its successor but to its predecessor. The LinkedList class in Java must use a doubly-linked list because this is also required in order to permit low-overhead deletion of an element from the middle of the queue.
In our code for parsing the description of a road network, we included several calls of the form:
SyntaxCheck.lineEnd(
sc,
"Road '" + srcName + "' '" + dstName + "'"
);
Each call to lineEnd() checks to see that the remainder of the input line is blank, and if it is not, it generates an error message that incorporates the second argument, a string. That is to say, in most cases, the value of the second argument is never used.
To call lineEnd() as it is called above poses a real performance penalty because the concatenation of the 5 strings making up the argument is computationally expensive. To evaluate the expression
"Road '" + srcName + "' '" + dstName + "'"
String s = new String();
s.concat( "Road '" );
s.concat( srcName );
s.concat( "' '" );
s.concat( dstName );
s.concat( "'" );
SyntaxCheck.lineEnd( sc, s );
The point of this is: The + (concatenation) operator, when applied to strings, is quite expensive. It requires creating a new object (not cheap) to hold the new string resulting from that concatenation, and then copying each of the arguments to the end of that new string.
What we need to do here is change the SyntaxCheck() method so that the second parameter is not a string, but a function that can be evaluated to give a string when it is needed.
This is an old idea. In the Algol 60 programming language, defined in 1960, all parameter passing was done this way. If you called f(i+1), the actual parameter was a function of no arguments, and in the body of f(), any use of the parameter was automatically replaced by a call to the function. This was called call by name parameter passing.
In C, parameters are passed by value, that is to call f(i+1), you first evaluate i+1 and then call f() passing that value. In the simple case of f(1), you pass a copy of the value. Because of this, inside the called routine, any changes made to the parameter do not have a lasting impact after the return. Java uses call by value parameter passing for built-in types that have lower-case names: int and float, for example.
The third common kind of parameter passing is conventionally called call by reference. When a parameter is passed by reference, you pass a pointer to that parameter, so that no copy is made. When you pass a paremeter by reference, changes made to the parameter inside the called routine have a lasting effect and are visible in the outside world after the routine returns. In java, when you pass a parameter of a user defined class (or a built-in class like String that has an upper-case name), the object is passed by reference, however, if there is an expression involved, the expression is evaluated first and then the object that is the result of that expression is passed by reference.
So the question is, does Java have a mechanism supporting call by name parameter passing?
We can fake it up using some very long winded code. First, we create an interface:
interface ByName {
/** Framework to fake up Call by Name parameter passing.
*/
String s();
/** object of class ByName can return a string.
*/
}
Then, we rewrite our code for lineEnd() so that it takes an object of this new ByName class where it would have taken a string, and so that it calls the s() method of that object were it would have simply used the string:
class SyntaxCheck {
static void lineEnd( Scanner sc, ByName c ) {
...
if ( ... ) {
Errors.fatal( c.s() + " has non-empty ...
}
}
}
Now, where we would have written this simple little bit of code:
SyntaxCheck.lineEnd( sc, "Intersection '" + name + "'" );
We use this verbose bit of code:
class MyString implements ByName { // example of an inner class
public String s() {
return "Intersection '" + name + "'";
}
}
MyString msg = new MyString();
SyntaxCheck.lineEnd( sc, msg );
Amazingly enough, this works just fine! Class MyString is an inner class, defined only inside the block of code where this call is made. The code within MyString.s() has access to all the local variables of the current block as well as everything defined in the current class, so calling msg.s() can do the required concatenation. The cost of this is not trivial -- not only is there a fair bit of code, but you are forced to allocate a bogus object, msg.
Had we been dealing with a more complex computation, the overhead of this trick would be insignificant, but as it is, the payback is minimal. Nonetheless, it is useful to understand this trick because in more complex programming contexts, tricks like this have very significant value.
And, the verbose excess of writing the code this way, with the need to name the "throw away" class MyString and the object msg has led the designers of Java to provide a more compact syntax.
A complete executable java program containing all the code we have discussed to date for the road network example is given on line here.