KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > persistence > antlr > ASTIterator


1 package persistence.antlr;
2
3 /* ANTLR Translator Generator
4  * Project led by Terence Parr at http://www.jGuru.com
5  * Software rights: http://www.antlr.org/license.html
6  *
7  */
8
9 import persistence.antlr.collections.AST;
10
11 public class ASTIterator {
12     protected AST cursor = null;
13     protected AST original = null;
14
15
16     public ASTIterator(AST t) {
17         original = cursor = t;
18     }
19
20     /** Is 'sub' a subtree of 't' beginning at the root? */
21     public boolean isSubtree(AST t, AST sub) {
22         AST sibling;
23
24         // the empty tree is always a subset of any tree.
25 if (sub == null) {
26             return true;
27         }
28
29         // if the tree is empty, return true if the subtree template is too.
30 if (t == null) {
31             if (sub != null) return false;
32             return true;
33         }
34
35         // Otherwise, start walking sibling lists. First mismatch, return false.
36 for (sibling = t;
37              sibling != null && sub != null;
38              sibling = sibling.getNextSibling(), sub = sub.getNextSibling()) {
39             // as a quick optimization, check roots first.
40 if (sibling.getType() != sub.getType()) return false;
41             // if roots match, do full match test on children.
42 if (sibling.getFirstChild() != null) {
43                 if (!isSubtree(sibling.getFirstChild(), sub.getFirstChild())) return false;
44             }
45         }
46         return true;
47     }
48
49     /** Find the next subtree with structure and token types equal to
50      * those of 'template'.
51      */
52     public AST next(AST template) {
53         AST t = null;
54         AST sibling = null;
55
56         if (cursor == null) { // do nothing if no tree to work on
57 return null;
58         }
59
60         // Start walking sibling list looking for subtree matches.
61 for (; cursor != null; cursor = cursor.getNextSibling()) {
62             // as a quick optimization, check roots first.
63 if (cursor.getType() == template.getType()) {
64                 // if roots match, do full match test on children.
65 if (cursor.getFirstChild() != null) {
66                     if (isSubtree(cursor.getFirstChild(), template.getFirstChild())) {
67                         return cursor;
68                     }
69                 }
70             }
71         }
72         return t;
73     }
74 }
75
Popular Tags