Modifier and Type	Class and Description
public static class	TreeLayout.DumpConfiguration
private class	TreeLayout.NormalizedPosition The algorithm calculates the position starting with the root at 0.

Modifier and Type	Field and Description
private final Map<TreeNode, TreeNode>	ancestor
private double	boundsBottom
private double	boundsLeft
private double	boundsRight
private double	boundsTop
private final Map<TreeNode, Double>	change
private final Configuration<TreeNode>	configuration
private final Map<TreeNode, Double>	mod
private Map<TreeNode, Rectangle2D.Double>	nodeBounds
private final NodeExtentProvider<TreeNode>	nodeExtentProvider
private final Map<TreeNode, Integer>	number
private final Map<TreeNode, Point2D>	positions
private final Map<TreeNode, Double>	prelim
private final Map<TreeNode, Double>	shift
private final List<Double>	sizeOfLevel
private final Map<TreeNode, TreeNode>	thread
private final TreeForTreeLayout<TreeNode>	tree
private final boolean	useIdentity

Access	Constructor and Description
public	TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration, boolean [default: false] when true, identity ("==") is used instead of equality ("equals(...)") when checking nodes. Within a tree each node must only exist once (using this check). useIdentity) Creates a TreeLayout for a given tree.
public	TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration)

Method Summary

Modifier and Type	Method and Description
private void	addUniqueNodes(Map<TreeNode, TreeNode> nodes, TreeNode newNode)
private TreeNode	Returns: the greatest distinct ancestor of vIMinus and its right neighbor v ancestor(TreeNode vIMinus, TreeNode v, TreeNode parentOfV, TreeNode defaultAncestor)
private TreeNode	Returns: the (possibly changes) defaultAncestor apportion(TreeNode v, TreeNode defaultAncestor, TreeNode [nullable] the left sibling v, if there is any leftSibling, TreeNode the parent of v parentOfV) In difference to the original algorithm we also pass in the leftSibling and the parent of v. Why adding the parameter 'parent of v' (parentOfV) ?
private void	calcSizeOfLevels(TreeNode node, int level)
public void	checkTree() Check if the tree is a "valid" tree.
private void	dumpTree(PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)
public void	dumpTree(PrintStream printStream, TreeLayout.DumpConfiguration [default: new DumpConfiguration()] dumpConfiguration) Prints a dump of the tree to the given printStream, using the node's "toString" method.
public void	dumpTree(PrintStream printStream)
private void	executeShifts(TreeNode [!tree.isLeaf(v)] v)
private void	firstWalk(TreeNode v, TreeNode [nullable] the left sibling v, if there is any leftSibling) In difference to the original algorithm we also pass in the leftSibling (see `apportion(Object, Object, Object, Object)` for a motivation).
private TreeNode	getAncestor(TreeNode node)
public Rectangle2D	Returns: the bounds of the tree layout getBounds() Returns the bounds of the tree layout.
private double	getChange(TreeNode node)
public Configuration<TreeNode>	Returns: the Configuration used by this `TreeLayout` getConfiguration() Returns the Configuration used by this `TreeLayout`.
private double	Returns: the distance between node v and w getDistance(TreeNode v, TreeNode w) The distance of two nodes is the distance of the centers of both noded.
private int	getLevelChangeSign()
public int	Returns: [level > 0] getLevelCount() Returns the number of levels of the tree.
private double	getMod(TreeNode node)
public Map<TreeNode, Rectangle2D.Double>	Returns: maps each node of the tree to its bounds (position and size). getNodeBounds() Returns the layout of the tree nodes by mapping each node of the tree to its bounds (position and size).
public NodeExtentProvider<TreeNode>	Returns: the `NodeExtentProvider` used by this `TreeLayout` getNodeExtentProvider() Returns the `NodeExtentProvider` used by this `TreeLayout`.
private double	getNodeHeight(TreeNode node)
private double	getNodeSize(TreeNode treeNode) When the level changes in Y-axis (i.e. root location Top or Bottom) the width of a node is its size, otherwise the node's height is its size.
private double	getNodeThickness(TreeNode treeNode) When the level changes in Y-axis (i.e. root location Top or Bottom) the height of a node is its thickness, otherwise the node's width is its thickness.
private double	getNodeWidth(TreeNode node)
private int	getNumber(TreeNode [tree.isChildOfParent(node, parentNode)] node, TreeNode parent of node parentNode)
private double	getPrelim(TreeNode node)
private double	getShift(TreeNode node)
public double	Returns: the size of the level [level >= 0 && level < levelCount] getSizeOfLevel(int level) Returns the size of a level.
private TreeNode	getThread(TreeNode node)
public TreeForTreeLayout<TreeNode>	Returns: the Tree the layout is created for getTree() Returns the Tree the layout is created for.
private double	getWidthOrHeightOfNode(TreeNode treeNode, boolean returnWidth)
private boolean	isLevelChangeInYAxis()
private void	moveSubtree(TreeNode wMinus, TreeNode wPlus, TreeNode parent, double shift)
private TreeNode	nextLeft(TreeNode v)
private TreeNode	nextRight(TreeNode v)
private void	secondWalk(TreeNode v, double m, int level, double levelStart) In difference to the original algorithm we also pass in extra level information.
private void	setAncestor(TreeNode node, TreeNode ancestor)
private void	setChange(TreeNode node, double d)
private void	setMod(TreeNode node, double d)
private void	setPrelim(TreeNode node, double d)
private void	setShift(TreeNode node, double d)
private void	setThread(TreeNode node, TreeNode thread)
private void	updateBounds(TreeNode node, double centerX, double centerY)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

