Paper 2004
Object Oriented Programming

Question 3

(a)

The Iterator pattern allows the client to control the traversal of a sequence of values.

A typical usage might be:

while(seq.hasCurrent())
{
	System.out.println(s.current());
	s.next();
}

It contrasts with things like hard-coding a traversal internally or the Visitor pattern.
The latter isn't too bad, but gives us all-or-nothing control of the traveral (unless we
use exceptions, of course).

(b)

class ArraySeq implements Seq
{
	private int cur = 0;
	private Object[] array;

	public ArraySeq(Object[] array) { this.array = array; }
	public boolean hasCurrent() { return cur < array.length; }
	public Object current() { if(hasCurrent()) return array[cur]; else throw new Error(); }
	public void next() { if(hasCurrent()) ++cur; else throw new Error(); }
}

(c)

class CatenateSeq implements Seq
{
	private Seq s1, s2;

	public CatenateSeq(Seq s1, Seq s2) { this.s1 = s1; this.s2 = s2; }
	public boolean hasCurrent() { return s1.hasCurrent() || s2.hasCurrent(); }
	public Object current() { if(s1.hasCurrent()) return s1.current(); else return s2.current(); }
	public void next() { if(s1.hasCurrent()) s1.next(); else s2.next(); }
}

(d)

class FilterSeq implements Seq
{
	private boolean currentOk = false;
	private Filter f;
	private Seq s;

	public FilterSeq(Filter f, Seq s) { this.f = f; this.s = s; }

	public boolean hasCurrent()
	{
		if(currentOk) return true;	// prevents rechecking f.pass on the current element
						// note that f.pass may modify f, so f.pass might not return the same thing
						// twice in a row! the current element is still ok if it was before, though

		while(s.hasCurrent())
		{
			if(f.pass(s.current())) { currentOk = true; return true; }
			else s.next();
		}
		return false;
	}

	public Object current()
	{
		if(hasCurrent()) return s.current();
		else throw new Error();
	}

	public void next()
	{
		s.next();
		currentOk = false;
	}
}

(e)

import java.util.*;

class Unique implements Seq
{
	private FilterSeq fs;

	public Unique(final Seq s)
	{
		final Filter f = new Filter()
		{
			private Set<Object> seen = new HashSet<Object>();

			public boolean pass(Object o)
			{
				if(seen.contains(o)) return false;

				seen.add(o);
				return true;
			}
		};

		fs = new FilterSeq(f, s);
	}

	public boolean hasCurrent() { return fs.hasCurrent(); }
	public Object current() { return fs.current(); }
	public void next() { fs.next(); }
}

(f)

i)

import java.util.*;

class BreadthFirst implements Seq
{
	private LinkedList<Node> queue = new LinkedList<Node>();

	public BreadthFirst(Node startNode) { queue.add(startNode); }

	public boolean hasCurrent() { return !queue.isEmpty(); }

	public Object current()
	{
		return queue.getFirst();
	}

	public void next()
	{
		Node head = queue.removeFirst();
		for(String a: head.arcs()) queue.add(head.nextNode(a));
	}
}

ii)

Seq s = new Unique(new BreadthFirst(startNode));
while(s.hasCurrent()) { System.out.println(s.current()); s.next(); }

It would fail if the graph were cyclic, because we'd go back to nodes we'd already visited
and the queue would never empty. Example:

A <---> B

Queue: A
next()
Queue: B
next()
Queue: A
etc.

Question 5

(a)

Model-View: Separate the representation of the model from how it is rendered. That way, we can have more than one view of it,
each of which may be different.

Model-View-Controller: The Controller allows the model to be changed. One way it can be implemented is as a subclass of a view.

Listener interfaces are used to allow a Model to notify its Views when it has changed without being aware that what it's
notifying are Views. Or to put it another way, listeners break the dependency of Model on View. Without them, there would
be a cyclic dependency, which would defeat the whole object of the pattern.

(b)

i)

class View extends Visible implements ModelListener
{
	final protected int SQUARE_SIZE = 32;

	protected Model model;

	public View(Model model) { this.model = model; }

