001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004: package com.tc.util;
005:
006: import com.tc.exception.ImplementMe;
007:
008: import java.util.ArrayList;
009: import java.util.Iterator;
010: import java.util.List;
011: import java.util.NoSuchElementException;
012:
013: /**
014: * Implements an AA-tree. AA tree provides all the advantages of a Red Black Tree while keeping the implementation
015: * simple. For more details on AA tree, check out http://user.it.uu.se/~arnea/abs/simp.html and
016: * http://en.wikipedia.org/wiki/AA_tree This source code is taken from
017: * http://www.cs.fiu.edu/~weiss/dsaa_java/Code/DataStructures/ and modified slightly. Note:: "matching" is based on the
018: * compareTo method. This class is *NOT* thread safe. Synchronize externally if you want it to be thread safe.
019: *
020: * @author Mark Allen Weiss
021: */
022: public class AATree {
023:
024: private AANode root;
025: private AANode deletedNode;
026: private AANode lastNode;
027: private Comparable deletedElement;
028: private boolean inserted;
029:
030: private static final AANode nullNode;
031:
032: static // static initializer for nullNode
033: {
034: nullNode = new AANode(null);
035: nullNode.left = nullNode.right = nullNode;
036: nullNode.level = 0;
037: }
038:
039: /**
040: * Construct the tree.
041: */
042: public AATree() {
043: root = nullNode;
044: }
045:
046: /**
047: * Insert into the tree.
048: *
049: * @param x the item to insert.
050: * @return true if the item was inserted, false if was already present
051: * @throws DuplicateItemException if x is already present.
052: */
053: public boolean insert(Comparable x) {
054: inserted = true;
055: root = insert(x, root);
056: return inserted;
057: }
058:
059: /**
060: * Remove from the tree.
061: *
062: * @param x the item to remove.
063: * @throws ItemNotFoundException if x is not found.
064: */
065: public Comparable remove(Comparable x) {
066: deletedNode = nullNode;
067: root = remove(x, root);
068: Comparable d = deletedElement;
069: // deletedElement is set to null to free the reference,
070: // deletedNode is not freed as it will endup pointing to a valid node.
071: deletedElement = null;
072: return d;
073: }
074:
075: /**
076: * Find the smallest item in the tree.
077: *
078: * @return the smallest item or null if empty.
079: */
080: public Comparable findMin() {
081: if (isEmpty())
082: return null;
083:
084: AANode ptr = root;
085:
086: while (ptr.left != nullNode)
087: ptr = ptr.left;
088:
089: return ptr.element;
090: }
091:
092: /**
093: * Find the largest item in the tree.
094: *
095: * @return the largest item or null if empty.
096: */
097: public Comparable findMax() {
098: if (isEmpty())
099: return null;
100:
101: AANode ptr = root;
102:
103: while (ptr.right != nullNode)
104: ptr = ptr.right;
105:
106: return ptr.element;
107: }
108:
109: /**
110: * Find an item in the tree.
111: *
112: * @param x the item to search for.
113: * @return the matching item of null if not found.
114: */
115:
116: public Comparable find(Comparable x) {
117: AANode current = root;
118:
119: while (current != nullNode) {
120: int res = x.compareTo(current.element);
121: if (res < 0)
122: current = current.left;
123: else if (res > 0)
124: current = current.right;
125: else
126: return current.element;
127: }
128: return null;
129: }
130:
131: /**
132: * Make the tree logically empty.
133: */
134: public void clear() {
135: root = nullNode;
136: }
137:
138: /**
139: * Test if the tree is logically empty.
140: *
141: * @return true if empty, false otherwise.
142: */
143: public boolean isEmpty() {
144: return root == nullNode;
145: }
146:
147: public Iterator iterator() {
148: return new AATreeIterator();
149: }
150:
151: /**
152: * Internal method to insert into a subtree.
153: *
154: * @param x the item to insert.
155: * @param t the node that roots the tree.
156: * @return the new root.
157: * @throws DuplicateItemException if x is already present.
158: */
159: private AANode insert(Comparable x, AANode t) {
160: if (t == nullNode) {
161: t = new AANode(x);
162: } else if (x.compareTo(t.element) < 0) {
163: t.left = insert(x, t.left);
164: } else if (x.compareTo(t.element) > 0) {
165: t.right = insert(x, t.right);
166: } else {
167: // XXX:: Not throwing DuplicateItemException as we may want to insert elements without doing a lookup.
168: // throw new RuntimeException("DuplicateItemExpection:" + x.toString());
169: inserted = false;
170: return t;
171: }
172:
173: t = skew(t);
174: t = split(t);
175: return t;
176: }
177:
178: /**
179: * Internal method to remove from a subtree.
180: *
181: * @param x the item to remove.
182: * @param t the node that roots the tree.
183: * @return the new root.
184: * @throws ItemNotFoundException if x is not found.
185: */
186: private AANode remove(Comparable x, AANode t) {
187: if (t != nullNode) {
188: // Step 1: Search down the tree and set lastNode and deletedNode
189: lastNode = t;
190: if (x.compareTo(t.element) < 0) {
191: t.left = remove(x, t.left);
192: } else {
193: deletedNode = t;
194: t.right = remove(x, t.right);
195: }
196:
197: // Step 2: If at the bottom of the tree and
198: // x is present, we remove it
199: if (t == lastNode) {
200: if (deletedNode == nullNode
201: || x.compareTo(deletedNode.element) != 0) {
202: // XXX:: Modified to no throw ItemNotFoundException as we want to be able to remove elements without doing a
203: // lookup.
204: // throw new RuntimeException("ItemNotFoundException : " + x.toString());
205: } else {
206: deletedElement = deletedNode.element;
207: deletedNode.element = t.element;
208: t = t.right;
209: }
210: }
211:
212: // Step 3: Otherwise, we are not at the bottom; rebalance
213: else if (t.left.level < t.level - 1
214: || t.right.level < t.level - 1) {
215: if (t.right.level > --t.level)
216: t.right.level = t.level;
217: t = skew(t);
218: t.right = skew(t.right);
219: t.right.right = skew(t.right.right);
220: t = split(t);
221: t.right = split(t.right);
222: }
223: }
224: return t;
225: }
226:
227: /**
228: * Skew primitive for AA-trees.
229: *
230: * @param t the node that roots the tree.
231: * @return the new root after the rotation.
232: */
233: private static AANode skew(AANode t) {
234: if (t.left.level == t.level)
235: t = rotateWithLeftChild(t);
236: return t;
237: }
238:
239: /**
240: * Split primitive for AA-trees.
241: *
242: * @param t the node that roots the tree.
243: * @return the new root after the rotation.
244: */
245: private static AANode split(AANode t) {
246: if (t.right.right.level == t.level) {
247: t = rotateWithRightChild(t);
248: t.level++;
249: }
250: return t;
251: }
252:
253: /**
254: * Rotate binary tree node with left child.
255: */
256: private static AANode rotateWithLeftChild(AANode k2) {
257: AANode k1 = k2.left;
258: k2.left = k1.right;
259: k1.right = k2;
260: return k1;
261: }
262:
263: /**
264: * Rotate binary tree node with right child.
265: */
266: private static AANode rotateWithRightChild(AANode k1) {
267: AANode k2 = k1.right;
268: k1.right = k2.left;
269: k2.left = k1;
270: return k2;
271: }
272:
273: public String dump() {
274: return "AATree = { " + root.dump() + " }";
275: }
276:
277: private static class AANode {
278: // Constructors
279: AANode(Comparable theElement) {
280: element = theElement;
281: left = right = nullNode;
282: level = 1;
283: }
284:
285: // XXX:: for debugging - costly operation
286: public String dump() {
287: String ds = String.valueOf(element);
288: if (left != nullNode) {
289: ds = ds + "," + left.dump();
290: }
291: if (right != nullNode) {
292: ds = ds + "," + right.dump();
293: }
294: return ds;
295: }
296:
297: Comparable element; // The data in the node
298: AANode left; // Left child
299: AANode right; // Right child
300: int level; // Level
301:
302: public String toString() {
303: return "AANode@" + System.identityHashCode(this ) + "{"
304: + element + "}";
305: }
306: }
307:
308: /*
309: * This class is slightly inefficient in that it uses a stack internally to store state. But it is needed so that we
310: * dont have to store parent references. Also it does not give the objects in sorted order (as it is just
311: */
312: private class AATreeIterator implements Iterator {
313:
314: // contains elements that needs to be travelled.
315: List s = new ArrayList();
316: AANode next = root;
317:
318: public boolean hasNext() {
319: return (next != nullNode);
320: }
321:
322: public Object next() {
323: if (next == nullNode) {
324: throw new NoSuchElementException();
325: }
326: Object element = next.element;
327: boolean leftNotNull = next.left != nullNode;
328: boolean rightNotNull = next.right != nullNode;
329: if (leftNotNull && rightNotNull) {
330: s.add(next.right);
331: next = next.left;
332: } else if (leftNotNull) {
333: next = next.left;
334: } else if (rightNotNull) {
335: next = next.right;
336: } else if (s.size() > 0) {
337: next = ((AANode) s.remove(s.size() - 1));
338: } else {
339: next = nullNode;
340: }
341: return element;
342: }
343:
344: // This is a little tricky, the tree might rebalance itself.
345: public void remove() {
346: throw new ImplementMe();
347: }
348:
349: }
350:
351: // Test program; should print min and max and nothing else
352: // public static void main(String[] args) {
353: // AATree t = new AATree();
354: // final int NUMS = 400000;
355: // final int GAP = 307;
356: //
357: // System.out.println("Checking... (no bad output means success)");
358: //
359: // t.insert(new Integer(NUMS * 2));
360: // t.insert(new Integer(NUMS * 3));
361: // for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
362: // t.insert(new Integer(i));
363: // System.out.println("Inserts complete");
364: //
365: // t.remove(t.findMax());
366: // for (int i = 1; i < NUMS; i += 2)
367: // t.remove(new Integer(i));
368: // t.remove(t.findMax());
369: // System.out.println("Removes complete");
370: //
371: // if (((Integer) (t.findMin())).intValue() != 2 || ((Integer) (t.findMax())).intValue() != NUMS - 2) System.out
372: // .println("FindMin or FindMax error!");
373: //
374: // for (int i = 2; i < NUMS; i += 2)
375: // if (((Integer) t.find(new Integer(i))).intValue() != i) System.out.println("Error: find fails for " + i);
376: //
377: // for (int i = 1; i < NUMS; i += 2)
378: // if (t.find(new Integer(i)) != null) System.out.println("Error: Found deleted item " + i);
379: // }
380:
381: public static void main(String[] args) {
382: AATree t = new AATree();
383: System.out.println("Inserted = " + t.insert(new Integer(8)));
384: System.out.println("Tree is : " + t.dump());
385: System.out.println("From Iterator : " + dumpUsingIterator(t));
386: System.out.println("Inserted = " + t.insert(new Integer(4)));
387: System.out.println("Tree is : " + t.dump());
388: System.out.println("From Iterator : " + dumpUsingIterator(t));
389: System.out.println("Inserted = " + t.insert(new Integer(10)));
390: System.out.println("Tree is : " + t.dump());
391: System.out.println("From Iterator : " + dumpUsingIterator(t));
392: System.out.println("Inserted = " + t.insert(new Integer(2)));
393: System.out.println("Tree is : " + t.dump());
394: System.out.println("From Iterator : " + dumpUsingIterator(t));
395: System.out.println("Inserted = " + t.insert(new Integer(6)));
396: System.out.println("Tree is : " + t.dump());
397: System.out.println("From Iterator : " + dumpUsingIterator(t));
398: System.out.println("Inserted = " + t.insert(new Integer(9)));
399: System.out.println("Tree is : " + t.dump());
400: System.out.println("From Iterator : " + dumpUsingIterator(t));
401: System.out.println("Inserted = " + t.insert(new Integer(11)));
402: System.out.println("Tree is : " + t.dump());
403: System.out.println("From Iterator : " + dumpUsingIterator(t));
404: System.out.println("Inserted = " + t.insert(new Integer(1)));
405: System.out.println("Tree is : " + t.dump());
406: System.out.println("From Iterator : " + dumpUsingIterator(t));
407: System.out.println("Inserted = " + t.insert(new Integer(3)));
408: System.out.println("Tree is : " + t.dump());
409: System.out.println("From Iterator : " + dumpUsingIterator(t));
410: System.out.println("Inserted = " + t.insert(new Integer(5)));
411: System.out.println("Tree is : " + t.dump());
412: System.out.println("From Iterator : " + dumpUsingIterator(t));
413: System.out.println("Inserted = " + t.insert(new Integer(7)));
414: System.out.println("Tree is : " + t.dump());
415: System.out.println("From Iterator : " + dumpUsingIterator(t));
416: System.out.println("Inserted = " + t.insert(new Integer(12)));
417: System.out.println("Tree is : " + t.dump());
418: System.out.println("From Iterator : " + dumpUsingIterator(t));
419: System.out.println("Inserted = " + t.insert(new Integer(1)));
420: System.out.println("Tree is : " + t.dump());
421: System.out.println("From Iterator : " + dumpUsingIterator(t));
422: System.out.println("Inserted = " + t.insert(new Integer(3)));
423: System.out.println("Tree is : " + t.dump());
424: System.out.println("From Iterator : " + dumpUsingIterator(t));
425:
426: System.out.println("Deleted = " + t.remove(new Integer(6)));
427: System.out.println("Tree is : " + t.dump());
428: System.out.println("From Iterator : " + dumpUsingIterator(t));
429: System.out.println("Deleted = " + t.remove(new Integer(8)));
430: System.out.println("Tree is : " + t.dump());
431: System.out.println("From Iterator : " + dumpUsingIterator(t));
432: System.out.println("Deleted = " + t.remove(new Integer(10)));
433: System.out.println("Tree is : " + t.dump());
434: System.out.println("From Iterator : " + dumpUsingIterator(t));
435: System.out.println("Deleted = " + t.remove(new Integer(12)));
436: System.out.println("Tree is : " + t.dump());
437: System.out.println("From Iterator : " + dumpUsingIterator(t));
438: System.out.println("Deleted = " + t.remove(new Integer(6)));
439: System.out.println("Tree is : " + t.dump());
440: System.out.println("From Iterator : " + dumpUsingIterator(t));
441: System.out.println("Deleted = " + t.remove(new Integer(8)));
442: System.out.println("Tree is : " + t.dump());
443: System.out.println("From Iterator : " + dumpUsingIterator(t));
444: System.out.println("Deleted = " + t.remove(new Integer(1)));
445: System.out.println("Tree is : " + t.dump());
446: System.out.println("From Iterator : " + dumpUsingIterator(t));
447:
448: }
449:
450: private static String dumpUsingIterator(AATree t) {
451: StringBuffer sb = new StringBuffer();
452: for (Iterator i = t.iterator(); i.hasNext();) {
453: sb.append(i.next());
454: if (i.hasNext()) {
455: sb.append(',');
456: }
457: }
458: return sb.toString();
459: }
460: }
|