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