ancestor	back to summary
private final Map<TreeNode, TreeNode> ancestor

boundsBottom	back to summary
private double boundsBottom

boundsLeft	back to summary
private double boundsLeft

boundsRight	back to summary
private double boundsRight

boundsTop	back to summary
private double boundsTop

change	back to summary
private final Map<TreeNode, Double> change

configuration	back to summary
private final Configuration<TreeNode> configuration

mod	back to summary
private final Map<TreeNode, Double> mod

nodeBounds	back to summary
private Map<TreeNode, Rectangle2D.Double> nodeBounds

nodeExtentProvider	back to summary
private final NodeExtentProvider<TreeNode> nodeExtentProvider

number	back to summary
private final Map<TreeNode, Integer> number

positions	back to summary
private final Map<TreeNode, Point2D> positions

prelim	back to summary
private final Map<TreeNode, Double> prelim

shift	back to summary
private final Map<TreeNode, Double> shift

sizeOfLevel	back to summary
private final List<Double> sizeOfLevel

thread	back to summary
private final Map<TreeNode, TreeNode> thread

tree	back to summary
private final TreeForTreeLayout<TreeNode> tree

useIdentity	back to summary
private final boolean useIdentity

Constructor Detail

TreeLayout back to summary

TreeLayout	back to summary
public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration, boolean useIdentity) Creates a TreeLayout for a given tree. In addition to the tree the `NodeExtentProvider` and the `Configuration` must be given. Parameters tree:TreeForTreeLayout<TreeNode> nodeExtentProvider:NodeExtentProvider<TreeNode> configuration:Configuration<TreeNode> useIdentity:boolean [default: false] when true, identity ("==") is used instead of equality ("equals(...)") when checking nodes. Within a tree each node must only exist once (using this check).

public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration, boolean useIdentity)

Creates a TreeLayout for a given tree.

In addition to the tree the NodeExtentProvider and the Configuration must be given.

Parameters

tree:TreeForTreeLayout<TreeNode>
nodeExtentProvider:NodeExtentProvider<TreeNode>
configuration:Configuration<TreeNode>
useIdentity:boolean: [default: false] when true, identity ("==") is used instead of equality ("equals(...)") when checking nodes. Within a tree each node must only exist once (using this check).

TreeLayout	back to summary
public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration)

Method Detail

addUniqueNodes	back to summary
private void addUniqueNodes(Map<TreeNode, TreeNode> nodes, TreeNode newNode)

ancestor	back to summary
private TreeNode ancestor(TreeNode vIMinus, TreeNode v, TreeNode parentOfV, TreeNode defaultAncestor) Returns:TreeNode the greatest distinct ancestor of vIMinus and its right neighbor v

apportion back to summary

