ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ArrayDequeTest.java
(Generate patch)

Comparing jsr166/src/test/tck/ArrayDequeTest.java (file contents):
Revision 1.34 by jsr166, Sat Apr 25 04:55:30 2015 UTC vs.
Revision 1.45 by jsr166, Mon Oct 17 01:57:00 2016 UTC

# Line 1 | Line 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
2 > * 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   * http://creativecommons.org/publicdomain/zero/1.0/
6   */
7  
8   import java.util.ArrayDeque;
9   import java.util.Arrays;
10   import java.util.Collection;
11 + import java.util.Collections;
12   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 + import java.util.concurrent.ThreadLocalRandom;
18  
19   import junit.framework.Test;
20   import junit.framework.TestSuite;
# Line 22 | Line 25 | public class ArrayDequeTest extends JSR1
25      }
26  
27      public static Test suite() {
28 <        return new TestSuite(ArrayDequeTest.class);
28 >        class Implementation implements CollectionImplementation {
29 >            public Class<?> klazz() { return ArrayDeque.class; }
30 >            public Collection emptyCollection() { return populatedDeque(0); }
31 >            public Object makeElement(int i) { return i; }
32 >            public boolean isConcurrent() { return false; }
33 >            public boolean permitsNulls() { return false; }
34 >        }
35 >        return newTestSuite(ArrayDequeTest.class,
36 >                            CollectionTest.testSuite(new Implementation()));
37      }
38  
39      /**
40       * Returns a new deque of given size containing consecutive
41 <     * Integers 0 ... n.
41 >     * Integers 0 ... n - 1.
42       */
43 <    private ArrayDeque<Integer> populatedDeque(int n) {
44 <        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
43 >    private static ArrayDeque<Integer> populatedDeque(int n) {
44 >        // Randomize various aspects of memory layout, including
45 >        // filled-to-capacity and wraparound.
46 >        final ArrayDeque<Integer> q;
47 >        ThreadLocalRandom rnd = ThreadLocalRandom.current();
48 >        switch (rnd.nextInt(6)) {
49 >        case 0: q = new ArrayDeque<Integer>();      break;
50 >        case 1: q = new ArrayDeque<Integer>(0);     break;
51 >        case 2: q = new ArrayDeque<Integer>(1);     break;
52 >        case 3: q = new ArrayDeque<Integer>(Math.max(0, n - 1)); break;
53 >        case 4: q = new ArrayDeque<Integer>(n);     break;
54 >        case 5: q = new ArrayDeque<Integer>(n + 1); break;
55 >        default: throw new AssertionError();
56 >        }
57 >        switch (rnd.nextInt(3)) {
58 >        case 0:
59 >            q.addFirst(42);
60 >            assertEquals((Integer) 42, q.removeLast());
61 >            break;
62 >        case 1:
63 >            q.addLast(42);
64 >            assertEquals((Integer) 42, q.removeFirst());
65 >            break;
66 >        case 2: /* do nothing */ break;
67 >        default: throw new AssertionError();
68 >        }
69          assertTrue(q.isEmpty());
70 <        for (int i = 0; i < n; ++i)
71 <            assertTrue(q.offerLast(new Integer(i)));
72 <        assertFalse(q.isEmpty());
70 >        if (rnd.nextBoolean())
71 >            for (int i = 0; i < n; i++)
72 >                assertTrue(q.offerLast((Integer) i));
73 >        else
74 >            for (int i = n; --i >= 0; )
75 >                q.addFirst((Integer) i);
76          assertEquals(n, q.size());
77 +        if (n > 0) {
78 +            assertFalse(q.isEmpty());
79 +            assertEquals((Integer) 0, q.peekFirst());
80 +            assertEquals((Integer) (n - 1), q.peekLast());
81 +        }
82          return q;
83      }
84  
# Line 61 | Line 104 | public class ArrayDequeTest extends JSR1
104       */
105      public void testConstructor4() {
106          try {
107 <            Integer[] ints = new Integer[SIZE];
65 <            new ArrayDeque(Arrays.asList(ints));
107 >            new ArrayDeque(Arrays.asList(new Integer[SIZE]));
108              shouldThrow();
109          } catch (NullPointerException success) {}
110      }
# Line 71 | Line 113 | public class ArrayDequeTest extends JSR1
113       * Initializing from Collection with some null elements throws NPE
114       */
115      public void testConstructor5() {
116 +        Integer[] ints = new Integer[SIZE];
117 +        for (int i = 0; i < SIZE - 1; ++i)
118 +            ints[i] = new Integer(i);
119          try {
75 –            Integer[] ints = new Integer[SIZE];
76 –            for (int i = 0; i < SIZE-1; ++i)
77 –                ints[i] = new Integer(i);
120              new ArrayDeque(Arrays.asList(ints));
121              shouldThrow();
122          } catch (NullPointerException success) {}
# Line 112 | Line 154 | public class ArrayDequeTest extends JSR1
154      public void testSize() {
155          ArrayDeque q = populatedDeque(SIZE);
156          for (int i = 0; i < SIZE; ++i) {
157 <            assertEquals(SIZE-i, q.size());
157 >            assertEquals(SIZE - i, q.size());
158              q.removeFirst();
159          }
160          for (int i = 0; i < SIZE; ++i) {
# Line 125 | Line 167 | public class ArrayDequeTest extends JSR1
167       * push(null) throws NPE
168       */
169      public void testPushNull() {
170 +        ArrayDeque q = new ArrayDeque(1);
171          try {
129 –            ArrayDeque q = new ArrayDeque(1);
172              q.push(null);
173              shouldThrow();
174          } catch (NullPointerException success) {}
# Line 160 | Line 202 | public class ArrayDequeTest extends JSR1
202       * offer(null) throws NPE
203       */
204      public void testOfferNull() {
205 +        ArrayDeque q = new ArrayDeque();
206          try {
164 –            ArrayDeque q = new ArrayDeque();
207              q.offer(null);
208              shouldThrow();
209          } catch (NullPointerException success) {}
# Line 171 | Line 213 | public class ArrayDequeTest extends JSR1
213       * offerFirst(null) throws NPE
214       */
215      public void testOfferFirstNull() {
216 +        ArrayDeque q = new ArrayDeque();
217          try {
175 –            ArrayDeque q = new ArrayDeque();
218              q.offerFirst(null);
219              shouldThrow();
220          } catch (NullPointerException success) {}
# Line 182 | Line 224 | public class ArrayDequeTest extends JSR1
224       * offerLast(null) throws NPE
225       */
226      public void testOfferLastNull() {
227 +        ArrayDeque q = new ArrayDeque();
228          try {
186 –            ArrayDeque q = new ArrayDeque();
229              q.offerLast(null);
230              shouldThrow();
231          } catch (NullPointerException success) {}
# Line 226 | Line 268 | public class ArrayDequeTest extends JSR1
268       * add(null) throws NPE
269       */
270      public void testAddNull() {
271 +        ArrayDeque q = new ArrayDeque();
272          try {
230 –            ArrayDeque q = new ArrayDeque();
273              q.add(null);
274              shouldThrow();
275          } catch (NullPointerException success) {}
# Line 237 | Line 279 | public class ArrayDequeTest extends JSR1
279       * addFirst(null) throws NPE
280       */
281      public void testAddFirstNull() {
282 +        ArrayDeque q = new ArrayDeque();
283          try {
241 –            ArrayDeque q = new ArrayDeque();
284              q.addFirst(null);
285              shouldThrow();
286          } catch (NullPointerException success) {}
# Line 248 | Line 290 | public class ArrayDequeTest extends JSR1
290       * addLast(null) throws NPE
291       */
292      public void testAddLastNull() {
293 +        ArrayDeque q = new ArrayDeque();
294          try {
252 –            ArrayDeque q = new ArrayDeque();
295              q.addLast(null);
296              shouldThrow();
297          } catch (NullPointerException success) {}
# Line 292 | Line 334 | public class ArrayDequeTest extends JSR1
334       * addAll(null) throws NPE
335       */
336      public void testAddAll1() {
337 +        ArrayDeque q = new ArrayDeque();
338          try {
296 –            ArrayDeque q = new ArrayDeque();
339              q.addAll(null);
340              shouldThrow();
341          } catch (NullPointerException success) {}
# Line 303 | Line 345 | public class ArrayDequeTest extends JSR1
345       * addAll of a collection with null elements throws NPE
346       */
347      public void testAddAll2() {
348 +        ArrayDeque q = new ArrayDeque();
349          try {
350 <            ArrayDeque q = new ArrayDeque();
308 <            Integer[] ints = new Integer[SIZE];
309 <            q.addAll(Arrays.asList(ints));
350 >            q.addAll(Arrays.asList(new Integer[SIZE]));
351              shouldThrow();
352          } catch (NullPointerException success) {}
353      }
# Line 316 | Line 357 | public class ArrayDequeTest extends JSR1
357       * possibly adding some elements
358       */
359      public void testAddAll3() {
360 +        ArrayDeque q = new ArrayDeque();
361 +        Integer[] ints = new Integer[SIZE];
362 +        for (int i = 0; i < SIZE - 1; ++i)
363 +            ints[i] = new Integer(i);
364          try {
320 –            ArrayDeque q = new ArrayDeque();
321 –            Integer[] ints = new Integer[SIZE];
322 –            for (int i = 0; i < SIZE-1; ++i)
323 –                ints[i] = new Integer(i);
365              q.addAll(Arrays.asList(ints));
366              shouldThrow();
367          } catch (NullPointerException success) {}
# Line 357 | Line 398 | public class ArrayDequeTest extends JSR1
398       */
399      public void testPollLast() {
400          ArrayDeque q = populatedDeque(SIZE);
401 <        for (int i = SIZE-1; i >= 0; --i) {
401 >        for (int i = SIZE - 1; i >= 0; --i) {
402              assertEquals(i, q.pollLast());
403          }
404          assertNull(q.pollLast());
# Line 397 | Line 438 | public class ArrayDequeTest extends JSR1
438              assertTrue(q.contains(i));
439              assertTrue(q.remove(i));
440              assertFalse(q.contains(i));
441 <            assertTrue(q.contains(i-1));
441 >            assertTrue(q.contains(i - 1));
442          }
443          for (int i = 0; i < SIZE; i += 2) {
444              assertTrue(q.contains(i));
445              assertTrue(q.remove(i));
446              assertFalse(q.contains(i));
447 <            assertFalse(q.remove(i+1));
448 <            assertFalse(q.contains(i+1));
447 >            assertFalse(q.remove(i + 1));
448 >            assertFalse(q.contains(i + 1));
449          }
450          assertTrue(q.isEmpty());
451      }
# Line 442 | Line 483 | public class ArrayDequeTest extends JSR1
483       */
484      public void testPeekLast() {
485          ArrayDeque q = populatedDeque(SIZE);
486 <        for (int i = SIZE-1; i >= 0; --i) {
486 >        for (int i = SIZE - 1; i >= 0; --i) {
487              assertEquals(i, q.peekLast());
488              assertEquals(i, q.pollLast());
489              assertTrue(q.peekLast() == null ||
# Line 486 | Line 527 | public class ArrayDequeTest extends JSR1
527       */
528      public void testLastElement() {
529          ArrayDeque q = populatedDeque(SIZE);
530 <        for (int i = SIZE-1; i >= 0; --i) {
530 >        for (int i = SIZE - 1; i >= 0; --i) {
531              assertEquals(i, q.getLast());
532              assertEquals(i, q.pollLast());
533          }
# Line 532 | Line 573 | public class ArrayDequeTest extends JSR1
573       */
574      public void testRemoveFirstOccurrence() {
575          ArrayDeque q = populatedDeque(SIZE);
576 +        assertFalse(q.removeFirstOccurrence(null));
577          for (int i = 1; i < SIZE; i += 2) {
578              assertTrue(q.removeFirstOccurrence(new Integer(i)));
579          }
580          for (int i = 0; i < SIZE; i += 2) {
581              assertTrue(q.removeFirstOccurrence(new Integer(i)));
582 <            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
582 >            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
583          }
584          assertTrue(q.isEmpty());
585 +        assertFalse(q.removeFirstOccurrence(null));
586 +        assertFalse(q.removeFirstOccurrence(42));
587 +        q = new ArrayDeque();
588 +        assertFalse(q.removeFirstOccurrence(null));
589 +        assertFalse(q.removeFirstOccurrence(42));
590      }
591  
592      /**
# Line 547 | Line 594 | public class ArrayDequeTest extends JSR1
594       */
595      public void testRemoveLastOccurrence() {
596          ArrayDeque q = populatedDeque(SIZE);
597 +        assertFalse(q.removeLastOccurrence(null));
598          for (int i = 1; i < SIZE; i += 2) {
599              assertTrue(q.removeLastOccurrence(new Integer(i)));
600          }
601          for (int i = 0; i < SIZE; i += 2) {
602              assertTrue(q.removeLastOccurrence(new Integer(i)));
603 <            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
603 >            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
604          }
605          assertTrue(q.isEmpty());
606 +        assertFalse(q.removeLastOccurrence(null));
607 +        assertFalse(q.removeLastOccurrence(42));
608 +        q = new ArrayDeque();
609 +        assertFalse(q.removeLastOccurrence(null));
610 +        assertFalse(q.removeLastOccurrence(42));
611      }
612  
613      /**
# Line 607 | Line 660 | public class ArrayDequeTest extends JSR1
660              boolean changed = q.retainAll(p);
661              assertEquals(changed, (i > 0));
662              assertTrue(q.containsAll(p));
663 <            assertEquals(SIZE-i, q.size());
663 >            assertEquals(SIZE - i, q.size());
664              p.removeFirst();
665          }
666      }
# Line 620 | Line 673 | public class ArrayDequeTest extends JSR1
673              ArrayDeque q = populatedDeque(SIZE);
674              ArrayDeque p = populatedDeque(i);
675              assertTrue(q.removeAll(p));
676 <            assertEquals(SIZE-i, q.size());
676 >            assertEquals(SIZE - i, q.size());
677              for (int j = 0; j < i; ++j) {
678                  assertFalse(q.contains(p.removeFirst()));
679              }
# Line 652 | Line 705 | public class ArrayDequeTest extends JSR1
705          for (int i = 0; i < SIZE; i++) {
706              checkToArray(q);
707              assertEquals(i, q.poll());
708 <            q.addLast(SIZE+i);
708 >            q.addLast(SIZE + i);
709          }
710          for (int i = 0; i < SIZE; i++) {
711              checkToArray(q);
712 <            assertEquals(SIZE+i, q.poll());
712 >            assertEquals(SIZE + i, q.poll());
713          }
714      }
715  
716      void checkToArray2(ArrayDeque q) {
717          int size = q.size();
718 <        Integer[] a1 = size == 0 ? null : new Integer[size-1];
718 >        Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
719          Integer[] a2 = new Integer[size];
720 <        Integer[] a3 = new Integer[size+2];
720 >        Integer[] a3 = new Integer[size + 2];
721          if (size > 0) Arrays.fill(a1, 42);
722          Arrays.fill(a2, 42);
723          Arrays.fill(a3, 42);
724 <        Integer[] b1 = size == 0 ? null : (Integer[]) q.toArray(a1);
724 >        Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
725          Integer[] b2 = (Integer[]) q.toArray(a2);
726          Integer[] b3 = (Integer[]) q.toArray(a3);
727          assertSame(a2, b2);
# Line 682 | Line 735 | public class ArrayDequeTest extends JSR1
735              assertSame(b3[i], x);
736          }
737          assertNull(a3[size]);
738 <        assertEquals(42, (int) a3[size+1]);
738 >        assertEquals(42, (int) a3[size + 1]);
739          if (size > 0) {
740              assertNotSame(a1, b1);
741              assertEquals(size, b1.length);
# Line 705 | Line 758 | public class ArrayDequeTest extends JSR1
758          for (int i = 0; i < SIZE; i++) {
759              checkToArray2(q);
760              assertEquals(i, q.poll());
761 <            q.addLast(SIZE+i);
761 >            q.addLast(SIZE + i);
762          }
763          for (int i = 0; i < SIZE; i++) {
764              checkToArray2(q);
765 <            assertEquals(SIZE+i, q.poll());
765 >            assertEquals(SIZE + i, q.poll());
766          }
767      }
768  
# Line 783 | Line 836 | public class ArrayDequeTest extends JSR1
836          final Random rng = new Random();
837          for (int iters = 0; iters < 100; ++iters) {
838              int max = rng.nextInt(5) + 2;
839 <            int split = rng.nextInt(max-1) + 1;
839 >            int split = rng.nextInt(max - 1) + 1;
840              for (int j = 1; j <= max; ++j)
841                  q.add(new Integer(j));
842              Iterator it = q.iterator();
843              for (int j = 1; j <= split; ++j)
844                  assertEquals(it.next(), new Integer(j));
845              it.remove();
846 <            assertEquals(it.next(), new Integer(split+1));
846 >            assertEquals(it.next(), new Integer(split + 1));
847              for (int j = 1; j <= split; ++j)
848                  q.remove(new Integer(j));
849              it = q.iterator();
850 <            for (int j = split+1; j <= max; ++j) {
850 >            for (int j = split + 1; j <= max; ++j) {
851                  assertEquals(it.next(), new Integer(j));
852                  it.remove();
853              }
# Line 851 | Line 904 | public class ArrayDequeTest extends JSR1
904          final Random rng = new Random();
905          for (int iters = 0; iters < 100; ++iters) {
906              int max = rng.nextInt(5) + 2;
907 <            int split = rng.nextInt(max-1) + 1;
907 >            int split = rng.nextInt(max - 1) + 1;
908              for (int j = max; j >= 1; --j)
909                  q.add(new Integer(j));
910              Iterator it = q.descendingIterator();
911              for (int j = 1; j <= split; ++j)
912                  assertEquals(it.next(), new Integer(j));
913              it.remove();
914 <            assertEquals(it.next(), new Integer(split+1));
914 >            assertEquals(it.next(), new Integer(split + 1));
915              for (int j = 1; j <= split; ++j)
916                  q.remove(new Integer(j));
917              it = q.descendingIterator();
918 <            for (int j = split+1; j <= max; ++j) {
918 >            for (int j = split + 1; j <= max; ++j) {
919                  assertEquals(it.next(), new Integer(j));
920                  it.remove();
921              }
# Line 901 | Line 954 | public class ArrayDequeTest extends JSR1
954      }
955  
956      /**
957 +     * A cloned deque has same elements in same order
958 +     */
959 +    public void testClone() throws Exception {
960 +        ArrayDeque<Integer> x = populatedDeque(SIZE);
961 +        ArrayDeque<Integer> y = x.clone();
962 +
963 +        assertNotSame(y, x);
964 +        assertEquals(x.size(), y.size());
965 +        assertEquals(x.toString(), y.toString());
966 +        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
967 +        while (!x.isEmpty()) {
968 +            assertFalse(y.isEmpty());
969 +            assertEquals(x.remove(), y.remove());
970 +        }
971 +        assertTrue(y.isEmpty());
972 +    }
973 +
974 +    /**
975       * remove(null), contains(null) always return false
976       */
977      public void testNeverContainsNull() {
# Line 917 | Line 988 | public class ArrayDequeTest extends JSR1
988          }
989      }
990  
991 +    /**
992 +     * Handle capacities near Integer.MAX_VALUE.
993 +     * ant -Dvmoptions=-Xmx24g -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ArrayDequeTest -Djsr166.methodFilter=testHuge tck
994 +     */
995 +    public void testHuge() {
996 +        if (! (testImplementationDetails
997 +               && expensiveTests
998 +               && Runtime.getRuntime().freeMemory() > 21_000_000_000L))
999 +            return;
1000 +        int maxSize = Integer.MAX_VALUE - 8;
1001 +        ArrayDeque<Integer> q;
1002 +
1003 +        q = new ArrayDeque<>(maxSize);
1004 +
1005 +        assertThrows(OutOfMemoryError.class,
1006 +                     () -> new ArrayDeque<>(Integer.MAX_VALUE));
1007 +
1008 +        q = populatedDeque(0);
1009 +        q.addAll(Collections.nCopies(maxSize - 2, (Integer) 42));
1010 +        assertEquals((Integer) 42, q.peekFirst());
1011 +        assertEquals((Integer) 42, q.peekLast());
1012 +        assertEquals(maxSize - 2, q.size());
1013 +        q.addFirst((Integer) 0);
1014 +        q.addLast((Integer) 1);
1015 +        assertEquals((Integer) 0, q.peekFirst());
1016 +        assertEquals((Integer) 1, q.peekLast());
1017 +        assertEquals(maxSize, q.size());
1018 +    }
1019 +
1020   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines