static class MyReverseComparator implements Comparator,Serializable {

private static final long serialVersionUID = 6921783514838686569L;

public int compare(Object x, Object y) {

return ((Comparable)y).compareTo(x);

}

}

/**

private NavigableSet<Integer> populatedSet(int n) {

NavigableSet<Integer> q = DBMaker.newMemoryDB().make().getTreeSet("test");

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)));

assertFalse(q.isEmpty());

assertEquals(n, q.size());

return q;

}

/**

private NavigableSet set5() {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

assertTrue(q.isEmpty());

q.add(one);

q.add(two);

q.add(three);

q.add(four);

q.add(five);

assertEquals(5, q.size());

return q;

}

/**

public void testConstructor1() {

assertEquals(0, DBMaker.newMemoryDB().make().getTreeSet("test").size());

}

/**

public void testConstructor7() {

MyReverseComparator cmp = new MyReverseComparator();

NavigableSet q =

DBMaker.newMemoryDB().make().createTreeSet("test").comparator(cmp).make();

assertEquals(cmp, q.comparator());

Integer[] ints = new Integer[SIZE];

for (int i = 0; i < SIZE; ++i)

ints[i] = new Integer(i);

q.addAll(Arrays.asList(ints));

for (int i = SIZE-1; i >= 0; --i)

assertEquals(ints[i], q.pollFirst());

}

/**

public void testEmpty() {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

assertTrue(q.isEmpty());

q.add(new Integer(1));

assertFalse(q.isEmpty());

q.add(new Integer(2));

q.pollFirst();

q.pollFirst();

assertTrue(q.isEmpty());

}

/**

public void testSize() {

NavigableSet q = populatedSet(SIZE);

for (int i = 0; i < SIZE; ++i) {

assertEquals(SIZE-i, q.size());

q.pollFirst();

}

for (int i = 0; i < SIZE; ++i) {

assertEquals(i, q.size());

q.add(new Integer(i));

}

}

/**

public void testAddNull() {

try {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

q.add(null);

shouldThrow();

} catch (NullPointerException success) {}

}

/**

public void testAdd() {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

assertTrue(q.add(zero));

assertTrue(q.add(one));

}

/**

public void testAddDup() {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

assertTrue(q.add(zero));

assertFalse(q.add(zero));

}

/**

public void testAddNonComparable() {

try {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

q.add(new Object());

q.add(new Object());

q.add(new Object());

shouldThrow();

} catch (ClassCastException success) {}

}

/**

public void testAddAll1() {

try {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

q.addAll(null);

shouldThrow();

} catch (NullPointerException success) {}

}

/**

public void testAddAll2() {

try {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

Integer[] ints = new Integer[SIZE];

q.addAll(Arrays.asList(ints));

shouldThrow();

} catch (NullPointerException success) {}

}

/**

public void testAddAll3() {

try {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

Integer[] ints = new Integer[SIZE];

for (int i = 0; i < SIZE-1; ++i)

ints[i] = new Integer(i);

q.addAll(Arrays.asList(ints));

shouldThrow();

} catch (NullPointerException success) {}

}

/**

public void testAddAll5() {

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 = DBMaker.newMemoryDB().make().getTreeSet("test");

assertFalse(q.addAll(Arrays.asList(empty)));

assertTrue(q.addAll(Arrays.asList(ints)));

for (int i = 0; i < SIZE; ++i)

assertEquals(i, q.pollFirst());

}

/**

public void testPollFirst() {

NavigableSet q = populatedSet(SIZE);

for (int i = 0; i < SIZE; ++i) {

assertEquals(i, q.pollFirst());

}

assertNull(q.pollFirst());

}

/**

public void testPollLast() {

NavigableSet q = populatedSet(SIZE);

for (int i = SIZE-1; i >= 0; --i) {

assertEquals(i, q.pollLast());

}

assertNull(q.pollFirst());

}

/**

public void testRemoveElement() {

NavigableSet q = populatedSet(SIZE);

for (int i = 1; i < SIZE; i+=2) {

assertTrue(q.contains(i));

assertTrue(q.remove(i));

assertFalse(q.contains(i));

assertTrue(q.contains(i-1));

}

for (int i = 0; i < SIZE; i+=2) {

assertTrue(q.contains(i));

assertTrue(q.remove(i));

assertFalse(q.contains(i));

assertFalse(q.remove(i + 1));

assertFalse(q.contains(i + 1));

}

assertTrue(q.isEmpty());

}

/**

public void testContains() {

NavigableSet q = populatedSet(SIZE);

for (int i = 0; i < SIZE; ++i) {

assertTrue(q.contains(new Integer(i)));

q.pollFirst();

assertFalse(q.contains(new Integer(i)));

}

}

/**

public void testClear() {

NavigableSet q = populatedSet(SIZE);

q.clear();

assertTrue(q.isEmpty());

assertEquals(0, q.size());

q.add(new Integer(1));

assertFalse(q.isEmpty());

q.clear();

assertTrue(q.isEmpty());

}

/**

public void testContainsAll() {

NavigableSet q = populatedSet(SIZE);

NavigableSet p = DBMaker.newMemoryDB().make().getTreeSet("test");

for (int i = 0; i < SIZE; ++i) {

assertTrue(q.containsAll(p));

assertFalse(p.containsAll(q));

p.add(new Integer(i));

}

assertTrue(p.containsAll(q));

}

/**

public void testRetainAll() {

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));

assertEquals(SIZE-i, q.size());

p.pollFirst();

}

}

/**

public void testRemoveAll() {

for (int i = 1; i < SIZE; ++i) {

NavigableSet q = populatedSet(SIZE);

NavigableSet p = populatedSet(i);

assertTrue(q.removeAll(p));

assertEquals(SIZE-i, q.size());

for (int j = 0; j < i; ++j) {

Integer I = (Integer)(p.pollFirst());

assertFalse(q.contains(I));

}

}

}

/**

public void testLower() {

NavigableSet q = set5();

Object e1 = q.lower(three);

assertEquals(two, e1);

Object e2 = q.lower(six);

assertEquals(five, e2);

Object e3 = q.lower(one);

assertNull(e3);

Object e4 = q.lower(zero);

assertNull(e4);

}

/**

public void testHigher() {

NavigableSet q = set5();

Object e1 = q.higher(three);

assertEquals(four, e1);

Object e2 = q.higher(zero);

assertEquals(one, e2);

Object e3 = q.higher(five);

assertNull(e3);

Object e4 = q.higher(six);

assertNull(e4);

}

/**

public void testFloor() {

NavigableSet q = set5();

Object e1 = q.floor(three);

assertEquals(three, e1);

Object e2 = q.floor(six);

assertEquals(five, e2);

Object e3 = q.floor(one);

assertEquals(one, e3);

Object e4 = q.floor(zero);

assertNull(e4);

}

/**

public void testCeiling() {

NavigableSet q = set5();

Object e1 = q.ceiling(three);

assertEquals(three, e1);

Object e2 = q.ceiling(zero);

assertEquals(one, e2);

Object e3 = q.ceiling(five);

assertEquals(five, e3);

Object e4 = q.ceiling(six);

assertNull(e4);

}

/**

public void testToArray() {

NavigableSet q = populatedSet(SIZE);

Object[] o = q.toArray();

for (int i = 0; i < o.length; i++)

assertSame(o[i], q.pollFirst());

}

/**

public void testToArray2() {

NavigableSet<Integer> q = populatedSet(SIZE);

Integer[] ints = new Integer[SIZE];

assertSame(ints, q.toArray(ints));

for (int i = 0; i < ints.length; i++)

assertSame(ints[i], q.pollFirst());

}

/**

public void testIterator() {

NavigableSet q = populatedSet(SIZE);

int i = 0;

Iterator it = q.iterator();

while (it.hasNext()) {

assertTrue(q.contains(it.next()));

++i;

}

assertEquals(i, SIZE);

}

/**

public void testEmptyIterator() {

NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

int i = 0;

Iterator it = q.iterator();

while (it.hasNext()) {

assertTrue(q.contains(it.next()));

++i;

}

assertEquals(0, i);

}

/**

public void testIteratorRemove() {

final NavigableSet q = DBMaker.newMemoryDB().make().getTreeSet("test");

q.add(new Integer(2));

q.add(new Integer(1));

q.add(new Integer(3));

Iterator it = q.iterator();

it.next();

it.remove();

it = q.iterator();

assertEquals(it.next(), new Integer(2));

assertEquals(it.next(), new Integer(3));

assertFalse(it.hasNext());

}

/**

public void testToString() {

NavigableSet q = populatedSet(SIZE);

String s = q.toString();

for (int i = 0; i < SIZE; ++i) {

assertTrue(s.contains(String.valueOf(i)));

}

}

/**

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);

assertFalse(i.hasNext());

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));

assertTrue(sm.isEmpty());

assertEquals(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);

assertFalse(i.hasNext());

Iterator j = sm.iterator();

j.next();

j.remove();

assertFalse(set.contains(two));

assertEquals(4, set.size());

assertEquals(0, sm.size());

assertTrue(sm.isEmpty());

assertFalse(sm.remove(three));

assertEquals(4, set.size());

}

/**

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);

assertFalse(i.hasNext());

sm.clear();

assertTrue(sm.isEmpty());

assertEquals(2, set.size());

assertEquals(four, set.first());

}

/**

public void testTailSetContents() {

NavigableSet set = set5();

SortedSet sm = set.tailSet(two);

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);

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());

}

Random rnd = new Random(666);

final boolean expensiveTests = true;

/**

public void testRecursiveSubSets() throws Exception {

int setSize = expensiveTests ? 1000 : 100;

Class cl = NavigableSet.class;

NavigableSet<Integer> set = newSet(cl);

BitSet bs = new BitSet(setSize);

populate(set, setSize, bs);

check(set, 0, setSize - 1, true, bs);

check(set.descendingSet(), 0, setSize - 1, false, bs);

mutateSet(set, 0, setSize - 1, bs);

check(set, 0, setSize - 1, true, bs);

check(set.descendingSet(), 0, setSize - 1, false, bs);

bashSubSet(set.subSet(0, true, setSize, false),

0, setSize - 1, true, bs);

}

/**

public void testAddAll_idempotent() throws Exception {

Set x = populatedSet(SIZE);

Set y = DBMaker.newMemoryDB().make().getTreeSet("test");

y.addAll(x);

assertEquals(x, y);

assertEquals(y, x);

}

static NavigableSet<Integer> newSet(Class cl) throws Exception {

NavigableSet<Integer> result = DBMaker.newMemoryDB().make().getTreeSet("test");

//(NavigableSet<Integer>) cl.newInstance();

assertEquals(0, result.size());

assertFalse(result.iterator().hasNext());

return result;

}

void populate(NavigableSet<Integer> set, int limit, BitSet bs) {

for (int i = 0, n = 2 * limit / 3; i < n; i++) {

int element = rnd.nextInt(limit);

put(set, element, bs);

}

}

void mutateSet(NavigableSet<Integer> set, int min, int max, BitSet bs) {

int size = set.size();

int rangeSize = max - min + 1;

// Remove a bunch of entries directly

for (int i = 0, n = rangeSize / 2; i < n; i++) {

remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);

}

// Remove a bunch of entries with iterator

for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {

if (rnd.nextBoolean()) {

bs.clear(it.next());

it.remove();

}

}

// Add entries till we're back to original size

while (set.size() < size) {

int element = min + rnd.nextInt(rangeSize);

assertTrue(element >= min && element<= max);

put(set, element, bs);

}

}

void mutateSubSet(NavigableSet<Integer> set, int min, int max,

BitSet bs) {

int size = set.size();

int rangeSize = max - min + 1;

// Remove a bunch of entries directly

for (int i = 0, n = rangeSize / 2; i < n; i++) {

remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);

}

// Remove a bunch of entries with iterator

for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {

if (rnd.nextBoolean()) {

bs.clear(it.next());

it.remove();

}

}

// Add entries till we're back to original size

while (set.size() < size) {

int element = min - 5 + rnd.nextInt(rangeSize + 10);

if (element >= min && element<= max) {

put(set, element, bs);

} else {

try {

set.add(element);

shouldThrow();

} catch (IllegalArgumentException success) {}

}

}

}

void put(NavigableSet<Integer> set, int element, BitSet bs) {

if (set.add(element))

bs.set(element);

}

void remove(NavigableSet<Integer> set, int element, BitSet bs) {

if (set.remove(element))

bs.clear(element);

}

void bashSubSet(NavigableSet<Integer> set,

int min, int max, boolean ascending,

BitSet bs) {

check(set, min, max, ascending, bs);

check(set.descendingSet(), min, max, !ascending, bs);

mutateSubSet(set, min, max, bs);

check(set, min, max, ascending, bs);

check(set.descendingSet(), min, max, !ascending, bs);

// Recurse

if (max - min < 2)

return;

int midPoint = (min + max) / 2;

// headSet - pick direction and endpoint inclusion randomly

boolean incl = rnd.nextBoolean();

NavigableSet<Integer> hm = set.headSet(midPoint, incl);

if (ascending) {

if (rnd.nextBoolean())

bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true, bs);

else

bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),

false, bs);

} else {

if (rnd.nextBoolean())

bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false, bs);

else

bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,

true, bs);

}

// tailSet - pick direction and endpoint inclusion randomly

incl = rnd.nextBoolean();

NavigableSet<Integer> tm = set.tailSet(midPoint,incl);

if (ascending) {

if (rnd.nextBoolean())

bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true, bs);

else

bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,

false, bs);

} else {

if (rnd.nextBoolean()) {

bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false, bs);

} else {

bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),

true, bs);

}

}

// subSet - pick direction and endpoint inclusion randomly

int rangeSize = max - min + 1;

int[] endpoints = new int[2];

endpoints[0] = min + rnd.nextInt(rangeSize);

endpoints[1] = min + rnd.nextInt(rangeSize);

Arrays.sort(endpoints);

boolean lowIncl = rnd.nextBoolean();

boolean highIncl = rnd.nextBoolean();

if (ascending) {

NavigableSet<Integer> sm = set.subSet(

endpoints[0], lowIncl, endpoints[1], highIncl);

if (rnd.nextBoolean())

bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),

endpoints[1] - (highIncl ? 0 : 1), true, bs);

else

bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),

endpoints[1] - (highIncl ? 0 : 1), false, bs);

} else {

NavigableSet<Integer> sm = set.subSet(

endpoints[1], highIncl, endpoints[0], lowIncl);

if (rnd.nextBoolean())

bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),

endpoints[1] - (highIncl ? 0 : 1), false, bs);

else

bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),

endpoints[1] - (highIncl ? 0 : 1), true, bs);

}

}

/**

void check(NavigableSet<Integer> set,

final int min, final int max, final boolean ascending,

final BitSet bs) {

class ReferenceSet {

int lower(int element) {

return ascending ?

lowerAscending(element) : higherAscending(element);

}

int floor(int element) {

return ascending ?

floorAscending(element) : ceilingAscending(element);

}

int ceiling(int element) {

return ascending ?

ceilingAscending(element) : floorAscending(element);

}

int higher(int element) {

return ascending ?

higherAscending(element) : lowerAscending(element);

}

int first() {

return ascending ? firstAscending() : lastAscending();

}

int last() {

return ascending ? lastAscending() : firstAscending();

}

int lowerAscending(int element) {

return floorAscending(element - 1);

}

int floorAscending(int element) {

if (element < min)

return -1;

else if (element > max)

element = max;

// BitSet should support this! Test would run much faster

while (element >= min) {

if (bs.get(element))

return element;

element--;

}

return -1;

}

int ceilingAscending(int element) {

if (element < min)

element = min;

else if (element > max)

return -1;

int result = bs.nextSetBit(element);

return result > max ? -1 : result;

}

int higherAscending(int element) {

return ceilingAscending(element + 1);

}

private int firstAscending() {

int result = ceilingAscending(min);

return result > max ? -1 : result;

}

private int lastAscending() {

int result = floorAscending(max);

return result < min ? -1 : result;

}

}

ReferenceSet rs = new ReferenceSet();

// Test contents using containsElement

int size = 0;

for (int i = min; i <= max; i++) {

boolean bsContainsI = bs.get(i);

assertEquals(bsContainsI, set.contains(i));

if (bsContainsI)

size++;

}

assertEquals(size, set.size());

// Test contents using contains elementSet iterator

int size2 = 0;

int previousElement = -1;

for (int element : set) {

assertTrue(bs.get(element));

size2++;

assertTrue(previousElement < 0 || (ascending ?

element - previousElement > 0 : element - previousElement < 0));

previousElement = element;

}

assertEquals(size2, size);

// Test navigation ops

for (int element = min - 1; element <= max + 1; element++) {

assertEq(set.lower(element), rs.lower(element));

assertEq(set.floor(element), rs.floor(element));

assertEq(set.higher(element), rs.higher(element));

assertEq(set.ceiling(element), rs.ceiling(element));

}

// Test extrema

if (set.size() != 0) {

assertEq(set.first(), rs.first());

assertEq(set.last(), rs.last());

} else {

assertEq(rs.first(), -1);

assertEq(rs.last(), -1);

try {

set.first();

shouldThrow();

} catch (NoSuchElementException success) {}

try {

set.last();

shouldThrow();

} catch (NoSuchElementException success) {}

}

}

static void assertEq(Integer i, int j) {

if (i == null)

assertEquals(j, -1);

else

assertEquals((int) i, j);

}

static boolean eq(Integer i, int j) {

return i == null ? j == -1 : i == j;

}

}