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 GrowingTreeHeadextends GrowingTreeNode
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. */ /*************************************************************************/ private IInsertOperator
insertOperator; private ISearchOperator
searchOperator; private IDeleteOperator
deleteOperator; private P nodePropertiesFactory; private IExperimentLogger
logger;
/**
* The list of listeners to this Tree. Used when the command waitingList;
/**
* Constructs a new, null BSTTreeHead, sorted according to the keys' natural
* order.
*
* Default type is BST_TREE_TYPE.
*/
public GrowingTreeHead() {
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:
* inserter, ISearchOperator searcher,
IDeleteOperator deleter,
TreeJPanel panel) {
this(GrowingTreeHead.ANIMATING_BST_TREE_TYPE);
insertOperator = inserter;
searchOperator = searcher;
deleteOperator = deleter;
nodePropertiesFactory = np;
}
public GrowingTreeHead(P np, IInsertOperator inserter, ISearchOperator searcher,
IDeleteOperator deleter,
TreeJPanel panel, IExperimentLogger logger) {
this(GrowingTreeHead.ANIMATING_BST_TREE_TYPE);
insertOperator = inserter;
searchOperator = searcher;
deleteOperator = deleter;
nodePropertiesFactory = np;
this.logger = logger;
}
/**
* Sets the tree type for the BSTTree. It additionally checks constructors for the head.
*
* @param treeType setting for the tree.
*/
public void setTreeType(int treeType) {
super.setTreeType(treeType);
checkHeadConstructors();
if (getChild() != null)
((GrowingTreeNode )getChild()).fixTreeType(treeType);
}
/**
* Checks the tree type and determines the appropriate construction necessary for the head.
* Generally called every time the tree type changes.
*/
private void checkHeadConstructors() {
if (getTreeType() >= BST_TREE_TYPE) {
constructBSTTreeHead();
}
if (getTreeType() >= DRAWING_BST_TREE_TYPE) {
constructDrawingBSTTreeHead();
}
if (getTreeType() >= ANIMATING_BST_TREE_TYPE) {
constructAnimatingBSTTreeHead();
}
}
/**
* Calls all of the listeners of the Tree and passes the tree message information information regarding the
* status of the Tree.
*
* @param msg String message being passed to all TreeMessage listeners.
*
*/
protected void messageAction(String msg) {
messageAction(msg, null);
}
/**
* Calls all of the listeners of the Tree and passes the tree message information information regarding the
* status of the Tree.
*
* @param msg String message being passed to all TreeMessage listeners.
* @param msgObj Object related to the message and usable by all listeners.
*/
protected void messageAction(String msg, Object msgObj) {
TreeMessageEvent messageEvent = new TreeMessageEvent(this, TreeMessageEvent.TREE, msg, msgObj);
ListIterator element) {
// insert.
if (action.equals(TreeHead.INSERT_NODE)) {
insert(element.getBSTTreeValue());
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 (!element.getBSTTreeValue().inTree())
return;
rotateUp(element.getBSTTreeValue());
}
// rotateUpDouble.
if (action.equals(TreeHead.ROTATE_UP_DOUBLE)) {
// Check if currently in the tree.
if (!element.getBSTTreeValue().inTree())
return;
rotateUpDouble(element.getBSTTreeValue());
}
// balance
if (action.equals(TreeHead.BALANCE_NODE)) {
// Check if currently in the tree.
if (!element.getBSTTreeValue().inTree())
return;
balance(element.getBSTTreeValue());
}
// remove
if (action.equals(TreeHead.REMOVE_NODE)) {
// Check if currently in the tree.
if (!element.getBSTTreeValue().inTree())
return;
remove(element.getBSTTreeValue());
}
// search
if (action.equals(TreeHead.SEARCH)) {
search(element.getKeyTypeValue());
}
// select
if (action.equals(TreeHead.SELECT)) {
select(element.getNodeAndKeyValue().getNode() , element.getNodeAndKeyValue().getKey() );
}
// swap
if (action.equals(TreeHead.SWAP)) {
swapAnimatingType(element.getNodeAndKeyValue().getNode() , element.getNodeAndKeyValue().getKey() );
}
// partition
if (action.equals(TreeHead.PARTITION_NODE)) {
partition(element.getNodeAndKeyValue().getNode() , element.getNodeAndKeyValue().getKey() );
}
if (action.equals(TreeHead.FREEZE)) {
freezeAnimatingType(element.getDoubleValue());
}
// splay
if (action.equals(TreeHead.SPLAY_NODE)) {
splayAnimatingType(element.getBSTTreeValue());
}
// rotate to top
if (action.equals(TreeHead.ROTATE_TO_TOP_NODE)) {
rotateToTopAnimatingType(element.getBSTTreeValue());
}
// rotate to top
if (action.equals(TreeHead.TRAVERSE)) {
traverse(element.getIntegerValue());
}
// rotate to top
if (action.equals(TreeHead.CHANGE_DISPLAY)) {
changeDisplay();
}
}
/**
* Gets the getWaitingList() {
return waitingList;
}
/*-----------------------------------------------------------------------*/
/*-------------------------------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;
/**
* True if integer fields should be drawn, false otherwise
*/
private boolean integerFieldsVisible = false;
/**
* 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 Accessor methods *
**********************************
*/
public IExperimentLogger getLogger() {
return logger;
}
/**
* Returns true if the )getChild()) == null);
}
/**
* Gets the child of the TreeHead. The child is the beginning of the Tree nodes.
*
* @param child getChild() {
return getLeftNodeInternal();
}
/**
* Gets the lowest level of the Tree. A level of 0 indicates an empty tree.
*
* @return integer level set for the )getChild()).size();
}
}
public boolean getSubtreeCountsVisible()
{
return integerFieldsVisible;
}
/**
**********************************
* BST_TREE_TYPE Mutator methods *
**********************************
*/
public void setSubtreeCountsVisible(boolean visible)
{
integerFieldsVisible = visible;
}
/**
* Sets the child of the TreeHead. The child is the beginning of the Tree nodes.
*
* @param child child) {
// Make the left subtree the child, saving links already defined by extending BSTTree.
setLeftTree((GrowingTreeNode )child);
}
/**
* Sets the lowest level of the )getChild()).fixLevel(1);
if (getChild().isEmpty()) {
setChild(null);
}
}
/**
* Fixes the size of each subtree, using recursive calls into the BSTTree.
*/
public int fixSize() {
// bug fix: if tree is empty, child is null
if (getChild() == null)
return size();
setSize(((GrowingTreeNode )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 GrowingTreeNode makeNode(KeyType 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(KeyType keyInsert, Object valueInsert) throws NullPointerException, ClassCastException {
if (keyInsert == null)
throw new NullPointerException();
if (!isTreeEmpty() && ((GrowingTreeNode )getChild()).contains(keyInsert))
return false;
int oldSize = size();
GrowingTreeNode newTree = makeNode(keyInsert,valueInsert);
if (!isTreeEmpty()) {
insertOperator.doInsert(((GrowingTreeNode ) getChild()).getShadowNode(),
((GrowingTreeNode ) newTree).getShadowNode());
}
else {
if (isAnimatingBSTTree()) {
insertAnimatingType((GrowingTreeNode )newTree);
}
else if (isDrawingBSTTree()) {
insertDrawingType((GrowingTreeNode )newTree);
}
else {
insertTreeType((GrowingTreeNode )newTree);
}
insertOperator.doInsert(((GrowingTreeNode ) newTree).getShadowNode(), null);
}
// Check correct insertion.
if (size() == (oldSize + 1)) {
return true;
}
return true;
}
/**
* 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((GrowingTreeNode )node);
}
else if (isDrawingBSTTree()) {
insertDrawingType((GrowingTreeNode )node);
}
else {
insertTreeType((GrowingTreeNode )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 node, boolean successorSwap) {
saveTreeProperties();
GrowingTreeNode n = (GrowingTreeNode ) node;
remove(n);
}
public void remove(Tree node) {
if (isAnimatingBSTTree()) {
removeAnimatingType((GrowingTreeNode ) node);
}
else {
popTreeProperties();
removeTreeType((GrowingTreeNode ) node);
}
}
/**
* Removes the comaparable object keyRemove from the removingNode = (GrowingTreeNode )searchTreeType(keyRemove);
if (!removingNode.getKey().equals(keyRemove)) {
return false;
}
deleteOperator.doDelete(((GrowingTreeNode )getChild()).getShadowNode(),
((GrowingTreeNode )removingNode).getShadowNode());
//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((GrowingTreeNode )node);
}
else {
balanceTreeType((GrowingTreeNode )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((GrowingTreeNode )node, keySelect);
}
else {
return partitionTreeType((GrowingTreeNode )node, keySelect);
}
}
/**
* Searches for the comaparable object in the search(KeyType keySearch) throws ClassCastException, NullPointerException {
if (keySearch == null)
throw new NullPointerException();
if (isTreeEmpty())
return null;
GrowingTreeNode searchNode = makeNode(keySearch, null);
if (isAnimatingBSTTree()) {
ShadowNode shadow = (ShadowNode ) searchOperator.doSearch(((GrowingTreeNode ) getChild()).getShadowNode(),
((GrowingTreeNode ) searchNode).getShadowNode());
if (shadow == null) return null;
return shadow.getGrowingNode();
}
else {
return (GrowingTreeNode )searchTreeType(keySearch);
}
}
/**
* Selects the kth smallest item in the select(Tree node, int keySelect) {
if (isTreeEmpty())
return null;
if (keySelect >= node.size() || keySelect < 0)
return null;
Tree returnNode;
if (isAnimatingBSTTree()) {
returnNode = selectAnimatingType((GrowingTreeNode )node, keySelect);
}
else {
returnNode = selectTreeType((GrowingTreeNode )node, keySelect);
}
if (returnNode != null)
return returnNode;
else
return selectTreeType((GrowingTreeNode )node, keySelect);
}
/**
* Swaps node with the the kth smallest item in its subtree 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 void swapNodes(Tree node, int keySelect) {
if (isTreeEmpty())
return;
if (keySelect >= node.size() || keySelect < 0)
return;
select(node, keySelect);
if (isAnimatingBSTTree()) {
swapAnimatingType((GrowingTreeNode )node, keySelect);
}
else {
swapTreeType((GrowingTreeNode )node, keySelect);
}
}
public void freeze(double lengthMult) {
if (!isAnimatingBSTTree()) {
return;
}
saveTreeProperties();
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.FREEZE, new ActionElementType (lengthMult));
return;
}
freezeAnimatingType(lengthMult);
}
public void freezeAnimatingType(double lengthMult) {
Animation freezeAnimator = makeFreezeAnimation(lengthMult);
this.addTreeAnimator(freezeAnimator);
freezeAnimator.addAnimationListener(this);
}
// return width (number of characters) in widest key in tree
public int maxKeyWidth()
{
if (isTreeEmpty())
return 0;
return ((GrowingTreeNode )getChild()).getMaxKeyWidth();
}
/**
********************************************
* BST_TREE_TYPE Binary Search Tree Methods *
********************************************
*/
/**
* Rotates the node) {
rotateUp(node, 1);
}
/**
* Rotates the node, int levelCount) {
// Check for null nodes (precaution only).
if (node == this)
return;
GrowingTreeNode parentTree = node.getParentTree();
/*if (parentTree == this ) {
return;
}*/
for (int i =0; i < levelCount; i++ ) {
if (isAnimatingBSTTree()) {
rotateUpAnimatingType(node);
}
else {
popTreeProperties();
rotateUpTreeType(node);
}
}
}
/**
* Double Rotatation of the node) {
rotateUpDouble(node, 1);
}
/**
* Doubly Rotates the node, int levelCount) {
// Check for null nodes (precaution only).
if (node == this) {
return;
}
GrowingTreeNode parentTree = (GrowingTreeNode )node.getParentTree();
if (parentTree == this ) {
return;
}
for (int i =0; i < levelCount; i++ ) {
if (isAnimatingBSTTree()) {
rotateUpDoubleAnimatingType(node);
}
else {
rotateUpDoubleTreeType(node);
}
}
}
/**
* Rotates the node) {
if (isAnimatingBSTTree()) {
rotateToTopAnimatingType(node);
}
else {
rotateToTopTreeType(node);
}
}
/**
* Splays the 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 makeNodeTreeType(KeyType keyInsert, Object valueInsert) {
// Get node from node factory.
GrowingTreeNode newTree = new GrowingTreeNode (getTreeType());
newTree.setHead(this);
P np = (P) this.nodePropertiesFactory.makeDefaultProperties();
//P cloned = (P) np.clone();
//newTree.nodePropertiesList.add(cloned);
if (logger == null) {
newTree.shadowNode = new ShadowNode (newTree, np);
}
else {
newTree.shadowNode = new ShadowNode (newTree, np, logger);
}
// Set the null leaves.
newTree.setLeaf();
((GrowingTreeNode )newTree.getRightNodeInternal()).setHead(this);
((GrowingTreeNode )newTree.getLeftNodeInternal()).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(GrowingTreeNode 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.
((GrowingTreeNode )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 node) {
resetTreeLevel();
if (((GrowingTreeNode )node).inTree()) {
((GrowingTreeNode )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 GrowingTreeNode partitionTreeType(GrowingTreeNode 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(GrowingTreeNode node) {
if (node.size() <= 2)
return;
GrowingTreeNode newNode = partitionTreeType(node, node.size()/2);
balanceTreeType(newNode.getLeftNodeInternal());
balanceTreeType(newNode.getRightNodeInternal());
}
/**
* Searches for the searchTreeType(KeyType keySearch) throws ClassCastException {
return ((GrowingTreeNode )getChild()).search(keySearch);
}
/**
* Selects for the selectTreeType(GrowingTreeNode node, int keySelect) throws ClassCastException {
return node.select(keySelect);
}
/**
* Selects for the node, int keySelect) throws ClassCastException {
GrowingTreeNode other = (GrowingTreeNode ) node.select(keySelect);
KeyType tempKey = other.getKey();
Object tempVal = other.getValue();
other.setNode(node.getKey(), node.getValue());
node.setNode(tempKey, tempVal);
return;
}
/**
* Rotates the node) {
// Get the parent for rotation.
GrowingTreeNode nodeParent = (GrowingTreeNode )node.getParentTree();
if (nodeParent == this) {
return;
}
resetTreeLevel();
// Get the ancestor node, whose child links are modified.
GrowingTreeNode nodeAncestor = (GrowingTreeNode )nodeParent.getParentTree();
GrowingTreeNode temp = null;
// Determine if the node is the left or right child and rotate accordingly.
if (node == nodeParent.getLeftNodeInternal() ) {
temp = nodeParent.rotateRightPointers();
}
else if (node == nodeParent.getRightNodeInternal()) {
temp = nodeParent.rotateLeftPointers();
}
// Resets links for Heaed rotate up.
if (nodeAncestor == getHead()) {
setChild(temp);
temp.setParentTree(this);
}
// Resets links for all others
else {
if (nodeAncestor.getLeftNodeInternal() == nodeParent) {
nodeAncestor.setLeftTree(temp);
}
else {
nodeAncestor.setRightTree(temp);
}
temp.setParentTree(nodeAncestor);
}
// Fixes the level.
fixLevel();
}
/**
* Double Rotates the node) {
GrowingTreeNode parentTree = (GrowingTreeNode ) node.getParentTree();
GrowingTreeNode grandParentTree = (GrowingTreeNode )parentTree.getParentTree();
if (grandParentTree == this) {
rotateUpTreeType(node);
return;
}
// Opposite direction, resulting in normal rotations (left-right and right-left)
if (
((grandParentTree.getLeftNodeInternal() == parentTree) && (parentTree.getRightNodeInternal() == node))
||
((grandParentTree.getRightNodeInternal() == parentTree) && (parentTree.getLeftNodeInternal() == 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(GrowingTreeNode 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(GrowingTreeNode node) {
rotateUp(node, node.getLevel());
}
/**
* Traverses the tree in the given traversal type.
*
* @param traverseType int defining the given traversal type.
*
*/
public LinkedList )getChild()).makePreorderTree(traverseList);
return traverseList;
}
/**
* Makes a inorder representation of the tree in an array of )getChild()).makeInorderTree(traverseList);
return traverseList;
}
/**
* Makes a postorder representation of the tree in an array of )getChild()).makePostorderTree(traverseList);
return traverseList;
}
/**
* Makes a levelorder representation of the tree in an array of currentNode = (GrowingTreeNode )getChild();
visitingList.addLast(currentNode);
while(!visitingList.isEmpty()) {
currentNode = (GrowingTreeNode )visitingList.removeFirst();
traverseList.add(currentNode);
if (!currentNode.getLeftNodeInternal().isEmpty()) {
visitingList.addLast(currentNode.getLeftNodeInternal());
}
if (!currentNode.getRightNodeInternal().isEmpty()) {
visitingList.addLast(currentNode.getRightNodeInternal());
}
}
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 )getChild()).setTreeSettings(s,k);
}
}
/**
* Sets the makeNodeDrawingType(KeyType keyInsert, Object valueInsert) {
GrowingTreeNode newNode = makeNodeTreeType(keyInsert, valueInsert);
newNode.setSettings(getDrawingNodeSettings());
if (valueInsert != null)
((DrawableKey)newNode.getValue()).setSettings(getDrawingKeySettings());
return newNode;
}
/**
* Insert the comaparable node to the tree using its natural ordering .
*
* Call to 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 )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 )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 ((GrowingTreeNode )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 ();
}
}
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Accesssor methods *
*********************************************
*/
/**
* Gets whether the AnimatingBSTTreeHead is removing an )getChild()).saveNodeProperties();
}
public void popTreeProperties() {
if (getChild() != null)
((GrowingTreeNode )getChild()).popNodeProperties();
}
/**
* Sets whether the AnimatingBSTTreeHead is removing an Call to 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, new ActionElementType (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 Call to searchAnimatingType(KeyType keySearch) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return searchTreeType(keySearch);
}
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.SEARCH, new ActionElementType (keySearch));
return null;
}
Animation searchAnimator = makeSearchAnimation(keySearch);
// Add tree animator.
this.addTreeAnimator(searchAnimator);
searchAnimator.addAnimationListener(this);
return searchTreeType(keySearch);
}
/**
* Selects for the Call to selectAnimatingType(GrowingTreeNode 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 ActionElementType (new NodeAndKey (node, keySelect)));
return null;
}
Animation selectAnimator = makeSelectionAnimation(node , keySelect);
// Add tree animator.
this.addTreeAnimator(selectAnimator);
selectAnimator.addAnimationListener(this);
return selectTreeType(node, keySelect);
}
/**
* Selects for the Call to swapAnimatingType(GrowingTreeNode 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.SWAP, new ActionElementType (new NodeAndKey (node, keySelect)));
return null;
}
Animation selectAnimator = makeSwapNodesAnimation(node , keySelect);
// Add tree animator.
this.addTreeAnimator(selectAnimator);
selectAnimator.addAnimationListener(this);
return selectTreeType(node, keySelect);
}
private int rank(KeyType key, GrowingTreeNode n) {
if (n.getKey() == null) return 0;
int cmp = key.compareTo(n.getKey());
if (cmp < 0) return rank(key, n.getLeftNodeInternal());
else if (cmp > 0) return 1 + n.getLeftNodeInternal().size()
+ rank(key, n.getRightNodeInternal());
else return n.getLeftNodeInternal().size();
}
protected void swapNodes(GrowingTreeNode n1, GrowingTreeNode n2) {
int rank = rank(n2.getKey(), n1);
this.swapNodes(n1, rank);
}
/**
* Rotates the node up in the BSTTree.
*
* @param node BSTTree node that is rotated up.
*/
protected void rotateUpAnimatingType(GrowingTreeNode node) {
boolean oldDisplayChange = false;
if (!isAnimatingBSTTree()) {
rotateUpTreeType(node);
return;
}
if (getDisplay() != BINARY_DISPLAY) {
changeDisplay();
oldDisplayChange = true;
}
// Get the parent for rotation.
GrowingTreeNode nodeParent = node.getParentTree();
/*if (nodeParent == this) {
return;
}*/
// If Animation is occuring, add ROTATE_UP to the waitingList.
if (isTreeAnimating()) {
waitingList.add(AnimatingTreeHead.ROTATE_UP, new ActionElementType (node));
if (oldDisplayChange) {
oldDisplayChange = false;
changeDisplay();
}
return;
}
Animation rotateUpAnimator = makeRotationAnimation(node);
// Add animation and receive 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(GrowingTreeNode 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, new ActionElementType (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(GrowingTreeNode 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, new ActionElementType (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, new ActionElementType (node));
}
// If the amount of nodes is odd, do a single rotation first
waitingList.addFirst(AnimatingTreeHead.ROTATE_UP, new ActionElementType (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, new ActionElementType (node));
}
}
}
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
}
/**
* Rotates to top the node in the BSTTree.
*
* @param node BSTTree node that is splayed.
*/
protected void rotateToTopAnimatingType(GrowingTreeNode 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, new ActionElementType (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, new ActionElementType (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 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, new ActionElementType (node));
if (oldDisplayChange) {
changeDisplay();
oldDisplayChange = false;
}
return;
}
assert(!node.getLeftNodeInternal().inTree() || !node.getRightNodeInternal().inTree());
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 partitionAnimatingType(GrowingTreeNode 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 ActionElementType (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 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, new ActionElementType (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 (traverseType));
return traverseTreeType(traverseType);
}
LinkedList 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());
insertNode.saveNodeProperties();
// 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.
((GrowingTreeNode )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(KeyType 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.
((GrowingTreeNode )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(GrowingTreeNode 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;
}
public Animation makeSwapNodesAnimation(GrowingTreeNode node, int keySelect) {
if (!isAnimatingBSTTree()) {
return null;
}
//SelectionBSTAnimation newAnimator = new SwapNodesBSTAnimation (keySelect, getSelectNodeLeftSettings(),getSelectNodeRightSettings(),getSelectAnimatorNodeSettings(), getSelectAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
// Recursive call to insert the tree, starting at the head level.
//node.makeSelectionAnimation(keySelect, newAnimator);
SwapBSTAnimation newAnimator = new SwapBSTAnimation (node, (GrowingTreeNode )node.select(keySelect), getTreeAnimationStepSize());
return newAnimator;
}
public Animation makeFreezeAnimation(double lengthMult) {
if (!isAnimatingBSTTree()) {
return null;
}
FreezeAnimation newAnimator = new FreezeAnimation (this, getTreeAnimationStepSize(), lengthMult);
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(GrowingTreeNode node) {
if (!isAnimatingBSTTree()) {
return null;
}
// Get parent.
GrowingTreeNode nodeParent = node.getParentTree();
// Make a new animation.
RotationBSTAnimation newAnimator;
// Check if node is left or right subtree.
if (node == nodeParent.getLeftNodeInternal() ) {
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(GrowingTreeNode 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(GrowingTreeNode 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(GrowingTreeNode 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(GrowingTreeNode 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 newAnimator = new TraverseBSTAnimation (getTraverseAnimatorNodeSettings(),getTraverseAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
int listSize = nodeList.size();
for (int i =0; i (this, newDisplay, getDrawingNodeSettings(), getDrawingKeySettings(), getTreeStatus(), getTreeAnimationStepSize());
return newAnimator;
}
/**
****************************************************
* ANIMATING_BST_TREE_TYPE Implements AnimatingTree *
****************************************************
*/
/**
* Animates the entire BSTTree. The animation is drawn to the Graphics2D passed.
* This method is called repeatedly and for each Animation within the list, the )((BalanceBSTAnimation )e.getSource()).getReplacingNode().getLeftNodeInternal());
balance((GrowingTreeNode )((BalanceBSTAnimation )e.getSource()).getReplacingNode().getRightNodeInternal());
}
else {
// If Animation is occuring, add ROTATE_UP to the waitingList.
waitingList.addFirst(AnimatingTreeHead.BALANCE_NODE, new ActionElementType ((GrowingTreeNode )((BalanceBSTAnimation)e.getSource()).getReplacingNode().getRightNodeInternal()));
waitingList.addFirst(AnimatingTreeHead.BALANCE_NODE, new ActionElementType ((GrowingTreeNode )((BalanceBSTAnimation)e.getSource()).getReplacingNode().getLeftNodeInternal()));
}
}
}
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());
}
}
}
addTreeMessageListener
* is used.
*/
private LinkedListWaitingActionList storing all of the actions waiting to occur.
*/
private WaitingActionList
*
*
*@param treeType type of tree that should be implemented.
*/
public GrowingTreeHead(int treeType) {
super(treeType);
setTreeType(treeType);
listeners = new LinkedListTreeMessageEvent.
*
* @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 :
*
*
*/
public String getTreeStatusMessage() {
String treeStatusMsg = getTreeTypeString()+" Status:\nTree Size = "+size()+
"\nTree Level = "+getTreeLevel();
return treeStatusMsg;
}
/**
******************************************************************************
* BST_TREE_TYPE Methods for determining best/average/worst case times *
******************************************************************************
*/
/**
* Returns the average Search hit time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageSearchHit(int n) {
return (Math.log((double)n) * 1.39);
}
/**
* Returns the average Search miss time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageSearchMiss(int n) {
return (Math.log((double)n) * 1.39);
}
/**
* Returns the worst case Search hit time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseSearchHit(int n) {
return n;
}
/**
* Returns the worst case Search miss time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseSearchMiss(int n) {
return n;
}
/**
* Returns the average Insertion time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the average search hit is needed.
*
* @return double the is the average search hit.
*/
public double averageInsertion(int n) {
return (Math.log((double)n) * 1.39);
}
/**
* Returns the worst case Insertion time, according to n, the amount of elements in the tree.
*
* @param n the size of the tree for which the worst case search hit is needed.
*
* @return double the is the worst case search hit.
*/
public double worstCaseInsertion(int n) {
return n;
}
/**
**********************************
* Waiting Action Method *
**********************************
*/
/**
* Acts according to the String action passed. The method generally accompanies
* a 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, ActionElementTypeWaitingActionList 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 WaitingActionListTreeHead is empty, indicating no Child node, and a level of 0.
*
* @return true if the TreeHead is empty.
*/
public boolean isTreeEmpty() {
return (((GrowingTreeNodeTree, beginning the Tree nodes.
*/
public TreeTree.
*/
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 ((GrowingTreeNodeTree, beginning the Tree nodes.
*/
public void setChild(TreeTree, 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() {
((GrowingTreeNodeTree node to be removed from the tree.
* @param successorSwap true if hibbard successor delete, false if predecessor
*/
public void delete(TreeBSTTree 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(KeyType keyRemove) throws ClassCastException, NullPointerException {
if (keyRemove == null)
throw new NullPointerException();
if (isTreeEmpty())
return false;
GrowingTreeNodeTree 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 TreeTree 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 TreeBSTTree 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(GrowingTreeNodeBSTTree 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(GrowingTreeNodeBSTTTree.
*
* @param node BSTTree that is double rotated (bottom rotation first).
*/
public void rotateUpDouble(GrowingTreeNodeBSTTree 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(GrowingTreeNodeBSTTTree to the top.
*
* @param node BSTTree that is rotated to the top.
*/
public void rotateToTop(GrowingTreeNodeBSTTTree to the top (Double rotates).
*
* @param node BSTTree that is rotated to the top.
*/
public void splay(GrowingTreeNodeTree node to be removed from the tree.
*/
public void removeTreeType(GrowingTreeNodeTree 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 TreeTree 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 TreeTree 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 void swapTreeType(GrowingTreeNodeBSTTree 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(GrowingTreeNodeBSTTree up.
*
* @param node BSTTree that rotated upwards.
*/
public void rotateUpDoubleTreeType(GrowingTreeNodeBSTTree.
*/
public void changeDisplayTreeType() {
int currentDisplay = getDisplay();
if (currentDisplay == GrowingTreeHead.SECTIONAL_DISPLAY) {
setDisplay(GrowingTreeHead.BINARY_DISPLAY);
}
else {
setDisplay(GrowingTreeHead.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 LinkedListBSTTrees.
* 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 LinkedListBSTTrees.
* 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 LinkedListBSTTrees.
* 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 LinkedListNodeSettings 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()) {
((GrowingTreeNodeNodeSettings 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 GrowingTreeNodeinsertTreeType
*
* @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(GrowingTreeNodeMakeTree.
*
* @param g2 Graphics2D which the tree is drawn onto.
*/
public void DrawTree(Graphics2D g2) {
if (!isDrawingBSTTree())
return;
if (isTreeEmpty())
return;
((GrowingTreeNodeAnimatingBSTTree, held in the AnimatingBSTTreeHead.
*/
private LinkedListAnimation 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 LinkedListAnimation.
*
* @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 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 *
*******************************************
*/
public void saveTreeProperties() {
if (getChild() != null)
((GrowingTreeNodeAnimation, 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 all 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;
}
ListIteratorAnimation 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;
ListIteratorinsertDrawingType
*
* @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(GrowingTreeNodeTree in the entire tree.
*
* 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 TreeTree in the entire tree.
*
* selectTreeType
*
* @param keySelect integer key selecting the count item.
* @return Tree the Tree found or null.
*/
protected TreeTree in the entire tree.
*
* selectTreeType
*
* @param keySelect integer key selecting the count item.
* @return Tree the Tree found or null.
*/
protected TreeDeleteBSTAnimation is built, using the node, the super remove method is called.
*
* @param node BSTTree node that is deleted.
*/
protected void removeAnimatingType(GrowingTreeNodeselectTreeType
*
* @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 TreebalanceTREE
* if no waiting action appears.
*
* @param node BSTTree that is balanced from.
*/
public void balanceAnimatingType(GrowingTreeNodeBSTTree.
*/
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(GrowingTreeNodedrawAnimation
* method is called. Within this method, checks for removing a Animation are made, as are checks
* for Waiting Actions.
*
* @param g2 Graphics2D to which the Animations 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 = 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 = 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 = 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((GrowingTreeNode