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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8