Class BSTTree

java.lang.Object
  |
  +--BSTTree

All Implemented Interfaces:

AnimatingTree, AnimationListener, DrawingTree, java.util.EventListener, Tree

Direct Known Subclasses:

BalancedBSTTree, BSTTreeHead, MovingBSTTree, RedBlackTree

public class BSTTree

extends java.lang.Object

implements Tree, DrawingTree, AnimationListener, AnimatingTree

The class provides the base structure of a 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.

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.

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.

Field Summary

static int	ANIMATING_BST_TREE_TYPE Tree type defining AnimatingBSTTree.
static int	BST_TREE_TYPE Tree type defining only a BSTTree.
static int	DRAWING_BST_TREE_TYPE Tree type defining a DrawingBSTTree.

Constructor Summary

BSTTree()
Constructs a new, empty BSTTree, sorted according to the keys' natural order.

BSTTree(int treeType)
Constructs a new, empty BSTTree according to the type passed.

Method Summary

void	addAnimator(Animation a) Adds an animation to the current node.
void	animationEventPerformed(AnimationEvent e) Implements AnimationListener which requires the following method.
void	constructAnimatingBSTTree() Constructor for the ANIMATING_BST_TREE_TYPE.
void	constructBSTTree() Constructor for the BST_TREE_TYPE.
void	constructDrawingBSTTree() Constructor for the DRAWING_BST_TREE_TYPE.
protected void	copyBSTTree(BSTTree copy) Copies the fields of this BSTTree into the BSTTree copy.
protected void	drawLeftLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) Draws just the left link according to the NodeSettings currently set.
void	drawNode() Draws the node of the tree using the previously defined graphics.
void	drawNode(java.awt.Graphics2D g2) Draws the node of the tree to the given Graphics2D.
void	drawNode(java.awt.Graphics2D g2, java.awt.geom.AffineTransform a) Draws the node of the tree to the given Graphics2D, using the AffineTransform.
void	drawNodeAndLeftLink() Draws the node and left link of the tree using the previously defined graphics.
void	drawNodeAndLink() Draws the node and link of the tree using the previously defined graphics..
void	drawNodeAndLink(java.awt.Graphics2D g2) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndLink(java.awt.Graphics2D g2, java.awt.geom.AffineTransform a) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndLink(java.awt.Graphics2D g2, java.awt.geom.AffineTransform a, boolean bottomLinks) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndLink(java.awt.Graphics2D g2, boolean bottomLinks) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) Draws the node and link of the tree to the given Graphics2D.
void	drawNodeAndRightLink() Draws the node and right link of the tree using the previously defined graphics.
protected void	drawRightLink(java.awt.Graphics2D g2, double sectionHeight, java.awt.geom.AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) Draws just the right link according to the NodeSettings currently set.
protected void	drawTree(java.awt.Graphics2D g2) Draws the tree recursively, on to the Graphics2D.
void	eraseNodeAndLink() Erases the previous drawing of the nodeAndLinkm, simply drawing.
protected DrawingTree	findNode(double x, double y) Finds the node represented by the x-y coordinates given.
protected void	fixLevel(int currentLevel) Fixes the level of the node.
protected int	fixSize() Fixes the size of the node.
protected void	fixTreeType(int treeType) Fixes the tree type for the entire BSTTree.
Animation	getAnimator() Gets the first Animation of the node.
Tree[]	getChildren() Returns the children of the current Tree.
java.awt.Graphics2D	getCurrentGraphics() Gets the graphics previously defined within the tree.
double	getCurrentPower2() Gets the current power of 2 to which the tree was last drawn.
protected java.awt.Shape	getCurrentShape() Gets the shape of the node previously drawn or transformed.
java.awt.geom.AffineTransform	getCurrentTransform() Gets the AffineTransform defined within the tree.
double	getDrawingLevel() Gets the drawing level for the current DrawingTree.
BSTTreeHead	getHead() Gets the head for the node.
int	getInorderCount() Returns the inorder count of the current node.
java.lang.Comparable	getKey() Returns the key of the current BSTTree.
protected java.awt.Shape	getKeyOriginRectangle() Gets the shape of the key within the node shape at the origin and size 1, for usage in transforming and drawing.
BSTTree	getLeftTree() Returns the left BSTTree of the current tree.
int	getLevel() Gets the the level of the current BSTTree.
protected java.awt.Shape	getNodeOriginShape() Gets the shape of the node at the origin and size 1, for usage in transforming and drawing.
Tree	getParentTree() Returns the parent of the current tree.
protected java.awt.geom.AffineTransform	getPreviousTransform() Gets the AffineTransform previously defined within the tree.
BSTTree	getRightTree() Returns the right BSTTree of the current tree.
java.awt.geom.Rectangle2D	getScreenBounds() Gets the bounds of the screen to which the tree is drawing.
double	getSectionHeight() Gets the height of the section for the DrawingTree.
NodeSettings	getSettings() Gets the NodeSettings of the tree.
int	getTreeType() Gets the tree type for the BSTTree.
java.lang.String	getTreeTypeString() Gets the tree type String for the BSTTree.
java.lang.Object	getValue() Returns the value of the current BSTTree.
protected void	insert(BSTTree newTree, int currentLevel) Inserts the given object into the tree, using recursive calls and is called from the Head node.
boolean	inTree() Determines if the current node is within a BSTTree.
boolean	isAnimateDrawing() Gets the boolean flag whether the node should draw if called from an animation.
protected boolean	isAnimatingBSTTree() Returns true if the BSTTree is of type AnimatingBSTTree.
protected boolean	isDrawingBSTTree() Returns true if the BSTTree is of type DrawingBSTTree or higher type.
boolean	isEmpty() Returns true if the current BSTTree is empty.
boolean	isNodeAnimating() Returns true if the node is animating.
boolean	isSettingsSaved() Returns true if the settings are currently saved for the DrawingTree.
protected static BSTTree	join(BSTTree treeJoinOne, BSTTree treeJoinTwo) Joins two subtrees together as one tree.
protected void	makeInorderTree(java.util.LinkedList treeList) Makes an array in inorder using recursive calls and the count.
protected void	makeInsertAnimation(BSTTree insertNode, InsertBSTAnimation newAnimator) Insert the BSTTree down from the current node.
protected void	makePostorderTree(java.util.LinkedList treeList) Makes an array in postorder using recursive calls and the count.
protected void	makePreorderTree(java.util.LinkedList treeList) Makes an array in preorder using recursive calls and the count.
protected void	makeSearchAnimation(java.lang.Comparable keySearch, SearchBSTAnimation newAnimator) Constructs the searchBSTAnimation down from the current node.
protected void	makeSelectionAnimation(int elementCount, SelectionBSTAnimation newAnimator) Constructs the partitionBSTAnimation down from the current node.
protected void	makeTree(java.awt.geom.AffineTransform a, int currentLevel) Makes the tree recursively using the two parameters.
protected BSTTree	partition(int keySelect, int levelCount) Partitions the Tree at the given keySelect and rotates the keySelectth node to this node's position.
protected void	remove() Removes the BSTTree from the tree.
void	restoreLeftSettings() Restores the settings for the tree, decrementing the count of left Saves and total saves by one.
void	restoreRightSettings() Restores the settings for the tree, decrementing the count of right Saves and total saves by one.
void	restoreSettings() Restores the settings for the tree, decrementing the count of saves by one.
void	restoreTransform() Restores the AffineTransform defined previously within the tree.
protected BSTTree	rotateLeft() Rotate the tree to the left.
protected BSTTree	rotateRight() Rotate the tree to the right.
void	saveLeftSettings() Saves the settings for the tree, incrementing the count of left Saves and total saves by one and setting the previous settings accordingly.
void	saveRightSettings() Saves the settings for the tree, incrementing the count of right Saves and total saves by one and setting the previous settings accordingly.
void	saveSettings() Saves the settings for the tree, incrementing the count of saves by one and setting the previous settings accordingly.
protected Tree	search(java.lang.Comparable keyFind) Finds a node within a tree using the comparable keyFind.
protected Tree	select(int keySelect) Selects for the Tree in the entire tree.
void	setAnimateDrawing(boolean animateDrawing) Sets the boolean flag whether the node should draw if called from an animation.
void	setCurrentGraphics(java.awt.Graphics2D g2) Sets the graphics defined within the tree.
protected void	setCurrentPower2(double p2) Sets the current power of 2.
protected void	setCurrentTransform(java.awt.geom.AffineTransform a) Sets the AffineTransform defined within the tree.
protected void	setDrawingLevel(double level) Sets the drawing level for the current DrawingTree.
protected void	setHead(BSTTreeHead head) Sets the head for the node.
protected void	setInorderCount(int inorder_count) Sets the inorder count of the current node.
protected void	setLeaf() Sets the values of a new Node left and right tress, to refer to null trees.
protected void	setLeftTree(BSTTree left) Sets the left tree for the node.
protected void	setLevel(int level) Sets the the level of the current BSTTree.
protected void	setNode(java.lang.Comparable keyInsert, java.lang.Object valueInsert) Sets the key and value of the BSTTree.
void	setNodeSettings(NodeSettings s) Sets the settings of the node for the BSTTree.
protected void	setParentTree(BSTTree parent) Sets the parent tree for the node.
protected void	setRightTree(BSTTree right) Sets the right tree for the node.
void	setScreenBounds(java.awt.geom.Rectangle2D bounds) Sets the bounds of the screen to which the tree is drawing.
void	setSettings(NodeSettings s) Sets the NodeSettings of the DrawingTree.
protected void	setSize(int size) Sets the the size of the current BSTTree.
protected void	setTreeSettings(NodeSettings s, KeySettings k) Sets the settings of the entire tree.
void	setTreeType(int treeType) Sets the tree type for the BSTTree.
int	size() Returns the number of nodes in the current Tree and below.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

