View Javadoc

1   /*
2    *   Copyright 2004 The Apache Software Foundation
3    *
4    *   Licensed under the Apache License, Version 2.0 (the "License");
5    *   you may not use this file except in compliance with the License.
6    *   You may obtain a copy of the License at
7    *
8    *       http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *   Unless required by applicable law or agreed to in writing, software
11   *   distributed under the License is distributed on an "AS IS" BASIS,
12   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *   See the License for the specific language governing permissions and
14   *   limitations under the License.
15   *
16   */
17  package org.apache.asn1.ber.digester ;
18  
19  
20  import java.util.ArrayList;
21  import java.util.Collections;
22  import java.util.HashMap;
23  import java.util.Iterator;
24  import java.util.List;
25  import java.util.Stack;
26  
27  import org.apache.commons.collections.primitives.IntStack;
28  import org.apache.commons.lang.Validate;
29  
30  
31  /***
32   * A disjointed tree of tag patterns with and without wild cards.
33   *
34   * @todo find and start using a hash table keyed by primitive int instead of
35   * an Integer
36   *
37   * @author <a href="mailto:dev@directory.apache.org">
38   * Apache Directory Project</a>
39   * @version $Rev: 157644 $
40   */
41  public class TagTree
42  {
43      /*** the wild card tag value as an integer = UNIVERSAL 2,097,151 (2^21-1) */
44      public static final int WILDCARD = 0x1FFFFFFF ;
45  
46      /*** a map of tag nodes for normal patterns */
47      private HashMap normNodes = new HashMap( 3 ) ;
48      /*** a map of tag nodes for wild carded patterns */
49      private HashMap wildNodes = new HashMap( 3 ) ;
50      /*** the list of normal rule regs with rule and pattern in order */
51      private ArrayList normRegistrations = new ArrayList() ;
52      /*** the list of wild carded rule regs with rule and pattern in order */
53      private ArrayList wildRegistrations = new ArrayList() ;
54  
55  
56      // ------------------------------------------------------------------------
57      // Methods used to add rules to trees
58      // ------------------------------------------------------------------------
59  
60  
61      /***
62       * Adds a Rule to this TagTree in a manner based on whether the pattern
63       * contains a wild card in front or not.
64       *
65       * @param pattern the pattern of nested tags
66       * @param rule the rule to add for the pattern
67       */
68      public void addRule( int[] pattern, Rule rule )
69      {
70          if ( pattern[0] == WILDCARD )
71          {
72              wildRegistrations.add( new RuleRegistration( pattern, rule ) ) ;
73              addWildRule( pattern, rule ) ;
74          }
75          else
76          {
77              normRegistrations.add( new RuleRegistration( pattern, rule ) ) ;
78              addNormalRule( pattern, rule ) ;
79          }
80      }
81  
82  
83      /***
84       * Adds a Rule to this TagTree.
85       * 
86       * @param pattern the pattern of nested tags
87       * @param rule the rule to add for the pattern
88       */
89      private void addNormalRule( int[] pattern, Rule rule )
90      {
91          Integer tag = null ;
92          TagNode node = null ;
93          Stack stack = new Stack() ;
94  
95          Validate.notNull( rule, "cannot add null rule" ) ;
96          Validate.notNull( pattern, "cannot add rule with null pattern" ) ;
97          Validate.isTrue( pattern.length > 0, 
98                  "cannot add rule with empty pattern" ) ;
99  
100         tag = new Integer( pattern[0] ) ;
101         if ( normNodes.containsKey( tag ) )
102         {
103             node = ( TagNode ) normNodes.get( tag ) ;
104             stack.push( node.getTag() ) ;
105         }
106         else
107         {
108             node = new TagNode( tag ) ;
109             normNodes.put( tag, node ) ;
110             stack.push( node.getTag() ) ;
111             addWildRulesToNewNormalNode( node, stack ) ;
112         }
113         
114         for ( int ii = 1; ii < pattern.length; ii++ )
115         {    
116             Integer childTag = new Integer( pattern[ii] ) ;
117             TagNode childNode = node.getChild( childTag ) ;
118             
119             if ( childNode == null )
120             {
121                 childNode = new TagNode( childTag ) ;
122                 node.addNode( childNode ) ;
123                 stack.push( childNode.getTag() ) ;
124                 addWildRulesToNewNormalNode( childNode, stack ) ;
125             }
126             else
127             {
128                 stack.push( childNode.getTag() ) ;
129             }
130 
131             node = childNode ;
132             tag = childTag ;
133         }
134         
135         node.addRule( rule ) ;
136     }
137 
138 
139     /***
140      * Adds a Rule using a pattern with a wild card in front to this TagTree.
141      *
142      * @param pattern the pattern of nested tags with starting wild card
143      * @param rule the rule to add for the pattern
144      */
145     private void addWildRule( int[] pattern, Rule rule )
146     {
147         Validate.notNull( pattern,
148                 "Attempting to register rule " + rule
149                 + " with null pattern" ) ;
150         Validate.isTrue( pattern.length > 0,
151                 "Attempting to register rule " + rule
152                 + " with zero length pattern" ) ;
153         Validate.isTrue( pattern[0] == WILDCARD,
154                 "Expected rule " + rule
155                 + " pattern to have front wild card but it did not" ) ;
156         Validate.isTrue( pattern.length > 1,
157                 "Cannot register only wild card \"*\" pattern for rule "
158                 + rule ) ;
159 
160         /*
161          * Adds the rule associated with the registration to the normal tag
162          * tree which involves a recursive descent on the normal tree.
163          */
164         TagNode node = null ;
165         Iterator list = normNodes.values().iterator() ;
166         while ( list.hasNext() )
167         {
168             node = ( TagNode ) list.next() ;
169             addWildRuleToNormalTree( pattern, rule, new Stack(), node ) ;
170         }
171 
172         /*
173          * first just lay down the new branch without adding the rule
174          * next do a recursive drilldown testing for rule addition to all nodes
175          */
176         Integer tag = new Integer( pattern[pattern.length-1] ) ;
177         if ( wildNodes.containsKey( tag ) )
178         {
179             node = ( TagNode ) wildNodes.get( tag ) ;
180         }
181         else
182         {
183             node = new TagNode( tag ) ;
184             wildNodes.put( tag, node ) ;
185         }
186 
187         for( int ii = pattern.length - 2; ii >= 1; ii-- )
188         {
189             Integer childTag = new Integer( pattern[ii] ) ;
190             TagNode childNode = node.getChild( childTag ) ;
191 
192             if ( childNode == null )
193             {
194                 childNode = new TagNode( childTag ) ;
195                 node.addNode( childNode ) ;
196             }
197 
198             node = childNode ;
199             tag = childTag ;
200         }
201 
202         /*
203          * Recusively drill down each branch of the wild tree checking at each
204          * node to see if we need to add the new rule based on the pattern
205          */
206         list = wildNodes.values().iterator() ;
207         while( list.hasNext() )
208         {
209             node = ( TagNode ) list.next() ;
210             addWildRuleToWildTree( pattern, rule, new Stack(), node ) ;
211         }
212     }
213 
214 
215     /***
216      * Adds wild carded rules to new nodes being added to the tag tree with
217      * normal patterns without wild cards.
218      *
219      * @param node the new node added to the tree of normal tags
220      * @param stack a stack of nodes encountered while walking the tree
221      */
222     private void addWildRulesToNewNormalNode( TagNode node, Stack stack )
223     {
224         for ( int jj = 0; jj < wildRegistrations.size(); jj++ )
225         {
226             RuleRegistration reg = ( RuleRegistration )
227                     wildRegistrations.get( jj ) ;
228 
229             if ( isTailMatch( reg.getPattern(), stack ) )
230             {
231                 node.addRule( reg.getRule() ) ;
232             }
233         }
234     }
235 
236 
237     /***
238      * Adds rules registered via wild cards to the wild TagTree to all
239      * nodes matching the pattern.  This method performs depth first recursion
240      * building a stack of TagNodes as dives into the TagTree.  At each point
241      * the pattern with the wild card is tested against the contents of the
242      * stack to see if it matches the nesting pattern, if it does then the
243      * rule is added to the current node.
244      *
245      * @param pattern the matching pattern with front wild card
246      * @param rule the rule registered with the pattern
247      * @param stack the stack storing the depth first nesting pattern
248      * @param node the current node scrutinized for a match by the pattern, and
249      * the current position of the depth first search
250      */
251     private void addWildRuleToWildTree( int[] pattern, Rule rule,
252                                         Stack stack, TagNode node )
253     {
254         stack.push( node.getTag() ) ;
255 
256         if ( isReverseTailMatch( pattern, stack ) )
257         {
258             if ( ! node.getRules().contains( rule ) )
259             {
260                 node.addRule( rule ) ;
261             }
262         }
263 
264         if ( ! node.isLeaf() )
265         {
266             Iterator children = node.getChildren() ;
267             while( children.hasNext() )
268             {
269                 addWildRuleToWildTree( pattern, rule, stack,
270                         ( TagNode ) children.next() ) ;
271             }
272         }
273 
274         stack.pop() ;
275     }
276 
277 
278     /***
279      * Called by depth first search used to add rules of wild card patterns to
280      * the wild TagTree.  This method compares a stack of Integers to a
281      * pattern.  The stack must have as many or more than pattern.length - 1
282      * elements to match.  Elements from the second element of the pattern to
283      * the last element are compared with the bottom stack element up to the
284      * top.  This is the reverse order because of the inverse paths in the
285      * pattern tree with wild cards.
286      *
287      * @param pattern the pattern with a wild card at position 0
288      * @param stack the nesting stack representing the depth first search path
289      * @return true if the elements [n-1] in the pattern match the bottom most
290      * elements in the stack where n+1 is length of the pattern array.
291      */
292     private boolean isReverseTailMatch( int[] pattern, Stack stack )
293     {
294         if ( stack.size() < pattern.length - 1 )
295         {
296             return false ;
297         }
298 
299         for( int ii = pattern.length - 1, jj = 0 ; ii >= 1; ii--, jj++ )
300         {
301             if ( pattern[ii] != ( ( Integer ) stack.get( jj ) ).intValue() )
302             {
303                 return false ;
304             }
305         }
306 
307         return true ;
308     }
309 
310 
311     /***
312      * Adds rules registered via wild cards to the nodes within a branch of the
313      * normal TagTree.  All nodes matching the pattern with wild cards has the
314      * rule added to it.  This method performs depth first recursion building
315      * a stack of TagNodes as it dives into the TagTree.  At each point the
316      * pattern with the wild card is tested against the contents of the
317      * stack to see if it matches the nesting pattern, if it does then the
318      * rule is added to the current node.
319      *
320      * @param pattern the matching pattern with front wild card
321      * @param rule the rule registered with the pattern
322      * @param stack the stack storing the depth first nesting pattern
323      * @param node the current node scrutinized for a match by the pattern, and
324      * the current position of the depth first search
325      */
326     private void addWildRuleToNormalTree( int[] pattern, Rule rule,
327                                           Stack stack, TagNode node )
328     {
329         stack.push( node.getTag() ) ;
330 
331         if ( isTailMatch( pattern, stack ) && node.isLeaf() )
332         {
333             if ( ! node.getRules().contains( rule ) )
334             {
335                 node.addRule( rule ) ;
336             }
337         }
338 
339         if ( ! node.isLeaf() )
340         {
341             Iterator children = node.getChildren() ;
342             while( children.hasNext() )
343             {
344                 addWildRuleToNormalTree( pattern, rule, stack,
345                         ( TagNode ) children.next() ) ;
346             }
347         }
348 
349         stack.pop() ;
350     }
351 
352 
353     /***
354      * Called by depth first search used to add rules of wild card patterns to
355      * the normal TagTree.  This method compares a stack of Integers to a
356      * pattern.  The stack must have as many or more than pattern.length - 1
357      * elements to match.  From the tail of the pattern to the second element
358      * is compared with the topmost stack element down.
359      *
360      * @param pattern the pattern with a wild card at position 0
361      * @param stack the nesting stack representing the depth first search path
362      * @return true if the elements [n-1] in the pattern match the topmost
363      * elements in the stack where n+1 is length of the pattern array.
364      */
365     private boolean isTailMatch( int[] pattern, Stack stack )
366     {
367         if ( stack.size() < pattern.length - 1 )
368         {
369             return false ;
370         }
371 
372         for( int ii = pattern.length - 1, jj = stack.size() - 1; ii >= 1;
373              ii--, jj-- )
374         {
375             if ( pattern[ii] != ( ( Integer ) stack.get( jj ) ).intValue() )
376             {
377                 return false ;
378             }
379         }
380 
381         return true ;
382     }
383 
384 
385     // ------------------------------------------------------------------------
386     // Methods used for matching a stack or a int[]
387     // ------------------------------------------------------------------------
388 
389 
390     public List match( IntStack stack )
391     {
392         TagNode node = getNode( stack ) ;
393         
394         if ( node == null )
395         {
396             return Collections.EMPTY_LIST ;
397         }
398         
399         return node.getRules() ;
400     }
401     
402     
403     public TagNode getNode( IntStack stack )
404     {
405         TagNode node = getNormalNode( stack ) ;
406 
407         if ( node == null )
408         {
409             node = getWildNode( stack ) ;
410         }
411 
412         return node ;
413     }
414 
415 
416     public List match( int[] pattern )
417     {
418         TagNode node = getNode( pattern ) ;
419 
420         if ( node == null )
421         {
422             return Collections.EMPTY_LIST ;
423         }
424 
425         return node.getRules() ;
426     }
427 
428 
429     public TagNode getNode( int[] pattern )
430     {
431         TagNode node = getNormalNode( pattern ) ;
432 
433         if ( node == null )
434         {
435             node = getWildNode( pattern ) ;
436         }
437 
438         return node ;
439     }
440 
441 
442     private TagNode getNormalNode( IntStack stack )
443     {
444         Integer tag = null ;
445         TagNode node = null ;
446 
447         Validate.notNull( stack, "cannot match using null pattern" ) ;
448         Validate.isTrue( !stack.empty(), "cannot match with empty pattern" ) ;
449 
450         tag = new Integer( stack.get( 0 ) ) ;
451         if ( normNodes.containsKey( tag ) )
452         {
453             node = ( TagNode ) normNodes.get( tag ) ;
454         }
455         else
456         {
457             return null ;
458         }
459         
460         for ( int ii = 1; ii < stack.size(); ii++ )
461         {    
462             Integer childTag = new Integer( stack.get( ii ) ) ;
463             TagNode childNode = node.getChild( childTag ) ;
464             
465             if ( childNode == null )
466             {
467                 return null ;
468             }
469             
470             node = childNode ;
471             tag = childTag ;
472         }
473         
474         return node ;
475     }
476 
477 
478     private TagNode getNormalNode( int[] pattern )
479     {
480         Integer tag = null ;
481         TagNode node = null ;
482 
483         Validate.notNull( pattern, "cannot match using null pattern" ) ;
484         Validate.isTrue( pattern.length > 0, 
485                 "cannot match with empty pattern" ) ;
486 
487         tag = new Integer( pattern[0] ) ;
488         if ( normNodes.containsKey( tag ) )
489         {
490             node = ( TagNode ) normNodes.get( tag ) ;
491         }
492         else
493         {
494             return null ;
495         }
496         
497         for ( int ii = 1; ii < pattern.length; ii++ )
498         {    
499             Integer childTag = new Integer( pattern[ii] ) ;
500             TagNode childNode = node.getChild( childTag ) ;
501             
502             if ( childNode == null )
503             {
504                 return null ;
505             }
506             
507             node = childNode ;
508             tag = childTag ;
509         }
510         
511         return node ;
512     }
513 
514 
515     /***
516      * Gets a node matching a pattern with a wild card from this TagTree.
517      *
518      * @param pattern the wild card pattern as an int array
519      * @return the matching wild card node if any
520      */
521     private TagNode getWildNode( int[] pattern )
522     {
523         Integer tag = null ;
524         TagNode node = null ;
525 
526         /*
527          * Restrict empty pattern, and zero length patterns.
528          */
529         Validate.notNull( pattern,
530                 "cannot match using null pattern" ) ;
531         Validate.isTrue( pattern.length > 0,
532                 "cannot match with empty pattern" ) ;
533 
534         /*
535          * Begin reverse walk by looking up the node corresponding
536          * to the last pattern element.  Return null if it does not exit.
537          */
538         tag = new Integer( pattern[pattern.length - 1] ) ;
539         if ( wildNodes.containsKey( tag ) )
540         {
541             node = ( TagNode ) wildNodes.get( tag ) ;
542         }
543         else
544         {
545             return null ;
546         }
547 
548         /*
549          * Walk using the second to last [pattern.length-2] element down to
550          * the first element at index 0 in the pattern.
551          */
552         for ( int ii = pattern.length-2; ii >= 0; ii-- )
553         {
554             Integer childTag = new Integer( pattern[ii] ) ;
555             TagNode childNode = node.getChild( childTag ) ;
556 
557             /*
558              * If no more children are present and we're about to walk off of
559              * the tree then we return the last node we have seen here.
560              */
561             if ( childNode == null )
562             {
563                 return node ;
564             }
565 
566             node = childNode ;
567             tag = childTag ;
568         }
569 
570         return node ;
571     }
572 
573 
574     /***
575      * Gets a node matching a pattern with a wild card from this TagTree.
576      *
577      * @param stack the wild card pattern as a stack
578      * @return the matching wild card node if any
579      */
580     private TagNode getWildNode( IntStack stack )
581     {
582         Integer tag = null ;
583         TagNode node = null ;
584 
585         /*
586          * Restrict empty pattern, and zero length patterns.
587          */
588         Validate.notNull( stack, "cannot match using null pattern" ) ;
589         Validate.isTrue( !stack.empty(), "cannot match with empty pattern" ) ;
590 
591         /*
592          * Begin reverse walk by looking up the node corresponding
593          * to the bottom stack element.  Return null if it does not exit.
594          */
595         tag = new Integer( stack.get( stack.size() - 1 ) ) ;
596         if ( wildNodes.containsKey( tag ) )
597         {
598             node = ( TagNode ) wildNodes.get( tag ) ;
599         }
600         else
601         {
602             return null ;
603         }
604 
605         /*
606          * Walk using the element above the bottom [stack.size()-2] up to
607          * the top element at index 0 in the stack.
608          */
609         for ( int ii = stack.size() - 2; ii >= 0; ii-- )
610         {
611             Integer childTag = new Integer( stack.get( ii ) ) ;
612             TagNode childNode = node.getChild( childTag ) ;
613 
614             /*
615              * If no more children are present and we're about to walk off of
616              * the tree then we return the last node we have seen here.
617              */
618             if ( childNode == null )
619             {
620                 return node ;
621             }
622 
623             node = childNode ;
624             tag = childTag ;
625         }
626 
627         return node ;
628     }
629 }