Class TreeLayout<TreeNode>
- Type Parameters:
TreeNode
- Type of elements used as nodes in the tree
The nodes with their final layout can be retrieved through
getNodeBounds()
.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
private class
The algorithm calculates the position starting with the root at 0. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate double
private double
private double
private double
private final Configuration<TreeNode>
private Map<TreeNode,
Rectangle2D.Double> private final NodeExtentProvider<TreeNode>
private final TreeForTreeLayout<TreeNode>
private final boolean
-
Constructor Summary
ConstructorsConstructorDescriptionTreeLayout
(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
Modifier and TypeMethodDescriptionprivate void
addUniqueNodes
(Map<TreeNode, TreeNode> nodes, TreeNode newNode) private TreeNode
private TreeNode
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
Check if the tree is a "valid" tree.void
dumpTree
(PrintStream printStream) void
dumpTree
(PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration) Prints a dump of the tree to the given printStream, using the node's "toString" method.private void
dumpTree
(PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration) private void
private void
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) Returns the bounds of the tree layout.private double
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
int
Returns the number of levels of the tree.private double
Returns the layout of the tree nodes by mapping each node of the tree to its bounds (position and size).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
private double
private double
double
getSizeOfLevel
(int level) Returns the size of a level.private TreeNode
getTree()
Returns the Tree the layout is created for.private double
getWidthOrHeightOfNode
(TreeNode treeNode, boolean returnWidth) private boolean
private void
moveSubtree
(TreeNode wMinus, TreeNode wPlus, TreeNode parent, double shift) private TreeNode
private TreeNode
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
private void
private void
private void
private void
private void
updateBounds
(TreeNode node, double centerX, double centerY)
-
Field Details
-
tree
-
nodeExtentProvider
-
configuration
-
boundsLeft
private double boundsLeft -
boundsRight
private double boundsRight -
boundsTop
private double boundsTop -
boundsBottom
private double boundsBottom -
sizeOfLevel
-
useIdentity
private final boolean useIdentity -
mod
-
thread
-
prelim
-
change
-
shift
-
ancestor
-
number
-
positions
-
nodeBounds
-
-
Constructor Details
-
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 Details
-
getTree
Returns the Tree the layout is created for.- Returns:
- the Tree the layout is created for
-
getNodeExtentProvider
Returns theNodeExtentProvider
used by thisTreeLayout
.- Returns:
- the
NodeExtentProvider
used by thisTreeLayout
-
getNodeHeight
-
getNodeWidth
-
getWidthOrHeightOfNode
-
getNodeThickness
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
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
Returns the Configuration used by thisTreeLayout
.- Returns:
- the Configuration used by this
TreeLayout
-
isLevelChangeInYAxis
private boolean isLevelChangeInYAxis() -
getLevelChangeSign
private int getLevelChangeSign() -
updateBounds
-
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
-
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
-
setMod
-
getThread
-
setThread
-
getAncestor
-
setAncestor
-
getPrelim
-
setPrelim
-
getChange
-
setChange
-
getShift
-
setShift
-
getDistance
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
-
nextLeft
-
nextRight
-
getNumber
- 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
-
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
- Parameters:
v
- [!tree.isLeaf(v)]
-
firstWalk
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
In difference to the original algorithm we also pass in extra level information.- Parameters:
v
-m
-level
-levelStart
-
-
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
-
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(PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration) -
dumpTree
Prints a dump of the tree to the given printStream, using the node's "toString" method.- Parameters:
printStream
-dumpConfiguration
- [default: new DumpConfiguration()]
-
dumpTree
-