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