edu.princeton.cs.algs4.growingtree.framework
Class MovingBSTTree<P extends NodeProperties>

java.lang.Object
  edu.princeton.cs.algs4.growingtree.framework.GrowingTreeNode<P>
      edu.princeton.cs.algs4.growingtree.framework.MovingBSTTree<P>

All Implemented Interfaces:

AnimatingTree<P>, AnimationListener, DrawingTree<P>, Tree<P>, java.util.EventListener

public class MovingBSTTree<P extends NodeProperties>
extends GrowingTreeNode<P>

The class provides the base structure for a BSTTree that can move to a new position in the Binary Search Tree. For that reason, it extends the BSTTree class.

The MovingBSTTree defines methods necessary to move a BSTTree from one location in a Binary Search Tree to another. Because the methods are moving, they require animation. Consequently, the extension must be from an AnimatingBSTTree. The constructor ensures this construction, however, changes cannot be made. To protect the changes from occuring, the methods have been overiden to have no affect.

Version:

2.2 9/15/01

Author:

Corey Sanders

Field Summary

static int	DOWN_LEFT Defines moving down and to the left.
static int	DOWN_RIGHT Defines moving down and to the right.
static int	FOLLOW_NODE Defines following the node passed as a follower.
static int	FOLLOW_PARENT_LEFT Defines following the parent as its left child.
static int	FOLLOW_PARENT_RIGHT Defines following the parent, as its right child.
static int	NULL_MOVEMENT Defines a null movement.
static int	UP_LEFT Defines moving up and to the left.
static int	UP_RIGHT Defines moving up and to the right.

Fields inherited from class edu.princeton.cs.algs4.growingtree.framework.GrowingTreeNode

ANIMATING_BST_TREE_TYPE, BST_TREE_TYPE, DRAWING_BST_TREE_TYPE

Constructor Summary

MovingBSTTree(GrowingTreeNode<P> node)
Constructor without a parent passed, indicating that FOLLOW_PARENT_LEFT and FOLLOW_PARENT_RIGHT are not accesible unless a parent is set.

MovingBSTTree(GrowingTreeNode<P> node, MovingBSTTree<P> movingParent)
Constructor with a parent passed.

Method Summary

void	drawFollowLeft(java.awt.Graphics2D g2) Draws the moving node in the given Graphics2D to follow its parent as if it were the left child.
void	drawFollowNode(java.awt.Graphics2D g2, double step) Draws the moving node in the given Graphics2D to follow the location of the imitating node.
void	drawFollowNode(java.awt.Graphics2D g2, double step, boolean bottomLinks) Draws the moving node in the given Graphics2D to follow the location of the imitating node.
void	drawFollowRight(java.awt.Graphics2D g2) Draws the moving node in the given Graphics2D to follow its parent as if it were the right child.
void	drawNodeAndLink(java.awt.Graphics2D g2, double step) Draws the node and link of the tree to the given Graphics2D.
int	getEndLevel() Gets the ending level for the moving of the node.
java.awt.geom.AffineTransform	getEndTransform() Gets the ending transform for the moving of the node.
int	getMovePosition() Gets the move position for the moving node.
MovingBSTTree<P>	getMovingParent() Gets the moving parent of the MovingBSTTree.
double	getMovingSectionHeight() Gets the section height for the drawing of the node.
GrowingTreeNode<P>	getNode() Gets the node that the MovingBSTTree is imitating.
int	getStartLevel() Gets the starting level for the moving of the node.
java.awt.geom.AffineTransform	getStartTransform() Gets the starting transform for the moving of the node.
void	initMovingBSTTree() Initiliazes the node with the move position defined within the node.
void	initMovingBSTTree(int movePosition) Initiliazes the node with the move position passed.
void	makeNode(java.awt.Graphics2D g2, double step) Sets the node of the tree in the given Graphics2D, by setting the AffineTransform.
void	setEndLevel(int endLevel) Sets the ending level for the moving of the node.
void	setEndTransform(java.awt.geom.AffineTransform endTransform) Sets the ending transform for the moving of the node.
void	setFollowLeftMovingTransform(java.awt.Graphics2D g2) Sets the current transform for a given following node.
void	setFollowNodeMovingTransform(java.awt.Graphics2D g2, double step) Sets the current transform for a given following node.
void	setFollowRightMovingTransform(java.awt.Graphics2D g2) Sets the current transform for a given following node.
void	setMovePosition(int m) Sets the move position for the moving node.
void	setMovingParent(MovingBSTTree<P> movingParent) Sets the moving parent of the MovingBSTTree.
void	setMovingSectionHeight(double height) Sets the section height for the drawing of the node.
void	setNode(GrowingTreeNode<P> node) Sets the node that the MovingBSTTree imitates.
void	setStartLevel(int startLevel) Sets the starting level for the moving of the node.
void	setStartTransform(java.awt.geom.AffineTransform startTransform) Sets the starting transform for the moving of the node.
void	setTreeType(int treeType) Sets the tree type for the BSTTree.

