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

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

Type Parameters:

P - NodeProperties subclass that parameterizes the tree

All Implemented Interfaces:

IAlgorithmNode<P>, IDeletingNode<P>, IInsertingNode<P>, INode<P>, ISearchingNode<P>, java.lang.Comparable<INode<P>>

public class ShadowNode<P extends NodeProperties>
extends java.lang.Object
implements IInsertingNode<P>, ISearchingNode<P>, IDeletingNode<P>

This class defines the nodes that interact directly with the operators defined by the client. Primitives such as rotation happen synchronously within the tree composed of these nodes, whereas they occur asynchronously within the GrowingTreeNode tree. Operators receive instances of these objects, though they are cast to the appropriate interface. When an operator calls a primitive, such as rotateLeft, it passed along to the GrowingTreeNode associated with this ShadowNode, so that the animation can be queued up.

Author:

Josh Israel

Field Summary

IExperimentLogger<P>

logger

Constructor Summary

ShadowNode(double key, P np, ExperimentTree<P> et)

ShadowNode(GrowingTreeNode<P> node, P np)

ShadowNode(GrowingTreeNode<P> node, P np, IExperimentLogger<P> logger)

Method Summary

int	compareTo(java.lang.Double other)
int	compareTo(INode<P> other)
void	freeze()
void	freeze(double lengthMult) Freezes the animation briefly and displays the current state of the tree.
GrowingTreeNode<P>	getGrowingNode()
java.lang.Double	getKey()
ShadowNode<P>	getLeft()
IExperimentLogger<P>	getLogger()
P	getNodeProperties()
ShadowNode<P>	getParent()
ShadowNode<P>	getPredecessor()
ShadowNode<P>	getRight()
ShadowNode<P>	getRoot()
ShadowNode<P>	getSuccessor()
ShadowNode<P>	insertLeft(INode<P> n) This should only be called once per call to IInsertOperator.doInsert
ShadowNode<P>	insertRight(INode<P> n) This should only be called once per call to IInsertOperator.doInsert
boolean	isBST()
void	markFound() This must be called on the node being sought in order to trigger the search animation.
ShadowNode<P>	predecessorHibbardDelete() Identical to successorHibbardDelete, except swaps with predecessor.
ShadowNode<P>	rotateLeft() Rotates the left child up.
ShadowNode<P>	rotateRight() Rotates the right child up.
ShadowNode<P>	successorHibbardDelete() This performs Hibbard deletion.

Methods inherited from class java.lang.Object

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

Field Detail

logger

public IExperimentLogger<P extends NodeProperties> logger

Constructor Detail

ShadowNode

public ShadowNode(GrowingTreeNode<P> node,
                  P np)

ShadowNode

public ShadowNode(GrowingTreeNode<P> node,
                  P np,
                  IExperimentLogger<P> logger)

ShadowNode

public ShadowNode(double key,
                  P np,
                  ExperimentTree<P> et)

Method Detail

getKey

public java.lang.Double getKey()

getGrowingNode

public GrowingTreeNode<P> getGrowingNode()

getLogger

public IExperimentLogger<P> getLogger()

Specified by:

getLogger in interface INode<P extends NodeProperties>

getRight

public ShadowNode<P> getRight()

Specified by:

getRight in interface IAlgorithmNode<P extends NodeProperties>

Specified by:

getRight in interface IInsertingNode<P extends NodeProperties>

Specified by:

getRight in interface ISearchingNode<P extends NodeProperties>

getLeft

public ShadowNode<P> getLeft()

Specified by:

getLeft in interface IAlgorithmNode<P extends NodeProperties>

Specified by:

getLeft in interface IInsertingNode<P extends NodeProperties>

Specified by:

getLeft in interface ISearchingNode<P extends NodeProperties>

getParent

public ShadowNode<P> getParent()

Specified by:

getParent in interface IAlgorithmNode<P extends NodeProperties>

Specified by:

getParent in interface IInsertingNode<P extends NodeProperties>