apportion	back to summary
private TreeNode apportion(TreeNode v, TreeNode defaultAncestor, TreeNode leftSibling, TreeNode parentOfV) In difference to the original algorithm we also pass in the leftSibling and the parent of v. Why adding the parameter 'parent of v' (parentOfV) ? In this method we need access to the parent of v. Not every tree implementation may support efficient (i.e. constant time) access to it. On the other hand the (only) caller of this method can provide this information with only constant extra time. Also we need access to the "left most sibling" of v. Not every tree implementation may support efficient (i.e. constant time) access to it. On the other hand the "left most sibling" of v is also the "first child" of the parent of v. The first child of a parent node we can get in constant time. As we got the parent of v we can so also get the "left most sibling" of v in constant time. Why adding the parameter 'leftSibling' ? In this method we need access to the "left sibling" of v. Not every tree implementation may support efficient (i.e. constant time) access to it. However it is easy for the caller of this method to provide this information with only constant extra time. In addition these extra parameters avoid the need for `TreeForTreeLayout` to include extra methods "getParent", "getLeftSibling", or "getLeftMostSibling". This keeps the interface `TreeForTreeLayout` small and avoids redundant implementations. Parameters leftSibling:TreeNode [nullable] the left sibling v, if there is any parentOfV:TreeNode the parent of v Returns:TreeNode the (possibly changes) defaultAncestor

private TreeNode apportion(TreeNode v, TreeNode defaultAncestor, TreeNode leftSibling, TreeNode parentOfV)

In difference to the original algorithm we also pass in the leftSibling and the parent of v.

Why adding the parameter 'parent of v' (parentOfV) ?

In this method we need access to the parent of v. Not every tree implementation may support efficient (i.e. constant time) access to it. On the other hand the (only) caller of this method can provide this information with only constant extra time.

Also we need access to the "left most sibling" of v. Not every tree implementation may support efficient (i.e. constant time) access to it. On the other hand the "left most sibling" of v is also the "first child" of the parent of v. The first child of a parent node we can get in constant time. As we got the parent of v we can so also get the "left most sibling" of v in constant time.

Why adding the parameter 'leftSibling' ?

In this method we need access to the "left sibling" of v. Not every tree implementation may support efficient (i.e. constant time) access to it. However it is easy for the caller of this method to provide this information with only constant extra time.

In addition these extra parameters avoid the need for TreeForTreeLayout to include extra methods "getParent", "getLeftSibling", or "getLeftMostSibling". This keeps the interface TreeForTreeLayout small and avoids redundant implementations.

Parameters

leftSibling:TreeNode: [nullable] the left sibling v, if there is any
parentOfV:TreeNode: the parent of v

Returns:TreeNode

the (possibly changes) defaultAncestor

calcSizeOfLevels	back to summary
private void calcSizeOfLevels(TreeNode node, int level)

checkTree	back to summary
public void checkTree() Check if the tree is a "valid" tree. Typically you will use this method during development when you get an unexpected layout from your trees. The following checks are performed: Each node must only occur once in the tree.

checkTree

back to summary

public void checkTree()

Check if the tree is a "valid" tree.

Typically you will use this method during development when you get an unexpected layout from your trees.

The following checks are performed:

Each node must only occur once in the tree.

dumpTree	back to summary
private void dumpTree(PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)

dumpTree	back to summary
public void dumpTree(PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration) Prints a dump of the tree to the given printStream, using the node's "toString" method. Parameters printStream:PrintStream dumpConfiguration:TreeLayout.DumpConfiguration [default: new DumpConfiguration()]

dumpTree

back to summary

public void dumpTree(PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration)

Prints a dump of the tree to the given printStream, using the node's "toString" method.

Parameters

printStream:PrintStream
dumpConfiguration:TreeLayout.DumpConfiguration: [default: new DumpConfiguration()]

dumpTree	back to summary
public void dumpTree(PrintStream printStream)

executeShifts	back to summary
private void executeShifts(TreeNode v) Parameters v:TreeNode [!tree.isLeaf(v)]

firstWalk back to summary

firstWalk	back to summary
private void firstWalk(TreeNode v, TreeNode leftSibling) In difference to the original algorithm we also pass in the leftSibling (see `apportion(Object, Object, Object, Object)` for a motivation). Parameters leftSibling:TreeNode [nullable] the left sibling v, if there is any

private void firstWalk(TreeNode v, TreeNode leftSibling)

In difference to the original algorithm we also pass in the leftSibling (see apportion(Object, Object, Object, Object) for a motivation).

Parameters

leftSibling:TreeNode: [nullable] the left sibling v, if there is any

getAncestor	back to summary
private TreeNode getAncestor(TreeNode node)

getBounds	back to summary
public Rectangle2D getBounds() Returns the bounds of the tree layout. The bounds of a TreeLayout is the smallest rectangle containing the bounds of all nodes in the layout. It always starts at (0,0). Returns:Rectangle2D the bounds of the tree layout

getBounds

back to summary

public Rectangle2D getBounds()

Returns the bounds of the tree layout.

The bounds of a TreeLayout is the smallest rectangle containing the bounds of all nodes in the layout. It always starts at (0,0).

