[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.46 - (view) (download)

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8