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

Comparing jsr166/src/test/tck/TreeSetTest.java (file contents):
Revision 1.13 by jsr166, Wed Aug 25 00:07:03 2010 UTC vs.
Revision 1.37 by jsr166, Sat Feb 28 20:13:46 2015 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
4 < * http://creativecommons.org/licenses/publicdomain
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7 < import junit.framework.*;
8 < import java.util.*;
9 < import java.util.concurrent.*;
10 < import java.io.*;
7 > import java.util.Arrays;
8 > import java.util.BitSet;
9 > import java.util.Collection;
10 > import java.util.Comparator;
11 > import java.util.Iterator;
12 > import java.util.NavigableSet;
13 > import java.util.NoSuchElementException;
14 > import java.util.Random;
15 > import java.util.Set;
16 > import java.util.SortedSet;
17 > import java.util.TreeSet;
18 >
19 > import junit.framework.Test;
20 > import junit.framework.TestSuite;
21  
22   public class TreeSetTest extends JSR166TestCase {
23      public static void main(String[] args) {
# Line 29 | Line 39 | public class TreeSetTest extends JSR166T
39      static final int SIZE = 20;
40  
41      /**
42 <     * Create a set of given size containing consecutive
42 >     * Returns a new set of given size containing consecutive
43       * Integers 0 ... n.
44       */
45 <    private TreeSet populatedSet(int n) {
46 <        TreeSet q = new TreeSet();
45 >    private TreeSet<Integer> populatedSet(int n) {
46 >        TreeSet<Integer> q = new TreeSet<Integer>();
47          assertTrue(q.isEmpty());
48 <        for (int i = n-1; i >= 0; i-=2)
48 >        for (int i = n-1; i >= 0; i -= 2)
49              assertTrue(q.add(new Integer(i)));
50 <        for (int i = (n & 1); i < n; i+=2)
50 >        for (int i = (n & 1); i < n; i += 2)
51              assertTrue(q.add(new Integer(i)));
52          assertFalse(q.isEmpty());
53          assertEquals(n, q.size());
# Line 45 | Line 55 | public class TreeSetTest extends JSR166T
55      }
56  
57      /**
58 <     * Create set of first 5 ints
58 >     * Returns a new set of first 5 ints.
59       */
60      private TreeSet set5() {
61          TreeSet q = new TreeSet();
# Line 71 | Line 81 | public class TreeSetTest extends JSR166T
81       */
82      public void testConstructor3() {
83          try {
84 <            TreeSet q = new TreeSet((Collection)null);
84 >            new TreeSet((Collection)null);
85              shouldThrow();
86          } catch (NullPointerException success) {}
87      }
# Line 82 | Line 92 | public class TreeSetTest extends JSR166T
92      public void testConstructor4() {
93          try {
94              Integer[] ints = new Integer[SIZE];
95 <            TreeSet q = new TreeSet(Arrays.asList(ints));
95 >            new TreeSet(Arrays.asList(ints));
96              shouldThrow();
97          } catch (NullPointerException success) {}
98      }
# Line 95 | Line 105 | public class TreeSetTest extends JSR166T
105              Integer[] ints = new Integer[SIZE];
106              for (int i = 0; i < SIZE-1; ++i)
107                  ints[i] = new Integer(i);
108 <            TreeSet q = new TreeSet(Arrays.asList(ints));
108 >            new TreeSet(Arrays.asList(ints));
109              shouldThrow();
110          } catch (NullPointerException success) {}
111      }
# Line 160 | Line 170 | public class TreeSetTest extends JSR166T
170       * add(null) throws NPE if nonempty
171       */
172      public void testAddNull() {
173 +        TreeSet q = populatedSet(SIZE);
174          try {
164 –            TreeSet q = populatedSet(SIZE);
175              q.add(null);
176              shouldThrow();
177          } catch (NullPointerException success) {}
# Line 189 | Line 199 | public class TreeSetTest extends JSR166T
199       * Add of non-Comparable throws CCE
200       */
201      public void testAddNonComparable() {
202 +        TreeSet q = new TreeSet();
203          try {
193 –            TreeSet q = new TreeSet();
194 –            q.add(new Object());
204              q.add(new Object());
205              q.add(new Object());
206              shouldThrow();
# Line 202 | Line 211 | public class TreeSetTest extends JSR166T
211       * addAll(null) throws NPE
212       */
213      public void testAddAll1() {
214 +        TreeSet q = new TreeSet();
215          try {
206 –            TreeSet q = new TreeSet();
216              q.addAll(null);
217              shouldThrow();
218          } catch (NullPointerException success) {}
219      }
220 +
221      /**
222       * addAll of a collection with null elements throws NPE
223       */
224      public void testAddAll2() {
225 +        TreeSet q = new TreeSet();
226 +        Integer[] ints = new Integer[SIZE];
227          try {
216 –            TreeSet q = new TreeSet();
217 –            Integer[] ints = new Integer[SIZE];
228              q.addAll(Arrays.asList(ints));
229              shouldThrow();
230          } catch (NullPointerException success) {}
231      }
232 +
233      /**
234       * addAll of a collection with any null elements throws NPE after
235       * possibly adding some elements
236       */
237      public void testAddAll3() {
238 +        TreeSet q = new TreeSet();
239 +        Integer[] ints = new Integer[SIZE];
240 +        for (int i = 0; i < SIZE-1; ++i)
241 +            ints[i] = new Integer(i);
242          try {
228 –            TreeSet q = new TreeSet();
229 –            Integer[] ints = new Integer[SIZE];
230 –            for (int i = 0; i < SIZE-1; ++i)
231 –                ints[i] = new Integer(i);
243              q.addAll(Arrays.asList(ints));
244              shouldThrow();
245          } catch (NullPointerException success) {}
# Line 271 | Line 282 | public class TreeSetTest extends JSR166T
282          assertNull(q.pollFirst());
283      }
284  
274 –
285      /**
286       * remove(x) removes x and returns true if present
287       */
288      public void testRemoveElement() {
289          TreeSet q = populatedSet(SIZE);
290 <        for (int i = 1; i < SIZE; i+=2) {
291 <            assertTrue(q.remove(new Integer(i)));
292 <        }
293 <        for (int i = 0; i < SIZE; i+=2) {
294 <            assertTrue(q.remove(new Integer(i)));
295 <            assertFalse(q.remove(new Integer(i+1)));
290 >        for (int i = 1; i < SIZE; i += 2) {
291 >            assertTrue(q.contains(i));
292 >            assertTrue(q.remove(i));
293 >            assertFalse(q.contains(i));
294 >            assertTrue(q.contains(i-1));
295 >        }
296 >        for (int i = 0; i < SIZE; i += 2) {
297 >            assertTrue(q.contains(i));
298 >            assertTrue(q.remove(i));
299 >            assertFalse(q.contains(i));
300 >            assertFalse(q.remove(i+1));
301 >            assertFalse(q.contains(i+1));
302          }
303          assertTrue(q.isEmpty());
304      }
# Line 356 | Line 372 | public class TreeSetTest extends JSR166T
372              assertTrue(q.removeAll(p));
373              assertEquals(SIZE-i, q.size());
374              for (int j = 0; j < i; ++j) {
375 <                Integer I = (Integer)(p.pollFirst());
376 <                assertFalse(q.contains(I));
375 >                Integer x = (Integer)(p.pollFirst());
376 >                assertFalse(q.contains(x));
377              }
378          }
379      }
380  
365 –
366 –
381      /**
382       * lower returns preceding element
383       */
# Line 437 | Line 451 | public class TreeSetTest extends JSR166T
451      }
452  
453      /**
454 <     * toArray contains all elements
454 >     * toArray contains all elements in sorted order
455       */
456      public void testToArray() {
457          TreeSet q = populatedSet(SIZE);
458          Object[] o = q.toArray();
445 –        Arrays.sort(o);
459          for (int i = 0; i < o.length; i++)
460 <            assertEquals(o[i], q.pollFirst());
460 >            assertSame(o[i], q.pollFirst());
461      }
462  
463      /**
464 <     * toArray(a) contains all elements
464 >     * toArray(a) contains all elements in sorted order
465       */
466      public void testToArray2() {
467 <        TreeSet q = populatedSet(SIZE);
467 >        TreeSet<Integer> q = populatedSet(SIZE);
468          Integer[] ints = new Integer[SIZE];
469 <        ints = (Integer[])q.toArray(ints);
470 <        Arrays.sort(ints);
469 >        Integer[] array = q.toArray(ints);
470 >        assertSame(ints, array);
471          for (int i = 0; i < ints.length; i++)
472 <            assertEquals(ints[i], q.pollFirst());
472 >            assertSame(ints[i], q.pollFirst());
473      }
474  
475      /**
# Line 464 | Line 477 | public class TreeSetTest extends JSR166T
477       */
478      public void testIterator() {
479          TreeSet q = populatedSet(SIZE);
467 –        int i = 0;
480          Iterator it = q.iterator();
481 <        while (it.hasNext()) {
481 >        int i;
482 >        for (i = 0; it.hasNext(); i++)
483              assertTrue(q.contains(it.next()));
471 –            ++i;
472 –        }
484          assertEquals(i, SIZE);
485 +        assertIteratorExhausted(it);
486      }
487  
488      /**
489       * iterator of empty set has no elements
490       */
491      public void testEmptyIterator() {
492 <        TreeSet q = new TreeSet();
481 <        int i = 0;
482 <        Iterator it = q.iterator();
483 <        while (it.hasNext()) {
484 <            assertTrue(q.contains(it.next()));
485 <            ++i;
486 <        }
487 <        assertEquals(i, 0);
492 >        assertIteratorExhausted(new TreeSet().iterator());
493      }
494  
495      /**
# Line 506 | Line 511 | public class TreeSetTest extends JSR166T
511          assertFalse(it.hasNext());
512      }
513  
509 –
514      /**
515       * toString contains toStrings of elements
516       */
# Line 514 | Line 518 | public class TreeSetTest extends JSR166T
518          TreeSet q = populatedSet(SIZE);
519          String s = q.toString();
520          for (int i = 0; i < SIZE; ++i) {
521 <            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
521 >            assertTrue(s.contains(String.valueOf(i)));
522          }
523      }
524  
# Line 522 | Line 526 | public class TreeSetTest extends JSR166T
526       * A deserialized serialized set has same elements
527       */
528      public void testSerialization() throws Exception {
529 <        TreeSet q = populatedSet(SIZE);
530 <        ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
531 <        ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
532 <        out.writeObject(q);
533 <        out.close();
534 <
535 <        ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
536 <        ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
537 <        TreeSet r = (TreeSet)in.readObject();
538 <        assertEquals(q.size(), r.size());
539 <        while (!q.isEmpty())
540 <            assertEquals(q.pollFirst(), r.pollFirst());
529 >        NavigableSet x = populatedSet(SIZE);
530 >        NavigableSet y = serialClone(x);
531 >
532 >        assertNotSame(x, y);
533 >        assertEquals(x.size(), y.size());
534 >        assertEquals(x, y);
535 >        assertEquals(y, x);
536 >        while (!x.isEmpty()) {
537 >            assertFalse(y.isEmpty());
538 >            assertEquals(x.pollFirst(), y.pollFirst());
539 >        }
540 >        assertTrue(y.isEmpty());
541      }
542  
543      /**
# Line 662 | Line 666 | public class TreeSetTest extends JSR166T
666       * Subsets of subsets subdivide correctly
667       */
668      public void testRecursiveSubSets() throws Exception {
669 <        int setSize = 1000;
669 >        int setSize = expensiveTests ? 1000 : 100;
670          Class cl = TreeSet.class;
671  
672          NavigableSet<Integer> set = newSet(cl);
# Line 680 | Line 684 | public class TreeSetTest extends JSR166T
684                     0, setSize - 1, true);
685      }
686  
687 +    /**
688 +     * addAll is idempotent
689 +     */
690 +    public void testAddAll_idempotent() throws Exception {
691 +        Set x = populatedSet(SIZE);
692 +        Set y = new TreeSet(x);
693 +        y.addAll(x);
694 +        assertEquals(x, y);
695 +        assertEquals(y, x);
696 +    }
697 +
698      static NavigableSet<Integer> newSet(Class cl) throws Exception {
699          NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
700 <        assertEquals(result.size(), 0);
700 >        assertEquals(0, result.size());
701          assertFalse(result.iterator().hasNext());
702          return result;
703      }
# Line 714 | Line 729 | public class TreeSetTest extends JSR166T
729          // Add entries till we're back to original size
730          while (set.size() < size) {
731              int element = min + rnd.nextInt(rangeSize);
732 <            assertTrue(element >= min && element<= max);
732 >            assertTrue(element >= min && element <= max);
733              put(set, element);
734          }
735      }
# Line 739 | Line 754 | public class TreeSetTest extends JSR166T
754          // Add entries till we're back to original size
755          while (set.size() < size) {
756              int element = min - 5 + rnd.nextInt(rangeSize + 10);
757 <            if (element >= min && element<= max) {
757 >            if (element >= min && element <= max) {
758                  put(set, element);
759              } else {
760                  try {
# Line 843 | Line 858 | public class TreeSetTest extends JSR166T
858       */
859      void check(NavigableSet<Integer> set,
860                        final int min, final int max, final boolean ascending) {
861 <       class ReferenceSet {
861 >        class ReferenceSet {
862              int lower(int element) {
863                  return ascending ?
864                      lowerAscending(element) : higherAscending(element);
# Line 878 | Line 893 | public class TreeSetTest extends JSR166T
893                  // BitSet should support this! Test would run much faster
894                  while (element >= min) {
895                      if (bs.get(element))
896 <                        return(element);
896 >                        return element;
897                      element--;
898                  }
899                  return -1;
# Line 913 | Line 928 | public class TreeSetTest extends JSR166T
928              if (bsContainsI)
929                  size++;
930          }
931 <        assertEquals(set.size(), size);
931 >        assertEquals(size, set.size());
932  
933          // Test contents using contains elementSet iterator
934          int size2 = 0;

Diff Legend

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