Instructions
Requirements and Specifications
- Concerning the SortedSequence ADT
Source Code
package edu.uwm.cs351;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Stack;
import java.util.function.Consumer;
import edu.uwm.cs.junit.LockedTestCase;
/******************************************************************************
* A Sequence is an aggregate class with a cursor (not an iterator)
* The sequence can have a special "current element," which is specified and
* accessed through four methods
* (start, getCurrent, advance and isCurrent).
* A SortedSequence keeps the elements in non-decreasing order using a comparator.
* This class uses a binary search tree for its implementation.
******************************************************************************/
public class SortedSequence implements Cloneable {
private static class Node {
T data;
Node left, right;
Node(T d) {
data = d;
}
@Override
public String toString() {
return super.toString() + ":" + data;
}
@Override
public boolean equals(Object x) {
throw new RuntimeException("Don't use '.equals' on nodes!");
}
}
private Node root;
private Comparator comparator;
private int manyItems;
private Stack> cursorStack;
// do not modify, but also do not use. Used for internal testing
SortedSequence(boolean ignored) {
}
// DO NOT CHANGE: Used for reporting invariant problems
private static Consumer logger = (s) -> System.out.println("Invariant error found: " + s);
/**
* Used to report an error found when checking the invariant.
* By providing a string, this will help debugging the class if the invariant should fail.
*
* @param error string to print to report the exact error found
* @return false always
*/
private static boolean report(String error) {
logger.accept(error);
return false;
}
/**
* Return the number of nodes in a subtree.
*
* @param r subtree to examine, may be null
* @return number of nodes in the subtree rooted at r
*/
private int countNodes(Node r) {
if (r == null) {
return 0;
}
int result = 1;
if (r.left != null) {
result += countNodes(r.left);
}
if (r.right != null) {
result += countNodes(r.right);
}
return result;
}
/**
* Return the node (if any) which has the given data in it.
*
* @param r subtree to look for data in (e.g., root)
* @param data data to look for, may be null
* @return node with this data, may be null (if data is not in
* the tree in the place expected). This method may get caught in
* a loop if the tree is malformed.
*/
private Node findNode(Node r, E data) {
if (data == null || r == null) {
return null;
}
E currValue = r.data;
int diff = comparator.compare(currValue, data);
if (diff > 0) {
return findNode(r.left, data);
}
if (diff < 0) {
return findNode(r.right, data);
}
return r;
}
/**
* Return true if the argument node is reachable from the root
* using its key. As a special case, null is always reachable,
* but no node with null data should be reachable.
* This method runs in time proportional to the height of the tree.
*
* @param r node to look for in tree, may be null
* @return whether the node is in the tree in the expected place.
* This method may get caught in a loop if the tree is not well formed.
*/
private boolean isInTree(Node r) {
if (r == null) {
return true;
}
if (r.data == null) {
return false;
}
Node curr = root;
E rValue = r.data;
while(curr != null) {
if (curr == r) {
return true;
}
E currValue = curr.data;
int diff = comparator.compare(currValue, rValue);
if (diff > 0) {
curr = curr.left;
}
else {
curr = curr.right;
}
}
return false;
}
/**
* Return true if this subtree is a legal BST between bounds.
* This method assumes the comparator is not null.
*
* @param r root of subtree, may be null
* @param lo lower (inclusive) bound, if null then unbounded from below
* @param hi upper (exclusive) bound, if null then unbounded from above
* @param max a bound on height of the tree
* @return whether the subtree is a well formed in this range with height no more max.
* If "false" is returned, then a report will have been made
*/
private boolean checkInRange(Node r, E lo, E hi, int max) {
if (r == null) {
return true;
}
E currValue = r.data;
if (currValue == null) {
return report("null data");
}
if (max <= 0) {
return report("invalid height");
}
if (lo != null && comparator.compare(lo, currValue) > 0) {
return report("value out of range");
}
if (hi != null && comparator.compare(currValue, hi) >= 0) {
return report("value out of range");
}
boolean leftResult = checkInRange(r.left, lo, currValue, max - 1);
boolean rightResult = checkInRange(r.right, currValue, hi, max - 1);
return leftResult && rightResult;
}
/**
* Return true if the first parameter is the closest ancestor to the node that is greater
* than the node. Note: some nodes (e.g. the root) have no closest ancestor
* in the tree, and so this method succeeds for such nodes only if the first parameter is null.
*
* Exercise: what other nodes have this property?
* How can we implement this method with the minimum of special cases?
*
* @param a ancestor, may be null
* @param n node, may be null.
* If null, then this routine will return true because
* there is always a null in the tree with a as its ancestor
* @return whether a is the immediate greater ancestor of n
* @precondition the tree is well formed and a and n are both in the tree.
* These conditions are assumed, and may not be checked.
* This method does not use the comparator, just the structure of the tree.
*/
private boolean isImmediateGreaterAncestor(Node a, Node n) {
if (n == null) {
return true;
}
if (a == null) {
Node curr = root;
while(curr != null) {
if (curr == n) {
return true;
}
curr = curr.right;
}
return false;
}
else {
Node curr = a.left;
while(curr != null) {
if (curr == n) {
return true;
}
curr = curr.right;
}
return false;
}
}
/**
* Check the invariant.
* Return false if any problem is found. Returning the result
* of {@link #report(String)} will make it easier to debug invariant problems.
*
* @return whether invariant is currently true
*/
private boolean wellFormed() {
if (comparator == null) {
return report("null comparator");
}
if (cursorStack == null) {
return report("null stack");
}
Iterator> iterator = cursorStack.iterator();
Node prev = null;
while(iterator.hasNext()) {
Node curr = iterator.next();
if (curr == null) {
return report("invalid cursor stack");
}
if (!isInTree(curr)) {
return report("invalid cursor stack");
}
if (!isImmediateGreaterAncestor(prev, curr)) {
return report("invalid cursor stack");
}
prev = curr;
}
if (!checkInRange(root, null, null, manyItems)) {
return false;
}
if (countNodes(root) != manyItems) {
return report("wrong element count");
}
return true;
}
/**
* Create an empty sequence.
*
* @param c comparator to order element, must not be null
* @postcondition This sequence is empty
**/
public SortedSequence(Comparator c) {
comparator = c;
manyItems = 0;
root = null;
cursorStack = new Stack<>();
assert wellFormed() : "invariant failed in constructor";
}
/**
* Determine the number of elements in this sequence.
*
* @return the number of elements in this sequence
**/
public int size() {
assert wellFormed() : "invariant wrong at start of size()";
return manyItems;
}
/**
* Set the current element at the front of this sequence.
*
* This operation runs in time proportional to the height of the tree.
*
* @postcondition The front element of this sequence is now the current element (but
* if this sequence has no elements at all, then there is no current
* element).
**/
public void start() {
assert wellFormed() : "invariant wrong at start of start()";
cursorStack.clear();
Node curr = root;
while (curr != null) {
cursorStack.add(curr);
curr = curr.left;
}
assert wellFormed() : "invariant wrong at end of start()";
}
/**
* Accessor method to determine whether this sequence has a specified
* current element that can be retrieved with the
* getCurrent method.
*
* This is a constant-time operation.
*
* @return true (there is a current element) or false (there is no current element at the moment)
**/
public boolean isCurrent() {
assert wellFormed() : "invariant wrong at start of getCurrent()";
return !cursorStack.isEmpty();
}
/**
* Accessor method to get the current element of this sequence.
*
* This is a constant-time operation.
*
* @return the current element of this sequence
* @throws IllegalStateException Indicates that there is no current element, so
* getCurrent may not be called.
* @precondition hasCurrent() returns true.
**/
public E getCurrent() {
assert wellFormed() : "invariant wrong at start of getCurrent()";
if (!isCurrent()) {
throw new IllegalStateException();
}
return cursorStack.peek().data;
}
/**
* Move forward, so that the current element will be the next element in
* this sequence.
*
* This operation runs in time proportional to the height of the tree.
*
* @throws IllegalStateException Indicates that there is no current element, so
* advance may not be called.
* @precondition hasCurrent() returns true.
* @postcondition If the current element was already the end element of this sequence
* (with nothing after it), then there is no longer any current element.
* Otherwise, the new element is the element immediately after the
* original current element.
**/
public void advance() {
assert wellFormed() : "invariant wrong at start of advance()";
if (!isCurrent()) {
throw new IllegalStateException();
}
Node curr = cursorStack.pop().right;
while (curr != null) {
cursorStack.push(curr);
curr = curr.left;
}
assert wellFormed() : "invariant wrong at end of advance()";
}
private void doAdd(Node r, E element) {
cursorStack.push(r);
E currValue = r.data;
int diff = comparator.compare(currValue, element);
if (diff > 0) {
if (r.left == null) {
Node newNode = new Node<>(element);
r.left = newNode;
cursorStack.push(newNode);
} else {
doAdd(r.left, element);
}
} else {
cursorStack.pop();
if (r.right == null) {
Node newNode = new Node<>(element);
r.right = newNode;
cursorStack.push(newNode);
} else {
doAdd(r.right, element);
}
}
}
/**
* Add a new element to this sequence, in the correct place according to the comparator.
* The new element becomes the new current element of this sequence.
*
* @param element the value that is being added, must not be null
* @throws NullPointerException if the element is null
**/
public void add(E element) {
if (element == null) {
throw new NullPointerException();
}
cursorStack.clear();
if (root == null) {
root = new Node<>(element);
cursorStack.push(root);
manyItems = 1;
} else {
doAdd(root, element);
manyItems++;
}
}
private Node getParent(Node curr, Node target) {
if (curr == null) {
return null;
}
E currValue = curr.data;
E targetValue = target.data;
int diff = comparator.compare(currValue, targetValue);
if (diff > 0) {
if (curr.left == target) {
return curr;
}
return getParent(curr.left, target);
}
else {
if (curr.right == target) {
return curr;
}
return getParent(curr.right, target);
}
}
/**
* Remove the current element from this sequence.
*
* @throws IllegalStateException Indicates that there is no current element, so
* removeCurrent may not be called.
* @precondition hasCurrent() returns true.
* @postcondition The current element has been removed from this sequence, and the
* following element (if there is one) is now the new current element.
* If there was no following element, then there is now no current
* element.
**/
public void removeCurrent() {
if (!isCurrent()) {
throw new IllegalStateException();
}
Node current = cursorStack.peek();
Node parent = getParent(root, current);
if (current.right == null && current.left == null) {
if (parent == null) {
root = null;
}
else if (parent.left == current) {
parent.left = null;
}
else {
parent.right = null;
}
cursorStack.pop();
manyItems--;
}
else if (current.right == null) {
if (parent == null) {
root = current.left;
}
else if (parent.left == current) {
parent.left = current.left;
}
else {
parent.right = current.left;
}
cursorStack.pop();
manyItems--;
}
else if (current.left == null) {
if (parent == null) {
root = current.right;
}
else if (parent.left == current) {
parent.left = current.right;
}
else {
parent.right = current.right;
}
cursorStack.pop();
Node curr = current.right;
while (curr != null) {
cursorStack.push(curr);
curr = curr.left;
}
manyItems--;
}
else {
Node curr = current.right;
if (curr.left == null) {
cursorStack.pop();
cursorStack.push(curr);
curr.left = current.left;
if (parent == null) {
root = curr;
}
else if (parent.left == current) {
parent.left = curr;
}
else {
parent.right = curr;
}
manyItems--;
return;
}
Node par = null;
while(curr.left != null) {
par = curr;
curr = curr.left;
}
Node newNode = par.left;
newNode.left = current.left;
newNode.right = current.right;
cursorStack.pop();
cursorStack.push(newNode);
par.left = null;
if (parent == null) {
root = newNode;
}
else if (parent.left == current) {
parent.left = newNode;
}
else {
parent.right = newNode;
}
manyItems--;
}
}
// We left out addAll and clone.
public static class TestInternals extends LockedTestCase {
private static String lastMessage;
private static Consumer saveMessage = (s) -> lastMessage = s;
private static Consumer errorMessage = (s) -> System.err.println("Erroneously reported problem: " + (lastMessage = s));
protected Comparator testComparator = (i1, i2) -> (i1 / 10 - i2 / 10);
protected SortedSequence self;
protected static final int NUM_NODES = 100;
protected Node[] nodes;
@SuppressWarnings("unchecked")
@Override
protected void setUp() {
self = new SortedSequence(false);
self.comparator = testComparator;
self.cursorStack = new Stack<>();
self.manyItems = -1;
self.root = null;
nodes = (Node[]) new Node[NUM_NODES];
for (int i = 0; i < nodes.length; ++i) {
nodes[i] = new Node<>(i);
if (i % 10 == 0) nodes[i].data = null;
}
logger = saveMessage;
}
protected void assertWellFormed(boolean expected) {
logger = expected ? errorMessage : saveMessage;
lastMessage = null;
assertEquals(expected, self.wellFormed());
logger = saveMessage;
if (expected == false) {
assertTrue("Didn't report problem", lastMessage != null && lastMessage.trim().length() > 0);
}
}
protected void assertInRange(boolean expected, Node r, Integer lo, Integer hi, int max) {
logger = expected ? errorMessage : saveMessage;
lastMessage = null;
assertEquals(expected, self.checkInRange(r, lo, hi, max));
logger = saveMessage;
if (expected == false) {
assertTrue("Didn't report problem", lastMessage != null && lastMessage.trim().length() > 0);
}
}
/// Count nodes tests
public void testC0() {
assertEquals(0, self.countNodes(null));
}
public void testC1() {
assertEquals(1, self.countNodes(nodes[0]));
}
public void testC2() {
nodes[1].left = nodes[2];
assertEquals(2, self.countNodes(nodes[1]));
}
public void testC3() {
nodes[3].right = nodes[4];
nodes[4].right = nodes[5];
assertEquals(3, self.countNodes(nodes[3]));
}
public void testC4() {
nodes[6].left = nodes[7];
nodes[7].right = nodes[8];
nodes[8].left = nodes[9];
assertEquals(4, self.countNodes(nodes[6]));
}
public void testC5() {
nodes[10].left = nodes[11];
nodes[10].right = nodes[12];
nodes[11].left = nodes[13];
nodes[11].right = nodes[14];
assertEquals(5, self.countNodes(nodes[10]));
}
public void testC6() {
nodes[15].right = nodes[16];
nodes[16].left = nodes[17];
nodes[17].left = nodes[18];
nodes[17].right = nodes[19];
nodes[19].right = nodes[20];
assertEquals(6, self.countNodes(nodes[15]));
}
public void testC7() {
nodes[21].left = nodes[22];
nodes[21].right = nodes[23];
nodes[22].left = nodes[24];
nodes[22].right = nodes[25];
nodes[23].left = nodes[26];
nodes[23].right = nodes[27];
assertEquals(7, self.countNodes(nodes[21]));
}
public void testC8() {
nodes[30].left = nodes[31];
nodes[30].right = nodes[31];
nodes[31].left = nodes[32];
nodes[31].right = nodes[32];
nodes[32].left = nodes[33];
nodes[32].right = nodes[33];
assertEquals(15, self.countNodes(nodes[30]));
}
public void testC9() {
int i = 1;
// hook up 99 nodes:
for (int j = 0; j < NUM_NODES / 2 - 1; ++j) {
nodes[j].left = nodes[i++];
nodes[j].right = nodes[i++];
}
assertEquals(NUM_NODES - 1, self.countNodes(nodes[0]));
}
/// Find in tree tests
public void testF0() {
assertNull(self.findNode(null, 42));
}
public void testF1() {
// 1 and 11 are NOT equivalent according to our comparator
assertNull(self.findNode(nodes[1], 11));
// 2 and 3 are equivalent according to our comparator
assertSame(nodes[2], self.findNode(nodes[2], 3));
assertNull(self.findNode(nodes[2], null)); // no crashing on null!
}
public void testF2() {
nodes[12].right = nodes[22];
nodes[12].left = nodes[32]; // not in correct place
assertSame(nodes[12], self.findNode(nodes[12], 10));
assertNull(self.findNode(nodes[12], 32));
assertSame(nodes[22], self.findNode(nodes[12], 21));
}
public void testF3() {
nodes[23].right = nodes[12]; // not in correct place
nodes[23].left = nodes[3];
assertSame(nodes[3], self.findNode(nodes[23], 9));
assertNull(self.findNode(nodes[23], 12));
}
public void testF4() {
nodes[4].right = nodes[34];
nodes[34].left = nodes[14];
nodes[14].right = nodes[24];
assertSame(nodes[4], self.findNode(nodes[4], 1));
assertSame(nodes[14], self.findNode(nodes[4], 11));
assertSame(nodes[24], self.findNode(nodes[4], 21));
assertSame(nodes[34], self.findNode(nodes[4], 31));
assertNull(self.findNode(nodes[4], 41));
}
public void testF5() {
nodes[55].left = nodes[5];
nodes[5].left = nodes[15];
nodes[5].right = nodes[35];
nodes[35].left = nodes[25];
nodes[35].right = nodes[45];
nodes[45].right = nodes[40];
nodes[40].data = 40;
assertSame(nodes[5], self.findNode(nodes[55], 0));
assertNull(self.findNode(nodes[55], 10));
assertSame(nodes[25], self.findNode(nodes[55], 20));
assertSame(nodes[35], self.findNode(nodes[55], 30));
assertSame(nodes[45], self.findNode(nodes[55], 40));
assertSame(nodes[55], self.findNode(nodes[55], 50));
}
// Is In tree tests
public void testI0() {
self.root = null;
assertFalse(self.isInTree(nodes[1]));
assertTrue(self.isInTree(null));
assertFalse(self.isInTree(nodes[0]));
try {
self.root = nodes[0];
assertFalse(self.isInTree(nodes[0])); // don't find node with null data!
} catch (RuntimeException ex) {
assertTrue(true); // OK to throw exception
}
}
public void testI1() {
self.root = nodes[2];
nodes[2].left = nodes[1]; // misplaced
nodes[22].data = nodes[2].data; // impostor
assertFalse(self.isInTree(nodes[1]));
assertTrue(self.isInTree(nodes[2]));
assertFalse(self.isInTree(nodes[22]));
assertTrue(self.isInTree(null));
assertFalse(self.isInTree(nodes[0])); // don't crash!
}
public void testI2() {
self.root = nodes[32];
nodes[32].left = nodes[12];
nodes[32].right = nodes[52];
nodes[12].right = nodes[2]; // misplaced
nodes[52].left = nodes[62]; // misplaced
assertFalse(self.isInTree(nodes[2]));
assertTrue(self.isInTree(nodes[12]));
assertTrue(self.isInTree(nodes[32]));
assertTrue(self.isInTree(nodes[52]));
assertFalse(self.isInTree(nodes[62]));
}
public void testI3() {
self.root = nodes[43];
nodes[43].left = nodes[13];
nodes[13].right = nodes[33];
nodes[33].right = nodes[23]; // misplaced
nodes[43].right = nodes[73];
nodes[73].left = nodes[63];
nodes[63].right = nodes[53]; // misplaced
nodes[73].right = nodes[83];
assertFalse(self.isInTree(nodes[3]));
assertTrue(self.isInTree(nodes[13]));
assertFalse(self.isInTree(nodes[23]));
assertTrue(self.isInTree(nodes[33]));
assertTrue(self.isInTree(nodes[43]));
assertFalse(self.isInTree(nodes[53]));
assertTrue(self.isInTree(nodes[63]));
assertTrue(self.isInTree(nodes[73]));
assertTrue(self.isInTree(nodes[83]));
assertFalse(self.isInTree(nodes[93]));
}
public void testI4() {
self.root = nodes[12];
nodes[12].right = nodes[13];
nodes[12].left = nodes[11]; // misplaced
nodes[3].data = nodes[13].data; // impostor
assertFalse(self.isInTree(nodes[3]));
assertFalse(self.isInTree(nodes[11]));
assertTrue(self.isInTree(nodes[12]));
assertTrue(self.isInTree(nodes[13]));
assertFalse(self.isInTree(nodes[10]));
assertTrue(self.isInTree(null));
}
public void testI5() {
self.root = nodes[13];
nodes[13].left = nodes[3];
nodes[13].right = nodes[23];
nodes[23].left = nodes[11];
nodes[23].right = nodes[17]; // misplaced
nodes[11].right = nodes[12];
nodes[1].data = nodes[11].data; // impostor
assertFalse(self.isInTree(nodes[1]));
assertTrue(self.isInTree(nodes[11]));
assertTrue(self.isInTree(nodes[12]));
assertTrue(self.isInTree(nodes[13]));
assertFalse(self.isInTree(nodes[17]));
assertTrue(self.isInTree(nodes[23]));
assertTrue(self.isInTree(null));
}
public void testI6() {
self.root = nodes[11];
Node target = nodes[16];
nodes[11].left = nodes[16];
nodes[11].right = nodes[96];
nodes[96].left = nodes[86];
nodes[96].right = target; // placed in many wrong places
assertFalse(self.isInTree(target));
nodes[86].left = nodes[12];
assertFalse(self.isInTree(target));
nodes[12].right = nodes[76];
assertFalse(self.isInTree(target));
nodes[76].left = nodes[66];
assertFalse(self.isInTree(target));
nodes[66].right = target;
assertFalse(self.isInTree(target));
nodes[66].left = nodes[56];
assertFalse(self.isInTree(target));
nodes[66].right = target;
assertFalse(self.isInTree(target));
nodes[56].right = target;
assertFalse(self.isInTree(target));
nodes[56].left = nodes[13];
assertFalse(self.isInTree(target));
nodes[13].right = nodes[14];
assertFalse(self.isInTree(target));
nodes[14].right = nodes[46];
assertFalse(self.isInTree(target));
nodes[46].left = nodes[15];
assertFalse(self.isInTree(target));
nodes[15].right = target;
assertTrue(self.isInTree(target)); // FINALLY
target.right = nodes[17];
assertTrue(self.isInTree(target));
nodes[17].right = nodes[36];
assertTrue(self.isInTree(target));
nodes[36].left = nodes[18];
assertTrue(self.isInTree(target));
}
/// check in Range tests
public void testR0() {
assertInRange(true, null, null, null, 0);
assertInRange(true, null, 10, null, 0);
assertInRange(true, null, null, 19, 0);
assertInRange(true, null, 10, 19, 0);
assertInRange(true, null, null, null, 1);
assertInRange(true, null, 10, 19, 1);
}
public void testR1() {
assertInRange(false, nodes[0], null, null, 1);
assertInRange(false, nodes[1], null, null, 0);
assertInRange(true, nodes[1], null, null, 1);
assertInRange(true, nodes[1], null, null, 2);
assertInRange(true, nodes[1], 9, null, 1);
assertInRange(true, nodes[1], 0, null, 1);
assertInRange(true, nodes[1], null, 10, 1);
assertInRange(true, nodes[1], 9, 10, 1);
assertInRange(false, nodes[1], null, 9, 1);
assertInRange(false, nodes[1], 10, null, 1);
}
public void testR2() {
nodes[2].right = nodes[3];
assertInRange(false, nodes[2], null, null, 0);
assertInRange(false, nodes[2], null, null, 1);
assertInRange(true, nodes[2], null, null, 2);
assertInRange(true, nodes[2], null, null, 3);
assertInRange(true, nodes[2], 9, null, 2);
assertInRange(true, nodes[2], 0, null, 2);
assertInRange(true, nodes[2], null, 10, 2);
assertInRange(true, nodes[2], 9, 10, 2);
assertInRange(false, nodes[2], null, 9, 2);
assertInRange(false, nodes[2], 10, null, 2);
nodes[3].left = nodes[4];
assertInRange(false, nodes[3], null, null, 2);
assertInRange(false, nodes[2], null, null, 3);
}
public void testR3() {
nodes[33].right = nodes[32];
nodes[32].right = nodes[31];
nodes[33].left = nodes[23];
nodes[23].right = nodes[22];
nodes[23].left = nodes[13];
assertInRange(false, nodes[33], null, null, 2);
assertInRange(true, nodes[33], null, null, 3);
assertInRange(true, nodes[33], 3, null, 3);
assertInRange(true, nodes[33], 13, null, 3);
assertInRange(true, nodes[33], 19, null, 3);
assertInRange(false, nodes[33], 20, null, 3);
assertInRange(true, nodes[33], null, 43, 3);
assertInRange(false, nodes[33], null, 39, 3);
assertInRange(true, nodes[33], 19, 40, 3);
assertInRange(false, nodes[33], 3, 39, 3);
assertInRange(false, nodes[33], 20, 53, 3);
nodes[32].left = nodes[34];
assertInRange(false, nodes[33], null, null, 3);
}
public void testR4() {
nodes[44].right = nodes[43];
nodes[43].right = nodes[53];
nodes[53].right = nodes[54];
nodes[53].left = nodes[42];
nodes[44].left = nodes[33];
nodes[33].right = nodes[32];
nodes[32].right = nodes[31];
nodes[33].left = nodes[14];
nodes[14].left = nodes[4];
nodes[14].right = nodes[24];
assertInRange(false, nodes[44], null, null, 0);
assertInRange(false, nodes[44], null, null, 1);
assertInRange(false, nodes[44], null, null, 2);
assertInRange(false, nodes[44], null, null, 3);
assertInRange(true, nodes[44], null, null, 4);
assertInRange(true, nodes[44], 9, 60, 4);
assertInRange(false, nodes[44], 10, null, 4);
assertInRange(false, nodes[44], null, 59, 4);
nodes[14].right = nodes[31];
assertInRange(false, nodes[44], null, null, 4);
}
public void testR5() {
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
assertInRange(false, nodes[55], null, null, 3);
assertInRange(true, nodes[55], null, null, 4);
assertInRange(true, nodes[55], null, null, 5);
nodes[5].right = nodes[14];
assertInRange(false, nodes[55], null, null, 5);
nodes[5].right = null;
nodes[14].left = nodes[9];
assertInRange(false, nodes[55], null, null, 5);
nodes[14].left = null;
nodes[14].right = nodes[23];
assertInRange(false, nodes[55], null, null, 5);
nodes[14].right = null;
nodes[24].left = nodes[19];
assertInRange(false, nodes[55], null, null, 5);
nodes[24].left = null;
nodes[24].right = nodes[34];
assertInRange(false, nodes[55], null, null, 5);
nodes[24].right = null;
nodes[45].left = nodes[29];
assertInRange(false, nodes[55], null, null, 5);
nodes[45].left = null;
nodes[45].right = nodes[53];
assertInRange(false, nodes[55], null, null, 5);
nodes[45].right = nodes[44];
assertInRange(true, nodes[55], null, null, 5);
nodes[54].left = nodes[49];
assertInRange(false, nodes[55], null, null, 5);
nodes[54].left = null;
nodes[54].right = nodes[64];
assertInRange(false, nodes[55], null, null, 5);
nodes[54].right = null;
nodes[64].left = nodes[63];
assertInRange(false, nodes[55], null, null, 5);
nodes[64].left = null;
nodes[64].right = nodes[74];
assertInRange(false, nodes[55], null, null, 5);
nodes[64].right = null;
nodes[74].left = nodes[69];
assertInRange(false, nodes[55], null, null, 5);
nodes[74].left = null;
nodes[74].right = nodes[84];
assertInRange(false, nodes[55], null, null, 5);
nodes[74].right = null;
nodes[95].left = nodes[79];
assertInRange(false, nodes[55], null, null, 5);
nodes[95].left = null;
nodes[95].right = nodes[94];
assertInRange(true, nodes[55], null, null, 5);
}
public void testR6() {
// same start as testR5:
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
assertInRange(false, nodes[55], null, null, 3);
assertInRange(true, nodes[55], null, null, 4);
assertInRange(true, nodes[55], null, null, 5);
nodes[5].left = nodes[0];
assertInRange(false, nodes[55], null, null, 5);
nodes[5].left = null;
nodes[5].right = nodes[10];
assertInRange(false, nodes[55], null, null, 5);
nodes[5].right = null;
nodes[14].left = nodes[0];
assertInRange(false, nodes[55], null, null, 5);
nodes[14].left = null;
nodes[14].right = nodes[20];
assertInRange(false, nodes[55], null, null, 5);
nodes[14].right = null;
nodes[24].left = nodes[10];
assertInRange(false, nodes[55], null, null, 5);
nodes[24].left = null;
nodes[24].right = nodes[30];
assertInRange(false, nodes[55], null, null, 5);
nodes[24].right = null;
nodes[45].left = nodes[20];
assertInRange(false, nodes[55], null, null, 5);
nodes[45].left = null;
nodes[45].right = nodes[50];
assertInRange(false, nodes[55], null, null, 5);
nodes[45].right = nodes[44];
assertInRange(true, nodes[55], null, null, 5);
nodes[54].left = nodes[40];
assertInRange(false, nodes[55], null, null, 5);
nodes[54].left = null;
nodes[54].right = nodes[60];
assertInRange(false, nodes[55], null, null, 5);
nodes[54].right = null;
nodes[64].left = nodes[60];
assertInRange(false, nodes[55], null, null, 5);
nodes[64].left = null;
nodes[64].right = nodes[70];
assertInRange(false, nodes[55], null, null, 5);
nodes[64].right = null;
nodes[74].left = nodes[60];
assertInRange(false, nodes[55], null, null, 5);
nodes[74].left = null;
nodes[74].right = nodes[80];
assertInRange(false, nodes[55], null, null, 5);
nodes[74].right = null;
nodes[95].left = nodes[70];
assertInRange(false, nodes[55], null, null, 5);
nodes[95].left = null;
nodes[95].right = nodes[90];
assertInRange(false, nodes[55], null, null, 5);
nodes[95].right = nodes[94];
assertInRange(true, nodes[55], null, null, 5);
}
public void testR7() {
for (int i = 0; i < 99; ++i) {
nodes[i].data = 42;
nodes[i].right = nodes[i + 1];
}
assertInRange(false, nodes[0], null, null, 99);
assertInRange(true, nodes[0], null, null, 100);
}
public void testR8() {
nodes[1].right = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[1].right = nodes[99];
nodes[99].left = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[99].left = nodes[2];
nodes[2].right = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[2].right = nodes[3];
nodes[3].right = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[3].right = nodes[88];
nodes[88].left = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[88].left = nodes[77];
nodes[77].left = nodes[1];
assertInRange(false, nodes[1], null, null, 100);
nodes[77].left = nodes[3];
assertInRange(false, nodes[1], null, null, 100);
nodes[77].left = nodes[2];
assertInRange(false, nodes[1], null, null, 100);
nodes[77].left = nodes[4];
assertInRange(true, nodes[1], null, null, 100);
}
public void testR9() {
// same start as testR5:
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
nodes[5].left = nodes[5];
assertInRange(false, nodes[55], null, null, 50);
nodes[5].left = null;
nodes[5].right = nodes[5];
assertInRange(false, nodes[55], null, null, 50);
nodes[5].right = nodes[15];
assertInRange(false, nodes[55], null, null, 50);
nodes[5].right = null;
nodes[14].left = nodes[15];
assertInRange(false, nodes[55], null, null, 50);
nodes[14].left = null;
nodes[14].right = nodes[15];
assertInRange(false, nodes[55], null, null, 50);
nodes[14].right = nodes[25];
assertInRange(false, nodes[55], null, null, 50);
nodes[14].right = null;
nodes[24].left = nodes[25];
assertInRange(false, nodes[55], null, null, 50);
nodes[24].left = null;
nodes[24].right = nodes[25];
assertInRange(false, nodes[55], null, null, 50);
nodes[24].right = nodes[35];
assertInRange(false, nodes[55], null, null, 50);
nodes[24].right = null;
nodes[45].left = nodes[35];
assertInRange(false, nodes[55], null, null, 50);
nodes[45].left = null;
nodes[45].right = nodes[35];
assertInRange(false, nodes[55], null, null, 50);
nodes[45].right = nodes[55];
assertInRange(false, nodes[55], null, null, 50);
nodes[45].right = nodes[44];
assertInRange(true, nodes[55], null, null, 50);
nodes[54].left = nodes[55];
assertInRange(false, nodes[55], null, null, 50);
nodes[54].left = null;
nodes[54].right = nodes[55];
assertInRange(false, nodes[55], null, null, 50);
nodes[54].right = nodes[65];
assertInRange(false, nodes[55], null, null, 50);
nodes[54].right = null;
nodes[64].left = nodes[65];
assertInRange(false, nodes[55], null, null, 50);
nodes[64].left = null;
nodes[64].right = nodes[65];
assertInRange(false, nodes[55], null, null, 50);
nodes[64].right = nodes[75];
assertInRange(false, nodes[55], null, null, 50);
nodes[64].right = null;
nodes[74].left = nodes[75];
assertInRange(false, nodes[55], null, null, 50);
nodes[74].left = null;
nodes[74].right = nodes[75];
assertInRange(false, nodes[55], null, null, 50);
nodes[74].right = nodes[85];
assertInRange(false, nodes[55], null, null, 50);
nodes[74].right = null;
nodes[95].left = nodes[85];
assertInRange(false, nodes[55], null, null, 50);
nodes[95].left = null;
nodes[95].right = nodes[85];
assertInRange(false, nodes[55], null, null, 50);
nodes[95].right = nodes[55];
assertInRange(false, nodes[55], null, null, 50);
nodes[95].right = nodes[94];
assertInRange(true, nodes[55], null, null, 50);
}
/// immediaTe greaTer ancesTor tests
public void testT0() {
self.root = null;
self.manyItems = 0;
assertTrue(self.isImmediateGreaterAncestor(null, null));
}
public void testT1() {
self.root = nodes[1];
self.manyItems = 1;
assertTrue(self.isImmediateGreaterAncestor(null, null));
assertTrue(self.isImmediateGreaterAncestor(nodes[1], null));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[1]));
assertFalse(self.isImmediateGreaterAncestor(nodes[1], nodes[1]));
}
public void testT2() {
self.root = nodes[2];
nodes[2].right = nodes[22];
assertTrue(self.isImmediateGreaterAncestor(null, null));
assertTrue(self.isImmediateGreaterAncestor(nodes[2], null));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[2]));
assertFalse(self.isImmediateGreaterAncestor(nodes[2], nodes[2]));
assertTrue(self.isImmediateGreaterAncestor(nodes[22], null));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[2], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[2]));
}
public void testT3() {
self.root = nodes[33];
nodes[33].left = nodes[3];
assertTrue(self.isImmediateGreaterAncestor(null, null));
assertTrue(self.isImmediateGreaterAncestor(nodes[3], null));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[3]));
assertFalse(self.isImmediateGreaterAncestor(nodes[3], nodes[3]));
assertTrue(self.isImmediateGreaterAncestor(nodes[33], null));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[3], nodes[33]));
assertTrue(self.isImmediateGreaterAncestor(nodes[33], nodes[3]));
}
public void testT4() {
self.root = nodes[44];
nodes[44].left = nodes[22];
nodes[44].right = nodes[66];
nodes[22].right = nodes[33];
nodes[22].left = nodes[11];
nodes[66].left = nodes[55];
nodes[66].right = nodes[77];
self.manyItems = 7;
assertFalse(self.isImmediateGreaterAncestor(null, nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[11]));
assertTrue(self.isImmediateGreaterAncestor(nodes[22], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[44], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[11]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[22]));
assertTrue(self.isImmediateGreaterAncestor(nodes[44], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[22]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[33]));
assertTrue(self.isImmediateGreaterAncestor(nodes[44], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[33]));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[44], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[44]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[44], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[55]));
assertTrue(self.isImmediateGreaterAncestor(nodes[66], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[55]));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[44], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[66]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[66]));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[11], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[22], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[44], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[66], nodes[77]));
assertFalse(self.isImmediateGreaterAncestor(nodes[77], nodes[77]));
}
public void testT5() {
self.root = nodes[5];
self.manyItems = 7;
nodes[5].right = nodes[55];
nodes[55].left = nodes[45];
nodes[45].left = nodes[35];
nodes[35].right = nodes[34];
nodes[34].right = nodes[33];
nodes[33].right = nodes[32];
assertTrue(self.isImmediateGreaterAncestor(null, nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[45], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[5]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[32]));
assertTrue(self.isImmediateGreaterAncestor(nodes[45], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[32]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[33]));
assertTrue(self.isImmediateGreaterAncestor(nodes[45], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[33]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[34]));
assertTrue(self.isImmediateGreaterAncestor(nodes[45], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[34]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[35]));
assertTrue(self.isImmediateGreaterAncestor(nodes[45], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[35]));
assertFalse(self.isImmediateGreaterAncestor(null, nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[45]));
assertFalse(self.isImmediateGreaterAncestor(nodes[45], nodes[45]));
assertTrue(self.isImmediateGreaterAncestor(nodes[55], nodes[45]));
assertTrue(self.isImmediateGreaterAncestor(null, nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[5], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[32], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[33], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[34], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[35], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[45], nodes[55]));
assertFalse(self.isImmediateGreaterAncestor(nodes[55], nodes[55]));
}
public void testW0() {
self.manyItems = 0;
assertWellFormed(true);
self.comparator = null;
assertWellFormed(false);
self.comparator = testComparator;
self.cursorStack = null;
assertWellFormed(false);
self.cursorStack = new Stack<>();
self.manyItems = 1;
assertWellFormed(false);
self.manyItems = -1;
assertWellFormed(false);
self.manyItems = 0;
assertWellFormed(true);
self.cursorStack.push(nodes[1]);
assertWellFormed(false);
self.cursorStack.pop();
self.cursorStack.push(nodes[0]);
assertWellFormed(false);
self.cursorStack.pop();
self.cursorStack.push(null);
assertWellFormed(false);
self.cursorStack.pop();
assertWellFormed(true);
}
public void testW1() {
self.manyItems = 1;
self.root = nodes[11];
assertWellFormed(true);
self.comparator = null;
assertWellFormed(false);
self.comparator = testComparator;
self.cursorStack = null;
assertWellFormed(false);
self.cursorStack = new Stack<>();
self.manyItems = 0;
assertWellFormed(false);
self.manyItems = 2;
assertWellFormed(false);
self.manyItems = 1;
assertWellFormed(true);
nodes[10].data = nodes[11].data; // impostor
self.cursorStack.push(nodes[10]);
assertWellFormed(false);
self.cursorStack.pop();
self.cursorStack.push(nodes[11]);
assertWellFormed(true);
/**/
self.cursorStack.push(nodes[11]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(null);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(null);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[11]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
}
public void testW2() {
self.root = nodes[2];
nodes[2].right = nodes[22];
self.manyItems = 3;
assertWellFormed(false);
self.manyItems = 1;
assertWellFormed(false);
self.manyItems = 2;
assertWellFormed(true);
nodes[0].data = nodes[2].data; // impostor
nodes[0].right = nodes[22];
nodes[20].data = nodes[22].data; // impostor
self.cursorStack.push(nodes[0]);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[22]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[2]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[2]);
assertWellFormed(true);
/**/
self.cursorStack.push(nodes[22]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[2]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[20]);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[22]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[2]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[22]);
assertWellFormed(true);
/**/
self.cursorStack.push(nodes[22]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[2]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
}
public void testW3() {
self.root = nodes[33];
nodes[33].left = nodes[3];
self.manyItems = 3;
assertWellFormed(false);
self.manyItems = 1;
assertWellFormed(false);
self.manyItems = 2;
assertWellFormed(true);
nodes[0].data = nodes[3].data; // impostor
nodes[0].right = nodes[33];
nodes[30].data = nodes[33].data; // impostor
self.cursorStack.push(nodes[0]);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[33]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[3]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[3]);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[33]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[3]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[30]);
assertWellFormed(false);
/**/
self.cursorStack.push(nodes[33]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[3]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
self.cursorStack.push(nodes[33]);
assertWellFormed(true);
/**/
self.cursorStack.push(nodes[33]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[3]);
/**/
assertWellFormed(true);
/**/
self.cursorStack.pop();
/**/
self.cursorStack.push(nodes[0]);
/**/
assertWellFormed(false);
/**/
self.cursorStack.pop();
self.cursorStack.pop();
}
public void testW4() {
self.root = nodes[44];
// from testR4:
nodes[44].right = nodes[43];
nodes[43].right = nodes[53];
nodes[53].right = nodes[54];
nodes[53].left = nodes[42];
nodes[44].left = nodes[33];
nodes[33].right = nodes[32];
nodes[32].right = nodes[31];
nodes[33].left = nodes[14];
nodes[14].left = nodes[4];
nodes[14].right = nodes[24];
self.manyItems = 0;
assertWellFormed(false);
self.manyItems = 1;
assertWellFormed(false);
self.manyItems = 2;
assertWellFormed(false);
self.manyItems = 3;
assertWellFormed(false);
self.manyItems = 4;
assertWellFormed(false);
self.manyItems = 5;
assertWellFormed(false);
self.manyItems = 6;
assertWellFormed(false);
self.manyItems = 7;
assertWellFormed(false);
self.manyItems = 8;
assertWellFormed(false);
self.manyItems = 9;
assertWellFormed(false);
self.manyItems = 10;
assertWellFormed(false);
self.manyItems = 11;
assertWellFormed(true);
}
public void testW5() {
self.root = nodes[55];
self.manyItems = 15;
// same start as testR5:
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
assertWellFormed(true);
nodes[14].left = nodes[13];
assertWellFormed(false);
nodes[14].left = null;
nodes[24].left = nodes[33];
assertWellFormed(false);
nodes[24].left = null;
nodes[45].right = nodes[53];
assertWellFormed(false);
nodes[45].right = null;
nodes[54].left = nodes[44];
assertWellFormed(false);
nodes[54].left = null;
nodes[64].right = nodes[65];
assertWellFormed(false);
nodes[64].right = null;
nodes[95].left = nodes[85];
assertWellFormed(false);
nodes[95].left = null;
assertWellFormed(true);
}
public void testW6() {
self.root = nodes[55];
self.manyItems = 15;
// same start as testR5:
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
assertWellFormed(true);
self.cursorStack.push(nodes[6]);
assertWellFormed(false);
self.cursorStack.pop();
// simulate traversing the sorted sequence
self.cursorStack.push(nodes[55]);
self.cursorStack.push(nodes[25]);
self.cursorStack.push(nodes[15]);
self.cursorStack.push(nodes[5]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[14]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[35]);
self.cursorStack.push(nodes[24]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[45]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[75]);
self.cursorStack.push(nodes[65]);
self.cursorStack.push(nodes[54]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[64]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[85]);
self.cursorStack.push(nodes[74]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
self.cursorStack.pop();
self.cursorStack.push(nodes[95]);
assertWellFormed(true);
self.cursorStack.pop();
assertWellFormed(true);
}
protected void setCursorStack(Integer... nums) {
self.cursorStack.clear();
for (Integer i : nums) {
if (i == null) self.cursorStack.push(null);
else self.cursorStack.push(nodes[i]);
}
}
public void testW7() {
self.root = nodes[55];
self.manyItems = 15;
// same start as testR5:
nodes[55].right = nodes[75];
nodes[55].left = nodes[25];
nodes[75].left = nodes[65];
nodes[65].left = nodes[54];
nodes[65].right = nodes[64];
nodes[75].right = nodes[85];
nodes[85].right = nodes[95];
nodes[85].left = nodes[74];
nodes[25].left = nodes[15];
nodes[15].right = nodes[14];
nodes[15].left = nodes[5];
nodes[25].right = nodes[35];
nodes[35].left = nodes[24];
nodes[35].right = nodes[45];
assertWellFormed(true);
setCursorStack(55);
assertWellFormed(true);
setCursorStack(25);
assertWellFormed(false);
setCursorStack(25, 15);
assertWellFormed(false);
setCursorStack(25, 15, 5);
assertWellFormed(false);
setCursorStack(55, 15);
assertWellFormed(false);
setCursorStack(55, 15, 5);
assertWellFormed(false);
setCursorStack(55, 5);
assertWellFormed(false);
setCursorStack(55, 25, 5);
assertWellFormed(false);
setCursorStack(55, 35, 25, 15, 5);
assertWellFormed(false);
setCursorStack(55, 25, 25, 15, 5);
assertWellFormed(false);
setCursorStack(55, null, 25, 15, 5);
assertWellFormed(false);
setCursorStack(55, 15, 25, 15, 5);
assertWellFormed(false);
setCursorStack(55, 25, 35);
assertWellFormed(false);
setCursorStack(55, 25, 35, 24);
assertWellFormed(false);
setCursorStack(55, 25, 15, 5);
assertWellFormed(true);
setCursorStack(55, 75);
assertWellFormed(false);
setCursorStack(55, 75, 65);
assertWellFormed(false);
setCursorStack(55, 75, 65, 54);
assertWellFormed(false);
setCursorStack(75, 54);
assertWellFormed(false);
}
public void testW8() {
// from testT5:
self.root = nodes[5];
self.manyItems = 7;
nodes[5].right = nodes[55];
nodes[55].left = nodes[45];
nodes[45].left = nodes[35];
nodes[35].right = nodes[34];
nodes[34].right = nodes[33];
nodes[33].right = nodes[32];
nodes[0].data = nodes[5].data; // impostor
nodes[0].right = nodes[5].right;
self.cursorStack.push(nodes[0]);
assertWellFormed(false);
setCursorStack(5);
assertWellFormed(true);
setCursorStack(55, 45, 35);
assertWellFormed(true);
setCursorStack(55, 45, 34);
assertWellFormed(true);
setCursorStack(55, 45, 33);
assertWellFormed(true);
setCursorStack(55, 45, 32);
assertWellFormed(true);
setCursorStack(55, 45);
assertWellFormed(true);
setCursorStack(55);
assertWellFormed(true);
}
public void testW9() {
// from testT5:
self.root = nodes[5];
self.manyItems = 7;
nodes[5].right = nodes[55];
nodes[55].left = nodes[45];
nodes[45].left = nodes[35];
nodes[35].right = nodes[34];
nodes[34].right = nodes[33];
nodes[33].right = nodes[32];
self.cursorStack.push(nodes[5]);
assertWellFormed(true);
setCursorStack(5, 55);
assertWellFormed(false);
setCursorStack(5, 55, 45, 35);
assertWellFormed(false);
setCursorStack(55, 35);
assertWellFormed(false);
setCursorStack(45, 35);
assertWellFormed(false);
setCursorStack(35);
assertWellFormed(false);
setCursorStack(55, 45, 35, 34, 33, 32);
assertWellFormed(false);
setCursorStack(34);
assertWellFormed(false);
setCursorStack(33);
assertWellFormed(false);
setCursorStack(32);
assertWellFormed(false);
setCursorStack(5, 55, 45, 35, 34, 33, 32);
assertWellFormed(false);
setCursorStack(35, 45, 55);
assertWellFormed(false);
}