01: // $Id: ASTParentsFirstIterator.java 7460 2005-07-12 20:27:29Z steveebersole $
02: package org.hibernate.hql.ast.util;
03:
04: import java.util.Iterator;
05: import java.util.LinkedList;
06:
07: import antlr.collections.AST;
08:
09: /**
10: * Depth first iteration of an ANTLR AST.
11: *
12: * @author josh Sep 25, 2004 7:44:39 AM
13: */
14: public class ASTParentsFirstIterator implements Iterator {
15: private AST next, current, tree;
16: private LinkedList parents = new LinkedList();
17:
18: public void remove() {
19: throw new UnsupportedOperationException(
20: "remove() is not supported");
21: }
22:
23: public boolean hasNext() {
24: return next != null;
25: }
26:
27: public Object next() {
28: return nextNode();
29: }
30:
31: public ASTParentsFirstIterator(AST tree) {
32: this .tree = next = tree;
33: }
34:
35: public AST nextNode() {
36: current = next;
37: if (next != null) {
38: AST child = next.getFirstChild();
39: if (child == null) {
40: AST sibling = next.getNextSibling();
41: if (sibling == null) {
42: AST parent = pop();
43: while (parent != null
44: && parent.getNextSibling() == null)
45: parent = pop();
46: next = (parent != null) ? parent.getNextSibling()
47: : null;
48: } else {
49: next = sibling;
50: }
51: } else {
52: if (next != tree) {
53: push(next);
54: }
55: next = child;
56: }
57: }
58: return current;
59: }
60:
61: private void push(AST parent) {
62: parents.addFirst(parent);
63: }
64:
65: private AST pop() {
66: if (parents.size() == 0) {
67: return null;
68: } else {
69: return (AST) parents.removeFirst();
70: }
71: }
72:
73: }
|