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 };