Lecture 09 Iterators and EnumerationsPractice practice practiceAbstract data typeType List211Implement list as a stackClass invariant: describes the fields and the values they contain:Interface ComparableImplementing method compareTo We look at a DrJava program that has abstract class Shape with two subclasses, Square and Circle. A main program creates an array of 8 shapes and sorts them. This illustrates nicely how the interface Comparable is used.Objects from the Shape DemoInterface Iterator in package java.util.Slide 11PowerPoint PresentationUsing the iteratorIterator to enumerate letters in a stringSlide 15A method to produce a string that contains all the items enumerated by any Iterator!!!1Lecture 09 Iterators and EnumerationsReading for these lectures: Weiss, Section 6.3.2 Iterator Interface.Much better is: ProgramLive, Section 12.3.The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity. Edsger W. DijkstraIncrementing C by 1 is not enough to make a good object-oriented language. M. Sakkinen(in C, C++, and Java, x++ adds 1 to x.)2Practice practice practiceIt will help you tremendously to download the programs that we look at today and experiment with them.It will help to write a few implementations of class Iterator yourself and test them. Examples:An Iterator of the digits in a String, producing objects of class Integer.An Iterator of the prime numbers.An Iterator of the chars of a String from end to beginning.An Iterator for the Fibonacci numbers.3Abstract data typeType: a bunch of values together with operations on them.We can write an interface that DEFINES such a type. We call it an “abstract data type” because we don’t give a concrete implementation of it, we just define it “abstractly”4Type List211/** A list is a sequence of Objects. */public interface List211 { /** Make the list empty */ void makeEmpty(); /** Add item e to the list */ void add(Object e); /** Delete an item from the list */ void delete(); /** = an item in the list */ Object getItem(); /** = the number of items in the list */ int size();}Operations are not only abstract but ambiguous. Doesn’t say which item to delete or where to add an item.5Implement list as a stack/** An instance is a stack s of Objects */public class Stack2 implements List211 { private int N; // Maximum number of values in s private Object[] b; // Stack s is in b[0..n-1] private int n;/** Constructor: empty stack with at most N elements */ public Stack2(int N) { } /** Make the stack empty */ public void makeEmpty() { } /** add item e to the front of the stack */ public void add(Object e) { } /** delete item from the front of the stack */ public void delete() { } /** = the front item of the stack */ public Object getItem() { return null; } /** = the number of items in the stack */ public int size() { return 0; } /** = stack elements, with top first, separated by “,” and delimited by “[“ and “]” */ public String toString() { return null; }}This class is on the website. Download and play with it.6Class invariant: describes the fields and the values they contain:/** An instance is a stack s of Objects, with a maximum size */public class Stack1 implements List211 { /** N is the max size of stack s. Stack s appears in b[0..n-1], so that s contains n items. b[0] is the bottom and b[n-1] the top of the stack*/ public Object[] b; public int n; /** Constructor: empty stack of <= m items */ public Stack1(int m) { n= m; b= new Object[m]; n= 0; }7public interface Comparable {/** = if this Object < ob then a negative integer if this Object = ob, then 0 if this Object > ob, then a positive integer */ int compareTo (Object ob);}It has ONE method, compareTo.Interface Comparable8public class Shape implements Comparable { // = if this Object < ob then a negative integer // if this Object = ob, then 0 // if this Object > ob, then a positive integer // (it’s expected that ob is really a Shape) int compareTo(Object ob) {if (this.getArea() < ((Shape)ob).getArea())return -1;if (this.getArea() ==((Shape)ob).getArea())return 0;return 1; } abstract int getArea();} (Shapes are ordered by their area)Implementing method compareToWe look at a DrJava program that has abstract class Shape with two subclasses, Square and Circle. A main program creates an array of 8 shapes and sorts them. This illustrates nicely how the interface Comparable is used. ob is castto Shape9Objects from the Shape Demo a0ShapegetArea() compareTo(Object)getPerimeter()Circlea1ShapegetArea()compareTo(Object)getPerimeter()Squareradius2.0side4.0Circle(double)getRadius()getArea()getPerimeter()toString()Square(double)getSide()getArea()getPerimeter()toString()ba3a3a0 a1 a6 a2 a7 a7 a9 a8b[i].compareTo(b[p])i p10Interface Iteratorin package java.util. (From dictionary)Enumeration: an itemized list.Enumerate: to relate one after another. It is not necessary to enumerate all the bitter and factious disputes that marked this unhappy quarter centuryHe enumerated the advantages of his new position.He enumerated the necessary qualities of a good generalA class that extends iterator is used to make it easy to write loops to enumerate a list of values.11public interface Iterator { /** = “there are more elements to enumerate */ boolean hasNext(); /** = the next element of the enumeration. throw NoSuchElementException if there are none */ Object next(); /** remove the last element returned */ void remove();}Interface Iteratorin package java.util.12/** An enumerator for the evens in h..k */public class EvensEnum implements Iterator { private int item; /** next even int to enum. (if <= k)*/ private int k; /** enumerate the evens <= k /** Constructor: an enumerator for the evens in h..k */ public EvensEnum(int h, int k) { this.k= k; if (h % 2 == 0) item= h; else item= h+1; } /** = "there is another item to enumerate" */ public boolean hasNext() { return item <= k; } /** = the next item to enumerate. Throw a NoSuchElementException if there is none.*/ public Object next() { if (item > k) throw new NoSuchElementException(); int r= item; item= item + 2; return new Integer(r); } /** not implemented */ public void remove() {}}13/** Print out the even
View Full Document
Unlocking...