Package com.macrofocus.hierarchy

Class AbstractHierarchy<T>

  • All Implemented Interfaces:
    Hierarchy<T>, java.io.Serializable
    Direct Known Subclasses:
    SimpleHierarchy
    public abstract class AbstractHierarchy<T>
extends java.lang.Object
implements Hierarchy<T>
    This class provides a skeletal implementation of the Hierarchy interface to minimize the effort required to implement this interface.
    See Also:
    Serialized Form

    • Constructor Detail

      • AbstractHierarchy

        public AbstractHierarchy()

    • Method Detail

      • isRoot

        public boolean isRoot​(T node)
        Specified by:
        isRoot in interface Hierarchy<T>

      • getNextSibling

        public T getNextSibling​(T parent,
                        T child)
        Returns the next sibling of this node in the parent's children array. Returns null if this node has no parent or is the parent's last child. This method performs a linear search that is O(n) where n is the number of children; to traverse the entire array, use the parent's child enumeration instead.
        Returns:
        the sibling of this node that immediately follows this node

      • isNodeSibling

        public boolean isNodeSibling​(T aNode,
                             T anotherNode)
        Returns true if anotherNode is a sibling of (has the same parent as) this node. A node is its own sibling. If anotherNode is null, returns false.
        Parameters:
        anotherNode - node to test as sibling of this node
        Returns:
        true if anotherNode is a sibling of this node

      • getPreviousSibling

        public T getPreviousSibling​(T parent,
                            T node)
        Returns the previous sibling of this node in the parent's children array. Returns null if this node has no parent or is the parent's first child. This method performs a linear search that is O(n) where n is the number of children.
        Returns:
        the sibling of this node that immediately precedes this node

      • getChildAfter

        public T getChildAfter​(T parent,
                       T child)
        Returns the child in this node's child array that immediately follows aChild, which must be a child of this node. If aChild is the last child, returns null. This method performs a linear search of this node's children for aChild and is O(n) where n is the number of children; to traverse the entire array of children, use an enumeration instead.
        Returns:
        the child of this node that immediately follows aChild
        Throws:
        java.lang.IllegalArgumentException - if aChild is null or is not a child of this node

      • getChildBefore

        public T getChildBefore​(T parent,
                        T child)
        Returns the child in this node's child array that immediately precedes aChild, which must be a child of this node. If aChild is the first child, returns null. This method performs a linear search of this node's children for aChild and is O(n) where n is the number of children.
        Returns:
        the child of this node that immediately precedes aChild
        Throws:
        java.lang.IllegalArgumentException - if aChild is null or is not a child of this node

      • getDepth

        public int getDepth()
        Returns the depth of the tree rooted at this node -- the longest distance from this node to a leaf. If this node has no children, returns 0. This operation is much more expensive than getLevel() because it must effectively traverse the entire tree rooted at this node.
        Specified by:
        getDepth in interface Hierarchy<T>
        Returns:
        the depth of the tree whose root is this node
        See Also:
        getLevel(T)

      • getLevel

        public int getLevel​(T node)
        Returns the number of levels above this node -- the distance from the root to this node. If this node is the root, returns 0.
        Specified by:
        getLevel in interface Hierarchy<T>
        Returns:
        the number of levels above this node
        See Also:
        getDepth()

      • getPath

        public java.util.List<T> getPath​(T node)
        Returns the path from the root, to get to this node. The last element in the path is this node.
        Specified by:
        getPath in interface Hierarchy<T>
        Returns:
        an array of TreeNode objects giving the path, where the first element in the path is the root and the last element is this node.

      • isAncestor

        public boolean isAncestor​(T ancestor,
                          T descendant)
        Indicates whether an element is ancestor of another one.
        Parameters:
        ancestor - potential ancestor
        descendant - potential descendant
        Returns:
        true if ancestor is equal to descendant or if ancestor is the parent of descendant or if ancestor is the parent of an ancestor of descendant; returns false otherwise

      • notifyHierarchyNodeInserted

        protected void notifyHierarchyNodeInserted​(T child,
                                           T parent,
                                           int index,
                                           boolean isAdjusting)

      • notifyHierarchyNodeChanged

        public void notifyHierarchyNodeChanged​(T child,
                                       T parent,
                                       int index,
                                       boolean isAdjusting)
        Specified by:
        notifyHierarchyNodeChanged in interface Hierarchy<T>

      • notifyHierarchyNodeRemoved

        protected void notifyHierarchyNodeRemoved​(T child,
                                          T parent,
                                          int index,
                                          boolean isAdjusting)

      • notifyHierarchyStructureChanged

        protected void notifyHierarchyStructureChanged()

      • preorderIterator

        public java.lang.Iterable<T> preorderIterator​(T parent)
        Description copied from interface: Hierarchy
        Creates and returns an iterable that traverses the subhierarchy rooted at the give node in preorder. The first node returned by the iterator's next() method is the given node.
        Specified by:
        preorderIterator in interface Hierarchy<T>
        Parameters:
        parent - the root of the hierarchy to traverse
        Returns:
        an iterable that traverses the subtree rooted at this node in preorder.

      • breadthFirstIterator

        public java.lang.Iterable<T> breadthFirstIterator​(T parent)
        Description copied from interface: Hierarchy
        Creates and returns an iterable that traverses the subhierarchy rooted at the give node in breadth-first order. The first node returned by the iterator's next() method is the given node.
        Specified by:
        breadthFirstIterator in interface Hierarchy<T>
        Parameters:
        parent - the root of the hierarchy to traverse
        Returns:
        an iterable that traverses the subtree rooted at this node in breadth-first order.

      • depthFirstIterator

        public java.lang.Iterable<T> depthFirstIterator​(T parent)
        Description copied from interface: Hierarchy
        Creates and returns an iterable that traverses the subhierarchy rooted at the give node in depth-first order. The first node returned by the iterator's next() method is the leftmost leaf.
        Specified by:
        depthFirstIterator in interface Hierarchy<T>
        Parameters:
        parent - the root of the hierarchy to traverse
        Returns:
        an iterable that traverses the subtree rooted at this node in depth-first order.

      • leavesIterator

        public java.lang.Iterable<T> leavesIterator​(T parent)
        Specified by:
        leavesIterator in interface Hierarchy<T>

      • getPathToRoot

        public java.lang.Object[] getPathToRoot​(T aNode)
        Builds the parents of node up to and including the root node, where the original node is the last element in the returned array. The length of the returned array gives the node's depth in the tree.
        Specified by:
        getPathToRoot in interface Hierarchy<T>
        Parameters:
        aNode - the TreeNode to get the path for

      • isNodeChild

        public boolean isNodeChild​(T parent,
                           T aNode)
        Returns true if aNode is a child of this node. If aNode is null, this method returns false.
        Returns:
        true if aNode is a child of this node; false if aNode is null

      • getFirstChild

        public T getFirstChild​(T node)
        Returns this node's first child. If this node has no children, throws NoSuchElementException.
        Returns:
        the first child of this node
        Throws:
        java.util.NoSuchElementException - if this node has no children

      • getLastChild

        public T getLastChild​(T node)
        Returns this node's last child. If this node has no children, throws NoSuchElementException.
        Returns:
        the last child of this node
        Throws:
        java.util.NoSuchElementException - if this node has no children

      • getPathToRoot

        protected java.lang.Object[] getPathToRoot​(T aNode,
                                           int depth)
        Builds the parents of node up to and including the root node, where the original node is the last element in the returned array. The length of the returned array gives the node's depth in the tree.
        Parameters:
        aNode - the TreeNode to get the path for
        depth - an int giving the number of steps already taken towards the root (on recursive calls), used to size the returned array
        Returns:
        an array of TreeNodes giving the path from the root to the specified node

      • isLeaf

        public boolean isLeaf​(T node)
        Returns true if this node has no children. To distinguish between nodes that have no children and nodes that cannot have children (e.g. to distinguish files from empty directories), use this method in conjunction with getAllowsChildren
        Specified by:
        isLeaf in interface Hierarchy<T>
        Returns:
        true if this node has no children

      • getFirstLeaf

        public T getFirstLeaf​(T node)
        Finds and returns the first leaf that is a descendant of this node -- either this node or its first child's first leaf. Returns this node if it is a leaf.
        Specified by:
        getFirstLeaf in interface Hierarchy<T>
        Returns:
        the first leaf in the subtree rooted at this node
        See Also:
        isLeaf(T)

      • getLastLeaf

        public T getLastLeaf​(T node)
        Finds and returns the last leaf that is a descendant of this node -- either this node or its last child's last leaf. Returns this node if it is a leaf.
        Specified by:
        getLastLeaf in interface Hierarchy<T>
        Returns:
        the last leaf in the subtree rooted at this node
        See Also:
        isLeaf(T)

      • getNextLeaf

        public T getNextLeaf​(T node)
        Returns the leaf after this node or null if this node is the last leaf in the tree.

        In this implementation of the MutableNode interface, this operation is very inefficient. In order to determine the next node, this method first performs a linear search in the parent's child-list in order to find the current node.

        That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use depthFirstEnumeration to enumerate the nodes in the tree and use isLeaf on each node to determine which are leaves.

        Specified by:
        getNextLeaf in interface Hierarchy<T>
        Returns:
        returns the next leaf past this node
        See Also:
        isLeaf(T)

      • getPreviousLeaf

        public T getPreviousLeaf​(T node)
        Returns the leaf before this node or null if this node is the first leaf in the tree.

        In this implementation of the MutableNode interface, this operation is very inefficient. In order to determine the previous node, this method first performs a linear search in the parent's child-list in order to find the current node.

        That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use depthFirstEnumeration to enumerate the nodes in the tree and use isLeaf on each node to determine which are leaves.

        Specified by:
        getPreviousLeaf in interface Hierarchy<T>
        Returns:
        returns the leaf before this node
        See Also:
        isLeaf(T)

      • getLeafCount

        public int getLeafCount​(T node)
        Returns the total number of leaves that are descendants of this node. If this node is a leaf, returns 1. This method is O(n) where n is the number of descendants of this node.
        Specified by:
        getLeafCount in interface Hierarchy<T>
        Returns:
        the number of leaves beneath this node

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object