Methods inherited from class edu.princeton.cs.algs4.growingtree.framework.GrowingTreeNode

addAnimator, animationEventPerformed, compareTo, constructAnimatingBSTTree, constructBSTTree, constructDrawingBSTTree, delete, drawNode, drawNode, drawNode, drawNodeAndLeftLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndLink, drawNodeAndRightLink, eraseNodeAndLink, eraseNodeAndLink, getAnimator, getChildren, getCurrentGraphics, getCurrentPower2, getCurrentTransform, getDrawingLevel, getHead, getInorderCount, getKey, getLeftLinkColor, getLeftNodeInternal, getLevel, getMaxKeyWidth, getNodeProperties, getParentTree, getRightLinkColor, getRightNodeInternal, getRoot, getScreenBounds, getSectionHeight, getSettings, getShadowNode, getTreeType, getTreeTypeString, getValue, insertNode, inTree, isAnimateDrawing, isEmpty, isLeaf, isNodeAnimating, isSettingsSaved, restoreLeftSettings, restoreRightSettings, restoreSettings, restoreTransform, rotateLeftPointers, rotateRightPointers, rotateUp, saveLeftSettings, saveRightSettings, saveSettings, setAnimateDrawing, setCurrentGraphics, setNodeSettings, setScreenBounds, setSettings, size

Methods inherited from class java.lang.Object

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

Field Detail

NULL_MOVEMENT

public static final int NULL_MOVEMENT

Defines a null movement.

See Also:

Constant Field Values

DOWN_RIGHT

public static final int DOWN_RIGHT

Defines moving down and to the right.

See Also:

Constant Field Values

DOWN_LEFT

public static final int DOWN_LEFT

Defines moving down and to the left.

See Also:

Constant Field Values

UP_RIGHT

public static final int UP_RIGHT

Defines moving up and to the right.

See Also:

Constant Field Values

UP_LEFT

public static final int UP_LEFT

Defines moving up and to the left.

See Also:

Constant Field Values

FOLLOW_PARENT_RIGHT

public static final int FOLLOW_PARENT_RIGHT

Defines following the parent, as its right child.

See Also:

Constant Field Values

FOLLOW_PARENT_LEFT

public static final int FOLLOW_PARENT_LEFT

Defines following the parent as its left child.

See Also:

Constant Field Values

FOLLOW_NODE

public static final int FOLLOW_NODE

Defines following the node passed as a follower.

See Also:

Constant Field Values

Constructor Detail

MovingBSTTree

public MovingBSTTree(GrowingTreeNode<P> node)

Constructor without a parent passed, indicating that FOLLOW_PARENT_LEFT and FOLLOW_PARENT_RIGHT are not accesible unless a parent is set. The MovingBSTTree constructs as an empty ANIMATING_BST_TREE_TYPEM , setting the value and key as the value and key of the given node. The MovingBSTTree imitates the BSTTree node given but does not affect the node.

