Package org.abego.treelayout

Class 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 getNodeBounds().

    See this summary to get an overview how to use TreeLayout.

    • Field Detail

      • 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

    • Method Detail

      • getTree

        public TreeForTreeLayout<TreeNode> getTree()
        Returns the Tree the layout is created for.
        Returns:
        the Tree the layout is created for

      • 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:

      • 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

      • 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 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).

      • 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

        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)