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.33 by jsr166, Sun Feb 22 04:34:44 2015 UTC vs.
Revision 1.49 by jsr166, Fri Oct 21 03:24: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.Spliterator;
18 + import java.util.concurrent.ThreadLocalRandom;
19  
20   import junit.framework.Test;
21   import junit.framework.TestSuite;
22  
23   public class ArrayDequeTest extends JSR166TestCase {
24      public static void main(String[] args) {
25 <        junit.textui.TestRunner.run(suite());
25 >        main(suite(), args);
26      }
27  
28      public static Test suite() {
29 <        return new TestSuite(ArrayDequeTest.class);
29 >        class Implementation implements CollectionImplementation {
30 >            public Class<?> klazz() { return ArrayDeque.class; }
31 >            public Collection emptyCollection() { return populatedDeque(0); }
32 >            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      }
39  
40      /**
41       * Returns a new deque of given size containing consecutive
42 <     * Integers 0 ... n.
42 >     * Integers 0 ... n - 1.
43       */
44 <    private ArrayDeque<Integer> populatedDeque(int n) {
45 <        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
44 >    private static ArrayDeque<Integer> populatedDeque(int n) {
45 >        // 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 >        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 >        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 >            assertEquals((Integer) 42, q.removeFirst());
66 >            break;
67 >        case 2: /* do nothing */ break;
68 >        default: throw new AssertionError();
69 >        }
70          assertTrue(q.isEmpty());
71 <        for (int i = 0; i < n; ++i)
72 <            assertTrue(q.offerLast(new Integer(i)));
73 <        assertFalse(q.isEmpty());
71 >        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          assertEquals(n, q.size());
78 +        if (n > 0) {
79 +            assertFalse(q.isEmpty());
80 +            assertEquals((Integer) 0, q.peekFirst());
81 +            assertEquals((Integer) (n - 1), q.peekLast());
82 +        }
83          return q;
84      }
85  
# Line 61 | Line 105 | public class ArrayDequeTest extends JSR1
105       */
106      public void testConstructor4() {
107          try {
108 <            Integer[] ints = new Integer[SIZE];
65 <            new ArrayDeque(Arrays.asList(ints));
108 >            new ArrayDeque(Arrays.asList(new Integer[SIZE]));
109              shouldThrow();
110          } catch (NullPointerException success) {}
111      }
# Line 71 | Line 114 | public class ArrayDequeTest extends JSR1
114       * Initializing from Collection with some null elements throws NPE
115       */
116      public void testConstructor5() {
117 +        Integer[] ints = new Integer[SIZE];
118 +        for (int i = 0; i < SIZE - 1; ++i)
119 +            ints[i] = new Integer(i);
120          try {
75 –            Integer[] ints = new Integer[SIZE];
76 –            for (int i = 0; i < SIZE-1; ++i)
77 –                ints[i] = new Integer(i);
121              new ArrayDeque(Arrays.asList(ints));
122              shouldThrow();
123          } catch (NullPointerException success) {}
# Line 112 | Line 155 | public class ArrayDequeTest extends JSR1
155      public void testSize() {
156          ArrayDeque q = populatedDeque(SIZE);
157          for (int i = 0; i < SIZE; ++i) {
158 <            assertEquals(SIZE-i, q.size());
158 >            assertEquals(SIZE - i, q.size());
159              q.removeFirst();
160          }
161          for (int i = 0; i < SIZE; ++i) {
# Line 125 | Line 168 | public class ArrayDequeTest extends JSR1
168       * push(null) throws NPE
169       */
170      public void testPushNull() {
171 +        ArrayDeque q = new ArrayDeque(1);
172          try {
129 –            ArrayDeque q = new ArrayDeque(1);
173              q.push(null);
174              shouldThrow();
175          } catch (NullPointerException success) {}
# Line 160 | Line 203 | public class ArrayDequeTest extends JSR1
203       * offer(null) throws NPE
204       */
205      public void testOfferNull() {
206 +        ArrayDeque q = new ArrayDeque();
207          try {
164 –            ArrayDeque q = new ArrayDeque();
208              q.offer(null);
209              shouldThrow();
210          } catch (NullPointerException success) {}
# Line 171 | Line 214 | public class ArrayDequeTest extends JSR1
214       * offerFirst(null) throws NPE
215       */
216      public void testOfferFirstNull() {
217 +        ArrayDeque q = new ArrayDeque();
218          try {
175 –            ArrayDeque q = new ArrayDeque();
219              q.offerFirst(null);
220              shouldThrow();
221          } catch (NullPointerException success) {}
# Line 182 | Line 225 | public class ArrayDequeTest extends JSR1
225       * offerLast(null) throws NPE
226       */
227      public void testOfferLastNull() {
228 +        ArrayDeque q = new ArrayDeque();
229          try {
186 –            ArrayDeque q = new ArrayDeque();
230              q.offerLast(null);
231              shouldThrow();
232          } catch (NullPointerException success) {}
# Line 226 | Line 269 | public class ArrayDequeTest extends JSR1
269       * add(null) throws NPE
270       */
271      public void testAddNull() {
272 +        ArrayDeque q = new ArrayDeque();
273          try {
230 –            ArrayDeque q = new ArrayDeque();
274              q.add(null);
275              shouldThrow();
276          } catch (NullPointerException success) {}
# Line 237 | Line 280 | public class ArrayDequeTest extends JSR1
280       * addFirst(null) throws NPE
281       */
282      public void testAddFirstNull() {
283 +        ArrayDeque q = new ArrayDeque();
284          try {
241 –            ArrayDeque q = new ArrayDeque();
285              q.addFirst(null);
286              shouldThrow();
287          } catch (NullPointerException success) {}
# Line 248 | Line 291 | public class ArrayDequeTest extends JSR1
291       * addLast(null) throws NPE
292       */
293      public void testAddLastNull() {
294 +        ArrayDeque q = new ArrayDeque();
295          try {
252 –            ArrayDeque q = new ArrayDeque();
296              q.addLast(null);
297              shouldThrow();
298          } catch (NullPointerException success) {}
# Line 292 | Line 335 | public class ArrayDequeTest extends JSR1
335       * addAll(null) throws NPE
336       */
337      public void testAddAll1() {
338 +        ArrayDeque q = new ArrayDeque();
339          try {
296 –            ArrayDeque q = new ArrayDeque();
340              q.addAll(null);
341              shouldThrow();
342          } catch (NullPointerException success) {}
# Line 303 | Line 346 | public class ArrayDequeTest extends JSR1
346       * addAll of a collection with null elements throws NPE
347       */
348      public void testAddAll2() {
349 +        ArrayDeque q = new ArrayDeque();
350          try {
351 <            ArrayDeque q = new ArrayDeque();
308 <            Integer[] ints = new Integer[SIZE];
309 <            q.addAll(Arrays.asList(ints));
351 >            q.addAll(Arrays.asList(new Integer[SIZE]));
352              shouldThrow();
353          } catch (NullPointerException success) {}
354      }
# Line 316 | Line 358 | public class ArrayDequeTest extends JSR1
358       * possibly adding some elements
359       */
360      public void testAddAll3() {
361 +        ArrayDeque q = new ArrayDeque();
362 +        Integer[] ints = new Integer[SIZE];
363 +        for (int i = 0; i < SIZE - 1; ++i)
364 +            ints[i] = new Integer(i);
365          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);
366              q.addAll(Arrays.asList(ints));
367              shouldThrow();
368          } catch (NullPointerException success) {}
# Line 357 | Line 399 | public class ArrayDequeTest extends JSR1
399       */
400      public void testPollLast() {
401          ArrayDeque q = populatedDeque(SIZE);
402 <        for (int i = SIZE-1; i >= 0; --i) {
402 >        for (int i = SIZE - 1; i >= 0; --i) {
403              assertEquals(i, q.pollLast());
404          }
405          assertNull(q.pollLast());
# Line 397 | Line 439 | public class ArrayDequeTest extends JSR1
439              assertTrue(q.contains(i));
440              assertTrue(q.remove(i));
441              assertFalse(q.contains(i));
442 <            assertTrue(q.contains(i-1));
442 >            assertTrue(q.contains(i - 1));
443          }
444          for (int i = 0; i < SIZE; i += 2) {
445              assertTrue(q.contains(i));
446              assertTrue(q.remove(i));
447              assertFalse(q.contains(i));
448 <            assertFalse(q.remove(i+1));
449 <            assertFalse(q.contains(i+1));
448 >            assertFalse(q.remove(i + 1));
449 >            assertFalse(q.contains(i + 1));
450          }
451          assertTrue(q.isEmpty());
452      }
# Line 442 | Line 484 | public class ArrayDequeTest extends JSR1
484       */
485      public void testPeekLast() {
486          ArrayDeque q = populatedDeque(SIZE);
487 <        for (int i = SIZE-1; i >= 0; --i) {
487 >        for (int i = SIZE - 1; i >= 0; --i) {
488              assertEquals(i, q.peekLast());
489              assertEquals(i, q.pollLast());
490              assertTrue(q.peekLast() == null ||
# Line 486 | Line 528 | public class ArrayDequeTest extends JSR1
528       */
529      public void testLastElement() {
530          ArrayDeque q = populatedDeque(SIZE);
531 <        for (int i = SIZE-1; i >= 0; --i) {
531 >        for (int i = SIZE - 1; i >= 0; --i) {
532              assertEquals(i, q.getLast());
533              assertEquals(i, q.pollLast());
534          }
# Line 532 | Line 574 | public class ArrayDequeTest extends JSR1
574       */
575      public void testRemoveFirstOccurrence() {
576          ArrayDeque q = populatedDeque(SIZE);
577 +        assertFalse(q.removeFirstOccurrence(null));
578          for (int i = 1; i < SIZE; i += 2) {
579              assertTrue(q.removeFirstOccurrence(new Integer(i)));
580          }
581          for (int i = 0; i < SIZE; i += 2) {
582              assertTrue(q.removeFirstOccurrence(new Integer(i)));
583 <            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
583 >            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
584          }
585          assertTrue(q.isEmpty());
586 +        assertFalse(q.removeFirstOccurrence(null));
587 +        assertFalse(q.removeFirstOccurrence(42));
588 +        q = new ArrayDeque();
589 +        assertFalse(q.removeFirstOccurrence(null));
590 +        assertFalse(q.removeFirstOccurrence(42));
591      }
592  
593      /**
# Line 547 | Line 595 | public class ArrayDequeTest extends JSR1
595       */
596      public void testRemoveLastOccurrence() {
597          ArrayDeque q = populatedDeque(SIZE);
598 +        assertFalse(q.removeLastOccurrence(null));
599          for (int i = 1; i < SIZE; i += 2) {
600              assertTrue(q.removeLastOccurrence(new Integer(i)));
601          }
602          for (int i = 0; i < SIZE; i += 2) {
603              assertTrue(q.removeLastOccurrence(new Integer(i)));
604 <            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
604 >            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
605          }
606          assertTrue(q.isEmpty());
607 +        assertFalse(q.removeLastOccurrence(null));
608 +        assertFalse(q.removeLastOccurrence(42));
609 +        q = new ArrayDeque();
610 +        assertFalse(q.removeLastOccurrence(null));
611 +        assertFalse(q.removeLastOccurrence(42));
612      }
613  
614      /**
# Line 607 | Line 661 | public class ArrayDequeTest extends JSR1
661              boolean changed = q.retainAll(p);
662              assertEquals(changed, (i > 0));
663              assertTrue(q.containsAll(p));
664 <            assertEquals(SIZE-i, q.size());
664 >            assertEquals(SIZE - i, q.size());
665              p.removeFirst();
666          }
667      }
# Line 620 | Line 674 | public class ArrayDequeTest extends JSR1
674              ArrayDeque q = populatedDeque(SIZE);
675              ArrayDeque p = populatedDeque(i);
676              assertTrue(q.removeAll(p));
677 <            assertEquals(SIZE-i, q.size());
677 >            assertEquals(SIZE - i, q.size());
678              for (int j = 0; j < i; ++j) {
679                  assertFalse(q.contains(p.removeFirst()));
680              }
# Line 652 | Line 706 | public class ArrayDequeTest extends JSR1
706          for (int i = 0; i < SIZE; i++) {
707              checkToArray(q);
708              assertEquals(i, q.poll());
709 <            q.addLast(SIZE+i);
709 >            q.addLast(SIZE + i);
710          }
711          for (int i = 0; i < SIZE; i++) {
712              checkToArray(q);
713 <            assertEquals(SIZE+i, q.poll());
713 >            assertEquals(SIZE + i, q.poll());
714          }
715      }
716  
717      void checkToArray2(ArrayDeque q) {
718          int size = q.size();
719 <        Integer[] a1 = size == 0 ? null : new Integer[size-1];
719 >        Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
720          Integer[] a2 = new Integer[size];
721 <        Integer[] a3 = new Integer[size+2];
721 >        Integer[] a3 = new Integer[size + 2];
722          if (size > 0) Arrays.fill(a1, 42);
723          Arrays.fill(a2, 42);
724          Arrays.fill(a3, 42);
725 <        Integer[] b1 = size == 0 ? null : (Integer[]) q.toArray(a1);
725 >        Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
726          Integer[] b2 = (Integer[]) q.toArray(a2);
727          Integer[] b3 = (Integer[]) q.toArray(a3);
728          assertSame(a2, b2);
# Line 682 | Line 736 | public class ArrayDequeTest extends JSR1
736              assertSame(b3[i], x);
737          }
738          assertNull(a3[size]);
739 <        assertEquals(42, (int) a3[size+1]);
739 >        assertEquals(42, (int) a3[size + 1]);
740          if (size > 0) {
741              assertNotSame(a1, b1);
742              assertEquals(size, b1.length);
# Line 705 | Line 759 | public class ArrayDequeTest extends JSR1
759          for (int i = 0; i < SIZE; i++) {
760              checkToArray2(q);
761              assertEquals(i, q.poll());
762 <            q.addLast(SIZE+i);
762 >            q.addLast(SIZE + i);
763          }
764          for (int i = 0; i < SIZE; i++) {
765              checkToArray2(q);
766 <            assertEquals(SIZE+i, q.poll());
766 >            assertEquals(SIZE + i, q.poll());
767          }
768      }
769  
# Line 783 | Line 837 | public class ArrayDequeTest extends JSR1
837          final Random rng = new Random();
838          for (int iters = 0; iters < 100; ++iters) {
839              int max = rng.nextInt(5) + 2;
840 <            int split = rng.nextInt(max-1) + 1;
840 >            int split = rng.nextInt(max - 1) + 1;
841              for (int j = 1; j <= max; ++j)
842                  q.add(new Integer(j));
843              Iterator it = q.iterator();
844              for (int j = 1; j <= split; ++j)
845                  assertEquals(it.next(), new Integer(j));
846              it.remove();
847 <            assertEquals(it.next(), new Integer(split+1));
847 >            assertEquals(it.next(), new Integer(split + 1));
848              for (int j = 1; j <= split; ++j)
849                  q.remove(new Integer(j));
850              it = q.iterator();
851 <            for (int j = split+1; j <= max; ++j) {
851 >            for (int j = split + 1; j <= max; ++j) {
852                  assertEquals(it.next(), new Integer(j));
853                  it.remove();
854              }
# Line 851 | Line 905 | public class ArrayDequeTest extends JSR1
905          final Random rng = new Random();
906          for (int iters = 0; iters < 100; ++iters) {
907              int max = rng.nextInt(5) + 2;
908 <            int split = rng.nextInt(max-1) + 1;
908 >            int split = rng.nextInt(max - 1) + 1;
909              for (int j = max; j >= 1; --j)
910                  q.add(new Integer(j));
911              Iterator it = q.descendingIterator();
912              for (int j = 1; j <= split; ++j)
913                  assertEquals(it.next(), new Integer(j));
914              it.remove();
915 <            assertEquals(it.next(), new Integer(split+1));
915 >            assertEquals(it.next(), new Integer(split + 1));
916              for (int j = 1; j <= split; ++j)
917                  q.remove(new Integer(j));
918              it = q.descendingIterator();
919 <            for (int j = split+1; j <= max; ++j) {
919 >            for (int j = split + 1; j <= max; ++j) {
920                  assertEquals(it.next(), new Integer(j));
921                  it.remove();
922              }
# Line 901 | Line 955 | public class ArrayDequeTest extends JSR1
955      }
956  
957      /**
958 +     * 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       * remove(null), contains(null) always return false
977       */
978      public void testNeverContainsNull() {
# Line 917 | Line 989 | public class ArrayDequeTest extends JSR1
989          }
990      }
991  
992 +    /**
993 +     * 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 +        assertTrue(s.hasCharacteristics(required));
1005 +        assertEquals(0, characteristics
1006 +                     & (Spliterator.CONCURRENT
1007 +                        | Spliterator.DISTINCT
1008 +                        | Spliterator.IMMUTABLE
1009 +                        | Spliterator.SORTED));
1010 +    }
1011 +
1012 +    /**
1013 +     * Spliterator.getComparator always throws IllegalStateException
1014 +     */
1015 +    public void testSpliterator_getComparator() {
1016 +        assertThrows(IllegalStateException.class,
1017 +                     () -> new ArrayDeque().spliterator().getComparator());
1018 +    }
1019 +
1020 +    /**
1021 +     * Handle capacities near Integer.MAX_VALUE.
1022 +     * ant -Dvmoptions='-Xms22g -Xmx22g' -Djsr166.testImplementationDetails=true -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ArrayDequeTest -Djsr166.methodFilter=testHuge tck
1023 +     */
1024 +    public void testHuge() {
1025 +        if (! (testImplementationDetails
1026 +               && expensiveTests
1027 +               && Runtime.getRuntime().maxMemory() > 21_000_000_000L))
1028 +            return;
1029 +
1030 +        ArrayDeque q;
1031 +        final int maxSize = Integer.MAX_VALUE - 8;
1032 +
1033 +        assertThrows(OutOfMemoryError.class,
1034 +                     () -> new ArrayDeque<>(Integer.MAX_VALUE));
1035 +
1036 +        {
1037 +            q = new ArrayDeque<>(maxSize);
1038 +            q = null;
1039 +        }
1040 +
1041 +        {
1042 +            q = new ArrayDeque();
1043 +            assertTrue(q.addAll(Collections.nCopies(maxSize - 2, (Integer) 42)));
1044 +            assertEquals((Integer) 42, q.peekFirst());
1045 +            assertEquals((Integer) 42, q.peekLast());
1046 +            assertEquals(maxSize - 2, q.size());
1047 +            q.addFirst((Integer) 0);
1048 +            q.addLast((Integer) 1);
1049 +            assertEquals((Integer) 0, q.peekFirst());
1050 +            assertEquals((Integer) 1, q.peekLast());
1051 +            assertEquals(maxSize, q.size());
1052 +            q = null;
1053 +        }
1054 +    }
1055 +
1056   }

Diff Legend

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