org.apache.asn1.ber.digester
Class TagTree

java.lang.Object
  extended byorg.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


Copyright © 2004-2006 . All Rights Reserved.