# TreeNode.java

    /*
    ** Module   : TreeNode.java
    ** Abstract : self-referential node structure that provides the base class
    **            for creating trees that structure custom information
    **
    ** Copyright (c) 2005-2017, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- ----------------------------Description------------------------------
    ** 001 GES 20050310  @20283 Created initial version which provides a wide range of possible methods
    **                          for tree walking including parent links, iterators for all immediate
    **                          children and for all children, the ability to get the first child, get
    **                          the next sibling and get the previous sibling.
    ** 002 NVS 20050527 @21325  Added getPath() method which returns an array of TreeNodes from the
    **                          root to this node.
    ** 003 NVS 20050601 @21365  Added getChildDepth() method which calculates the distance from this
    **                          node to the farmost child.
    ** 004 CA  20140313         Infered generics.
    */
    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program is distributed in the hope that it will be useful,
    ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    ** GNU Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.util;

    import java.util.*;

    /**
     * A tree node which is a base class which provides a simple mechanism to
     * create and use trees to store custom data.  The subclass can be limited
     * to providing the data storage and access while this superclass handles
     * all aspects of tree structuring and facilities for walking or inspecting
     * the tree.
     *
     * Each instance of this class provides:
     * <ul>
     *    <li> An ordered list of child nodes.
     *    <li> A link to the parent node. This permits leaf-to-root path
     *         traversal.
     *    <li> An iterator for all immediate children.
     *    <li> An iterator for the entire tree rooted at this node, in depth-first
     *         order.
     *    <li> The ability to get the first child and get the next or previous
     *         sibling.
     *    <li> The number of immediate children.
     *    <li> The depth from the root of the tree (that ancestor node which has
     *         a <code>null</code> parent.
     * </ul>
     */
    public class TreeNode
    {
       /** Parent node to this node */
       private TreeNode parent = null;

       /** List of children, in order of insertion. */
       private LinkedList<TreeNode> children = new LinkedList<>();

       /**
        * Default constructor.
        */
       public TreeNode()
       {
       }

       /**
        * Adds a node to the end of the list of children.  The child node's
        * parent will be set.
        *
        * @param    child
        *           The node to add.
        */
       public void addChild(TreeNode child)
       {
          child.setParent(this);
          children.add(child);
       }

       /**
        * Get the level of nesting of this node from the root, where
        * <code>0</code> indicates the root, and a positive number indicates
        * generations from the root.
        *
        * @return  Nesting level.
        */
       public int getDepth()
       {
          TreeNode next;
          int depth = 0;

          for (next = this; (next = next.getParent()) != null; depth++);

          return depth;
       }

       /**
        * Get the level of nesting of the farmost child node from this node, where
        * <code>0</code> indicates this node, and a positive number indicates
        * generations from this node.
        *
        * @return  Nesting level.
        */
       public int getChildDepth()
       {
          return getChildDepth(this);
       }

       /**
        * Get the array of tree nodes which represents the path to this node from
        * the root of the tree.
        * <p>The array always contains the root of the tree at index 0 and this
        * node as the last item.
        *
        * @return  array of tree nodes.
        */
       public TreeNode[] getPath()
       {
          List<TreeNode> path = new LinkedList<>();
          TreeNode next;

          for (next = this; next != null; next = next.getParent())
             path.add(0, next);

          TreeNode[] array = new TreeNode[path.size()];
          array = path.toArray(array);

          return array;
       }

       /**
        * Get the number of immediate child nodes.
        *
        * @return  Number of immediate child nodes.
        */
       public int getNumChildren()
       {
          return children.size();
       }

       /**
        * Access the first child in the list of children.
        *
        * @return   The first child in the list of children or <code>null</code>
        *           if there are no children in the list.
        */
       public TreeNode getFirstChild()
       {
          TreeNode child = null;

          try
          {
             child = children.getFirst();
          }
          catch (NoSuchElementException nse)
          {
             // we just return null in this case
          }

          return child;
       }

       /**
        * Access the next sibling (the child to the right of this node in the
        * parent's list of children).
        *
        * @return   The next sibling in the parent's list or <code>null</code> if
        *           there is no child to the right.
        */
       public TreeNode getNextSibling()
       {
          return getRelativeSibling(1);
       }

       /**
        * Access the previous sibling (the child to the left of this node in the
        * parent's list of children).
        *
        * @return   The next sibling in the parent's list or <code>null</code> if
        *           there is no child to the left.
        */
       public TreeNode getPreviousSibling()
       {
          return getRelativeSibling(-1);
       }

       /**
        * Get this nodes's parent, if any.
        *
        * @return  Parent node, or <code>null</code> if this node represents
        *          the root of a hierarchy.
        */
       public TreeNode getParent()
       {
          return parent;
       }

       /**
        * Sets this nodes's parent.
        *
        * @param    parent
        *           The parent node of this node.
        */
       public void setParent(TreeNode parent)
       {
          this.parent = parent;
       }

       /**
        * Return an iterator to walk this node's children recursively in a
        * depth-first traversal. 'Depth-first' means that the iteration will
        * traverse the children of any given node before traversing that node's
        * siblings.
        *
        * @return  An iterator which will walk this node and all of its
        *          descendants.
        */
       public Iterator<? extends TreeNode> descendantsIterator()
       {
          LinkedList<TreeNode> fullList = new LinkedList<>();

          // recursively walk all children depth-first and add all in proper
          // order to this list (we are degenerating the tree)
          addChildrenToList(fullList);

          return fullList.listIterator();
       }

       /**
        * Return an iterator to walk ONLY the immediate children of this node.
        *
        * @return  An iterator to the list of children nodes, each element being
        *          an instance of this class.
        */
       public Iterator<? extends TreeNode> childIterator()
       {
          return children.listIterator();
       }

       /**
        * Recursively walk the list of children and add each child to the list
        * in a depth-first traversal.  'Depth-first' means that the iteration will
        * traverse the children of any given node before traversing that node's
        * siblings.  This method is used to create an iterator for the entire
        * tree.
        *
        * @param    list
        *           The list to which children need to be added.
        */
       private void addChildrenToList(LinkedList<TreeNode> list)
       {
          list.add(this);

          Iterator<TreeNode> iter = children.listIterator();

          while(iter.hasNext())
          {
             TreeNode child = iter.next();
             child.addChildrenToList(list);
          }
       }

       /**
        * Return the sibling at the index relative (positive or negative) to the
        * this node.
        *
        * @param    relativeIndex
        *           The positive or negative relative index position.
        *
        * @return   The sibling at that relative index position or
        *           <code>null</code> if no such sibling exists.
        */
       private TreeNode getRelativeSibling(int relativeIndex)
       {
          TreeNode sibling = null;

          // no possible siblings?
          if (parent == null)
             return null;

          try
          {
             int idx = parent.children.indexOf(this) + relativeIndex;

             sibling = (TreeNode) parent.children.get(idx);
          }

          catch (IndexOutOfBoundsException iob)
          {
             // just return null in this case
          }

          return sibling;
       }

       /**
        * Get the level of nesting of the farmost child node from this node, where
        * <code>0</code> indicates this node, and a positive number indicates
        * generations from this node.
        *
        * @param   node
        *          node to start with
        * @return  Nesting level.
        */
       private int getChildDepth(TreeNode node)
       {
          Iterator<? extends TreeNode> iter = node.childIterator();
          if (!iter.hasNext())
             return 0;

          TreeNode next = null;
          int depth = 0;
          int nextDepth = 0;

          while (iter.hasNext())
          {
             next = iter.next();
             nextDepth = getChildDepth(next);
             if (nextDepth > depth)
                depth = nextDepth;
          }

          return 1 + depth;
       }
    }