Returns:Rectangle2D: the bounds of the tree layout

getChange	back to summary
private double getChange(TreeNode node)

getConfiguration back to summary

getConfiguration	back to summary
public Configuration<TreeNode> getConfiguration() Returns the Configuration used by this `TreeLayout`. Returns:Configuration<TreeNode> the Configuration used by this `TreeLayout`

public Configuration<TreeNode> getConfiguration()

Returns the Configuration used by this TreeLayout.

Returns:Configuration<TreeNode>: the Configuration used by this TreeLayout

getDistance	back to summary
private double getDistance(TreeNode v, TreeNode w) The distance of two nodes is the distance of the centers of both noded. I.e. the distance includes the gap between the nodes and half of the sizes of the nodes. Returns:double the distance between node v and w

getDistance

back to summary

private double getDistance(TreeNode v, TreeNode w)

The distance of two nodes is the distance of the centers of both noded.

I.e. the distance includes the gap between the nodes and half of the sizes of the nodes.

Returns:double: the distance between node v and w

getLevelChangeSign	back to summary
private int getLevelChangeSign()

getLevelCount	back to summary
public int getLevelCount() Returns the number of levels of the tree. Returns:int [level > 0]

getLevelCount

back to summary

public int getLevelCount()

Returns the number of levels of the tree.

Returns:int: [level > 0]

getMod	back to summary
private double getMod(TreeNode node)

getNodeBounds	back to summary
public Map<TreeNode, Rectangle2D.Double> getNodeBounds() Returns the layout of the tree nodes by mapping each node of the tree to its bounds (position and size). For each rectangle x and y will be >= 0. At least one rectangle will have an x == 0 and at least one rectangle will have an y == 0. Returns:Map<TreeNode, Rectangle2D.Double> maps each node of the tree to its bounds (position and size).

getNodeBounds

back to summary

public Map<TreeNode, Rectangle2D.Double> getNodeBounds()

Returns the layout of the tree nodes by mapping each node of the tree to its bounds (position and size).

For each rectangle x and y will be >= 0. At least one rectangle will have an x == 0 and at least one rectangle will have an y == 0.

Returns:Map<TreeNode, Rectangle2D.Double>: maps each node of the tree to its bounds (position and size).

getNodeExtentProvider back to summary

getNodeExtentProvider	back to summary
public NodeExtentProvider<TreeNode> getNodeExtentProvider() Returns the `NodeExtentProvider` used by this `TreeLayout`. Returns:NodeExtentProvider<TreeNode> the `NodeExtentProvider` used by this `TreeLayout`

public NodeExtentProvider<TreeNode> getNodeExtentProvider()

Returns the NodeExtentProvider used by this TreeLayout.

Returns:NodeExtentProvider<TreeNode>: the NodeExtentProvider used by this TreeLayout

getNodeHeight	back to summary
private double getNodeHeight(TreeNode node)

getNodeSize	back to summary
private double getNodeSize(TreeNode treeNode) When the level changes in Y-axis (i.e. root location Top or Bottom) the width of a node is its size, otherwise the node's height is its size. The size of a node is used when calculating the distance between two nodes.

getNodeSize

back to summary

private double getNodeSize(TreeNode treeNode)

When the level changes in Y-axis (i.e. root location Top or Bottom) the width of a node is its size, otherwise the node's height is its size.

The size of a node is used when calculating the distance between two nodes.

getNodeThickness	back to summary
private double getNodeThickness(TreeNode treeNode) When the level changes in Y-axis (i.e. root location Top or Bottom) the height of a node is its thickness, otherwise the node's width is its thickness. The thickness of a node is used when calculating the locations of the levels.

getNodeThickness

back to summary

private double getNodeThickness(TreeNode treeNode)

When the level changes in Y-axis (i.e. root location Top or Bottom) the height of a node is its thickness, otherwise the node's width is its thickness.

The thickness of a node is used when calculating the locations of the levels.

getNodeWidth	back to summary
private double getNodeWidth(TreeNode node)

getNumber	back to summary
private int getNumber(TreeNode node, TreeNode parentNode) Parameters node:TreeNode [tree.isChildOfParent(node, parentNode)] parentNode:TreeNode parent of node

getPrelim	back to summary
private double getPrelim(TreeNode node)

getShift	back to summary
private double getShift(TreeNode node)

getSizeOfLevel

back to summary

public double getSizeOfLevel(int level)

Returns the size of a level.

When the root is located at the top or bottom the size of a level is the maximal height of the nodes of that level. When the root is located at the left or right the size of a level is the maximal width of the nodes of that level.

