BSTTree. It implements the
* interface for TreeHead and implements all important methods necessary for maintaining a
* Binary Search Tree.
*
* The BSTTreeHead additionally extends BSTTree, using the information and methods of a
* BSTTree in addition to the specialized methods of a BSTTreeHead.
*
* @author Corey Sanders
* @version 3.4 9/15/01
*/
public class BSTTreeHead extends BSTTree implements TreeHead, AnimationListener, AnimatingTreeHead{
/**
* String representing information regarding the type of tree.
*/
public static final String TREE_INFORMATION =
"A Binary Search Tree(BST) is a binary tree that has a key associated with each of its\n"+
"internal nodes, with the additional property that the key in any node is larger than\n"+
"(or equal to) the keys in all nodes in that node's left subtree and smaller than\n"+
"(or equal to) the keys in all nodes in that node's right subtree (Sedgewick, 502).\n\n"+
"Search Hits, Search Misses, and Insertions require about 2 ln N (1.39 lg N) comparisons,\n"+
"on the average, in a BST built from N random keys.\n\n"+
"Search Hits, Search Misses, and Insertions can require N comparisons in the worst case.\n";
/*************************************************************************/
/* BSTTreeHead constructor, methods, and variables, regardless of type. */
/*************************************************************************/
/**
* The list of listeners to this Tree. Used when the command addTreeMessageListener
* is used.
*/
private LinkedList listeners;
/**
* WaitingActionList storing all of the actions waiting to occur.
*/
private WaitingActionList waitingList;
/**
* Constructs a new, null BSTTreeHead, sorted according to the keys' natural
* order.
*
* Default type is BST_TREE_TYPE. */ public BSTTreeHead() { this(0); } /** * Constructs a new, empty BSTTree according to the type passed. The options for the * types are BST_TREE_TYPE, DRAWING_BST_TREE_TYPE, and ANIMATING_BST_TREE_TYPE. The * types are defined as follows: *
TreeMessageEvent.
*
* @param l the listener added recieves the TreeMessageEvents occuring.
*/
public void addTreeMessageListener(TreeMessageListener l) {
listeners.add(l);
}
/**
* Removes an TreeMessageListener from the TREE, according to
* the TreeMessageListener interface and the TreeMessageEvent.
*
* @param l the listener removed from recieving the TreeMessageEvents occuring.
*/
public void removeTreeMessageListener(TreeMessageListener l) {
listeners.remove(l);
}
/**
* Makes a new tree message. The method calls messageAction with the information
* necessary for the tree status. The information presented include :
* WaitingActionList which keeps the list of actions, and calls the method when
* instructed to call the next action.
*
* @param action String action representing the next action for the BSTTreeHead.
* @param element element to which the action could be occuring, depending on the type of action.
*/
public void waitingAction(String action, Object element) {
// insert.
if (action.equals(TreeHead.INSERT_NODE)) {
insert(((BSTTree)element));
if (!waitingList.isEmpty()) {
if (waitingList.getFirstAction().equals(TreeHead.INSERT_NODE)) {
waitingList.nextAction(this);
}
}
}
// rotateUp.
if (action.equals(TreeHead.ROTATE_UP)) {
// Check if currently in the tree.
if (!((BSTTree)element).inTree())
return;
rotateUp(((BSTTree)element));
}
// rotateUpDouble.
if (action.equals(TreeHead.ROTATE_UP_DOUBLE)) {
// Check if currently in the tree.
if (!((BSTTree)element).inTree())
return;
rotateUpDouble(((BSTTree)element));
}
// balance
if (action.equals(TreeHead.BALANCE_NODE)) {
// Check if currently in the tree.
if (!((BSTTree)element).inTree())
return;
balance(((BSTTree)element));
}
// remove
if (action.equals(TreeHead.REMOVE_NODE)) {
// Check if currently in the tree.
if (!((BSTTree)element).inTree())
return;
remove(((BSTTree)element));
}
// search
if (action.equals(TreeHead.SEARCH)) {
search((Comparable)element);
}
// select
if (action.equals(TreeHead.SELECT)) {
select(((NodeAndKey)element).getNode(), ((NodeAndKey)element).getKey());
}
// partition
if (action.equals(TreeHead.PARTITION_NODE)) {
partition(((NodeAndKey)element).getNode() , ((NodeAndKey)element).getKey() );
}
// splay
if (action.equals(TreeHead.SPLAY_NODE)) {
splayAnimatingType((BSTTree)element);
}
// rotate to top
if (action.equals(TreeHead.ROTATE_TO_TOP_NODE)) {
rotateToTopAnimatingType((BSTTree)element);
}
// rotate to top
if (action.equals(TreeHead.TRAVERSE)) {
traverse(((Integer)element).intValue());
}
// rotate to top
if (action.equals(TreeHead.CHANGE_DISPLAY)) {
changeDisplay();
}
}
/**
* Gets the WaitingActionList representing the waitingList for the tree. This allows
* extension of the class have tthe ability to modify the attributes of the list.
*
* @return WaitingActionList waiting list for the tree.
*/
protected WaitingActionList getWaitingList() {
return waitingList;
}
/**
* An object which keeps both a BSTTree node and an integer key. Useful when dealing with
* waitingActions that must involve both a node and key. This class makes that possible
* within one object.
*/
public class NodeAndKey {
/**
* BSTTree node
*/
BSTTree node;
/**
* key
*/
int key;
/**
* Constructor, making an empty NodeAndKey Object. Using the set methods, it can be
* set.
*/
public NodeAndKey() {
this(null, 0);
}
/**
* Constructor, making a NodeAndKey Object with the speficied node and key.
*
* @param node BSTTree node for the current NodeAndKey.
* @param key int for the NodeAndKey.
*/
public NodeAndKey(BSTTree node, int key) {
setNode(node);
setKey(key);
}
/**
* Sets the node for the object.
*
* @param node BSTTree node for the object.
*/
protected void setNode(BSTTree node) {
this.node = node;
}
/**
* Sets the key for the object.
*
* @param key int for the object.
*/
protected void setKey(int key) {
this.key = key;
}
/**
* Gets the node for the object.
*
* @return BSTTree node for the object.
*/
public BSTTree getNode() {
return node;
}
/**
* Gets the key for the object.
*
* @return int key for the object.
*/
public int getKey() {
return key;
}
}
/*-----------------------------------------------------------------------*/
/*-------------------------------BST_TREE_TYPE---------------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* BST_TREE_TYPE : Methods and Variables specific to the BST_TREE_TYPE. */
/* These methods are universally used, regardless of the type of BST. */
/*************************************************************************/
/**
* The amount of levels to the bottom of the tree.
*/
private int treeLevel=0;
/**
* Constructor for the BST_TREE_TYPE. This constructs and sets all values to defaults
* for the BST_TREE_TYPE.
*/
public void constructBSTTreeHead() {
if (getHead() == null) {
setHead(this);
setChild(null);
setParentTree(null);
setTreeLevel(0);
setSize(0);
}
}
/**
**********************************
* BST_TREE_TYPE Accesssor methods*
**********************************
*/
/**
* Returns true if the TreeHead is empty.
*/
public boolean isTreeEmpty() {
return (((BSTTree)getChild()) == null);
}
/**
* Gets the child of the TreeHead. The child is the beginning of the Tree nodes.
*
* @param child Tree, beginning the Tree nodes.
*/
public Tree getChild() {
return getLeftTree();
}
/**
* Gets the lowest level of the Tree. A level of 0 indicates an empty tree.
*
* @return integer level set for the Tree.
*/
public int getTreeLevel() {
return treeLevel;
}
/**
* Returns the number of objects in the entire tree.
*
* @return the number of objects in the entire tree.
*/
public int size() {
if (isTreeEmpty()) {
return 0;
}
else {
return ((BSTTree)getChild()).size();
}
}
/**
**********************************
* BST_TREE_TYPE Mutator methods *
**********************************
*/
/**
* Sets the child of the TreeHead. The child is the beginning of the Tree nodes.
*
* @param child Tree, beginning the Tree nodes.
*/
public void setChild(Tree child) {
// Make the left subtree the child, saving links already defined by extending BSTTree.
setLeftTree((BSTTree)child);
}
/**
* Sets the lowest level of the Tree, used in numerous methods. The level must remain very accurate. A level of 0 indicates an empty Tree.
*
* @param level integer level set for the BSTTree.
*/
protected void setTreeLevel(int level) {
treeLevel = level;
}
/**
* Resets the lowest level of the Tree. The level is set to 0, so that is can be recalculated, using fixLevel.
*/
public void resetTreeLevel() {
treeLevel = 0;
}
/**
* Fixes the lowest level of the Tree, using recursive calls into the BSTTree. Generally, resetTreeLevel is called before the method.
*/
public void fixLevel() {
((BSTTree)getChild()).fixLevel(1);
if (getChild().isEmpty()) {
setChild(null);
}
}
/**
* Fixes the size of each subtree, using recursive calls into the BSTTree.
*/
public int fixSize() {
setSize(((BSTTree)getChild()).fixSize());
return size();
}
/**
* Makes and places the node into the tree. The node is returned for further manipulation.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return BSTTree that was recently inserted into the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected BSTTree makeNode(Comparable keyInsert, Object valueInsert) throws ClassCastException {
if (isDrawingBSTTree()) {
return makeNodeDrawingType(keyInsert, valueInsert);
}
else {
return makeNodeTreeType(keyInsert, valueInsert);
}
}
/**
*************************************
* BST_TREE_TYPE Implements TreeHead *
*************************************
*/
/**
* Clears the BSTTree completely, removing all references to all nodes and all
* values return to the default.
*/
public void clear() {
resetTreeLevel();
setChild(null);
if (isAnimatingBSTTree()) {
clearAnimators();
}
}
/**
* Inserts the comaparable object keyInsert to the tree using its natural ordering .
* The value, valueInsert is added with the key to the node.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return boolean true if this collection changed as a result of the call.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException key is null.
*/
public boolean insert(Comparable keyInsert, Object valueInsert) throws NullPointerException, ClassCastException {
if (keyInsert == null)
throw new NullPointerException();
int oldSize = size();
BSTTree newTree = makeNode(keyInsert,valueInsert);
insert(newTree);
// Check correct insertion.
if (size() == (oldSize + 1)) {
return true;
}
return false;
}
/**
* Inserts the node to the tree using its natural ordering .
*
* @param node BSTTree which is added to the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
public void insert(Tree node) throws ClassCastException {
if (isAnimatingBSTTree()) {
insertAnimatingType((BSTTree)node);
}
else if (isDrawingBSTTree()) {
insertDrawingType((BSTTree)node);
}
else {
insertTreeType((BSTTree)node);
}
}
/**
* Removes the given node from the tree. The accompanying value is also
* removed from the tree and the node is deleted.
*
* @param node the Tree node to be removed from the tree.
*/
public void remove(Tree node) {
if (isAnimatingBSTTree()) {
removeAnimatingType((BSTTree)node);
}
else {
removeTreeType((BSTTree)node);
}
}
/**
* Removes the comaparable object keyRemove from the BSTTree using its natural ordering .
* If the method is successful in removing the element, true is returned.
*
* @param keyRemove comparable object which is removed from the tree.
*
* @return boolean true if this collection changed as a result of the call.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException key is null.
*/
public boolean remove(Comparable keyRemove) throws ClassCastException, NullPointerException {
if (keyRemove == null)
throw new NullPointerException();
if (isTreeEmpty())
return false;
BSTTree removingNode = (BSTTree)searchTreeType(keyRemove);
if (!removingNode.getKey().equals(keyRemove)) {
return false;
}
remove(removingNode);
return true;
}
/**
* Balances the entire tree, recursively rotating the median to the top.
*/
public void balanceTree() {
balance(getChild());
}
/**
* Balances the tree, from the node downward, recursively rotating the median to the top.
*
* @param node the node from which the balance occurs
*/
public void balance(Tree node) {
if (node == null) {
return;
}
if (node.isEmpty()) {
return;
}
if (isAnimatingBSTTree()) {
balanceAnimatingType((BSTTree)node);
}
else {
balanceTreeType((BSTTree)node);
}
}
/**
* Partitions from the given node the keySelect value. Replacing the reference in the
* Tree to the given node, to the keySelectth item.
*
* @param Tree which the partition occurs at.
* @param keySelect integer key selecting the count item.
*
* @return Tree that is the reference to the newly partitioned tree.
*/
public Tree partition(Tree node, int keySelect) {
if (isTreeEmpty())
return null;
if (keySelect > node.size() || keySelect < 0) {
return null;
}
if (isAnimatingBSTTree()) {
return partitionAnimatingType((BSTTree)node, keySelect);
}
else {
return partitionTreeType((BSTTree)node, keySelect);
}
}
/**
* Searches for the comaparable object in the Tree using its natural ordering .
* If the method is successful in finding the element, the item is returned. Otherwise, the closest item is
* returned.
*
* @param keySearch comparable object which is search for within the tree.
*
* @return Tree element which matches the keySearch or the nearest node or null if the search is impossible to perform.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
* @throws NullPointerException key is null.
*/
public Tree search(Comparable keySearch) throws ClassCastException, NullPointerException {
if (keySearch == null)
throw new NullPointerException();
if (isTreeEmpty())
return null;
BSTTree node;
if (isAnimatingBSTTree()) {
return (BSTTree)searchAnimatingType(keySearch);
}
else {
return (BSTTree)searchTreeType(keySearch);
}
}
/**
* Selects the kth smallest item in the Tree using its natural ordering from the given node.
* If the method is successful in finding the element, the item is returned. Otherwise, null is
* returned if the integer is greater than the size.
*
* @param Tree which the partition occurs at.
* @param keySelect integer key selecting the count item.
*
* @return Tree element which matches the kth element or null if k > size.
*/
public Tree select(Tree node, int keySelect) {
if (isTreeEmpty())
return null;
if (keySelect >= node.size() || keySelect < 0)
return null;
Tree returnNode;
if (isAnimatingBSTTree()) {
returnNode = selectAnimatingType((BSTTree)node, keySelect);
}
else {
returnNode = selectTreeType((BSTTree)node, keySelect);
}
if (returnNode != null)
return returnNode;
else
return selectTreeType((BSTTree)node, keySelect);
}
/**
********************************************
* BST_TREE_TYPE Binary Search Tree Methods *
********************************************
*/
/**
* Rotates the BSTTree up. It simply changes around references, including the
* parent reference and the ancestor reference. The rotation upwards replaces the parent with
* the node and brings the parent down a level.
*
* @param node BSTTree that rotated upwards.
*/
public void rotateUp(BSTTree node) {
rotateUp(node, 1);
}
/**
* Rotates the BSTTree up. It simply changes around references, including the
* parent reference and the ancestor reference. The rotation upwards replaces the parent with
* the node and brings the parent down a level.
*
* @param node BSTTree that rotated upwards.
* @param levelCount the amount of levels up the node should rotate
*/
public void rotateUp(BSTTree node, int levelCount) {
// Check for null nodes (precaution only).
if (node == this)
return;
BSTTree parentTree = (BSTTree)node.getParentTree();
if (parentTree == this ) {
return;
}
for (int i =0; i < levelCount; i++ ) {
if (isAnimatingBSTTree()) {
rotateUpAnimatingType(node);
}
else {
rotateUpTreeType(node);
}
}
}
/**
* Double Rotatation of the BSTTTree.
*
* @param node BSTTree that is double rotated (bottom rotation first).
*/
public void rotateUpDouble(BSTTree node) {
rotateUpDouble(node, 1);
}
/**
* Doubly Rotates the BSTTree up to the top. This is also referred to as a Splay
* and is the basis for a splay tree if the double rotation occurs to the top.
*
* @param node BSTTree that rotated upwards.
* @param levelCount the amount of levels up the node should rotate
*/
public void rotateUpDouble(BSTTree node, int levelCount) {
// Check for null nodes (precaution only).
if (node == this) {
return;
}
BSTTree parentTree = (BSTTree)node.getParentTree();
if (parentTree == this ) {
return;
}
for (int i =0; i < levelCount; i++ ) {
if (isAnimatingBSTTree()) {
rotateUpDoubleAnimatingType(node);
}
else {
rotateUpDoubleTreeType(node);
}
}
}
/**
* Rotates the BSTTTree to the top.
*
* @param node BSTTree that is rotated to the top.
*/
public void rotateToTop(BSTTree node) {
if (isAnimatingBSTTree()) {
rotateToTopAnimatingType(node);
}
else {
rotateToTopTreeType(node);
}
}
/**
* Splays the BSTTTree to the top (Double rotates).
*
* @param node BSTTree that is rotated to the top.
*/
public void splay(BSTTree node) {
if (isAnimatingBSTTree()) {
splayAnimatingType(node);
}
else {
splayTreeType(node);
}
}
/**
* Changes the display of the current tree.
*/
public void changeDisplay() {
if (isAnimatingBSTTree()) {
changeDisplayAnimatingType();
}
else {
changeDisplayTreeType();
}
}
/**
* Traverses the tree in the given traversal type.
*
* @param traverseType int defining the given traversal type.
*
*/
public LinkedList traverse(int traverseType) {
if (isAnimatingBSTTree()) {
return traverseAnimatingType(traverseType);
}
else {
return traverseTreeType(traverseType);
}
}
/**
************************************************************************
* BST_TREE_TYPE Original Methods(Overiden in ANIMATING_BST_TREE_TYPE *
************************************************************************
*/
/**
* Makes and places the node into the tree. The node is returned for further manipulation.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return BSTTree that was recently inserted into the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected BSTTree makeNodeTreeType(Comparable keyInsert, Object valueInsert) {
// Get node from node factory.
BSTTree newTree = new BSTTree(getTreeType());
newTree.setHead(this);
// Set the null leaves.
newTree.setLeaf();
((BSTTree)newTree.getRightTree()).setHead(this);
((BSTTree)newTree.getLeftTree()).setHead(this);
// Set the values of the node.
newTree.setNode(keyInsert, valueInsert);
return newTree;
}
/**
* Insert the comaparable node to the tree using its natural ordering .
*
* @param node BSTTree node to be inserted into the tree
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected void insertTreeType(BSTTree node) throws ClassCastException {
// Empty Tree
if (isTreeEmpty()) {
setChild(node);
node.setParentTree(this);
node.setLevel(1); // Set initial size and level.
node.setSize(1);
this.setTreeLevel(1);
return;
}
// Recursive call to insert the tree, starting at the head level.
((BSTTree)getChild()).insert(node, 0);
}
/**
* Removes the given node from the tree. The accompanying value is also
* removed from the tree and the node is deleted.
*
* @param node the Tree node to be removed from the tree.
*/
public void removeTreeType(BSTTree node) {
resetTreeLevel();
if (((BSTTree)node).inTree()) {
((BSTTree)node).remove();
}
fixLevel();
fixSize();
}
/**
* Partitions from the given node the keySelect value. Replacing the reference in the
* Tree to the given node, to the keySelectth item.
*
* @param Tree which the partition occurs at.
* @param keySelect integer key selecting the count item.
* @return Tree that is the reference to the newly partitioned tree.
*/
protected BSTTree partitionTreeType(BSTTree node, int keySelect) {
return node.partition(keySelect, 0);
}
/**
* Balances the tree from the given node, recursively rotating the median to the top.
*
* @param node BSTTree that is balanced from.
*/
public void balanceTreeType(BSTTree node) {
if (node.size() <= 2)
return;
BSTTree newNode = partitionTreeType(node, node.size()/2);
balanceTreeType(newNode.getLeftTree());
balanceTreeType(newNode.getRightTree());
}
/**
* Searches for the Tree in the entire tree.
*
* @param keySearch the comparable key which is searched for within the tree.
* @return Tree the Tree found or null if keySearch was not present within the tree.
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
public Tree searchTreeType(Comparable keySearch) throws ClassCastException {
return ((BSTTree)getChild()).search(keySearch);
}
/**
* Selects for the Tree in the entire tree.
*
* @param node the node from which the selection takes place.
* @param keySelect integer key selecting the count item.
* @return Tree the Tree found or null.
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
public Tree selectTreeType(BSTTree node, int keySelect) throws ClassCastException {
return node.select(keySelect);
}
/**
* Rotates the BSTTree up. It simply changes around references, including the
* parent reference and the ancestor reference. The rotation upwards replaces the parent with
* the node and brings the parent down a level.
*
* @param node BSTTree that rotated upwards.
*/
public void rotateUpTreeType(BSTTree node) {
// Get the parent for rotation.
BSTTree nodeParent = (BSTTree)node.getParentTree();
if (nodeParent == this) {
return;
}
resetTreeLevel();
// Get the ancestor node, whose child links are modified.
BSTTree nodeAncestor = (BSTTree)nodeParent.getParentTree();
BSTTree temp = null;
// Determine if the node is the left or right child and rotate accordingly.
if (node == nodeParent.getLeftTree() ) {
temp = nodeParent.rotateRight();
}
else if (node == nodeParent.getRightTree()) {
temp = nodeParent.rotateLeft();
}
// Resets links for Heaed rotate up.
if (nodeAncestor == getHead()) {
setChild(temp);
temp.setParentTree(this);
}
// Resets links for all others
else {
if (nodeAncestor.getLeftTree() == nodeParent) {
nodeAncestor.setLeftTree(temp);
}
else {
nodeAncestor.setRightTree(temp);
}
temp.setParentTree(nodeAncestor);
}
// Fixes the level.
fixLevel();
}
/**
* Double Rotates the BSTTree up.
*
* @param node BSTTree that rotated upwards.
*/
public void rotateUpDoubleTreeType(BSTTree node) {
BSTTree parentTree = (BSTTree) node.getParentTree();
BSTTree grandParentTree = (BSTTree)parentTree.getParentTree();
if (grandParentTree == this) {
rotateUpTreeType(node);
return;
}
// Opposite direction, resulting in normal rotations (left-right and right-left)
if (
((grandParentTree.getLeftTree() == parentTree) && (parentTree.getRightTree() == node))
||
((grandParentTree.getRightTree() == parentTree) && (parentTree.getLeftTree() == node))
) {
// Rotate node up twice
rotateUpTreeType(node);
rotateUpTreeType(node);
}
// Same direction, Splay rotation
else {
rotateUpTreeType(parentTree);
rotateUpTreeType(node);
}
}
/**
* Splays the node up in the BSTTree.
*
* @param node BSTTree node that is splayed.
*/
protected void splayTreeType(BSTTree node) {
if ( (node.getLevel() != 2) && ( (node.getLevel() % 2) == 0) ) {
// If the count is odd, it must single rotate first (without animation, no wait is necessary)
rotateUp(node);
// After the single rotation is must take the new parent and continue with the rotations
rotateUpDouble(node, node.getLevel()/2);
}
else {
// No single rotation is necessary
rotateUpDouble(node, node.getLevel() / 2);
}
}
/**
* Rotates to top the node up in the BSTTree.
*
* @param node BSTTree node that is rotated up.
*/
protected void rotateToTopTreeType(BSTTree node) {
rotateUp(node, node.getLevel());
}
/**
* Traverses the tree in the given traversal type.
*
* @param traverseType int defining the given traversal type.
*
*/
public LinkedList traverseTreeType(int traverseType) {
if (traverseType == PREORDER_TRAVERSAL) {
return getPreorderTree();
}
else if (traverseType == INORDER_TRAVERSAL) {
return getInorderTree();
}
else if (traverseType == POSTORDER_TRAVERSAL) {
return getPostorderTree();
}
else if (traverseType == LEVELORDER_TRAVERSAL) {
return getLevelorderTree();
}
else {
return new LinkedList();
}
}
/**
* Change Display of the BSTTree.
*/
public void changeDisplayTreeType() {
int currentDisplay = getDisplay();
if (currentDisplay == BSTTreeHead.SECTIONAL_DISPLAY) {
setDisplay(BSTTreeHead.BINARY_DISPLAY);
}
else {
setDisplay(BSTTreeHead.SECTIONAL_DISPLAY);
}
}
/**
**********************************
* Traversal Methods *
**********************************
*/
/**
* Makes a preorder representation of the tree in an array of BSTTrees.
* Changes in the references in the array have no effect upon the tree.
*
* @return LinkedList of BSTTree objects that are the preorder representation of the tree.
*
*/
public LinkedList getPreorderTree() {
LinkedList traverseList = new LinkedList();
((BSTTree)getChild()).makePreorderTree(traverseList);
return traverseList;
}
/**
* Makes a inorder representation of the tree in an array of BSTTrees.
* Changes in the references in the array have no effect upon the tree.
*
* @return LinkedList of BSTTree objects that are the preorder representation of the tree.
*
*/
public LinkedList getInorderTree() {
LinkedList traverseList = new LinkedList();
((BSTTree)getChild()).makeInorderTree(traverseList);
return traverseList;
}
/**
* Makes a postorder representation of the tree in an array of BSTTrees.
* Changes in the references in the array have no effect upon the tree.
*
* @return LinkedList of BSTTree objects that are the preorder representation of the tree.
*
*/
public LinkedList getPostorderTree() {
LinkedList traverseList = new LinkedList();
((BSTTree)getChild()).makePostorderTree(traverseList);
return traverseList;
}
/**
* Makes a levelorder representation of the tree in an array of BSTTrees.
* Changes in the references in the array have no effect upon the tree.
*
* @return Array of BSTTree objects that are the preorder representation of the tree.
*
*/
public LinkedList getLevelorderTree() {
LinkedList traverseList = new LinkedList();
LinkedList visitingList = new LinkedList();
BSTTree currentNode = (BSTTree)getChild();
visitingList.addLast(currentNode);
while(!visitingList.isEmpty()) {
currentNode = (BSTTree)visitingList.removeFirst();
traverseList.add(currentNode);
if (!currentNode.getLeftTree().isEmpty()) {
visitingList.addLast(currentNode.getLeftTree());
}
if (!currentNode.getRightTree().isEmpty()) {
visitingList.addLast(currentNode.getRightTree());
}
}
return traverseList;
}
/*-----------------------------------------------------------------------*/
/*-------------------------------BST_TREE_TYPE---------------------------*/
/*------------------------------------END--------------------------------*/
/*-----------------------------------------------------------------------*/
/*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
/*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/
/*-----------------------------------------------------------------------*/
/*----------------------------DRAWING_BST_TREE_TYPE----------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* DRAWING_BST_TREE_TYPE : Methods and Variables specific to the */
/* DRAWING_BST_TREE_TYPE. These methods are specificaly used for drawing*/
/* to a Graphics2D. Therefore, do not use this type unless that is your */
/* purpose. */
/*************************************************************************/
/**
* Binary Display
*/
public static final int BINARY_DISPLAY = 0;
/**
* sectional display
*/
public static final int SECTIONAL_DISPLAY = 1;
/**
* Type of display being used for the tree. (Binary or sectional)
*/
private int display;
/**
* The previous display type.
*/
private int previousDisplay;
/**
* Settings for the entire tree. The default settings for each node.
*/
private NodeSettings nodeSettings;
/**
* Settings for the entire tree. The default settings for each node.
*/
private KeySettings keySettings;
/**
* Node width to height ratio. Change for a different ratio in drawing the nodes.
*/
private double treeNodeWidthToHeightRatio;
/**
* Stores the width of the standard node.
*/
private double nodeWidth;
/**
* Stores the height of the standard node.
*/
private double nodeHeight;
/**
* Stores the height of each drawn section.
*/
private double sectionHeight;
/**
* Bounds of the drawing screen.
*/
private Rectangle2D screenBounds;
/**
* Bounds of the drawing screen.
*/
private Color backgroundColor;
/**
/*****************************************
/* Settings for Animations. Can be set, *
/* even if the tree is a drawing type, *
/* but are only used if animating. *
/*****************************************
*/
/**
* Node Left Settings for Insertion.
*/
private NodeSettings insertNodeLeftSettings;
/**
* Node Right Settings for Insertion.
*/
private NodeSettings insertNodeRightSettings;
/**
* Animator Node Settings for Insertion.
*/
private NodeSettings insertAnimatorNodeSettings;
/**
* Animator Key Settings for Insertion.
*/
private KeySettings insertAnimatorKeySettings;
/**
* Node Left Settings for Searching.
*/
private NodeSettings searchNodeLeftSettings;
/**
* Node Right Settings for Searching.
*/
private NodeSettings searchNodeRightSettings;
/**
* Animator Node Settings for Searching.
*/
private NodeSettings searchAnimatorNodeSettings;
/**
* Animator Key Settings for Searching.
*/
private KeySettings searchAnimatorKeySettings;
/**
* Node Left Settings for Selection.
*/
private NodeSettings selectNodeLeftSettings;
/**
* Node Right Settings for Selection.
*/
private NodeSettings selectNodeRightSettings;
/**
* Animator Node Settings for Selection.
*/
private NodeSettings selectAnimatorNodeSettings;
/**
* Animator Key Settings for Selection.
*/
private KeySettings selectAnimatorKeySettings;
/**
* Node Child Settings for Rotation.
*/
private NodeSettings rotateChildNodeSettings;
/**
* Node Root Settings for Rotation.
*/
private NodeSettings rotateRootNodeSettings;
/**
* Node Descendant Settings for Rotation.
*/
private NodeSettings rotateDescendantNodeSettings;
/**
* Node Original Settings for Rotation.
*/
private NodeSettings rotateOriginalNodeSettings;
/**
* Key Animator Settings for Rotation.
*/
private KeySettings rotateAnimatorKeySettings;
/**
* Key Original Settings for Rotation.
*/
private KeySettings rotateOriginalKeySettings;
/**
* Left paint for Deletion.
*/
private PaintSettings deleteLeftLinePaintSettings;
/**
* Right paint for Deletion.
*/
private PaintSettings deleteRightLinePaintSettings;
/**
* Animator Node Settings for Traversal.
*/
private NodeSettings traverseAnimatorNodeSettings;
/**
* Animator Key Settings for Traversal.
*/
private KeySettings traverseAnimatorKeySettings;
/**
* Constructor for the DRAWING_BST_TREE_TYPE. This constructs and sets all values to defaults
* for the DRAWING_BST_TREE_TYPE.
*/
public void constructDrawingBSTTreeHead() {
if (getDrawingNodeSettings() == null) {
super.constructDrawingBSTTree();
setDisplay(BINARY_DISPLAY);
setDrawingNodeSettings(new NodeSettings(NodeSettings.DEFAULT_SCHEME));
setDrawingKeySettings(new KeySettings(KeySettings.DEFAULT_SCHEME));
treeNodeWidthToHeightRatio = 1.0;
screenBounds = null;
setInsertNodeLeftSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setInsertNodeRightSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setInsertAnimatorNodeSettings(NodeSettings.getScheme(NodeSettings.ANIMATOR_SCHEME_1));
setInsertAnimatorKeySettings(KeySettings.getScheme(KeySettings.ANIMATOR_SCHEME_1));
setSearchNodeLeftSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setSearchNodeRightSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setSearchAnimatorNodeSettings(NodeSettings.getScheme(NodeSettings.ANIMATOR_SCHEME_1));
setSearchAnimatorKeySettings(KeySettings.getScheme(KeySettings.ANIMATOR_SCHEME_1));
setSelectNodeLeftSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setSelectNodeRightSettings(NodeSettings.getScheme(NodeSettings.ANIMATION_SCHEME_1));
setSelectAnimatorNodeSettings(NodeSettings.getScheme(NodeSettings.ANIMATOR_SCHEME_1));
setSelectAnimatorKeySettings(KeySettings.getScheme(KeySettings.ANIMATOR_SCHEME_1));
setRotateRootNodeSettings(NodeSettings.getScheme(NodeSettings.ROTATION_SCHEME_1));
setRotateChildNodeSettings(NodeSettings.getScheme(NodeSettings.ROTATION_SCHEME_1));
setRotateDescendantNodeSettings(NodeSettings.getScheme(NodeSettings.ROTATION_SCHEME_1));
setRotateOriginalNodeSettings(NodeSettings.getScheme(NodeSettings.DEFAULT_SCHEME));
setRotateAnimatorKeySettings(KeySettings.getScheme(KeySettings.ANIMATOR_SCHEME_1));
setRotateOriginalKeySettings(KeySettings.getScheme(KeySettings.DEFAULT_SCHEME));
setDeleteLeftLinePaintSettings(PaintSettings.getScheme(PaintSettings.RED));
setDeleteRightLinePaintSettings(PaintSettings.getScheme(PaintSettings.BLUE));
setTraverseAnimatorNodeSettings(NodeSettings.getScheme(NodeSettings.ANIMATOR_SCHEME_1));
setTraverseAnimatorKeySettings(KeySettings.getScheme(KeySettings.ANIMATOR_SCHEME_1));
}
}
/**
*******************************************
* DRAWING_BST_TREE_TYPE Accesssor methods *
*******************************************
*/
/**
* Gets the display choice for the tree.
*
* @return the integer that defines the display choice of the tree.
*/
public int getDisplay() {
return display;
}
/**
* Gets the previous display choice for the tree.
*
* @return the integer that defines the display choice of the tree.
*/
public int getPreviousDisplay() {
return previousDisplay;
}
/**
* Gets the NodeSettings for the entire tree.
*
* @return NodeSettings for defined for the entire tree.
*/
public NodeSettings getDrawingNodeSettings() {
return nodeSettings;
}
/**
* Gets the KeySettings for the entire tree.
*
* @return KeySettings for defined for the entire tree.
*/
public KeySettings getDrawingKeySettings() {
return keySettings;
}
/**
* Gets the width of the standard node within the tree. Every node is not necessarily the same
* width, but the standard is set within the Head.
*
* @return width of the standard node.
*/
public double getNodeWidth() {
return nodeWidth;
}
/**
* Gets the height of the standard node within the tree. Every node is not necessarily the same
* height, but the standard is set within the Head.
*
* @return height of the standard node.
*/
public double getNodeHeight() {
return nodeHeight;
}
/**
* Gets the bounds of the screen to which the tree is drawing. The bounds generally is simply
* the rectangle enclosing the Graphics2D passed.
*
* @return the rectangle representing the bounds of the screen.
*/
public Rectangle2D getScreenBounds() {
return screenBounds;
}
/**
* Returns the height of the section, used for rendering the tree.
*
* @return double height of the section.
*/
protected double getTreeSectionHeight() {
return sectionHeight;
}
/**
* Sets the background paint for the tree.
*
* @param background paint of the background.
*/
protected Color getBackgroundColor() {
return backgroundColor;
}
/**
/*****************************************
/* Settings for Animations. Can be set, *
/* even if the tree is a drawing type, *
/* but are only used if animating. *
/*****************************************
*/
/**
* Gets the NodeSettings for the left node settings for insertion.
*
* @return NodeSettings for the left node.
*/
public NodeSettings getInsertNodeLeftSettings() {
return insertNodeLeftSettings;
}
/**
* Gets the NodeSettings for the right node settings for insertion.
*
* @return NodeSettings for the right node.
*/
public NodeSettings getInsertNodeRightSettings() {
return insertNodeRightSettings;
}
/**
* Gets the NodeSettings for the animator node settings for insertion.
*
* @return NodeSettings for the animator node.
*/
public NodeSettings getInsertAnimatorNodeSettings() {
return insertAnimatorNodeSettings;
}
/**
* Gets the KeySettings for the animator key settings for insertion.
*
* @return KeySettings for the animator key.
*/
public KeySettings getInsertAnimatorKeySettings() {
return insertAnimatorKeySettings;
}
/**
* Gets the NodeSettings for the left node settings for searching.
*
* @return NodeSettings for the left node.
*/
public NodeSettings getSearchNodeLeftSettings() {
return searchNodeLeftSettings;
}
/**
* Gets the NodeSettings for the right node settings for searching.
*
* @return NodeSettings for the right node.
*/
public NodeSettings getSearchNodeRightSettings() {
return searchNodeRightSettings;
}
/**
* Gets the NodeSettings for the animator node settings for searching.
*
* @return NodeSettings for the animator node.
*/
public NodeSettings getSearchAnimatorNodeSettings() {
return searchAnimatorNodeSettings;
}
/**
* Gets the KeySettings for the animator key settings for searching.
*
* @return KeySettings for the animator key.
*/
public KeySettings getSearchAnimatorKeySettings() {
return searchAnimatorKeySettings;
}
/**
* Gets the NodeSettings for the left node settings for selection.
*
* @return NodeSettings for the left node.
*/
public NodeSettings getSelectNodeLeftSettings() {
return selectNodeLeftSettings;
}
/**
* Gets the NodeSettings for the right node settings for selection.
*
* @return NodeSettings for the right node.
*/
public NodeSettings getSelectNodeRightSettings() {
return selectNodeRightSettings;
}
/**
* Gets the NodeSettings for the animator node settings for selection.
*
* @return NodeSettings for the animator node.
*/
public NodeSettings getSelectAnimatorNodeSettings() {
return selectAnimatorNodeSettings;
}
/**
* Gets the KeySettings for the animator key settings for selection.
*
* @return KeySettings for the animator key.
*/
public KeySettings getSelectAnimatorKeySettings() {
return selectAnimatorKeySettings;
}
/**
* Gets the NodeSettings for the root node settings for rotation.
*
* @return NodeSettings for the root node.
*/
public NodeSettings getRotateRootNodeSettings() {
return rotateRootNodeSettings;
}
/**
* Gets the NodeSettings for the child node settings for rotation.
*
* @return NodeSettings for the child node.
*/
public NodeSettings getRotateChildNodeSettings() {
return rotateChildNodeSettings;
}
/**
* Gets the NodeSettings for the descendant node settings for rotation.
*
* @return NodeSettings for the descendant node.
*/
public NodeSettings getRotateDescendantNodeSettings() {
return rotateDescendantNodeSettings;
}
/**
* Gets the NodeSettings for the original node settings for rotation.
*
* @return NodeSettings for the original node.
*/
public NodeSettings getRotateOriginalNodeSettings() {
return rotateOriginalNodeSettings;
}
/**
* Gets the KeySettings for the animator key settings for rotation.
*
* @return KeySettings for the animator key.
*/
public KeySettings getRotateAnimatorKeySettings() {
return rotateAnimatorKeySettings;
}
/**
* Gets the KeySettings for the original key settings for rotation.
*
* @return KeySettings for the original key.
*/
public KeySettings getRotateOriginalKeySettings() {
return rotateOriginalKeySettings;
}
/**
* Gets the Paint for the left line of Paint.
*
* @return Paint for the left line.
*/
public PaintSettings getDeleteLeftLinePaintSettings() {
return deleteLeftLinePaintSettings;
}
/**
* Gets the Paint for the right line of Paint.
*`
* @return Paint for the right line.
*/
public PaintSettings getDeleteRightLinePaintSettings() {
return deleteRightLinePaintSettings;
}
/**
* Gets the NodeSettings for the animator node settings for traversal.
*
* @return NodeSettings for the animator node.
*/
public NodeSettings getTraverseAnimatorNodeSettings() {
return traverseAnimatorNodeSettings;
}
/**
* Gets the KeySettings for the animator key settings for traversal.
*
* @return KeySettings for the animator key.
*/
public KeySettings getTraverseAnimatorKeySettings() {
return traverseAnimatorKeySettings;
}
/**
*******************************************
* DRAWING_BST_TREE_TYPE Mutator methods *
*******************************************
*/
/**
* Sets the display choice for the tree.
*
* @param display sets the integer that defines the display choice of the tree.
*/
public void setDisplay(int display) {
this.display = display;
}
/**
* Sets the previous display choice for the tree.
*
* @param display sets the integer that defines the display choice of the tree.
*/
public void setPreviousDisplay(int previousDisplay) {
this.previousDisplay = previousDisplay;
}
/**
* Sets the NodeSettings for the entire tree from the head down.
* These settings are used for drawing the node and the links of each given tree.
*
* @param s NodeSettings for use in drawing the entire tree.
* @param k KeySettings for use in drawing the keys of the entire tree.
*/
public void setTreeSettings(NodeSettings s, KeySettings k) {
if (!isDrawingBSTTree())
return;
setDrawingNodeSettings(s);
setDrawingKeySettings(k);
if (!isTreeEmpty()) {
((BSTTree)getChild()).setTreeSettings(s,k);
}
}
/**
* Sets the NodeSettings for the node of the head, used in creation of new nodes.
*
* @param s NodeSettings for use in drawing the nodes.
*/
public void setDrawingNodeSettings(NodeSettings s) {
if (!isDrawingBSTTree())
return;
nodeSettings = (NodeSettings)s.clone();
}
/**
* Sets the KeySettings for the key of the head, used in creation of new nodes.
*
* @param k KeySettings for use in drawing the keys.
*/
public void setDrawingKeySettings(KeySettings k) {
if (!isDrawingBSTTree())
return;
keySettings = (KeySettings)k.clone();
}
/**
* Sets the node width for the standard node. Generally defined in MakeTree.
*
* @param width the width of the node.
*/
protected void setNodeWidth(double width) {
if (!isDrawingBSTTree())
return;
nodeWidth = width;
}
/**
* Sets the node height for the standard node. Generally defined in MakeTree.
*
* @param height the height of the node.
*/
protected void setNodeHeight(double height) {
if (!isDrawingBSTTree())
return;
nodeHeight = height;
}
/**
* Sets the bounds of the screen to which the tree is drawing. Generally, these bounds
* are set using getClipBounds on the Graphics2D passed, however, the bounds
* can be set in any way.
*
* @param bounds the rectangle representing the bounds of the screen.
*/
public void setScreenBounds(Rectangle2D screen) {
if (!isDrawingBSTTree())
return;
screenBounds = screen;
}
/**
* Sets the height of the section, used for rendering the tree.
*
* @param height of the section, used for drawing the tree.
*/
protected void setSectionHeight(double height) {
if (!isDrawingBSTTree())
return;
sectionHeight = height;
}
/**
* Sets the background paint for the tree.
*
* @param background paint of the background.
*/
protected void setBackgroundColor(Color background) {
if (!isDrawingBSTTree())
return;
backgroundColor = background;
}
/**
/*****************************************
/* Settings for Animations. Can be set, *
/* even if the tree is a drawing type, *
/* but are only used if animating. *
/*****************************************
*/
/**
* Sets the NodeSettings for the left node settings for insertion.
*
* @return NodeSettings for the left node.
*/
public void setInsertNodeLeftSettings(NodeSettings n) {
insertNodeLeftSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the right node settings for insertion.
*
* @return NodeSettings for the right node.
*/
public void setInsertNodeRightSettings(NodeSettings n) {
insertNodeRightSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the animator node settings for insertion.
*
* @return NodeSettings for the animator node.
*/
public void setInsertAnimatorNodeSettings(NodeSettings n) {
insertAnimatorNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the KeySettings for the animator key settings for insertion.
*
* @return KeySettings for the animator key.
*/
public void setInsertAnimatorKeySettings(KeySettings k) {
insertAnimatorKeySettings = (KeySettings)k.clone();
}
/**
* Sets the NodeSettings for the left node settings for searching.
*
* @return NodeSettings for the left node.
*/
public void setSearchNodeLeftSettings(NodeSettings n) {
searchNodeLeftSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the right node settings for searching.
*
* @return NodeSettings for the right node.
*/
public void setSearchNodeRightSettings(NodeSettings n) {
searchNodeRightSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the animator node settings for searching.
*
* @return NodeSettings for the animator node.
*/
public void setSearchAnimatorNodeSettings(NodeSettings n) {
searchAnimatorNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the KeySettings for the animator key settings for searching.
*
* @return KeySettings for the animator key.
*/
public void setSearchAnimatorKeySettings(KeySettings k) {
searchAnimatorKeySettings = (KeySettings)k.clone();
}
/**
* Sets the NodeSettings for the left node settings for selection.
*
* @return NodeSettings for the left node.
*/
public void setSelectNodeLeftSettings(NodeSettings n) {
selectNodeLeftSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the right node settings for selection.
*
* @return NodeSettings for the right node.
*/
public void setSelectNodeRightSettings(NodeSettings n) {
selectNodeRightSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the animator node settings for selection.
*
* @return NodeSettings for the animator node.
*/
public void setSelectAnimatorNodeSettings(NodeSettings n) {
selectAnimatorNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the KeySettings for the animator key settings for selection.
*
* @return KeySettings for the animator key.
*/
public void setSelectAnimatorKeySettings(KeySettings k) {
selectAnimatorKeySettings = (KeySettings)k.clone();
}
/**
* Sets the NodeSettings for the root node settings for rotation.
*
* @return NodeSettings for the root node.
*/
public void setRotateRootNodeSettings(NodeSettings n) {
rotateRootNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the child node settings for rotation.
*
* @return NodeSettings for the child node.
*/
public void setRotateChildNodeSettings(NodeSettings n) {
rotateChildNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the descendant node settings for rotation.
*
* @return NodeSettings for the descendant node.
*/
public void setRotateDescendantNodeSettings(NodeSettings n) {
rotateDescendantNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the NodeSettings for the original node settings for rotation.
*
* @return NodeSettings for the original node.
*/
public void setRotateOriginalNodeSettings(NodeSettings n) {
rotateOriginalNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the KeySettings for the animator key settings for rotation.
*
* @return KeySettings for the animator key.
*/
public void setRotateAnimatorKeySettings(KeySettings k) {
rotateAnimatorKeySettings = (KeySettings)k.clone();
}
/**
* Sets the KeySettings for the original key settings for rotation.
*
* @return KeySettings for the original key.
*/
public void setRotateOriginalKeySettings(KeySettings k) {
rotateOriginalKeySettings = (KeySettings)k.clone();
}
/**
* Sets the PaintSettings for the left line of Paint.
*
* @return PaintSettings for the left line.
*/
public void setDeleteLeftLinePaintSettings(PaintSettings p) {
deleteLeftLinePaintSettings = (PaintSettings)p.clone();
}
/**
* Sets the PaintSettings for the right line of Paint.
*
* @return PaintSettings for the right line.
*/
public void setDeleteRightLinePaintSettings(PaintSettings p) {
deleteRightLinePaintSettings = (PaintSettings)p.clone();
}
/**
* Sets the NodeSettings for the animator node settings for traversal.
*
* @return NodeSettings for the animator node.
*/
public void setTraverseAnimatorNodeSettings(NodeSettings n) {
traverseAnimatorNodeSettings = (NodeSettings)n.clone();
}
/**
* Sets the KeySettings for the animator key settings for traversal.
*
* @return KeySettings for the animator key.
*/
public void setTraverseAnimatorKeySettings(KeySettings k) {
traverseAnimatorKeySettings = (KeySettings)k.clone();
}
/**
****************************************************
* DRAWING_BST_TREE_TYPE Overiding Methods *
****************************************************
*/
/**
* Makes and places the node into the tree. The node is returned for further manipulation.
*
* Specific methods for setting the original scheme.
*
* @param keyInsert comparable object which is added to the tree.
* @param valueInsert Object that accompanies keyInsert in the node.
*
* @return BSTTree that was recently inserted into the tree.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected BSTTree makeNodeDrawingType(Comparable keyInsert, Object valueInsert) {
BSTTree newNode = makeNodeTreeType(keyInsert, valueInsert);
newNode.setSettings(getDrawingNodeSettings());
((DrawableKey)newNode.getValue()).setSettings(getDrawingKeySettings());
return newNode;
}
/**
* Insert the comaparable node to the tree using its natural ordering .
*
* Call to insertTreeType
*
* @param node BSTTree node to be inserted into the tree
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected void insertDrawingType(BSTTree node) throws ClassCastException {
if (!isDrawingBSTTree()) {
insertTreeType(node);
return;
}
if (!(node.getValue() instanceof DrawableKey))
throw new ClassCastException();
insertTreeType(node);
node.setSettings(getDrawingNodeSettings());
((DrawableKey)node.getValue()).setSettings(getDrawingKeySettings());
}
/**
*********************************************************************
* DRAWING_BST_TREE_TYPE Drawing methods (DrawingTreeHead Interface) *
*********************************************************************
*/
/**
* Makes the entire tree from the null head down. The tree is made using the Graphics2D,
* and generally fills the entire Graphics2D parameter. This method allows the tree's
* drawing information to be defined without having to render the entire tree.
*
* @param g2 Graphics2D which the tree is made to fit unto.
*/
public void MakeTree(Graphics2D g2) {
if (!isDrawingBSTTree())
return;
if (isTreeEmpty())
return;
setScreenBounds(g2.getClipBounds());
setBackgroundColor(g2.getBackground());
// Maximum horizontal nodes possible based upon level (2^level)
double maxHorizontalNodes = (Math.pow(2.0, getTreeLevel()));
/* double sizeModification = (maxHorizontalNodes - 1) / (double)size();
if (sizeModification > 1) {
sizeModification *= .5;
}
if (sizeModification < 1) {
sizeModification = 1;
}
*/
AffineTransform scaleTransform;
AffineTransform translateTransform;
if (getDisplay() == SECTIONAL_DISPLAY) {
if (size() == 0) {
setNodeWidth(1);
}
else {
setNodeWidth(screenBounds.getWidth() / (size()));
}
LinkedList inorder = getInorderTree();
for (int i=0; i< inorder.size(); i++) {
((BSTTree)inorder.get(i)).setInorderCount(i+1);
}
// Set the height of the node using the ratio and maximum horizontal nodes
setNodeHeight((getScreenBounds().getHeight() / getTreeLevel())*.9);
if (getNodeWidth() < getNodeHeight()) {
setNodeHeight(getNodeWidth());
}
if (getNodeWidth() > (2*getNodeHeight())) {
setNodeWidth(getNodeHeight() * 2);
}
scaleTransform = AffineTransform.getScaleInstance(getNodeWidth(), getNodeHeight());
translateTransform = AffineTransform.getTranslateInstance(getScreenBounds().getX() - scaleTransform.getScaleX(),getScreenBounds().getY());
}
else {
// Set the width of the node using the maximum horizontal nodes
//setNodeWidth(screenBounds.getWidth() / (maxHorizontalNodes * .6) * sizeModification );
setNodeWidth(screenBounds.getWidth() / (maxHorizontalNodes * .6) );
// Set the height of the node using the ratio and maximum horizontal nodes
//setNodeHeight((getScreenBounds().getHeight() / (maxHorizontalNodes * .6) * sizeModification)/treeNodeWidthToHeightRatio );
setNodeHeight((getScreenBounds().getHeight() / (maxHorizontalNodes * .6) )/treeNodeWidthToHeightRatio );
scaleTransform = AffineTransform.getScaleInstance(getNodeWidth(), getNodeHeight());
translateTransform = AffineTransform.getTranslateInstance(getScreenBounds().getX() + getScreenBounds().getWidth()/2.0 - scaleTransform.getScaleX()/2.0,getScreenBounds().getY());
}
// Set the section height by dividing the entire height by the amount of levels.
setSectionHeight(getScreenBounds().getHeight() / (getTreeLevel()));
translateTransform.concatenate(scaleTransform);
// Recursive call
((BSTTree)getChild()).makeTree(translateTransform, 1);
}
/**
* Draws the entire tree from the null head down. The tree is drawn onto the Graphics2D,
* and uses the information defined in the previous call to MakeTree.
*
* @param g2 Graphics2D which the tree is drawn onto.
*/
public void DrawTree(Graphics2D g2) {
if (!isDrawingBSTTree())
return;
if (isTreeEmpty())
return;
((BSTTree)getChild()).drawTree(g2);
}
/**
* Finds the node represented by the x-y coordinates given. The (x,y) location represents a location
* within the Graphics2D to which the node appears. The recursive method progresses through the entire tree
* looking for the proper node.
*
* @param x x-coordinate to find the node.
* @param y y-coordinate to find the node.
*
* @return DrawingTree representing the x-y coordinates passed or null if no node is found.
*/
public DrawingTree findNode(double x, double y) {
if (!isDrawingBSTTree())
return null;
if (isTreeEmpty())
return null;
else
return ((BSTTree)getChild()).findNode(x, y);
}
/*-----------------------------------------------------------------------*/
/*----------------------------DRAWING_BST_TREE_TYPE----------------------*/
/*------------------------------------END--------------------------------*/
/*-----------------------------------------------------------------------*/
/*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
/*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/
/*-----------------------------------------------------------------------*/
/*---------------------------ANIMATING_BST_TREE_TYPE---------------------*/
/*-----------------------------------START-------------------------------*/
/*-----------------------------------------------------------------------*/
/*************************************************************************/
/* ANIMATING_BST_TREE_TYPE : Methods and Variables specific to the */
/* ANIMATING_BST_TREE_TYPE. These methods are specificaly used for */
/* animaitng to a Graphics2D. Therefore, do not use this type unless */
/* that is your purpose. */
/*************************************************************************/
/**
* The step size of the animations controlled by this AnimatingBSTTreeHead.
*/
private int animateStepSize;
/**
* The animators of the entire AnimatingBSTTree, held in the AnimatingBSTTreeHead.
*/
private LinkedList treeAnimators;
/**
* Boolean variable whether an animation needs to be removed.
*/
private boolean remove;
/**
* Boolean whether the Animation is jumping entire steps.
*/
private boolean jumpStep;
/**
* Boolean whether the Animation is pausing at steps.
*/
private boolean stepPause;
/**
* Status of the AnimatingBSTTree.
*/
private String treeStatus;
/**
* Constructor for the ANIMATING_BST_TREE_TYPE. This constructs and sets all values to defaults
* for the ANIMATING_BST_TREE_TYPE.
*/
public void constructAnimatingBSTTreeHead() {
if (treeAnimators == null) {
super.constructAnimatingBSTTree();
treeAnimators = new LinkedList();
animateStepSize = 16;
setRemove(false);
setJumpStep(false);
setStepPause(false);
setTreeStatus(Animation.PLAY);
waitingList = new WaitingActionList();
}
}
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Accesssor methods *
*********************************************
*/
/**
* Gets whether the AnimatingBSTTreeHead is removing an Animation.
*
* @return boolean value as to whether the tree is removing an Animation.
*/
public boolean isTreeRemove() {
return remove;
}
/**
* Gets the first Animation in the list of Animations for the Head and null if no
* Animations are present.
*
* @return first Animation in the Animation list.
*/
public Animation getTreeAnimator() {
if (!isAnimatingBSTTree()) {
return null;
}
return (Animation)treeAnimators.getFirst();
}
/**
* Returns true if the current AnimatingBSTTreeHead is animating (whether the animating list
* is empty.
*
* @return true if the current tree is animating and not empty.
*/
public boolean isTreeAnimating() {
if (!isAnimatingBSTTree()) {
return false;
}
return (!treeAnimators.isEmpty() && (!isTreeEmpty()));
}
/**
* Gets the JumpStep of the current tree.
*
* @return true if the tree is jumpSteping.
*/
public boolean isJumpStep() {
return jumpStep;
}
/**
* Gets the StepPause of the current tree.
*
* @return true if the tree is pausing at the completion of each step.
*/
public boolean isStepPause() {
return stepPause;
}
/**
* Gets the step size of the Animations of the tree.
*
* @return integer step size of the tree.
*/
public int getTreeAnimationStepSize() {
return animateStepSize;
}
/**
* Gets the Tree's status, using the String status of Animation.
*
* @return String status of the Tree, representing the Animation status.
*/
public String getTreeStatus() {
return treeStatus;
}
/**
*******************************************
* ANIMATING_BST_TREE_TYPE Mutator methods *
*******************************************
*/
/**
* Sets whether the AnimatingBSTTreeHead is removing an Animation, because
* multiple Animations may occur simultaneously.
*
* @param b boolean value as to whether the tree is removing an Animation.
*/
protected void setRemove(boolean b) {
if (!isAnimatingBSTTree()) {
return;
}
remove = b;
}
/**
* Clears the Animations from the list of Animations for the Head.
*/
public void clearAnimators() {
if (!isAnimatingBSTTree()) {
return;
}
treeAnimators.clear();
}
/**
* Adds the Animation to the list of Animations for the Head. The method does
* not add the tree as a listener to the Animation. That must be accomplished by
* the client.
*
* @param a Animation added to the Animation list.
*/
public void addTreeAnimator(Animation a) {
if (!isAnimatingBSTTree()) {
return;
}
treeAnimators.add(a);
}
/**
* Quickly removes all Animations within the Tree. The method sets the Status of all the
* Animations to Animation.FINISH so that al listeners of the Animations will
* receive the AnimationEvent.
*/
public void removeTreeAnimation() {
if (!isAnimatingBSTTree()) {
return;
}
setTreeAnimationStatus(Animation.FINISH);
setTreeAnimationStatus(Animation.PLAY);
}
/**
* Sets the JumpStep of the current tree to the boolean value. The jumpStep determines whether
* the Animation skips through an entire step at each AnimateTree call.
*
* @param b sets the jumpStep to the value b.
*/
public void setJumpStep(boolean b) {
jumpStep = b;
if (!isAnimatingBSTTree()) {
return;
}
}
/**
* Sets the StepPause of the current tree to the boolean value. The stepPause determines whether
* the Animation pauses after each step of the Animation completes.
*
* @param b sets the stepPause to the value b.
*/
public void setStepPause(boolean b) {
stepPause = b;
if (!isAnimatingBSTTree()) {
return;
}
if (stepPause) {
// Pauses the current Tree.
setTreeAnimationStatus(Animation.PAUSE);
}
else {
// Restarts the Tree.
setTreeAnimationStatus(treeStatus);
}
}
/**
* Sets the step size of the Animations of the tree. The integer value
* is passed to every Animation's setStepTime method.
*
* @param t integer step size setting.
*/
public void setTreeAnimationsStepSize(int t) {
animateStepSize = t;
if (!isAnimatingBSTTree()) {
return;
}
ListIterator animateList = treeAnimators.listIterator(0);
while(animateList.hasNext()) {
((Animation)animateList.next()).setStepTime(t);
}
}
/**
* Sets the Status of the entire tree, using the status of Animation class.
*
* @param s String status to set the Tree's Status.
*/
public void setTreeStatus(String s) {
treeStatus = s;
if (!isAnimatingBSTTree()) {
return;
}
if ((treeStatus == null) || (!treeStatus.equals(s))) {
setTreeAnimationStatus(s);
}
}
/**
* Sets the TreeStatus, and resets the status of all Animations within the current Tree.
*
* @param cmd String Status which sets the treeStatus and the entire list of Animations currently
* controlled by he tree.
*/
private void setTreeAnimationStatus(String cmd) {
treeStatus = cmd;
ListIterator animateList = treeAnimators.listIterator(0);
while(animateList.hasNext()) {
// Reset all values.
Animation animator = ((Animation)animateList.next());
animator.setStep(isJumpStep());
animator.setStatus(getTreeStatus());
}
}
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Overiding methods *
*********************************************
*/
/**
* Inserts the comaparable node to the tree using its natural ordering .
*
*
Call to insertDrawingType
*
* @param node BSTTree node to be inserted into the tree
* @throws ClassCastException key cannot be compared with the keys
* currently in the map.
*/
protected void insertAnimatingType(BSTTree node) throws ClassCastException {
if ((!isAnimatingBSTTree()) || (isTreeEmpty())) {
insertDrawingType(node);
return;
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating() && !(treeAnimators.getFirst() instanceof InsertBSTAnimation)) {
waitingList.add(AnimatingTreeHead.INSERT_NODE, node);
return;
}
Animation insertAnimator = makeInsertAnimation(node);
// Add animation and recieve listening events.
this.addTreeAnimator(insertAnimator);
insertAnimator.addAnimationListener(this);
// Add animation to the inserting node.
node.addAnimator(insertAnimator);
insertAnimator.addAnimationListener(node);
// Super call
insertDrawingType(node);
// Add the final location, after the tree is built.
((InsertBSTAnimation)insertAnimator).add(node);
}
/**
* Searches for the Tree in the entire tree.
*
*
Call to searchTreeType
*
* @param keySearch the comparable key which is searched for within the tree.
* @return Tree the Tree found or null if keySearch was not present within the tree.
*/
protected Tree searchAnimatingType(Comparable keySearch) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return searchTreeType(keySearch);
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.SEARCH, keySearch);
return null;
}
Animation searchAnimator = makeSearchAnimation(keySearch);
// Add tree animator.
this.addTreeAnimator(searchAnimator);
searchAnimator.addAnimationListener(this);
return searchTreeType(keySearch);
}
/**
* Selects for the Tree in the entire tree.
*
*
Call to selectTreeType
*
* @param keySelect integer key selecting the count item.
* @return Tree the Tree found or null.
*/
protected Tree selectAnimatingType(BSTTree node, int keySelect) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return selectTreeType(node, keySelect);
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.SELECT, new NodeAndKey(node, keySelect));
return null;
}
Animation selectAnimator = makeSelectionAnimation(node , keySelect);
// Add tree animator.
this.addTreeAnimator(selectAnimator);
selectAnimator.addAnimationListener(this);
return selectTreeType(node, keySelect);
}
/**
* Rotates the node up in the BSTTree.
*
* @param node BSTTree node that is rotated up.
*/
protected void rotateUpAnimatingType(BSTTree node) {
boolean oldDisplayChange = false;
if (!isAnimatingBSTTree()) {
rotateUpTreeType(node);
return;
}
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// Get the parent for rotation.
BSTTree nodeParent = (BSTTree)node.getParentTree();
if (nodeParent == this) {
return;
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.ROTATE_UP, node);
if (oldDisplayChange) {
oldDisplayChange = false;
changeDisplay();
}
return;
}
Animation rotateUpAnimator = makeRotationAnimation(node);
// Add animation and recieve listening events.
this.addTreeAnimator(rotateUpAnimator);
rotateUpAnimator.addAnimationListener(this);
if (oldDisplayChange) {
changeDisplay();
}
}
/**
* Double Rotates the node up in the BSTTree.
*
* @param node BSTTree node that is rotated up twice.
*/
protected void rotateUpDoubleAnimatingType(BSTTree node) {
boolean oldDisplayChange = false;
if (!isAnimatingBSTTree()) {
rotateUpDoubleTreeType(node);
return;
}
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.ROTATE_UP_DOUBLE, node);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
Animation rotateUpDoubleAnimator = makeRotationDoubleAnimation(node);
// Add animation and recieve listening events.
this.addTreeAnimator(rotateUpDoubleAnimator);
rotateUpDoubleAnimator.addAnimationListener(this);
if (oldDisplayChange) {
changeDisplay();
}
}
/**
* Splays the node up in the BSTTree.
*
* @param node BSTTree node that is splayed.
*/
protected void splayAnimatingType(BSTTree node) {
if (!isAnimatingBSTTree()) {
splayTreeType(node);
return;
}
boolean oldDisplayChange = false;
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// If Animation is occuring, add SPLAY_CLICK to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.SPLAY_NODE, node);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
messageAction("*-----Splaying "+node.getKey().toString()+ "-----*");
if (waitingList.isEmpty()) {
if ( (node.getLevel() != 2) && ( (node.getLevel() % 2) == 0) ) {
messageAction("Start with a single rotation");
// If the amount of nodes is odd, do a single rotation first
rotateUp(node);
rotateUpDouble(node, node.getLevel()/2);
}
else {
// No single rotation necessary
rotateUpDouble(node, node.getLevel() / 2);
}
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
else {
if ( (node.getLevel() != 2) && ( (node.getLevel() % 2) == 0) ) {
// This is done because it is assumed it will return here before the rotation completes (Grandparent which is future parent)
for (int i = 0; i < node.getLevel()/ 2; i++) {
waitingList.addFirst(AnimatingTreeHead.ROTATE_UP_DOUBLE, node);
}
// If the amount of nodes is odd, do a single rotation first
waitingList.addFirst(AnimatingTreeHead.ROTATE_UP, node);
}
else {
// If Animation is occuring, add ROTATE_UP to the waitingList.
for (int i = 0; i < node.getLevel()/ 2; i++) {
waitingList.addFirst(AnimatingTreeHead.ROTATE_UP_DOUBLE, node);
}
}
}
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
}
/**
* Rotates to top the node in the BSTTree.
*
* @param node BSTTree node that is splayed.
*/
protected void rotateToTopAnimatingType(BSTTree node) {
if (!isAnimatingBSTTree()) {
rotateToTopTreeType(node);
return;
}
boolean oldDisplayChange = false;
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// If Animation is occuring, add SPLAY_CLICK to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.ROTATE_TO_TOP_NODE, node);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
messageAction("*-----Rotating To Top "+node.getKey().toString()+ "-----*");
if (waitingList.isEmpty()) {
rotateUp(node, node.getLevel());
}
else {
// If Animation is occuring, add ROTATE_UP to the waitingList.
for (int i = 0; i < node.getLevel(); i++) {
waitingList.addFirst(AnimatingTreeHead.ROTATE_UP, node);
}
}
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
}
/**
* Removes the node in the BSTTree. The method is overiden to allow for animation of the deletion.
* After the DeleteBSTAnimation is built, using the node, the super remove method is called.
*
* @param node BSTTree node that is deleted.
*/
protected void removeAnimatingType(BSTTree node) {
if (!isAnimatingBSTTree()) {
removeTreeType(node);
return;
}
boolean oldDisplayChange = false;
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// If Animation is occuring, add REMOVE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.REMOVE_NODE, node);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
Animation removeAnimator = makeDeletionAnimation(node);
// Add tree animator.
this.addTreeAnimator(removeAnimator);
removeAnimator.addAnimationListener(this);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
}
/**
* Partitions from the given node the keySelect value. Replacing the reference in the
* Tree to the given node, to the keySelectth item.
*
*
Call to selectTreeType
*
* @param Tree which the partition occurs at.
* @param keySelect integer key selecting the count item.
* @return Tree that is the reference to the newly partitioned tree (Using selectTreeType).
*/
protected Tree partitionAnimatingType(BSTTree node, int keySelect) {
if (!isAnimatingBSTTree()) {
return partitionTreeType(node, keySelect);
}
boolean oldDisplayChange = false;
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// If Animation is occuring, add REMOVE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.PARTITION_NODE, new NodeAndKey(node, keySelect));
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return null;
}
Animation partitionAnimator = makePartitionAnimation(node, keySelect);
// Add tree animator.
this.addTreeAnimator(partitionAnimator);
partitionAnimator.addAnimationListener(this);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return selectTreeType(node, keySelect);
}
/**
* Balances the tree from the given node, recursively rotating the median to the top.
* The method is overiden to allow for animation of the balancing, simply calling balanceTREE
* if no waiting action appears.
*
* @param node BSTTree that is balanced from.
*/
public void balanceAnimatingType(BSTTree node) {
if (!isAnimatingBSTTree()) {
balanceTreeType(node);
return;
}
boolean oldDisplayChange = false;
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
if (node.size() <= 2)
return;
// If Animation is occuring, add REMOVE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.BALANCE_NODE, node);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
Animation balanceAnimator = makeBalanceAnimation(node);
this.addTreeAnimator(balanceAnimator);
balanceAnimator.addAnimationListener(this);
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
}
/**
* Traverses the tree in the given traversal type.
*
* @param traverseType int defining the given traversal type.
*
*/
public LinkedList traverseAnimatingType(int traverseType) {
if (!isAnimatingBSTTree()) {
return traverseTreeType(traverseType);
}
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.TRAVERSE, new Integer(traverseType));
return traverseTreeType(traverseType);
}
LinkedList traversal;
if (traverseType == PREORDER_TRAVERSAL) {
messageAction("*-----Preorder Traversal-----*");
messageAction("1) Visit the node");
messageAction("2) Visit the left child");
messageAction("3) Visit the right child\n");
traversal = getPreorderTree();
}
else if (traverseType == INORDER_TRAVERSAL) {
messageAction("*-----Inorder Traversal-----*");
messageAction("1) Visit the left chiild");
messageAction("2) Visit the node");
messageAction("3) Visit the right child\n");
traversal = getInorderTree();
}
else if (traverseType == POSTORDER_TRAVERSAL) {
messageAction("*-----Postorder Traversal-----*");
messageAction("1) Visit the left child");
messageAction("2) Visit the right child");
messageAction("3) Visit the node\n");
traversal = getPostorderTree();
}
else if (traverseType == LEVELORDER_TRAVERSAL) {
messageAction("*-----Levelorder Traversal-----*");
messageAction("Visit all nodes on each level, in order.\n");
traversal = getLevelorderTree();
}
else {
traversal = new LinkedList();
}
Animation traverseAnimator = makeTraverseAnimation(traversal);
this.addTreeAnimator(traverseAnimator);
traverseAnimator.addAnimationListener(this);
return traversal;
}
/**
* Change Display of the BSTTree.
*/
public void changeDisplayAnimatingType() {
if (!isAnimatingBSTTree()) {
changeDisplayTreeType();
}
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.CHANGE_DISPLAY);
return;
}
Animation changeDisplayAnimator = makeChangeDisplayAnimation();
this.addTreeAnimator(changeDisplayAnimator);
changeDisplayAnimator.addAnimationListener(this);
}
/**
****************************************************
* ANIMATING_BST_TREE_TYPE Constructing Animations *
****************************************************
*/
/**
* Makes an insert Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param insertNode BSTTree node that the insert Animation is built for.
* @return Animation that represents the insertAnimation.
*/
public Animation makeInsertAnimation(BSTTree insertNode) {
if (!isAnimatingBSTTree()) {
return null;
}
// Head node (backup test).
if (insertNode == this)
return null;
// Construct animation for Insert.
InsertBSTAnimation newAnimator = new InsertBSTAnimation(insertNode,getInsertNodeLeftSettings(),getInsertNodeRightSettings(),getInsertAnimatorNodeSettings(), getInsertAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
// Starting Animation.
//AffineTransform a = AffineTransform.getScaleInstance(getScreenBounds().getWidth() * .35, getScreenBounds().getHeight() * .35);
// Add initial animation.
//newAnimator.add(a);
// Recursive call to insert the tree, starting at the head level.
((BSTTree)getChild()).makeInsertAnimation(insertNode, newAnimator);
return newAnimator;
}
/**
* Makes a search Animation using the given keySearch. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param keySearch the comparable object which is search for within the tree.
*/
public Animation makeSearchAnimation(Comparable keySearch) {
if (!isAnimatingBSTTree()) {
return null;
}
SearchBSTAnimation newAnimator = new SearchBSTAnimation(keySearch, this, getSearchNodeLeftSettings(),getSearchNodeRightSettings(),getSearchAnimatorNodeSettings(), getSearchAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
// Recursive call to insert the tree, starting at the head level.
((BSTTree)getChild()).makeSearchAnimation(keySearch, newAnimator);
return newAnimator;
}
/**
* Makes a select Animation using the given keySelect. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param keySelect the int which is selected for within the tree.
*/
public Animation makeSelectionAnimation(BSTTree node, int keySelect) {
if (!isAnimatingBSTTree()) {
return null;
}
SelectionBSTAnimation newAnimator = new SelectionBSTAnimation(keySelect, getSelectNodeLeftSettings(),getSelectNodeRightSettings(),getSelectAnimatorNodeSettings(), getSelectAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
// Recursive call to insert the tree, starting at the head level.
node.makeSelectionAnimation(keySelect, newAnimator);
return newAnimator;
}
/**
* Makes a rotation Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the rotation Animation is built from.
* @return Animation that represents the rotationAnimation.
*/
public Animation makeRotationAnimation(BSTTree node) {
if (!isAnimatingBSTTree()) {
return null;
}
// Get parent.
BSTTree nodeParent = (BSTTree)node.getParentTree();
// Make a new animation.
RotationBSTAnimation newAnimator;
// Check if node is left or right subtree.
if (node == nodeParent.getLeftTree() ) {
newAnimator = new RotationBSTAnimation(nodeParent, node, RotationBSTAnimation.RIGHT_ROTATION, getRotateRootNodeSettings(), getRotateChildNodeSettings(), getRotateDescendantNodeSettings(), getRotateOriginalNodeSettings(), getRotateAnimatorKeySettings(), getRotateOriginalKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
}
else {
newAnimator = new RotationBSTAnimation(nodeParent, node, RotationBSTAnimation.LEFT_ROTATION,getRotateRootNodeSettings(), getRotateChildNodeSettings(), getRotateDescendantNodeSettings(), getRotateOriginalNodeSettings(), getRotateAnimatorKeySettings(), getRotateOriginalKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
}
return newAnimator;
}
/**
* Makes a deletion Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the deletion Animation is built from.
* @return Animation that represents the deleteAnimation.
*/
public Animation makeDeletionAnimation(BSTTree node) {
if (!isAnimatingBSTTree()) {
return null;
}
// If this is the node to be deleted (precautionary check).
if (node == this)
return null;
// New deletion animation.
DeleteBSTAnimation newAnimator = new DeleteBSTAnimation(node, getDeleteLeftLinePaintSettings(), getDeleteRightLinePaintSettings(), getTreeStatus(), getTreeAnimationStepSize());
return newAnimator;
}
/**
* Makes a partition Animation using the given node and given keySelect. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the deletion Animation is built from.
* @param keySelect finds the keySelectth node and rotates it to the top.
* @return Animation that represents the deleteAnimation.
*/
public Animation makePartitionAnimation(BSTTree node, int keySelect) {
if (!isAnimatingBSTTree()) {
return null;
}
// If this is the node to be deleted (precautionary check).
if (node == this)
return null;
// New deletion animation.
PartitionBSTAnimation newAnimator = new PartitionBSTAnimation(node, keySelect, getTreeStatus(),getTreeAnimationStepSize());
return newAnimator;
}
/**
* Makes a balance Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the balance Animation is built from.
* @return Animation that represents the balanceAnimation.
*/
public Animation makeBalanceAnimation(BSTTree node) {
if (!isAnimatingBSTTree()) {
return null;
}
// If this is the node to be deleted (precautionary check).
if (node == this)
return null;
// New balance animation.
BalanceBSTAnimation newAnimator = new BalanceBSTAnimation(node, getTreeStatus(), getTreeAnimationStepSize());
return newAnimator;
}
/**
* Makes a rotationDouble Animation using the given node. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param node BSTTree node that the doubleRotation Animation is built from.
* @return Animation that represents the balanceAnimation.
*/
public Animation makeRotationDoubleAnimation(BSTTree node) {
if (!isAnimatingBSTTree()) {
return null;
}
// If this is the node to be deleted (precautionary check).
if (node == this)
return null;
// New balance animation.
RotationDoubleBSTAnimation newAnimator = new RotationDoubleBSTAnimation(node, getTreeStatus(), getTreeAnimationStepSize());
return newAnimator;
}
/**
* Makes a traverse Animation using the given LinkedList. The Animation adds no listeners, making
* the client have to add the listeners.
*
* @param nodeList the LinkedList containing the nodes that are the path of the traversal.
*/
public Animation makeTraverseAnimation(LinkedList nodeList) {
if (!isAnimatingBSTTree()) {
return null;
}
TraverseBSTAnimation newAnimator = new TraverseBSTAnimation(getTraverseAnimatorNodeSettings(),getTraverseAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
int listSize = nodeList.size();
for (int i =0; iAnimations are drawn.
*/
public void AnimateTree(Graphics2D g2) {
// Not an animatingBSTTree
if (!isAnimatingBSTTree()) {
if (treeAnimators == null)
return;
if (treeAnimators.isEmpty())
return;
// Set status to FINISH
setTreeAnimationStatus(Animation.FINISH);
int size = treeAnimators.size();
for (int i = 0; (i < size); i++) {
//Gets the next Animation
Animation animator = (Animation)treeAnimators.get(i);
// Draws the Animation with FINISH status
animator.drawAnimation(g2);
}
// Removes the Animation.
treeAnimators.clear();
if (waitingList == null)
return;
// Clear waitingList
while (!waitingList.isEmpty()) {
waitingList.nextAction(this);
}
return;
}
// Is an animatingBSTTree
// Sets the remove status to false.
setRemove(false);
// Counting variables. i Counts the current Animation, and removingNode keeps the node to
// be removed.
int i, removingNode;
int size = treeAnimators.size();
for (i = 0; (i < size); i++) {
//Gets the next Animation
Animation animator = (Animation)treeAnimators.get(i);
// Draws the Animation.
animator.drawAnimation(g2, getTreeStatus());
// If remove is set
if (isTreeRemove()) {
// Store the node to be removed.
removingNode = i;
i++;
// Continue through the Animations, Pausing the other Animations and drawing them paused.
for ( ; (i < treeAnimators.size()); i++) {
animator = (Animation)treeAnimators.get(i);
animator.setStatus(Animation.PAUSE);
animator.drawAnimation(g2, getTreeStatus());
animator.setStatus(getTreeStatus());
}
// Removes the Animation.
treeAnimators.remove(removingNode);
}
}
// If the Animations complete
while (!isTreeAnimating()) {
if (waitingList.isEmpty()) {
return;
}
// WaitingActions are performed.
else {
messageAction(Animation.REDRAW);
waitingList.nextAction(this);
}
}
}
/**
* Sets the status of the AnimatingBSTTree to play.
*/
public void play() {
if (!isAnimatingBSTTree()) {
return;
}
setTreeAnimationStatus(Animation.PLAY);
}
/**
* Sets the status of the AnimatingBSTTree to stop.
*/
public void stop() {
if (!isAnimatingBSTTree()) {
return;
}
setTreeAnimationStatus(Animation.STOP);
}
/**
* Sets the status of the AnimatingBSTTree to rewind.
*/
public void rewind() {
if (!isAnimatingBSTTree()) {
return;
}
setTreeAnimationStatus(Animation.REWIND);
}
/**
* Sets the status of the AnimatingBSTTree to pause.
*/
public void pause() {
if (!isAnimatingBSTTree()) {
return;
}
setTreeAnimationStatus(Animation.PAUSE);
}
/**
********************************************************
* ANIMATING_BST_TREE_TYPE Implements AnimationListener *
********************************************************
*/
/**
* Implements AnimationListener which requires the following method.
* The only status of animation it listens for is Animation.FINISH, to remove
* the animation from the animators list and Animation.STEP, to possible pause
* the animation if stepPause is true.
*
* @param e AnimationEvent that represents the information of the Animation.
*/
public void animationEventPerformed(AnimationEvent e) {
if (!isAnimatingBSTTree()) {
if (e.getStatus().equals(Animation.ANIMATION_MESSAGE)) {
messageAction(e.getAnimationDescription(), e.getSource());
}
return;
}
if (e.getStatus().equals(Animation.FINISH)) {
setRemove(true);
if (e.getID() == AnimationEvent.BALANCE_BST_ANIMATION) {
if (waitingList.isEmpty()) {
balance((BSTTree)((BalanceBSTAnimation)e.getSource()).getReplacingNode().getLeftTree());
balance((BSTTree)((BalanceBSTAnimation)e.getSource()).getReplacingNode().getRightTree());
}
else {
// If Animation is occuring, add ROTATE_UP to the waitingList.
waitingList.addFirst(AnimatingTreeHead.BALANCE_NODE, (BSTTree)((BalanceBSTAnimation)e.getSource()).getReplacingNode().getRightTree());
waitingList.addFirst(AnimatingTreeHead.BALANCE_NODE, (BSTTree)((BalanceBSTAnimation)e.getSource()).getReplacingNode().getLeftTree());
}
}
}
if (e.getStatus().equals(Animation.STEP)) {
if(isStepPause()) {
((Animation)e.getSource()).setStatus(Animation.PAUSE);
}
}
if (e.getStatus().equals(Animation.ANIMATION_MESSAGE)) {
messageAction(e.getAnimationDescription(), e.getSource());
}
}
}