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.8 by jsr166, Sat Nov 21 10:25:05 2009 UTC vs.
Revision 1.25 by jsr166, Sat Nov 26 05:42:14 2011 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.*;
8 > import java.util.Arrays;
9 > import java.util.BitSet;
10 > import java.util.Collection;
11 > import java.util.Comparator;
12 > import java.util.Iterator;
13 > import java.util.NavigableSet;
14 > import java.util.NoSuchElementException;
15 > import java.util.Random;
16 > import java.util.Set;
17 > import java.util.SortedSet;
18 > import java.util.TreeSet;
19  
20   public class TreeSetTest extends JSR166TestCase {
21      public static void main(String[] args) {
22 <        junit.textui.TestRunner.run (suite());
22 >        junit.textui.TestRunner.run(suite());
23      }
24      public static Test suite() {
25          return new TestSuite(TreeSetTest.class);
# Line 19 | Line 27 | public class TreeSetTest extends JSR166T
27  
28      static class MyReverseComparator implements Comparator {
29          public int compare(Object x, Object y) {
30 <            int i = ((Integer)x).intValue();
23 <            int j = ((Integer)y).intValue();
24 <            if (i < j) return 1;
25 <            if (i > j) return -1;
26 <            return 0;
30 >            return ((Comparable)y).compareTo(x);
31          }
32      }
33  
# Line 36 | Line 40 | public class TreeSetTest extends JSR166T
40       * Create a set of given size containing consecutive
41       * Integers 0 ... n.
42       */
43 <    private TreeSet populatedSet(int n) {
44 <        TreeSet q = new TreeSet();
43 >    private TreeSet<Integer> populatedSet(int n) {
44 >        TreeSet<Integer> q = new TreeSet<Integer>();
45          assertTrue(q.isEmpty());
46          for (int i = n-1; i >= 0; i-=2)
47              assertTrue(q.add(new Integer(i)));
# Line 108 | Line 112 | public class TreeSetTest extends JSR166T
112       * Set contains all elements of collection used to initialize
113       */
114      public void testConstructor6() {
115 <        try {
116 <            Integer[] ints = new Integer[SIZE];
117 <            for (int i = 0; i < SIZE; ++i)
118 <                ints[i] = new Integer(i);
119 <            TreeSet q = new TreeSet(Arrays.asList(ints));
120 <            for (int i = 0; i < SIZE; ++i)
117 <                assertEquals(ints[i], q.pollFirst());
118 <        }
119 <        finally {}
115 >        Integer[] ints = new Integer[SIZE];
116 >        for (int i = 0; i < SIZE; ++i)
117 >            ints[i] = new Integer(i);
118 >        TreeSet q = new TreeSet(Arrays.asList(ints));
119 >        for (int i = 0; i < SIZE; ++i)
120 >            assertEquals(ints[i], q.pollFirst());
121      }
122  
123      /**
124       * The comparator used in constructor is used
125       */
126      public void testConstructor7() {
127 <        try {
128 <            MyReverseComparator cmp = new MyReverseComparator();
129 <            TreeSet q = new TreeSet(cmp);
130 <            assertEquals(cmp, q.comparator());
131 <            Integer[] ints = new Integer[SIZE];
132 <            for (int i = 0; i < SIZE; ++i)
133 <                ints[i] = new Integer(i);
134 <            q.addAll(Arrays.asList(ints));
135 <            for (int i = SIZE-1; i >= 0; --i)
135 <                assertEquals(ints[i], q.pollFirst());
136 <        }
137 <        finally {}
127 >        MyReverseComparator cmp = new MyReverseComparator();
128 >        TreeSet q = new TreeSet(cmp);
129 >        assertEquals(cmp, q.comparator());
130 >        Integer[] ints = new Integer[SIZE];
131 >        for (int i = 0; i < SIZE; ++i)
132 >            ints[i] = new Integer(i);
133 >        q.addAll(Arrays.asList(ints));
134 >        for (int i = SIZE-1; i >= 0; --i)
135 >            assertEquals(ints[i], q.pollFirst());
136      }
137  
138      /**
# Line 218 | Line 216 | public class TreeSetTest extends JSR166T
216              shouldThrow();
217          } catch (NullPointerException success) {}
218      }
219 +
220      /**
221       * addAll of a collection with null elements throws NPE
222       */
# Line 229 | Line 228 | public class TreeSetTest extends JSR166T
228              shouldThrow();
229          } catch (NullPointerException success) {}
230      }
231 +
232      /**
233       * addAll of a collection with any null elements throws NPE after
234       * possibly adding some elements
# Line 248 | Line 248 | public class TreeSetTest extends JSR166T
248       * Set contains all elements of successful addAll
249       */
250      public void testAddAll5() {
251 <        try {
252 <            Integer[] empty = new Integer[0];
253 <            Integer[] ints = new Integer[SIZE];
254 <            for (int i = 0; i < SIZE; ++i)
255 <                ints[i] = new Integer(SIZE-1-i);
256 <            TreeSet q = new TreeSet();
257 <            assertFalse(q.addAll(Arrays.asList(empty)));
258 <            assertTrue(q.addAll(Arrays.asList(ints)));
259 <            for (int i = 0; i < SIZE; ++i)
260 <                assertEquals(new Integer(i), q.pollFirst());
261 <        }
262 <        finally {}
251 >        Integer[] empty = new Integer[0];
252 >        Integer[] ints = new Integer[SIZE];
253 >        for (int i = 0; i < SIZE; ++i)
254 >            ints[i] = new Integer(SIZE-1-i);
255 >        TreeSet q = new TreeSet();
256 >        assertFalse(q.addAll(Arrays.asList(empty)));
257 >        assertTrue(q.addAll(Arrays.asList(ints)));
258 >        for (int i = 0; i < SIZE; ++i)
259 >            assertEquals(new Integer(i), q.pollFirst());
260      }
261  
262      /**
# Line 268 | Line 265 | public class TreeSetTest extends JSR166T
265      public void testPollFirst() {
266          TreeSet q = populatedSet(SIZE);
267          for (int i = 0; i < SIZE; ++i) {
268 <            assertEquals(i, ((Integer)q.pollFirst()).intValue());
268 >            assertEquals(i, q.pollFirst());
269          }
270          assertNull(q.pollFirst());
271      }
# Line 279 | Line 276 | public class TreeSetTest extends JSR166T
276      public void testPollLast() {
277          TreeSet q = populatedSet(SIZE);
278          for (int i = SIZE-1; i >= 0; --i) {
279 <            assertEquals(i, ((Integer)q.pollLast()).intValue());
279 >            assertEquals(i, q.pollLast());
280          }
281          assertNull(q.pollFirst());
282      }
283  
287 –
284      /**
285       * remove(x) removes x and returns true if present
286       */
287      public void testRemoveElement() {
288          TreeSet q = populatedSet(SIZE);
289          for (int i = 1; i < SIZE; i+=2) {
290 <            assertTrue(q.remove(new Integer(i)));
290 >            assertTrue(q.contains(i));
291 >            assertTrue(q.remove(i));
292 >            assertFalse(q.contains(i));
293 >            assertTrue(q.contains(i-1));
294          }
295          for (int i = 0; i < SIZE; i+=2) {
296 <            assertTrue(q.remove(new Integer(i)));
297 <            assertFalse(q.remove(new Integer(i+1)));
296 >            assertTrue(q.contains(i));
297 >            assertTrue(q.remove(i));
298 >            assertFalse(q.contains(i));
299 >            assertFalse(q.remove(i+1));
300 >            assertFalse(q.contains(i+1));
301          }
302          assertTrue(q.isEmpty());
303      }
# Line 375 | Line 377 | public class TreeSetTest extends JSR166T
377          }
378      }
379  
378 –
379 –
380      /**
381       * lower returns preceding element
382       */
# Line 393 | Line 393 | public class TreeSetTest extends JSR166T
393  
394          Object e4 = q.lower(zero);
395          assertNull(e4);
396 –
396      }
397  
398      /**
# Line 412 | Line 411 | public class TreeSetTest extends JSR166T
411  
412          Object e4 = q.higher(six);
413          assertNull(e4);
415 –
414      }
415  
416      /**
# Line 431 | Line 429 | public class TreeSetTest extends JSR166T
429  
430          Object e4 = q.floor(zero);
431          assertNull(e4);
434 –
432      }
433  
434      /**
# Line 450 | Line 447 | public class TreeSetTest extends JSR166T
447  
448          Object e4 = q.ceiling(six);
449          assertNull(e4);
453 –
450      }
451  
452      /**
453 <     * toArray contains all elements
453 >     * toArray contains all elements in sorted order
454       */
455      public void testToArray() {
456          TreeSet q = populatedSet(SIZE);
457          Object[] o = q.toArray();
462 –        Arrays.sort(o);
458          for (int i = 0; i < o.length; i++)
459 <            assertEquals(o[i], q.pollFirst());
459 >            assertSame(o[i], q.pollFirst());
460      }
461  
462      /**
463 <     * toArray(a) contains all elements
463 >     * toArray(a) contains all elements in sorted order
464       */
465      public void testToArray2() {
466 <        TreeSet q = populatedSet(SIZE);
466 >        TreeSet<Integer> q = populatedSet(SIZE);
467          Integer[] ints = new Integer[SIZE];
468 <        ints = (Integer[])q.toArray(ints);
469 <        Arrays.sort(ints);
468 >        Integer[] array = q.toArray(ints);
469 >        assertSame(ints, array);
470          for (int i = 0; i < ints.length; i++)
471 <            assertEquals(ints[i], q.pollFirst());
471 >            assertSame(ints[i], q.pollFirst());
472      }
473  
474      /**
# Line 501 | Line 496 | public class TreeSetTest extends JSR166T
496              assertTrue(q.contains(it.next()));
497              ++i;
498          }
499 <        assertEquals(i, 0);
499 >        assertEquals(0, i);
500      }
501  
502      /**
503       * iterator.remove removes current element
504       */
505 <    public void testIteratorRemove () {
505 >    public void testIteratorRemove() {
506          final TreeSet q = new TreeSet();
507          q.add(new Integer(2));
508          q.add(new Integer(1));
# Line 523 | Line 518 | public class TreeSetTest extends JSR166T
518          assertFalse(it.hasNext());
519      }
520  
526 –
521      /**
522       * toString contains toStrings of elements
523       */
# Line 531 | Line 525 | public class TreeSetTest extends JSR166T
525          TreeSet q = populatedSet(SIZE);
526          String s = q.toString();
527          for (int i = 0; i < SIZE; ++i) {
528 <            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
528 >            assertTrue(s.contains(String.valueOf(i)));
529          }
530      }
531  
# Line 539 | Line 533 | public class TreeSetTest extends JSR166T
533       * A deserialized serialized set has same elements
534       */
535      public void testSerialization() throws Exception {
536 <        TreeSet q = populatedSet(SIZE);
537 <        ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
538 <        ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
539 <        out.writeObject(q);
540 <        out.close();
541 <
542 <        ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
543 <        ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
544 <        TreeSet r = (TreeSet)in.readObject();
545 <        assertEquals(q.size(), r.size());
546 <        while (!q.isEmpty())
547 <            assertEquals(q.pollFirst(), r.pollFirst());
536 >        NavigableSet x = populatedSet(SIZE);
537 >        NavigableSet y = serialClone(x);
538 >
539 >        assertTrue(x != y);
540 >        assertEquals(x.size(), y.size());
541 >        assertEquals(x, y);
542 >        assertEquals(y, x);
543 >        while (!x.isEmpty()) {
544 >            assertFalse(y.isEmpty());
545 >            assertEquals(x.pollFirst(), y.pollFirst());
546 >        }
547 >        assertTrue(y.isEmpty());
548      }
549  
550      /**
# Line 678 | Line 672 | public class TreeSetTest extends JSR166T
672      /**
673       * Subsets of subsets subdivide correctly
674       */
675 <    public void testRecursiveSubSets() {
676 <        int setSize = 1000;
675 >    public void testRecursiveSubSets() throws Exception {
676 >        int setSize = expensiveTests ? 1000 : 100;
677          Class cl = TreeSet.class;
678  
679          NavigableSet<Integer> set = newSet(cl);
# Line 697 | Line 691 | public class TreeSetTest extends JSR166T
691                     0, setSize - 1, true);
692      }
693  
694 <    static NavigableSet<Integer> newSet(Class cl) {
695 <        NavigableSet<Integer> result = null;
696 <        try {
703 <            result = (NavigableSet<Integer>) cl.newInstance();
704 <        } catch (Exception e) {
705 <            fail();
706 <        }
707 <        assertEquals(result.size(), 0);
694 >    static NavigableSet<Integer> newSet(Class cl) throws Exception {
695 >        NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
696 >        assertEquals(0, result.size());
697          assertFalse(result.iterator().hasNext());
698          return result;
699      }
# Line 766 | Line 755 | public class TreeSetTest extends JSR166T
755              } else {
756                  try {
757                      set.add(element);
758 <                    fail();
759 <                } catch (IllegalArgumentException e) {
771 <                    // expected
772 <                }
758 >                    shouldThrow();
759 >                } catch (IllegalArgumentException success) {}
760              }
761          }
762      }
# Line 867 | Line 854 | public class TreeSetTest extends JSR166T
854       */
855      void check(NavigableSet<Integer> set,
856                        final int min, final int max, final boolean ascending) {
857 <       class ReferenceSet {
857 >        class ReferenceSet {
858              int lower(int element) {
859                  return ascending ?
860                      lowerAscending(element) : higherAscending(element);
# Line 902 | Line 889 | public class TreeSetTest extends JSR166T
889                  // BitSet should support this! Test would run much faster
890                  while (element >= min) {
891                      if (bs.get(element))
892 <                        return(element);
892 >                        return element;
893                      element--;
894                  }
895                  return -1;
# Line 937 | Line 924 | public class TreeSetTest extends JSR166T
924              if (bsContainsI)
925                  size++;
926          }
927 <        assertEquals(set.size(), size);
927 >        assertEquals(size, set.size());
928  
929          // Test contents using contains elementSet iterator
930          int size2 = 0;
# Line 968 | Line 955 | public class TreeSetTest extends JSR166T
955              assertEq(rs.last(),  -1);
956              try {
957                  set.first();
958 <                fail();
959 <            } catch (NoSuchElementException e) {
973 <                // expected
974 <            }
958 >                shouldThrow();
959 >            } catch (NoSuchElementException success) {}
960              try {
961                  set.last();
962 <                fail();
963 <            } catch (NoSuchElementException e) {
979 <                // expected
980 <            }
962 >                shouldThrow();
963 >            } catch (NoSuchElementException success) {}
964          }
965      }
966  

Diff Legend

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