org.apache.asn1.ber.digester
Class TagTree

java.lang.Object
  org.apache.asn1.ber.digester.TagTree

public class TagTree

extends java.lang.Object

A disjointed tree of tag patterns with and without wild cards.

Version:

$Rev: 157644 $

Author:

Apache Directory Project

To Do:

find and start using a hash table keyed by primitive int instead of an Integer

Field Summary

private java.util.HashMap	normNodes a map of tag nodes for normal patterns
private java.util.ArrayList	normRegistrations the list of normal rule regs with rule and pattern in order
static int	WILDCARD the wild card tag value as an integer = UNIVERSAL 2,097,151 (2^21-1)
private java.util.HashMap	wildNodes a map of tag nodes for wild carded patterns
private java.util.ArrayList	wildRegistrations the list of wild carded rule regs with rule and pattern in order

Constructor Summary

TagTree()

Method Summary

private void	addNormalRule(int[] pattern, Rule rule) Adds a Rule to this TagTree.
void	addRule(int[] pattern, Rule rule) Adds a Rule to this TagTree in a manner based on whether the pattern contains a wild card in front or not.
private void	addWildRule(int[] pattern, Rule rule) Adds a Rule using a pattern with a wild card in front to this TagTree.
private void	addWildRulesToNewNormalNode(TagNode node, java.util.Stack stack) Adds wild carded rules to new nodes being added to the tag tree with normal patterns without wild cards.
private void	addWildRuleToNormalTree(int[] pattern, Rule rule, java.util.Stack stack, TagNode node) Adds rules registered via wild cards to the nodes within a branch of the normal TagTree.
private void	addWildRuleToWildTree(int[] pattern, Rule rule, java.util.Stack stack, TagNode node) Adds rules registered via wild cards to the wild TagTree to all nodes matching the pattern.
TagNode	getNode(int[] pattern)
TagNode	getNode(org.apache.commons.collections.primitives.IntStack stack)
private TagNode	getNormalNode(int[] pattern)
private TagNode	getNormalNode(org.apache.commons.collections.primitives.IntStack stack)
private TagNode	getWildNode(int[] pattern) Gets a node matching a pattern with a wild card from this TagTree.
private TagNode	getWildNode(org.apache.commons.collections.primitives.IntStack stack) Gets a node matching a pattern with a wild card from this TagTree.
private boolean	isReverseTailMatch(int[] pattern, java.util.Stack stack) Called by depth first search used to add rules of wild card patterns to the wild TagTree.
private boolean	isTailMatch(int[] pattern, java.util.Stack stack) Called by depth first search used to add rules of wild card patterns to the normal TagTree.
java.util.List	match(int[] pattern)
java.util.List	match(org.apache.commons.collections.primitives.IntStack stack)

Methods inherited from class java.lang.Object

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

Field Detail

WILDCARD

public static final int WILDCARD

the wild card tag value as an integer = UNIVERSAL 2,097,151 (2^21-1)

See Also:

Constant Field Values

normNodes

private java.util.HashMap normNodes

a map of tag nodes for normal patterns

wildNodes

private java.util.HashMap wildNodes

a map of tag nodes for wild carded patterns

normRegistrations

private java.util.ArrayList normRegistrations

the list of normal rule regs with rule and pattern in order

wildRegistrations

private java.util.ArrayList wildRegistrations

the list of wild carded rule regs with rule and pattern in order

Constructor Detail

TagTree

public TagTree()

Method Detail

addRule

public void addRule(int[] pattern,
                    Rule rule)

Adds a Rule to this TagTree in a manner based on whether the pattern contains a wild card in front or not.

Parameters:

pattern - the pattern of nested tags

rule - the rule to add for the pattern

addNormalRule

private void addNormalRule(int[] pattern,
                           Rule rule)

Adds a Rule to this TagTree.

Parameters:

pattern - the pattern of nested tags

rule - the rule to add for the pattern

addWildRule

private void addWildRule(int[] pattern,
                         Rule rule)

