/*
* @(#)BSTTree.java
*
* Last Modified: 8/06/02
*/
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.font.*;
import java.awt.geom.*;
/** * The class provides the base structure of a <code>BSTTree</code>, a node of the Binary Search Tree.
* It uses the elements <i>natural ordering</i>. It uses everything defined within the <code>AbstractTree</code>
* <p>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.
*
* <p><hr>The BSTTree defines methods necessary for a BSTTree, a DrawingBSTTree, and an AnimatingBSTTree.
* The type is set when the node is constructed but can be changed in the middle. If a method is
* called for a type that is higher is level than the type of the tree, the method will be ignored.
*
* <p> <i>A <b>Binary Search Tree</b> 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. </i> (Sedgewick, 502, <i>Algorithms in C</i>)
*
* <p><b>Note that this implementation is not synchronized.</b> If multiple
* threads access this tree concurrently, and at least one of the threads modifies
* the tree structurally, it <i>must</i> be synchronized externally.
*
* @author Corey Sanders
* @version 3.4 9/15/01
*/
public class BSTTree implements Tree, DrawingTree, AnimationListener, AnimatingTree {
/*************************************************************************/
/* 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
* <tt>Comparable</tt> interface. Furthermore, all such keys must be
* <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
* ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> 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 <tt>add(Comparable key, Object
* value)</tt> call will throw a <tt>ClassCastException</tt>.
*
* <p><b>Default type is BST_TREE_TYPE.</b>
*/
public BSTTree() {
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:
* <ul>
* <li><b>BST_TREE_TYPE</b>: Only implements the basic methods of a Binary Search Tree.
* A lot of the expensive (huge overhead) information necessary for drawing and animating
* are left not instantiated to save time. This basic type is simply for BST usage.</li>
* <li><b>DRAWING_BST_TREE_TYPE</b>: Implements the methods necessary to draw the BST onto
* the screen. This includes a lot of overhead data that is necessary for rendering the tree. </li>
* <li><b>ANIMATING_BST_TREE_TYPE</b>: This implements the rest of the methods necessary to
* animate the tree. The overhead is small for the animating methods, but for every method
* possible, the animation occurs. Therefore, to stop animation, the node must be set to just
* DRAWING_BST_TREE_TYPE and then the method will ignore the animation.</li></ul>
*
*@param treeType type of tree that should be implemented.
*/
public BSTTree(int treeType) {
setTreeType(treeType);
}
/**
* 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;
((BSTTree)getLeftTree()).fixTreeType(treeType);
((BSTTree)getRightTree()).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 <code>BSTTree</code> into the <code>BSTTree</code> copy.
* It simply copies it field by field, for usage when changes are made to the head node.<p>
* If the tree type is Drawing or Animating, the method copies the fields accordingly.
*
* @param copy the <code>BSTTree</code> that takes the fields of the <code>BSTTree</code>.
*/
protected void copyBSTTree(BSTTree 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. */
/*************************************************************************/
/**
* 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 BSTTree left;
private BSTTree right;
/**
* The key object in this current node.
*/
private Comparable 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 BSTTree parent;
/**
* Parent link
*/
private BSTTreeHead 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*
**********************************
*/
/**
* 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 BSTTreeHead 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 <code>BSTTree</code> is empty.
*
* @return the boolean true if the <code>BSTTree</code> is empty.
*/
public boolean isEmpty() {
return (key == null);
}
/**
* Returns the value of the current <code>BSTTree</code>.
*
* @return the value of the current <code>BSTTree</code>.
*/
public Object getValue() {
return value;
}
/**
* Returns the key of the current <code>BSTTree</code>.
*
* @return the key of the current <code>BSTTree</code>.
*/
public Comparable getKey() {
return key;
}
/**
* Gets the the level of the current <code>BSTTree</code>.
* 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 <code>BSTTree</code>.
*/
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 <code>BSTTree</code> of the current tree. Used to traverse down
* the binary tree.
*
* @return <code>BSTTree</code> that is the left subtree of the current <code>BSTTree</code>,
* null of no such tree exists.
*/
public BSTTree getLeftTree() {
return left;
}
/**
* Returns the right <code>BSTTree</code> of the current tree. Used to traverse down
* the binary tree.
*
* @return <code>BSTTree</code> that is the right subtree of the current <code>BSTTree</code>,
* null of no such tree exists.
*/
public BSTTree getRightTree() {
return right;
}
/**
* Returns the children of the current <code>Tree</code>.
*
* @return <code>Tree</code> array that is the children and null if the tree is an exterior node.
*/
public Tree[] getChildren() {
BSTTree[] treeList = new BSTTree[2];
treeList[0] = getLeftTree();
treeList[1] = getRightTree();
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 Tree getParentTree() {
return parent;
}
/**
* 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 (getLeftTree() == null || getRightTree() == null || ((BSTTree)getParentTree()) == null)
return false;
return
(
(this.getLeftTree().getParentTree() == this)
&& (this.getRightTree().getParentTree() == this)
&& (( ((BSTTree)this.getParentTree()).getRightTree() == this)
|| ( ((BSTTree)this.getParentTree()).getLeftTree() == this))
);
}
/**
**********************************
* 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 <code>getLevel</code>).
*
* @param head TreeHead for the current node.
*/
protected void setHead(BSTTreeHead 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(BSTTree 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(BSTTree 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(BSTTree parent) {
this.parent = parent;
}
/**
* Sets the the level of the current <code>BSTTree</code>.
* 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 <code>BSTTree</code>.
* 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 <code>BSTTree</code>. 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 <code>BSTTree</code>.
*
* @param valueInsert object to be inserted as the value of the <code>BSTTree</code>.
*/
protected void setNode(Comparable 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 <code>BSTTree</code>
*
*/
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 BSTTree(getTreeType()));
setRightTree(new BSTTree(getTreeType()));
getLeftTree().setParentTree(this);
getRightTree().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(BSTTree newTree, int currentLevel) throws ClassCastException {
currentLevel++; // Increments the level.
if ((newTree.getKey()).compareTo(getKey()) < 0) { // Go to the left
if(getLeftTree().isEmpty()) { // Leaf of tree
setLeftTree(newTree); // Set tree.
getLeftTree().setParentTree(this); // Set parent.
getLeftTree().setLevel(currentLevel+1); // Increase level
if (getLeftTree().getLevel() > getHead().getTreeLevel())
getHead().setTreeLevel(getLeftTree().getLevel());
getLeftTree().setSize(1); // Set initial size
}
else
getLeftTree().insert(newTree, currentLevel);
}
else { // Go to the right
if(getRightTree().isEmpty()) { // Leaf of tree
setRightTree(newTree); // Set tree.
getRightTree().setParentTree(this); // Set parent.
getRightTree().setLevel(currentLevel+1); // Increase level
if (getRightTree().getLevel() > getHead().getTreeLevel())
getHead().setTreeLevel(getRightTree().getLevel());
getRightTree().setSize(1); // Set initial size
}
else
getRightTree().insert(newTree, currentLevel);
}
// Set the size as one plus the left and sizes.
setSize(getLeftTree().size() + getRightTree().size() + 1);
return;
}
/**
* Removes the BSTTree from the tree. The call bypasses the <code>BSTTree</code> by
* partitioning the right subTree and replacing itself with the smallest of the right tree.
*/
protected void remove() {
BSTTree currentParent = (BSTTree)getParentTree();
// Gets the smallest of the right tree.
BSTTree temp = join(getLeftTree(), getRightTree());
// Replaces links
if (this == currentParent.getLeftTree()) {
currentParent.setLeftTree(temp);
}
else {
currentParent.setRightTree(temp);
}
temp.setParentTree(currentParent);
if (temp.isEmpty())
return;
// fixes the size
temp.setSize(temp.getLeftTree().size() + temp.getRightTree().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(Comparable keyFind) throws ClassCastException {
if(isEmpty()) {
return getParentTree();
}
// Go left
if (keyFind.compareTo(getKey()) < 0) {
return getLeftTree().search(keyFind);
}
// Go right
if (keyFind.compareTo(getKey()) > 0) {
return getRightTree().search(keyFind);
}
else { // Equal (Match)
return this;
}
}
/**
* Selects for the <code>Tree</code> in the entire tree.
*
* @param keySelect integer key selecting the count item.
* @return Tree the <code>Tree</code> found or null.
*/
protected Tree select(int keySelect) {
if(isEmpty()) {
return null;
}
if (getLeftTree().size() > keySelect) {
return getLeftTree().select(keySelect);
}
else if (getLeftTree().size() < keySelect) {
return getRightTree().select(keySelect - getLeftTree().size() - 1);
}
return this;
}
/**
* Partitions the <code>Tree</code> 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 BSTTree partition(int keySelect, int levelCount) {
BSTTree newNode;
if (getLeftTree().size() > keySelect) {
// Recursive call
return getLeftTree().partition(keySelect, levelCount + 1);
}
else if (getLeftTree().size() < keySelect) {
return getRightTree().partition(keySelect - getLeftTree().size() - 1, levelCount + 1);
}
// Rotate Up the amount of levels the partition went down.
((BSTTreeHead)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.
*/
protected BSTTree rotateRight() {
BSTTree temp = (BSTTree)getLeftTree();
setLeftTree((BSTTree)temp.getRightTree());
getLeftTree().setParentTree(this);
temp.setRightTree(this);
setParentTree(temp);
temp.setParentTree(null);
// Fix sizes
setSize(getLeftTree().size() + getRightTree().size() + 1);
temp.setSize(temp.getLeftTree().size() + temp.getRightTree().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.
*/
protected BSTTree rotateLeft() {
BSTTree temp = (BSTTree)getRightTree();
setRightTree((BSTTree)temp.getLeftTree());
getRightTree().setParentTree(this);
temp.setLeftTree(this);
setParentTree(temp);
temp.setParentTree(null);
// Fix sizes
setSize(getLeftTree().size() + getRightTree().size() + 1);
temp.setSize(temp.getLeftTree().size() + temp.getRightTree().size() + 1);
return temp;
}
/**
* 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 BSTTree join(BSTTree treeJoinOne, BSTTree treeJoinTwo) {
// Empty trees
if (treeJoinTwo.isEmpty()) {
return treeJoinOne;
}
if (treeJoinOne.isEmpty()) {
return treeJoinTwo;
}
BSTTree returnTree;
// Tree one is less than tree two
if (treeJoinOne.getKey().compareTo(treeJoinTwo.getKey()) < 0) {
treeJoinOne.setParentTree(treeJoinTwo.partition(0, 0));
((BSTTree)treeJoinOne.getParentTree()).setLeftTree(treeJoinOne);
((BSTTree)treeJoinOne.getParentTree()).setSize(((BSTTree)treeJoinOne.getParentTree()).getLeftTree().size() + ((BSTTree)treeJoinOne.getParentTree()).getRightTree().size() + 1);
return ((BSTTree)treeJoinOne.getParentTree());
}
else {
treeJoinTwo.setParentTree(treeJoinOne.partition(0, 0));
((BSTTree)treeJoinTwo.getParentTree()).setLeftTree(treeJoinTwo);
((BSTTree)treeJoinTwo.getParentTree()).setSize(((BSTTree)treeJoinTwo.getParentTree()).getLeftTree().size() + ((BSTTree)treeJoinTwo.getParentTree()).getRightTree().size() + 1);
return (BSTTree)treeJoinTwo.getParentTree();
}
}
/**
**********************************
* 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 treeList) {
if (isEmpty())
return;
// Push onto stack
treeList.add(this);
((BSTTree)getLeftTree()).makePreorderTree(treeList);
((BSTTree)getRightTree()).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 treeList) {
if (isEmpty())
return;
((BSTTree)getLeftTree()).makeInorderTree(treeList);
// Push onto stack
treeList.add(this);
((BSTTree)getRightTree()).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 treeList) {
if (isEmpty())
return;
((BSTTree)getLeftTree()).makePostorderTree(treeList);
((BSTTree)getRightTree()).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 <code>DrawingTree</code> 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 <code>DrawingTree</code>, last drawn as this specific shape.
*/
private Shape currentShape;
/**
* The current <code>AffineTransform</code> of the <code>DrawingTree</code>, representing the
* most current Transformation to draw the nodeOriginShape and keyOriginRectangle.
*/
private AffineTransform currentTransform;
/**
* The previous <code>AffineTransform</code> of the <code>DrawingTree</code>.
*/
private AffineTransform previousTransform;
/**
* The double drawing level for the current <code>DrawingTree</code>.
*/
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 (<code>saveLeftSettings</code>).
*/
private int countLeftSaves = 0;
/**
* The count for how many right saves the current Node has been called (<code>saveRightSettings</code>).
*/
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 <code>DrawingTree</code>. 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 <code>DrawingTree</code>. 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 <code>NodeSettings</code> of the tree.
* These settings are used for drawing the node and the links of the given tree.
*
* @return <code>NodeSettings</code> 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 <code>NodeSettings</code> 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 <code>Shape</code> 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 <code>Shape</code> of the key.
*/
protected Shape getKeyOriginRectangle() {
return keyOriginRectangle;
}
/**
* Gets the shape of the node previously drawn or transformed.
*
* @return <code>Shape</code> of the node previously drawn.
*/
protected Shape getCurrentShape() {
return currentShape;
}
/**
* Gets the <code>AffineTransform</code> defined within the tree. The current transform
* is used when calling <code>draw</code> without the <code>AffineTransform</code> value.
*
* @return transform set for the current drawing of the tree.
*/
public AffineTransform getCurrentTransform() {
return currentTransform;
}
/**
* Gets the <code>AffineTransform</code> previously defined within the tree. The previous transform
* is used when calling <code>restoreTransform</code> and is automatically
* updates with each call of <code>setCurrentTransform</code>.
*
* @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
* <code>makeTree</code> or by the client using <code>setCurrentGraphics</code>.
*
* @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 <code>DrawingTree</code>. 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 <code>getClipBounds</code> 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);
getLeftTree().setTreeSettings(s, k);
getRightTree().setTreeSettings(s, k);
}
/**
* Sets the settings of the node for the <code>BSTTree</code>. No settings are saved
* and the previous settings are not modified.
*
* @param s <code>NodeSettings</code> set for the entire tree.
*/
public void setNodeSettings(NodeSettings s) {
currentSettings = (NodeSettings)s.clone();
}
/**
* Sets the <code>NodeSettings</code> of the <code>DrawingTree</code>.
* These settings are used for drawing the node and the links of the given tree.
* <p> If the settings are saved, the <b>previous</b> settings are modified to the <code>NodeSettings</code>,
* leaving the current settings unmodified. To modify the current settings, use <code>setNodeSettings</code>.
*
* If the settings are not saved, the previous settings are made null and the currentSettings are set.
*
* @param s <code>NodeSettings</code> 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 <code>AffineTransform</code> defined within the tree. The set transform
* is used when calling <code>draw</code> without the <code>AffineTransform</code> 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 <code>AffineTransform</code> defined previously within the tree.
* The previous transform is always the last transform defined and is automatically
* updated each time <code>setCurrentTransform</code> is called.
*/
public void restoreTransform() {
if (!isDrawingBSTTree())
return;
currentTransform = previousTransform;
}
/**
*****************************************************
* DRAWING_BST_TREE_TYPE NodeSettings Saving methods *
*****************************************************
*/
/**
* 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: <br>
* <ul>
* <li><code>setCurrentTransform</code></li>
* <li><code>setLevel</code></li>
* <li><code>setDrawingLevel</code></li>
* <li><code>setCurrentPower2</code></li>
* <li><code>setScreenBounds</code>(using head bounds)</li>
* </ul><p>
* The method calls the method for the left and right children, using properly modified
* <code>AffineTransform</code> and level.
*
* @param a <code>AffineTransform</code> 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 ( ((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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.
getLeftTree().makeTree(leftTransform, currentLevel+1);
getRightTree().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);
}
getLeftTree().drawTree(g2);
getRightTree().drawTree(g2);
}
/**
* Draws the node of the tree using the previously defined graphics. The drawing uses
* the previously defined <code>AffineTransform</code>.
*
*/
public void drawNode() {
NodeSettings temp = (NodeSettings)getSettings().clone();
getSettings().setScheme(NodeSettings.ERASE, Color.black);
drawNode(getCurrentGraphics());
setNodeSettings(temp);
drawNode(getCurrentGraphics());
}
/**
* Draws the node of the tree to the given Graphics2D. The drawing uses
* the previously defined <code>AffineTransform</code>.
*
* @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 <code>AffineTransform</code>.
* The drawing uses the <code>AffineTransform</code> 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());
// 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);
// Draws the key.
((DrawableKey)getValue()).drawKey(g2, translateTransform);
}
/**
* Draws the node and left link of the tree using the previously defined graphics.
* The drawing uses the previously defined <code>AffineTransform</code>,
* section height, drawing level, and power level.
*/
public void drawNodeAndLeftLink() {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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 <code>AffineTransform</code>,
* section height, drawing level, and power level.
*/
public void drawNodeAndRightLink() {
boolean bottomLinks;
if (getHead() != null) {
bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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);
}
/**
* Draws the node and link of the tree using the previously defined graphics..
* The drawing uses the previously defined <code>AffineTransform</code>,
* 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 <code>AffineTransform</code>,
* 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 = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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 <code>AffineTransform</code>,
* 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 = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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 <code>AffineTransform</code>, 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 = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.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 <code>AffineTransform</code>, 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();
BSTTree rightTree = getRightTree();
Line2D.Double right;
if (rightTree != null) {
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();
BSTTree leftTree = getLeftTree();
// Draw the left and right links
Line2D.Double left;
if (leftTree != 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 getRightTree().findNode(x, y);
else
// Otherwise the method is called for the right.
return getLeftTree().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 animators;
/**
* The boolean flag whether when called form within an Animation, it should draw.
*/
private boolean animateDrawing;
/**
* Constructor for the ANIMATING_BST_TREE_TYPE. This constructs and sets all values to defaults
* for the ANIMATING_BST_TREE_TYPE.
*/
public void constructAnimatingBSTTree() {
if (animators == null) {
animators = new LinkedList();
}
animateDrawing = true;
}
/**
*********************************************
* ANIMATING_BST_TREE_TYPE Accesssor methods *
*********************************************
*/
/**
* Returns true if the node is animating. It simply determines if the list of animators is empty.
*
* @return true if the node is currently animating.
*/
public boolean isNodeAnimating() {
if (animators == null)
return false;
else
return (!animators.isEmpty());
}
/**
* Gets the first <code>Animation</code> 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 (Animation)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 <code>Animation</code> 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 <code>BSTTree</code> down from the current node. This is a recursive call,
* defined in <code>BSTTree</code>. 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
* <code>WaitingActionList</code>.
*
* @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(BSTTree 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
getLeftTree().makeInsertAnimation(insertNode, newAnimator);
}
else { // Go to the right
getRightTree().makeInsertAnimation(insertNode, newAnimator);
}
}
/**
* Constructs the <code>searchBSTAnimation</code> 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(Comparable keySearch, SearchBSTAnimation 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
getLeftTree().makeSearchAnimation(keySearch, newAnimator);
}
else if (keySearch.compareTo(getKey()) > 0) { // Go to the right
getRightTree().makeSearchAnimation(keySearch, newAnimator);
}
// If equal, stop. (SEARCH HIT)
}
/**
* Constructs the <code>partitionBSTAnimation</code> 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, SelectionBSTAnimation newAnimator) throws ClassCastException {
if (!isAnimatingBSTTree()) {
return;
}
if (isEmpty()) {
return;
}
// Add the animator to the Insertion animation.
newAnimator.add(this);
if (getLeftTree().size() > elementCount) {
getLeftTree().makeSelectionAnimation(elementCount, newAnimator);
}
if (getLeftTree().size() < elementCount) {
getRightTree().makeSelectionAnimation(elementCount - getLeftTree().size() - 1, newAnimator);
}
}
/**
********************************************************
* ANIMATING_BST_TREE_TYPE Implements Animation Listener*
********************************************************
*/
/**
* Implements <code>AnimationListener</code> which requires the following method.
* The only status of animation it listens for is <code>Animation.FINISH</code>, 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());
}
}
}