BST_TREE_TYPE

public static final int BST_TREE_TYPE

Tree type defining only a BSTTree. The Drawing and Animating methods will not be available.

See Also:

Constant Field Values

DRAWING_BST_TREE_TYPE

public static final int DRAWING_BST_TREE_TYPE

Tree type defining a DrawingBSTTree. The Animating methods will not be available.

See Also:

Constant Field Values

ANIMATING_BST_TREE_TYPE

public static final int ANIMATING_BST_TREE_TYPE

Tree type defining AnimatingBSTTree. All methods will be available and all animations will occur.

See Also:

Constant Field Values

Constructor Detail

BSTTree

public BSTTree()

Constructs a new, empty BSTTree, sorted according to the keys' natural order. All keys inserted into the tree must implement the Comparable 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(Comparable key, Object value) call will throw a ClassCastException.

Default type is BST_TREE_TYPE.

BSTTree

public BSTTree(int treeType)

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:

• BST_TREE_TYPE: 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.
• DRAWING_BST_TREE_TYPE: 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.
• ANIMATING_BST_TREE_TYPE: 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.

Parameters:

treeType - type of tree that should be implemented.

Method Detail

setTreeType

public void setTreeType(int treeType)

Sets the tree type for the BSTTree.

Parameters:

treeType - setting for the tree.

