001: package ro.infoiasi.donald.compiler.simple;
002:
003: import java.util.*;
004:
005: /** A binary tree of objects */
006: public class BinTree {
007: private BinTreeNodeP root;
008:
009: /** A node in a binary tree */
010: private class BinTreeNodeP implements BinTreeNode {
011: private Object obj;
012: private BinTreeNodeP parent;
013: private BinTreeNodeP left;
014: private BinTreeNodeP right;
015: private int weight = 1;
016:
017: BinTreeNodeP(Object obj) {
018: this .obj = obj;
019: }
020:
021: public void put(Object obj) {
022: this .obj = obj;
023: }
024:
025: public Object get() {
026: return obj;
027: }
028:
029: public BinTreeNode parent() {
030: return parent;
031: }
032:
033: public BinTreeNode left() {
034: return left;
035: }
036:
037: public BinTreeNode right() {
038: return right;
039: }
040:
041: public String toString() {
042: return "[" + obj + "]";
043: }
044: }
045:
046: private abstract class BinTreeIterator implements Iterator {
047: protected BinTreeNodeP p = root;
048: protected BinTreeNodeP q = null;
049: protected int visited = 0;
050:
051: /** Returns true if the iteration has more elements. */
052: public boolean hasNext() {
053: if (visited < size()) {
054: return true;
055: } else {
056: return false;
057: }
058: }
059:
060: /** Returns the next element in the iteration. */
061: public abstract Object next();
062:
063: /** A node of the tree cannot be removed unless it is a leaf */
064: public void remove() throws UnsupportedOperationException {
065: throw new UnsupportedOperationException();
066: }
067: }
068:
069: /** Iterates the nodes of the tree in pre-order (root-left-right) */
070: private class PreIterator extends BinTreeIterator {
071: /** Returns the next element in the iteration. */
072: public Object next() throws NoSuchElementException {
073: if (p == null || (p == root && q != null)) {
074: throw new NoSuchElementException();
075: } else {
076: boolean foundNext = false;
077: do {
078: if (q == p.parent) {
079: q = p;
080: if (p.left != null)
081: p = p.left;
082: else {
083: if (p.right != null)
084: p = p.right;
085: else {
086: p = p.parent;
087: }
088: }
089: foundNext = true;
090: } else if (q == p.left) {
091: q = p;
092: if (p.right != null)
093: p = p.right;
094: else {
095: p = p.parent;
096: }
097: } else {
098: q = p;
099: p = p.parent;
100: }
101: } while (p != null && !foundNext);
102: //System.out.println("p:"+p+" q:"+q);
103: visited++;
104: return q;
105: }
106: }
107: }
108:
109: /** Iterates the nodes of the tree in in-order (left-root-right) */
110: private class InIterator extends BinTreeIterator {
111: /** Returns the next element in the iteration. */
112: public Object next() throws NoSuchElementException {
113: if (p == null) {
114: throw new NoSuchElementException();
115: } else {
116: boolean foundNext = false;
117: do {
118: if (q == p.parent) {
119: q = p;
120: if (p.left != null)
121: p = p.left;
122: else {
123: if (p.right != null)
124: p = p.right;
125: else {
126: p = p.parent;
127: }
128: foundNext = true;
129: }
130: } else if (q == p.left) {
131: q = p;
132: if (p.right != null)
133: p = p.right;
134: else {
135: p = p.parent;
136: }
137: foundNext = true;
138: } else {
139: q = p;
140: p = p.parent;
141: }
142: } while (p != null && !foundNext);
143: visited++;
144: return q;
145: }
146: }
147: }
148:
149: /** Iterates the nodes of the tree in post-order (left-right-root) */
150: private class PostIterator extends BinTreeIterator {
151: /** Returns the next element in the iteration. */
152: public Object next() throws NoSuchElementException {
153: if (p == null) {
154: throw new NoSuchElementException();
155: } else {
156: boolean foundNext = false;
157: while (p != null && !foundNext) {
158: if (q == p.parent) {
159: q = p;
160: if (p.left != null)
161: p = p.left;
162: else {
163: if (p.right != null)
164: p = p.right;
165: else {
166: p = p.parent;
167: foundNext = true;
168: }
169: }
170: } else if (q == p.left) {
171: q = p;
172: if (p.right != null)
173: p = p.right;
174: else {
175: p = p.parent;
176: foundNext = true;
177: }
178: } else {
179: q = p;
180: p = p.parent;
181: foundNext = true;
182: }
183: }
184: visited++;
185: return q;
186: }
187: }
188: }
189:
190: /** Returns the root of the tree. */
191: public BinTreeNode root() {
192: return root;
193: }
194:
195: /** Returns the number of nodes in the tree. */
196: public int size() {
197: return getWeight(root);
198: }
199:
200: /** Returns the number of nodes in the subtree of the specified node */
201: private int getWeight(BinTreeNodeP node) {
202: if (node != null) {
203: return node.weight;
204: } else {
205: return 0;
206: }
207: }
208:
209: /** Fixes the weights of the given node and of all
210: the nodes all the way to the root of the tree */
211: private void fixWeight(BinTreeNodeP node, int i) {
212: if (i != 0) {
213: while (node != null) {
214: node.weight += i;
215: node = node.parent;
216: }
217: }
218: }
219:
220: /** Adds the given object as the root of the tree.
221: If the tree already had a root the link to that node
222: (and possibly many others) is lost.*/
223: public BinTreeNode addRoot(Object obj) {
224: root = new BinTreeNodeP(obj);
225: return root;
226: }
227:
228: /** Adds the given subTree as the root of the tree. */
229: public void addRootSubTree(BinTree subTree) {
230: subTree.root.parent = null;
231: root = subTree.root;
232: }
233:
234: /** Adds the given object as a left child of the specified parent.
235: If the parent already had a left child the link to that node
236: (and possibly many others) is lost.*/
237: public BinTreeNode addLeftChild(Object obj, BinTreeNode parentNode) {
238: BinTreeNodeP node = new BinTreeNodeP(obj);
239: BinTreeNodeP p = (BinTreeNodeP) parentNode;
240: fixWeight(p, 1 - getWeight(p.left));
241: node.parent = p;
242: p.left = node;
243: return node;
244: }
245:
246: /** Adds the given tree as the left subtree of the specified parent.
247: If the parent already had a left child the link to that node
248: (and possibly many others) is lost.*/
249: public void addLeftSubTree(BinTree subTree, BinTreeNode parentNode) {
250: BinTreeNodeP p = (BinTreeNodeP) parentNode;
251: fixWeight(p, subTree.size() - getWeight(p.left));
252: subTree.root.parent = p;
253: p.left = subTree.root;
254: }
255:
256: /** Adds the given object as a right child of the specified parent.
257: If the parent already had a right child the link to that node
258: (and possibly many others) is lost.*/
259: public BinTreeNode addRightChild(Object obj, BinTreeNode parentNode) {
260: BinTreeNodeP node = new BinTreeNodeP(obj);
261: BinTreeNodeP p = (BinTreeNodeP) parentNode;
262: fixWeight(p, 1 - getWeight(p.right));
263: node.parent = p;
264: p.right = node;
265: return node;
266: }
267:
268: /** Adds the given tree as the right subtree of the specified parent.
269: If the parent already had a right child the link to that node
270: (and possibly many others) is lost.*/
271: public void addRightSubTree(BinTree subTree, BinTreeNode parentNode) {
272: BinTreeNodeP p = (BinTreeNodeP) parentNode;
273: fixWeight(p, subTree.size() - getWeight(p.right));
274: subTree.root.parent = p;
275: p.right = subTree.root;
276: }
277:
278: /** Removes the specified node and all its children from the tree. */
279: public void removeNode(BinTreeNode node) {
280: BinTreeNodeP p = (BinTreeNodeP) node;
281: if (p == root) {
282: root = null;
283: } else {
284: fixWeight(p.parent, -getWeight(p));
285: if (p.parent.left == p) {
286: p.parent.left = null;
287: } else {
288: p.parent.right = null;
289: }
290: p.parent = null;
291: }
292: }
293:
294: /** Returns an Iteratator that over the nodes of this
295: tree in pre-order sequence (root-left-right). */
296: public Iterator preIterator() {
297: return new PreIterator();
298: }
299:
300: /** Returns an Iteratator that over the nodes of this
301: tree in in-order sequence (left-root-right). */
302: public Iterator inIterator() {
303: return new InIterator();
304: }
305:
306: /** Returns an Iteratator that over the nodes of this
307: tree in post-order sequence (left-right-root) */
308: public Iterator postIterator() {
309: return new PostIterator();
310: }
311:
312: /** Returns true if the tree has no nodes. */
313: public boolean IsEmpty() {
314: return root == null;
315: }
316: }
|