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;
}
}