ca.quine.jcommons.transform.graph
Class SearchUtils

java.lang.Object
  |
  +--ca.quine.jcommons.transform.graph.SearchUtils

public class SearchUtils

extends Object

Field Summary

static int	TRAVERSAL_BFS Use a breadth first search traversal.
static int	TRAVERSAL_DFS_POSTORDER Use a depth first search traversal, where we visit each node after its children.
static int	TRAVERSAL_DFS_PRE_AND_POSTORDER Use a depth first search traversal, where each node is applied before and after its children.
static int	TRAVERSAL_DFS_PREORDER Use a depth first search traversal, where we visit each node before its children.

Method Summary

static void	apply(TransformNode parentNode, int traversal, INodeApplicator applicator) Applies the given applicator to the given TransformNode and it's children in the given traversal order.
static void	apply(TransformNode parentNode, TransformNode node, int traversal, INodeApplicator applicator) Applies the given applicator to the given TransformNode in the given traversal order.
static boolean	applyDFS(TransformNode inGPNode, TransformNode inParentNode, IDFSNodeApplicator applicator) Perform a DFS with a Stack instead of recursion to get around Java's problem of having a much smaller stack size than heap space.
static boolean	applyDFSMarkedEdges(TransformNode inGPNode, TransformNode inParentNode, IDFSNodeApplicator applicator) Similar to applyDFS(TransformNode, TransformNode, IDFSNodeApplicator) but only traverses marked edges.
static boolean	applyDFSRecursive(TransformNode grandParentNode, TransformNode parentNode, IDFSNodeApplicator applicator) Sample code for perfectly ordinary recursive DFS.

Methods inherited from class java.lang.Object

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

Field Detail

TRAVERSAL_DFS_PREORDER

public static final int TRAVERSAL_DFS_PREORDER

Use a depth first search traversal, where we visit each node before its children.

See Also:

apply(TransformNode, int, INodeApplicator), apply(TransformNode, TransformNode, int, INodeApplicator), Constant Field Values

TRAVERSAL_DFS_POSTORDER

public static final int TRAVERSAL_DFS_POSTORDER

Use a depth first search traversal, where we visit each node after its children.

See Also:

apply(TransformNode, int, INodeApplicator), apply(TransformNode, TransformNode, int, INodeApplicator), Constant Field Values

TRAVERSAL_BFS

public static final int TRAVERSAL_BFS

Use a breadth first search traversal.

See Also:

apply(TransformNode, int, INodeApplicator), apply(TransformNode, TransformNode, int, INodeApplicator), Constant Field Values

TRAVERSAL_DFS_PRE_AND_POSTORDER

public static final int TRAVERSAL_DFS_PRE_AND_POSTORDER

Use a depth first search traversal, where each node is applied before and after its children.

See Also:

apply(TransformNode, int, INodeApplicator), apply(TransformNode, TransformNode, int, INodeApplicator), Constant Field Values

Method Detail

apply

public static void apply(TransformNode parentNode,
                         int traversal,
                         INodeApplicator applicator)

Applies the given applicator to the given TransformNode and it's children in the given traversal order.

Parameters:

traversal - one of TRAVERSAL_DFS_PREORDER or TRAVERSAL_DFS_POSTORDER

applicator -

apply

public static void apply(TransformNode parentNode,
                         TransformNode node,
                         int traversal,
                         INodeApplicator applicator)

Applies the given applicator to the given TransformNode in the given traversal order.

Parameters:

parentNode - the parent Node of node (or null if node is the root node)

node -

traversal - one of TRAVERSAL_DFS_PREORDER or TRAVERSAL_DFS_POSTORDER

applicator -

applyDFSRecursive

public static boolean applyDFSRecursive(TransformNode grandParentNode,
                                        TransformNode parentNode,
                                        IDFSNodeApplicator applicator)

Sample code for perfectly ordinary recursive DFS. (The iterative one was based off of this code.)

Parameters:

grandParentNode -

parentNode -

applicator -

Returns:

false if the search was requested to stop, true if the search should continue or fully completed (at the top level of the recursion)

applyDFS

public static boolean applyDFS(TransformNode inGPNode,
                               TransformNode inParentNode,
                               IDFSNodeApplicator applicator)

Perform a DFS with a Stack instead of recursion to get around Java's problem of having a much smaller stack size than heap space.

Parameters:

inGPNode -

inParentNode -

applicator -

Returns:

false if the search was requested to stop before completion, true if the search applied every node (and thus fully completed)

applyDFSMarkedEdges

public static boolean applyDFSMarkedEdges(TransformNode inGPNode,
                                          TransformNode inParentNode,
                                          IDFSNodeApplicator applicator)

Similar to applyDFS(TransformNode, TransformNode, IDFSNodeApplicator) but only traverses marked edges.

Parameters:

inGPNode -

inParentNode -

applicator -

Returns:

false if the search was requested to stop before completion, true if the search applied every node (and thus fully completed)