getTreeType

public int getTreeType()

Gets the tree type for the BSTTree.

Returns:

tree type for the tree.

fixTreeType

protected void fixTreeType(int treeType)

Fixes the tree type for the entire BSTTree.

Parameters:

treeType - setting for the tree.

getTreeTypeString

public java.lang.String getTreeTypeString()

Gets the tree type String for the BSTTree.

Returns:

tree type String for the tree.

isDrawingBSTTree

protected boolean isDrawingBSTTree()

Returns true if the BSTTree is of type DrawingBSTTree or higher type.

Returns:

true if is is DRAWING_BST_TREE_TYPE.

isAnimatingBSTTree

protected boolean isAnimatingBSTTree()

Returns true if the BSTTree is of type AnimatingBSTTree.

Returns:

true if is is DRAWING_BST_TREE_TYPE.

copyBSTTree

protected void copyBSTTree(BSTTree copy)

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.

Parameters:

copy - the BSTTree that takes the fields of the BSTTree.

constructBSTTree

public void constructBSTTree()

Constructor for the BST_TREE_TYPE. This constructs and sets all values to defaults for the BST_TREE_TYPE.

getHead

public BSTTreeHead getHead()

Gets the head for the node. The head node is used in numerous operations and is the reference for the tree.

Returns:

BSTTreeHead that represents the head for this node, indicating the tree.

size

public int size()

Returns the number of nodes in the current Tree and below.

Specified by:

size in interface Tree

Returns:

the number of nodes in the current Tree and below.

isEmpty

public boolean isEmpty()

Returns true if the current BSTTree is empty.

Specified by:

isEmpty in interface Tree

Returns:

