Paper 2003 Object Oriented Programming Question 1 (a) public interface File { /** Creates a file in this directory. @param name The name of the file to (if possible) create @return The created file @throw Error If this isn't a directory or a file with that name exists */ File createFile(String name); /** Creates a subdirectory in this directory. @param name The name of the subdirectory to (if possible) create @return The created subdirectory @throw Error If this isn't a directory or a file with that name exists */ File createSubdirectory(String name); /** Returns a handle to a file in the current directory. @param name The name of the file to get @return The file in question or null, if it doesn't exist @throw Error If this isn't a directory */ File getChild(String name); /** Returns an array of the files in the current directory. @return As specified above @throw Error If this isn't a directory */ File[] getChildren(); /** Returns the contents of this simple file as a String. @return As specified above @throw Error If this isn't a simple file */ String getContents(); /** Returns the name of this file as a String. @return As specified above */ String getName(); /** Returns the full path of this file as a String. */ String getPath(); /** Returns a boolean indicating either that this file is a directory (true) or not (false). @return As specified above */ boolean isDirectory(); /** Sets the contents of this simple file. @param newContents The new contents of the file @throw Error If this isn't a simple file */ void setContents(String newContents); } (b) i) static File lookup(File folder, String[] path) { File current = folder; for(String p: path) { if(current.isDirectory()) { File f = current.getChild(p); if(f == null) return null; else current = f; } else { return null; } } return current; } ii) static File mkDir(File folder, String[] path) { File current = folder; for(String p: path) { if(current.isDirectory()) { File f = current.getChild(p); if(f != null) { if(f.isDirectory()) current = f; else return null; } else current = current.createSubdirectory(p); } else { return null; } } return current; } (c) Very Concise Example Structure: interface Iterator { T current(); boolean hasCurrent(); void next(); } ... class List { public Iterator iterator() { ... } } ... List lst = new List(); ... Iterator it = lst.iterator(); while(it.hasCurrent()) { System.out.println(it.current()); it.next(); } Purpose: Accessing the elements of a collection in sequence. The advantage the pattern has is that the client has control of the traversal of the elements, e.g. in the above example, we could do something with every second element, say. More straightforward methods of traversal, like the Visitor pattern, where we pass in a function which does something with each element of the collection, are less flexible because they give the client "all-or-nothing" control of the traversal. The really obvious method, where we code operations on the elements internally to the collection, has a number of disadvantages. Consider saving a collection to a file, for example. If we have several implementations of a collection interface, then we have to write a routine to save the collection for each implementation! If we just used the Iterator pattern, we could write one saving routine which would work for all the implementations. Problems: If the collection changes while we're using the iterator, the iterator can be invalidated - it might not point to a valid point in the sequence any longer and, even supposing it does, it might be pointing to the wrong place in the sequence. We can avoid problems like this by taking a snapshot of the sequence when we build the iterator, though this may be costly in memory terms. (d) This implementation yields the paths in depth-first order. import java.util.LinkedList; class FileTreeIterator implements Iterator { private boolean doneThis = false; private File root; private Iterator[] children = null; private int pos = 0; public FileTreeIterator(File root) { this.root = root; } public String current() { if(!doneThis) return root.getPath(); else return children[pos].current(); } public boolean hasCurrent() { return (!doneThis || pos < children.length); } public void next() { if(!doneThis) { doneThis = true; if(root.isDirectory()) { File[] ch = root.getChildren(); children = new Iterator[ch.length]; for(int i=0; i[] {}; } else { children[pos].next(); } while(pos < children.length && !children[pos].hasCurrent()) ++pos; } } static Iterator paths(File folder) { return new FileTreeIterator(folder); } Explanation of why I think it's right: Initially, hasCurrent() returns true because !doneThis We call current(), which returns root.getPath() because !doneThis We call next(), which sets doneThis to true - If the root's a file... - We make an empty array of child iterators - The while loop terminates because pos == children.length - When we call hasCurrent(), it returns false, because pos == children.length - If the root's a directory... - We make an array of child iterators - The while loop loops through until the current child iterator isn't empty - When it terminates, either pos == children.length or children[pos].hasCurrent() - If the former, we're done, hasCurrent() will return false (correctly) - If the latter, we're ready to return the next element When we call next() when doneThis is true, we just move the current child iterator along by one - If we're then done with that child iterator, we search for the next one which isn't empty, as above When we call current() when doneThis is true, we just return the current thing from the current child iterator Essentially, all this inductively suggests that it's right, because it's doing the right thing locally at each stage of the process. Question 2 (a) Model-View: Separate whatever's being modelled (in this case the board) from the way it's rendered. This allows there to be multiple (potentially different) views of a given model. (It also gives good separation of concerns.) Model-View-Controller: A controller allows the user to make changes to the model. It can be implemented as a subclass of a view, though it doesn't have to be implemented that way. Listener interfaces are used to allow models to notify interested parties (like views or controllers) that they have changed. In practice, what they do is to break the dependency of models on views - models need to tell views that they've changed, but they shouldn't know that what they're telling is a view of them. If we didn't use listeners, we'd have a cyclic dependency (bad!) between models and views, since views need to know about models in order to render them. (b) i) public class View extends Visual implements ModelListener { final static 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<9; ++i) { for(int j=0; j<9; ++j) { Contents c = model.get_square(i,j); if(c == Contents.EMPTY) s.fillSquare(j*SQUARE_SIZE, i*SQUARE_SIZE, SQUARE_SIZE); else if(c == Contents.FULL) s.fillCircle(j*SQUARE_SIZE, i*SQUARE_SIZE, SQUARE_SIZE); } } } public void model_changed() { redraw(); } } ii) interface ModelListener { void model_changed(); public static ModelListener NULL = new ModelListener() { public void model_changed() {} }; } enum Contents { NULL, EMPTY, FULL } public class Model { final static private Contents N = Contents.NULL, E = Contents.EMPTY, F = Contents.FULL; private Contents[][] squares = new Contents[][] { {N,N,N,F,F,F,N,N,N}, {N,N,N,F,F,F,N,N,N}, {N,N,N,F,F,F,N,N,N}, {F,F,F,F,F,F,F,F,F}, {F,F,F,F,E,F,F,F,F}, {F,F,F,F,F,F,F,F,F}, {N,N,N,F,F,F,N,N,N}, {N,N,N,F,F,F,N,N,N}, {N,N,N,F,F,F,N,N,N}, }; private ModelListener listener = ModelListener.NULL; /** Returns true if the move from (i1,j1) to (i2,j2) is legal and false otherwise. */ private boolean legal_move(int i1, int j1, int i2, int j2) { if(get_square(i1,j1) != F) return false; if(get_square(i2,j2) != E) return false; int di = Math.abs(i2-i1), dj = Math.abs(j2-j1); if((di == 2 && dj == 0) || (di == 0 && dj == 2)) { int mi = (i1+i2)/2, mj = (j1+j2)/2; if(get_square(mi,mj) == F) return true; } return false; } public void add_listener(ModelListener listener) { this.listener = listener; } public Contents get_square(int i, int j) { if(i >= 0 && i < 9 && j >= 0 && j < 9) return squares[i][j]; else return N; } /** Make the move from (i1,j1) to (i2,j2) if it's legal. */ public void make_move(int i1, int j1, int i2, int j2) { if(legal_move(i1, j1, i2, j2)) { int mi = (i1+i2)/2, mj = (j1+j2)/2; squares[i1][j1] = squares[mi][mj] = E; squares[i2][j2] = F; listener.model_changed(); } } } Initialisation: Model m = new Model(); View v = new View(m); m.add_listener(v); (c) Clicking on a piece selects it (regardless of whether a piece is already selected). Clicking on an empty square with a piece selected makes the move if it's legal and clears the selection. public class Controller extends View { private int selI = -1, selJ = -1; public Controller(Model model) { super(model); } public void mousePress(int x, int y) { int i = y/SQUARE_SIZE, j = x/SQUARE_SIZE; Contents c = model.get_square(i, j); if(c == Contents.FULL) { selI = i; selJ = j; } else if(selI != -1) { model.make_move(selI, selJ, i, j); selI = selJ = -1; } } } Question 3 (a) If association loops are the same thing as cyclic dependencies (I'm just guessing!), then there are a couple of problems worth mentioning: i) Changing anything in the loop affects everything else - e.g. if A depends on B depends on C depends on D depends on A, then changing B might require changes to A, C and D as well. In particular, recompilation may be required even if no actual changes have to be made. ii) Code with association loops is harder to understand and therefore harder to reason about. The bottom line is thus that it's harder to get it right and it's especially hard to *know* that it's right. Care necessary: TODO (b) The Composite pattern. (c) Just change Kit so that it doesn't inherit from Part any more. Then Kits can still contain Parts, but a Part can't be a Kit, so there's no problem. One might even want to get rid of Basic and rewrite Part so that it's concrete and does what Basic did, but that's a design decision. (d) Key features: * You can (externally) access elements of a collection in some order. * You can check whether there are more elements to get. * You can get the next element. { Pedantry (sorry!) Should it read "Define a Java class that allows the storage of a collection of *instances of* Java classes that extend Object, ..."? Also, don't all Java classes extend Object? } class Vector { private Object[] elts = new Object[1]; private int size = 0; private void ensure_capacity() { int len = elts.length; if(size < len) return; Object[] newElts = new Object[len*2]; for(int i=0; i locations = new LinkedList(); private LinkedList types = new LinkedList(); public Iterator get_locations() { return locations.iterator(); } public Iterator get_types { return types.iterator(); } } class Location extends Identifiable { private LinkedList parts = new LinkedList(); public Iterator get_parts() { return parts.iterator(); } } abstract class Type extends Identifiable { public abstract Part make(); } abstract class Part extends Identifiable { protected int location; public Part(int location) { this.location = location; } public int get_location() { return location; } } class Basic extends Part { public Basic(int location) { super(location); } } class Kit extends Part { private LinkedList parts = new LinkedList(); public Kit(int location) { super(location); } public Iterator get_parts() { return parts.iterator(); } } Example: class PenType extends Type { public Part make() { return new Pen(); } } class Pen extends Basic {} Data Invariants: * Each location is in exactly one warehouse. * Each part is in exactly one location. * If a part's in a kit, it doesn't exist separately on its own. (f) An association that you can compute from the actual associations there. (Sort of like saying there's a path from A to C because there are ones from A to B and B to C.) abstract class Part extends Identifiable { protected int location; protected Kit kit = null; public Part(int location) { this.location = location; } public void added_to_kit(Kit kit) { this.kit = kit; } public int get_location() { return kit == null ? location : kit.get_location(); } } The class diagram gets modified so that there's a link from Part to Kit saying "refers to" or something like that (I haven't done any UML, so I'm just guessing). Unfortunately this creates a cyclic dependency between Part and Kit, so in practice you'd probably be a little more cunning about it. Using the identifier might be a good way round the problem, if we had a lookup table somewhere from identifiers to Kits.