Class TreeLayout<TreeNode>
- java.lang.Object
-
- org.abego.treelayout.TreeLayout<TreeNode>
-
- Type Parameters:
TreeNode
- Type of elements used as nodes in the tree
public class TreeLayout<TreeNode> extends java.lang.Object
Implements the actual tree layout algorithm.The nodes with their final layout can be retrieved through
See this summary to get an overview how to use TreeLayout.getNodeBounds()
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
TreeLayout.DumpConfiguration
private class
TreeLayout.NormalizedPosition
The algorithm calculates the position starting with the root at 0.
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<TreeNode,TreeNode>
ancestor
private double
boundsBottom
private double
boundsLeft
private double
boundsRight
private double
boundsTop
private java.util.Map<TreeNode,java.lang.Double>
change
private Configuration<TreeNode>
configuration
private java.util.Map<TreeNode,java.lang.Double>
mod
private java.util.Map<TreeNode,java.awt.geom.Rectangle2D.Double>
nodeBounds
private NodeExtentProvider<TreeNode>
nodeExtentProvider
private java.util.Map<TreeNode,java.lang.Integer>
number
private java.util.Map<TreeNode,java.awt.geom.Point2D>
positions
private java.util.Map<TreeNode,java.lang.Double>
prelim
private java.util.Map<TreeNode,java.lang.Double>
shift
private java.util.List<java.lang.Double>
sizeOfLevel
private java.util.Map<TreeNode,TreeNode>
thread
private TreeForTreeLayout<TreeNode>
tree
private boolean
useIdentity
-
Constructor Summary
Constructors Constructor Description TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration)
TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration, boolean useIdentity)
Creates a TreeLayout for a given tree.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addUniqueNodes(java.util.Map<TreeNode,TreeNode> nodes, TreeNode newNode)
private TreeNode
ancestor(TreeNode vIMinus, TreeNode v, TreeNode parentOfV, TreeNode 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.private void
calcSizeOfLevels(TreeNode node, int level)
void
checkTree()
Check if the tree is a "valid" tree.void
dumpTree(java.io.PrintStream printStream)
void
dumpTree(java.io.PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration)
Prints a dump of the tree to the given printStream, using the node's "toString" method.private void
dumpTree(java.io.PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)
private void
executeShifts(TreeNode v)
private void
firstWalk(TreeNode v, TreeNode leftSibling)
In difference to the original algorithm we also pass in the leftSibling (seeapportion(Object, Object, Object, Object)
for a motivation).private TreeNode
getAncestor(TreeNode node)
java.awt.geom.Rectangle2D
getBounds()
Returns the bounds of the tree layout.private double
getChange(TreeNode node)
Configuration<TreeNode>
getConfiguration()
Returns the Configuration used by thisTreeLayout
.private double
getDistance(TreeNode v, TreeNode w)
The distance of two nodes is the distance of the centers of both noded.private int
getLevelChangeSign()
int
getLevelCount()
Returns the number of levels of the tree.private double
getMod(TreeNode node)
java.util.Map<TreeNode,java.awt.geom.Rectangle2D.Double>
getNodeBounds()
Returns the layout of the tree nodes by mapping each node of the tree to its bounds (position and size).NodeExtentProvider<TreeNode>
getNodeExtentProvider()
Returns theNodeExtentProvider
used by thisTreeLayout
.private double
getNodeHeight(TreeNode node)
private double
getNodeSize(TreeNode treeNode)
When the level changes in Y-axis (i.e.private double
getNodeThickness(TreeNode treeNode)
When the level changes in Y-axis (i.e.private double
getNodeWidth(TreeNode node)
private int
getNumber(TreeNode node, TreeNode parentNode)
private double
getPrelim(TreeNode node)
private double
getShift(TreeNode node)
double
getSizeOfLevel(int level)
Returns the size of a level.private TreeNode
getThread(TreeNode node)
TreeForTreeLayout<TreeNode>
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)
-
-
-
Field Detail
-
tree
private final TreeForTreeLayout<TreeNode> tree
-
nodeExtentProvider
private final NodeExtentProvider<TreeNode> nodeExtentProvider
-
configuration
private final Configuration<TreeNode> configuration
-
boundsLeft
private double boundsLeft
-
boundsRight
private double boundsRight
-
boundsTop
private double boundsTop
-
boundsBottom
private double boundsBottom
-
sizeOfLevel
private final java.util.List<java.lang.Double> sizeOfLevel
-
useIdentity
private final boolean useIdentity
-
mod
private final java.util.Map<TreeNode,java.lang.Double> mod
-
prelim
private final java.util.Map<TreeNode,java.lang.Double> prelim
-
change
private final java.util.Map<TreeNode,java.lang.Double> change
-
shift
private final java.util.Map<TreeNode,java.lang.Double> shift
-
number
private final java.util.Map<TreeNode,java.lang.Integer> number
-
positions
private final java.util.Map<TreeNode,java.awt.geom.Point2D> positions
-
nodeBounds
private java.util.Map<TreeNode,java.awt.geom.Rectangle2D.Double> nodeBounds
-
-
Constructor Detail
-
TreeLayout
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 theConfiguration
must be given.- Parameters:
tree
-nodeExtentProvider
-configuration
-useIdentity
- [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
public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration)
-
-
Method Detail
-
getTree
public TreeForTreeLayout<TreeNode> getTree()
Returns the Tree the layout is created for.- Returns:
- the Tree the layout is created for
-
getNodeExtentProvider
public NodeExtentProvider<TreeNode> getNodeExtentProvider()
Returns theNodeExtentProvider
used by thisTreeLayout
.- Returns:
- the
NodeExtentProvider
used by thisTreeLayout
-
getNodeHeight
private double getNodeHeight(TreeNode node)
-
getNodeWidth
private double getNodeWidth(TreeNode node)
-
getWidthOrHeightOfNode
private double getWidthOrHeightOfNode(TreeNode treeNode, boolean returnWidth)
-
getNodeThickness
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.
- Parameters:
treeNode
-- Returns:
-
getNodeSize
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.
- Parameters:
treeNode
-- Returns:
-
getConfiguration
public Configuration<TreeNode> getConfiguration()
Returns the Configuration used by thisTreeLayout
.- Returns:
- the Configuration used by this
TreeLayout
-
isLevelChangeInYAxis
private boolean isLevelChangeInYAxis()
-
getLevelChangeSign
private int getLevelChangeSign()
-
updateBounds
private void updateBounds(TreeNode node, double centerX, double centerY)
-
getBounds
public java.awt.geom.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:
- the bounds of the tree layout
-
calcSizeOfLevels
private void calcSizeOfLevels(TreeNode node, int level)
-
getLevelCount
public int getLevelCount()
Returns the number of levels of the tree.- Returns:
- [level > 0]
-
getSizeOfLevel
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
-- Returns:
- the size of the level [level >= 0 && level < levelCount]
-
getMod
private double getMod(TreeNode node)
-
setMod
private void setMod(TreeNode node, double d)
-
getPrelim
private double getPrelim(TreeNode node)
-
setPrelim
private void setPrelim(TreeNode node, double d)
-
getChange
private double getChange(TreeNode node)
-
setChange
private void setChange(TreeNode node, double d)
-
getShift
private double getShift(TreeNode node)
-
setShift
private void setShift(TreeNode node, double d)
-
getDistance
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.
- Parameters:
v
-w
-- Returns:
- the distance between node v and w
-
getNumber
private int getNumber(TreeNode node, TreeNode parentNode)
- Parameters:
node
- [tree.isChildOfParent(node, parentNode)]parentNode
- parent of node- Returns:
-
ancestor
private TreeNode ancestor(TreeNode vIMinus, TreeNode v, TreeNode parentOfV, TreeNode defaultAncestor)
- Parameters:
vIMinus
-v
-parentOfV
-defaultAncestor
-- Returns:
- the greatest distinct ancestor of vIMinus and its right neighbor v
-
moveSubtree
private void moveSubtree(TreeNode wMinus, TreeNode wPlus, TreeNode parent, double shift)
-
apportion
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 interfaceTreeForTreeLayout
small and avoids redundant implementations.- Parameters:
v
-defaultAncestor
-leftSibling
- [nullable] the left sibling v, if there is anyparentOfV
- the parent of v- Returns:
- the (possibly changes) defaultAncestor
-
executeShifts
private void executeShifts(TreeNode v)
- Parameters:
v
- [!tree.isLeaf(v)]
-
firstWalk
private void firstWalk(TreeNode v, TreeNode leftSibling)
In difference to the original algorithm we also pass in the leftSibling (seeapportion(Object, Object, Object, Object)
for a motivation).- Parameters:
v
-leftSibling
- [nullable] the left sibling v, if there is any
-
secondWalk
private void secondWalk(TreeNode v, double m, int level, double levelStart)
In difference to the original algorithm we also pass in extra level information.- Parameters:
v
-m
-level
-levelStart
-
-
getNodeBounds
public java.util.Map<TreeNode,java.awt.geom.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:
- maps each node of the tree to its bounds (position and size).
-
addUniqueNodes
private void addUniqueNodes(java.util.Map<TreeNode,TreeNode> nodes, TreeNode newNode)
-
checkTree
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
private void dumpTree(java.io.PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)
-
dumpTree
public void dumpTree(java.io.PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration)
Prints a dump of the tree to the given printStream, using the node's "toString" method.- Parameters:
printStream
-dumpConfiguration
- [default: new DumpConfiguration()]
-
dumpTree
public void dumpTree(java.io.PrintStream printStream)
-
-