BSTTree, a node of the Binary Search Tree.
* It uses the elements natural ordering. It uses everything defined within the AbstractTree
* The BSTTree cannot be the head of the tree, it is only the nodes. It defines recursive methods * which aren't defined in the head node and it does not define the methods for the head node. * *
A Binary Search Tree is a binary tree that has a key associated with each * of its internal nodes, with the additional property that the key in any node is larger than * (or eqaul to) that keys in all nodes in that node's left subtree and smaller than (or equal to) * the keys in all nodes in the node's right subtree. (Sedgewick, 502, Algorithms in C) * *
Note that this implementation is not synchronized. If multiple * threads access this tree concurrently, and at least one of the threads modifies * the tree structurally, it must be synchronized externally. * * @author Corey Sanders * @version 3.4 9/15/01 */ public class GrowingTreeNode
implements Tree
, DrawingTree
, AnimationListener, AnimatingTree
{ //IDeletingNode
, //IInsertingNode
{ /*************************************************************************/ /* BSTTree constructor, methods, and variables for all types of BSTTrees */ /*************************************************************************/ /** * Tree type defining only a BSTTree. The Drawing and Animating methods will not be available. */ public final static int BST_TREE_TYPE = 0; /** * Tree type defining a DrawingBSTTree. The Animating methods will not be available. */ public final static int DRAWING_BST_TREE_TYPE = 1; /** * Tree type defining AnimatingBSTTree. All methods will be available and all animations will occur. */ public final static int ANIMATING_BST_TREE_TYPE = 2; /** * Stores the type of tree the BSTTree is. */ private int treeType; /** * Constructs a new, empty BSTTree, sorted according to the keys' natural * order. All keys inserted into the tree must implement the * KeyType interface. Furthermore, all such keys must be * mutually comparable: k1.compareTo(k2) must not throw a * ClassCastException for any elements k1 and k2 in the * tree. If the user attempts to put a key into the tree that violates this * constraint (for example, the user attempts to put a string key into a * map whose keys are integers), the add(KeyType key, Object * value) call will throw a ClassCastException. * *
Default type is BST_TREE_TYPE. */ public GrowingTreeNode() { 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: *
logger) { this(treeType); //nodeProperties = p if (logger == null) shadowNode = new ShadowNode
(this, p); else shadowNode = new ShadowNode
(this, p, logger); nodePropertiesList = new LinkedList
(); nodePropertiesList.add((P) shadowNode.getNodeProperties().clone()); } /** * Checks the tree type and determines the appropriate construction necessary. * Generally called every time the tree type changes. */ private void checkConstructors() { if (getTreeType() >= BST_TREE_TYPE) { constructBSTTree(); } if (getTreeType() >= DRAWING_BST_TREE_TYPE) { constructDrawingBSTTree(); } if (getTreeType() >= ANIMATING_BST_TREE_TYPE) { constructAnimatingBSTTree(); } } /** * Sets the tree type for the BSTTree. * * @param treeType setting for the tree. */ public void setTreeType(int treeType) { this.treeType = treeType; checkConstructors(); } /** * Gets the tree type for the BSTTree. * * @return tree type for the tree. */ public int getTreeType() { return treeType; } /** * Fixes the tree type for the entire BSTTree. * * @param treeType setting for the tree. */ protected void fixTreeType(int treeType) { setTreeType(treeType); if (isEmpty()) return; ((GrowingTreeNode
)getLeftNodeInternal()).fixTreeType(treeType); ((GrowingTreeNode
)getRightNodeInternal()).fixTreeType(treeType);
}
/**
* Gets the tree type String for the BSTTree.
*
* @return tree type String for the tree.
*/
public String getTreeTypeString() {
return "BST Tree";
}
/**
* Returns true if the BSTTree is of type DrawingBSTTree or higher type.
*
* @return true if is is DRAWING_BST_TREE_TYPE.
*/
protected boolean isDrawingBSTTree() {
return (treeType >= DRAWING_BST_TREE_TYPE);
}
/**
* Returns true if the BSTTree is of type AnimatingBSTTree.
*
* @return true if is is DRAWING_BST_TREE_TYPE.
*/
protected boolean isAnimatingBSTTree() {
return (treeType >= ANIMATING_BST_TREE_TYPE);
}
/**
* Copies the fields of this BSTTree into the BSTTree copy.
* It simply copies it field by field, for usage when changes are made to the head node.
* If the tree type is Drawing or Animating, the method copies the fields accordingly.
*
* @param copy the BSTTree that takes the fields of the BSTTree.
*/
protected void copyBSTTree(GrowingTreeNode
copy) { copy.key = key; copy.value = value; copy.left = left; if (left != null) left.parent = copy; copy.right = right; if (right != null) right.parent = copy; copy.parent = parent; copy.level = level; copy.size = size; if (isDrawingBSTTree()) { copy.setSettings((NodeSettings)(this.getSettings().clone())); ((DrawableKey)copy.getValue()).setSettings((KeySettings)((DrawableKey)this.getValue()).getSettings().clone()); } } /*-----------------------------------------------------------------------*/ /*-------------------------------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. */ /*************************************************************************/ //protected P nodeProperties; protected ShadowNode
shadowNode; protected LinkedList
nodePropertiesList = new LinkedList
(); /** * The number of entries in the BSTTree. */ private int size; /** * The amount of levels to the bottom of the tree. */ private int level; /** * The left and right branches of the given tree. */ private GrowingTreeNode
left; private GrowingTreeNode
right; /** * The key object in this current node. */ private KeyType key; /** * The key object in this current node. */ private Object value; /** * The count of the node in the inorder list. */ private int inorder_count; /** * Parent link */ private GrowingTreeNode
parent; /** * Parent link */ private GrowingTreeHead
head; /** * Constructor for the BST_TREE_TYPE. This constructs and sets all values to defaults * for the BST_TREE_TYPE. */ public void constructBSTTree() { if (getHead() == null && getParentTree() == null) { setSize(0); setLevel(0); setLeftTree(null); setRightTree(null); setNode(null, null); setParentTree(null); setHead(null); } } /** ********************************** * BST_TREE_TYPE Accesssor methods* ********************************** */ public ShadowNode
getShadowNode() { return shadowNode; } public P getNodeProperties() { if (nodePropertiesList != null) { if (nodePropertiesList.peek() != null) { return (P) nodePropertiesList.peek(); } else if (getShadowNode() != null){ return getShadowNode().getNodeProperties(); } } /*if (getShadowNode() != null) { return getShadowNode().getNodeProperties(); }*/ return null; } public Color getLeftLinkColor() { if (getNodeProperties() != null) { return getNodeProperties().getLeftLinkColor(); } return Color.black; } public Color getRightLinkColor() { if (getNodeProperties() != null) { return getNodeProperties().getRightLinkColor(); } return Color.black; } /** * Gets the head for the node. The head node is used in numerous operations and is * the reference for the tree. * * @return BSTTreeHead that represents the head for this node, indicating the tree. */ public GrowingTreeHead
getHead() {
return head;
}
/**
* Returns the number of nodes in the current Tree and below.
*
* @return the number of nodes in the current Tree and below.
*/
public int size() {
return size;
}
/**
* Returns true if the current BSTTree is empty.
*
* @return the boolean true if the BSTTree is empty.
*/
public boolean isEmpty() {
return (key == null);
}
/**
* Returns the value of the current BSTTree.
*
* @return the value of the current BSTTree.
*/
public Object getValue() {
return value;
}
public int compareTo(GrowingTreeNode
that) {
return getKey().compareTo(that.getKey());
}
/**
* Returns the key of the current BSTTree.
*
* @return the key of the current BSTTree.
*/
public KeyType getKey() {
return key;
}
/**
* Gets the the level of the current BSTTree.
* The level is the integer count of how far down the tree is to the current node.
*
* @return integer count of the level of the current BSTTree.
*/
public int getLevel() {
return level;
}
/**
* Returns the inorder count of the current node.
*
* @return the inorder count of the node.
*/
public int getInorderCount() {
return inorder_count;
}
/**
* Returns the left BSTTree of the current tree. Used to traverse down
* the binary tree.
*
* @return BSTTree that is the left subtree of the current BSTTree,
* null of no such tree exists.
*/
public GrowingTreeNode
getLeftNodeInternal() {
return left;
}
/**
* Returns the right BSTTree of the current tree. Used to traverse down
* the binary tree.
*
* @return BSTTree that is the right subtree of the current BSTTree,
* null of no such tree exists.
*/
public GrowingTreeNode
getRightNodeInternal() {
return right;
}
/**
* Returns the children of the current Tree.
*
* @return Tree array that is the children and null if the tree is an exterior node.
*/
public Tree[] getChildren() {
GrowingTreeNode
[] treeList = new GrowingTreeNode[2]; treeList[0] = getLeftNodeInternal(); treeList[1] = getRightNodeInternal(); return treeList; } /** * Returns the parent of the current tree. Used to traverse up * the binary tree. * * @return Tree that is the parent of the current tree and null if the tree is the head. */ public GrowingTreeNode
getParentTree() { return parent; } public GrowingTreeNode
getRoot() { return (GrowingTreeNode
) getHead().getChild(); } /** * Determines if the current node is within a BSTTree. It quickly checks if its parent * points to it, and if its two children point up to it. A quick check that does not go through * the entire tree. * * @return true if the node is within a BSTTree. */ public boolean inTree() { if (getLeftNodeInternal() == null || getRightNodeInternal() == null || ((GrowingTreeNode
)getParentTree()) == null) return false; return ( (this.getLeftNodeInternal().getParentTree() == this) && (this.getRightNodeInternal().getParentTree() == this) && (( ((GrowingTreeNode
)this.getParentTree()).getRightNodeInternal() == this) || ( ((GrowingTreeNode
)this.getParentTree()).getLeftNodeInternal() == this))
);
}
/**
* Determines if the current node is a leaf
* @return true if the node is a leaf.
*/
public boolean isLeaf() {
if (getLeftNodeInternal().inTree() ||
getRightNodeInternal().inTree())
return false;
else
return true;
}
/**
**********************************
* BST_TREE_TYPE Mutator methods *
**********************************
*/
/**
* Sets the head for the node. The head node is used in numerous operations and is
* the reference for the tree. It is a protected class for changing the node results in
* changes to all operations (including getLevel).
*
* @param head TreeHead for the current node.
*/
protected void setHead(GrowingTreeHead
head) { this.head = head; } /** * Sets the left tree for the node. The left and right tree are used in many operations. * It is a protected class for changing the left results in * changes to some operations. * * @param left BSTTree that sets the left link for the current node. */ protected void setLeftTree(GrowingTreeNode
left) { this.left = left; } /** * Sets the right tree for the node. The left and right tree are used in many operations. * It is a protected class for changing the right results in * changes to some operations. * * @param right BSTTree that sets the right link for the current node. */ protected void setRightTree(GrowingTreeNode
right) { this.right = right; } /** * Sets the parent tree for the node. The parent tree are used in many operations. * It is a protected class for changing the parent results in * changes to some operations. * * @param parent BSTTree that sets the parent link for the current node. */ protected void setParentTree(GrowingTreeNode
parent) {
this.parent = parent;
}
/**
* Sets the the level of the current BSTTree.
* The level sets the integer count of how far down the tree is.
*
* @param level the level set for the node.
*/
protected void setLevel(int level) {
this.level = level;
}
/**
* Sets the the size of the current BSTTree.
* The size represents the nodes below and including the current node.
*
* @param size integer setting the size of the node, which is the count of the nodes below
* and including the current node.
*/
protected void setSize(int size) {
this.size = size;
}
/**
* Sets the inorder count of the current node.
*
* @param the inorder count for the node.
*/
protected void setInorderCount(int inorder_count) {
this.inorder_count = inorder_count;
}
/**
* Sets the key and value of the BSTTree. This is prtoected for usage by
* extended classes but not for public access.
*
* @param keyInsert comparable object to be inserted as the key of the BSTTree.
*
* @param valueInsert object to be inserted as the value of the BSTTree.
*/
protected void setNode(KeyType keyInsert, Object valueInsert) {
key = keyInsert;
value = valueInsert;
}
/**
* Fixes the level of the node. Given the currentLevel of the BSTtree, the level of each successive BSTtree (both left
* and right) are fixed until the leaf nodes are reached. The method call is recursive.
*
* @param currentLevel currentLevel of the BSTTree
*
*/
protected void fixLevel(int currentLevel) {
if (isEmpty()) {
return;
}
this.level = currentLevel;
left.fixLevel(currentLevel+1);
right.fixLevel(currentLevel+1);
if (currentLevel > getHead().getTreeLevel()) {
getHead().setTreeLevel(currentLevel);
}
return;
}
/**
* Fixes the size of the node. The method call is recursive.
*
*
* @return integer of the size fixed, which is passed up through the BSTTree, recursively.
*/
protected int fixSize() {
if (isEmpty()) {
return 0;
}
setSize(left.fixSize() + right.fixSize() + 1);
return size();
}
/**
* Sets the values of a new Node left and right tress, to refer to null trees. Both the left and right trees are
* instantiated and their values are set to the default null values.
*/
protected void setLeaf() {
setLeftTree(new GrowingTreeNode
(getTreeType()/*, (P) nodeProperties.makeDefaultProperties()*/)); setRightTree(new GrowingTreeNode
(getTreeType()/*, (P) nodeProperties.makeDefaultProperties()*/)); getLeftNodeInternal().setParentTree(this); getRightNodeInternal().setParentTree(this); } /** ********************************** * BST_TREE_TYPE Tree Methods * ********************************** */ /** * Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it * finds a subtree that is null and sets the node. * * @param newTree the tree to be inserted, with key and value already set. * * @param currentLevel keeps track of the recursive call, and sets the new level if it changes. * * @throws ClassCastException key cannot be compared with the keys * currently in the tree. */ protected void insert(GrowingTreeNode
newTree, int currentLevel) throws ClassCastException { currentLevel++; if ((newTree.getKey()).compareTo(getKey()) < 0) { // Go to the left if(getLeftNodeInternal().isEmpty()) { // Leaf of tree setLeftTree(newTree); // Set tree. getLeftNodeInternal().setParentTree(this); // Set parent. getLeftNodeInternal().setLevel(currentLevel+1); // Increase level if (getLeftNodeInternal().getLevel() > getHead().getTreeLevel()) getHead().setTreeLevel(getLeftNodeInternal().getLevel()); getLeftNodeInternal().setSize(1); // Set initial size } else getLeftNodeInternal().insert(newTree, currentLevel); } else // no duplicates allowed, so compare is > 0; go right { if(getRightNodeInternal().isEmpty()) { // Leaf of tree setRightTree(newTree); // Set tree. getRightNodeInternal().setParentTree(this); // Set parent. getRightNodeInternal().setLevel(currentLevel+1); // Increase level if (getRightNodeInternal().getLevel() > getHead().getTreeLevel()) getHead().setTreeLevel(getRightNodeInternal().getLevel()); getRightNodeInternal().setSize(1); // Set initial size } else getRightNodeInternal().insert(newTree, currentLevel); } // Set the size as one plus the left and sizes. setSize(getLeftNodeInternal().size() + getRightNodeInternal().size() + 1); return; } public IAlgorithmNode
insertNode(GrowingTreeNode
node) { if (isAnimatingBSTTree()) { getHead().saveTreeProperties(); getHead().insertAnimatingType((GrowingTreeNode
)node); } else if (isDrawingBSTTree()) { getHead().insertDrawingType((GrowingTreeNode
)node); } else { getHead().insertTreeType((GrowingTreeNode
)node); } //getHead().panel.repaintAttempt(); //getHead().reMakeTree(); //getHead().reDrawTree(); //getHead().reAnimateTree(); //while(getHead().isTreeAnimating()); return node.getShadowNode(); } // TODO: Implement this public GrowingTreeNode
delete() { return null; }
/**
* Removes the BSTTree from the tree. The call bypasses the BSTTree by
* partitioning the right subTree and replacing itself with the smallest of the right tree.
*/
protected void remove() {
GrowingTreeNode
currentParent = (GrowingTreeNode
)getParentTree(); // Gets the smallest of the right tree. GrowingTreeNode
temp = join(getLeftNodeInternal(), getRightNodeInternal()); // Replaces links if (this == currentParent.getLeftNodeInternal()) { currentParent.setLeftTree(temp); } else { currentParent.setRightTree(temp); } temp.setParentTree(currentParent); if (temp.isEmpty()) return; // fixes the size temp.setSize(temp.getLeftNodeInternal().size() + temp.getRightNodeInternal().size() + 1); } /** * Finds a node within a tree using the comparable keyFind. Null is returned if the * key is not within the tree and the node is returned otherwise. The method is a recursive * call. * * @param keyFind the key which the method is attempting to find. * @return Tree which contains the keyFind as a key or the last examined tree if the keyFind is not present * in the entire tree. */ protected Tree
search(KeyType keyFind) throws ClassCastException {
if(isEmpty()) {
return getParentTree();
}
// Go left
if (keyFind.compareTo(getKey()) < 0) {
return getLeftNodeInternal().search(keyFind);
}
// Go right
if (keyFind.compareTo(getKey()) > 0) {
return getRightNodeInternal().search(keyFind);
}
else { // Equal (Match)
return this;
}
}
// a quick search for a key, with no animating
protected boolean contains(KeyType keyFind) throws ClassCastException {
if (isEmpty())
return false;
// Go left
if (keyFind.compareTo(getKey()) < 0) {
return getLeftNodeInternal().contains(keyFind);
}
// Go right
if (keyFind.compareTo(getKey()) > 0) {
return getRightNodeInternal().contains(keyFind);
}
else { // Equal (Match)
return true;
}
}
/**
* Selects for the Tree in the entire tree.
*
* @param keySelect integer key selecting the count item.
* @return Tree the Tree found or null.
*/
protected Tree
select(int keySelect) {
if(isEmpty()) {
return null;
}
if (getLeftNodeInternal().size() > keySelect) {
return getLeftNodeInternal().select(keySelect);
}
else if (getLeftNodeInternal().size() < keySelect) {
return getRightNodeInternal().select(keySelect - getLeftNodeInternal().size() - 1);
}
return this;
}
/**
* Partitions the Tree at the given keySelect and rotates the keySelectth node
* to this node's position. A recursive call generally called from the head
*
* @param keySelect integer key selecting the count item.
* @param levelCount integer counting the levels down the partition is going.
*
* @return BSTTree that is the reference to the newly partitioned tree.
*/
protected GrowingTreeNode
partition(int keySelect, int levelCount) { if (getLeftNodeInternal().size() > keySelect) { // Recursive call return getLeftNodeInternal().partition(keySelect, levelCount + 1); } else if (getLeftNodeInternal().size() < keySelect) { return getRightNodeInternal().partition(keySelect - getLeftNodeInternal().size() - 1, levelCount + 1); } // Rotate Up the amount of levels the partition went down. ((GrowingTreeHead
)getHead()).rotateUp(this, levelCount); return this; } /** * Rotate the tree to the right. It simply changes around references to BSTTrees. * * @return BSTTree that is the reference to the newly rotated tree. */ public GrowingTreeNode
rotateRightPointers() { GrowingTreeNode
temp = (GrowingTreeNode
)getLeftNodeInternal(); setLeftTree((GrowingTreeNode
)temp.getRightNodeInternal()); getLeftNodeInternal().setParentTree(this); temp.setRightTree(this); setParentTree(temp); temp.setParentTree(null); // Fix sizes setSize(getLeftNodeInternal().size() + getRightNodeInternal().size() + 1); temp.setSize(temp.getLeftNodeInternal().size() + temp.getRightNodeInternal().size() + 1); return temp; } /** * Rotate the tree to the left. It simply changes around references to BSTTrees. * * @return BSTTree that is the reference to the newly rotated tree. */ public GrowingTreeNode
rotateLeftPointers() { GrowingTreeNode
temp = (GrowingTreeNode
)getRightNodeInternal(); setRightTree((GrowingTreeNode
)temp.getLeftNodeInternal()); getRightNodeInternal().setParentTree(this); temp.setLeftTree(this); setParentTree(temp); temp.setParentTree(null); // Fix sizes setSize(getLeftNodeInternal().size() + getRightNodeInternal().size() + 1); temp.setSize(temp.getLeftNodeInternal().size() + temp.getRightNodeInternal().size() + 1); return temp; } public void rotateUp() { getHead().saveTreeProperties(); getHead().rotateUp(this); //getHead().rotateUp(this); //getHead().reMakeTree(); //getHead().reDrawTree(); //getHead().reAnimateTree(); //getHead().panel.repaintAttempt(); } /** * Joins two subtrees together as one tree. It takes the greater subtree and * partitions the smallest element to the root. Then it makes that new head * element's left subtree the smaller subtree. * * @param treeJoinOne one subtree to be joined. * @param treeJoinTwo second subtree to be joined. * * @return BSTTree object which is the new reference to the joined tree. */ protected static
GrowingTreeNode
join(GrowingTreeNode
treeJoinOne, GrowingTreeNode
treeJoinTwo) { // Empty trees if (treeJoinTwo.isEmpty()) { return treeJoinOne; } if (treeJoinOne.isEmpty()) { return treeJoinTwo; } // Tree one is less than tree two if (treeJoinOne.getKey().compareTo(treeJoinTwo.getKey()) < 0) { treeJoinOne.setParentTree(treeJoinTwo.partition(0, 0)); ((GrowingTreeNode
)treeJoinOne.getParentTree()).setLeftTree(treeJoinOne); ((GrowingTreeNode
)treeJoinOne.getParentTree()).setSize(((GrowingTreeNode
)treeJoinOne.getParentTree()).getLeftNodeInternal().size() + ((GrowingTreeNode
)treeJoinOne.getParentTree()).getRightNodeInternal().size() + 1); return ((GrowingTreeNode
)treeJoinOne.getParentTree()); } else { treeJoinTwo.setParentTree(treeJoinOne.partition(0, 0)); ((GrowingTreeNode
)treeJoinTwo.getParentTree()).setLeftTree(treeJoinTwo); ((GrowingTreeNode
)treeJoinTwo.getParentTree()).setSize(((GrowingTreeNode
)treeJoinTwo.getParentTree()).getLeftNodeInternal().size() + ((GrowingTreeNode
)treeJoinTwo.getParentTree()).getRightNodeInternal().size() + 1); return (GrowingTreeNode
)treeJoinTwo.getParentTree();
}
}
// return the width (number of characters) of widest key in this
// subtree
public int getMaxKeyWidth()
{
if (isEmpty())
return 0;
int left = getLeftNodeInternal().getMaxKeyWidth();
int right = getRightNodeInternal().getMaxKeyWidth();
int max = Math.max(left, right);
return Math.max(max, getKey().toString().length());
}
/**
**********************************
* Traversal Methods *
**********************************
*/
/**
* Makes an array in preorder using recursive calls and the count. The BSTTree
* is traversed in preorder, adding the BSTTree objects in turn to the array.
*
* @param treeArray the array that has the BSTTree objects.
*/
protected void makePreorderTree(LinkedList )getLeftNodeInternal()).makePreorderTree(treeList);
((GrowingTreeNode )getRightNodeInternal()).makePreorderTree(treeList);
}
/**
* Makes an array in inorder using recursive calls and the count. The BSTTree
* is traversed in inorder, adding the BSTTree objects in turn to the array.
*
* @param treeArray the array that has the BSTTree objects.
*/
protected void makeInorderTree(LinkedList )getLeftNodeInternal()).makeInorderTree(treeList);
// Push onto stack
treeList.add(this);
((GrowingTreeNode )getRightNodeInternal()).makeInorderTree(treeList);
}
/**
* Makes an array in postorder using recursive calls and the count. The BSTTree
* is traversed in postorder, adding the BSTTree objects in turn to the array.
*
* @param treeArray the array that has the BSTTree objects.
*/
protected void makePostorderTree(LinkedList )getLeftNodeInternal()).makePostorderTree(treeList);
((GrowingTreeNode )getRightNodeInternal()).makePostorderTree(treeList);
// Push onto stack
treeList.add(this);
}
/*-----------------------------------------------------------------------*/
/*-------------------------------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. */
/*************************************************************************/
/**
* Bounds defining the screen in which the If the settings are saved, the previous settings are modified to the
* The method calls the method for the left and right children, using properly modified
* )getHead()).getDisplay() == GrowingTreeHead.SECTIONAL_DISPLAY) {
a.translate(((getScreenBounds().getWidth() / getHead().size())*getInorderCount())/getCurrentTransform().getScaleX(), 0);
// Set the current values.
setCurrentTransform(a);
leftTransform.translate(0, ( getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
rightTransform.translate(0, (getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
}
else {
leftTransform.translate(((-getScreenBounds().getWidth()/getCurrentPower2())/getCurrentTransform().getScaleX()), ( getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
rightTransform.translate(((getScreenBounds().getWidth()/getCurrentPower2())/getCurrentTransform().getScaleX()), (getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
}
// Call the left and right tress.
getLeftNodeInternal().makeTree(leftTransform, currentLevel+1);
getRightNodeInternal().makeTree(rightTransform, currentLevel+1);
}
/**
* Draws the tree recursively, on to the Graphics2D. The current transform, drawing level,
* power, and screen bounds must all be set before the recursive method is called.
*
* @param g2 the Graphics2D to which the tree is drawn.
*/
protected void drawTree(Graphics2D g2) {
if (isEmpty())
return;
setCurrentGraphics(g2);
if (!isNodeAnimating()) {
drawNodeAndLink(g2);
}
getLeftNodeInternal().drawTree(g2);
getRightNodeInternal().drawTree(g2);
}
/**
* Draws the node of the tree using the previously defined graphics. The drawing uses
* the previously defined )getHead()).getDisplay() == GrowingTreeHead.BINARY_DISPLAY);
}
else {
bottomLinks = true;
}
// Redraw
drawLeftLink(getCurrentGraphics(), getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);
// Draw the node
drawNode(getCurrentGraphics(), getCurrentTransform());
}
/**
* Draws the node and right link of the tree using the previously defined graphics.
* The drawing uses the previously defined )getHead()).getDisplay() == GrowingTreeHead.BINARY_DISPLAY);
}
else {
bottomLinks = true;
}
// Redraw
drawRightLink(getCurrentGraphics(), getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);
// Draw the node
drawNode(getCurrentGraphics(), getCurrentTransform());
}
/**
* Erases the previous drawing of the nodeAndLinkm, simply drawing.
*/
public void eraseNodeAndLink() {
// Copy the settings
NodeSettings temp = (NodeSettings)getSettings();
// Erase setting
setNodeSettings(NodeSettings.getScheme(NodeSettings.ERASE, getHead().getBackgroundColor()));
drawNodeAndLink(getCurrentGraphics());
// Reset settings
setNodeSettings(temp);
}
/**
* Erases the previous drawing of the nodeAndLinkm, simply drawing.
*/
public void eraseNodeAndLink(Graphics2D g2) {
// Copy the settings
NodeSettings temp = (NodeSettings)getSettings();
// Erase setting
setNodeSettings(NodeSettings.getScheme(NodeSettings.ERASE, getHead().getBackgroundColor()));
drawNodeAndLink(g2);
// Reset settings
setNodeSettings(temp);
}
/**
* Draws the node and link of the tree using the previously defined graphics..
* The drawing uses the previously defined )getHead()).getDisplay() == GrowingTreeHead.BINARY_DISPLAY);
}
else {
bottomLinks = true;
}
drawNodeAndLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(),bottomLinks);
}
/**
* Draws the node and link of the tree to the given Graphics2D.
* The drawing generally uses the previously defined )getHead()).getDisplay() == GrowingTreeHead.BINARY_DISPLAY);
}
else {
bottomLinks = true;
}
drawNodeAndLink(g2, a, bottomLinks);
}
/**
* Draws the node and link of the tree to the given Graphics2D. Using the Transform, the node
* is affect, while the links use the previously defined transform to draw. Consequently, the
* node made shift and enlarge while keeping the links constant.
*
* @param g2 graphics to which the node and links are drawn.
* @param a transfrom to draw the node and links.
* @param bottomLinks the boolean to declare whether the bottom links should be drawn.
*/
public void drawNodeAndLink(Graphics2D g2, AffineTransform a, boolean bottomLinks) {
drawRightLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);
drawLeftLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);
// Draw the node
drawNode(g2, a);
}
/**
* Draws the node and link of the tree to the given Graphics2D.
* The drawing generally uses the )getHead()).getDisplay() == GrowingTreeHead.BINARY_DISPLAY);
}
else {
bottomLinks = true;
}
drawNodeAndLink(g2, sectionHeight, a, drawingLevel, powerLevel,bottomLinks);
}
/**
* Draws the node and link of the tree to the given Graphics2D.
* The drawing generally uses the rightTree = getRightNodeInternal();
Line2D.Double right;
if (getSettings().getSettingName().equals(NodeSettings.ERASE)) {
// don't do anything
}
else if (getRightNodeInternal() != null &&
getRightNodeInternal().getNodeProperties() != null &&
getRightNodeInternal().getNodeProperties().colorParentLink()) {// getNodeProperties().colorParentLink() && rightTree != null && rightTree.inTree()) {
getSettings().setRightLinkPaint(getRightNodeInternal().getNodeProperties().getNodeColor());
}
/*else if (getNodeProperties().colorParentLink() &&
getRightNodeInternal() == null &&
this instanceof MovingBSTTree) {
//do nothing
}*/
else {
getSettings().setRightLinkPaint(getNodeProperties().getRightLinkColor());
}
if (rightTree != null && !(rightTree instanceof MovingBSTTree)) {
if (!(rightTree.isEmpty())) {
double horizontal = rightTree.getCurrentTransform().getTranslateX() + rightTree.getCurrentTransform().getScaleX()/2.0;
double vertical = rightTree.getCurrentTransform().getTranslateY();
// Right line
right = new Line2D.Double((a.getTranslateX() + (3*a.getScaleX())/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , horizontal , vertical);
g2.setComposite(getSettings().getRightLinkComposite());
g2.setStroke(getSettings().getRightLinkStroke());
g2.setPaint(getSettings().getRightLinkPaint());
g2.draw(right);
return;
}
}
if (bottomLinks) {
// Right line
right = new Line2D.Double( (a.getTranslateX() + (3*a.getScaleX())/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , (a.getTranslateX() + a.getScaleX()/2.0 + bounds.getWidth()/powerLevel) , (sectionHeight * drawingLevel));
g2.setComposite(getSettings().getRightLinkComposite());
g2.setStroke(getSettings().getRightLinkStroke());
g2.setPaint(getSettings().getRightLinkPaint());
g2.draw(right);
}
}
/**
* Draws just the left link according to the NodeSettings currently set.
*
* @param g2 graphics to which the node and links are drawn.
* @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
* @param a transfrom to draw the node and links.
* @param drawingLevel the level in the tree to which the node is currently being drawn.
* @param powerLevel the power to which the links extend, depending on how many links are present.
* @param bottomLinks the boolean to declare whether the bottom links should be drawn.
*/
protected void drawLeftLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {
Rectangle2D bounds = g2.getClipBounds();
GrowingTreeNode leftTree = getLeftNodeInternal();
// Draw the left and right links
Line2D.Double left;
if (getSettings().getSettingName().equals(NodeSettings.ERASE)) {
// don't do anything
}
else if (getLeftNodeInternal() != null &&
getLeftNodeInternal().getNodeProperties() != null &&
getNodeProperties().colorParentLink()) {
getSettings().setLeftLinkPaint(getLeftNodeInternal().getNodeProperties().getNodeColor());
}
/*else if (getNodeProperties().colorParentLink() &&
getLeftNodeInternal() == null &&
this instanceof MovingBSTTree) {
// do nothing
}*/
else {
getSettings().setLeftLinkPaint(getNodeProperties().getLeftLinkColor());
}
if (leftTree != null && leftTree.getCurrentTransform() != null) {
if (!(leftTree.isEmpty())) {
double horizontal = leftTree.getCurrentTransform().getTranslateX() + leftTree.getCurrentTransform().getScaleX()/2.0;
double vertical = leftTree.getCurrentTransform().getTranslateY();
// Right line
left = new Line2D.Double( (a.getTranslateX() + a.getScaleX()/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , horizontal, vertical);
// Set graphics information
g2.setComposite(getSettings().getLeftLinkComposite());
g2.setStroke(getSettings().getLeftLinkStroke());
g2.setPaint(getSettings().getLeftLinkPaint());
g2.draw(left);
return;
}
}
if (bottomLinks) {
// left line
left = new Line2D.Double( (a.getTranslateX() + a.getScaleX()/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , (a.getTranslateX() + a.getScaleX()/2.0 - bounds.getWidth()/powerLevel) , (sectionHeight * drawingLevel));
// Set graphics information
g2.setComposite(getSettings().getLeftLinkComposite());
g2.setStroke(getSettings().getLeftLinkStroke());
g2.setPaint(getSettings().getLeftLinkPaint());
g2.draw(left);
}
}
/**
* 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.
*/
protected DrawingTree findNode(double x, double y) {
if (isEmpty())
return null;
if (isNodeAnimating())
return null;
if (getCurrentTransform() == null || getHead() == null )
return null;
// If y < (1.6)(section height) of this current node, than the node is returned.
if( y <= (getCurrentTransform().getTranslateY() + getHead().getSectionHeight() / 1.6) ){
return this;
}
else {
// If x is less than half this width, the method is called for the left.
if (x >= getCurrentTransform().getTranslateX() + getCurrentTransform().getScaleX()/2.0)
return getRightNodeInternal().findNode(x, y);
else
// Otherwise the method is called for the right.
return getLeftNodeInternal().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 list of animators of the current node.
*/
private LinkedList insertNode, InsertBSTAnimation newAnimator) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return;
}
if (isEmpty()) {
return;
}
// Add the animator to the Insertion animation.
newAnimator.add(this);
if ((insertNode.getKey()).compareTo(key) < 0) { // Go to the left
getLeftNodeInternal().makeInsertAnimation(insertNode, newAnimator);
}
else { // Go to the right
getRightNodeInternal().makeInsertAnimation(insertNode, newAnimator);
}
}
/**
* Constructs the newAnimator) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return;
}
if (isEmpty()) {
return;
}
// Add the animator to the Insertion animation.
newAnimator.add(this);
if (keySearch.compareTo(getKey()) < 0) { // Go to the left
getLeftNodeInternal().makeSearchAnimation(keySearch, newAnimator);
}
else if (keySearch.compareTo(getKey()) > 0) { // Go to the right
getRightNodeInternal().makeSearchAnimation(keySearch, newAnimator);
}
// If equal, stop. (SEARCH HIT)
}
/**
* Constructs the newAnimator) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return;
}
if (isEmpty()) {
return;
}
// Add the animator to the Insertion animation.
newAnimator.add(this);
if (getLeftNodeInternal().size() > elementCount) {
getLeftNodeInternal().makeSelectionAnimation(elementCount, newAnimator);
}
if (getLeftNodeInternal().size() < elementCount) {
getRightNodeInternal().makeSelectionAnimation(elementCount - getLeftNodeInternal().size() - 1, newAnimator);
}
}
/**
********************************************************
* ANIMATING_BST_TREE_TYPE Implements Animation Listener*
********************************************************
*/
/**
* Implements DrawingTree exists.
*/
private Rectangle2D screenBounds;
/**
* Origin shape, defining the shape of the node at the origin and size 1.
*/
private Shape nodeOriginShape;
/**
* Origin shape, defining the shape of the bounding box of the key contained within the nodeOriginShape.
*/
private Shape keyOriginRectangle;
/**
* The current Shape of the DrawingTree, last drawn as this specific shape.
*/
private Shape currentShape;
/**
* The current AffineTransform of the DrawingTree, representing the
* most current Transformation to draw the nodeOriginShape and keyOriginRectangle.
*/
private AffineTransform currentTransform;
/**
* The previous AffineTransform of the DrawingTree.
*/
private AffineTransform previousTransform;
/**
* The double drawing level for the current DrawingTree.
*/
private double drawingLevel;
/**
* The current power of 2 representing, 2^drawinLevel.
*/
private double currentPower2;
/**
* The current drawing settings of the node.
*/
private NodeSettings currentSettings = null;
/**
* The previous drawing settings of the node.
*/
private NodeSettings previousSettings = null;
/**
* The count for how many total saves the current Node has been called (to save the NodeSettings).
*/
private int countSaves = 0;
/**
* The count for how many left saves the current Node has been called (saveLeftSettings).
*/
private int countLeftSaves = 0;
/**
* The count for how many right saves the current Node has been called (saveRightSettings).
*/
private int countRightSaves = 0;
/**
* Graphics2D for drawing the node on the previous graphics defined.
*/
private Graphics2D graphics;
/**
* Constructor for the DRAWING_BST_TREE_TYPE. This constructs and sets all values to defaults
* for the DRAWING_BST_TREE_TYPE.
*/
public void constructDrawingBSTTree() {
if (currentSettings == null) {
currentSettings = new NodeSettings();
previousSettings = null;
countSaves = 0;
countLeftSaves = 0;
countRightSaves = 0;
currentTransform = null;
previousTransform = null;
newNodeShape();
}
}
/**
*******************************************
* DRAWING_BST_TREE_TYPE Accesssor methods *
*******************************************
*/
/**
* Gets the drawing level for the current DrawingTree. This is a necessary method for allowing
* intermidiary drawing between two levels, because the param is a double, not an integer.
*
* @return the double level for the drawing node.
*/
public double getDrawingLevel() {
return drawingLevel;
}
/**
* Gets the height of the section for the DrawingTree. The section height is generally
* used to determine link length and node height when drawing the tree.
*
* @return double height of the drawing section for the node.
*/
public double getSectionHeight() {
return getHead().getTreeSectionHeight();
}
/**
* 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;
}
/**
* Gets the current power of 2 to which the tree was last drawn. The power is
* stored in this way to allow quick access and avoiding power methods.
*
* @return double power of 2 last used in drawing the tree (2^drawingLevel).
*/
public double getCurrentPower2() {
return currentPower2;
}
/**
* Gets the NodeSettings of the tree.
* These settings are used for drawing the node and the links of the given tree.
*
* @return NodeSettings for use in drawing the tree.
*/
public NodeSettings getSettings() {
return currentSettings;
}
/**
* Returns true if the settings are currently saved for the DrawingTree.
*
* @return true if the NodeSettings are saved.
*/
public boolean isSettingsSaved() {
// Saved if previousSettings is not null.
return (previousSettings != null);
}
/**
* Gets the shape of the node at the origin and size 1, for usage in
* transforming and drawing.
*
* @return Shape of the node at the origin and size 1.
*/
protected Shape getNodeOriginShape() {
return nodeOriginShape;
}
/**
* Gets the shape of the key within the node shape at the origin and size 1,
* for usage in transforming and drawing.
*
* @return Shape of the key.
*/
protected Shape getKeyOriginRectangle() {
return keyOriginRectangle;
}
/**
* Gets the shape of the node previously drawn or transformed.
*
* @return Shape of the node previously drawn.
*/
protected Shape getCurrentShape() {
return currentShape;
}
/**
* Gets the AffineTransform defined within the tree. The current transform
* is used when calling draw without the AffineTransform value.
*
* @return transform set for the current drawing of the tree.
*/
public AffineTransform getCurrentTransform() {
return currentTransform;
}
/**
* Gets the AffineTransform previously defined within the tree. The previous transform
* is used when calling restoreTransform and is automatically
* updates with each call of setCurrentTransform.
*
* @return transform previously set for the drawing of the tree.
*/
protected AffineTransform getPreviousTransform() {
return previousTransform;
}
/**
* Gets the graphics previously defined within the tree. The graphics are defined in
* makeTree or by the client using setCurrentGraphics.
*
* @return Graphics2D which was the previously defined graphics.
*/
public Graphics2D getCurrentGraphics() {
return graphics;
}
/**
*******************************************
* DRAWING_BST_TREE_TYPE Mutator methods *
*******************************************
*/
/**
* Sets the drawing level for the current DrawingTree. This is a necessary method for allowing
* intermidiary drawing between two levels, because the param is a double, not an integer.
*
* @param level the double level for the drawing node.
*/
protected void setDrawingLevel(double level) {
if (!isDrawingBSTTree())
return;
drawingLevel = level;
}
/**
* 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 bounds) {
if (!isDrawingBSTTree())
return;
screenBounds = bounds;
}
/**
* Sets the graphics defined within the tree.
*
* @param g2 Graphics2D which are the defined graphics for the tree.
*/
public void setCurrentGraphics(Graphics2D g2) {
graphics = g2;
}
/**
* Sets the current power of 2. The power is
* stored in this way to allow quick access and avoiding power methods.
*
* @return p2 power of 2 for drawing the tree (generally 2^drawingLevel).
*/
protected void setCurrentPower2(double p2) {
if (!isDrawingBSTTree())
return;
currentPower2 = p2;
}
/**
* Sets the settings of the entire tree. This represents a recursive call through the tree,
* setting the tree's NodeSettings and then calling both children.
*
* @param s NodeSettings being set for the entire tree.
*/
protected void setTreeSettings(NodeSettings s, KeySettings k) {
if (!isDrawingBSTTree())
return;
if(isEmpty())
return;
setSettings(s);
((DrawableKey)getValue()).setSettings(k);
getLeftNodeInternal().setTreeSettings(s, k);
getRightNodeInternal().setTreeSettings(s, k);
}
/**
* Sets the settings of the node for the BSTTree. No settings are saved
* and the previous settings are not modified.
*
* @param s NodeSettings set for the entire tree.
*/
public void setNodeSettings(NodeSettings s) {
currentSettings = (NodeSettings)s.clone();
}
/**
* Sets the NodeSettings of the DrawingTree.
* These settings are used for drawing the node and the links of the given tree.
* NodeSettings,
* leaving the current settings unmodified. To modify the current settings, use setNodeSettings.
*
* If the settings are not saved, the previous settings are made null and the currentSettings are set.
*
* @param s NodeSettings for use in drawing the tree.
*/
public void setSettings(NodeSettings s) {
NodeSettings newSettings = (NodeSettings)s.clone();
if (!isDrawingBSTTree())
return;
// No previous saved settings
if (!isSettingsSaved()) {
// null previous settings
previousSettings = null;
currentSettings = newSettings;
// Reset saves
countSaves = 0;
countLeftSaves = 0;
countRightSaves = 0;
}
else {
// Set previous settings as s, because currently the settings are saved.
previousSettings = newSettings;
}
}
/**
* Sets the AffineTransform defined within the tree. The set transform
* is used when calling draw without the AffineTransform value.
*
* @param a transform set for the current drawing of the tree.
*/
protected void setCurrentTransform(AffineTransform a) {
if (!isDrawingBSTTree())
return;
previousTransform = currentTransform;
currentTransform = a;
}
/**
* Restores the AffineTransform defined previously within the tree.
* The previous transform is always the last transform defined and is automatically
* updated each time setCurrentTransform is called.
*/
public void restoreTransform() {
if (!isDrawingBSTTree())
return;
currentTransform = previousTransform;
}
/**
*****************************************************
* DRAWING_BST_TREE_TYPE NodeSettings Saving methods *
*****************************************************
*/
protected void saveNodeProperties() {
nodePropertiesList.addLast((P) getShadowNode().getNodeProperties().clone());
if (getLeftNodeInternal().inTree()) {
getLeftNodeInternal().saveNodeProperties();
}
if (getRightNodeInternal().inTree()) {
getRightNodeInternal().saveNodeProperties();
}
}
protected void popNodeProperties() {
if (nodePropertiesList.size() > 0)
nodePropertiesList.pop();
if (getLeftNodeInternal().inTree()) {
getLeftNodeInternal().popNodeProperties();
}
if (getRightNodeInternal().inTree()) {
getRightNodeInternal().popNodeProperties();
}
//System.out.println(getKey().intValue() + ": " + nodePropertiesList.size());
}
/**
* Saves the settings for the tree, incrementing the count of saves by one and setting the
* previous settings accordingly.
*/
public void saveSettings() {
if (!isDrawingBSTTree())
return;
countSaves++;
if (previousSettings == null) {
previousSettings = (NodeSettings)currentSettings.clone();
}
}
/**
* Saves the settings for the tree, incrementing the count of left Saves and total saves by one and setting the
* previous settings accordingly.
*/
public void saveLeftSettings() {
if (!isDrawingBSTTree())
return;
countLeftSaves++;
saveSettings();
}
/**
* Saves the settings for the tree, incrementing the count of right Saves and total saves by one and setting the
* previous settings accordingly.
*/
public void saveRightSettings() {
if (!isDrawingBSTTree())
return;
countRightSaves++;
saveSettings();
}
/**
* Restores the settings for the tree, decrementing the count of left Saves and total saves by one.
* If the left settings have been restored completely, than the NodeSettings for the tree are set accordingly.
*/
public void restoreLeftSettings() {
if (!isDrawingBSTTree())
return;
countLeftSaves--;
if (countLeftSaves <= 0) { // Completely Restored
currentSettings.setLeftSettings(previousSettings);
countLeftSaves = 0;
}
restoreSettings();
}
/**
* Restores the settings for the tree, decrementing the count of right Saves and total saves by one.
* If the right settings have been restored completely, than the NodeSettings for the tree are set accordingly.
*/
public void restoreRightSettings() {
if (!isDrawingBSTTree())
return;
countRightSaves--;
if (countRightSaves <= 0) { // Completely Restored
currentSettings.setRightSettings(previousSettings);
countRightSaves = 0;
}
restoreSettings();
}
/**
* Restores the settings for the tree, decrementing the count of saves by one.
* If the settings have been restored completely, than the NodeSettings for the tree
* are set accordingly.
*/
public void restoreSettings() {
if (!isDrawingBSTTree())
return;
countSaves--;
if (countSaves <= 0) { // Completely Restored
currentSettings = previousSettings;
previousSettings = null;
countSaves = 0;
countRightSaves = 0;
countLeftSaves = 0;
}
}
/**
*****************************************************************
* DRAWING_BST_TREE_TYPE Drawing methods (DrawingTree Interface) *
*****************************************************************
*/
/**
* Makes a new shape for the node and key. This method must be called to develop the nodeOriginShape and keyOriginRectangle, which
* is not modified or changed after the initial call. Basically, this instantiates the important
* data for the tree.
*/
private void newNodeShape() {
// Bounds of the nodeShape.
Rectangle2D nodeShapeBounds = getSettings().getNodeShape().getBounds2D();
// Make the scale and translate transforms.
AffineTransform scaleTransform = AffineTransform.getScaleInstance(1/nodeShapeBounds.getWidth() , 1/nodeShapeBounds.getHeight());
AffineTransform translateTransform = AffineTransform.getTranslateInstance(-nodeShapeBounds.getX(), -nodeShapeBounds.getY());
scaleTransform.concatenate(translateTransform);
// Make the nodeOriginShape
nodeOriginShape = scaleTransform.createTransformedShape(getSettings().getNodeShape());
// Create Shape for key inside node.
keyOriginRectangle = getSettings().getNodeShape().getInscribedRectangle();
keyOriginRectangle = (scaleTransform.createTransformedShape(keyOriginRectangle)).getBounds2D();
}
/**
* Makes the tree recursively using the two parameters. The tree is made by setting the values using the
* following methods:
*
*
setCurrentTransformsetLevelsetDrawingLevelsetCurrentPower2setScreenBounds(using head bounds)AffineTransform and level.
*
* @param a AffineTransform for the current tree.
* @param currentLevel the current level for the tree.
*/
protected void makeTree(AffineTransform a, int currentLevel) {
if (isEmpty())
return;
// Set the current values.
setCurrentTransform(a);
setLevel(currentLevel);
setDrawingLevel((double)currentLevel);
setCurrentPower2(Math.pow(2.0, currentLevel+1));
// Bounds of the graphics
setScreenBounds(getHead().getScreenBounds());
// Make the left and right transforms.
AffineTransform leftTransform = (AffineTransform)getCurrentTransform().clone();
AffineTransform rightTransform = (AffineTransform)getCurrentTransform().clone();
if ( ((GrowingTreeHeadAffineTransform.
*
*/
public void drawNode() {
NodeSettings temp = (NodeSettings)getSettings().clone();
getSettings().setScheme(NodeSettings.ERASE, Color.white);
drawNode(getCurrentGraphics());
setNodeSettings(temp);
drawNode(getCurrentGraphics());
}
/**
* Draws the node of the tree to the given Graphics2D. The drawing uses
* the previously defined AffineTransform.
*
* @param g2 graphics to which the node is drawn.
*/
public void drawNode(Graphics2D g2) {
drawNode(g2, getCurrentTransform());
}
/**
* Draws the node of the tree to the given Graphics2D, using the AffineTransform.
* The drawing uses the AffineTransform to determine the exact way to draw the
* node.
*
* @param g2 graphics to which the node is drawn.
* @param a transform to draw the node.
*/
public void drawNode(Graphics2D g2, AffineTransform a) {
currentShape = a.createTransformedShape(getNodeOriginShape());
NodeProperties currProps = getNodeProperties();
// Update settings based on the NodeProperties
if (currProps != null) {
// Search trees animations create nodes that don't get node properties,
// since they're not in the tree
if (getSettings().getSettingName().equals(NodeSettings.ERASE)) {
// don't do anything
}
else if (currProps.colorParentLink()) {
getSettings().setNodeFillPaint(Color.black);
getSettings().setNodeOutlinePaint(Color.black);
if (getLeftNodeInternal() != null && getLeftNodeInternal().getNodeProperties() != null) {
getSettings().setLeftLinkPaint(getLeftNodeInternal().getNodeProperties().getNodeColor());
}
if (getRightNodeInternal() != null && getRightNodeInternal().getNodeProperties() != null) {
getSettings().setRightLinkPaint(getRightNodeInternal().getNodeProperties().getNodeColor());
}
}
else {
getSettings().setNodeFillPaint(getNodeProperties().getNodeColor());
getSettings().setNodeOutlinePaint(getNodeProperties().getNodeColor());
}
}
else {
getSettings().setNodeFillPaint(Color.black);
getSettings().setNodeOutlinePaint(Color.black);
}
// Set graphics information
g2.setComposite(getSettings().getNodeComposite());
g2.setPaint(getSettings().getNodeFillPaint());
g2.fill(currentShape);
g2.setStroke(getSettings().getNodeOutlineStroke());
g2.setPaint(getSettings().getNodeOutlinePaint());
g2.draw(currentShape);
// Get keyShape
Shape keyShape = a.createTransformedShape(getKeyOriginRectangle());
// Bounding Box
Rectangle2D keyBoundingBox = keyShape.getBounds2D();
AffineTransform scaleTransform = AffineTransform.getScaleInstance(keyBoundingBox.getWidth() , keyBoundingBox.getHeight());
AffineTransform translateTransform = AffineTransform.getTranslateInstance(keyBoundingBox.getX(), keyBoundingBox.getY());
translateTransform.concatenate(scaleTransform);
//DrawingKey intFields = new DrawingKey(null);
KeySettings countSettings
= new KeySettings(KeySettings.SUBTREE_COUNT_SCHEME);
//intFields.setSettings(countSettings);
countSettings.setKeyFillPaint(currProps.getIntegerFieldColor());
int width = getHead().maxKeyWidth();
int countWidth = (new Integer(getHead().size())).toString().length();
// Draws the key and integer fields, if the option is set.
/* an odd graphical glitch occurs when very small keys are scaled,
so if the tree is tall enough, don't scale the keys or draw
integer fields
*/
if (getHead().getTreeLevel() > 20)
{
((DrawingKey)getValue()).drawKey(g2, translateTransform);
}
else
{
if (getHead().getSubtreeCountsVisible()) {
if (currProps.getULIntegerFieldValue() != null) {
DrawingKey intFields = new DrawingKey(new KeyType(currProps.getULIntegerFieldValue()));
intFields.setSettings(countSettings);
intFields.drawKeyUpperLeft(g2, translateTransform, countWidth);
}
if (currProps.getURIntegerFieldValue() != null) {
DrawingKey intFields = new DrawingKey(new KeyType(currProps.getURIntegerFieldValue()));
intFields.setSettings(countSettings);
intFields.drawKeyUpperRight(g2, translateTransform, countWidth);
}
if (currProps.getLLIntegerFieldValue() != null) {
DrawingKey intFields = new DrawingKey(new KeyType(currProps.getLLIntegerFieldValue()));
intFields.setSettings(countSettings);
intFields.drawKeyLowerLeft(g2, translateTransform, countWidth);
}
if (currProps.getLRIntegerFieldValue() != null) {
DrawingKey intFields = new DrawingKey(new KeyType(currProps.getLRIntegerFieldValue()));
intFields.setSettings(countSettings);
intFields.drawKeyLowerRight(g2, translateTransform, countWidth);
}
}
((DrawingKey)getValue()).drawKeyScaled(g2, translateTransform, width);
}
}
/**
* Draws the node and left link of the tree using the previously defined graphics.
* The drawing uses the previously defined AffineTransform,
* section height, drawing level, and power level.
*/
public void drawNodeAndLeftLink() {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((GrowingTreeHeadAffineTransform,
* section height, drawing level, and power level.
*/
public void drawNodeAndRightLink() {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((GrowingTreeHeadAffineTransform,
* section height, drawing level, and power level.
*/
public void drawNodeAndLink() {
// Redraw
drawNodeAndLink(getCurrentGraphics());
}
/**
* Draws the node and link of the tree to the given Graphics2D.
* The drawing generally uses the previously defined AffineTransform,
* section height, drawing level, and power level.
*
* @param g2 graphics to which the node is drawn.
*/
public void drawNodeAndLink(Graphics2D g2) {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((GrowingTreeHeadAffineTransform,
* section height, drawing level, and power level.
*
* @param g2 graphics to which the node is drawn.
* @param bottomLinks the boolean to declare whether the bottom links should be drawn.
*/
public void drawNodeAndLink(Graphics2D g2, boolean bottomLinks) {
drawNodeAndLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(),bottomLinks);
}
/**
* Draws the node and link of the tree to the given Graphics2D. Using the Transform, the node
* is affect, while the links use the previously defined transform to draw. Consequently, the
* node made shift and enlarge while keeping the links constant.
*
* @param g2 graphics to which the node and links are drawn.
* @param a transfrom to draw the node and links.
*/
public void drawNodeAndLink(Graphics2D g2, AffineTransform a) {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((GrowingTreeHeadAffineTransform, section height,
* drawing level, and power level to render the node and its links.
*
* @param g2 graphics to which the node and links are drawn.
* @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
* @param a transfrom to draw the node and links.
* @param drawingLevel the level in the tree to which the node is currently being drawn.
* @param powerLevel the power to which the links extend, depending on how many links are present.
*/
public void drawNodeAndLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel) {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((GrowingTreeHeadAffineTransform, section height,
* drawing level, and power level to render the node and its links.
*
* @param g2 graphics to which the node and links are drawn.
* @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
* @param a transfrom to draw the node and links.
* @param drawingLevel the level in the tree to which the node is currently being drawn.
* @param powerLevel the power to which the links extend, depending on how many links are present.
* @param bottomLinks the boolean to declare whether the bottom links should be drawn.
*/
public void drawNodeAndLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {
//Rectangle2D bounds = g2.getClipBounds();
drawRightLink(g2, sectionHeight, a, drawingLevel, powerLevel, bottomLinks);
drawLeftLink(g2, sectionHeight, a, drawingLevel, powerLevel, bottomLinks);
// Draw the node
drawNode(g2, a);
}
/**
* Draws just the right link according to the NodeSettings currently set.
*
* @param g2 graphics to which the node and links are drawn.
* @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
* @param a transfrom to draw the node and links.
* @param drawingLevel the level in the tree to which the node is currently being drawn.
* @param powerLevel the power to which the links extend, depending on how many links are present.
* @param bottomLinks the boolean to declare whether the bottom links should be drawn.
*/
protected void drawRightLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {
Rectangle2D bounds = g2.getClipBounds();
GrowingTreeNodeAnimation of the node.
*
* @return Animation which is the first Animation of the node.
*/
public Animation getAnimator() {
if (!isAnimatingBSTTree())
return null;
if (animators.isEmpty()) {
return null;
}
return animators.getFirst();
}
/**
* Sets the boolean flag whether the node should draw if called from an animation.
* Only special cases is the flag set to false (Deletion Animations).
*
* @param animateDrawing boolean flag to draw if animating.
*/
public void setAnimateDrawing(boolean animateDrawing) {
this.animateDrawing = animateDrawing;
}
/**
*******************************************
* ANIMATING_BST_TREE_TYPE Mutator methods *
*******************************************
*/
/**
* Adds an animation to the current node. This method does not add the node to listen for
* AnimationEvents. That must be performed by the user.
*
* @param a the Animation being added to the node.
*/
public void addAnimator(Animation a) {
if (!isAnimatingBSTTree()) {
return;
}
animators.add(a);
}
/**
* Gets the boolean flag whether the node should draw if called from an animation.
* Only special cases is the flag set to false (Deletion Animations).
*
* @return boolean flag to draw if animating.
*/
public boolean isAnimateDrawing() {
return animateDrawing;
}
/**********************************/
/* Recursive Constructing methods */
/**********************************/
/**
* Insert the BSTTree down from the current node. This is a recursive call,
* defined in BSTTree. It is overiden in this class to build the animation
* of the insertion. The reason this animation is overiden and not simply added in the AnimatingBSTTreeHead,
* is to allow multiple insertions to occur at once. Therefore, insertion never goes through
* WaitingActionList.
*
* @param node the node being inserted into the tree.
* @param newAnimator the InsertBSTAnimation to which the nodes are being added.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the tree.
*/
protected void makeInsertAnimation(GrowingTreeNodesearchBSTAnimation down from the current node.
* This is a recursive call through the tree. No Listeners are affected by this call.
*
* @param keySearch the key being searched for.
*
* @param newAnimator the SerachBSTAnimation to which the nodes are being added.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the tree.
*/
protected void makeSearchAnimation(KeyType keySearch, SearchBSTAnimationpartitionBSTAnimation down from the current node.
* This is a recursive call through the tree. No Listeners are affected by this call.
*
* @param elementCount the integer (kth small element) searching for that partition
*
* @param newAnimator the PartitionBSTAnimation to which the nodes are being added.
*
* @throws ClassCastException key cannot be compared with the keys
* currently in the tree.
*/
protected void makeSelectionAnimation(int elementCount, SelectionBSTAnimationAnimationListener which requires the following method.
* The only status of animation it listens for is Animation.FINISH, to remove
* the animation from the animators list.
*
* @param e AnimationEvent that represents the information of the Animation.
*/
public void animationEventPerformed(AnimationEvent e) {
if (!isAnimatingBSTTree()) {
if (animators != null) {
animators.clear();
}
return;
}
if (e.getStatus().equals(Animation.FINISH)) {
animators.remove(e.getSource());
}
}
}