Parameters

level:int

Returns:double

the size of the level [level >= 0 && level < levelCount]

getThread	back to summary
private TreeNode getThread(TreeNode node)

getTree

back to summary

public TreeForTreeLayout<TreeNode> getTree()

Returns the Tree the layout is created for.

Returns:TreeForTreeLayout<TreeNode>: the Tree the layout is created for

getWidthOrHeightOfNode	back to summary
private double getWidthOrHeightOfNode(TreeNode treeNode, boolean returnWidth)

isLevelChangeInYAxis	back to summary
private boolean isLevelChangeInYAxis()

moveSubtree	back to summary
private void moveSubtree(TreeNode wMinus, TreeNode wPlus, TreeNode parent, double shift)

nextLeft	back to summary
private TreeNode nextLeft(TreeNode v)

nextRight	back to summary
private TreeNode nextRight(TreeNode v)

secondWalk	back to summary
private void secondWalk(TreeNode v, double m, int level, double levelStart) In difference to the original algorithm we also pass in extra level information.

setAncestor	back to summary
private void setAncestor(TreeNode node, TreeNode ancestor)

setChange	back to summary
private void setChange(TreeNode node, double d)

setMod	back to summary
private void setMod(TreeNode node, double d)

setPrelim	back to summary
private void setPrelim(TreeNode node, double d)

setShift	back to summary
private void setShift(TreeNode node, double d)

setThread	back to summary
private void setThread(TreeNode node, TreeNode thread)

updateBounds	back to summary
private void updateBounds(TreeNode node, double centerX, double centerY)

org.abego.treelayout back to summary

public Class TreeLayout.DumpConfiguration

Class Inheritance

extends Object

java.lang.Object
org.abego.treelayout.TreeLayout.DumpConfiguration

Field Summary

Modifier and Type	Field and Description
public final boolean	includeNodeSize When true the dump also includes the size of each node, otherwise not.
public final boolean	includeObjectToString When true, the text as returned by `Object#toString()`, is included in the dump, in addition to the text returned by the possibly overridden toString method of the node.
public final String	indent The text used to indent the output per level.

Constructor Summary

Access	Constructor and Description
public	DumpConfiguration(String [default: " "] indent, boolean [default: false] includeNodeSize, boolean [default: false] includePointer)
public	DumpConfiguration()

Method Summary

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

includeNodeSize	back to summary
public final boolean includeNodeSize When true the dump also includes the size of each node, otherwise not.

includeObjectToString	back to summary
public final boolean includeObjectToString When true, the text as returned by `Object#toString()`, is included in the dump, in addition to the text returned by the possibly overridden toString method of the node. When the hashCode method is overridden the output will also include the "identityHashCode".

indent	back to summary
public final String indent The text used to indent the output per level.

Constructor Detail

DumpConfiguration	back to summary
public DumpConfiguration(String indent, boolean includeNodeSize, boolean includePointer) Parameters indent:String [default: " "] includeNodeSize:boolean [default: false] includePointer:boolean [default: false]

DumpConfiguration	back to summary
public DumpConfiguration()

org.abego.treelayout back to summary

private Class TreeLayout.NormalizedPosition

Class Inheritance

extends Point2D

java.lang.Object
java.awt.geom.Point2D
org.abego.treelayout.TreeLayout.NormalizedPosition

The algorithm calculates the position starting with the root at 0. I.e. the left children will get negative positions. However we want the result to be normalized to (0,0).

NormalizedPosition will normalize the position (given relative to the root position), taking the current bounds into account. This way the left most node bounds will start at x = 0, the top most node bounds at y = 0.

Field Summary

Modifier and Type	Field and Description
private double	x_relativeToRoot
private double	y_relativeToRoot

Constructor Summary

Access	Constructor and Description
public	NormalizedPosition(double x_relativeToRoot, double y_relativeToRoot)

Method Summary

Modifier and Type	Method and Description
public double	getX() Implements abstract java.awt.geom.Point2D.getX. Returns the X coordinate of this `Point2D` in `double` precision.
public double	getY() Implements abstract java.awt.geom.Point2D.getY. Returns the Y coordinate of this `Point2D` in `double` precision.
public void	setLocation(double the new X coordinate of this `Point2D` x_relativeToRoot, double the new Y coordinate of this `Point2D` y_relativeToRoot) Implements abstract java.awt.geom.Point2D.setLocation. Sets the location of this `Point2D` to the specified `double` coordinates.