|
1
28
29 package com.caucho.util;
30
31 import java.util.Iterator  ;
32
33 public class Tree {
34 private Tree parent;
35
36 private Tree next;
37 private Tree previous;
38
39 private Tree first;
40 private Tree last;
41
42 private Object data;
43
44 public Tree(Object data)
45 {
46 this.data = data;
47 }
48
49 public Object getData()
50 {
51 return data;
52 }
53
54 public void setData(Object data)
55 {
56 this.data = data;
57 }
58
59 public Tree getParent()
60 {
61 return parent;
62 }
63
64 public Tree getNext()
65 {
66 return next;
67 }
68
69 public Tree getNextPreorder()
70 {
71 if (first != null)
72 return first;
73
74 for (Tree ptr = this; ptr != null; ptr = ptr.parent) {
75 if (ptr.next != null)
76 return ptr.next;
77 }
78
79 return null;
80 }
81
82 public Tree getPreviousPreorder()
83 {
84 Tree ptr;
85
86 if ((ptr = previous) != null) {
87 for (; ptr.last != null; ptr = ptr.last) {
88 }
89
90 return ptr;
91 }
92
93 return parent;
94 }
95
96 public Tree getPrevious()
97 {
98 return previous;
99 }
100
101 public Tree getFirst()
102 {
103 return first;
104 }
105
106 public Tree getLast()
107 {
108 return last;
109 }
110
111 public Tree append(Object data)
112 {
113 Tree child = new Tree(data);
114
115 child.parent = this;
116 child.previous = last;
117 if (last != null)
118 last.next = child;
119 else
120 first = child;
121 last = child;
122
123 return last;
124 }
125
126 public void appendTree(Tree child)
127 {
128 Tree subChild = append(child.getData());
129
130 for (child = child.getFirst(); child != null; child = child.getNext()) {
131 subChild.appendTree(child);
132 }
133 }
134
135 public Iterator children()
136 {
137 return new ChildIterator(first);
138 }
139
140 public Iterator dfs()
141 {
142 return new DfsIterator(first);
143 }
144
145 public Iterator iterator()
146 {
147 return new ChildDataIterator(first);
148 }
149
150 static class ChildIterator implements Iterator {
151 private Tree node;
152
153 ChildIterator(Tree child)
154 {
155 node = child;
156 }
157
158 public boolean hasNext()
159 {
160 return node != null;
161 }
162
163 public Object next()
164 {
165 Tree next = node;
166
167 if (node != null)
168 node = node.getNext();
169
170 return next;
171 }
172
173 public void remove()
174 {
175 throw new UnsupportedOperationException ();
176 }
177 }
178
179 static class ChildDataIterator implements Iterator {
180 private Tree node;
181
182 ChildDataIterator(Tree child)
183 {
184 node = child;
185 }
186
187 public boolean hasNext()
188 {
189 return node != null;
190 }
191
192 public Object next()
193 {
194 Tree next = node;
195
196 if (node != null)
197 node = node.getNext();
198
199 return next == null ? null : next.data;
200 }
201
202 public void remove()
203 {
204 throw new UnsupportedOperationException ();
205 }
206 }
207
208 static class DfsIterator implements Iterator {
209 private Tree top;
210 private Tree node;
211
212 DfsIterator(Tree top)
213 {
214 this.top = top;
215 node = top;
216 }
217
218 public boolean hasNext()
219 {
220 return node != null;
221 }
222
223 public Object next()
224 {
225 Tree next = node;
226
227 if (node != null)
228 node = node.getNextPreorder();
229
230 return next;
231 }
232
233 public void remove()
234 {
235 throw new UnsupportedOperationException ();
236 }
237 }
238 }
239 |
Popular Tags |
Java API By Example, From Geeks To Geeks.