the boolean true if the BSTTree is empty.

getValue

public java.lang.Object getValue()

Returns the value of the current BSTTree.

Specified by:

getValue in interface Tree

Returns:

the value of the current BSTTree.

getKey

public java.lang.Comparable getKey()

Returns the key of the current BSTTree.

Specified by:

getKey in interface Tree

Returns:

the key of the current BSTTree.

getLevel

public int getLevel()

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.

Specified by:

getLevel in interface Tree

Returns:

integer count of the level of the current BSTTree.

getInorderCount

public int getInorderCount()

Returns the inorder count of the current node.

Returns:

the inorder count of the node.

getLeftTree

public BSTTree getLeftTree()

Returns the left BSTTree of the current tree. Used to traverse down the binary tree.

Returns:

BSTTree that is the left subtree of the current BSTTree, null of no such tree exists.

getRightTree

public BSTTree getRightTree()

Returns the right BSTTree of the current tree. Used to traverse down the binary tree.

Returns:

BSTTree that is the right subtree of the current BSTTree, null of no such tree exists.

getChildren

public Tree[] getChildren()

Returns the children of the current Tree.

Specified by:

getChildren in interface Tree

Returns:

Tree array that is the children and null if the tree is an exterior node.

getParentTree

public Tree getParentTree()

Returns the parent of the current tree. Used to traverse up the binary tree.

Specified by:

getParentTree in interface Tree

Returns:

Tree that is the parent of the current tree and null if the tree is the head.

inTree

public boolean inTree()

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.

Returns:

true if the node is within a BSTTree.

setHead

protected void setHead(BSTTreeHead head)

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).

Parameters:

head - TreeHead for the current node.

setLeftTree

protected void setLeftTree(BSTTree left)

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.

Parameters:

left - BSTTree that sets the left link for the current node.

setRightTree

protected void setRightTree(BSTTree right)

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.

Parameters:

right - BSTTree that sets the right link for the current node.

setParentTree

protected void setParentTree(BSTTree parent)

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.

Parameters:

parent - BSTTree that sets the parent link for the current node.

setLevel

protected void setLevel(int level)

Sets the the level of the current BSTTree. The level sets the integer count of how far down the tree is.

Parameters:

level - the level set for the node.

setSize

protected void setSize(int size)

Sets the the size of the current BSTTree. The size represents the nodes below and including the current node.

Parameters:

size - integer setting the size of the node, which is the count of the nodes below and including the current node.

setInorderCount

protected void setInorderCount(int inorder_count)

Sets the inorder count of the current node.

setNode

protected void setNode(java.lang.Comparable keyInsert,
                       java.lang.Object valueInsert)

Sets the key and value of the BSTTree. This is prtoected for usage by extended classes but not for public access.

Parameters:

keyInsert - comparable object to be inserted as the key of the BSTTree.

valueInsert - object to be inserted as the value of the BSTTree.

fixLevel

protected void fixLevel(int currentLevel)

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.

Parameters:

currentLevel - currentLevel of the BSTTree

fixSize

protected int fixSize()

Fixes the size of the node. The method call is recursive.

Returns:

integer of the size fixed, which is passed up through the BSTTree, recursively.

setLeaf

protected void setLeaf()

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.

insert

protected void insert(BSTTree newTree,
                      int currentLevel)
               throws java.lang.ClassCastException

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.

Parameters:

newTree - the tree to be inserted, with key and value already set.

currentLevel - keeps track of the recursive call, and sets the new level if it changes.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the tree.

remove

protected void remove()

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.

search

protected Tree search(java.lang.Comparable keyFind)
               throws java.lang.ClassCastException

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.

Parameters:

keyFind - the key which the method is attempting to find.

Returns:

Tree which contains the keyFind as a key or the last examined tree if the keyFind is not present in the entire tree.

java.lang.ClassCastException

select

protected Tree select(int keySelect)

Selects for the Tree in the entire tree.

Parameters:

keySelect - integer key selecting the count item.

Returns:

Tree the Tree found or null.

partition

protected BSTTree partition(int keySelect,
                            int levelCount)

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

Parameters:

keySelect - integer key selecting the count item.

levelCount - integer counting the levels down the partition is going.

Returns:

BSTTree that is the reference to the newly partitioned tree.

rotateRight

protected BSTTree rotateRight()

