1 /**
  2  * The Render Engine
  3  * HashContainer
  4  *
  5  * @fileoverview A set of objects which can be used to create a collection
  6  *               of objects, and to iterate over a container.
  7  *
  8  * @author: Brett Fattori (brettf@renderengine.com)
  9  * @author: $Author: bfattori $
 10  * @version: $Revision: 1555 $
 11  *
 12  * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com)
 13  *
 14  * Permission is hereby granted, free of charge, to any person obtaining a copy
 15  * of this software and associated documentation files (the "Software"), to deal
 16  * in the Software without restriction, including without limitation the rights
 17  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 18  * copies of the Software, and to permit persons to whom the Software is
 19  * furnished to do so, subject to the following conditions:
 20  *
 21  * The above copyright notice and this permission notice shall be included in
 22  * all copies or substantial portions of the Software.
 23  *
 24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 25  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 26  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 27  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 28  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 29  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 30  * THE SOFTWARE.
 31  *
 32  */
 33 
 34 // The class this file defines and its required classes
 35 R.Engine.define({
 36     "class":"R.struct.RedBlackTree",
 37     "requires":[
 38         "R.engine.PooledObject"
 39     ]
 40 });
 41 
 42 /**
 43  * The RedBlackNode is a private class which is used by the RedBlackTree class
 44  * to contain the data.  It is a simple container with basic structures
 45  * which are accessed directly.  Modification of this class should be done
 46  * with care!!
 47  */
 48 R.struct.RedBlackNode = Base.extend(/** @scope R.struct.RedBlackNode.prototype */{
 49     e:null,
 50     left:null,
 51     right:null,
 52     color:0,
 53 
 54     constructor:function (element, left, right) {
 55         this.element = element;
 56         this.left = left || null;
 57         this.right = right || null;
 58         this.color = 1;	// Starts BLACK
 59     }
 60 }, /** @scope R.struct.RedBlackNode.prototype */{
 61     BLACK:1,
 62     RED:0
 63 });
 64 
 65 /**
 66  * @class An implementation of a RedBlackTree data structure.  RedBlackTree has
 67  *             a worst-case time of O(log n) which is fast enough to quickly locate
 68  *             objects in the tree.  Duplicates are not allowed in a RedBlackTree.
 69  *             <p/>
 70  *             Items added to a RedBlackTree must implement a <code>compareTo(t)</code>
 71  *             method which returns a Number.  Zero if the value of the item is equal to
 72  *             "t", -1 if the value is less than t, 1 if the value is greater than "t".
 73  *             <p/>
 74  *             References:
 75  *               http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html<br/>
 76  *                http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
 77  *
 78  * @param name {String} The name of the container. Default: RBTree
 79  * @extends R.engine.PooledObject
 80  * @constructor
 81  * @description Create a red-black tree object.
 82  */
 83 R.struct.RedBlackTree = function () {
 84     return R.engine.PooledObject.extend(/** @scope R.struct.RedBlackTree.prototype */{
 85 
 86         nullNode:null,
 87         current:null,
 88         parent:null,
 89         grand:null,
 90         great:null,
 91         header:null,
 92 
 93         /** @private */
 94         constructor:function (name) {
 95             this.base(name || "RBTree");
 96 
 97             this.nullNode = new R.struct.RedBlackNode(null);
 98             this.nullNode.left = this.nullNode.right = this.nullNode;
 99 
100             this.header = new R.struct.RedBlackNode(null);
101             this.header.left = this.header.right = this.nullNode;
102         },
103 
104         /**
105          * Insert into the tree.  <code>item</code> must implement the <code>compareTo(t)</code>
106          * method, otherwise insertion will fail with an assertion.
107          *
108          * @param item {Object} the item to insert.
109          */
110         insert:function (item) {
111             Assert(item.compareTo, "Items added to RedBlackTree must implement compareTo() method");
112             this.current = this.parent = this.grand = this.header;
113             this.nullNode.element = item;
114 
115             while (R.struct.RedBlackTree.compare(item, this.current) != 0) {
116                 this.great = this.grand;
117                 this.grand = this.parent;
118                 this.parent = this.current;
119                 this.current = R.struct.RedBlackTree.compare(item, this.current) < 0 ? this.current.left : this.current.right;
120 
121                 // Check if two red children; fix if so
122                 if (this.current.left.color == R.struct.RedBlackNode.RED &&
123                     this.current.right.color == R.struct.RedBlackNode.RED) {
124                     this.handleReorient(item);
125                 }
126             }
127 
128             // Insertion fails if item already present
129             Assert(this.current == this.nullNode, "RedBlackTree duplication exception: " + item.toString());
130             this.current = new R.struct.RedBlackNode(item, this.nullNode, this.nullNode);
131 
132             // Attach to parent
133             if (R.struct.RedBlackTree.compare(item, this.parent) < 0) {
134                 this.parent.left = this.current;
135             }
136             else {
137                 this.parent.right = this.current;
138             }
139 
140             this.handleReorient(item);
141         },
142 
143         remove:function (item) {
144             R._unsupported("remove()", this);
145             // see: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
146         },
147 
148         /**
149          * Replace the the item in the tree with the new item.
150          * @param oldItem {Object} The object to find
151          * @param newItem {Object} The object to replace it with
152          */
153         replace:function (oldItem, newItem) {
154             Assert(newItem.compareTo, "Cannot use replace() in RedBlackTree if item doesn't have compareTo()");
155             var node = this.findNode(oldItem);
156             if (node) {
157                 node.element = newItem;
158             }
159         },
160 
161         /**
162          * Find the smallest item  the tree.
163          * @return the smallest item or null if empty.
164          */
165         findMin:function () {
166             if (this.isEmpty()) {
167                 return null;
168             }
169             else {
170                 var itr = this.header.right;
171                 while (itr.left != this.nullNode) {
172                     itr = itr.left;
173                 }
174 
175                 return itr.element;
176             }
177         },
178 
179         /**
180          * Find the largest item in the tree.
181          * @return the largest item or null if empty.
182          */
183         findMax:function () {
184             if (this.isEmpty()) {
185                 return null;
186             }
187             else {
188                 var itr = this.header.right;
189                 while (itr.right != this.nullNode) {
190                     itr = itr.right;
191                 }
192 
193                 return itr.element;
194             }
195         },
196 
197         /**
198          * Find an item in the tree. The item "x" must implement the <code>compareTo(t)</code>method.
199          * @param x {Object} the item to search for.
200          * @return {Object} the matching item or <code>null</code> if not found.
201          */
202         find:function (x) {
203             Assert(x.compareTo, "Cannot use find() in RedBlackTree if item doesn't have compareTo()");
204             var node = this.findNode(x);
205             return node.element;
206         },
207 
208         /**
209          * Find the node containing an item in the tree.
210          * The item "x" must implement the <code>compareTo(t)</code>method.
211          * @param x {Object} the item to search for.
212          * @return {RedBlackNode} the matching node or <code>null</code> if not found.
213          */
214         findNode:function (x) {
215             Assert(x.compareTo, "Cannot use findNode() in RedBlackTree if item doesn't have compareTo()");
216             this.nullNode.element = x;
217             this.current = this.header.right;
218 
219             for (; ;) {
220                 if (x.compareTo(this.current.element) < 0) {
221                     this.current = this.current.left;
222                 }
223                 else if (x.compareTo(current.element) > 0) {
224                     this.current = this.current.right;
225                 }
226                 else if (current != nullNode) {
227                     return this.current;
228                 }
229                 else {
230                     return null;
231                 }
232             }
233         },
234 
235         /**
236          * Make the tree logically empty.
237          */
238         makeEmpty:function () {
239             this.header.right = this.nullNode;
240         },
241 
242         /**
243          * Test if the tree is logically empty.
244          * @return true if empty, false otherwise.
245          */
246         isEmpty:function () {
247             return this.header.right == this.nullNode;
248         },
249 
250         /**
251          * Internal routine that is called during an insertion
252          * if a node has two red children. Performs flip and rotations.
253          * @param item the item being inserted.
254          * @private
255          */
256         handleReorient:function (item) {
257             // Do the color flip
258             this.current.color = R.struct.RedBlackNode.RED;
259             this.current.left.color = R.struct.RedBlackNode.BLACK;
260             this.current.right.color = R.struct.RedBlackNode.BLACK;
261 
262             if (this.parent.color == R.struct.RedBlackNode.RED) { // Have to rotate
263                 this.grand.color = R.struct.RedBlackNode.RED;
264                 if ((R.struct.RedBlackTree.compare(item, this.grand) < 0) !=
265                     (R.struct.RedBlackTree.compare(item, this.parent) < 0)) {
266                     this.parent = this.rotate(item, this.grand); // Start double rotate
267                 }
268                 this.current = this.rotate(item, this.great);
269                 this.current.color = R.struct.RedBlackNode.BLACK;
270             }
271             this.header.right.color = R.struct.RedBlackNode.BLACK;
272         },
273 
274         /**
275          * Internal routine that performs a single or double rotation.
276          * Because the result is attached to the parent, there are four cases.
277          * Called by handleReorient.
278          * @param item the item in handleReorient.
279          * @param parent the parent of the root of the rotated subtree.
280          * @return the root of the rotated subtree.
281          * @private
282          */
283         rotate:function (item, prnt) {
284             if (R.struct.RedBlackTree.compare(item, prnt) < 0) {
285                 return prnt.left = R.struct.RedBlackTree.compare(item, prnt.left) < 0 ? R.struct.RedBlackTree.rotateWithLeftChild(prnt.left) : R.struct.RedBlackTree.rotateWithRightChild(prnt.left);
286             }
287             else {
288                 return prnt.right = R.struct.RedBlackTree.compare(item, prnt.right) < 0 ? R.struct.RedBlackTree.rotateWithLeftChild(prnt.right) : R.struct.RedBlackTree.rotateWithRightChild(prnt.right);
289             }
290         }
291 
292     }, /** @scope R.struct.RedBlackTree.prototype */{
293 
294         getClassName:function () {
295             return "R.struct.RedBlackTree";
296         },
297 
298         /**
299          * Compare item and t.element, using compareTo, with
300          * caveat that if t is header, then item is always larger.
301          * This routine is called if is possible that t is header.
302          * If it is not possible for t to be header, use compareTo directly.
303          * @private
304          */
305         compare:function (item, t) {
306             if (t == header) {
307                 return 1;
308             }
309             else {
310                 return item.compareTo(t.element);
311             }
312         },
313 
314         /**
315          * Rotate binary tree node with left child.
316          */
317         rotateWithLeftChild:function (k2) {
318             var k1 = k2.left;
319             k2.left = k1.right;
320             k1.right = k2;
321             return k1;
322         },
323 
324         /**
325          * Rotate binary tree node with right child.
326          */
327         rotateWithRightChild:function (k1) {
328             var k2 = k1.right;
329             k1.right = k2.left;
330             k2.left = k1;
331             return k2;
332         }
333     });
334 
335 };