01: /**
02: * Copyright (c) 2004-2006 Regents of the University of California.
03: * See "license-prefuse.txt" for licensing terms.
04: */package prefuse.data.util;
05:
06: import java.util.ArrayList;
07: import java.util.Iterator;
08:
09: import prefuse.data.Node;
10:
11: /**
12: * A depth-first iterator over the subtree rooted at given node.
13: *
14: * @author <a href="http://jheer.org">jeffrey heer</a>
15: */
16: public class TreeNodeIterator implements Iterator {
17:
18: private ArrayList m_stack;
19: private Node m_root;
20: private boolean m_preorder = true;
21:
22: /**
23: * Create a new TreeNodeIterator over the given subtree.
24: * @param root the root of the subtree to traverse
25: */
26: public TreeNodeIterator(Node root) {
27: this (root, true);
28: }
29:
30: /**
31: * Create a new TreeNodeIterator over the given subtree.
32: * @param root the root of the subtree to traverse
33: * @param preorder true to use a pre-order traversal, false
34: * for a post-order traversal
35: */
36: public TreeNodeIterator(Node root, boolean preorder) {
37: m_preorder = preorder;
38: m_root = root;
39: m_stack = new ArrayList();
40: m_stack.add(root);
41:
42: if (!preorder) {
43: for (Node n = root.getChild(0); n != null; n = n
44: .getChild(0))
45: m_stack.add(n);
46: }
47:
48: }
49:
50: /**
51: * @see java.util.Iterator#hasNext()
52: */
53: public boolean hasNext() {
54: return !m_stack.isEmpty();
55: }
56:
57: /**
58: * @see java.util.Iterator#next()
59: */
60: public Object next() {
61: Node c, x = null;
62: if (m_preorder) {
63: x = (Node) m_stack.get(m_stack.size() - 1);
64: if ((c = x.getChild(0)) != null) {
65: m_stack.add(c);
66: } else if ((c = x.getNextSibling()) != null) {
67: m_stack.set(m_stack.size() - 1, c);
68: } else {
69: m_stack.remove(m_stack.size() - 1);
70: while (!m_stack.isEmpty()) {
71: c = (Node) m_stack.remove(m_stack.size() - 1);
72: if (c == m_root) {
73: break;
74: } else if ((c = c.getNextSibling()) != null) {
75: m_stack.add(c);
76: break;
77: }
78: }
79: }
80: } else {
81: x = (Node) m_stack.remove(m_stack.size() - 1);
82: if (x != m_root && (c = x.getNextSibling()) != null) {
83: for (; c != null; c = c.getChild(0)) {
84: m_stack.add(c);
85: }
86: }
87: }
88: return x;
89: }
90:
91: /**
92: * Throws an UnsupportedOperationException
93: * @see java.util.Iterator#remove()
94: */
95: public void remove() {
96: throw new UnsupportedOperationException("Remove not supported");
97: }
98:
99: } // end of class TreeNodeIterator
|