Rotate the tree to the right. It simply changes around references to BSTTrees.

Returns:

BSTTree that is the reference to the newly rotated tree.

rotateLeft

protected BSTTree rotateLeft()

Rotate the tree to the left. It simply changes around references to BSTTrees.

Returns:

BSTTree that is the reference to the newly rotated tree.

join

protected static BSTTree join(BSTTree treeJoinOne,
                              BSTTree treeJoinTwo)

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.

Parameters:

treeJoinOne - one subtree to be joined.

treeJoinTwo - second subtree to be joined.

Returns:

BSTTree object which is the new reference to the joined tree.

makePreorderTree

protected void makePreorderTree(java.util.LinkedList treeList)

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.

makeInorderTree

protected void makeInorderTree(java.util.LinkedList 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.

makePostorderTree

protected void makePostorderTree(java.util.LinkedList 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.

constructDrawingBSTTree

public void constructDrawingBSTTree()

Constructor for the DRAWING_BST_TREE_TYPE. This constructs and sets all values to defaults for the DRAWING_BST_TREE_TYPE.

getDrawingLevel

public double getDrawingLevel()

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.

Specified by:

getDrawingLevel in interface DrawingTree

Returns:

the double level for the drawing node.

getSectionHeight

public double getSectionHeight()

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.

Specified by:

getSectionHeight in interface DrawingTree

Returns:

double height of the drawing section for the node.

getScreenBounds

public java.awt.geom.Rectangle2D getScreenBounds()

Gets the bounds of the screen to which the tree is drawing. The bounds generally is simply the rectangle enclosing the Graphics2D passed.

Specified by:

getScreenBounds in interface DrawingTree

Returns:

the rectangle representing the bounds of the screen.

getCurrentPower2

public double getCurrentPower2()

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.

Returns:

double power of 2 last used in drawing the tree (2^drawingLevel).

getSettings

public NodeSettings getSettings()

Gets the NodeSettings of the tree. These settings are used for drawing the node and the links of the given tree.

Specified by:

getSettings in interface DrawingTree

Returns:

NodeSettings for use in drawing the tree.

isSettingsSaved

public boolean isSettingsSaved()

Returns true if the settings are currently saved for the DrawingTree.

Returns:

true if the NodeSettings are saved.

getNodeOriginShape

protected java.awt.Shape getNodeOriginShape()

Gets the shape of the node at the origin and size 1, for usage in transforming and drawing.

Returns:

Shape of the node at the origin and size 1.

getKeyOriginRectangle

protected java.awt.Shape getKeyOriginRectangle()

Gets the shape of the key within the node shape at the origin and size 1, for usage in transforming and drawing.

Returns:

Shape of the key.

getCurrentShape

protected java.awt.Shape getCurrentShape()

Gets the shape of the node previously drawn or transformed.

Returns:

Shape of the node previously drawn.

getCurrentTransform

public java.awt.geom.AffineTransform getCurrentTransform()

Gets the AffineTransform defined within the tree. The current transform is used when calling draw without the AffineTransform value.

Specified by:

getCurrentTransform in interface DrawingTree

Returns:

transform set for the current drawing of the tree.

getPreviousTransform

protected java.awt.geom.AffineTransform getPreviousTransform()

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.

Returns:

transform previously set for the drawing of the tree.

getCurrentGraphics

public java.awt.Graphics2D getCurrentGraphics()

Gets the graphics previously defined within the tree. The graphics are defined in makeTree or by the client using setCurrentGraphics.

Returns:

Graphics2D which was the previously defined graphics.

setDrawingLevel

protected void setDrawingLevel(double level)

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.

Parameters:

level - the double level for the drawing node.

setScreenBounds

public void setScreenBounds(java.awt.geom.Rectangle2D bounds)

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.

Specified by:

setScreenBounds in interface DrawingTree

Parameters:

bounds - the rectangle representing the bounds of the screen.

setCurrentGraphics

public void setCurrentGraphics(java.awt.Graphics2D g2)

Sets the graphics defined within the tree.

Parameters:

g2 - Graphics2D which are the defined graphics for the tree.

setCurrentPower2

protected void setCurrentPower2(double p2)

Sets the current power of 2. The power is stored in this way to allow quick access and avoiding power methods.

Returns:

p2 power of 2 for drawing the tree (generally 2^drawingLevel).

setTreeSettings

protected void setTreeSettings(NodeSettings s,
                               KeySettings k)

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.

Parameters:

s - NodeSettings being set for the entire tree.

setNodeSettings

public void setNodeSettings(NodeSettings s)

Sets the settings of the node for the BSTTree. No settings are saved and the previous settings are not modified.

Parameters:

s - NodeSettings set for the entire tree.

setSettings

public void setSettings(NodeSettings s)

Sets the NodeSettings of the DrawingTree. These settings are used for drawing the node and the links of the given tree.

If the settings are saved, the previous settings are modified to the 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.

Specified by:

setSettings in interface DrawingTree

Parameters:

s - NodeSettings for use in drawing the tree.

setCurrentTransform

protected void setCurrentTransform(java.awt.geom.AffineTransform a)

Sets the AffineTransform defined within the tree. The set transform is used when calling draw without the AffineTransform value.

Parameters:

a - transform set for the current drawing of the tree.

restoreTransform

public void restoreTransform()

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.

saveSettings

public void saveSettings()

Saves the settings for the tree, incrementing the count of saves by one and setting the previous settings accordingly.

saveLeftSettings

public void saveLeftSettings()

Saves the settings for the tree, incrementing the count of left Saves and total saves by one and setting the previous settings accordingly.

saveRightSettings

public void saveRightSettings()

Saves the settings for the tree, incrementing the count of right Saves and total saves by one and setting the previous settings accordingly.

restoreLeftSettings

public void restoreLeftSettings()

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.

restoreRightSettings

public void restoreRightSettings()

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.

restoreSettings

public void 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.

makeTree

protected void makeTree(java.awt.geom.AffineTransform a,
                        int currentLevel)

Makes the tree recursively using the two parameters. The tree is made by setting the values using the following methods:

• setCurrentTransform
• setLevel
• setDrawingLevel
• setCurrentPower2
• setScreenBounds(using head bounds)

The method calls the method for the left and right children, using properly modified AffineTransform and level.

Parameters:

a - AffineTransform for the current tree.

currentLevel - the current level for the tree.

drawTree

protected void drawTree(java.awt.Graphics2D g2)

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.

Parameters:

g2 - the Graphics2D to which the tree is drawn.

drawNode

public void drawNode()

Draws the node of the tree using the previously defined graphics. The drawing uses the previously defined AffineTransform.

Specified by:

drawNode in interface DrawingTree

drawNode

public void drawNode(java.awt.Graphics2D g2)

Draws the node of the tree to the given Graphics2D. The drawing uses the previously defined AffineTransform.

Specified by:

drawNode in interface DrawingTree

Parameters:

g2 - graphics to which the node is drawn.

drawNode

public void drawNode(java.awt.Graphics2D g2,
                     java.awt.geom.AffineTransform a)

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.

Specified by:

drawNode in interface DrawingTree

Parameters:

g2 - graphics to which the node is drawn.

a - transform to draw the node.

drawNodeAndLeftLink

public void drawNodeAndLeftLink()

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.

drawNodeAndRightLink

public void drawNodeAndRightLink()

Draws the node and right link of the tree using the previously defined graphics. The drawing uses the previously defined AffineTransform, section height, drawing level, and power level.

eraseNodeAndLink

public void eraseNodeAndLink()

Erases the previous drawing of the nodeAndLinkm, simply drawing.

drawNodeAndLink

public void drawNodeAndLink()

Draws the node and link of the tree using the previously defined graphics.. The drawing uses the previously defined AffineTransform, section height, drawing level, and power level.

Specified by:

drawNodeAndLink in interface DrawingTree

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2)

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.

Specified by:

drawNodeAndLink in interface DrawingTree

Parameters:

g2 - graphics to which the node is drawn.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            boolean bottomLinks)

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.