Parameters:

node - BSTTree node that the MovingBSTTree imitates.

MovingBSTTree

public MovingBSTTree(GrowingTreeNode<P> node,
                     MovingBSTTree<P> movingParent)

Constructor with a parent passed. The MovingBSTTree constructs as an empty ANIMATING_BST_TREE_TYPEM , setting the value and key as the value and key of the given node. The MovingBSTTree imitates the BSTTree node given but does not affect the node.

Parameters:

node - BSTTree node that the MovingBSTTree imitates.

movingParent - MovingBSTTree that is the parent of the current node, allowing the follow parent move positions.

Method Detail

getNode

public GrowingTreeNode<P> getNode()

Gets the node that the MovingBSTTree is imitating.

Returns:

BSTTree node that the MovingBSTTree is imitating.

getMovingParent

public MovingBSTTree<P> getMovingParent()

Gets the moving parent of the MovingBSTTree.

Returns:

MovingBSTTree parent .

getMovingSectionHeight

public double getMovingSectionHeight()

Gets the section height for the drawing of the node.

Returns:

double section height used for the moving node.

getStartTransform

public java.awt.geom.AffineTransform getStartTransform()

Gets the starting transform for the moving of the node.

Returns:

transform start for the MovingBSTTree.

getEndTransform

public java.awt.geom.AffineTransform getEndTransform()

Gets the ending transform for the moving of the node.

Returns:

ending transform for the MovingBSTTree.

getStartLevel

public int getStartLevel()

Gets the starting level for the moving of the node.

Returns:

starting level for the MovingBSTTree.

getEndLevel

public int getEndLevel()

Gets the ending level for the moving of the node.

Returns:

ending transform for the MovingBSTTree.

getMovePosition

public int getMovePosition()

Gets the move position for the moving node.

Returns:

integer representing a predefined move position.

setNode

public void setNode(GrowingTreeNode<P> node)

Sets the node that the MovingBSTTree imitates. The key and value are set according to the given node.

Parameters:

node - BSTTree node that the MovingBSTTree imitates.

setMovingParent

public void setMovingParent(MovingBSTTree<P> movingParent)

Sets the moving parent of the MovingBSTTree. After the parent is set, the movements FOLLOW_PARENT_RIGHT and FOLLOW_PARENT_LEFT are allowed.

Parameters:

movingParent - MovingBSTTree parent for the node.

setMovingSectionHeight

public void setMovingSectionHeight(double height)

Sets the section height for the drawing of the node. The section is very necessary in drawing a moving node, because the distance the node travels up or down is determined by the section height.

Parameters:

height - the section height used for the moving node.

setStartTransform

public void setStartTransform(java.awt.geom.AffineTransform startTransform)

Sets the starting transform for the moving of the node.

Parameters:

startTransform - starting transform for the MovingBSTTree.

setEndTransform

public void setEndTransform(java.awt.geom.AffineTransform endTransform)

Sets the ending transform for the moving of the node. This makes the moving node not initialize to the move position and instead use the end transform set here. To set the move position for initialization, use setMovePosition.

Parameters:

endTransform - ending transform for the MovingBSTTree.

setStartLevel

public void setStartLevel(int startLevel)

Sets the starting level for the moving of the node.

Parameters:

startLevel - starting level for the MovingBSTTree.

setEndLevel

public void setEndLevel(int endLevel)

Sets the ending level for the moving of the node. This makes the moving node not initialize to the move position and instead use the end level set here. To set the move position for initialization, use setMovePosition.

Parameters:

endLevel - ending transform for the MovingBSTTree.

setMovePosition

public void setMovePosition(int m)

Sets the move position for the moving node. Setting this forces initialization of the node when drawNodeAndLink is called.

Parameters:

m - integer representing a predefined move position.

setTreeType

public void setTreeType(int treeType)

