22 |
|
static int nextHead = -1; |
23 |
|
static int size() { return nextTail - nextHead - 1; } |
24 |
|
|
25 |
< |
|
26 |
< |
static int random(int bound) { |
25 |
> |
|
26 |
> |
static int random(int bound) { |
27 |
|
int x = seed; |
28 |
|
int t = (x % 127773) * 16807 - (x / 127773) * 2836; |
29 |
< |
seed = (t > 0)? t : t + 0x7fffffff; |
29 |
> |
seed = (t > 0) ? t : t + 0x7fffffff; |
30 |
|
return (t & 0x7fffffff) % bound; |
31 |
|
} |
32 |
|
|
33 |
< |
static int random() { |
33 |
> |
static int random() { |
34 |
|
int x = seed; |
35 |
|
int t = (x % 127773) * 16807 - (x / 127773) * 2836; |
36 |
< |
seed = (t > 0)? t : t + 0x7fffffff; |
36 |
> |
seed = (t > 0) ? t : t + 0x7fffffff; |
37 |
|
return (t & 0x7fffffff); |
38 |
|
} |
39 |
|
|
64 |
|
randomOp(deque); |
65 |
|
|
66 |
|
// Test iterator occasionally |
67 |
< |
if ((i & 1023) == 0) |
67 |
> |
if ((i & 1023) == 0) { |
68 |
|
testIter(deque); |
69 |
+ |
testDescendingIter(deque); |
70 |
+ |
} |
71 |
|
|
72 |
|
// Test serialization and copying |
73 |
|
if ((i & 4095) == 0) { |
75 |
|
testEqual(deque, (Deque<Integer>) deque.getClass(). |
76 |
|
getConstructor(Collection.class).newInstance(deque)); |
77 |
|
} |
78 |
< |
|
78 |
> |
|
79 |
|
// Test fancy removal stuff once in a blue moon |
80 |
|
if ((i & 8191) == 0) |
81 |
|
testRemove(deque); |
82 |
< |
|
82 |
> |
|
83 |
|
} |
84 |
|
|
85 |
|
// Stupid tests for clear, toString |
91 |
|
throw new Exception("Deque.toString(): " + deque.toString()); |
92 |
|
} |
93 |
|
|
94 |
< |
static void testIter(Deque<Integer> deque) throws Exception { |
94 |
> |
static void testIter(Deque<Integer> deque) throws Exception { |
95 |
|
int next = nextHead + 1; |
96 |
|
int count = 0; |
97 |
|
for (int j : deque) { |
103 |
|
throw new Exception("Count " + count + " != " + size()); |
104 |
|
} |
105 |
|
|
106 |
+ |
static void testDescendingIter(Deque<Integer> deque) throws Exception { |
107 |
+ |
int next = deque.size() + nextHead; |
108 |
+ |
int count = 0; |
109 |
+ |
for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) { |
110 |
+ |
int j = it.next(); |
111 |
+ |
if (j != next--) |
112 |
+ |
throw new Exception("Element "+ j + " != " + (next-1)); |
113 |
+ |
count++; |
114 |
+ |
} |
115 |
+ |
if (count != size()) |
116 |
+ |
throw new Exception("Count " + count + " != " + size()); |
117 |
+ |
} |
118 |
+ |
|
119 |
|
static void sizeTests(Deque<Integer> deque) throws Exception { |
120 |
|
if (deque.size() != size()) |
121 |
|
throw new Exception("Size: " + deque.size() + |
124 |
|
throw new Exception( |
125 |
|
"IsEmpty " + deque.isEmpty() + ", size " + size()); |
126 |
|
// Check head and tail |
127 |
< |
if (size() == 0) |
127 |
> |
if (size() == 0) |
128 |
|
testEmpty(deque); |
129 |
< |
else |
129 |
> |
else |
130 |
|
nonEmptyTest(deque); |
131 |
|
|
132 |
|
} |
133 |
|
|
134 |
< |
static void nonEmptyTest(Deque<Integer> deque) throws Exception { |
134 |
> |
static void nonEmptyTest(Deque<Integer> deque) throws Exception { |
135 |
|
if (deque.getFirst() != nextHead + 1) |
136 |
< |
throw new Exception("getFirst got: " + |
136 |
> |
throw new Exception("getFirst got: " + |
137 |
|
deque.getFirst() + " expecting " + (nextHead + 1)); |
138 |
|
if (deque.element() != nextHead + 1) |
139 |
|
throw new Exception("element got: " + deque.element() + |
144 |
|
if (deque.peek() != nextHead + 1) |
145 |
|
throw new Exception("peek got: " + deque.peek() + |
146 |
|
" expecting " + (nextHead + 1)); |
147 |
< |
|
147 |
> |
|
148 |
|
if (deque.peekLast() != nextTail - 1) |
149 |
|
throw new Exception("peekLast got: " + deque.peekLast() + |
150 |
|
" expecting " + (nextTail - 1)); |
151 |
|
if (deque.getLast() != nextTail - 1) |
152 |
< |
throw new Exception("getLast got: " + |
152 |
> |
throw new Exception("getLast got: " + |
153 |
|
deque.getLast() + " expecting " + (nextTail - 1)); |
154 |
< |
} |
155 |
< |
|
154 |
> |
} |
155 |
> |
|
156 |
|
|
157 |
|
static void randomOp(Deque<Integer> deque) throws Exception { |
158 |
< |
|
158 |
> |
|
159 |
|
// Perform a random operation |
160 |
< |
switch(random() & 3) { |
160 |
> |
switch (random() & 3) { |
161 |
|
case 0: |
162 |
< |
switch(random() & 3) { |
162 |
> |
switch (random() & 3) { |
163 |
|
case 0: deque.addLast(nextTail++); break; |
164 |
|
case 1: deque.offerLast(nextTail++); break; |
165 |
|
case 2: deque.offer(nextTail++); break; |
172 |
|
int result = 666; |
173 |
|
boolean threw = false; |
174 |
|
try { |
175 |
< |
switch(random(3)) { |
175 |
> |
switch (random(3)) { |
176 |
|
case 0: result = deque.removeFirst(); break; |
177 |
|
case 1: result = deque.remove(); break; |
178 |
|
case 2: result = deque.pop(); break; |
179 |
|
default: throw new Exception("How'd we get here"); |
180 |
|
} |
181 |
< |
} catch(NoSuchElementException e) { |
181 |
> |
} catch (NoSuchElementException e) { |
182 |
|
threw = true; |
183 |
|
} |
184 |
|
if (!threw) |
185 |
|
throw new Exception("Remove-no exception: " + result); |
186 |
|
} else { // deque nonempty |
187 |
|
int result = -1; |
188 |
< |
switch(random(5)) { |
188 |
> |
switch (random(5)) { |
189 |
|
case 0: result = deque.removeFirst(); break; |
190 |
|
case 1: result = deque.remove(); break; |
191 |
|
case 2: result = deque.pop(); break; |
199 |
|
} |
200 |
|
break; |
201 |
|
case 2: |
202 |
< |
switch(random(3)) { |
202 |
> |
switch (random(3)) { |
203 |
|
case 0: deque.addFirst(nextHead--); break; |
204 |
|
case 1: deque.offerFirst(nextHead--); break; |
205 |
|
case 2: deque.push(nextHead--); break; |
212 |
|
boolean threw = false; |
213 |
|
try { |
214 |
|
result = deque.removeLast(); |
215 |
< |
} catch(NoSuchElementException e) { |
215 |
> |
} catch (NoSuchElementException e) { |
216 |
|
threw = true; |
217 |
|
} |
218 |
|
if (!threw) |
219 |
|
throw new Exception("Remove-no exception: " + result); |
220 |
|
} else { // deque nonempty |
221 |
< |
int result = ((random() & 1) == 0? |
221 |
> |
int result = ((random() & 1) == 0 ? |
222 |
|
deque.removeLast() : deque.pollLast()); |
223 |
|
if (result != --nextTail) |
224 |
|
throw new Exception( |
225 |
< |
"Removed "+ result + " expecting "+(nextTail + 1)); |
225 |
> |
"Removed "+ result + " expecting "+(nextTail + 1)); |
226 |
|
} |
227 |
|
break; |
228 |
|
default: |
237 |
|
if (d1.size() != d2.size()) |
238 |
|
throw new Exception("Size " + d1.size() + " != " + d2.size()); |
239 |
|
Iterator<Integer> it = d2.iterator(); |
240 |
< |
for(int i : d1) { |
240 |
> |
for (int i : d1) { |
241 |
|
int j = it.next(); |
242 |
|
if (j != i) |
243 |
|
throw new Exception("Element " + j + " != " + i); |
244 |
|
} |
245 |
|
|
246 |
< |
for(int i : d1) |
246 |
> |
for (int i : d1) |
247 |
|
if (!d2.contains(i)) |
248 |
|
throw new Exception("d2 doesn't contain " + i); |
249 |
< |
for(int i : d2) |
249 |
> |
for (int i : d2) |
250 |
|
if (!d1.contains(i)) |
251 |
|
throw new Exception("d2 doesn't contain " + i); |
252 |
|
|
280 |
|
bos.toByteArray()); |
281 |
|
ObjectInputStream ois = new ObjectInputStream(bin); |
282 |
|
return (T) ois.readObject(); |
283 |
< |
} catch(Exception e) { |
283 |
> |
} catch (Exception e) { |
284 |
|
throw new IllegalArgumentException(e); |
285 |
|
} |
286 |
|
} |
287 |
|
|
288 |
|
private static void testRemove(Deque<Integer> deque) throws Exception { |
289 |
|
Deque<Integer> copy = null; |
290 |
< |
switch(random() & 1) { |
290 |
> |
switch (random() & 1) { |
291 |
|
case 0: |
292 |
|
copy = (Deque<Integer>) deque.getClass(). |
293 |
|
getConstructor(Collection.class).newInstance(deque); |
320 |
|
throw new Exception(e + " missing."); |
321 |
|
|
322 |
|
boolean removed = false; |
323 |
< |
switch(random(3)) { |
323 |
> |
switch (random(3)) { |
324 |
|
case 0: removed = copy.remove(e); break; |
325 |
|
case 1: removed = copy.removeFirstOccurrence(e); break; |
326 |
|
case 2: removed = copy.removeLastOccurrence(e); break; |
327 |
< |
default: throw new Exception("How'd we get here"); |
327 |
> |
default: throw new Exception("How'd we get here"); |
328 |
|
} |
329 |
|
if (!removed) |
330 |
|
throw new Exception(e + " not removed."); |
368 |
|
boolean threw = false; |
369 |
|
int result = 666; |
370 |
|
try { |
371 |
< |
result = ((random() & 1) == 0? |
371 |
> |
result = ((random() & 1) == 0 ? |
372 |
|
deque.getFirst() : deque.element()); |
373 |
< |
} catch(NoSuchElementException e) { |
373 |
> |
} catch (NoSuchElementException e) { |
374 |
|
threw = true; |
375 |
|
} |
376 |
|
if (!threw) |
378 |
|
threw = false; |
379 |
|
try { |
380 |
|
result = deque.getLast(); |
381 |
< |
} catch(NoSuchElementException e) { |
381 |
> |
} catch (NoSuchElementException e) { |
382 |
|
threw = true; |
383 |
|
} |
384 |
|
if (!threw) |