gumbo.util.relation
Class TreeNodes

java.lang.Object
  |
  +--gumbo.util.relation.TreeNodes

public class TreeNodes

extends java.lang.Object

Constants and utilities related to IntersectionTreeNode.

Version:

$Revision: 1.2 $

Author:

Jon Barrilleaux (jonb@jmbaai.com) of JMB and Associates Inc.

Nested Class Summary

static class	TreeNodes.GlobalTree Global tree used as the default singleton for global-relationship tree nodes.
static class	TreeNodes.Tree A relationship whose relations are tree nodes.
static class	TreeNodes.TreeNodeImm A serializable immutable view wrapper for a target TreeNode.
static class	TreeNodes.TreeNodeWrapper A serializable wrapper for a target TreeNode.

Method Summary

static void	disposeAncestors(TreeNode seedNode) Disposes the ancestors of a seed node, but not the seed node.
static void	disposeDescendants(TreeNode seedNode) Disposes the descendants of a seed node, but not the seed node.
static java.lang.Object	findRoot(TreeNode seedNode) Returns the root of a tree node's tree.
static boolean	isAcyclic(TreeNode seedNode, java.util.Set retSet, java.util.List retVal) Returns true if the tree is acyclic.
static boolean	isAcyclic(TreeNode parentNode, TreeNode childNode, java.util.Set retSet, java.util.List retVal) Returns true if a proposed tree is acyclic.
static boolean	isAncestor(TreeNode ancNode, TreeNode dscNode) Returns true if one tree node is the same as or an ancestor of another tree node.
static TreeNode	leafTreeNode(TreeNode target) Returns a mutable leaf view of a target tree node, which throws an exception if a child is added or removed.
static TreeNode	rootTreeNode(TreeNode target) Returns a mutable root view of a target tree node, which throws an exception if the parent is set to anything but null.
static java.util.List	traceAncestors(TreeNode seedNode, TreeNode pruneNode, java.util.Set retSet, java.util.List retVal) Performs a breadth-first search of a tree's ancestor subgraph (parent lineage) starting with a seed node and returning the tree node delegators found.
static java.util.List	traceDescendants(TreeNode seedNode, TreeNode pruneNode, java.util.Set retSet, java.util.List retVal) Performs a breadth-first search of a tree's descendent subgraph (child lineage) starting with a seed node and returning the tree node delegators found.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

rootTreeNode

public static TreeNode rootTreeNode(TreeNode target)

Returns a mutable root view of a target tree node, which throws an exception if the parent is set to anything but null.

Parameters:

target - Target of this wrapper. Never null.

Returns:

A new wrapper for the target. Never null.

leafTreeNode

public static TreeNode leafTreeNode(TreeNode target)

Returns a mutable leaf view of a target tree node, which throws an exception if a child is added or removed.

Parameters:

target - Target of this wrapper. Never null.

Returns:

A new wrapper for the target. Never null.

isAncestor

public static boolean isAncestor(TreeNode ancNode,
                                 TreeNode dscNode)

Returns true if one tree node is the same as or an ancestor of another tree node.

Parameters:

ancNode - The suspected ancestor. If null, returns false.

dscNode - The suspected descendant. If null, returns false.

Returns:

True if ancNode is the same as or an ancestor of dscNode. False if ancNode or dscNode are null, or if a cycle is found.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.

findRoot

public static java.lang.Object findRoot(TreeNode seedNode)

Returns the root of a tree node's tree.

Parameters:

seedNode - The seed tree node. If null returns null.

Returns:

The root delegator. Null if the tree is cyclic.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.

isAcyclic

public static boolean isAcyclic(TreeNode seedNode,
                                java.util.Set retSet,
                                java.util.List retVal)

Returns true if the tree is acyclic.

Parameters:

seedNode - Any tree node in the tree. If null, returns false.

retSet - Return value object. The tree trace from its root, as a set of tree node delegators (Object). Also used internally for fast lookup (use a HashSet). If null, retList is used for lookup (which may be slow). Any previous entries will be lost.

