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