Java > Open Source Codes > com > tc > util > AATree


1 /*
2  * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
3  */
4 package com.tc.util;
5
6 import com.tc.exception.ImplementMe;
7
8 import java.util.ArrayList ;
9 import java.util.Iterator ;
10 import java.util.List ;
11 import java.util.NoSuchElementException ;
12
13 /**
14  * Implements an AA-tree. AA tree provides all the advantages of a Red Black Tree while keeping the implementation
15  * simple. For more details on AA tree, check out http://user.it.uu.se/~arnea/abs/simp.html and
16  * http://en.wikipedia.org/wiki/AA_tree This source code is taken from
17  * http://www.cs.fiu.edu/~weiss/dsaa_java/Code/DataStructures/ and modified slightly. Note:: "matching" is based on the
18  * compareTo method. This class is *NOT* thread safe. Synchronize externally if you want it to be thread safe.
19  *
20  * @author Mark Allen Weiss
21  */
22 public class AATree {
23
24   private AANode root;
25   private AANode deletedNode;
26   private AANode lastNode;
27   private Comparable deletedElement;
28   private boolean inserted;
29
30   private static final AANode nullNode;
31
32   static // static initializer for nullNode
33 {
34     nullNode = new AANode(null);
35     nullNode.left = nullNode.right = nullNode;
36     nullNode.level = 0;
37   }
38
39   /**
40    * Construct the tree.
41    */
42   public AATree() {
43     root = nullNode;
44   }
45
46   /**
47    * Insert into the tree.
48    *
49    * @param x the item to insert.
50    * @return true if the item was inserted, false if was already present
51    * @throws DuplicateItemException if x is already present.
52    */
53   public boolean insert(Comparable x) {
54     inserted = true;
55     root = insert(x, root);
56     return inserted;
57   }
58
59   /**
60    * Remove from the tree.
61    *
62    * @param x the item to remove.
63    * @throws ItemNotFoundException if x is not found.
64    */
65   public Comparable remove(Comparable x) {
66     deletedNode = nullNode;
67     root = remove(x, root);
68     Comparable d = deletedElement;
69     // deletedElement is set to null to free the reference,
70 // deletedNode is not freed as it will endup pointing to a valid node.
71 deletedElement = null;
72     return d;
73   }
74
75   /**
76    * Find the smallest item in the tree.
77    *
78    * @return the smallest item or null if empty.
79    */
80   public Comparable findMin() {
81     if (isEmpty()) return null;
82
83     AANode ptr = root;
84
85     while (ptr.left != nullNode)
86       ptr = ptr.left;
87
88     return ptr.element;
89   }
90
91   /**
92    * Find the largest item in the tree.
93    *
94    * @return the largest item or null if empty.
95    */
96   public Comparable findMax() {
97     if (isEmpty()) return null;
98
99     AANode ptr = root;
100
101     while (ptr.right != nullNode)
102       ptr = ptr.right;
103
104     return ptr.element;
105   }
106
107   /**
108    * Find an item in the tree.
109    *
110    * @param x the item to search for.
111    * @return the matching item of null if not found.
112    */
113
114   public Comparable find(Comparable x) {
115     AANode current = root;
116
117     while (current != nullNode) {
118       int res = x.compareTo(current.element);
119       if (res < 0) current = current.left;
120       else if (res > 0) current = current.right;
121       else return current.element;
122     }
123     return null;
124   }
125
126   /**
127    * Make the tree logically empty.
128    */
129   public void clear() {
130     root = nullNode;
131   }
132
133   /**
134    * Test if the tree is logically empty.
135    *
136    * @return true if empty, false otherwise.
137    */
138   public boolean isEmpty() {
139     return root == nullNode;
140   }
141
142   public Iterator iterator() {
143     return new AATreeIterator();
144   }
145
146   /**
147    * Internal method to insert into a subtree.
148    *
149    * @param x the item to insert.
150    * @param t the node that roots the tree.
151    * @return the new root.
152    * @throws DuplicateItemException if x is already present.
153    */
154   private AANode insert(Comparable x, AANode t) {
155     if (t == nullNode) {
156       t = new AANode(x);
157     } else if (x.compareTo(t.element) < 0) {
158       t.left = insert(x, t.left);
159     } else if (x.compareTo(t.element) > 0) {
160       t.right = insert(x, t.right);
161     } else {
162       // XXX:: Not throwing DuplicateItemException as we may want to insert elements without doing a lookup.
163 // throw new RuntimeException("DuplicateItemExpection:" + x.toString());
164 inserted = false;
165       return t;
166     }
167
168     t = skew(t);
169     t = split(t);
170     return t;
171   }
172
173   /**
174    * Internal method to remove from a subtree.
175    *
176    * @param x the item to remove.
177    * @param t the node that roots the tree.
178    * @return the new root.
179    * @throws ItemNotFoundException if x is not found.
180    */
181   private AANode remove(Comparable x, AANode t) {
182     if (t != nullNode) {
183       // Step 1: Search down the tree and set lastNode and deletedNode
184 lastNode = t;
185       if (x.compareTo(t.element) < 0) {
186         t.left = remove(x, t.left);
187       } else {
188         deletedNode = t;
189         t.right = remove(x, t.right);
190       }
191
192       // Step 2: If at the bottom of the tree and
193 // x is present, we remove it
194 if (t == lastNode) {
195         if (deletedNode == nullNode || x.compareTo(deletedNode.element) != 0) {
196           // XXX:: Modified to no throw ItemNotFoundException as we want to be able to remove elements without doing a
197 // lookup.
198 // throw new RuntimeException("ItemNotFoundException : " + x.toString());
199 } else {
200           deletedElement = deletedNode.element;
201           deletedNode.element = t.element;
202           t = t.right;
203         }
204       }
205
206       // Step 3: Otherwise, we are not at the bottom; rebalance
207 else if (t.left.level < t.level - 1 || t.right.level < t.level - 1) {
208         if (t.right.level > --t.level) t.right.level = t.level;
209         t = skew(t);
210         t.right = skew(t.right);
211         t.right.right = skew(t.right.right);
212         t = split(t);
213         t.right = split(t.right);
214       }
215     }
216     return t;
217   }
218
219   /**
220    * Skew primitive for AA-trees.
221    *
222    * @param t the node that roots the tree.
223    * @return the new root after the rotation.
224    */
225   private static AANode skew(AANode t) {
226     if (t.left.level == t.level) t = rotateWithLeftChild(t);
227     return t;
228   }
229
230   /**
231    * Split primitive for AA-trees.
232    *
233    * @param t the node that roots the tree.
234    * @return the new root after the rotation.
235    */
236   private static AANode split(AANode t) {
237     if (t.right.right.level == t.level) {
238       t = rotateWithRightChild(t);
239       t.level++;
240     }
241     return t;
242   }
243
244   /**
245    * Rotate binary tree node with left child.
246    */
247   private static AANode rotateWithLeftChild(AANode k2) {
248     AANode k1 = k2.left;
249     k2.left = k1.right;
250     k1.right = k2;
251     return k1;
252   }
253
254   /**
255    * Rotate binary tree node with right child.
256    */
257   private static AANode rotateWithRightChild(AANode k1) {
258     AANode k2 = k1.right;
259     k1.right = k2.left;
260     k2.left = k1;
261     return k2;
262   }
263
264   public String dump() {
265     return "AATree = { " + root.dump() + " }";
266   }
267
268   private static class AANode {
269     // Constructors
270 AANode(Comparable theElement) {
271       element = theElement;
272       left = right = nullNode;
273       level = 1;
274     }
275
276     // XXX:: for debugging - costly operation
277 public String dump() {
278       String ds = String.valueOf(element);
279       if (left != nullNode) {
280         ds = ds + "," + left.dump();
281       }
282       if (right != nullNode) {
283         ds = ds + "," + right.dump();
284       }
285       return ds;
286     }
287
288     Comparable element; // The data in the node
289 AANode left; // Left child
290 AANode right; // Right child
291 int level; // Level
292
293     public String toString() {
294       return "AANode@" + System.identityHashCode(this) + "{" + element + "}";
295     }
296   }
297
298   /*
299    * This class is slightly inefficient in that it uses a stack internally to store state. But it is needed so that we
300    * dont have to store parent references. Also it does not give the objects in sorted order (as it is just
301    */
302   private class AATreeIterator implements Iterator {
303
304     // contains elements that needs to be travelled.
305 List s = new ArrayList ();
306     AANode next = root;
307
308     public boolean hasNext() {
309       return (next != nullNode);
310     }
311
312     public Object next() {
313       if (next == nullNode) { throw new NoSuchElementException (); }
314       Object element = next.element;
315       boolean leftNotNull = next.left != nullNode;
316       boolean rightNotNull = next.right != nullNode;
317       if (leftNotNull && rightNotNull) {
318         s.add(next.right);
319         next = next.left;
320       } else if (leftNotNull) {
321         next = next.left;
322       } else if (rightNotNull) {
323         next = next.right;
324       } else if (s.size() > 0) {
325         next = ((AANode) s.remove(s.size() - 1));
326       } else {
327         next = nullNode;
328       }
329       return element;
330     }
331
332     // This is a little tricky, the tree might rebalance itself.
333 public void remove() {
334       throw new ImplementMe();
335     }
336
337   }
338
339   // Test program; should print min and max and nothing else
340 // public static void main(String[] args) {
341 // AATree t = new AATree();
342 // final int NUMS = 400000;
343 // final int GAP = 307;
344 //
345 // System.out.println("Checking... (no bad output means success)");
346 //
347 // t.insert(new Integer(NUMS * 2));
348 // t.insert(new Integer(NUMS * 3));
349 // for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
350 // t.insert(new Integer(i));
351 // System.out.println("Inserts complete");
352 //
353 // t.remove(t.findMax());
354 // for (int i = 1; i < NUMS; i += 2)
355 // t.remove(new Integer(i));
356 // t.remove(t.findMax());
357 // System.out.println("Removes complete");
358 //
359 // if (((Integer) (t.findMin())).intValue() != 2 || ((Integer) (t.findMax())).intValue() != NUMS - 2) System.out
360 // .println("FindMin or FindMax error!");
361 //
362 // for (int i = 2; i < NUMS; i += 2)
363 // if (((Integer) t.find(new Integer(i))).intValue() != i) System.out.println("Error: find fails for " + i);
364 //
365 // for (int i = 1; i < NUMS; i += 2)
366 // if (t.find(new Integer(i)) != null) System.out.println("Error: Found deleted item " + i);
367 // }
368
369   public static void main(String [] args) {
370     AATree t = new AATree();
371     System.out.println("Inserted = " + t.insert(new Integer (8)));
372     System.out.println("Tree is : " + t.dump());
373     System.out.println("From Iterator : " + dumpUsingIterator(t));
374     System.out.println("Inserted = " + t.insert(new Integer (4)));
375     System.out.println("Tree is : " + t.dump());
376     System.out.println("From Iterator : " + dumpUsingIterator(t));
377     System.out.println("Inserted = " + t.insert(new Integer (10)));
378     System.out.println("Tree is : " + t.dump());
379     System.out.println("From Iterator : " + dumpUsingIterator(t));
380     System.out.println("Inserted = " + t.insert(new Integer (2)));
381     System.out.println("Tree is : " + t.dump());
382     System.out.println("From Iterator : " + dumpUsingIterator(t));
383     System.out.println("Inserted = " + t.insert(new Integer (6)));
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 (9)));
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 (11)));
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 (1)));
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 (3)));
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 (5)));
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 (7)));
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 (12)));
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 (1)));
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 (3)));
411     System.out.println("Tree is : " + t.dump());
412     System.out.println("From Iterator : " + dumpUsingIterator(t));
413
414     System.out.println("Deleted = " + t.remove(new Integer (6)));
415     System.out.println("Tree is : " + t.dump());
416     System.out.println("From Iterator : " + dumpUsingIterator(t));
417     System.out.println("Deleted = " + t.remove(new Integer (8)));
418     System.out.println("Tree is : " + t.dump());
419     System.out.println("From Iterator : " + dumpUsingIterator(t));
420     System.out.println("Deleted = " + t.remove(new Integer (10)));
421     System.out.println("Tree is : " + t.dump());
422     System.out.println("From Iterator : " + dumpUsingIterator(t));
423     System.out.println("Deleted = " + t.remove(new Integer (12)));
424     System.out.println("Tree is : " + t.dump());
425     System.out.println("From Iterator : " + dumpUsingIterator(t));
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 (1)));
433     System.out.println("Tree is : " + t.dump());
434     System.out.println("From Iterator : " + dumpUsingIterator(t));
435
436   }
437
438   private static String dumpUsingIterator(AATree t) {
439     StringBuffer sb = new StringBuffer ();
440     for (Iterator i = t.iterator(); i.hasNext();) {
441       sb.append(i.next());
442       if (i.hasNext()) {
443         sb.append(',');
444       }
445     }
446     return sb.toString();
447   }
448 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags