Create A Program to Implement Sorted Sequence in Java Assignment Solution
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a java assignment program to implement sorted sequence.
Requirements and Specifications
- Concerning the SortedSequence ADT
The SortedSequence ADT has a comparator (provided when the sorted sequence is created) and uses to keep the elements in order. It is generic class, with an element type parameter named E, and provides the following operations: size Return the number of items in the sorted sequence. This should be a constant-time operation. add(E elem) Add an element to the sorted sequence in the correct place in non-descreasing order according to the comparator. If there are already elements equivalent (see below) to it, it should go directly after the last of these. (Warning: \directly after" refers to the sequence order, not to node connections.) The newly added element becomes the \current" element. start Set the cursor so that the first element (in sorted order), if any, is current. If there are no elements, then there is no current element. isCurrent Return true if there is a current element. getCurrent Return the current element, or (if there is none) throw an IllegalStateException. advance Move the cursor so that the next element is current, if any. If there was no current element, then throw an IllegalStateException. removeCurrent Remove the current element, and advance to the next element (if any). If there was no current element, then throw an IllegalStateException. The full ADT has addAll and clone operations, but these are dropped to keep this homework assignment manageable.
This ADT can be usefully implemented using a dynamic array or a linked list, although the \add" operation in the worst case will take linear time with either of these choices. We already saw that the removeCurrent method can be more efficiently implemented with a linked list than a dynamic array (whch needs to shift over elements). With a (balanced) binary search tree, none of these operations need take more than \log" Time.
Screenshot
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);
}
Similar Samples
At ProgrammingHomeworkHelp.com, explore our curated samples of programming assignments. These examples span various languages and topics, showcasing our expertise in algorithms, data structures, and more. Each sample reflects our commitment to delivering clear, well-structured solutions tailored to academic excellence. Discover how our samples can assist you in mastering programming concepts and achieving your academic goals.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java