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 org.apache.commons.collections.primitives.IntStack;
21  import org.apache.commons.test.PrivateTestCase;
22  
23  import java.util.HashMap;
24  import java.util.List;
25  import java.util.Stack;
26  
27  
28  /***
29   * Tests the TagTree class.
30   *
31   * @author <a href="mailto:dev@directory.apache.org">
32   * Apache Directory Project</a>
33   * @version $Rev: 158144 $
34   */
35  public class TagTreeTest extends PrivateTestCase
36  {
37      /***
38       * Constructor for TagTreeTest.
39       * @param name the name of the test case
40       */
41      public TagTreeTest( String name )
42      {
43          super( name ) ;
44      }
45  
46  
47      /***
48       * Accesses the private wildNodes member to extract the TagNode 
49       * with the int tag argument as a value.
50       * 
51       * @param tree the tree to access
52       * @param tag the tag value to get the TagNode for
53       * @return the tag node accessed or null
54       */ 
55      private TagNode getWildNode( TagTree tree, int tag )
56      {
57          HashMap nodes = ( HashMap ) getMember( "wildNodes", tree ) ;
58          return ( TagNode ) nodes.get( new Integer( tag ) ) ;
59      }
60  
61  
62      /***
63       * Accesses the private normNodes member to extract the TagNode 
64       * with the int tag argument as a value.
65       * 
66       * @param tree the tree to access
67       * @param tag the tag value to get the TagNode for
68       * @return the tag node accessed or null
69       */ 
70      private TagNode getNormalNode( TagTree tree, int tag )
71      {
72          HashMap nodes = ( HashMap ) getMember( "normNodes", tree ) ;
73          return ( TagNode ) nodes.get( new Integer( tag ) ) ;
74      }
75  
76  
77      /***
78       * Used to white box test the private isTailMatch() method of the TagTree.
79       *
80       * @param tree the tree instance to test
81       * @param pattern the pattern arg
82       * @param stack the stack arg
83       * @return the resultant true or false return value
84       */
85      private boolean isTailMatch( TagTree tree, int[] pattern, Stack stack )
86      {
87          Class[] argClasses = { pattern.getClass(), Stack.class } ;
88          Object[] args = { pattern, stack } ;
89          Object result = invoke( tree, TagTree.class, "isTailMatch", argClasses,
90                  args ) ;
91          return ( ( Boolean ) result ).booleanValue() ;
92      }
93  
94  
95      /***
96       * Used to white box test the private isReverseTailMatch() method of the
97       * TagTree.
98       *
99       * @param tree the tree instance to test
100      * @param pattern the pattern arg
101      * @param stack the stack arg
102      * @return the resultant true or false return value
103      */
104     private boolean isReverseTailMatch( TagTree tree, int[] pattern,
105                                         Stack stack )
106     {
107         Class[] argClasses = { pattern.getClass(), Stack.class } ;
108         Object[] args = { pattern, stack } ;
109         Object result = invoke( tree, TagTree.class, "isReverseTailMatch",
110                 argClasses, args ) ;
111         return ( ( Boolean ) result ).booleanValue() ;
112     }
113 
114 
115     /***
116      * Tests the private isTailMatch() method.
117      */
118     public void testIsTailMatch()
119     {
120         TagTree tree = new TagTree() ;
121         int[] pattern = {TagTree.WILDCARD,1,2,3} ;
122         Stack stack = new Stack() ;
123         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
124         stack.push( new Integer( 5 ) ) ;
125         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
126         stack.push( new Integer( 6 ) ) ;
127         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
128         stack.push( new Integer( 1 ) ) ;
129         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
130         stack.push( new Integer( 2 ) ) ;
131         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
132         stack.push( new Integer( 3 ) ) ;
133         assertTrue( isTailMatch( tree, pattern, stack ) ) ;
134 
135         tree = new TagTree() ;
136         pattern = new int[]{TagTree.WILDCARD} ;
137         stack = new Stack() ;
138         assertTrue( isTailMatch( tree, pattern, stack ) ) ;
139 
140         tree = new TagTree() ;
141         pattern = new int[]{} ;
142         stack = new Stack() ;
143         assertTrue( isTailMatch( tree, pattern, stack ) ) ;
144 
145         tree = new TagTree() ;
146         pattern = new int[]{TagTree.WILDCARD, 1} ;
147         stack = new Stack() ;
148         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
149         stack.push( new Integer( 2 ) ) ;
150         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
151         stack.push( new Integer( 1 ) ) ;
152         assertTrue( isTailMatch( tree, pattern, stack ) ) ;
153         stack.push( new Integer( 1 ) ) ;
154         assertTrue( isTailMatch( tree, pattern, stack ) ) ;
155         stack.push( new Integer( 2 ) ) ;
156         assertFalse( isTailMatch( tree, pattern, stack ) ) ;
157     }
158 
159 
160     /***
161      * Tests the private isTailMatch() method.
162      */
163     public void testIsReverseTailMatch()
164     {
165         TagTree tree = new TagTree() ;
166         int[] pattern = {TagTree.WILDCARD,1,2,3} ;
167         Stack stack = new Stack() ;
168         stack.push( new Integer( 3 ) ) ;
169         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
170         stack.push( new Integer( 2 ) ) ;
171         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
172         stack.push( new Integer( 1 ) ) ;
173         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
174 
175         tree = new TagTree() ;
176         pattern = new int[]{TagTree.WILDCARD} ;
177         stack = new Stack() ;
178         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
179 
180         tree = new TagTree() ;
181         pattern = new int[]{} ;
182         stack = new Stack() ;
183         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
184 
185         tree = new TagTree() ;
186         pattern = new int[]{TagTree.WILDCARD, 1, 1} ;
187         stack = new Stack() ;
188         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
189         stack.push( new Integer( 1 ) ) ;
190         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
191         stack.push( new Integer( 1 ) ) ;
192         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
193         stack.push( new Integer( 2 ) ) ;
194         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
195         stack.push( new Integer( 3 ) ) ;
196         assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
197 
198         tree = new TagTree() ;
199         pattern = new int[]{TagTree.WILDCARD, 1, 2} ;
200         stack = new Stack() ;
201         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
202         stack.push( new Integer( 1 ) ) ;
203         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
204         stack.push( new Integer( 1 ) ) ;
205         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
206         stack.push( new Integer( 2 ) ) ;
207         assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
208     }
209 
210 
211     /***
212      * Used to white box test the private addWildRuleToNormalTree() method of
213      * the TagTree class.
214      *
215      * @param tree the tree instance to test
216      * @param pattern the 1st int[] pattern arg
217      * @param rule the 2nd Rule arg
218      * @param stack the 3rd Stack arg
219      * @param node the last TagNode arg
220      */
221     public void addWildRuleToNormalTree( TagTree tree, int[] pattern,
222                                          Rule rule, Stack stack, TagNode node )
223     {
224         Class[] argClasses = {
225             pattern.getClass(), Rule.class, Stack.class, TagNode.class
226         } ;
227 
228         Object[] args = { pattern, rule, stack, node } ;
229         invoke( tree, TagTree.class, "addWildRuleToNormalTree",
230                 argClasses, args ) ;
231     }
232 
233 
234     /***
235      * Tests various combinations of wild card patterns and trees to make sure
236      * all is working with addWildRuleToNormalTree().
237      */
238     public void testAddWildRuleToNormalTree2()
239     {
240         TagTree tree = new TagTree() ;
241         int[] pattern = {1,2,3} ;
242         Rule r0 = new MockRule() ;
243         tree.addRule( pattern, r0 ) ;
244 
245         // Walk the branch of tag nodes and validate contents along the way
246         TagNode node = getNormalNode( tree, 1 ) ;
247         assertEquals( 0, node.getRules().size() ) ;
248         node = node.getChild( new Integer( 2 ) ) ;
249         assertEquals( 0, node.getRules().size() ) ;
250         node = node.getChild( new Integer( 3 ) ) ;
251         assertEquals( 1, node.getRules().size() ) ;
252         assertEquals( r0, node.getRules().get( 0 ) ) ;
253 
254         // setup the first wild card addition but it should not match
255         int[] wildpat = { TagTree.WILDCARD,1,2} ;
256         Rule r1 = new MockRule() ;
257         addWildRuleToNormalTree( tree, wildpat, r1, new Stack(), node ) ;
258 
259         // the pattern *,1,2 should NOT match 1,2,3
260         // walk of the branch of tag nodes and validate contents along the way
261         node = getNormalNode( tree, 1 ) ;
262         assertEquals( 0, node.getRules().size() ) ;
263         node = node.getChild( new Integer( 2 ) ) ;
264         assertEquals( 0, node.getRules().size() ) ;
265         node = node.getChild( new Integer( 3 ) ) ;
266         assertEquals( 1, node.getRules().size() ) ;
267         assertEquals( r0, node.getRules().get( 0 ) ) ;
268 
269         // now try a matching the pattern with *,1,2,3 so r1 should be present
270         wildpat = new int[]{TagTree.WILDCARD, 1, 2, 3} ;
271         r1 = new MockRule() ;
272         node = getNormalNode( tree, 1 ) ;
273         addWildRuleToNormalTree( tree, wildpat, r1, new Stack(), node ) ;
274 
275         // the pattern *,1,2,3 should match 1,2,3 now
276         // walk of the branch of tag nodes and validate contents along the way
277         assertEquals( 0, node.getRules().size() ) ;
278         node = node.getChild( new Integer( 2 ) ) ;
279         assertEquals( 0, node.getRules().size() ) ;
280         node = node.getChild( new Integer( 3 ) ) ;
281         assertEquals( 2, node.getRules().size() ) ;
282         assertEquals( r0, node.getRules().get( 0 ) ) ;
283         assertEquals( r1, node.getRules().get( 1 ) ) ;
284 
285         // now try a less specific matching the pattern *,2,3
286         wildpat = new int[]{TagTree.WILDCARD, 2, 3} ;
287         Rule r2 = new MockRule() ;
288         node = getNormalNode( tree, 1 ) ;
289         addWildRuleToNormalTree( tree, wildpat, r2, new Stack(), node ) ;
290 
291         // the pattern *,2,3 should match 1,2,3 now
292         // walk of the branch of tag nodes and validate contents along the way
293         assertEquals( 0, node.getRules().size() ) ;
294         node = node.getChild( new Integer( 2 ) ) ;
295         assertEquals( 0, node.getRules().size() ) ;
296         node = node.getChild( new Integer( 3 ) ) ;
297         assertEquals( 3, node.getRules().size() ) ;
298         assertEquals( r0, node.getRules().get( 0 ) ) ;
299         assertEquals( r1, node.getRules().get( 1 ) ) ;
300         assertEquals( r2, node.getRules().get( 2 ) ) ;
301 
302         // now try least specific matching using pattern *,3
303         wildpat = new int[]{TagTree.WILDCARD, 3} ;
304         Rule r3 = new MockRule() ;
305         node = getNormalNode( tree, 1 ) ;
306         addWildRuleToNormalTree( tree, wildpat, r3, new Stack(), node ) ;
307 
308         // the pattern *,3 should match 1,2,3 now
309         // walk of the branch of tag nodes and validate contents along the way
310         assertEquals( 0, node.getRules().size() ) ;
311         node = node.getChild( new Integer( 2 ) ) ;
312         assertEquals( 0, node.getRules().size() ) ;
313         node = node.getChild( new Integer( 3 ) ) ;
314         assertEquals( 4, node.getRules().size() ) ;
315         assertEquals( r0, node.getRules().get( 0 ) ) ;
316         assertEquals( r1, node.getRules().get( 1 ) ) ;
317         assertEquals( r2, node.getRules().get( 2 ) ) ;
318         assertEquals( r3, node.getRules().get( 3 ) ) ;
319     }
320 
321 
322     /***
323      * Tests to see that we do not add the rule with wild card pattern more
324      * than once to a node in the normal tree by first checking if it already
325      * contains that rule before a rule add operation to the node.
326      */
327     public void testAddWildRuleToNormalTree1()
328     {
329         TagTree tree = new TagTree() ;
330         int[] pattern = {1,2,3} ;
331         Rule r0 = new MockRule() ;
332         tree.addRule( pattern, r0 ) ;
333 
334         int[] wildpat = { TagTree.WILDCARD,1,2,3} ;
335         TagNode node = getNormalNode( tree, 1 ) ;
336 
337         // see if the rule r0 is added - should not be!
338         addWildRuleToNormalTree( tree, wildpat, r0, new Stack(), node ) ;
339         node = node.getChild( new Integer( 2 ) ).getChild( new Integer( 3 ) ) ;
340         List rules = node.getRules() ;
341 
342         // only one copy of r0 should exist
343         assertEquals( 1, rules.size() ) ;
344         assertEquals( r0, rules.get( 0 ) ) ;
345     }
346 
347 
348     /***
349      * Used to white box test the private addWildRuleToNormalTree() method of
350      * the TagTree class.
351      *
352      * @param tree the tree instance to test
353      * @param pattern the 1st int[] pattern arg
354      * @param rule the 2nd Rule arg
355      * @param stack the 3rd Stack arg
356      * @param node the last TagNode arg
357      */
358     public void addWildRuleToWildTree( TagTree tree, int[] pattern,
359                                        Rule rule, Stack stack, TagNode node )
360     {
361         Class[] argClasses = {
362             pattern.getClass(), Rule.class, Stack.class, TagNode.class
363         } ;
364 
365         Object[] args = { pattern, rule, stack, node } ;
366         invoke( tree, TagTree.class, "addWildRuleToWildTree", argClasses,
367                 args ) ;
368     }
369 
370 
371 
372     /***
373      * Tests various combinations of wild card patterns and trees to make sure
374      * all is working with addWildRuleToWildTree().
375      */
376     public void testAddWildRuleToWildTree2()
377     {
378         TagTree tree = new TagTree() ;
379         TagNode n0 = new TagNode( new Integer( 2 ) ) ;
380         TagNode n1 = new TagNode( new Integer( 1 ) ) ;
381         TagNode n2 = new TagNode( new Integer( 3 ) ) ;
382         n0.addNode( n1 ) ;
383         n1.addNode( n2 ) ;
384         HashMap wildNodes = ( HashMap ) getMember( "wildNodes", tree ) ;
385         wildNodes.put( new Integer( 2 ), n0 ) ;
386 
387         int[] pattern = {TagTree.WILDCARD,1,2} ;
388         Rule r0 = new MockRule() ;
389         addWildRuleToWildTree( tree, pattern, r0, new Stack(), n0 ) ;
390 
391         // the pattern *,1,2 should match at nodes 2-1 and 2-1-3
392         assertEquals( 0, n0.getRules().size() ) ;
393         assertEquals( 1, n1.getRules().size() ) ;
394         assertEquals( r0, n1.getRules().get( 0 ) ) ;
395         assertEquals( 1, n2.getRules().size() ) ;
396         assertEquals( r0, n2.getRules().get( 0 ) ) ;
397     }
398 
399     /***
400      * Tests various combinations of wild card patterns and trees to make sure
401      * all is working with addWildRuleToWildTree().
402      */
403     public void testAddWildRuleToWildTree1()
404     {
405         TagTree tree = new TagTree() ;
406         TagNode n0 = new TagNode( new Integer( 2 ) ) ;
407         TagNode n1 = new TagNode( new Integer( 1 ) ) ;
408         TagNode n2 = new TagNode( new Integer( 3 ) ) ;
409         n0.addNode( n1 ) ;
410         n1.addNode( n2 ) ;
411         HashMap wildNodes = ( HashMap ) getMember( "wildNodes", tree ) ;
412         wildNodes.put( new Integer( 2 ), n0 ) ;
413 
414         int[] pattern = {TagTree.WILDCARD,1,2} ;
415         Rule r0 = new MockRule() ;
416         n1.addRule( r0 );
417         n2.addRule( r0 );
418         addWildRuleToWildTree( tree, pattern, r0, new Stack(), n0 ) ;
419 
420         // the pattern *,1,2 should match at nodes 2-1 and 2-1-3
421         assertEquals( 0, n0.getRules().size() ) ;
422         assertEquals( 1, n1.getRules().size() ) ;
423         assertEquals( r0, n1.getRules().get( 0 ) ) ;
424         assertEquals( 1, n2.getRules().size() ) ;
425         assertEquals( r0, n2.getRules().get( 0 ) ) ;
426     }
427 
428 
429     /***
430      * Tests the addRule method of the tree.
431      */
432     public void testAddRuleNormal()
433     {
434         TagTree tree = new TagTree() ;
435         int[] pattern = {1,2,3} ;
436         tree.addRule( pattern, new MockRule() ) ;
437         assertNull( getNormalNode( tree, 4 ) ) ;
438 
439         TagNode node = getNormalNode( tree, 1 ) ;
440         assertNotNull( node ) ;
441         node = node.getChild( new Integer(2) ) ;
442         assertNotNull( node ) ;
443         node = node.getChild( new Integer(3) ) ;
444         assertNotNull( node ) ;
445         node = node.getChild( new Integer(4) ) ;
446         assertNull( node ) ;
447 
448         tree.addRule( pattern, new MockRule() ) ;
449     }
450 
451 
452     /***
453      * Used to white box test the private addWildRule() method of the
454      * TagTree.
455      *
456      * @param tree the tree instance to test
457      * @param pattern the pattern arg
458      * @param rule the Rule arg
459      */
460     private void addWildRule( TagTree tree, int[] pattern, Rule rule )
461     {
462         Class[] argClasses = { pattern.getClass(), Rule.class } ;
463         Object[] args = { pattern, rule } ;
464         invoke( tree, TagTree.class, "addWildRule", argClasses, args ) ;
465     }
466 
467 
468     /***
469      * Used to white box test the private addNormalRule() method of the
470      * TagTree.
471      *
472      * @param tree the tree instance to test
473      * @param pattern the pattern arg
474      * @param rule the Rule arg
475      */
476     private void addNormalRule( TagTree tree, int[] pattern, Rule rule )
477     {
478         Class[] argClasses = { pattern.getClass(), Rule.class } ;
479         Object[] args = { pattern, rule } ;
480         invoke( tree, TagTree.class, "addNormalRule",
481                 argClasses, args ) ;
482     }
483 
484 
485     /***
486      * Tests the addRule method of the tree.
487      */
488     public void testAddWildRule1()
489     {
490         TagTree tree = new TagTree() ;
491         int[] pattern = {TagTree.WILDCARD,1,2,3} ;
492         Rule r0 = new MockRule() ;
493         addWildRule( tree, pattern, r0 );
494         assertNull( getWildNode( tree, 4 ) ) ;
495 
496         TagNode node = getWildNode( tree, 3 ) ;
497         assertNotNull( node ) ;
498         node = node.getChild( new Integer(2) ) ;
499         assertNotNull( node ) ;
500         node = node.getChild( new Integer(1) ) ;
501         assertNotNull( node ) ;
502         assertEquals( 1, node.getRules().size() ) ;
503         assertEquals( r0, node.getRules().get( 0 ) ) ;
504         node = node.getChild( new Integer(4) ) ;
505         assertNull( node ) ;
506     }
507 
508 
509     /***
510      * Tests the addRule method of the tree.
511      */
512     public void testAddWildRule2()
513     {
514         TagTree tree = new TagTree() ;
515         int[] pattern0 = {TagTree.WILDCARD,1,2} ;
516         int[] pattern1 = {3,1,2} ;
517         int[] pattern2 = {TagTree.WILDCARD,2} ;
518         Rule r0 = new MockRule() ;
519         Rule r1 = new MockRule() ;
520         Rule r2 = new MockRule() ;
521         addNormalRule( tree, pattern1, r1 ) ;
522         addWildRule( tree, pattern0, r0 );
523         assertNull( getWildNode( tree, 4 ) ) ;
524 
525         // now test that we have made the addition to the wild tree
526         TagNode node = getWildNode( tree, 2 ) ;
527         assertNotNull( node ) ;
528         node = node.getChild( new Integer(1) ) ;
529         assertNotNull( node ) ;
530         assertEquals( 1, node.getRules().size() ) ;
531         assertEquals( r0, node.getRules().get( 0 ) ) ;
532 
533         node = node.getChild( new Integer(4) ) ;
534         assertNull( node ) ;
535 
536         // now test the normal tree
537         HashMap normNodes = ( HashMap ) getMember( "normNodes", tree ) ;
538         assertEquals( 1, normNodes.size() ) ;
539         node = getNormalNode( tree, 3 ) ;
540         assertNotNull( node ) ;
541         assertEquals( 0, node.getRules().size() ) ;
542         node = node.getChild( new Integer( 1 ) ) ;
543         assertNotNull( node ) ;
544         assertEquals( 0, node.getRules().size() ) ;
545         node = node.getChild( new Integer( 2 ) ) ;
546         assertNotNull( node ) ;
547         assertEquals( 2, node.getRules().size() ) ;
548         assertEquals( r1, node.getRules().get( 0 ) ) ;
549         assertEquals( r0, node.getRules().get( 1 ) ) ;
550 
551         // now we'll add the other wild card and see if it adds correctly
552         addWildRule( tree, pattern2, r2 ) ;
553 
554         // test that we have made the r2 addition to the places in wild tree
555         node = getWildNode( tree, 2 ) ;
556         assertNotNull( node ) ;
557         assertEquals( 1, node.getRules().size() ) ;
558         assertEquals( r2, node.getRules().get( 0 ) ) ;
559         node = node.getChild( new Integer(1) ) ;
560         assertNotNull( node ) ;
561         assertEquals( 2, node.getRules().size() ) ;
562         assertEquals( r0, node.getRules().get( 0 ) ) ;
563         assertEquals( r2, node.getRules().get( 1 ) ) ;
564         assertTrue( node.isLeaf() ) ;
565 
566         // test that we have added r2 to the normal tree
567         assertEquals( 1, normNodes.size() ) ;
568         node = getNormalNode( tree, 3 ) ;
569         assertNotNull( node ) ;
570         assertEquals( 0, node.getRules().size() ) ;
571         node = node.getChild( new Integer( 1 ) ) ;
572         assertNotNull( node ) ;
573         assertEquals( 0, node.getRules().size() ) ;
574         node = node.getChild( new Integer( 2 ) ) ;
575         assertNotNull( node ) ;
576         assertEquals( 3, node.getRules().size() ) ;
577         assertEquals( r1, node.getRules().get( 0 ) ) ;
578         assertEquals( r0, node.getRules().get( 1 ) ) ;
579         assertEquals( r2, node.getRules().get( 2 ) ) ;
580 
581         // control
582         node = node.getChild( new Integer(4) ) ;
583         assertNull( node ) ;
584     }
585 
586 
587     /***
588      * Tests the addNormalRule method of the tree after registering
589      * rule patterns using wild cards.
590      */
591     public void testAddNormalRule1()
592     {
593         TagTree tree = new TagTree() ;
594         int[] pattern0 = {TagTree.WILDCARD,1,2} ;
595         int[] pattern1 = {3,1,2} ;
596         int[] pattern2 = {TagTree.WILDCARD,2} ;
597         Rule r0 = new MockRule() ;
598         Rule r1 = new MockRule() ;
599         Rule r2 = new MockRule() ;
600         addNormalRule( tree, pattern1, r1 ) ;
601         addWildRule( tree, pattern0, r0 );
602         assertNull( getWildNode( tree, 4 ) ) ;
603 
604         // now test that we have made the addition to the wild tree
605         TagNode node = getWildNode( tree, 2 ) ;
606         assertNotNull( node ) ;
607         node = node.getChild( new Integer(1) ) ;
608         assertNotNull( node ) ;
609         assertEquals( 1, node.getRules().size() ) ;
610         assertEquals( r0, node.getRules().get( 0 ) ) ;
611 
612         node = node.getChild( new Integer(4) ) ;
613         assertNull( node ) ;
614 
615         // now test the normal tree
616         HashMap normNodes = ( HashMap ) getMember( "normNodes", tree ) ;
617         assertEquals( 1, normNodes.size() ) ;
618         node = getNormalNode( tree, 3 ) ;
619         assertNotNull( node ) ;
620         assertEquals( 0, node.getRules().size() ) ;
621         node = node.getChild( new Integer( 1 ) ) ;
622         assertNotNull( node ) ;
623         assertEquals( 0, node.getRules().size() ) ;
624         node = node.getChild( new Integer( 2 ) ) ;
625         assertNotNull( node ) ;
626         assertEquals( 2, node.getRules().size() ) ;
627         assertEquals( r1, node.getRules().get( 0 ) ) ;
628         assertEquals( r0, node.getRules().get( 1 ) ) ;
629 
630         // now we'll add the other wild card and see if it adds correctly
631         addWildRule( tree, pattern2, r2 ) ;
632 
633         // test that we have made the r2 addition to the places in wild tree
634         node = getWildNode( tree, 2 ) ;
635         assertNotNull( node ) ;
636         assertEquals( 1, node.getRules().size() ) ;
637         assertEquals( r2, node.getRules().get( 0 ) ) ;
638         node = node.getChild( new Integer(1) ) ;
639         assertNotNull( node ) ;
640         assertEquals( 2, node.getRules().size() ) ;
641         assertEquals( r0, node.getRules().get( 0 ) ) ;
642         assertEquals( r2, node.getRules().get( 1 ) ) ;
643         assertTrue( node.isLeaf() ) ;
644 
645         // test that we have added r2 to the normal tree
646         assertEquals( 1, normNodes.size() ) ;
647         node = getNormalNode( tree, 3 ) ;
648         assertNotNull( node ) ;
649         assertEquals( 0, node.getRules().size() ) ;
650         node = node.getChild( new Integer( 1 ) ) ;
651         assertNotNull( node ) ;
652         assertEquals( 0, node.getRules().size() ) ;
653         node = node.getChild( new Integer( 2 ) ) ;
654         assertNotNull( node ) ;
655         assertEquals( 3, node.getRules().size() ) ;
656         assertEquals( r1, node.getRules().get( 0 ) ) ;
657         assertEquals( r0, node.getRules().get( 1 ) ) ;
658         assertEquals( r2, node.getRules().get( 2 ) ) ;
659 
660         // control
661         node = node.getChild( new Integer(4) ) ;
662         assertNull( node ) ;
663 
664         // lets add a normal node to the normal tree matching these patterns
665         int[] pattern3 = {8,1,2} ;
666         Rule r3 = new MockRule() ;
667         List wildRegistrations = ( List )
668                 getMember( "wildRegistrations", tree ) ;
669         wildRegistrations.add( new RuleRegistration( pattern0, r0 ) ) ;
670         wildRegistrations.add( new RuleRegistration( pattern2, r2 ) ) ;
671         addNormalRule( tree, pattern3, r3 ) ;
672 
673         // test if we have added the rules and nodes correctly
674         assertEquals( 2, normNodes.size() ) ;
675         node = getNormalNode( tree, 8 ) ;
676         assertNotNull( node ) ;
677         assertEquals( 0, node.getRules().size() ) ;
678         node = node.getChild( new Integer( 1 ) ) ;
679         assertNotNull( node ) ;
680         assertEquals( 0, node.getRules().size() ) ;
681         node = node.getChild( new Integer( 2 ) ) ;
682         assertNotNull( node ) ;
683         assertEquals( 3, node.getRules().size() ) ;
684         assertEquals( r0, node.getRules().get( 0 ) ) ;
685         assertEquals( r2, node.getRules().get( 1 ) ) ;
686         assertEquals( r3, node.getRules().get( 2 ) ) ;
687     }
688 
689 
690     /***
691      * Tests the TagTree.match(int[]) method.
692      */
693     public void testMatchintArray()
694     {
695         TagTree tree = new TagTree() ;
696         int[] pattern0 = {1,2,3} ;
697         int[] pattern1 = {4,2,7} ;
698         int[] pattern2 = {1,5,3} ;
699         Rule rule0 = new MockRule() ;
700         Rule rule1 = new MockRule() ;
701         Rule rule2 = new MockRule() ;
702         tree.addRule( pattern0, rule0 ) ;
703         tree.addRule( pattern1, rule1 ) ;
704         tree.addRule( pattern2, rule2 ) ;
705         assertEquals( rule0, ( (List) tree.match( pattern0 ) ).get(0) ) ;
706         assertEquals( rule1, ( (List) tree.match( pattern1 ) ).get(0) ) ;
707         assertEquals( rule2, ( (List) tree.match( pattern2 ) ).get(0) ) ;
708 
709         assertNotSame( rule0, ( (List) tree.match( pattern1 ) ).get(0) ) ;
710         assertNotSame( rule1, ( (List) tree.match( pattern2 ) ).get(0) ) ;
711         assertNotSame( rule2, ( (List) tree.match( pattern0 ) ).get(0) ) ;
712 
713         int[] pattern3 = { 12 } ;
714         tree.match( pattern3 ) ;
715     }
716 
717 
718     /***
719      * Tests the TagTree.match(IntStack) method.
720      */
721     public void testMatchIntStack()
722     {
723         TagTree tree = new TagTree() ;
724         int[] pattern0 = {1,2,3} ;
725         int[] pattern1 = {4,2,7} ;
726         int[] pattern2 = {1,5,3} ;
727         Rule rule0 = new MockRule() ;
728         Rule rule1 = new MockRule() ;
729         Rule rule2 = new MockRule() ;
730         tree.addRule( pattern0, rule0 ) ;
731         tree.addRule( pattern1, rule1 ) ;
732         tree.addRule( pattern2, rule2 ) ;
733         
734         assertEquals( rule0, ( (List) tree.match( new IntStack( pattern0 ) ) )
735                 .get(0) ) ;
736         assertEquals( rule1, ( (List) tree.match( new IntStack( pattern1 ) ) )
737                 .get(0) ) ;
738         assertEquals( rule2, ( (List) tree.match( new IntStack( pattern2 ) ) )
739                 .get(0) ) ;
740         assertNotSame( rule0, ( (List) tree.match( new IntStack( pattern1 ) ) )
741                 .get(0) ) ;
742         assertNotSame( rule1, ( (List) tree.match( new IntStack( pattern2 ) ) )
743                 .get(0) ) ;
744         assertNotSame( rule2, ( (List) tree.match( new IntStack( pattern0 ) ) )
745                 .get(0) ) ;
746     }
747 
748 
749     /***
750      * Tests the TagTree.getNormalNode(int[]) method.
751      */
752     public void testGetNodeintArray()
753     {
754         TagTree tree = new TagTree() ;
755         int[] pattern0 = {1,2,3} ;
756         int[] pattern1 = {4,2,7} ;
757         int[] pattern2 = {1,5,3} ;
758         Rule rule0 = new MockRule() ;
759         Rule rule1 = new MockRule() ;
760         Rule rule2 = new MockRule() ;
761         tree.addRule( pattern0, rule0 ) ;
762         tree.addRule( pattern1, rule1 ) ;
763         tree.addRule( pattern2, rule2 ) ;
764 
765         int[] pattern3 = { 1, 23 } ;
766         assertNull( tree.getNode( pattern3 ) ) ;
767     }
768 
769 
770     class MockRule extends AbstractRule { }
771 }