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