Parameters:

g2 - graphics to which the node is drawn.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            java.awt.geom.AffineTransform a)

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.

Parameters:

g2 - graphics to which the node and links are drawn.

a - transfrom to draw the node and links.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            java.awt.geom.AffineTransform a,
                            boolean 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.

Parameters:

g2 - graphics to which the node and links are drawn.

a - transfrom to draw the node and links.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            double sectionHeight,
                            java.awt.geom.AffineTransform a,
                            double drawingLevel,
                            double powerLevel)

Draws the node and link of the tree to the given Graphics2D. The drawing generally uses the AffineTransform, section height, drawing level, and power level to render the node and its links.

Specified by:

drawNodeAndLink in interface DrawingTree

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            double sectionHeight,
                            java.awt.geom.AffineTransform a,
                            double drawingLevel,
                            double powerLevel,
                            boolean bottomLinks)

Draws the node and link of the tree to the given Graphics2D. The drawing generally uses the AffineTransform, section height, drawing level, and power level to render the node and its links.

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

drawRightLink

protected void drawRightLink(java.awt.Graphics2D g2,
                             double sectionHeight,
                             java.awt.geom.AffineTransform a,
                             double drawingLevel,
                             double powerLevel,
                             boolean bottomLinks)

Draws just the right link according to the NodeSettings currently set.

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

