public class ArrayListWithListIterator
1: import java.util.Arrays;
2: import java.util.Iterator;
3: import java.util.ListIterator;
4: import java.util.NoSuchElementException;
5: /**
6: A class that implements the ADT list by using a resizable array.
7: The list has entries that are numbered beginning at 1.
8: The list has an iterator that implements the interface ListIterator.
9: Iterator positions (indexes) are numbered beginning at 0.
10:
11: @author Frank M. Carrano
12: @author Timothy M. Henry
13: @version 4.0
14: */
15: public class ArrayListWithListIterator<T>
16: implements ListWithListIteratorInterface<T>
17: {
18: private T[] list; // Array of list entries; ignore list[0]
19: private int numberOfEntries;
20: private boolean initialized = false;
21: private static final int DEFAULT_CAPACITY = 25;
22: private static final int MAX_CAPACITY = 10000;
23:
24: public ArrayListWithListIterator()
25: {
26: this(DEFAULT_CAPACITY);
27: } // end default constructor
28:
29: public ArrayListWithListIterator(int initialCapacity)
30: {
31: // Is initialCapacity too small?
32: if (initialCapacity < DEFAULT_CAPACITY)
33: initialCapacity = DEFAULT_CAPACITY;
34: else // Is initialCapacity too big?
35: checkCapacity(initialCapacity);
36:
37: // The cast is safe because the new array contains null entries
38: @SuppressWarnings("unchecked")
39: T[] tempList = (T[])new Object[initialCapacity + 1];
40: list = tempList;
41: numberOfEntries = 0;
42: initialized = true;
43: } // end constructor
44:
45: /* < Implementations of the methods of the ADT list go here;
46: you can see them in Chapter 13, beginning at Segment 13.5. */
47:
48: public ListIterator<T> getIterator()
49: {
50: return new ListIteratorForArrayList();
51: } // end getIterator
52:
53: public Iterator<T> iterator()
54: {
55: return getIterator();
56: } // end iterator
57:
58: // 15.24
59: private enum Move {NEXT, PREVIOUS}
60: // 15.24
61: private class ListIteratorForArrayList implements ListIterator<T>
62: {
63: private int nextIndex; // Index of next entry in the iteration
64: private boolean isRemoveOrSetLegal;
65: private Move lastMove;
66:
67: private ListIteratorForArrayList()
68: {
69: nextIndex = 1; // Iteration begins at list's first entry
70: isRemoveOrSetLegal = false;
71: lastMove = null;
72: } // end default constructor
73:
74: // 15.25
75: public boolean hasNext()
76: {
77: return nextIndex <= numberOfEntries;
78: } // end hasNext
79:
80: // 15.26
81: public T next()
82: {
83: if (hasNext())
84: {
85: lastMove = Move.NEXT;
86: isRemoveOrSetLegal = true;
87:
88: T nextEntry = list[nextIndex];
89: nextIndex++; // Advance iterator
90:
91: return nextEntry;
92: }
93: else
94: throw new NoSuchElementException("Illegal call to next(); " +
95: "iterator is after end of list.");
96: } // end next
97:
98: // 15.27
99: public boolean hasPrevious()
100: {
101: return (nextIndex > 1) && (nextIndex <= numberOfEntries + 1);
102: } // end hasPrevious
103:
104: // 15.27
105: public T previous()
106: {
107: if (hasPrevious())
108: {
109: lastMove = Move.PREVIOUS;
110: isRemoveOrSetLegal = true;
111:
112: T previousEntry = list[nextIndex - 1];
113: nextIndex--; // Move iterator back
114: return previousEntry;
115: }
116: else
117: throw new NoSuchElementException("Illegal call to previous(); " +
118: "iterator is before beginning of list.");
119: } // end previous
120:
121: // 15.28
122: public int nextIndex()
123: {
124: int result;
125:
126: if (hasNext())
127: result = nextIndex - 1; // Change to zero-based numbering of iterator
128: else
129: result = numberOfEntries; // End-of-list flag
130:
131: return result;
132: } // end nextIndex
133:
134: // 15.28
135: public int previousIndex()
136: {
137: int result;
138:
139: if (hasPrevious())
140: result = nextIndex - 2; // Change to zero-based numbering of iterator
141: else
142: result = -1; // Beginning-of-list flag
143:
144: return result;
145: } // end previousIndex
146:
147: // 15.29
148: public void add(T newEntry)
149: {
150: isRemoveOrSetLegal = false;
151:
152: // Insert newEntry immediately before the the iterator's current position
153: ArrayListWithListIterator.this.add(nextIndex, newEntry);
154: nextIndex++;
155: } // end add
156:
157: // 15.30
158: public void remove()
159: {
160: if (isRemoveOrSetLegal)
161: {
162: isRemoveOrSetLegal = false;
163:
164: if (lastMove.equals(Move.NEXT))
165: {
166: // next() called, but neither add() nor remove() has been
167: // called since.
168:
169: // Remove entry last returned by next().
170:
171: // nextIndex is 1 more than the index of the entry
172: // returned by next()
173: ArrayListWithListIterator.this.remove(nextIndex - 1);
174: nextIndex--; // Move iterator back
175: }
176: else
177: {
178: // previous() called, but neither add() nor remove() has been
179: // called since
180: assert lastMove.equals(Move.PREVIOUS);
181:
182: // Remove entry last returned by previous().
183:
184: // nextIndex is the index of the entry returned by previous().
185: ArrayListWithListIterator.this.remove(nextIndex);
186: } // end if
187: }
188: else
189: throw new IllegalStateException("Illegal call to remove(); " +
190: "next() or previous() not called, OR " +
191: "add() or remove() called since then.");
192: } // end remove
193: // 15.31
194: public void set(T newEntry)
195: {
196: if (isRemoveOrSetLegal)
197: {
198: if (lastMove.equals(Move.NEXT))
199: {
200: list[nextIndex - 1] = newEntry; // Replace entry last returned by next()
201: }
202: else
203: {
204: assert lastMove.equals(Move.PREVIOUS);
205: list[nextIndex] = newEntry; // Replace entry last returned by previous()
206: } // end if
207: }
208: else
209: throw new IllegalStateException("Illegal call to set(); " +
210: "next() or previous() not called, OR " +
211: "add() or remove() called since then.");
212: } // end set
213: } // end ListIteratorForArrayList
214: } // end ArrayListWithListIterator