[cvs] / jsr166 / src / test / tck / ArrayDequeTest.java Repository:
ViewVC logotype

Annotation of /jsr166/src/test/tck/ArrayDequeTest.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.42 - (view) (download)

1 : dl 1.1 /*
2 :     * Written by Doug Lea with assistance from members of JCP JSR-166
3 :     * Expert Group and released to the public domain, as explained at
4 : jsr166 1.22 * http://creativecommons.org/publicdomain/zero/1.0/
5 : dl 1.1 */
6 :    
7 : jsr166 1.30 import java.util.ArrayDeque;
8 : jsr166 1.24 import java.util.Arrays;
9 :     import java.util.Collection;
10 :     import java.util.Deque;
11 :     import java.util.Iterator;
12 :     import java.util.NoSuchElementException;
13 :     import java.util.Queue;
14 :     import java.util.Random;
15 : jsr166 1.42 import java.util.concurrent.ThreadLocalRandom;
16 : dl 1.1
17 : jsr166 1.30 import junit.framework.Test;
18 :     import junit.framework.TestSuite;
19 :    
20 : dl 1.1 public class ArrayDequeTest extends JSR166TestCase {
21 :     public static void main(String[] args) {
22 : jsr166 1.34 main(suite(), args);
23 : dl 1.1 }
24 :    
25 :     public static Test suite() {
26 : jsr166 1.40 class Implementation implements CollectionImplementation {
27 :     public Class<?> klazz() { return ArrayDeque.class; }
28 :     public Collection emptyCollection() { return new ArrayDeque(); }
29 :     public Object makeElement(int i) { return i; }
30 :     public boolean isConcurrent() { return false; }
31 :     public boolean permitsNulls() { return false; }
32 :     }
33 :     return newTestSuite(ArrayDequeTest.class,
34 :     CollectionTest.testSuite(new Implementation()));
35 : dl 1.1 }
36 :    
37 :     /**
38 : jsr166 1.26 * Returns a new deque of given size containing consecutive
39 : jsr166 1.41 * Integers 0 ... n - 1.
40 : dl 1.1 */
41 : jsr166 1.20 private ArrayDeque<Integer> populatedDeque(int n) {
42 : jsr166 1.42 // Randomize various aspects of memory layout, including
43 :     // filled-to-capacity and wraparound.
44 :     final ArrayDeque<Integer> q;
45 :     ThreadLocalRandom rnd = ThreadLocalRandom.current();
46 :     switch (rnd.nextInt(6)) {
47 :     case 0: q = new ArrayDeque<Integer>(); break;
48 :     case 1: q = new ArrayDeque<Integer>(0); break;
49 :     case 2: q = new ArrayDeque<Integer>(1); break;
50 :     case 3: q = new ArrayDeque<Integer>(n - 1); break;
51 :     case 4: q = new ArrayDeque<Integer>(n); break;
52 :     case 5: q = new ArrayDeque<Integer>(n + 1); break;
53 :     default: throw new AssertionError();
54 :     }
55 :     switch (rnd.nextInt(3)) {
56 :     case 0:
57 :     q.addFirst(42);
58 :     assertEquals((Integer) 42, q.removeLast());
59 :     break;
60 :     case 1:
61 :     q.addLast(42);
62 :     assertEquals((Integer) 42, q.removeLast());
63 :     break;
64 :     case 2: /* do nothing */ break;
65 :     default: throw new AssertionError();
66 :     }
67 : dl 1.1 assertTrue(q.isEmpty());
68 : jsr166 1.42 if (rnd.nextBoolean())
69 :     for (int i = 0; i < n; i++)
70 :     assertTrue(q.offerLast((Integer) i));
71 :     else
72 :     for (int i = n; --i >= 0; )
73 :     q.addFirst((Integer) i);
74 : dl 1.1 assertFalse(q.isEmpty());
75 : jsr166 1.8 assertEquals(n, q.size());
76 : jsr166 1.41 assertEquals((Integer) 0, q.peekFirst());
77 :     assertEquals((Integer) (n - 1), q.peekLast());
78 : dl 1.1 return q;
79 :     }
80 : jsr166 1.5
81 : dl 1.1 /**
82 : jsr166 1.16 * new deque is empty
83 : dl 1.1 */
84 :     public void testConstructor1() {
85 :     assertEquals(0, new ArrayDeque().size());
86 :     }
87 :    
88 :     /**
89 :     * Initializing from null Collection throws NPE
90 :     */
91 :     public void testConstructor3() {
92 :     try {
93 : jsr166 1.33 new ArrayDeque((Collection)null);
94 : dl 1.1 shouldThrow();
95 : jsr166 1.9 } catch (NullPointerException success) {}
96 : dl 1.1 }
97 :    
98 :     /**
99 : jsr166 1.16 * Initializing from Collection of null elements throws NPE
100 :     */
101 :     public void testConstructor4() {
102 :     try {
103 : jsr166 1.35 new ArrayDeque(Arrays.asList(new Integer[SIZE]));
104 : jsr166 1.16 shouldThrow();
105 :     } catch (NullPointerException success) {}
106 :     }
107 : dl 1.1
108 : jsr166 1.16 /**
109 :     * Initializing from Collection with some null elements throws NPE
110 :     */
111 :     public void testConstructor5() {
112 : jsr166 1.35 Integer[] ints = new Integer[SIZE];
113 : jsr166 1.36 for (int i = 0; i < SIZE - 1; ++i)
114 : jsr166 1.35 ints[i] = new Integer(i);
115 : jsr166 1.16 try {
116 : jsr166 1.33 new ArrayDeque(Arrays.asList(ints));
117 : jsr166 1.16 shouldThrow();
118 :     } catch (NullPointerException success) {}
119 :     }
120 :    
121 :     /**
122 :     * Deque contains all elements of collection used to initialize
123 : dl 1.1 */
124 :     public void testConstructor6() {
125 : jsr166 1.9 Integer[] ints = new Integer[SIZE];
126 :     for (int i = 0; i < SIZE; ++i)
127 :     ints[i] = new Integer(i);
128 :     ArrayDeque q = new ArrayDeque(Arrays.asList(ints));
129 :     for (int i = 0; i < SIZE; ++i)
130 :     assertEquals(ints[i], q.pollFirst());
131 : dl 1.1 }
132 :    
133 :     /**
134 :     * isEmpty is true before add, false after
135 :     */
136 :     public void testEmpty() {
137 :     ArrayDeque q = new ArrayDeque();
138 :     assertTrue(q.isEmpty());
139 :     q.add(new Integer(1));
140 :     assertFalse(q.isEmpty());
141 :     q.add(new Integer(2));
142 :     q.removeFirst();
143 :     q.removeFirst();
144 :     assertTrue(q.isEmpty());
145 :     }
146 :    
147 :     /**
148 :     * size changes when elements added and removed
149 :     */
150 :     public void testSize() {
151 :     ArrayDeque q = populatedDeque(SIZE);
152 :     for (int i = 0; i < SIZE; ++i) {
153 : jsr166 1.36 assertEquals(SIZE - i, q.size());
154 : dl 1.1 q.removeFirst();
155 :     }
156 :     for (int i = 0; i < SIZE; ++i) {
157 :     assertEquals(i, q.size());
158 :     q.add(new Integer(i));
159 :     }
160 :     }
161 :    
162 :     /**
163 :     * push(null) throws NPE
164 :     */
165 :     public void testPushNull() {
166 : jsr166 1.35 ArrayDeque q = new ArrayDeque(1);
167 : jsr166 1.8 try {
168 : dl 1.1 q.push(null);
169 :     shouldThrow();
170 : jsr166 1.9 } catch (NullPointerException success) {}
171 : dl 1.1 }
172 :    
173 :     /**
174 : jsr166 1.16 * peekFirst() returns element inserted with push
175 : dl 1.1 */
176 :     public void testPush() {
177 :     ArrayDeque q = populatedDeque(3);
178 :     q.pollLast();
179 : jsr166 1.8 q.push(four);
180 : jsr166 1.12 assertSame(four, q.peekFirst());
181 : jsr166 1.5 }
182 : dl 1.1
183 :     /**
184 : jsr166 1.16 * pop() removes next element, or throws NSEE if empty
185 : dl 1.1 */
186 :     public void testPop() {
187 :     ArrayDeque q = populatedDeque(SIZE);
188 :     for (int i = 0; i < SIZE; ++i) {
189 : jsr166 1.12 assertEquals(i, q.pop());
190 : dl 1.1 }
191 :     try {
192 :     q.pop();
193 :     shouldThrow();
194 : jsr166 1.9 } catch (NoSuchElementException success) {}
195 : dl 1.1 }
196 :    
197 :     /**
198 :     * offer(null) throws NPE
199 :     */
200 : jsr166 1.16 public void testOfferNull() {
201 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
202 : jsr166 1.16 try {
203 :     q.offer(null);
204 :     shouldThrow();
205 :     } catch (NullPointerException success) {}
206 :     }
207 :    
208 :     /**
209 :     * offerFirst(null) throws NPE
210 :     */
211 : dl 1.1 public void testOfferFirstNull() {
212 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
213 : jsr166 1.8 try {
214 : dl 1.1 q.offerFirst(null);
215 :     shouldThrow();
216 : jsr166 1.9 } catch (NullPointerException success) {}
217 : dl 1.1 }
218 :    
219 :     /**
220 : jsr166 1.16 * offerLast(null) throws NPE
221 :     */
222 :     public void testOfferLastNull() {
223 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
224 : jsr166 1.16 try {
225 :     q.offerLast(null);
226 :     shouldThrow();
227 :     } catch (NullPointerException success) {}
228 :     }
229 :    
230 :     /**
231 :     * offer(x) succeeds
232 :     */
233 :     public void testOffer() {
234 :     ArrayDeque q = new ArrayDeque();
235 :     assertTrue(q.offer(zero));
236 :     assertTrue(q.offer(one));
237 :     assertSame(zero, q.peekFirst());
238 :     assertSame(one, q.peekLast());
239 :     }
240 :    
241 :     /**
242 :     * offerFirst(x) succeeds
243 : dl 1.1 */
244 :     public void testOfferFirst() {
245 :     ArrayDeque q = new ArrayDeque();
246 : jsr166 1.16 assertTrue(q.offerFirst(zero));
247 :     assertTrue(q.offerFirst(one));
248 :     assertSame(one, q.peekFirst());
249 :     assertSame(zero, q.peekLast());
250 : dl 1.1 }
251 :    
252 :     /**
253 : jsr166 1.16 * offerLast(x) succeeds
254 : dl 1.1 */
255 :     public void testOfferLast() {
256 :     ArrayDeque q = new ArrayDeque();
257 : jsr166 1.16 assertTrue(q.offerLast(zero));
258 :     assertTrue(q.offerLast(one));
259 :     assertSame(zero, q.peekFirst());
260 :     assertSame(one, q.peekLast());
261 : dl 1.1 }
262 :    
263 :     /**
264 : jsr166 1.16 * add(null) throws NPE
265 :     */
266 :     public void testAddNull() {
267 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
268 : jsr166 1.16 try {
269 :     q.add(null);
270 :     shouldThrow();
271 :     } catch (NullPointerException success) {}
272 :     }
273 :    
274 :     /**
275 :     * addFirst(null) throws NPE
276 :     */
277 :     public void testAddFirstNull() {
278 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
279 : jsr166 1.16 try {
280 :     q.addFirst(null);
281 :     shouldThrow();
282 :     } catch (NullPointerException success) {}
283 :     }
284 :    
285 :     /**
286 :     * addLast(null) throws NPE
287 :     */
288 :     public void testAddLastNull() {
289 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
290 : jsr166 1.16 try {
291 :     q.addLast(null);
292 :     shouldThrow();
293 :     } catch (NullPointerException success) {}
294 :     }
295 :    
296 :     /**
297 :     * add(x) succeeds
298 : dl 1.1 */
299 :     public void testAdd() {
300 :     ArrayDeque q = new ArrayDeque();
301 : jsr166 1.16 assertTrue(q.add(zero));
302 :     assertTrue(q.add(one));
303 :     assertSame(zero, q.peekFirst());
304 :     assertSame(one, q.peekLast());
305 :     }
306 :    
307 :     /**
308 :     * addFirst(x) succeeds
309 :     */
310 :     public void testAddFirst() {
311 :     ArrayDeque q = new ArrayDeque();
312 :     q.addFirst(zero);
313 :     q.addFirst(one);
314 :     assertSame(one, q.peekFirst());
315 :     assertSame(zero, q.peekLast());
316 :     }
317 :    
318 :     /**
319 :     * addLast(x) succeeds
320 :     */
321 :     public void testAddLast() {
322 :     ArrayDeque q = new ArrayDeque();
323 :     q.addLast(zero);
324 :     q.addLast(one);
325 :     assertSame(zero, q.peekFirst());
326 :     assertSame(one, q.peekLast());
327 : dl 1.1 }
328 :    
329 :     /**
330 :     * addAll(null) throws NPE
331 :     */
332 :     public void testAddAll1() {
333 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
334 : dl 1.1 try {
335 :     q.addAll(null);
336 :     shouldThrow();
337 : jsr166 1.9 } catch (NullPointerException success) {}
338 : dl 1.1 }
339 :    
340 :     /**
341 : jsr166 1.16 * addAll of a collection with null elements throws NPE
342 :     */
343 :     public void testAddAll2() {
344 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
345 : jsr166 1.16 try {
346 : jsr166 1.35 q.addAll(Arrays.asList(new Integer[SIZE]));
347 : jsr166 1.16 shouldThrow();
348 :     } catch (NullPointerException success) {}
349 :     }
350 :    
351 :     /**
352 :     * addAll of a collection with any null elements throws NPE after
353 :     * possibly adding some elements
354 :     */
355 :     public void testAddAll3() {
356 : jsr166 1.35 ArrayDeque q = new ArrayDeque();
357 :     Integer[] ints = new Integer[SIZE];
358 : jsr166 1.36 for (int i = 0; i < SIZE - 1; ++i)
359 : jsr166 1.35 ints[i] = new Integer(i);
360 : jsr166 1.16 try {
361 :     q.addAll(Arrays.asList(ints));
362 :     shouldThrow();
363 :     } catch (NullPointerException success) {}
364 :     }
365 :    
366 :     /**
367 :     * Deque contains all elements, in traversal order, of successful addAll
368 : dl 1.1 */
369 :     public void testAddAll5() {
370 : jsr166 1.10 Integer[] empty = new Integer[0];
371 :     Integer[] ints = new Integer[SIZE];
372 :     for (int i = 0; i < SIZE; ++i)
373 :     ints[i] = new Integer(i);
374 :     ArrayDeque q = new ArrayDeque();
375 :     assertFalse(q.addAll(Arrays.asList(empty)));
376 :     assertTrue(q.addAll(Arrays.asList(ints)));
377 :     for (int i = 0; i < SIZE; ++i)
378 :     assertEquals(ints[i], q.pollFirst());
379 : dl 1.1 }
380 :    
381 :     /**
382 : jsr166 1.16 * pollFirst() succeeds unless empty
383 : dl 1.1 */
384 :     public void testPollFirst() {
385 :     ArrayDeque q = populatedDeque(SIZE);
386 :     for (int i = 0; i < SIZE; ++i) {
387 : jsr166 1.12 assertEquals(i, q.pollFirst());
388 : dl 1.1 }
389 : jsr166 1.8 assertNull(q.pollFirst());
390 : dl 1.1 }
391 :    
392 :     /**
393 : jsr166 1.16 * pollLast() succeeds unless empty
394 : dl 1.1 */
395 :     public void testPollLast() {
396 :     ArrayDeque q = populatedDeque(SIZE);
397 : jsr166 1.36 for (int i = SIZE - 1; i >= 0; --i) {
398 : jsr166 1.12 assertEquals(i, q.pollLast());
399 : dl 1.1 }
400 : jsr166 1.8 assertNull(q.pollLast());
401 : dl 1.1 }
402 :    
403 :     /**
404 : jsr166 1.16 * poll() succeeds unless empty
405 : dl 1.1 */
406 :     public void testPoll() {
407 :     ArrayDeque q = populatedDeque(SIZE);
408 :     for (int i = 0; i < SIZE; ++i) {
409 : jsr166 1.12 assertEquals(i, q.poll());
410 : dl 1.1 }
411 : jsr166 1.8 assertNull(q.poll());
412 : dl 1.1 }
413 :    
414 :     /**
415 : jsr166 1.16 * remove() removes next element, or throws NSEE if empty
416 : dl 1.1 */
417 :     public void testRemove() {
418 :     ArrayDeque q = populatedDeque(SIZE);
419 :     for (int i = 0; i < SIZE; ++i) {
420 : jsr166 1.12 assertEquals(i, q.remove());
421 : dl 1.1 }
422 :     try {
423 :     q.remove();
424 :     shouldThrow();
425 : jsr166 1.9 } catch (NoSuchElementException success) {}
426 : dl 1.1 }
427 :    
428 :     /**
429 : jsr166 1.16 * remove(x) removes x and returns true if present
430 :     */
431 :     public void testRemoveElement() {
432 :     ArrayDeque q = populatedDeque(SIZE);
433 : jsr166 1.31 for (int i = 1; i < SIZE; i += 2) {
434 : jsr166 1.21 assertTrue(q.contains(i));
435 :     assertTrue(q.remove(i));
436 :     assertFalse(q.contains(i));
437 : jsr166 1.38 assertTrue(q.contains(i - 1));
438 : jsr166 1.16 }
439 : jsr166 1.31 for (int i = 0; i < SIZE; i += 2) {
440 : jsr166 1.21 assertTrue(q.contains(i));
441 :     assertTrue(q.remove(i));
442 :     assertFalse(q.contains(i));
443 : jsr166 1.38 assertFalse(q.remove(i + 1));
444 :     assertFalse(q.contains(i + 1));
445 : jsr166 1.16 }
446 :     assertTrue(q.isEmpty());
447 :     }
448 :    
449 :     /**
450 :     * peekFirst() returns next element, or null if empty
451 : dl 1.1 */
452 :     public void testPeekFirst() {
453 :     ArrayDeque q = populatedDeque(SIZE);
454 :     for (int i = 0; i < SIZE; ++i) {
455 : jsr166 1.12 assertEquals(i, q.peekFirst());
456 :     assertEquals(i, q.pollFirst());
457 : dl 1.1 assertTrue(q.peekFirst() == null ||
458 : jsr166 1.12 !q.peekFirst().equals(i));
459 : dl 1.1 }
460 : jsr166 1.8 assertNull(q.peekFirst());
461 : dl 1.1 }
462 :    
463 :     /**
464 : jsr166 1.16 * peek() returns next element, or null if empty
465 : dl 1.1 */
466 :     public void testPeek() {
467 :     ArrayDeque q = populatedDeque(SIZE);
468 :     for (int i = 0; i < SIZE; ++i) {
469 : jsr166 1.12 assertEquals(i, q.peek());
470 :     assertEquals(i, q.poll());
471 : dl 1.1 assertTrue(q.peek() == null ||
472 : jsr166 1.12 !q.peek().equals(i));
473 : dl 1.1 }
474 : jsr166 1.8 assertNull(q.peek());
475 : dl 1.1 }
476 :    
477 :     /**
478 : jsr166 1.16 * peekLast() returns next element, or null if empty
479 : dl 1.1 */
480 :     public void testPeekLast() {
481 :     ArrayDeque q = populatedDeque(SIZE);
482 : jsr166 1.36 for (int i = SIZE - 1; i >= 0; --i) {
483 : jsr166 1.12 assertEquals(i, q.peekLast());
484 :     assertEquals(i, q.pollLast());
485 : dl 1.1 assertTrue(q.peekLast() == null ||
486 : jsr166 1.12 !q.peekLast().equals(i));
487 : dl 1.1 }
488 : jsr166 1.8 assertNull(q.peekLast());
489 : dl 1.1 }
490 :    
491 :     /**
492 : jsr166 1.16 * element() returns first element, or throws NSEE if empty
493 :     */
494 :     public void testElement() {
495 :     ArrayDeque q = populatedDeque(SIZE);
496 :     for (int i = 0; i < SIZE; ++i) {
497 :     assertEquals(i, q.element());
498 :     assertEquals(i, q.poll());
499 :     }
500 :     try {
501 :     q.element();
502 :     shouldThrow();
503 :     } catch (NoSuchElementException success) {}
504 :     }
505 :    
506 :     /**
507 :     * getFirst() returns first element, or throws NSEE if empty
508 : dl 1.1 */
509 :     public void testFirstElement() {
510 :     ArrayDeque q = populatedDeque(SIZE);
511 :     for (int i = 0; i < SIZE; ++i) {
512 : jsr166 1.12 assertEquals(i, q.getFirst());
513 :     assertEquals(i, q.pollFirst());
514 : dl 1.1 }
515 :     try {
516 :     q.getFirst();
517 :     shouldThrow();
518 : jsr166 1.9 } catch (NoSuchElementException success) {}
519 : dl 1.1 }
520 :    
521 :     /**
522 : jsr166 1.16 * getLast() returns last element, or throws NSEE if empty
523 : dl 1.1 */
524 :     public void testLastElement() {
525 :     ArrayDeque q = populatedDeque(SIZE);
526 : jsr166 1.36 for (int i = SIZE - 1; i >= 0; --i) {
527 : jsr166 1.12 assertEquals(i, q.getLast());
528 :     assertEquals(i, q.pollLast());
529 : dl 1.1 }
530 :     try {
531 :     q.getLast();
532 :     shouldThrow();
533 : jsr166 1.9 } catch (NoSuchElementException success) {}
534 : jsr166 1.8 assertNull(q.peekLast());
535 : dl 1.1 }
536 :    
537 :     /**
538 : jsr166 1.16 * removeFirst() removes first element, or throws NSEE if empty
539 : dl 1.1 */
540 :     public void testRemoveFirst() {
541 :     ArrayDeque q = populatedDeque(SIZE);
542 :     for (int i = 0; i < SIZE; ++i) {
543 : jsr166 1.12 assertEquals(i, q.removeFirst());
544 : dl 1.1 }
545 :     try {
546 :     q.removeFirst();
547 :     shouldThrow();
548 : jsr166 1.9 } catch (NoSuchElementException success) {}
549 : jsr166 1.16 assertNull(q.peekFirst());
550 :     }
551 :    
552 :     /**
553 :     * removeLast() removes last element, or throws NSEE if empty
554 :     */
555 :     public void testRemoveLast() {
556 :     ArrayDeque q = populatedDeque(SIZE);
557 :     for (int i = SIZE - 1; i >= 0; --i) {
558 :     assertEquals(i, q.removeLast());
559 :     }
560 :     try {
561 :     q.removeLast();
562 :     shouldThrow();
563 :     } catch (NoSuchElementException success) {}
564 :     assertNull(q.peekLast());
565 : dl 1.1 }
566 :    
567 :     /**
568 :     * removeFirstOccurrence(x) removes x and returns true if present
569 :     */
570 :     public void testRemoveFirstOccurrence() {
571 :     ArrayDeque q = populatedDeque(SIZE);
572 : jsr166 1.39 assertFalse(q.removeFirstOccurrence(null));
573 : jsr166 1.31 for (int i = 1; i < SIZE; i += 2) {
574 : dl 1.1 assertTrue(q.removeFirstOccurrence(new Integer(i)));
575 :     }
576 : jsr166 1.31 for (int i = 0; i < SIZE; i += 2) {
577 : dl 1.1 assertTrue(q.removeFirstOccurrence(new Integer(i)));
578 : jsr166 1.38 assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
579 : dl 1.1 }
580 :     assertTrue(q.isEmpty());
581 : jsr166 1.39 assertFalse(q.removeFirstOccurrence(null));
582 :     assertFalse(q.removeFirstOccurrence(42));
583 :     q = new ArrayDeque();
584 :     assertFalse(q.removeFirstOccurrence(null));
585 :     assertFalse(q.removeFirstOccurrence(42));
586 : dl 1.1 }
587 :    
588 :     /**
589 :     * removeLastOccurrence(x) removes x and returns true if present
590 :     */
591 :     public void testRemoveLastOccurrence() {
592 :     ArrayDeque q = populatedDeque(SIZE);
593 : jsr166 1.39 assertFalse(q.removeLastOccurrence(null));
594 : jsr166 1.31 for (int i = 1; i < SIZE; i += 2) {
595 : dl 1.1 assertTrue(q.removeLastOccurrence(new Integer(i)));
596 :     }
597 : jsr166 1.31 for (int i = 0; i < SIZE; i += 2) {
598 : dl 1.1 assertTrue(q.removeLastOccurrence(new Integer(i)));
599 : jsr166 1.38 assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
600 : dl 1.1 }
601 :     assertTrue(q.isEmpty());
602 : jsr166 1.39 assertFalse(q.removeLastOccurrence(null));
603 :     assertFalse(q.removeLastOccurrence(42));
604 :     q = new ArrayDeque();
605 :     assertFalse(q.removeLastOccurrence(null));
606 :     assertFalse(q.removeLastOccurrence(42));
607 : dl 1.1 }
608 :    
609 :     /**
610 :     * contains(x) reports true when elements added but not yet removed
611 :     */
612 :     public void testContains() {
613 :     ArrayDeque q = populatedDeque(SIZE);
614 :     for (int i = 0; i < SIZE; ++i) {
615 :     assertTrue(q.contains(new Integer(i)));
616 : jsr166 1.12 assertEquals(i, q.pollFirst());
617 : dl 1.1 assertFalse(q.contains(new Integer(i)));
618 :     }
619 :     }
620 :    
621 :     /**
622 :     * clear removes all elements
623 :     */
624 :     public void testClear() {
625 :     ArrayDeque q = populatedDeque(SIZE);
626 :     q.clear();
627 :     assertTrue(q.isEmpty());
628 :     assertEquals(0, q.size());
629 : jsr166 1.12 assertTrue(q.add(new Integer(1)));
630 : dl 1.1 assertFalse(q.isEmpty());
631 :     q.clear();
632 :     assertTrue(q.isEmpty());
633 :     }
634 :    
635 :     /**
636 :     * containsAll(c) is true when c contains a subset of elements
637 :     */
638 :     public void testContainsAll() {
639 :     ArrayDeque q = populatedDeque(SIZE);
640 :     ArrayDeque p = new ArrayDeque();
641 :     for (int i = 0; i < SIZE; ++i) {
642 :     assertTrue(q.containsAll(p));
643 :     assertFalse(p.containsAll(q));
644 : jsr166 1.12 assertTrue(p.add(new Integer(i)));
645 : dl 1.1 }
646 :     assertTrue(p.containsAll(q));
647 :     }
648 :    
649 :     /**
650 :     * retainAll(c) retains only those elements of c and reports true if changed
651 :     */
652 :     public void testRetainAll() {
653 :     ArrayDeque q = populatedDeque(SIZE);
654 :     ArrayDeque p = populatedDeque(SIZE);
655 :     for (int i = 0; i < SIZE; ++i) {
656 :     boolean changed = q.retainAll(p);
657 : jsr166 1.12 assertEquals(changed, (i > 0));
658 : dl 1.1 assertTrue(q.containsAll(p));
659 : jsr166 1.36 assertEquals(SIZE - i, q.size());
660 : dl 1.1 p.removeFirst();
661 :     }
662 :     }
663 :    
664 :     /**
665 :     * removeAll(c) removes only those elements of c and reports true if changed
666 :     */
667 :     public void testRemoveAll() {
668 :     for (int i = 1; i < SIZE; ++i) {
669 :     ArrayDeque q = populatedDeque(SIZE);
670 :     ArrayDeque p = populatedDeque(i);
671 :     assertTrue(q.removeAll(p));
672 : jsr166 1.36 assertEquals(SIZE - i, q.size());
673 : dl 1.1 for (int j = 0; j < i; ++j) {
674 : jsr166 1.12 assertFalse(q.contains(p.removeFirst()));
675 : dl 1.1 }
676 :     }
677 :     }
678 :    
679 : jsr166 1.27 void checkToArray(ArrayDeque q) {
680 :     int size = q.size();
681 :     Object[] o = q.toArray();
682 :     assertEquals(size, o.length);
683 :     Iterator it = q.iterator();
684 :     for (int i = 0; i < size; i++) {
685 :     Integer x = (Integer) it.next();
686 :     assertEquals((Integer)o[0] + i, (int) x);
687 :     assertSame(o[i], x);
688 :     }
689 :     }
690 :    
691 : dl 1.1 /**
692 : jsr166 1.19 * toArray() contains all elements in FIFO order
693 : dl 1.1 */
694 :     public void testToArray() {
695 : jsr166 1.27 ArrayDeque q = new ArrayDeque();
696 :     for (int i = 0; i < SIZE; i++) {
697 :     checkToArray(q);
698 :     q.addLast(i);
699 :     }
700 :     // Provoke wraparound
701 :     for (int i = 0; i < SIZE; i++) {
702 :     checkToArray(q);
703 :     assertEquals(i, q.poll());
704 : jsr166 1.36 q.addLast(SIZE + i);
705 : jsr166 1.27 }
706 :     for (int i = 0; i < SIZE; i++) {
707 :     checkToArray(q);
708 : jsr166 1.36 assertEquals(SIZE + i, q.poll());
709 : jsr166 1.27 }
710 :     }
711 :    
712 :     void checkToArray2(ArrayDeque q) {
713 :     int size = q.size();
714 : jsr166 1.37 Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
715 : jsr166 1.27 Integer[] a2 = new Integer[size];
716 : jsr166 1.37 Integer[] a3 = new Integer[size + 2];
717 : jsr166 1.27 if (size > 0) Arrays.fill(a1, 42);
718 :     Arrays.fill(a2, 42);
719 :     Arrays.fill(a3, 42);
720 : jsr166 1.37 Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
721 : jsr166 1.27 Integer[] b2 = (Integer[]) q.toArray(a2);
722 :     Integer[] b3 = (Integer[]) q.toArray(a3);
723 :     assertSame(a2, b2);
724 :     assertSame(a3, b3);
725 :     Iterator it = q.iterator();
726 :     for (int i = 0; i < size; i++) {
727 :     Integer x = (Integer) it.next();
728 :     assertSame(b1[i], x);
729 :     assertEquals(b1[0] + i, (int) x);
730 :     assertSame(b2[i], x);
731 :     assertSame(b3[i], x);
732 :     }
733 :     assertNull(a3[size]);
734 : jsr166 1.37 assertEquals(42, (int) a3[size + 1]);
735 : jsr166 1.27 if (size > 0) {
736 :     assertNotSame(a1, b1);
737 :     assertEquals(size, b1.length);
738 :     for (int i = 0; i < a1.length; i++) {
739 :     assertEquals(42, (int) a1[i]);
740 :     }
741 :     }
742 : dl 1.1 }
743 :    
744 :     /**
745 : jsr166 1.19 * toArray(a) contains all elements in FIFO order
746 : dl 1.1 */
747 :     public void testToArray2() {
748 : jsr166 1.27 ArrayDeque q = new ArrayDeque();
749 :     for (int i = 0; i < SIZE; i++) {
750 :     checkToArray2(q);
751 :     q.addLast(i);
752 :     }
753 :     // Provoke wraparound
754 :     for (int i = 0; i < SIZE; i++) {
755 :     checkToArray2(q);
756 :     assertEquals(i, q.poll());
757 : jsr166 1.36 q.addLast(SIZE + i);
758 : jsr166 1.27 }
759 :     for (int i = 0; i < SIZE; i++) {
760 :     checkToArray2(q);
761 : jsr166 1.36 assertEquals(SIZE + i, q.poll());
762 : jsr166 1.27 }
763 : dl 1.1 }
764 :    
765 :     /**
766 : jsr166 1.18 * toArray(null) throws NullPointerException
767 : dl 1.1 */
768 : jsr166 1.18 public void testToArray_NullArg() {
769 : jsr166 1.12 ArrayDeque l = new ArrayDeque();
770 :     l.add(new Object());
771 : jsr166 1.8 try {
772 : jsr166 1.18 l.toArray(null);
773 : jsr166 1.8 shouldThrow();
774 :     } catch (NullPointerException success) {}
775 : dl 1.1 }
776 :    
777 :     /**
778 : jsr166 1.17 * toArray(incompatible array type) throws ArrayStoreException
779 : dl 1.1 */
780 :     public void testToArray1_BadArg() {
781 : jsr166 1.12 ArrayDeque l = new ArrayDeque();
782 :     l.add(new Integer(5));
783 : jsr166 1.8 try {
784 : jsr166 1.17 l.toArray(new String[10]);
785 : jsr166 1.8 shouldThrow();
786 : jsr166 1.9 } catch (ArrayStoreException success) {}
787 : dl 1.1 }
788 : jsr166 1.5
789 : dl 1.1 /**
790 : jsr166 1.16 * Iterator iterates through all elements
791 : dl 1.1 */
792 :     public void testIterator() {
793 :     ArrayDeque q = populatedDeque(SIZE);
794 : jsr166 1.8 Iterator it = q.iterator();
795 : jsr166 1.32 int i;
796 :     for (i = 0; it.hasNext(); i++)
797 : dl 1.1 assertTrue(q.contains(it.next()));
798 :     assertEquals(i, SIZE);
799 : jsr166 1.32 assertIteratorExhausted(it);
800 :     }
801 :    
802 :     /**
803 :     * iterator of empty collection has no elements
804 :     */
805 :     public void testEmptyIterator() {
806 :     Deque c = new ArrayDeque();
807 :     assertIteratorExhausted(c.iterator());
808 :     assertIteratorExhausted(c.descendingIterator());
809 : dl 1.1 }
810 :    
811 :     /**
812 : jsr166 1.16 * Iterator ordering is FIFO
813 : dl 1.1 */
814 :     public void testIteratorOrdering() {
815 :     final ArrayDeque q = new ArrayDeque();
816 : jsr166 1.16 q.add(one);
817 :     q.add(two);
818 :     q.add(three);
819 : dl 1.1 int k = 0;
820 :     for (Iterator it = q.iterator(); it.hasNext();) {
821 : jsr166 1.12 assertEquals(++k, it.next());
822 : dl 1.1 }
823 :    
824 :     assertEquals(3, k);
825 :     }
826 :    
827 :     /**
828 : jsr166 1.16 * iterator.remove() removes current element
829 : dl 1.1 */
830 : jsr166 1.16 public void testIteratorRemove() {
831 : dl 1.1 final ArrayDeque q = new ArrayDeque();
832 : dl 1.4 final Random rng = new Random();
833 : dl 1.3 for (int iters = 0; iters < 100; ++iters) {
834 : dl 1.4 int max = rng.nextInt(5) + 2;
835 : jsr166 1.38 int split = rng.nextInt(max - 1) + 1;
836 : dl 1.4 for (int j = 1; j <= max; ++j)
837 :     q.add(new Integer(j));
838 : dl 1.3 Iterator it = q.iterator();
839 : jsr166 1.5 for (int j = 1; j <= split; ++j)
840 : dl 1.4 assertEquals(it.next(), new Integer(j));
841 : dl 1.3 it.remove();
842 : jsr166 1.38 assertEquals(it.next(), new Integer(split + 1));
843 : jsr166 1.5 for (int j = 1; j <= split; ++j)
844 : dl 1.4 q.remove(new Integer(j));
845 : dl 1.3 it = q.iterator();
846 : jsr166 1.38 for (int j = split + 1; j <= max; ++j) {
847 : dl 1.4 assertEquals(it.next(), new Integer(j));
848 :     it.remove();
849 :     }
850 : dl 1.3 assertFalse(it.hasNext());
851 : dl 1.4 assertTrue(q.isEmpty());
852 : dl 1.3 }
853 : dl 1.1 }
854 :    
855 : dl 1.2 /**
856 : jsr166 1.16 * Descending iterator iterates through all elements
857 : dl 1.2 */
858 :     public void testDescendingIterator() {
859 :     ArrayDeque q = populatedDeque(SIZE);
860 :     int i = 0;
861 : jsr166 1.8 Iterator it = q.descendingIterator();
862 : jsr166 1.6 while (it.hasNext()) {
863 : dl 1.2 assertTrue(q.contains(it.next()));
864 :     ++i;
865 :     }
866 :     assertEquals(i, SIZE);
867 :     assertFalse(it.hasNext());
868 :     try {
869 :     it.next();
870 : jsr166 1.11 shouldThrow();
871 : jsr166 1.9 } catch (NoSuchElementException success) {}
872 : dl 1.2 }
873 :    
874 :     /**
875 : jsr166 1.16 * Descending iterator ordering is reverse FIFO
876 : dl 1.2 */
877 :     public void testDescendingIteratorOrdering() {
878 :     final ArrayDeque q = new ArrayDeque();
879 : dl 1.3 for (int iters = 0; iters < 100; ++iters) {
880 :     q.add(new Integer(3));
881 :     q.add(new Integer(2));
882 :     q.add(new Integer(1));
883 :     int k = 0;
884 :     for (Iterator it = q.descendingIterator(); it.hasNext();) {
885 : jsr166 1.12 assertEquals(++k, it.next());
886 : dl 1.3 }
887 : jsr166 1.5
888 : dl 1.3 assertEquals(3, k);
889 :     q.remove();
890 :     q.remove();
891 :     q.remove();
892 : dl 1.2 }
893 :     }
894 :    
895 :     /**
896 : jsr166 1.16 * descendingIterator.remove() removes current element
897 : dl 1.2 */
898 : jsr166 1.16 public void testDescendingIteratorRemove() {
899 : dl 1.2 final ArrayDeque q = new ArrayDeque();
900 : dl 1.4 final Random rng = new Random();
901 : dl 1.3 for (int iters = 0; iters < 100; ++iters) {
902 : dl 1.4 int max = rng.nextInt(5) + 2;
903 : jsr166 1.38 int split = rng.nextInt(max - 1) + 1;
904 : dl 1.4 for (int j = max; j >= 1; --j)
905 :     q.add(new Integer(j));
906 : dl 1.3 Iterator it = q.descendingIterator();
907 : jsr166 1.5 for (int j = 1; j <= split; ++j)
908 : dl 1.4 assertEquals(it.next(), new Integer(j));
909 : dl 1.3 it.remove();
910 : jsr166 1.38 assertEquals(it.next(), new Integer(split + 1));
911 : jsr166 1.5 for (int j = 1; j <= split; ++j)
912 : dl 1.4 q.remove(new Integer(j));
913 : dl 1.3 it = q.descendingIterator();
914 : jsr166 1.38 for (int j = split + 1; j <= max; ++j) {
915 : dl 1.4 assertEquals(it.next(), new Integer(j));
916 :     it.remove();
917 :     }
918 : dl 1.3 assertFalse(it.hasNext());
919 : dl 1.4 assertTrue(q.isEmpty());
920 : dl 1.3 }
921 : dl 1.2 }
922 :    
923 : dl 1.1 /**
924 : jsr166 1.16 * toString() contains toStrings of elements
925 : dl 1.1 */
926 :     public void testToString() {
927 :     ArrayDeque q = populatedDeque(SIZE);
928 :     String s = q.toString();
929 :     for (int i = 0; i < SIZE; ++i) {
930 : jsr166 1.23 assertTrue(s.contains(String.valueOf(i)));
931 : dl 1.1 }
932 : jsr166 1.5 }
933 : dl 1.1
934 :     /**
935 : jsr166 1.16 * A deserialized serialized deque has same elements in same order
936 : dl 1.1 */
937 : jsr166 1.16 public void testSerialization() throws Exception {
938 : jsr166 1.24 Queue x = populatedDeque(SIZE);
939 :     Queue y = serialClone(x);
940 :    
941 : jsr166 1.28 assertNotSame(y, x);
942 : jsr166 1.24 assertEquals(x.size(), y.size());
943 :     assertEquals(x.toString(), y.toString());
944 :     assertTrue(Arrays.equals(x.toArray(), y.toArray()));
945 :     while (!x.isEmpty()) {
946 :     assertFalse(y.isEmpty());
947 :     assertEquals(x.remove(), y.remove());
948 :     }
949 :     assertTrue(y.isEmpty());
950 : jsr166 1.5 }
951 : dl 1.1
952 : jsr166 1.29 /**
953 :     * remove(null), contains(null) always return false
954 :     */
955 :     public void testNeverContainsNull() {
956 :     Deque<?>[] qs = {
957 :     new ArrayDeque<Object>(),
958 :     populatedDeque(2),
959 :     };
960 :    
961 :     for (Deque<?> q : qs) {
962 :     assertFalse(q.contains(null));
963 :     assertFalse(q.remove(null));
964 :     assertFalse(q.removeFirstOccurrence(null));
965 :     assertFalse(q.removeLastOccurrence(null));
966 :     }
967 :     }
968 :    
969 : dl 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8