Sets the tree type for the BSTTree. Overiden to disallow changes in AnimatingBSTTre.

Overrides:

setTreeType in class GrowingTreeNode<P extends NodeProperties>

Parameters:

treeType - setting for the tree (no affect).

makeNode

public void makeNode(java.awt.Graphics2D g2,
                     double step)

Sets the node of the tree in the given Graphics2D, by setting the AffineTransform. If the move position needs to be initialized, it is built within this method.

FOLLOW_PARENT_RIGHT, FOLLOW_PARENT_LEFT, and FOLLOW_NODE do not initialize but must be reconfigured every call to the method. The other movements are not changed after the first initlization.

Parameters:

g2 - graphics to which the node is drawn.

step - double value [0,1] which indicates the progress of the drawing.

drawNodeAndLink

public void drawNodeAndLink(java.awt.Graphics2D g2,
                            double step)

Draws the node and link of the tree to the given Graphics2D. If the move position needs to be initialized, it is built within this method.

FOLLOW_PARENT_RIGHT, FOLLOW_PARENT_LEFT, and FOLLOW_NODE do not initialize but must be reconfigured every call to the method. The other movements are not changed after the first initlization.

Parameters:

g2 - graphics to which the node is drawn.

step - double value [0,1] which indicates the progress of the drawing.

initMovingBSTTree

public void initMovingBSTTree(int movePosition)

Initiliazes the node with the move position passed.

Parameters:

movePostition - the move position set for the node and initialized to.

initMovingBSTTree

public void initMovingBSTTree()

Initiliazes the node with the move position defined within the node. The only move positions that need initialization are

• DOWN_RIGHT
• DOWN_LEFT
• UP_RIGHT
• UP_LEFT

drawFollowRight

public void drawFollowRight(java.awt.Graphics2D g2)

Draws the moving node in the given Graphics2D to follow its parent as if it were the right child. If the parent is not defined, the node is draw at its starting transform and level.

Parameters:

g2 - Graphics2D to which to node is drawn.

drawFollowLeft

public void drawFollowLeft(java.awt.Graphics2D g2)

Draws the moving node in the given Graphics2D to follow its parent as if it were the left child. If the parent is not defined, the node is draw at its starting transform and level.

Parameters:

g2 - Graphics2D to which to node is drawn.

drawFollowNode

public void drawFollowNode(java.awt.Graphics2D g2,
                           double step)

Draws the moving node in the given Graphics2D to follow the location of the imitating node. The step is necessary to determine the progress of the animation. The FOLLOW_NODE movement simply starts at the start transform and ends at the current transform of the imitating node.

Parameters:

g2 - Graphics2D to which to node is drawn.

step - double value [0,1] which indicates the progress of the drawing.

drawFollowNode

public void drawFollowNode(java.awt.Graphics2D g2,
                           double step,
                           boolean bottomLinks)

Draws the moving node in the given Graphics2D to follow the location of the imitating node. The step is necessary to determine the progress of the animation. The FOLLOW_NODE movement simply starts at the start transform and ends at the current transform of the imitating node.

Parameters:

g2 - Graphics2D to which to node is drawn.

step - double value [0,1] which indicates the progress of the drawing.

bottomLinks - boolean whether the bottom links should be drawn.

setFollowNodeMovingTransform

public void setFollowNodeMovingTransform(java.awt.Graphics2D g2,
                                         double step)

Sets the current transform for a given following node.

Parameters:

g2 - Graphics2D to which to node is drawn.

step - double value [0,1] which indicates the progress of the drawing.

setFollowRightMovingTransform

public void setFollowRightMovingTransform(java.awt.Graphics2D g2)

Sets the current transform for a given following node.

Parameters:

g2 - Graphics2D to which to node is drawn.

setFollowLeftMovingTransform

public void setFollowLeftMovingTransform(java.awt.Graphics2D g2)

Sets the current transform for a given following node.

Parameters:

g2 - Graphics2D to which to node is drawn.