Home | History | Annotate | Download | only in jsr166 
      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/publicdomain/zero/1.0/
      5  */
      6 
      7 package jsr166;
      8 
      9 import java.util.Arrays;
     10 import java.util.Comparator;
     11 import java.util.Iterator;
     12 import java.util.NavigableSet;
     13 import java.util.Set;
     14 import java.util.SortedSet;
     15 import java.util.TreeSet;
     16 
     17 import junit.framework.Test;
     18 import junit.framework.TestSuite;
     19 
     20 public class TreeSubSetTest extends JSR166TestCase {
     21     // android-note: Removed because the CTS runner does a bad job of
     22     // retrying tests that have suite() declarations.
     23     //
     24     // public static void main(String[] args) {
     25     //     main(suite(), args);
     26     // }
     27     // public static Test suite() {
     28     //     return new TestSuite(TreeSubSetTest.class);
     29     // }
     30 
     31     static class MyReverseComparator implements Comparator {
     32         public int compare(Object x, Object y) {
     33             return ((Comparable)y).compareTo(x);
     34         }
     35     }
     36 
     37     /**
     38      * Returns a new set of given size containing consecutive
     39      * Integers 0 ... n.
     40      */
     41     private NavigableSet<Integer> populatedSet(int n) {
     42         TreeSet<Integer> q = new TreeSet<Integer>();
     43         assertTrue(q.isEmpty());
     44 
     45         for (int i = n - 1; i >= 0; i -= 2)
     46             assertTrue(q.add(new Integer(i)));
     47         for (int i = (n & 1); i < n; i += 2)
     48             assertTrue(q.add(new Integer(i)));
     49         assertTrue(q.add(new Integer(-n)));
     50         assertTrue(q.add(new Integer(n)));
     51         NavigableSet s = q.subSet(new Integer(0), true, new Integer(n), false);
     52         assertFalse(s.isEmpty());
     53         assertEquals(n, s.size());
     54         return s;
     55     }
     56 
     57     /**
     58      * Returns a new set of first 5 ints.
     59      */
     60     private NavigableSet set5() {
     61         TreeSet q = new TreeSet();
     62         assertTrue(q.isEmpty());
     63         q.add(one);
     64         q.add(two);
     65         q.add(three);
     66         q.add(four);
     67         q.add(five);
     68         q.add(zero);
     69         q.add(seven);
     70         NavigableSet s = q.subSet(one, true, seven, false);
     71         assertEquals(5, s.size());
     72         return s;
     73     }
     74 
     75     private NavigableSet dset5() {
     76         TreeSet q = new TreeSet();
     77         assertTrue(q.isEmpty());
     78         q.add(m1);
     79         q.add(m2);
     80         q.add(m3);
     81         q.add(m4);
     82         q.add(m5);
     83         NavigableSet s = q.descendingSet();
     84         assertEquals(5, s.size());
     85         return s;
     86     }
     87 
     88     private static NavigableSet set0() {
     89         TreeSet set = new TreeSet();
     90         assertTrue(set.isEmpty());
     91         return set.tailSet(m1, false);
     92     }
     93 
     94     private static NavigableSet dset0() {
     95         TreeSet set = new TreeSet();
     96         assertTrue(set.isEmpty());
     97         return set;
     98     }
     99 
    100     /**
    101      * A new set has unbounded capacity
    102      */
    103     public void testConstructor1() {
    104         assertEquals(0, set0().size());
    105     }
    106 
    107     /**
    108      * isEmpty is true before add, false after
    109      */
    110     public void testEmpty() {
    111         NavigableSet q = set0();
    112         assertTrue(q.isEmpty());
    113         assertTrue(q.add(new Integer(1)));
    114         assertFalse(q.isEmpty());
    115         assertTrue(q.add(new Integer(2)));
    116         q.pollFirst();
    117         q.pollFirst();
    118         assertTrue(q.isEmpty());
    119     }
    120 
    121     /**
    122      * size changes when elements added and removed
    123      */
    124     public void testSize() {
    125         NavigableSet q = populatedSet(SIZE);
    126         for (int i = 0; i < SIZE; ++i) {
    127             assertEquals(SIZE - i, q.size());
    128             q.pollFirst();
    129         }
    130         for (int i = 0; i < SIZE; ++i) {
    131             assertEquals(i, q.size());
    132             q.add(new Integer(i));
    133         }
    134     }
    135 
    136     /**
    137      * add(null) throws NPE
    138      */
    139     public void testAddNull() {
    140         NavigableSet q = set0();
    141         try {
    142             q.add(null);
    143             shouldThrow();
    144         } catch (NullPointerException success) {}
    145     }
    146 
    147     /**
    148      * Add of comparable element succeeds
    149      */
    150     public void testAdd() {
    151         NavigableSet q = set0();
    152         assertTrue(q.add(six));
    153     }
    154 
    155     /**
    156      * Add of duplicate element fails
    157      */
    158     public void testAddDup() {
    159         NavigableSet q = set0();
    160         assertTrue(q.add(six));
    161         assertFalse(q.add(six));
    162     }
    163 
    164     /**
    165      * Add of non-Comparable throws CCE
    166      */
    167     public void testAddNonComparable() {
    168         NavigableSet q = set0();
    169         try {
    170             q.add(new Object());
    171             q.add(new Object());
    172             shouldThrow();
    173         } catch (ClassCastException success) {}
    174     }
    175 
    176     /**
    177      * addAll(null) throws NPE
    178      */
    179     public void testAddAll1() {
    180         NavigableSet q = set0();
    181         try {
    182             q.addAll(null);
    183             shouldThrow();
    184         } catch (NullPointerException success) {}
    185     }
    186 
    187     /**
    188      * addAll of a collection with null elements throws NPE
    189      */
    190     public void testAddAll2() {
    191         NavigableSet q = set0();
    192         Integer[] ints = new Integer[SIZE];
    193         try {
    194             q.addAll(Arrays.asList(ints));
    195             shouldThrow();
    196         } catch (NullPointerException success) {}
    197     }
    198 
    199     /**
    200      * addAll of a collection with any null elements throws NPE after
    201      * possibly adding some elements
    202      */
    203     public void testAddAll3() {
    204         NavigableSet q = set0();
    205         Integer[] ints = new Integer[SIZE];
    206         for (int i = 0; i < SIZE - 1; ++i)
    207             ints[i] = new Integer(i + SIZE);
    208         try {
    209             q.addAll(Arrays.asList(ints));
    210             shouldThrow();
    211         } catch (NullPointerException success) {}
    212     }
    213 
    214     /**
    215      * Set contains all elements of successful addAll
    216      */
    217     public void testAddAll5() {
    218         Integer[] empty = new Integer[0];
    219         Integer[] ints = new Integer[SIZE];
    220         for (int i = 0; i < SIZE; ++i)
    221             ints[i] = new Integer(SIZE - 1 - i);
    222         NavigableSet q = set0();
    223         assertFalse(q.addAll(Arrays.asList(empty)));
    224         assertTrue(q.addAll(Arrays.asList(ints)));
    225         for (int i = 0; i < SIZE; ++i)
    226             assertEquals(new Integer(i), q.pollFirst());
    227     }
    228 
    229     /**
    230      * poll succeeds unless empty
    231      */
    232     public void testPoll() {
    233         NavigableSet q = populatedSet(SIZE);
    234         for (int i = 0; i < SIZE; ++i) {
    235             assertEquals(i, q.pollFirst());
    236         }
    237         assertNull(q.pollFirst());
    238     }
    239 
    240     /**
    241      * remove(x) removes x and returns true if present
    242      */
    243     public void testRemoveElement() {
    244         NavigableSet q = populatedSet(SIZE);
    245         for (int i = 1; i < SIZE; i += 2) {
    246             assertTrue(q.contains(i));
    247             assertTrue(q.remove(i));
    248             assertFalse(q.contains(i));
    249             assertTrue(q.contains(i - 1));
    250         }
    251         for (int i = 0; i < SIZE; i += 2) {
    252             assertTrue(q.contains(i));
    253             assertTrue(q.remove(i));
    254             assertFalse(q.contains(i));
    255             assertFalse(q.remove(i + 1));
    256             assertFalse(q.contains(i + 1));
    257         }
    258         assertTrue(q.isEmpty());
    259     }
    260 
    261     /**
    262      * contains(x) reports true when elements added but not yet removed
    263      */
    264     public void testContains() {
    265         NavigableSet q = populatedSet(SIZE);
    266         for (int i = 0; i < SIZE; ++i) {
    267             assertTrue(q.contains(new Integer(i)));
    268             q.pollFirst();
    269             assertFalse(q.contains(new Integer(i)));
    270         }
    271     }
    272 
    273     /**
    274      * clear removes all elements
    275      */
    276     public void testClear() {
    277         NavigableSet q = populatedSet(SIZE);
    278         q.clear();
    279         assertTrue(q.isEmpty());
    280         assertEquals(0, q.size());
    281         assertTrue(q.add(new Integer(1)));
    282         assertFalse(q.isEmpty());
    283         q.clear();
    284         assertTrue(q.isEmpty());
    285     }
    286 
    287     /**
    288      * containsAll(c) is true when c contains a subset of elements
    289      */
    290     public void testContainsAll() {
    291         NavigableSet q = populatedSet(SIZE);
    292         NavigableSet p = set0();
    293         for (int i = 0; i < SIZE; ++i) {
    294             assertTrue(q.containsAll(p));
    295             assertFalse(p.containsAll(q));
    296             p.add(new Integer(i));
    297         }
    298         assertTrue(p.containsAll(q));
    299     }
    300 
    301     /**
    302      * retainAll(c) retains only those elements of c and reports true if changed
    303      */
    304     public void testRetainAll() {
    305         NavigableSet q = populatedSet(SIZE);
    306         NavigableSet p = populatedSet(SIZE);
    307         for (int i = 0; i < SIZE; ++i) {
    308             boolean changed = q.retainAll(p);
    309             if (i == 0)
    310                 assertFalse(changed);
    311             else
    312                 assertTrue(changed);
    313 
    314             assertTrue(q.containsAll(p));
    315             assertEquals(SIZE - i, q.size());
    316             p.pollFirst();
    317         }
    318     }
    319 
    320     /**
    321      * removeAll(c) removes only those elements of c and reports true if changed
    322      */
    323     public void testRemoveAll() {
    324         for (int i = 1; i < SIZE; ++i) {
    325             NavigableSet q = populatedSet(SIZE);
    326             NavigableSet p = populatedSet(i);
    327             assertTrue(q.removeAll(p));
    328             assertEquals(SIZE - i, q.size());
    329             for (int j = 0; j < i; ++j) {
    330                 Integer x = (Integer)(p.pollFirst());
    331                 assertFalse(q.contains(x));
    332             }
    333         }
    334     }
    335 
    336     /**
    337      * lower returns preceding element
    338      */
    339     public void testLower() {
    340         NavigableSet q = set5();
    341         Object e1 = q.lower(three);
    342         assertEquals(two, e1);
    343 
    344         Object e2 = q.lower(six);
    345         assertEquals(five, e2);
    346 
    347         Object e3 = q.lower(one);
    348         assertNull(e3);
    349 
    350         Object e4 = q.lower(zero);
    351         assertNull(e4);
    352     }
    353 
    354     /**
    355      * higher returns next element
    356      */
    357     public void testHigher() {
    358         NavigableSet q = set5();
    359         Object e1 = q.higher(three);
    360         assertEquals(four, e1);
    361 
    362         Object e2 = q.higher(zero);
    363         assertEquals(one, e2);
    364 
    365         Object e3 = q.higher(five);
    366         assertNull(e3);
    367 
    368         Object e4 = q.higher(six);
    369         assertNull(e4);
    370     }
    371 
    372     /**
    373      * floor returns preceding element
    374      */
    375     public void testFloor() {
    376         NavigableSet q = set5();
    377         Object e1 = q.floor(three);
    378         assertEquals(three, e1);
    379 
    380         Object e2 = q.floor(six);
    381         assertEquals(five, e2);
    382 
    383         Object e3 = q.floor(one);
    384         assertEquals(one, e3);
    385 
    386         Object e4 = q.floor(zero);
    387         assertNull(e4);
    388     }
    389 
    390     /**
    391      * ceiling returns next element
    392      */
    393     public void testCeiling() {
    394         NavigableSet q = set5();
    395         Object e1 = q.ceiling(three);
    396         assertEquals(three, e1);
    397 
    398         Object e2 = q.ceiling(zero);
    399         assertEquals(one, e2);
    400 
    401         Object e3 = q.ceiling(five);
    402         assertEquals(five, e3);
    403 
    404         Object e4 = q.ceiling(six);
    405         assertNull(e4);
    406     }
    407 
    408     /**
    409      * toArray contains all elements in sorted order
    410      */
    411     public void testToArray() {
    412         NavigableSet q = populatedSet(SIZE);
    413         Object[] o = q.toArray();
    414         for (int i = 0; i < o.length; i++)
    415             assertSame(o[i], q.pollFirst());
    416     }
    417 
    418     /**
    419      * toArray(a) contains all elements in sorted order
    420      */
    421     public void testToArray2() {
    422         NavigableSet<Integer> q = populatedSet(SIZE);
    423         Integer[] ints = new Integer[SIZE];
    424         Integer[] array = q.toArray(ints);
    425         assertSame(ints, array);
    426         for (int i = 0; i < ints.length; i++)
    427             assertSame(ints[i], q.pollFirst());
    428     }
    429 
    430     /**
    431      * iterator iterates through all elements
    432      */
    433     public void testIterator() {
    434         NavigableSet q = populatedSet(SIZE);
    435         Iterator it = q.iterator();
    436         int i;
    437         for (i = 0; it.hasNext(); i++)
    438             assertTrue(q.contains(it.next()));
    439         assertEquals(i, SIZE);
    440         assertIteratorExhausted(it);
    441     }
    442 
    443     /**
    444      * iterator of empty set has no elements
    445      */
    446     public void testEmptyIterator() {
    447         assertIteratorExhausted(set0().iterator());
    448     }
    449 
    450     /**
    451      * iterator.remove removes current element
    452      */
    453     public void testIteratorRemove() {
    454         final NavigableSet q = set0();
    455         q.add(new Integer(2));
    456         q.add(new Integer(1));
    457         q.add(new Integer(3));
    458 
    459         Iterator it = q.iterator();
    460         it.next();
    461         it.remove();
    462 
    463         it = q.iterator();
    464         assertEquals(2, it.next());
    465         assertEquals(3, it.next());
    466         assertFalse(it.hasNext());
    467     }
    468 
    469     /**
    470      * toString contains toStrings of elements
    471      */
    472     public void testToString() {
    473         NavigableSet q = populatedSet(SIZE);
    474         String s = q.toString();
    475         for (int i = 0; i < SIZE; ++i) {
    476             assertTrue(s.contains(String.valueOf(i)));
    477         }
    478     }
    479 
    480     /**
    481      * A deserialized serialized set has same elements
    482      */
    483     public void testSerialization() throws Exception {
    484         NavigableSet x = populatedSet(SIZE);
    485         NavigableSet y = serialClone(x);
    486 
    487         assertNotSame(x, y);
    488         assertEquals(x.size(), y.size());
    489         assertEquals(x, y);
    490         assertEquals(y, x);
    491         while (!x.isEmpty()) {
    492             assertFalse(y.isEmpty());
    493             assertEquals(x.pollFirst(), y.pollFirst());
    494         }
    495         assertTrue(y.isEmpty());
    496     }
    497 
    498     /**
    499      * subSet returns set with keys in requested range
    500      */
    501     public void testSubSetContents() {
    502         NavigableSet set = set5();
    503         SortedSet sm = set.subSet(two, four);
    504         assertEquals(two, sm.first());
    505         assertEquals(three, sm.last());
    506         assertEquals(2, sm.size());
    507         assertFalse(sm.contains(one));
    508         assertTrue(sm.contains(two));
    509         assertTrue(sm.contains(three));
    510         assertFalse(sm.contains(four));
    511         assertFalse(sm.contains(five));
    512         Iterator i = sm.iterator();
    513         Object k;
    514         k = (Integer)(i.next());
    515         assertEquals(two, k);
    516         k = (Integer)(i.next());
    517         assertEquals(three, k);
    518         assertFalse(i.hasNext());
    519         Iterator j = sm.iterator();
    520         j.next();
    521         j.remove();
    522         assertFalse(set.contains(two));
    523         assertEquals(4, set.size());
    524         assertEquals(1, sm.size());
    525         assertEquals(three, sm.first());
    526         assertEquals(three, sm.last());
    527         assertTrue(sm.remove(three));
    528         assertTrue(sm.isEmpty());
    529         assertEquals(3, set.size());
    530     }
    531 
    532     public void testSubSetContents2() {
    533         NavigableSet set = set5();
    534         SortedSet sm = set.subSet(two, three);
    535         assertEquals(1, sm.size());
    536         assertEquals(two, sm.first());
    537         assertEquals(two, sm.last());
    538         assertFalse(sm.contains(one));
    539         assertTrue(sm.contains(two));
    540         assertFalse(sm.contains(three));
    541         assertFalse(sm.contains(four));
    542         assertFalse(sm.contains(five));
    543         Iterator i = sm.iterator();
    544         Object k;
    545         k = (Integer)(i.next());
    546         assertEquals(two, k);
    547         assertFalse(i.hasNext());
    548         Iterator j = sm.iterator();
    549         j.next();
    550         j.remove();
    551         assertFalse(set.contains(two));
    552         assertEquals(4, set.size());
    553         assertEquals(0, sm.size());
    554         assertTrue(sm.isEmpty());
    555         assertFalse(sm.remove(three));
    556         assertEquals(4, set.size());
    557     }
    558 
    559     /**
    560      * headSet returns set with keys in requested range
    561      */
    562     public void testHeadSetContents() {
    563         NavigableSet set = set5();
    564         SortedSet sm = set.headSet(four);
    565         assertTrue(sm.contains(one));
    566         assertTrue(sm.contains(two));
    567         assertTrue(sm.contains(three));
    568         assertFalse(sm.contains(four));
    569         assertFalse(sm.contains(five));
    570         Iterator i = sm.iterator();
    571         Object k;
    572         k = (Integer)(i.next());
    573         assertEquals(one, k);
    574         k = (Integer)(i.next());
    575         assertEquals(two, k);
    576         k = (Integer)(i.next());
    577         assertEquals(three, k);
    578         assertFalse(i.hasNext());
    579         sm.clear();
    580         assertTrue(sm.isEmpty());
    581         assertEquals(2, set.size());
    582         assertEquals(four, set.first());
    583     }
    584 
    585     /**
    586      * tailSet returns set with keys in requested range
    587      */
    588     public void testTailSetContents() {
    589         NavigableSet set = set5();
    590         SortedSet sm = set.tailSet(two);
    591         assertFalse(sm.contains(one));
    592         assertTrue(sm.contains(two));
    593         assertTrue(sm.contains(three));
    594         assertTrue(sm.contains(four));
    595         assertTrue(sm.contains(five));
    596         Iterator i = sm.iterator();
    597         Object k;
    598         k = (Integer)(i.next());
    599         assertEquals(two, k);
    600         k = (Integer)(i.next());
    601         assertEquals(three, k);
    602         k = (Integer)(i.next());
    603         assertEquals(four, k);
    604         k = (Integer)(i.next());
    605         assertEquals(five, k);
    606         assertFalse(i.hasNext());
    607 
    608         SortedSet ssm = sm.tailSet(four);
    609         assertEquals(four, ssm.first());
    610         assertEquals(five, ssm.last());
    611         assertTrue(ssm.remove(four));
    612         assertEquals(1, ssm.size());
    613         assertEquals(3, sm.size());
    614         assertEquals(4, set.size());
    615     }
    616 
    617     /**
    618      * size changes when elements added and removed
    619      */
    620     public void testDescendingSize() {
    621         NavigableSet q = populatedSet(SIZE);
    622         for (int i = 0; i < SIZE; ++i) {
    623             assertEquals(SIZE - i, q.size());
    624             q.pollFirst();
    625         }
    626         for (int i = 0; i < SIZE; ++i) {
    627             assertEquals(i, q.size());
    628             q.add(new Integer(i));
    629         }
    630     }
    631 
    632     /**
    633      * Add of comparable element succeeds
    634      */
    635     public void testDescendingAdd() {
    636         NavigableSet q = dset0();
    637         assertTrue(q.add(m6));
    638     }
    639 
    640     /**
    641      * Add of duplicate element fails
    642      */
    643     public void testDescendingAddDup() {
    644         NavigableSet q = dset0();
    645         assertTrue(q.add(m6));
    646         assertFalse(q.add(m6));
    647     }
    648 
    649     /**
    650      * Add of non-Comparable throws CCE
    651      */
    652     public void testDescendingAddNonComparable() {
    653         NavigableSet q = dset0();
    654         try {
    655             q.add(new Object());
    656             q.add(new Object());
    657             shouldThrow();
    658         } catch (ClassCastException success) {}
    659     }
    660 
    661     /**
    662      * addAll(null) throws NPE
    663      */
    664     public void testDescendingAddAll1() {
    665         NavigableSet q = dset0();
    666         try {
    667             q.addAll(null);
    668             shouldThrow();
    669         } catch (NullPointerException success) {}
    670     }
    671 
    672     /**
    673      * addAll of a collection with null elements throws NPE
    674      */
    675     public void testDescendingAddAll2() {
    676         NavigableSet q = dset0();
    677         Integer[] ints = new Integer[SIZE];
    678         try {
    679             q.addAll(Arrays.asList(ints));
    680             shouldThrow();
    681         } catch (NullPointerException success) {}
    682     }
    683 
    684     /**
    685      * addAll of a collection with any null elements throws NPE after
    686      * possibly adding some elements
    687      */
    688     public void testDescendingAddAll3() {
    689         NavigableSet q = dset0();
    690         Integer[] ints = new Integer[SIZE];
    691         for (int i = 0; i < SIZE - 1; ++i)
    692             ints[i] = new Integer(i + SIZE);
    693         try {
    694             q.addAll(Arrays.asList(ints));
    695             shouldThrow();
    696         } catch (NullPointerException success) {}
    697     }
    698 
    699     /**
    700      * Set contains all elements of successful addAll
    701      */
    702     public void testDescendingAddAll5() {
    703         Integer[] empty = new Integer[0];
    704         Integer[] ints = new Integer[SIZE];
    705         for (int i = 0; i < SIZE; ++i)
    706             ints[i] = new Integer(SIZE - 1 - i);
    707         NavigableSet q = dset0();
    708         assertFalse(q.addAll(Arrays.asList(empty)));
    709         assertTrue(q.addAll(Arrays.asList(ints)));
    710         for (int i = 0; i < SIZE; ++i)
    711             assertEquals(new Integer(i), q.pollFirst());
    712     }
    713 
    714     /**
    715      * poll succeeds unless empty
    716      */
    717     public void testDescendingPoll() {
    718         NavigableSet q = populatedSet(SIZE);
    719         for (int i = 0; i < SIZE; ++i) {
    720             assertEquals(i, q.pollFirst());
    721         }
    722         assertNull(q.pollFirst());
    723     }
    724 
    725     /**
    726      * remove(x) removes x and returns true if present
    727      */
    728     public void testDescendingRemoveElement() {
    729         NavigableSet q = populatedSet(SIZE);
    730         for (int i = 1; i < SIZE; i += 2) {
    731             assertTrue(q.remove(new Integer(i)));
    732         }
    733         for (int i = 0; i < SIZE; i += 2) {
    734             assertTrue(q.remove(new Integer(i)));
    735             assertFalse(q.remove(new Integer(i + 1)));
    736         }
    737         assertTrue(q.isEmpty());
    738     }
    739 
    740     /**
    741      * contains(x) reports true when elements added but not yet removed
    742      */
    743     public void testDescendingContains() {
    744         NavigableSet q = populatedSet(SIZE);
    745         for (int i = 0; i < SIZE; ++i) {
    746             assertTrue(q.contains(new Integer(i)));
    747             q.pollFirst();
    748             assertFalse(q.contains(new Integer(i)));
    749         }
    750     }
    751 
    752     /**
    753      * clear removes all elements
    754      */
    755     public void testDescendingClear() {
    756         NavigableSet q = populatedSet(SIZE);
    757         q.clear();
    758         assertTrue(q.isEmpty());
    759         assertEquals(0, q.size());
    760         assertTrue(q.add(new Integer(1)));
    761         assertFalse(q.isEmpty());
    762         q.clear();
    763         assertTrue(q.isEmpty());
    764     }
    765 
    766     /**
    767      * containsAll(c) is true when c contains a subset of elements
    768      */
    769     public void testDescendingContainsAll() {
    770         NavigableSet q = populatedSet(SIZE);
    771         NavigableSet p = dset0();
    772         for (int i = 0; i < SIZE; ++i) {
    773             assertTrue(q.containsAll(p));
    774             assertFalse(p.containsAll(q));
    775             p.add(new Integer(i));
    776         }
    777         assertTrue(p.containsAll(q));
    778     }
    779 
    780     /**
    781      * retainAll(c) retains only those elements of c and reports true if changed
    782      */
    783     public void testDescendingRetainAll() {
    784         NavigableSet q = populatedSet(SIZE);
    785         NavigableSet p = populatedSet(SIZE);
    786         for (int i = 0; i < SIZE; ++i) {
    787             boolean changed = q.retainAll(p);
    788             if (i == 0)
    789                 assertFalse(changed);
    790             else
    791                 assertTrue(changed);
    792 
    793             assertTrue(q.containsAll(p));
    794             assertEquals(SIZE - i, q.size());
    795             p.pollFirst();
    796         }
    797     }
    798 
    799     /**
    800      * removeAll(c) removes only those elements of c and reports true if changed
    801      */
    802     public void testDescendingRemoveAll() {
    803         for (int i = 1; i < SIZE; ++i) {
    804             NavigableSet q = populatedSet(SIZE);
    805             NavigableSet p = populatedSet(i);
    806             assertTrue(q.removeAll(p));
    807             assertEquals(SIZE - i, q.size());
    808             for (int j = 0; j < i; ++j) {
    809                 Integer x = (Integer)(p.pollFirst());
    810                 assertFalse(q.contains(x));
    811             }
    812         }
    813     }
    814 
    815     /**
    816      * lower returns preceding element
    817      */
    818     public void testDescendingLower() {
    819         NavigableSet q = dset5();
    820         Object e1 = q.lower(m3);
    821         assertEquals(m2, e1);
    822 
    823         Object e2 = q.lower(m6);
    824         assertEquals(m5, e2);
    825 
    826         Object e3 = q.lower(m1);
    827         assertNull(e3);
    828 
    829         Object e4 = q.lower(zero);
    830         assertNull(e4);
    831     }
    832 
    833     /**
    834      * higher returns next element
    835      */
    836     public void testDescendingHigher() {
    837         NavigableSet q = dset5();
    838         Object e1 = q.higher(m3);
    839         assertEquals(m4, e1);
    840 
    841         Object e2 = q.higher(zero);
    842         assertEquals(m1, e2);
    843 
    844         Object e3 = q.higher(m5);
    845         assertNull(e3);
    846 
    847         Object e4 = q.higher(m6);
    848         assertNull(e4);
    849     }
    850 
    851     /**
    852      * floor returns preceding element
    853      */
    854     public void testDescendingFloor() {
    855         NavigableSet q = dset5();
    856         Object e1 = q.floor(m3);
    857         assertEquals(m3, e1);
    858 
    859         Object e2 = q.floor(m6);
    860         assertEquals(m5, e2);
    861 
    862         Object e3 = q.floor(m1);
    863         assertEquals(m1, e3);
    864 
    865         Object e4 = q.floor(zero);
    866         assertNull(e4);
    867     }
    868 
    869     /**
    870      * ceiling returns next element
    871      */
    872     public void testDescendingCeiling() {
    873         NavigableSet q = dset5();
    874         Object e1 = q.ceiling(m3);
    875         assertEquals(m3, e1);
    876 
    877         Object e2 = q.ceiling(zero);
    878         assertEquals(m1, e2);
    879 
    880         Object e3 = q.ceiling(m5);
    881         assertEquals(m5, e3);
    882 
    883         Object e4 = q.ceiling(m6);
    884         assertNull(e4);
    885     }
    886 
    887     /**
    888      * toArray contains all elements
    889      */
    890     public void testDescendingToArray() {
    891         NavigableSet q = populatedSet(SIZE);
    892         Object[] o = q.toArray();
    893         Arrays.sort(o);
    894         for (int i = 0; i < o.length; i++)
    895             assertEquals(o[i], q.pollFirst());
    896     }
    897 
    898     /**
    899      * toArray(a) contains all elements
    900      */
    901     public void testDescendingToArray2() {
    902         NavigableSet q = populatedSet(SIZE);
    903         Integer[] ints = new Integer[SIZE];
    904         assertSame(ints, q.toArray(ints));
    905         Arrays.sort(ints);
    906         for (int i = 0; i < ints.length; i++)
    907             assertEquals(ints[i], q.pollFirst());
    908     }
    909 
    910     /**
    911      * iterator iterates through all elements
    912      */
    913     public void testDescendingIterator() {
    914         NavigableSet q = populatedSet(SIZE);
    915         int i = 0;
    916         Iterator it = q.iterator();
    917         while (it.hasNext()) {
    918             assertTrue(q.contains(it.next()));
    919             ++i;
    920         }
    921         assertEquals(i, SIZE);
    922     }
    923 
    924     /**
    925      * iterator of empty set has no elements
    926      */
    927     public void testDescendingEmptyIterator() {
    928         NavigableSet q = dset0();
    929         int i = 0;
    930         Iterator it = q.iterator();
    931         while (it.hasNext()) {
    932             assertTrue(q.contains(it.next()));
    933             ++i;
    934         }
    935         assertEquals(0, i);
    936     }
    937 
    938     /**
    939      * iterator.remove removes current element
    940      */
    941     public void testDescendingIteratorRemove() {
    942         final NavigableSet q = dset0();
    943         q.add(new Integer(2));
    944         q.add(new Integer(1));
    945         q.add(new Integer(3));
    946 
    947         Iterator it = q.iterator();
    948         it.next();
    949         it.remove();
    950 
    951         it = q.iterator();
    952         assertEquals(2, it.next());
    953         assertEquals(3, it.next());
    954         assertFalse(it.hasNext());
    955     }
    956 
    957     /**
    958      * toString contains toStrings of elements
    959      */
    960     public void testDescendingToString() {
    961         NavigableSet q = populatedSet(SIZE);
    962         String s = q.toString();
    963         for (int i = 0; i < SIZE; ++i) {
    964             assertTrue(s.contains(String.valueOf(i)));
    965         }
    966     }
    967 
    968     /**
    969      * A deserialized serialized set has same elements
    970      */
    971     public void testDescendingSerialization() throws Exception {
    972         NavigableSet x = dset5();
    973         NavigableSet y = serialClone(x);
    974 
    975         assertNotSame(x, y);
    976         assertEquals(x.size(), y.size());
    977         assertEquals(x.toString(), y.toString());
    978         assertEquals(x, y);
    979         assertEquals(y, x);
    980         while (!x.isEmpty()) {
    981             assertFalse(y.isEmpty());
    982             assertEquals(x.pollFirst(), y.pollFirst());
    983         }
    984         assertTrue(y.isEmpty());
    985     }
    986 
    987     /**
    988      * subSet returns set with keys in requested range
    989      */
    990     public void testDescendingSubSetContents() {
    991         NavigableSet set = dset5();
    992         SortedSet sm = set.subSet(m2, m4);
    993         assertEquals(m2, sm.first());
    994         assertEquals(m3, sm.last());
    995         assertEquals(2, sm.size());
    996         assertFalse(sm.contains(m1));
    997         assertTrue(sm.contains(m2));
    998         assertTrue(sm.contains(m3));
    999         assertFalse(sm.contains(m4));
   1000         assertFalse(sm.contains(m5));
   1001         Iterator i = sm.iterator();
   1002         Object k;
   1003         k = (Integer)(i.next());
   1004         assertEquals(m2, k);
   1005         k = (Integer)(i.next());
   1006         assertEquals(m3, k);
   1007         assertFalse(i.hasNext());
   1008         Iterator j = sm.iterator();
   1009         j.next();
   1010         j.remove();
   1011         assertFalse(set.contains(m2));
   1012         assertEquals(4, set.size());
   1013         assertEquals(1, sm.size());
   1014         assertEquals(m3, sm.first());
   1015         assertEquals(m3, sm.last());
   1016         assertTrue(sm.remove(m3));
   1017         assertTrue(sm.isEmpty());
   1018         assertEquals(3, set.size());
   1019     }
   1020 
   1021     public void testDescendingSubSetContents2() {
   1022         NavigableSet set = dset5();
   1023         SortedSet sm = set.subSet(m2, m3);
   1024         assertEquals(1, sm.size());
   1025         assertEquals(m2, sm.first());
   1026         assertEquals(m2, sm.last());
   1027         assertFalse(sm.contains(m1));
   1028         assertTrue(sm.contains(m2));
   1029         assertFalse(sm.contains(m3));
   1030         assertFalse(sm.contains(m4));
   1031         assertFalse(sm.contains(m5));
   1032         Iterator i = sm.iterator();
   1033         Object k;
   1034         k = (Integer)(i.next());
   1035         assertEquals(m2, k);
   1036         assertFalse(i.hasNext());
   1037         Iterator j = sm.iterator();
   1038         j.next();
   1039         j.remove();
   1040         assertFalse(set.contains(m2));
   1041         assertEquals(4, set.size());
   1042         assertEquals(0, sm.size());
   1043         assertTrue(sm.isEmpty());
   1044         assertFalse(sm.remove(m3));
   1045         assertEquals(4, set.size());
   1046     }
   1047 
   1048     /**
   1049      * headSet returns set with keys in requested range
   1050      */
   1051     public void testDescendingHeadSetContents() {
   1052         NavigableSet set = dset5();
   1053         SortedSet sm = set.headSet(m4);
   1054         assertTrue(sm.contains(m1));
   1055         assertTrue(sm.contains(m2));
   1056         assertTrue(sm.contains(m3));
   1057         assertFalse(sm.contains(m4));
   1058         assertFalse(sm.contains(m5));
   1059         Iterator i = sm.iterator();
   1060         Object k;
   1061         k = (Integer)(i.next());
   1062         assertEquals(m1, k);
   1063         k = (Integer)(i.next());
   1064         assertEquals(m2, k);
   1065         k = (Integer)(i.next());
   1066         assertEquals(m3, k);
   1067         assertFalse(i.hasNext());
   1068         sm.clear();
   1069         assertTrue(sm.isEmpty());
   1070         assertEquals(2, set.size());
   1071         assertEquals(m4, set.first());
   1072     }
   1073 
   1074     /**
   1075      * tailSet returns set with keys in requested range
   1076      */
   1077     public void testDescendingTailSetContents() {
   1078         NavigableSet set = dset5();
   1079         SortedSet sm = set.tailSet(m2);
   1080         assertFalse(sm.contains(m1));
   1081         assertTrue(sm.contains(m2));
   1082         assertTrue(sm.contains(m3));
   1083         assertTrue(sm.contains(m4));
   1084         assertTrue(sm.contains(m5));
   1085         Iterator i = sm.iterator();
   1086         Object k;
   1087         k = (Integer)(i.next());
   1088         assertEquals(m2, k);
   1089         k = (Integer)(i.next());
   1090         assertEquals(m3, k);
   1091         k = (Integer)(i.next());
   1092         assertEquals(m4, k);
   1093         k = (Integer)(i.next());
   1094         assertEquals(m5, k);
   1095         assertFalse(i.hasNext());
   1096 
   1097         SortedSet ssm = sm.tailSet(m4);
   1098         assertEquals(m4, ssm.first());
   1099         assertEquals(m5, ssm.last());
   1100         assertTrue(ssm.remove(m4));
   1101         assertEquals(1, ssm.size());
   1102         assertEquals(3, sm.size());
   1103         assertEquals(4, set.size());
   1104     }
   1105 
   1106     /**
   1107      * addAll is idempotent
   1108      */
   1109     public void testAddAll_idempotent() throws Exception {
   1110         Set x = populatedSet(SIZE);
   1111         Set y = new TreeSet(x);
   1112         y.addAll(x);
   1113         assertEquals(x, y);
   1114         assertEquals(y, x);
   1115     }
   1116 
   1117 }
   1118