--- jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java 2006/04/19 15:10:54 1.3 +++ jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java 2021/01/27 01:57:24 1.41 @@ -1,57 +1,59 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ -import junit.framework.*; -import java.util.*; -import java.util.concurrent.*; -import java.io.*; +import java.util.Arrays; +import java.util.Comparator; +import java.util.Iterator; +import java.util.NavigableSet; +import java.util.SortedSet; +import java.util.concurrent.ConcurrentSkipListSet; + +import junit.framework.Test; +import junit.framework.TestSuite; public class ConcurrentSkipListSubSetTest extends JSR166TestCase { public static void main(String[] args) { - junit.textui.TestRunner.run (suite()); + main(suite(), args); } public static Test suite() { - return new TestSuite(ConcurrentSkipListSubSetTest.class); + return new TestSuite(ConcurrentSkipListSubSetTest.class); } - static class MyReverseComparator implements Comparator { + static class MyReverseComparator implements Comparator { + @SuppressWarnings("unchecked") public int compare(Object x, Object y) { - int i = ((Integer)x).intValue(); - int j = ((Integer)y).intValue(); - if (i < j) return 1; - if (i > j) return -1; - return 0; + return ((Comparable)y).compareTo(x); } } /** - * Create a set of given size containing consecutive - * Integers 0 ... n. + * Returns a new set of given size containing consecutive + * Items 0 ... n - 1. */ - private NavigableSet populatedSet(int n) { - ConcurrentSkipListSet q = new ConcurrentSkipListSet(); + private static NavigableSet populatedSet(int n) { + ConcurrentSkipListSet q = new ConcurrentSkipListSet<>(); assertTrue(q.isEmpty()); - for(int i = n-1; i >= 0; i-=2) - assertTrue(q.add(new Integer(i))); - for(int i = (n & 1); i < n; i+=2) - assertTrue(q.add(new Integer(i))); - assertTrue(q.add(new Integer(-n))); - assertTrue(q.add(new Integer(n))); - NavigableSet s = q.navigableSubSet(new Integer(0), true, new Integer(n), false); + for (int i = n - 1; i >= 0; i -= 2) + mustAdd(q, i); + for (int i = (n & 1); i < n; i += 2) + mustAdd(q, i); + mustAdd(q, -n); + mustAdd(q, n); + NavigableSet s = q.subSet(itemFor(0), true, itemFor(n), false); assertFalse(s.isEmpty()); - assertEquals(n, s.size()); + mustEqual(n, s.size()); return s; } /** - * Create set of first 5 ints + * Returns a new set of first 5 ints. */ - private NavigableSet set5() { - ConcurrentSkipListSet q = new ConcurrentSkipListSet(); + private static NavigableSet set5() { + ConcurrentSkipListSet q = new ConcurrentSkipListSet<>(); assertTrue(q.isEmpty()); q.add(one); q.add(two); @@ -60,34 +62,55 @@ public class ConcurrentSkipListSubSetTes q.add(five); q.add(zero); q.add(seven); - NavigableSet s = q.navigableSubSet(one, true, seven, false); - assertEquals(5, s.size()); + NavigableSet s = q.subSet(one, true, seven, false); + mustEqual(5, s.size()); + return s; + } + + /** + * Returns a new set of first 5 negative ints. + */ + private static NavigableSet dset5() { + ConcurrentSkipListSet q = new ConcurrentSkipListSet<>(); + assertTrue(q.isEmpty()); + q.add(minusOne); + q.add(minusTwo); + q.add(minusThree); + q.add(minusFour); + q.add(minusFive); + NavigableSet s = q.descendingSet(); + mustEqual(5, s.size()); return s; } - private static NavigableSet set0() { - ConcurrentSkipListSet set = new ConcurrentSkipListSet(); + private static NavigableSet set0() { + ConcurrentSkipListSet set = new ConcurrentSkipListSet<>(); + assertTrue(set.isEmpty()); + return set.tailSet(minusOne, true); + } + + private static NavigableSet dset0() { + ConcurrentSkipListSet set = new ConcurrentSkipListSet<>(); assertTrue(set.isEmpty()); - return set.navigableTailSet(m1, true); + return set; } - + /** * A new set has unbounded capacity */ public void testConstructor1() { - assertEquals(0, set0().size()); + mustEqual(0, set0().size()); } - /** * isEmpty is true before add, false after */ public void testEmpty() { - NavigableSet q = set0(); + NavigableSet q = set0(); assertTrue(q.isEmpty()); - q.add(new Integer(1)); + mustAdd(q, one); assertFalse(q.isEmpty()); - q.add(new Integer(2)); + mustAdd(q, two); q.pollFirst(); q.pollFirst(); assertTrue(q.isEmpty()); @@ -97,14 +120,14 @@ public class ConcurrentSkipListSubSetTes * size changes when elements added and removed */ public void testSize() { - NavigableSet q = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); for (int i = 0; i < SIZE; ++i) { - assertEquals(SIZE-i, q.size()); + mustEqual(SIZE - i, q.size()); q.pollFirst(); } for (int i = 0; i < SIZE; ++i) { - assertEquals(i, q.size()); - q.add(new Integer(i)); + mustEqual(i, q.size()); + mustAdd(q, i); } } @@ -112,18 +135,18 @@ public class ConcurrentSkipListSubSetTes * add(null) throws NPE */ public void testAddNull() { - try { - NavigableSet q = set0(); + NavigableSet q = set0(); + try { q.add(null); shouldThrow(); - } catch (NullPointerException success) { } + } catch (NullPointerException success) {} } /** * Add of comparable element succeeds */ public void testAdd() { - NavigableSet q = set0(); + NavigableSet q = set0(); assertTrue(q.add(six)); } @@ -131,7 +154,7 @@ public class ConcurrentSkipListSubSetTes * Add of duplicate element fails */ public void testAddDup() { - NavigableSet q = set0(); + NavigableSet q = set0(); assertTrue(q.add(six)); assertFalse(q.add(six)); } @@ -140,109 +163,107 @@ public class ConcurrentSkipListSubSetTes * Add of non-Comparable throws CCE */ public void testAddNonComparable() { + ConcurrentSkipListSet src = new ConcurrentSkipListSet<>(); + NavigableSet q = src.tailSet(minusOne, true); try { - NavigableSet q = set0(); - q.add(new Object()); q.add(new Object()); q.add(new Object()); shouldThrow(); - } - catch(ClassCastException success) {} + } catch (ClassCastException success) {} } - /** * addAll(null) throws NPE */ public void testAddAll1() { + NavigableSet q = set0(); try { - NavigableSet q = set0(); q.addAll(null); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } + /** * addAll of a collection with null elements throws NPE */ public void testAddAll2() { + NavigableSet q = set0(); + Item[] items = new Item[SIZE]; try { - NavigableSet q = set0(); - Integer[] ints = new Integer[SIZE]; - q.addAll(Arrays.asList(ints)); + q.addAll(Arrays.asList(items)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } + /** * addAll of a collection with any null elements throws NPE after * possibly adding some elements */ public void testAddAll3() { + NavigableSet q = set0(); + Item[] items = new Item[2]; items[0] = zero; try { - NavigableSet q = set0(); - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE-1; ++i) - ints[i] = new Integer(i+SIZE); - q.addAll(Arrays.asList(ints)); + q.addAll(Arrays.asList(items)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } /** * Set contains all elements of successful addAll */ public void testAddAll5() { - try { - Integer[] empty = new Integer[0]; - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE; ++i) - ints[i] = new Integer(SIZE-1- i); - NavigableSet q = set0(); - assertFalse(q.addAll(Arrays.asList(empty))); - assertTrue(q.addAll(Arrays.asList(ints))); - for (int i = 0; i < SIZE; ++i) - assertEquals(new Integer(i), q.pollFirst()); - } - finally {} + Item[] empty = new Item[0]; + Item[] items = new Item[SIZE]; + for (int i = 0; i < SIZE; ++i) + items[i] = itemFor(SIZE - 1 - i); + NavigableSet q = set0(); + assertFalse(q.addAll(Arrays.asList(empty))); + assertTrue(q.addAll(Arrays.asList(items))); + for (int i = 0; i < SIZE; ++i) + mustEqual(i, q.pollFirst()); } /** * poll succeeds unless empty */ public void testPoll() { - NavigableSet q = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); for (int i = 0; i < SIZE; ++i) { - assertEquals(i, ((Integer)q.pollFirst()).intValue()); + mustEqual(i, q.pollFirst()); } - assertNull(q.pollFirst()); + assertNull(q.pollFirst()); } /** * remove(x) removes x and returns true if present */ public void testRemoveElement() { - NavigableSet q = populatedSet(SIZE); - for (int i = 1; i < SIZE; i+=2) { - assertTrue(q.remove(new Integer(i))); + NavigableSet q = populatedSet(SIZE); + for (int i = 1; i < SIZE; i += 2) { + mustContain(q, i); + mustRemove(q, i); + mustNotContain(q, i); + mustContain(q, i - 1); } - for (int i = 0; i < SIZE; i+=2) { - assertTrue(q.remove(new Integer(i))); - assertFalse(q.remove(new Integer(i+1))); + for (int i = 0; i < SIZE; i += 2) { + mustContain(q, i); + mustRemove(q, i); + mustNotContain(q, i); + mustNotRemove(q, i + 1); + mustNotContain(q, i + 1); } assertTrue(q.isEmpty()); } - + /** * contains(x) reports true when elements added but not yet removed */ public void testContains() { - NavigableSet q = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); for (int i = 0; i < SIZE; ++i) { - assertTrue(q.contains(new Integer(i))); + mustContain(q, i); q.pollFirst(); - assertFalse(q.contains(new Integer(i))); + mustNotContain(q, i); } } @@ -250,11 +271,11 @@ public class ConcurrentSkipListSubSetTes * clear removes all elements */ public void testClear() { - NavigableSet q = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); q.clear(); assertTrue(q.isEmpty()); - assertEquals(0, q.size()); - q.add(new Integer(1)); + mustEqual(0, q.size()); + mustAdd(q, one); assertFalse(q.isEmpty()); q.clear(); assertTrue(q.isEmpty()); @@ -264,12 +285,12 @@ public class ConcurrentSkipListSubSetTes * containsAll(c) is true when c contains a subset of elements */ public void testContainsAll() { - NavigableSet q = populatedSet(SIZE); - NavigableSet p = set0(); + NavigableSet q = populatedSet(SIZE); + NavigableSet p = set0(); for (int i = 0; i < SIZE; ++i) { assertTrue(q.containsAll(p)); assertFalse(p.containsAll(q)); - p.add(new Integer(i)); + mustAdd(p, i); } assertTrue(p.containsAll(q)); } @@ -278,8 +299,8 @@ public class ConcurrentSkipListSubSetTes * retainAll(c) retains only those elements of c and reports true if changed */ public void testRetainAll() { - NavigableSet q = populatedSet(SIZE); - NavigableSet p = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); + NavigableSet p = populatedSet(SIZE); for (int i = 0; i < SIZE; ++i) { boolean changed = q.retainAll(p); if (i == 0) @@ -288,7 +309,7 @@ public class ConcurrentSkipListSubSetTes assertTrue(changed); assertTrue(q.containsAll(p)); - assertEquals(SIZE-i, q.size()); + mustEqual(SIZE - i, q.size()); p.pollFirst(); } } @@ -298,317 +319,790 @@ public class ConcurrentSkipListSubSetTes */ public void testRemoveAll() { for (int i = 1; i < SIZE; ++i) { - NavigableSet q = populatedSet(SIZE); - NavigableSet p = populatedSet(i); + NavigableSet q = populatedSet(SIZE); + NavigableSet p = populatedSet(i); assertTrue(q.removeAll(p)); - assertEquals(SIZE-i, q.size()); + mustEqual(SIZE - i, q.size()); for (int j = 0; j < i; ++j) { - Integer I = (Integer)(p.pollFirst()); - assertFalse(q.contains(I)); + mustNotContain(q, p.pollFirst()); } } } - - /** * lower returns preceding element */ public void testLower() { - NavigableSet q = set5(); + NavigableSet q = set5(); Object e1 = q.lower(three); - assertEquals(two, e1); + mustEqual(two, e1); Object e2 = q.lower(six); - assertEquals(five, e2); + mustEqual(five, e2); Object e3 = q.lower(one); assertNull(e3); Object e4 = q.lower(zero); assertNull(e4); - } /** * higher returns next element */ public void testHigher() { - NavigableSet q = set5(); + NavigableSet q = set5(); Object e1 = q.higher(three); - assertEquals(four, e1); + mustEqual(four, e1); Object e2 = q.higher(zero); - assertEquals(one, e2); + mustEqual(one, e2); Object e3 = q.higher(five); assertNull(e3); Object e4 = q.higher(six); assertNull(e4); - } /** * floor returns preceding element */ public void testFloor() { - NavigableSet q = set5(); + NavigableSet q = set5(); Object e1 = q.floor(three); - assertEquals(three, e1); + mustEqual(three, e1); Object e2 = q.floor(six); - assertEquals(five, e2); + mustEqual(five, e2); Object e3 = q.floor(one); - assertEquals(one, e3); + mustEqual(one, e3); Object e4 = q.floor(zero); assertNull(e4); - } /** * ceiling returns next element */ public void testCeiling() { - NavigableSet q = set5(); + NavigableSet q = set5(); Object e1 = q.ceiling(three); - assertEquals(three, e1); + mustEqual(three, e1); Object e2 = q.ceiling(zero); - assertEquals(one, e2); + mustEqual(one, e2); Object e3 = q.ceiling(five); - assertEquals(five, e3); + mustEqual(five, e3); Object e4 = q.ceiling(six); assertNull(e4); - } /** - * toArray contains all elements + * toArray contains all elements in sorted order */ public void testToArray() { - NavigableSet q = populatedSet(SIZE); - Object[] o = q.toArray(); - Arrays.sort(o); - for(int i = 0; i < o.length; i++) - assertEquals(o[i], q.pollFirst()); + NavigableSet q = populatedSet(SIZE); + Object[] a = q.toArray(); + assertSame(Object[].class, a.getClass()); + for (Object o : a) + assertSame(o, q.pollFirst()); + assertTrue(q.isEmpty()); } /** - * toArray(a) contains all elements + * toArray(a) contains all elements in sorted order */ public void testToArray2() { - NavigableSet q = populatedSet(SIZE); - Integer[] ints = new Integer[SIZE]; - ints = (Integer[])q.toArray(ints); - Arrays.sort(ints); - for(int i = 0; i < ints.length; i++) - assertEquals(ints[i], q.pollFirst()); + NavigableSet q = populatedSet(SIZE); + Item[] items = new Item[SIZE]; + Item[] array = q.toArray(items); + assertSame(items, array); + for (Item o : items) + assertSame(o, q.pollFirst()); + assertTrue(q.isEmpty()); } - + /** * iterator iterates through all elements */ public void testIterator() { - NavigableSet q = populatedSet(SIZE); - int i = 0; - Iterator it = q.iterator(); - while(it.hasNext()) { + NavigableSet q = populatedSet(SIZE); + Iterator it = q.iterator(); + int i; + for (i = 0; it.hasNext(); i++) assertTrue(q.contains(it.next())); - ++i; - } - assertEquals(i, SIZE); + mustEqual(i, SIZE); + assertIteratorExhausted(it); } /** * iterator of empty set has no elements */ public void testEmptyIterator() { - NavigableSet q = set0(); - int i = 0; - Iterator it = q.iterator(); - while(it.hasNext()) { - assertTrue(q.contains(it.next())); - ++i; - } - assertEquals(i, 0); + assertIteratorExhausted(set0().iterator()); } /** * iterator.remove removes current element */ - public void testIteratorRemove () { - final NavigableSet q = set0(); - q.add(new Integer(2)); - q.add(new Integer(1)); - q.add(new Integer(3)); - - Iterator it = q.iterator(); + public void testIteratorRemove() { + final NavigableSet q = set0(); + mustAdd(q, two); + mustAdd(q, one); + mustAdd(q, three); + Iterator it = q.iterator(); it.next(); it.remove(); it = q.iterator(); - assertEquals(it.next(), new Integer(2)); - assertEquals(it.next(), new Integer(3)); + mustEqual(it.next(), two); + mustEqual(it.next(), three); assertFalse(it.hasNext()); } - /** * toString contains toStrings of elements */ public void testToString() { - NavigableSet q = populatedSet(SIZE); + NavigableSet q = populatedSet(SIZE); String s = q.toString(); for (int i = 0; i < SIZE; ++i) { - assertTrue(s.indexOf(String.valueOf(i)) >= 0); + assertTrue(s.contains(String.valueOf(i))); } - } + } /** - * A deserialized serialized set has same elements + * A deserialized/reserialized set equals original */ - public void testSerialization() { - NavigableSet q = populatedSet(SIZE); - try { - ByteArrayOutputStream bout = new ByteArrayOutputStream(10000); - ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout)); - out.writeObject(q); - out.close(); - - ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray()); - ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin)); - NavigableSet r = (NavigableSet)in.readObject(); - assertEquals(q.size(), r.size()); - while (!q.isEmpty()) - assertEquals(q.pollFirst(), r.pollFirst()); - } catch(Exception e){ - e.printStackTrace(); - unexpectedException(); + public void testSerialization() throws Exception { + NavigableSet x = populatedSet(SIZE); + NavigableSet y = serialClone(x); + + assertNotSame(y, x); + mustEqual(x.size(), y.size()); + mustEqual(x, y); + mustEqual(y, x); + while (!x.isEmpty()) { + assertFalse(y.isEmpty()); + mustEqual(x.pollFirst(), y.pollFirst()); } + assertTrue(y.isEmpty()); } /** * subSet returns set with keys in requested range */ public void testSubSetContents() { - NavigableSet set = set5(); - SortedSet sm = set.subSet(two, four); - assertEquals(two, sm.first()); - assertEquals(three, sm.last()); - assertEquals(2, sm.size()); - assertFalse(sm.contains(one)); - assertTrue(sm.contains(two)); - assertTrue(sm.contains(three)); - assertFalse(sm.contains(four)); - assertFalse(sm.contains(five)); - Iterator i = sm.iterator(); - Object k; - k = (Integer)(i.next()); - assertEquals(two, k); - k = (Integer)(i.next()); - assertEquals(three, k); + NavigableSet set = set5(); + SortedSet sm = set.subSet(two, four); + mustEqual(two, sm.first()); + mustEqual(three, sm.last()); + mustEqual(2, sm.size()); + mustNotContain(sm, one); + mustContain(sm, two); + mustContain(sm, three); + mustNotContain(sm, four); + mustNotContain(sm, five); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(two, k); + k = i.next(); + mustEqual(three, k); assertFalse(i.hasNext()); - Iterator j = sm.iterator(); + Iterator j = sm.iterator(); j.next(); j.remove(); - assertFalse(set.contains(two)); - assertEquals(4, set.size()); - assertEquals(1, sm.size()); - assertEquals(three, sm.first()); - assertEquals(three, sm.last()); - assertTrue(sm.remove(three)); + mustNotContain(set, two); + mustEqual(4, set.size()); + mustEqual(1, sm.size()); + mustEqual(three, sm.first()); + mustEqual(three, sm.last()); + mustRemove(sm, three); assertTrue(sm.isEmpty()); - assertEquals(3, set.size()); + mustEqual(3, set.size()); } public void testSubSetContents2() { - NavigableSet set = set5(); - SortedSet sm = set.subSet(two, three); - assertEquals(1, sm.size()); - assertEquals(two, sm.first()); - assertEquals(two, sm.last()); - assertFalse(sm.contains(one)); - assertTrue(sm.contains(two)); - assertFalse(sm.contains(three)); - assertFalse(sm.contains(four)); - assertFalse(sm.contains(five)); - Iterator i = sm.iterator(); - Object k; - k = (Integer)(i.next()); - assertEquals(two, k); + NavigableSet set = set5(); + SortedSet sm = set.subSet(two, three); + mustEqual(1, sm.size()); + mustEqual(two, sm.first()); + mustEqual(two, sm.last()); + mustNotContain(sm, one); + mustContain(sm, two); + mustNotContain(sm, three); + mustNotContain(sm, four); + mustNotContain(sm, five); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(two, k); assertFalse(i.hasNext()); - Iterator j = sm.iterator(); + Iterator j = sm.iterator(); j.next(); j.remove(); - assertFalse(set.contains(two)); - assertEquals(4, set.size()); - assertEquals(0, sm.size()); + mustNotContain(set, two); + mustEqual(4, set.size()); + mustEqual(0, sm.size()); assertTrue(sm.isEmpty()); assertFalse(sm.remove(three)); - assertEquals(4, set.size()); + mustEqual(4, set.size()); } /** * headSet returns set with keys in requested range */ public void testHeadSetContents() { - NavigableSet set = set5(); - SortedSet sm = set.headSet(four); - assertTrue(sm.contains(one)); - assertTrue(sm.contains(two)); - assertTrue(sm.contains(three)); - assertFalse(sm.contains(four)); - assertFalse(sm.contains(five)); - Iterator i = sm.iterator(); - Object k; - k = (Integer)(i.next()); - assertEquals(one, k); - k = (Integer)(i.next()); - assertEquals(two, k); - k = (Integer)(i.next()); - assertEquals(three, k); + NavigableSet set = set5(); + SortedSet sm = set.headSet(four); + mustContain(sm, one); + mustContain(sm, two); + mustContain(sm, three); + mustNotContain(sm, four); + mustNotContain(sm, five); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(one, k); + k = i.next(); + mustEqual(two, k); + k = i.next(); + mustEqual(three, k); assertFalse(i.hasNext()); sm.clear(); assertTrue(sm.isEmpty()); - assertEquals(2, set.size()); - assertEquals(four, set.first()); + mustEqual(2, set.size()); + mustEqual(four, set.first()); } /** * tailSet returns set with keys in requested range */ public void testTailSetContents() { - NavigableSet set = set5(); - SortedSet sm = set.tailSet(two); + NavigableSet set = set5(); + SortedSet sm = set.tailSet(two); + mustNotContain(sm, one); + mustContain(sm, two); + mustContain(sm, three); + mustContain(sm, four); + mustContain(sm, five); assertFalse(sm.contains(one)); assertTrue(sm.contains(two)); assertTrue(sm.contains(three)); assertTrue(sm.contains(four)); assertTrue(sm.contains(five)); - Iterator i = sm.iterator(); - Object k; - k = (Integer)(i.next()); - assertEquals(two, k); - k = (Integer)(i.next()); - assertEquals(three, k); - k = (Integer)(i.next()); - assertEquals(four, k); - k = (Integer)(i.next()); - assertEquals(five, k); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(two, k); + k = i.next(); + mustEqual(three, k); + k = i.next(); + mustEqual(four, k); + k = i.next(); + mustEqual(five, k); + assertFalse(i.hasNext()); + + SortedSet ssm = sm.tailSet(four); + mustEqual(four, ssm.first()); + mustEqual(five, ssm.last()); + mustRemove(ssm, four); + mustEqual(1, ssm.size()); + mustEqual(3, sm.size()); + mustEqual(4, set.size()); + } + + /** + * size changes when elements added and removed + */ + public void testDescendingSize() { + NavigableSet q = populatedSet(SIZE); + for (int i = 0; i < SIZE; ++i) { + mustEqual(SIZE - i, q.size()); + q.pollFirst(); + } + for (int i = 0; i < SIZE; ++i) { + mustEqual(i, q.size()); + mustAdd(q, i); + } + } + + /** + * add(null) throws NPE + */ + public void testDescendingAddNull() { + NavigableSet q = dset0(); + try { + q.add(null); + shouldThrow(); + } catch (NullPointerException success) {} + } + + /** + * Add of comparable element succeeds + */ + public void testDescendingAdd() { + NavigableSet q = dset0(); + assertTrue(q.add(minusSix)); + } + + /** + * Add of duplicate element fails + */ + public void testDescendingAddDup() { + NavigableSet q = dset0(); + assertTrue(q.add(minusSix)); + assertFalse(q.add(minusSix)); + } + + /** + * Add of non-Comparable throws CCE + */ + public void testDescendingAddNonComparable() { + NavigableSet q = new ConcurrentSkipListSet<>(); + try { + q.add(new Object()); + q.add(new Object()); + shouldThrow(); + } catch (ClassCastException success) {} + } + + /** + * addAll(null) throws NPE + */ + public void testDescendingAddAll1() { + NavigableSet q = dset0(); + try { + q.addAll(null); + shouldThrow(); + } catch (NullPointerException success) {} + } + + /** + * addAll of a collection with null elements throws NPE + */ + public void testDescendingAddAll2() { + NavigableSet q = dset0(); + Item[] items = new Item[1]; + try { + q.addAll(Arrays.asList(items)); + shouldThrow(); + } catch (NullPointerException success) {} + } + + /** + * addAll of a collection with any null elements throws NPE after + * possibly adding some elements + */ + public void testDescendingAddAll3() { + NavigableSet q = dset0(); + Item[] items = new Item[2]; items[0] = zero; + try { + q.addAll(Arrays.asList(items)); + shouldThrow(); + } catch (NullPointerException success) {} + } + + /** + * Set contains all elements of successful addAll + */ + public void testDescendingAddAll5() { + Item[] empty = new Item[0]; + Item[] items = new Item[SIZE]; + for (int i = 0; i < SIZE; ++i) + items[i] = itemFor(SIZE - 1 - i); + NavigableSet q = dset0(); + assertFalse(q.addAll(Arrays.asList(empty))); + assertTrue(q.addAll(Arrays.asList(items))); + for (int i = 0; i < SIZE; ++i) + mustEqual(i, q.pollFirst()); + } + + /** + * poll succeeds unless empty + */ + public void testDescendingPoll() { + NavigableSet q = populatedSet(SIZE); + for (int i = 0; i < SIZE; ++i) { + mustEqual(i, q.pollFirst()); + } + assertNull(q.pollFirst()); + } + + /** + * remove(x) removes x and returns true if present + */ + public void testDescendingRemoveElement() { + NavigableSet q = populatedSet(SIZE); + for (int i = 1; i < SIZE; i += 2) { + mustRemove(q, i); + } + for (int i = 0; i < SIZE; i += 2 ) { + mustRemove(q, i); + mustNotRemove(q, i + 1); + } + assertTrue(q.isEmpty()); + } + + /** + * contains(x) reports true when elements added but not yet removed + */ + public void testDescendingContains() { + NavigableSet q = populatedSet(SIZE); + for (int i = 0; i < SIZE; ++i) { + mustContain(q, i); + q.pollFirst(); + mustNotContain(q, i); + } + } + + /** + * clear removes all elements + */ + public void testDescendingClear() { + NavigableSet q = populatedSet(SIZE); + q.clear(); + assertTrue(q.isEmpty()); + mustEqual(0, q.size()); + mustAdd(q, one); + assertFalse(q.isEmpty()); + q.clear(); + assertTrue(q.isEmpty()); + } + + /** + * containsAll(c) is true when c contains a subset of elements + */ + public void testDescendingContainsAll() { + NavigableSet q = populatedSet(SIZE); + NavigableSet p = dset0(); + for (int i = 0; i < SIZE; ++i) { + assertTrue(q.containsAll(p)); + assertFalse(p.containsAll(q)); + mustAdd(p, i); + } + assertTrue(p.containsAll(q)); + } + + /** + * retainAll(c) retains only those elements of c and reports true if changed + */ + public void testDescendingRetainAll() { + NavigableSet q = populatedSet(SIZE); + NavigableSet p = populatedSet(SIZE); + for (int i = 0; i < SIZE; ++i) { + boolean changed = q.retainAll(p); + if (i == 0) + assertFalse(changed); + else + assertTrue(changed); + + assertTrue(q.containsAll(p)); + mustEqual(SIZE - i, q.size()); + p.pollFirst(); + } + } + + /** + * removeAll(c) removes only those elements of c and reports true if changed + */ + public void testDescendingRemoveAll() { + for (int i = 1; i < SIZE; ++i) { + NavigableSet q = populatedSet(SIZE); + NavigableSet p = populatedSet(i); + assertTrue(q.removeAll(p)); + mustEqual(SIZE - i, q.size()); + for (int j = 0; j < i; ++j) { + mustNotContain(q, p.pollFirst()); + } + } + } + + /** + * lower returns preceding element + */ + public void testDescendingLower() { + NavigableSet q = dset5(); + Object e1 = q.lower(minusThree); + mustEqual(minusTwo, e1); + + Object e2 = q.lower(minusSix); + mustEqual(minusFive, e2); + + Object e3 = q.lower(minusOne); + assertNull(e3); + + Object e4 = q.lower(zero); + assertNull(e4); + } + + /** + * higher returns next element + */ + public void testDescendingHigher() { + NavigableSet q = dset5(); + Object e1 = q.higher(minusThree); + mustEqual(minusFour, e1); + + Object e2 = q.higher(zero); + mustEqual(minusOne, e2); + + Object e3 = q.higher(minusFive); + assertNull(e3); + + Object e4 = q.higher(minusSix); + assertNull(e4); + } + + /** + * floor returns preceding element + */ + public void testDescendingFloor() { + NavigableSet q = dset5(); + Object e1 = q.floor(minusThree); + mustEqual(minusThree, e1); + + Object e2 = q.floor(minusSix); + mustEqual(minusFive, e2); + + Object e3 = q.floor(minusOne); + mustEqual(minusOne, e3); + + Object e4 = q.floor(zero); + assertNull(e4); + } + + /** + * ceiling returns next element + */ + public void testDescendingCeiling() { + NavigableSet q = dset5(); + Object e1 = q.ceiling(minusThree); + mustEqual(minusThree, e1); + + Object e2 = q.ceiling(zero); + mustEqual(minusOne, e2); + + Object e3 = q.ceiling(minusFive); + mustEqual(minusFive, e3); + + Object e4 = q.ceiling(minusSix); + assertNull(e4); + } + + /** + * toArray contains all elements + */ + public void testDescendingToArray() { + NavigableSet q = populatedSet(SIZE); + Object[] o = q.toArray(); + Arrays.sort(o); + for (int i = 0; i < o.length; i++) + mustEqual(o[i], q.pollFirst()); + } + + /** + * toArray(a) contains all elements + */ + public void testDescendingToArray2() { + NavigableSet q = populatedSet(SIZE); + Item[] items = new Item[SIZE]; + assertSame(items, q.toArray(items)); + Arrays.sort(items); + for (int i = 0; i < items.length; i++) + mustEqual(items[i], q.pollFirst()); + } + + /** + * iterator iterates through all elements + */ + public void testDescendingIterator() { + NavigableSet q = populatedSet(SIZE); + int i = 0; + Iterator it = q.iterator(); + while (it.hasNext()) { + mustContain(q, it.next()); + ++i; + } + mustEqual(i, SIZE); + } + + /** + * iterator of empty set has no elements + */ + public void testDescendingEmptyIterator() { + NavigableSet q = dset0(); + int i = 0; + Iterator it = q.iterator(); + while (it.hasNext()) { + mustContain(q, it.next()); + ++i; + } + mustEqual(0, i); + } + + /** + * iterator.remove removes current element + */ + public void testDescendingIteratorRemove() { + final NavigableSet q = dset0(); + q.add(two); + q.add(one); + q.add(three); + + Iterator it = q.iterator(); + it.next(); + it.remove(); + + it = q.iterator(); + mustEqual(it.next(), two); + mustEqual(it.next(), three); + assertFalse(it.hasNext()); + } + + /** + * toString contains toStrings of elements + */ + public void testDescendingToString() { + NavigableSet q = populatedSet(SIZE); + String s = q.toString(); + for (int i = 0; i < SIZE; ++i) { + assertTrue(s.contains(String.valueOf(i))); + } + } + + /** + * A deserialized/reserialized set equals original + */ + public void testDescendingSerialization() throws Exception { + NavigableSet x = dset5(); + NavigableSet y = serialClone(x); + + assertNotSame(y, x); + mustEqual(x.size(), y.size()); + mustEqual(x, y); + mustEqual(y, x); + while (!x.isEmpty()) { + assertFalse(y.isEmpty()); + mustEqual(x.pollFirst(), y.pollFirst()); + } + assertTrue(y.isEmpty()); + } + + /** + * subSet returns set with keys in requested range + */ + public void testDescendingSubSetContents() { + NavigableSet set = dset5(); + SortedSet sm = set.subSet(minusTwo, minusFour); + mustEqual(minusTwo, sm.first()); + mustEqual(minusThree, sm.last()); + mustEqual(2, sm.size()); + mustNotContain(sm, minusOne); + mustContain(sm, minusTwo); + mustContain(sm, minusThree); + mustNotContain(sm, minusFour); + mustNotContain(sm, minusFive); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(minusTwo, k); + k = i.next(); + mustEqual(minusThree, k); + assertFalse(i.hasNext()); + Iterator j = sm.iterator(); + j.next(); + j.remove(); + mustNotContain(set, minusTwo); + mustEqual(4, set.size()); + mustEqual(1, sm.size()); + mustEqual(minusThree, sm.first()); + mustEqual(minusThree, sm.last()); + mustRemove(sm, minusThree); + assertTrue(sm.isEmpty()); + mustEqual(3, set.size()); + } + + public void testDescendingSubSetContents2() { + NavigableSet set = dset5(); + SortedSet sm = set.subSet(minusTwo, minusThree); + mustEqual(1, sm.size()); + mustEqual(minusTwo, sm.first()); + mustEqual(minusTwo, sm.last()); + mustNotContain(sm, minusOne); + mustContain(sm, minusTwo); + mustNotContain(sm, minusThree); + mustNotContain(sm, minusFour); + mustNotContain(sm, minusFive); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(minusTwo, k); + assertFalse(i.hasNext()); + Iterator j = sm.iterator(); + j.next(); + j.remove(); + mustNotContain(set, minusTwo); + mustEqual(4, set.size()); + mustEqual(0, sm.size()); + assertTrue(sm.isEmpty()); + mustNotRemove(sm, minusThree); + mustEqual(4, set.size()); + } + + /** + * headSet returns set with keys in requested range + */ + public void testDescendingHeadSetContents() { + NavigableSet set = dset5(); + SortedSet sm = set.headSet(minusFour); + mustContain(sm, minusOne); + mustContain(sm, minusTwo); + mustContain(sm, minusThree); + mustNotContain(sm, minusFour); + mustNotContain(sm, minusFive); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(minusOne, k); + k = i.next(); + mustEqual(minusTwo, k); + k = i.next(); + mustEqual(minusThree, k); + assertFalse(i.hasNext()); + sm.clear(); + assertTrue(sm.isEmpty()); + mustEqual(2, set.size()); + mustEqual(minusFour, set.first()); + } + + /** + * tailSet returns set with keys in requested range + */ + public void testDescendingTailSetContents() { + NavigableSet set = dset5(); + SortedSet sm = set.tailSet(minusTwo); + mustNotContain(sm, minusOne); + mustContain(sm, minusTwo); + mustContain(sm, minusThree); + mustContain(sm, minusFour); + mustContain(sm, minusFive); + Iterator i = sm.iterator(); + Item k = i.next(); + mustEqual(minusTwo, k); + k = i.next(); + mustEqual(minusThree, k); + k = i.next(); + mustEqual(minusFour, k); + k = i.next(); + mustEqual(minusFive, k); assertFalse(i.hasNext()); - SortedSet ssm = sm.tailSet(four); - assertEquals(four, ssm.first()); - assertEquals(five, ssm.last()); - assertTrue(ssm.remove(four)); - assertEquals(1, ssm.size()); - assertEquals(3, sm.size()); - assertEquals(4, set.size()); + SortedSet ssm = sm.tailSet(minusFour); + mustEqual(minusFour, ssm.first()); + mustEqual(minusFive, ssm.last()); + mustRemove(ssm, minusFour); + mustEqual(1, ssm.size()); + mustEqual(3, sm.size()); + mustEqual(4, set.size()); } }