Adds a Rule using a pattern with a wild card in front to this TagTree.

Parameters:

pattern - the pattern of nested tags with starting wild card

rule - the rule to add for the pattern

addWildRulesToNewNormalNode

private void addWildRulesToNewNormalNode(TagNode node,
                                         java.util.Stack stack)

Adds wild carded rules to new nodes being added to the tag tree with normal patterns without wild cards.

Parameters:

node - the new node added to the tree of normal tags

stack - a stack of nodes encountered while walking the tree

addWildRuleToWildTree

private void addWildRuleToWildTree(int[] pattern,
                                   Rule rule,
                                   java.util.Stack stack,
                                   TagNode node)

Adds rules registered via wild cards to the wild TagTree to all nodes matching the pattern. This method performs depth first recursion building a stack of TagNodes as dives into the TagTree. At each point the pattern with the wild card is tested against the contents of the stack to see if it matches the nesting pattern, if it does then the rule is added to the current node.

Parameters:

pattern - the matching pattern with front wild card

rule - the rule registered with the pattern

stack - the stack storing the depth first nesting pattern

node - the current node scrutinized for a match by the pattern, and the current position of the depth first search

isReverseTailMatch

private boolean isReverseTailMatch(int[] pattern,
                                   java.util.Stack stack)

Called by depth first search used to add rules of wild card patterns to the wild TagTree. This method compares a stack of Integers to a pattern. The stack must have as many or more than pattern.length - 1 elements to match. Elements from the second element of the pattern to the last element are compared with the bottom stack element up to the top. This is the reverse order because of the inverse paths in the pattern tree with wild cards.

Parameters:

pattern - the pattern with a wild card at position 0

stack - the nesting stack representing the depth first search path

Returns:

true if the elements [n-1] in the pattern match the bottom most elements in the stack where n+1 is length of the pattern array.

addWildRuleToNormalTree

private void addWildRuleToNormalTree(int[] pattern,
                                     Rule rule,
                                     java.util.Stack stack,
                                     TagNode node)

Adds rules registered via wild cards to the nodes within a branch of the normal TagTree. All nodes matching the pattern with wild cards has the rule added to it. This method performs depth first recursion building a stack of TagNodes as it dives into the TagTree. At each point the pattern with the wild card is tested against the contents of the stack to see if it matches the nesting pattern, if it does then the rule is added to the current node.

Parameters:

pattern - the matching pattern with front wild card

rule - the rule registered with the pattern

stack - the stack storing the depth first nesting pattern

node - the current node scrutinized for a match by the pattern, and the current position of the depth first search

isTailMatch

private boolean isTailMatch(int[] pattern,
                            java.util.Stack stack)

Called by depth first search used to add rules of wild card patterns to the normal TagTree. This method compares a stack of Integers to a pattern. The stack must have as many or more than pattern.length - 1 elements to match. From the tail of the pattern to the second element is compared with the topmost stack element down.

Parameters:

pattern - the pattern with a wild card at position 0

stack - the nesting stack representing the depth first search path

Returns:

true if the elements [n-1] in the pattern match the topmost elements in the stack where n+1 is length of the pattern array.

match

public java.util.List match(org.apache.commons.collections.primitives.IntStack stack)

getNode

public TagNode getNode(org.apache.commons.collections.primitives.IntStack stack)

match

public java.util.List match(int[] pattern)

getNode

public TagNode getNode(int[] pattern)

getNormalNode

private TagNode getNormalNode(org.apache.commons.collections.primitives.IntStack stack)

getNormalNode

private TagNode getNormalNode(int[] pattern)

getWildNode

private TagNode getWildNode(int[] pattern)

Gets a node matching a pattern with a wild card from this TagTree.

Parameters:

pattern - the wild card pattern as an int array

Returns:

the matching wild card node if any

getWildNode

private TagNode getWildNode(org.apache.commons.collections.primitives.IntStack stack)

Gets a node matching a pattern with a wild card from this TagTree.

Parameters:

stack - the wild card pattern as a stack

Returns:

the matching wild card node if any