	public void draw(Screen s)
	{
		for(int i=0; i<10; ++i)
		{
			for(int j=0; j<10; ++j)
			{
				s.fillSquare(j*SQUARE_SIZE, i*SQUARE_SIZE, SQUARE_SIZE);

				Model.Contents c = model.get_square(i,j);
				if(c != Model.Contents.EMPTY)
				{
					s.fillCircle(c == RED, j*SQUARE_SIZE, i*SQUARE_SIZE, SQUARE_SIZE);
				}
			}
		}
	}

	public void model_changed() { redraw(); }
}

ii)

interface ModelListener
{
	void model_changed();
}

class Model
{
	public enum Contents
	{
		EMPTY, BLUE, RED
	}

	private Contents[][] squares = new Contents[10][10];
	private ModelListener listener = null;

	private boolean legal_move(int i1, int j1, int i2, int j2)
	{
		if(squares[i1][j1] == EMPTY) return false;
		if(squares[i2][j2] != EMPTY) return false;

		if(Math.abs(i2-i1) <= 1 && Math.abs(j2-j1) <= 1) return true;	// move to an adjacent square

		if((Math.abs(i2-i1) == 2 && (Math.abs(j2-j1) == 0 || Math.abs(j2-j1) == 2)) ||
		   (Math.abs(j2-j1) == 2 && (Math.abs(i2-i1) == 0 || Math.abs(i2-i1) == 2)))
		{
			int mi = (i1+i2)/2, mj = (j1+j2)/2;
			if(squares[mi][mj] != EMPTY) return true;		// jump over a piece
		}

		return false;
	}

	public Model
	{
		for(int i=0; i<10; ++i)
			for(int j=0; j<10; ++j)
				if(i+j <= 4) squares[i][j] = RED;
				else if(i+j >= 14) squares[i][j] = BLUE;
				else squares[i][j] = EMPTY;
	}

	public void add_model_listener(ModelListener listener) { this.listener = listener; }
	public Contents get_square(int i, int j) { return squares[i][j]; }

	public make_move(int i1, int j1, int i2, int j2)
	{
		// Move piece from (i1,j1) to (i2,j2) if it's a legal move

		if(legal_move(i1, j1, i2, j2))
		{
			squares[i2][j2] = squares[i1][j1];
			squares[i1][j1] = EMPTY;
			if(listener != null) listener.model_changed();
		}
	}
}

...

Model model = new Model();
View view = new View(model);
model.add_model_listener(view);

(c)

Clicking on a piece selects it. Clicking on an empty square with a piece selected moves it there. Clicking
on an empty square without a piece selected does nothing. Clicking on another piece with a piece selected
selects that instead.

class Controller extends View
{
	// Datatype invariant: selI == -1 -> selJ == -1
	private int selI = -1, selJ = -1;

	public void mousePress(int x, int y)
	{
		int i = x/SQUARE_SIZE, j = y/SQUARE_SIZE;

		if(i < 0 || i > 9) return;
		if(j < 0 || j > 9) return;

		Model.Contents c = model.get_square(i,j);

		if(c != Model.Contents.EMPTY)
		{
			selI = i;
			selJ = j;
		}
		else if(selI != -1)
		{
			model.make_move(selI, selJ, i, j);
			selI = -1;
			selJ = -1;
		}
	}
}

(d)

If we already have a listener, we make a composite containing it and the new listener.

class Model
{
	public void add_model_listener(ModelListener listener)
	{
		if(this.listener != null) listener = new ModelListenerComposite(this.listener, listener);
	}
}

Composite listeners simply forward model_changed() events to their component listeners.

class ModelListenerComposite implements ModelListener
{
	private ModelListener a, b;

	public ModelListenerComposite(ModelListener a, ModelListener b) { this.a = a; this.b = b; }

	public void model_changed() { a.model_changed(); b.model_changed(); }
}

Question 6

(a)

o1 == o2 checks whether o1 and o2 are identical (i.e. the same object)
o1.equals(o2) checks whether o1 and o2 are equivalent

(Note that if o1 and o2 were built-in types rather than reference types, i.e. both had type int,
 for example, then comparing them with o1 == o2 would be the way forward, since o1.equals(o2)
 would be a syntax error...)

In terms of language mechanics, == is an operator and part of the language, whereas equals is
a method inherited from Object. The default implementation of equals in Object does the same
as ==, but we can override it in subclasses.

