1CMSC 433 – Programming LanguageTechnologies and ParadigmsSpring 2004Iterators and Design PatternsFebruary 17, 20042Administrivia• Reading, Liskov ch 6, 15• Another resource: Thinking in Patterns with Java– Link from the class web page• Project 2 due February 25– Version 3 of code posted3Inner Classes• Classes can be nested inside other classes– These are called inner classes• Within a class that contains an inner class, you canuse the inner class just like any other class4Example: The Queue Classclass Queue<Element> { class Entry { // Java inner class Element elt; Entry next; Entry(Element i) { elt = i; next = null; } } Entry theQueue; void enqueue(Element e) { if (theQueue == null) theQueue = new Entry(e); else { Entry last = theQueue; while (last.next != null) last = last.next; last.next = new Entry(e); } } ...5Example: The Queue Class (cont’d)class Queue<Element> { ... Element dequeue() throws EmptyQueueException { if (theQueue == null) throw new EmptyQueueException(); Element e = theQueue.elt; theQueue = theQueue.next; return e; }}6Referring to Outer Class class Queue<Element> { ... int numEntries; class Entry { Element elt; Entry next; Entry(Element i) { elt = i; next = null; numEntries++; } } }• Each inner “object” has an implicit reference tothe outer “object” whose method created it– Can refer to fields directly, or use outer class name.7Anonymous Inner Classes (new Thread() { public void run() { try { Thread.sleep(1000*60*20); System.out.println(”..."); System.exit(1); } catch (Exception e) {} } }).start();• Create anonymous subclass of thread, and invokemethod on it8Other Features of Inner Classes• Outside of the outer class, use outer.inner notationto refer to type of inner class– E.g., Queue.Entry• An inner class marked static does not have areference to outer class– Can’t refer to instance variables of outer class– Must also use outer.inner notation to refer to inner class• Question: Can Queue.Element be made static?9Compiling Inner Classes• The JVM doesn’t know about inner classes– Compiled away, similar to generics– Inner class Foo of outer class A produces A$Foo.class– Anonymous inner class of outer class A producesA$1.class• Why are inner classes useful?10Iteration• Goal: Loop through all objects in an aggregateclass Node { Element elt; Node next; }Node n = ...;while (n != null) { ...; n = n.next; }• Problems:– Depends on implementation details– Varies from one aggregate to another11Iterators in Javapublic interface Iterator {// returns true if the iteration has more elts public boolean hasNext(); // returns the next element in the iteration public Object next() throws NoSuchElementException;}(plus optional remove method)– Implementation of aggregate not exposed– Generic for wide variety of aggregates– Supports multiple traversal strategies12Generic Iterators in Java 1.5public interface Iterator<A> {// returns true if the iteration has more elts public boolean hasNext(); // returns the next element in the iteration public A next() throws NoSuchElementException;}13Using IteratorsIterator<Element> i = c.iterator();while (i.hasNext()) { Element e = i.next(); // do stuff with e}// alternatively use forfor (Iterator i = c.iterator(); i.hasNext(); ) { Element e = (Element) i.next(); // do stuff with e}14Iterators and Queues• Recall queue example from beginning of lecture• We’ll explore options for adding iterators15next() Shouldn’t Mutate Aggregateclass Queue<Element> { ... class QueueIterator implements Iterator<Element> { Entry rest; QueueIterator(Entry q) { rest = q; } boolean hasNext() { return rest != null; } Element next() throws NoSuchElementException { if (rest == null) throw new NoSuchElementException(); Element e = rest.elt; rest = rest.next; // queue data intact return e; } }}16Evil Mutating Clients• But a client could mutate the data structure …HashMap h = ...;...Iterator i = h.entrySet().iterator();System.out.println(i.next());System.out.println(i.next());h.put(“Foo”, “Bar”); // hash table resize!System.out.println(i.next()); // prints ???17Defensive (Proactive) Copying• Solution 1: Iterator copies data structureclass QueueIterator implements Iterator<Element> { Entry rest; QueueIterator(Queue q) { // copy q.theQueue to rest }}• Pro: Works even if queue is mutated• Con: Expensive to construct iterator18Timestamps• Solution 2: Track Mutationsclass Queue<Element> { ... int modCount = 0; void enqueue(Element e) { ... modCount++; } Element dequeue() { ... modCount++; } ...19Timestamps (cont’d) ... class QueueIterator implements Iterator<Element> { int expectedModCount = modCount; // set at iterator // construction time Element next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); ... } // does hasNext() need to be modified? }}• Pro: Iteration construction cheap• Con: Doesn’t allow any mutation20Comments• Neither solution tracks mutations to container elts– Could use clone(), but tricky21What if Mutation is Allowed?• Allowed mutation must be part of iterator spec public void remove()throws IllegalStateException;• Removes from the underlying collection the last elementreturned by the iterator (optional operation). This method can becalled only once per call to next.• The behavior of an iterator is unspecified if the underlyingcollection is modified while the iteration is in progress in anyway other than by calling this method.22Iterators• Key ideas– Separate aggregate structure from traversal protocol– Support additional kinds of traversals• E.g., smallest to largest, largest to smallest, unordered– Multiple simultaneous traversals• Though many Java Collections do not provide this• Structure– Iterator interface defines traversal protocol– Concrete Iterator implementations for each aggregate• And for each traversal strategy– Aggregate instances create Iterator object instances23Design Patterns• Iterators are an example of a design pattern:– Design pattern = problem + solution in context– Iterators: solution for providing generic traversals• Design patterns capture software
View Full Document
Unlocking...