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 Object
Implements the actual tree layout algorithm.

The nodes with their final layout can be retrieved through getNodeBounds().

See this summary to get an overview how to use TreeLayout.
  • Field Details

  • Constructor Details

  • Method Details

    • 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 the NodeExtentProvider used by this TreeLayout.
      Returns:
      the NodeExtentProvider used by this TreeLayout
    • 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 this TreeLayout.
      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 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)
    • getThread

      private TreeNode getThread(TreeNode node)
    • setThread

      private void setThread(TreeNode node, TreeNode thread)
    • getAncestor

      private TreeNode getAncestor(TreeNode node)
    • setAncestor

      private void setAncestor(TreeNode node, TreeNode ancestor)
    • 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
    • nextLeft

      private TreeNode nextLeft(TreeNode v)
    • nextRight

      private TreeNode nextRight(TreeNode v)
    • 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 interface TreeForTreeLayout small and avoids redundant implementations.

      Parameters:
      v -
      defaultAncestor -
      leftSibling - [nullable] the left sibling v, if there is any
      parentOfV - 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 (see apportion(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 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:
      maps each node of the tree to its bounds (position and size).
    • addUniqueNodes

      private void addUniqueNodes(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(PrintStream output, TreeNode node, int indent, TreeLayout.DumpConfiguration dumpConfiguration)
    • dumpTree

      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 -  
      dumpConfiguration - [default: new DumpConfiguration()]
    • dumpTree

      public void dumpTree(PrintStream printStream)