Specified by:

getParent in interface ISearchingNode<P extends NodeProperties>

getRoot

public ShadowNode<P> getRoot()

Specified by:

getRoot in interface IAlgorithmNode<P extends NodeProperties>

compareTo

public int compareTo(INode<P> other)

Specified by:

compareTo in interface java.lang.Comparable<INode<P extends NodeProperties>>

compareTo

public int compareTo(java.lang.Double other)

getNodeProperties

public P getNodeProperties()

Specified by:

getNodeProperties in interface INode<P extends NodeProperties>

rotateLeft

public ShadowNode<P> rotateLeft()

Description copied from interface: IAlgorithmNode

Rotates the left child up.

Specified by:

rotateLeft in interface IAlgorithmNode<P extends NodeProperties>

Specified by:

rotateLeft in interface IInsertingNode<P extends NodeProperties>

Returns:

The new parent of the node (the former left child).

rotateRight

public ShadowNode<P> rotateRight()

Description copied from interface: IAlgorithmNode

Rotates the right child up.

Specified by:

rotateRight in interface IAlgorithmNode<P extends NodeProperties>

Specified by:

rotateRight in interface IInsertingNode<P extends NodeProperties>

Returns:

The new parent of the node (the former right child).

insertLeft

public ShadowNode<P> insertLeft(INode<P> n)

Description copied from interface: IInsertingNode

This should only be called once per call to IInsertOperator.doInsert

Specified by:

insertLeft in interface IInsertingNode<P extends NodeProperties>

Parameters:

n - Node to be inserted as the left child of this one. It should not be any node other than the newNode argument to IInsertOperator.doInsert

Returns:

The node just inserted into the tree

insertRight

public ShadowNode<P> insertRight(INode<P> n)

Description copied from interface: IInsertingNode

This should only be called once per call to IInsertOperator.doInsert

Specified by:

insertRight in interface IInsertingNode<P extends NodeProperties>

Parameters:

n - Node to be inserted as the left child of this one. It should not be any node other than the newNode argument to IInsertOperator.doInsert

Returns:

The node just inserted into the tree

getSuccessor

public ShadowNode<P> getSuccessor()

Specified by:

getSuccessor in interface IAlgorithmNode<P extends NodeProperties>

getPredecessor

public ShadowNode<P> getPredecessor()

Specified by:

getPredecessor in interface IAlgorithmNode<P extends NodeProperties>

successorHibbardDelete

public ShadowNode<P> successorHibbardDelete()

Description copied from interface: IDeletingNode

This performs Hibbard deletion. There are 3 cases: If the node is a leaf, it is simply removed. If the node has 1 child, it is replaced by its child If the node has 2 children, it is swapped with its successor and then deleted as a node with 1 child or a leaf.

Specified by:

successorHibbardDelete in interface IDeletingNode<P extends NodeProperties>

Returns:

If a leaf, null. If it has 1 child, returns its child. If it has 2 children, the child of the successor.

predecessorHibbardDelete

public ShadowNode<P> predecessorHibbardDelete()

Description copied from interface: IDeletingNode

Identical to successorHibbardDelete, except swaps with predecessor.

Specified by:

predecessorHibbardDelete in interface IDeletingNode<P extends NodeProperties>

Returns:

If a leaf, null. If it has 1 child, returns its child. If it has 2 children, the child of the predecessor.

markFound

public void markFound()

Description copied from interface: ISearchingNode

This must be called on the node being sought in order to trigger the search animation.

Specified by:

markFound in interface ISearchingNode<P extends NodeProperties>

isBST

public boolean isBST()

freeze

public void freeze()

Specified by:

freeze in interface IAlgorithmNode<P extends NodeProperties>

freeze

public void freeze(double lengthMult)

Description copied from interface: IAlgorithmNode

Freezes the animation briefly and displays the current state of the tree. This allows states between events like rotations to be displayed.

Specified by:

freeze in interface IAlgorithmNode<P extends NodeProperties>