drawLeftLink

protected void drawLeftLink(java.awt.Graphics2D g2,
                            double sectionHeight,
                            java.awt.geom.AffineTransform a,
                            double drawingLevel,
                            double powerLevel,
                            boolean bottomLinks)

Draws just the left link according to the NodeSettings currently set.

Parameters:

g2 - graphics to which the node and links are drawn.

sectionHeight - the height of the tree' section, to draw the correct lengths for the links.

a - transfrom to draw the node and links.

drawingLevel - the level in the tree to which the node is currently being drawn.

powerLevel - the power to which the links extend, depending on how many links are present.

bottomLinks - the boolean to declare whether the bottom links should be drawn.

findNode

protected DrawingTree findNode(double x,
                               double y)

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.

Parameters:

x - x-coordinate to find the node.

y - y-coordinate to find the node.

Returns:

DrawingTree representing the x-y coordinates passed or null if no node is found.

constructAnimatingBSTTree

public void constructAnimatingBSTTree()

Constructor for the ANIMATING_BST_TREE_TYPE. This constructs and sets all values to defaults for the ANIMATING_BST_TREE_TYPE.

isNodeAnimating

public boolean isNodeAnimating()

Returns true if the node is animating. It simply determines if the list of animators is empty.

Specified by:

isNodeAnimating in interface AnimatingTree

Returns:

true if the node is currently animating.

getAnimator

public Animation getAnimator()

Gets the first Animation of the node.

Specified by:

getAnimator in interface AnimatingTree

Returns:

Animation which is the first Animation of the node.

setAnimateDrawing

public void setAnimateDrawing(boolean animateDrawing)

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).

Parameters:

animateDrawing - boolean flag to draw if animating.

addAnimator

public void addAnimator(Animation a)

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.

Specified by:

addAnimator in interface AnimatingTree

Parameters:

a - the Animation being added to the node.

isAnimateDrawing

public boolean isAnimateDrawing()

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).

Returns:

boolean flag to draw if animating.

makeInsertAnimation

protected void makeInsertAnimation(BSTTree insertNode,
                                   InsertBSTAnimation newAnimator)
                            throws java.lang.ClassCastException

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.

Parameters:

newAnimator - the InsertBSTAnimation to which the nodes are being added.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the tree.

makeSearchAnimation

protected void makeSearchAnimation(java.lang.Comparable keySearch,
                                   SearchBSTAnimation newAnimator)
                            throws java.lang.ClassCastException

Constructs the searchBSTAnimation down from the current node. This is a recursive call through the tree. No Listeners are affected by this call.

Parameters:

keySearch - the key being searched for.

newAnimator - the SerachBSTAnimation to which the nodes are being added.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the tree.

makeSelectionAnimation

protected void makeSelectionAnimation(int elementCount,
                                      SelectionBSTAnimation newAnimator)
                               throws java.lang.ClassCastException

Constructs the partitionBSTAnimation down from the current node. This is a recursive call through the tree. No Listeners are affected by this call.

Parameters:

elementCount - the integer (kth small element) searching for that partition

newAnimator - the PartitionBSTAnimation to which the nodes are being added.

Throws:

java.lang.ClassCastException - key cannot be compared with the keys currently in the tree.

animationEventPerformed

public void animationEventPerformed(AnimationEvent e)

Implements AnimationListener which requires the following method. The only status of animation it listens for is Animation.FINISH, to remove the animation from the animators list.

Specified by:

animationEventPerformed in interface AnimationListener

Parameters:

e - AnimationEvent that represents the information of the Animation.