1 /** 2 * The Render Engine 3 * 4 * @fileoverview A doubly linked list. 5 * 6 * @author: Brett Fattori (brettf@renderengine.com) 7 * @author: $Author: bfattori@gmail.com $ 8 * @version: $Revision: 1572 $ 9 * 10 * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com) 11 * 12 * Permission is hereby granted, free of charge, to any person obtaining a copy 13 * of this software and associated documentation files (the "Software"), to deal 14 * in the Software without restriction, including without limitation the rights 15 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 16 * copies of the Software, and to permit persons to whom the Software is 17 * furnished to do so, subject to the following conditions: 18 * 19 * The above copyright notice and this permission notice shall be included in 20 * all copies or substantial portions of the Software. 21 * 22 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 23 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 24 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 25 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 26 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 27 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 28 * THE SOFTWARE. 29 * 30 */ 31 32 // The class this file defines and its required classes 33 R.Engine.define({ 34 "class":"R.struct.LinkedList", 35 "requires":[ 36 "R.struct.Container", 37 "R.lang.Iterator" 38 ] 39 }); 40 41 /** 42 * @class A linked list is a logical collection of objects. 43 * When a linked list is destroyed, none of the objects within it 44 * are destroyed with it. If the objects must be destroyed, call 45 * {@link #cleanUp}. This type of list is doubly-linked, which means 46 * you can traverse it both forward and backward. 47 * 48 * @param containerName {String} The name of the container 49 * @extends R.struct.Container 50 * @constructor 51 * @description Create a linked list container. 52 */ 53 R.struct.LinkedList = function () { 54 return R.struct.Container.extend(/** @scope R.struct.LinkedList.prototype */{ 55 56 _head:null, 57 _tail:null, 58 sz:0, 59 60 /** 61 * @private 62 */ 63 constructor:function (containerName) { 64 this.base(containerName || "LinkedList"); 65 this._head = null; 66 this._tail = null; 67 this.sz = 0; 68 }, 69 70 /** 71 * Release the object back into the object pool. 72 */ 73 release:function () { 74 this.base(); 75 this.clear(); 76 }, 77 78 /** 79 * Clears the container, however, all of the objects within the container 80 * are not destroyed automatically. This is to prevent the early clean up of 81 * objects which are being used by a transient container. 82 */ 83 destroy:function () { 84 this.base(); 85 }, 86 87 /** 88 * Returns the count of the number of objects within the 89 * container. 90 * 91 * @return {Number} The number of objects in the container 92 */ 93 size:function () { 94 return this.sz; 95 }, 96 97 /** 98 * Create a new node for the list 99 * @param obj {Object} The object 100 * @private 101 */ 102 _new:function (obj) { 103 var o = { 104 prev:null, 105 next:null, 106 ptr:obj 107 }; 108 return o; 109 }, 110 111 /** 112 * Find the list node at the given index. No bounds checking 113 * is performed with this function. 114 * @param idx {Number} The index where the item exists 115 * @param offset {Object} The object to start at, "head" if null 116 * @private 117 */ 118 _find:function (idx, offset) { 119 var n = offset || this._head, c = idx; 120 while (n != null && c-- > 0) { 121 n = n.next; 122 } 123 return (c > 0 ? null : n); 124 }, 125 126 /** 127 * Look through the list to find the given object. If the object is 128 * found, the list node is returned. If no object is found, the method 129 * returns <code>null</code>. 130 * 131 * @param obj {Object} The object to find 132 * @private 133 */ 134 _peek:function (obj) { 135 var n = this._head; 136 while (n != null) { 137 if (n.ptr === obj) { 138 return n; 139 } 140 n = n.next; 141 } 142 return null; 143 }, 144 145 /** 146 * Returns <tt>true</tt> if the object is in the container. 147 * @param obj {Object} The object to find 148 * @return {Boolean} 149 */ 150 contains:function (obj) { 151 return (this._peek(obj) !== null); 152 }, 153 154 /** 155 * Add an object to the container. 156 * 157 * @param obj {Object} The object to add to the container. 158 */ 159 add:function (obj) { 160 var n = this._new(obj); 161 if (this._head == null && this._tail == null) { 162 this._head = n; 163 this._tail = n; 164 } else { 165 this._tail.next = n; 166 n.prev = this._tail; 167 this._tail = n; 168 } 169 170 if (obj.getId) { 171 R.debug.Console.log("Added ", obj.getId(), "[", obj, "] to ", this.getId(), "[", this, "]"); 172 } 173 this.sz++; 174 175 // Return the list node that was added 176 return n; 177 }, 178 179 /** 180 * Concatenate a container or array to the end of this container, 181 * returning a new container with all of the elements. The 182 * array or container will be copied and appended to this 183 * container. While the actual pointers to the objects aren't deep copied, 184 * one can be assured that modifying the array or container structure being 185 * appended will not affect either container. Note, however, that modifying 186 * the objects within the container will modify the objects in the original 187 * containers as well. 188 * 189 * @param arr {R.struct.Container|Array} A container or array of objects 190 * @return {R.struct.Container} A new container with all objects from both 191 */ 192 concat:function (arr) { 193 if (arr instanceof R.struct.Container) { 194 arr = arr.getAll(); 195 } 196 var c = this.clone(); 197 c.addAll(arr); 198 return c; 199 }, 200 201 /** 202 * Append a container to the end of this container. When you append a 203 * container, its head will now point to the tail of this container and 204 * the tail of this container will become the tail of the appended container. 205 * The appended container will still exist, but navigating the container in 206 * reverse past the head of the container will navigate into the container 207 * which was appended to. If you need the containers to remain independent 208 * of eachother, see the {@link #concat} method. 209 * 210 * @param c {R.struct.Container} The container to append. 211 */ 212 append:function (c) { 213 if (!(c instanceof R.struct.LinkedList)) { 214 R.debug.Console.error("Can only append R.struct.LinkedList, or subclasses, to an R.struct.LinkedList"); 215 return; 216 } 217 218 // Create the linkage and update the tail 219 if (this._head == null && this._tail == null && 220 c._head != null && c._tail != null) { 221 // If the container is empty, but the one to append is not 222 this._head = c._head; 223 this._tail = c._tail; 224 } else if (this._head != c._head && this._tail != c._tail) { 225 c._head.prev = this._tail; 226 this._tail.next = c._head; 227 this._tail = c._tail; 228 } 229 }, 230 231 /** 232 * Insert an object into the container at the given index. Asserts if the 233 * index is out of bounds for the container. The index must be greater than 234 * or equal to zero, and less than or equal to the size of the container minus one. 235 * The effect is to extend the length of the container by one. 236 * 237 * @param index {Number} The index to insert the object at. 238 * @param obj {Object} The object to insert into the container 239 */ 240 insert:function (index, obj) { 241 Assert(!(index < 0 || index > this.size()), "Index out of range when inserting object!"); 242 var o = this._find(index); 243 var n = this._new(obj); 244 245 n.prev = o.prev; 246 n.prev.next = n; 247 n.next = o; 248 o.prev = n; 249 this.sz++; 250 251 // Return the list node that was inserted 252 return n; 253 }, 254 255 /** 256 * Replaces the given object with the new object. If the old object is 257 * not found, no action is performed. 258 * 259 * @param oldObj {Object} The object to replace 260 * @param newObj {Object} The object to put in place 261 * @return {Object} The object which was replaced 262 */ 263 replace:function (oldObj, newObj) { 264 var o = this._peek(oldObj), r = null; 265 if (o.ptr != null) { 266 r = o.ptr; 267 o.ptr = newObj; 268 } 269 return r; 270 }, 271 272 /** 273 * Replaces the object at the given index, returning the object that was there 274 * previously. Asserts if the index is out of bounds for the container. The index 275 * must be greater than or equal to zero, and less than or equal to the size of the 276 * container minus one. 277 * 278 * @param index {Number} The index at which to replace the object 279 * @param obj {Object} The object to put in place 280 * @return {Object} The object which was replaced 281 */ 282 replaceAt:function (index, obj) { 283 Assert(!(index < 0 || index > this.size()), "Index out of range when inserting object!"); 284 var o = this._find(index); 285 var r = o.ptr; 286 o.ptr = obj; 287 return r; 288 }, 289 290 /** 291 * Remove an object from the container. The object is 292 * not destroyed when it is removed from the container. 293 * 294 * @param obj {Object} The object to remove from the container. 295 * @return {Object} The object that was removed 296 */ 297 remove:function (obj) { 298 var o = this._peek(obj); 299 //AssertWarn(o != null, "Removing object from collection which is not in collection"); 300 301 if (o != null) { 302 if (o === this._head && o === this._tail) { 303 this.clear(); 304 this.sz = 0; 305 return null; 306 } 307 308 if (o === this._head) { 309 this._head = o.next; 310 if (this._head == null) { 311 this.clear(); 312 this.sz = 0; 313 return null; 314 } 315 } 316 317 if (o === this._tail) { 318 this._tail = o.prev; 319 } 320 321 if (o.next) o.next.prev = o.prev; 322 if (o.prev) o.prev.next = o.next; 323 o.prev = o.next = null; 324 this.sz--; 325 326 if (obj.getId) { 327 R.debug.Console.log("Removed ", obj.getId(), "[", obj, "] from ", this.getId(), "[", this, "]"); 328 } 329 330 return o.ptr; 331 } 332 return null; 333 }, 334 335 /** 336 * Remove an object from the container at the specified index. 337 * The object is not destroyed when it is removed. 338 * 339 * @param idx {Number} An index between zero and the size of the container minus 1. 340 * @return {Object} The object removed from the container. 341 */ 342 removeAtIndex:function (idx) { 343 Assert((idx >= 0 && idx < this.size()), "Index of out range in Container"); 344 345 var o = this._find(idx); 346 if (o === this._head) { 347 this._head = o.next; 348 } 349 if (o === this.tail) { 350 this._tail = o.prev; 351 } 352 if (o.next) o.next.prev = o.prev; 353 if (o.prev) o.prev.next = o.next; 354 o.prev = o.next = null; 355 var r = o.ptr; 356 357 R.debug.Console.log("Removed ", r.getId(), "[", r, "] from ", this.getId(), "[", this, "]"); 358 this.sz--; 359 return r; 360 }, 361 362 /** 363 * Reduce the container so that it's length is the specified length. If <code>length</code> 364 * is larger than the size of this container, no operation is performed. Setting <code>length</code> 365 * to zero is effectively the same as calling {@link #clear}. Objects which would logically 366 * fall after <code>length</code> are not automatically destroyed. 367 * 368 * @param length {Number} The maximum number of elements 369 * @return {R.struct.Container} The subset of elements being removed 370 */ 371 reduce:function (length) { 372 if (length > this.size()) { 373 return R.struct.Container.create(); 374 } 375 var a = this.getAll(); 376 var sub = this.subset(length, a.length, a); 377 if (length == 0) { 378 return sub; 379 } 380 381 a.length = length; 382 this.clear(); 383 for (var i in a) { 384 this.add(a[i]); 385 } 386 return sub; 387 }, 388 389 /** 390 * Get the object at the index specified. If the container has been 391 * sorted, objects might not be in the position you'd expect. 392 * 393 * @param idx {Number} The index of the object to get 394 * @return {Object} The object at the index within the container 395 * @throws {Error} Index out of bounds if the index is out of the list of objects 396 */ 397 get:function (idx) { 398 if (idx < 0 || idx > this.size()) { 399 throw new Error("Index out of bounds"); 400 } 401 return this._find(idx).ptr; 402 }, 403 404 /** 405 * Get an array of all of the objects in this container. 406 * @return {Array} An array of all of the objects in the container 407 */ 408 getAll:function () { 409 var a = [], i = this.iterator(); 410 while (i.hasNext()) { 411 a.push(i.next()); 412 } 413 i.destroy(); 414 return a; 415 }, 416 417 /** 418 * Filters the container with the function, returning a new <code>Container</code> 419 * with the objects that pass the test in the function. If the object should be 420 * included in the new <code>Container</code>, the function should return <code>true</code>. 421 * The function takes one argument: the object being processed. 422 * Unless otherwise specified, <code>this</code> refers to the container. 423 * 424 * @param fn {Function} The function to execute for each object 425 * @param [thisp] {Object} The object to use as <code>this</code> inside the function 426 * @return {R.struct.Container} 427 */ 428 filter:function (fn, thisp) { 429 var arr = R.engine.Support.filter(this.getAll(), fn, thisp || this); 430 var c = R.struct.Container.create(); 431 c.addAll(arr); 432 return c; 433 }, 434 435 /** 436 * Remove all references to objects in the container. None of the objects are 437 * actually destroyed. Use {@link #cleanUp} to remove and destroy all objects. 438 */ 439 clear:function () { 440 this._head = null; 441 this._tail = null; 442 this.sz = 0; 443 }, 444 445 /** 446 * Get the array of all objects within this container. If a filtering 447 * function is provided, only objects matching the filter will be 448 * returned from the object collection. 449 * <p/> 450 * The filter function needs to return <tt>true</tt> for each element 451 * that should be contained in the filtered set. The function will be 452 * passed the following arguments: 453 * <ul> 454 * <li>element - The array element being operated upon</li> 455 * <li>index - The index of the element in the array</li> 456 * <li>array - The entire array of elements in the container</li> 457 * </ul> 458 * Say you wanted to filter a host objects components based on a 459 * particular type. You might do something like the following: 460 * <pre> 461 * var logicComponents = host.getObjects(function(el, idx) { 462 * if (el.getType() == BaseComponent.TYPE_LOGIC) { 463 * return true; 464 * } 465 * }); 466 * </pre> 467 * 468 * @param filterFn {Function} A function to filter the set of 469 * elements with. If you pass <tt>null</tt> the 470 * entire set of objects will be returned. 471 * @return {Array} The array of filtered objects 472 */ 473 getObjects:function (filterFn) { 474 var a = this.getAll(); 475 if (filterFn) { 476 return R.engine.Support.filter(a, filterFn); 477 } else { 478 return a; 479 } 480 }, 481 482 /** 483 * Sort the objects within the container, using the provided function. 484 * The function will be provided object A and B. If the result of the 485 * function is less than zero, A will be sorted before B. If the result is zero, 486 * A and B retain their order. If the result is greater than zero, A will 487 * be sorted after B. 488 * 489 * @param [fn] {Function} The function to sort with. If <tt>null</tt> the objects 490 * will be sorted in "natural" order. 491 */ 492 sort:function (fn) { 493 R.debug.Console.log("Sorting ", this.getName(), "[" + this.getId() + "]"); 494 var a = this.getAll().sort(fn); 495 496 // Relink 497 this._head = this._new(a[0]); 498 var p = this._head; 499 for (var i = 1; i < a.length; i++) { 500 var n = this._new(a[i]); 501 p.next = n; 502 n.prev = p; 503 p = n; 504 } 505 this._tail = p; 506 this.sz = a.length; 507 }, 508 509 /** 510 * Returns a property object with accessor methods to modify the property. 511 * @return {Object} The properties object 512 */ 513 getProperties:function () { 514 var self = this; 515 var prop = this.base(self); 516 return $.extend(prop, { 517 "Size":[function () { 518 return self.size(); 519 }, 520 null, false] 521 }); 522 }, 523 524 /** 525 * Serializes a container to XML. 526 * @return {String} The XML string 527 */ 528 toXML:function (indent) { 529 indent = indent ? indent : ""; 530 var props = this.getProperties(); 531 var xml = indent + "<" + this.constructor.getClassName(); 532 for (var p in props) { 533 // If the value should be serialized, call it's getter 534 if (props[p][2]) { 535 xml += " " + p.toLowerCase() + "=\"" + props[p][0]().toString() + "\""; 536 } 537 } 538 xml += ">\n"; 539 540 // Dump children 541 var all = this.getAll(); 542 for (var o in all) { 543 xml += all[o].toXML(indent + " "); 544 } 545 546 // Closing tag 547 xml += indent + "</" + this.constructor.getClassName() + ">\n"; 548 return xml; 549 }, 550 551 iterator:function () { 552 return R.lang.Iterator.create(this); 553 } 554 555 }, /** @scope R.struct.LinkedList.prototype */{ 556 /** 557 * Get the class name of this object 558 * 559 * @return {String} "R.struct.LinkedList" 560 */ 561 getClassName:function () { 562 return "R.struct.LinkedList"; 563 }, 564 565 /** @private */ 566 resolved:function () { 567 R.struct.LinkedList.EMPTY = new R.struct.LinkedList("EMPTY"); 568 }, 569 570 /** 571 * Create a new <code>R.struct.LinkedList</code> from an <code>Array</code>. 572 * @param array {Array} An array of objects 573 * @return {R.struct.LinkedList} 574 * @static 575 */ 576 fromArray:function (array) { 577 var c = R.struct.LinkedList.create(); 578 c.addAll(array); 579 return c; 580 }, 581 582 /** 583 * An empty container - DO NOT MODIFY!! 584 * @type {R.struct.LinkedList} 585 */ 586 EMPTY:null 587 588 }); 589 590 };