Example showing the distinction:

String s1 = "Blah";
String s2 = s1;
String s3 = "Blah";

System.out.println(s1 == s2 ? "Equal" : "Not Equal");		// outputs "Equal"
System.out.println(s1 == s3 ? "Equal" : "Not Equal");		// outputs "Not Equal"
System.out.println(s1.equals(s2) ? "Equal" : "Not Equal");	// outputs "Equal"
System.out.println(s1.equals(s3) ? "Equal" : "Not Equal");	// outputs "Equal"

(b)

i)

class SetImp implements Set
{
	final private Object[] elts;

	private SetImp(final Object[] oldElts, final Object x)
	{
		int len = oldElts.length;
		elts = new Object[len+1];
		for(int i=0; i<len; ++i) elts[i] = oldElts[i];
		elts[len] = x;
	}

	public SetImp()
	{
		elts = new Object[] {};
	}

	public Set add(Object x)
	{
		if(!member(x)) return new SetImp(elts, x); else return this;
	}

	public Iterator elements()
	{
		return new Iterator()
		{
			private int cur = 0;

			public boolean hasNext()
			{
				return cur < elts.length;
			}

			public Object next()
			{
				return elts[cur++];
			}
		};
	}

	public boolean member(Object x)
	{
		int len = elts.length;
		for(int i=0; i<len; ++i)
		{
			if(elts[i].equals(x)) return true;
		}
		return false;
	}
}

ii)

A)

class IntSet
{
	private Set internal = new SetImp();

	public boolean member(int x)
	{
		return internal.member(x);
	}

	public void add(int x)
	{
		internal = internal.add(x);
	}

	public Iterator elements()
	{
		return internal.elements();
	}

	public boolean equals(Object other)
	{
		IntSet otherSet = (IntSet)other;

		Iterator elts = elements();
		while(elts.hasNext())
		{
			int x = (Integer)elts.next();
			if(!otherSet.member(x)) return false;
		}

		Iterator otherElts = otherSet.elements();
		while(otherElts.hasNext())
		{
			int x = (Integer)otherElts.next();
			if(!member(x)) return false;
		}

		return true;
	}
}

B)

class IntSetSet
{
	private Set internal = new SetImp();

	public boolean member(IntSet x)
	{
		return internal.member(x);
	}

	public Iterator elements()
	{
		return internal.elements();
	}

	public void add(IntSet x)
	{
		internal = internal.add(x);
	}
}

C)

One element.

{{1,2},{2,1}} = {{1,2}}, which is a set with one element.

(Note: Actually, no elements are delivered by it, as it doesn't compile. IntSetSet's add method
returns void. Furthermore, IntSetSet doesn't have to have an elements method, as it's not really
implementing Set (its member and add methods have different signatures)).

(c)

It shouldn't have allowed us to add CoolingOutletTemp, as it's not a sensor. The consequence of
this is that the program will crash horribly when we call sensor.isSafe() on the non-sensor. In
particular, it will say something like "can't find isSafe() in class Integer".

Problems like this could be avoided with Generic Java because we can then say what we mean,
namely that the Set contains Sensors, rather than Objects. Then we'll get a compile-time error
when we try and add an Integer to a Sensor set.

interface Set<T>
{
	Set<T> add(T x);
	Iterator<T> elements();
	boolean member(T x);
}

interface Iterator<T>
{
	boolean hasNext();
	T next();
}

public class MainSensorVoter
{

...

Sensor MainReactorTempSensor = ...
int CoolingOutletTemp = 123;	// note: we can take advantage of auto-boxing etc. when this is used
Sensor CoolingOutletTempSensor = ...
Sensor CoolingInletTempSensor = ...

...

Set<Sensor> criticalSensors = new SetImp<Sensor>();

public boolean isSafe()
{
	...
	Iterator<Sensor> sensors = ...
	while(...)
	{
		...
		if(sensors.next().isSafe()) ++safeCount;
	}
	...
}

public void init()
{
	criticalSensors = new SetImp<Sensor>();
	criticalSensors = criticalSensors.add(MainReactorTempSensor);	// as before
	criticialSensors = criticalSensors.add(CoolingOutletTemp);	// compile-time error
	...
}

}