TreeNode
- Type of elements used as nodes in the treepublic class TreeLayout<TreeNode>
extends java.lang.Object
The nodes with their final layout can be retrieved through
getNodeBounds()
.
Modifier and Type | Class and Description |
---|---|
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 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 and 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.
|
Modifier and Type | Method and 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
(see
apportion(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 this
TreeLayout . |
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 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.
|
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) |
private final TreeForTreeLayout<TreeNode> tree
private final NodeExtentProvider<TreeNode> nodeExtentProvider
private final Configuration<TreeNode> configuration
private double boundsLeft
private double boundsRight
private double boundsTop
private double boundsBottom
private final java.util.List<java.lang.Double> sizeOfLevel
private final boolean useIdentity
private final java.util.Map<TreeNode,java.lang.Double> mod
private final java.util.Map<TreeNode,java.lang.Double> prelim
private final java.util.Map<TreeNode,java.lang.Double> change
private final java.util.Map<TreeNode,java.lang.Double> shift
private final java.util.Map<TreeNode,java.lang.Integer> number
private final java.util.Map<TreeNode,java.awt.geom.Point2D> positions
private java.util.Map<TreeNode,java.awt.geom.Rectangle2D.Double> nodeBounds
public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration, boolean useIdentity)
In addition to the tree the NodeExtentProvider
and the
Configuration
must be given.
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).public TreeLayout(TreeForTreeLayout<TreeNode> tree, NodeExtentProvider<TreeNode> nodeExtentProvider, Configuration<TreeNode> configuration)
public TreeForTreeLayout<TreeNode> getTree()
public NodeExtentProvider<TreeNode> getNodeExtentProvider()
NodeExtentProvider
used by this TreeLayout
.NodeExtentProvider
used by this TreeLayout
private double getNodeHeight(TreeNode node)
private double getNodeWidth(TreeNode node)
private double getWidthOrHeightOfNode(TreeNode treeNode, boolean returnWidth)
private double getNodeThickness(TreeNode treeNode)
The thickness of a node is used when calculating the locations of the levels.
treeNode
- private double getNodeSize(TreeNode treeNode)
The size of a node is used when calculating the distance between two nodes.
treeNode
- public Configuration<TreeNode> getConfiguration()
TreeLayout
.TreeLayout
private boolean isLevelChangeInYAxis()
private int getLevelChangeSign()
private void updateBounds(TreeNode node, double centerX, double centerY)
public java.awt.geom.Rectangle2D getBounds()
The bounds of a TreeLayout is the smallest rectangle containing the bounds of all nodes in the layout. It always starts at (0,0).
private void calcSizeOfLevels(TreeNode node, int level)
public int getLevelCount()
public double getSizeOfLevel(int 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.
level
- private double getMod(TreeNode node)
private void setMod(TreeNode node, double d)
private double getPrelim(TreeNode node)
private void setPrelim(TreeNode node, double d)
private double getChange(TreeNode node)
private void setChange(TreeNode node, double d)
private double getShift(TreeNode node)
private void setShift(TreeNode node, double d)
private double getDistance(TreeNode v, TreeNode w)
I.e. the distance includes the gap between the nodes and half of the sizes of the nodes.
v
- w
- private int getNumber(TreeNode node, TreeNode parentNode)
node
- [tree.isChildOfParent(node, parentNode)]parentNode
- parent of nodeprivate TreeNode ancestor(TreeNode vIMinus, TreeNode v, TreeNode parentOfV, TreeNode defaultAncestor)
vIMinus
- v
- parentOfV
- defaultAncestor
- private void moveSubtree(TreeNode wMinus, TreeNode wPlus, TreeNode parent, double shift)
private TreeNode apportion(TreeNode v, TreeNode defaultAncestor, TreeNode leftSibling, TreeNode parentOfV)
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.
v
- defaultAncestor
- leftSibling
- [nullable] the left sibling v, if there is anyparentOfV
- the parent of vprivate void executeShifts(TreeNode v)
v
- [!tree.isLeaf(v)]private void firstWalk(TreeNode v, TreeNode leftSibling)
apportion(Object, Object, Object, Object)
for a
motivation).v
- leftSibling
- [nullable] the left sibling v, if there is anyprivate void secondWalk(TreeNode v, double m, int level, double levelStart)
v
- m
- level
- levelStart
- public java.util.Map<TreeNode,java.awt.geom.Rectangle2D.Double> getNodeBounds()
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.
private void addUniqueNodes(java.util.Map<TreeNode,TreeNode> nodes, TreeNode newNode)
public void checkTree()
Typically you will use this method during development when you get an unexpected layout from your trees.
The following checks are performed:
private void dumpTree(java.io.PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)
public void dumpTree(java.io.PrintStream printStream, TreeLayout.DumpConfiguration dumpConfiguration)
printStream
- dumpConfiguration
- [default: new DumpConfiguration()]public void dumpTree(java.io.PrintStream printStream)