KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > antlr > ASTIterator


1 package antlr;
2
3 /* ANTLR Translator Generator
4  * Project led by Terence Parr at http://www.jGuru.com
5  * Software rights: http://www.antlr.org/RIGHTS.html
6  *
7  * $Id: //depot/code/org.antlr/main/main/antlr/ASTIterator.java#4 $
8  */

9
10 import antlr.collections.AST;
11
12 public class ASTIterator {
13     protected AST cursor = null;
14     protected AST original = null;
15
16
17     public ASTIterator(AST t) {
18         original = cursor = t;
19     }
20
21     /** Is 'sub' a subtree of 't' beginning at the root? */
22     public boolean isSubtree(AST t, AST sub) {
23         AST sibling;
24
25         // the empty tree is always a subset of any tree.
26
if (sub == null) {
27             return true;
28         }
29
30         // if the tree is empty, return true if the subtree template is too.
31
if (t == null) {
32             if (sub != null) return false;
33             return true;
34         }
35
36         // Otherwise, start walking sibling lists. First mismatch, return false.
37
for (sibling = t;
38              sibling != null && sub != null;
39              sibling = sibling.getNextSibling(), sub = sub.getNextSibling()) {
40             // as a quick optimization, check roots first.
41
if (sibling.getType() != sub.getType()) return false;
42             // if roots match, do full match test on children.
43
if (sibling.getFirstChild() != null) {
44                 if (!isSubtree(sibling.getFirstChild(), sub.getFirstChild())) return false;
45             }
46         }
47         return true;
48     }
49
50     /** Find the next subtree with structure and token types equal to
51      * those of 'template'.
52      */

53     public AST next(AST template) {
54         AST t = null;
55         AST sibling = null;
56
57         if (cursor == null) { // do nothing if no tree to work on
58
return null;
59         }
60
61         // Start walking sibling list looking for subtree matches.
62
for (; cursor != null; cursor = cursor.getNextSibling()) {
63             // as a quick optimization, check roots first.
64
if (cursor.getType() == template.getType()) {
65                 // if roots match, do full match test on children.
66
if (cursor.getFirstChild() != null) {
67                     if (isSubtree(cursor.getFirstChild(), template.getFirstChild())) {
68                         return cursor;
69                     }
70                 }
71             }
72         }
73         return t;
74     }
75 }
76
Popular Tags