retVal - Return value object. The tree trace from its root, as a list of tree node delegators (Object). Never null. Any previous entries will be lost.

Returns:

False if the seed is null or the tree is acyclic.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.

isAcyclic

public static boolean isAcyclic(TreeNode parentNode,
                                TreeNode childNode,
                                java.util.Set retSet,
                                java.util.List retVal)

Returns true if a proposed tree is acyclic.

Parameters:

parentNode - The parent tree node in the proposed tree. If null, returns false.

childNode - The child tree node in the proposed tree. If null or can't be added (has a parent), returns false.

retSet - Return value object. The tree trace from its root, as a set of tree node delegators (Object). Also used internally for fast lookup (use a HashSet). If null, retList is used for lookup (which may be slow). Any previous entries will be lost.

retVal - Return value object. The tree trace from its root, as a list of tree node delegators (Object). Never null. Any previous entries will be lost.

Returns:

False if the proposed tree is acyclic or can't be formed.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.

traceAncestors

public static java.util.List traceAncestors(TreeNode seedNode,
                                            TreeNode pruneNode,
                                            java.util.Set retSet,
                                            java.util.List retVal)

Performs a breadth-first search of a tree's ancestor subgraph (parent lineage) starting with a seed node and returning the tree node delegators found. Preserves the relative depth from the seed and blocks cycles. Includes provisions for pruning a subgraph (such as the "far" subgraph of a cyclic tree).

Parameters:

seedNode - The seed tree node of the trace. The seed is included in the trace unless pruned. If null, the trace will be empty.

pruneNode - A node whose subgraph will be pruned from the trace. The prune tree node is excluded from the trace. Null if none (prune nothing from the trace). If the seed, the trace is generated and then the seed is removed.

retSet - Return value object. The tree trace, as a set of tree node delegators (Object). Also used internally for fast lookup (use a HashSet). If null, retVal is used for lookup (which may be slow). Any previous entries will be lost.

retVal - Return value object. The tree trace, as a list of tree node delegators (Object). Never null. Empty if seed is null. The seed will be the first entry if not pruned. Any previous entries will be lost.

Returns:

Reference to retVal.

Throws:

java.lang.IllegalArgumentException - The return value object is null.

java.lang.IllegalStateException - if a relation is not in a relationship.

traceDescendants

public static java.util.List traceDescendants(TreeNode seedNode,
                                              TreeNode pruneNode,
                                              java.util.Set retSet,
                                              java.util.List retVal)

Performs a breadth-first search of a tree's descendent subgraph (child lineage) starting with a seed node and returning the tree node delegators found. Preserves the relative depth from the seed and blocks cycles. Includes provisions for pruning a subgraph (such as the "far" subgraph of a cyclic tree).

Parameters:

seedNode - The seed tree node of the trace. The seed is included in the trace unless pruned. If null, the trace will be empty.

pruneNode - A tree node whose subgraph will be pruned from the trace. The prune node is excluded from the trace. Null if none (prune nothing from the trace). If the seed, the trace is generated and then the seed is removed.

retSet - Return value object. The tree trace, as a set of tree node delegators (Object). Also used internally for fast lookup (use a HashSet). If null, retVal is used for lookup (which may be slow). Any previous entries will be lost.

retVal - Return value object. The tree trace, as a list of tree node delegators (Object). Never null. Empty if seed is null. The seed will be the first entry if not pruned. Any previous entries will be lost.

Returns:

Reference to retVal.

Throws:

java.lang.IllegalArgumentException - The return value object is null.

java.lang.IllegalStateException - if a relation is not in a relationship.

disposeAncestors

public static void disposeAncestors(TreeNode seedNode)

Disposes the ancestors of a seed node, but not the seed node.

Parameters:

seedNode - The seed tree node. If null, does nothing.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.

disposeDescendants

public static void disposeDescendants(TreeNode seedNode)

Disposes the descendants of a seed node, but not the seed node.

Parameters:

seedNode - The seed tree node. If null, does nothing.

Throws:

java.lang.IllegalStateException - if a relation is not in a relationship.