1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
162
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
174
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
204
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
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
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
536
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
550
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
559
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
587
588 Validate.notNull( stack, "cannot match using null pattern" ) ;
589 Validate.isTrue( !stack.empty(), "cannot match with empty pattern" ) ;
590
591
592
593
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
607
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
616
617
618 if ( childNode == null )
619 {
620 return node ;
621 }
622
623 node = childNode ;
624 tag = childTag ;
625 }
626
627 return node ;
628 }
629 }