001: /*
002: * Copyright (c) 1998-2008 Caucho Technology -- all rights reserved
003: *
004: * This file is part of Resin(R) Open Source
005: *
006: * Each copy or derived work must preserve the copyright notice and this
007: * notice unmodified.
008: *
009: * Resin Open Source is free software; you can redistribute it and/or modify
010: * it under the terms of the GNU General Public License as published by
011: * the Free Software Foundation; either version 2 of the License, or
012: * (at your option) any later version.
013: *
014: * Resin Open Source is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
017: * of NON-INFRINGEMENT. See the GNU General Public License for more
018: * details.
019: *
020: * You should have received a copy of the GNU General Public License
021: * along with Resin Open Source; if not, write to the
022: * Free SoftwareFoundation, Inc.
023: * 59 Temple Place, Suite 330
024: * Boston, MA 02111-1307 USA
025: *
026: * @author Scott Ferguson
027: */
028:
029: package com.caucho.util;
030:
031: import java.util.Iterator;
032:
033: public class Tree {
034: private Tree parent;
035:
036: private Tree next;
037: private Tree previous;
038:
039: private Tree first;
040: private Tree last;
041:
042: private Object data;
043:
044: public Tree(Object data) {
045: this .data = data;
046: }
047:
048: public Object getData() {
049: return data;
050: }
051:
052: public void setData(Object data) {
053: this .data = data;
054: }
055:
056: public Tree getParent() {
057: return parent;
058: }
059:
060: public Tree getNext() {
061: return next;
062: }
063:
064: public Tree getNextPreorder() {
065: if (first != null)
066: return first;
067:
068: for (Tree ptr = this ; ptr != null; ptr = ptr.parent) {
069: if (ptr.next != null)
070: return ptr.next;
071: }
072:
073: return null;
074: }
075:
076: public Tree getPreviousPreorder() {
077: Tree ptr;
078:
079: if ((ptr = previous) != null) {
080: for (; ptr.last != null; ptr = ptr.last) {
081: }
082:
083: return ptr;
084: }
085:
086: return parent;
087: }
088:
089: public Tree getPrevious() {
090: return previous;
091: }
092:
093: public Tree getFirst() {
094: return first;
095: }
096:
097: public Tree getLast() {
098: return last;
099: }
100:
101: public Tree append(Object data) {
102: Tree child = new Tree(data);
103:
104: child.parent = this ;
105: child.previous = last;
106: if (last != null)
107: last.next = child;
108: else
109: first = child;
110: last = child;
111:
112: return last;
113: }
114:
115: public void appendTree(Tree child) {
116: Tree subChild = append(child.getData());
117:
118: for (child = child.getFirst(); child != null; child = child
119: .getNext()) {
120: subChild.appendTree(child);
121: }
122: }
123:
124: public Iterator children() {
125: return new ChildIterator(first);
126: }
127:
128: public Iterator dfs() {
129: return new DfsIterator(first);
130: }
131:
132: public Iterator iterator() {
133: return new ChildDataIterator(first);
134: }
135:
136: static class ChildIterator implements Iterator {
137: private Tree node;
138:
139: ChildIterator(Tree child) {
140: node = child;
141: }
142:
143: public boolean hasNext() {
144: return node != null;
145: }
146:
147: public Object next() {
148: Tree next = node;
149:
150: if (node != null)
151: node = node.getNext();
152:
153: return next;
154: }
155:
156: public void remove() {
157: throw new UnsupportedOperationException();
158: }
159: }
160:
161: static class ChildDataIterator implements Iterator {
162: private Tree node;
163:
164: ChildDataIterator(Tree child) {
165: node = child;
166: }
167:
168: public boolean hasNext() {
169: return node != null;
170: }
171:
172: public Object next() {
173: Tree next = node;
174:
175: if (node != null)
176: node = node.getNext();
177:
178: return next == null ? null : next.data;
179: }
180:
181: public void remove() {
182: throw new UnsupportedOperationException();
183: }
184: }
185:
186: static class DfsIterator implements Iterator {
187: private Tree top;
188: private Tree node;
189:
190: DfsIterator(Tree top) {
191: this .top = top;
192: node = top;
193: }
194:
195: public boolean hasNext() {
196: return node != null;
197: }
198:
199: public Object next() {
200: Tree next = node;
201:
202: if (node != null)
203: node = node.getNextPreorder();
204:
205: return next;
206: }
207:
208: public void remove() {
209: throw new UnsupportedOperationException();
210: }
211: }
212: }
|