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: 1570 $ 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.Container", 35 "requires":[ 36 "R.engine.BaseObject", 37 "R.lang.Iterator" 38 ] 39 }); 40 41 /** 42 * @class A container is a logical collection of objects. A container 43 * is responsible for maintaining the list of objects within it. 44 * When a container is destroyed, none of the objects within the container 45 * are destroyed with it. If the objects must be destroyed, call 46 * {@link #cleanUp}. A container is a doubly linked list. 47 * 48 * @param containerName {String} The name of the container 49 * @extends R.engine.BaseObject 50 * @constructor 51 * @description Create a container. 52 */ 53 R.struct.Container = function () { 54 return R.engine.BaseObject.extend(/** @scope R.struct.Container.prototype */{ 55 56 objects:null, 57 58 /** 59 * @private 60 */ 61 constructor:function (containerName, initial) { 62 this.base(containerName || "Container"); 63 this.objects = []; 64 if (!R.isUndefined(initial)) { 65 this.addAll(initial); 66 } 67 }, 68 69 /** 70 * Release the object back into the object pool. 71 */ 72 release:function () { 73 this.objects = null; 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.objects.length; 95 }, 96 97 /** 98 * Returns <tt>true</tt> if the object is in the container. 99 * @param obj {Object} The object to find 100 * @return {Boolean} 101 */ 102 contains:function (obj) { 103 return (R.engine.Support.indexOf(this.objects, obj) != -1); 104 }, 105 106 /** 107 * Add an object to the container. 108 * 109 * @param obj {Object} The object to add to the container. 110 */ 111 add:function (obj) { 112 this.objects.push(obj); 113 114 if (obj.getId) { 115 R.debug.Console.log("Added ", obj.getId(), "[", obj, "] to ", this.getId(), "[", this, "]"); 116 } 117 118 // Return the index of the added object 119 return (this.objects.length - 1); 120 }, 121 122 /** 123 * Add all of the objects in the container or array to this container, at the end 124 * of this container. If "arr" is a container, the head of "arr" is joined to the 125 * tail of this, resulting in a very fast operation. Because this method, when 126 * performed on a container, is just joining the two lists, no duplication of 127 * elements from the container is performed. As such, removing elements from the 128 * new container will affect this container as well. 129 * 130 * @param arr {R.struct.Container|Array} A container or array of objects 131 */ 132 addAll:function (arr) { 133 var i; 134 if (arr instanceof R.struct.Container) { 135 for (i = arr.iterator(); i.hasNext();) { 136 this.add(i.next()); 137 } 138 i.destroy(); 139 } else if ($.isArray(arr)) { 140 for (i in arr) { 141 this.add(arr[i]); 142 } 143 } else { 144 Assert(false, "R.struct.Container.addAll() - invalid object!") 145 } 146 }, 147 148 /** 149 * Clone this container, returning a new container which points to all of the 150 * objects in this container. 151 * @return {R.struct.Container} A new container with all of the objects from the current container 152 */ 153 clone:function () { 154 var c = this.constructor.create(); 155 c.addAll(this.getAll()); 156 return c; 157 }, 158 159 /** 160 * Concatenate a container or array to the end of this container, 161 * returning a new container with all of the elements. The 162 * array or container will be copied and appended to this 163 * container. While the actual pointers to the objects aren't deep copied, 164 * one can be assured that modifying the array or container structure being 165 * appended will not affect either container. Note, however, that modifying 166 * the objects within the container will modify the objects in the original 167 * containers as well. 168 * 169 * @param arr {R.struct.Container|Array} A container or array of objects 170 * @return {R.struct.Container} A new container with all objects from both 171 */ 172 concat:function (arr) { 173 if (arr instanceof R.struct.Container) { 174 arr = arr.getAll(); 175 } 176 var c = this.clone(); 177 c.objects = c.objects.concat(arr); 178 return c; 179 }, 180 181 /** 182 * Append a container to the end of this container. When you append a 183 * container, its head will now point to the tail of this container and 184 * the tail of this container will become the tail of the appended container. 185 * The appended container will still exist, but navigating the container in 186 * reverse past the head of the container will navigate into the container 187 * which was appended to. If you need the containers to remain independent 188 * of eachother, see the {@link #concat} method. 189 * 190 * @param c {R.struct.Container} The container to append. 191 */ 192 append:function (c) { 193 if (!(c instanceof R.struct.Container)) { 194 R.debug.Console.error("Can only append R.struct.Container, or subclasses, to an R.struct.Container"); 195 return; 196 } 197 198 this.objects = this.objects.concat(c.getAll()); 199 }, 200 201 /** 202 * Insert an object into the container at the given index. Asserts if the 203 * index is out of bounds for the container. The index must be greater than 204 * or equal to zero, and less than or equal to the size of the container minus one. 205 * The effect is to extend the length of the container by one. 206 * 207 * @param index {Number} The index to insert the object at. 208 * @param obj {Object} The object to insert into the container 209 */ 210 insert:function (index, obj) { 211 Assert(!(index < 0 || index > this.size()), "Index out of range when inserting object!"); 212 213 this.objects.splice(index, 0, obj); 214 215 // Return the list node that was inserted 216 return index; 217 }, 218 219 /** 220 * Replaces the given object with the new object. If the old object is 221 * not found, no action is performed. 222 * 223 * @param oldObj {Object} The object to replace 224 * @param newObj {Object} The object to put in place 225 * @return {Object} The object which was replaced 226 */ 227 replace:function (oldObj, newObj) { 228 var i = R.engine.Support.indexOf(this.objects, oldObj); 229 this.objects[i] = newObj; 230 return oldObj; 231 }, 232 233 /** 234 * Replaces the object at the given index, returning the object that was there 235 * previously. Asserts if the index is out of bounds for the container. The index 236 * must be greater than or equal to zero, and less than or equal to the size of the 237 * container minus one. 238 * 239 * @param index {Number} The index at which to replace the object 240 * @param obj {Object} The object to put in place 241 * @return {Object} The object which was replaced 242 */ 243 replaceAt:function (index, obj) { 244 Assert(!(index < 0 || index > this.size()), "Index out of range when inserting object!"); 245 var r = this.objects[index]; 246 this.objects[index] = obj; 247 return r; 248 }, 249 250 /** 251 * Remove an object from the container. The object is 252 * not destroyed when it is removed from the container. 253 * 254 * @param obj {Object} The object to remove from the container. 255 * @return {Object} The object that was removed 256 */ 257 remove:function (obj) { 258 var r = this.objects.splice(R.engine.Support.indexOf(this.objects, obj), 1); 259 if (obj.getId) { 260 R.debug.Console.log("Removed ", obj.getId(), "[", obj, "] from ", this.getId(), "[", this, "]"); 261 } 262 return obj; 263 }, 264 265 /** 266 * Remove an object from the container at the specified index. 267 * The object is not destroyed when it is removed. 268 * 269 * @param idx {Number} An index between zero and the size of the container minus 1. 270 * @return {Object} The object removed from the container. 271 */ 272 removeAtIndex:function (idx) { 273 Assert((idx >= 0 && idx < this.size()), "Index of out range in Container"); 274 var r = this.objects.splice(idx, 1); 275 R.debug.Console.log("Removed ", r.getId(), "[", r, "] from ", this.getId(), "[", this, "]"); 276 return r; 277 }, 278 279 /** 280 * Reduce the container so that it's length is the specified length. If <code>length</code> 281 * is larger than the size of this container, no operation is performed. Setting <code>length</code> 282 * to zero is effectively the same as calling {@link #clear}. Objects which would logically 283 * fall after <code>length</code> are not automatically destroyed. 284 * 285 * @param length {Number} The maximum number of elements 286 * @return {R.struct.Container} The subset of elements being removed 287 */ 288 reduce:function (length) { 289 if (length > this.size()) { 290 return R.struct.Container.create(); 291 } 292 var a = this.getAll(); 293 var sub = this.subset(length, a.length, a); 294 if (length == 0) { 295 return sub; 296 } 297 298 a.length = length; 299 return sub; 300 }, 301 302 /** 303 * A new <code>Container</code> which is a subset of the current container 304 * from the starting index (inclusive) to the ending index (exclusive). Modifications 305 * made to the objects in the subset will affect this container's objects. 306 * 307 * @param start {Number} The starting index in the container 308 * @param end {Number} The engine index in the container 309 * @return {R.struct.Container} A subset of the container. 310 */ 311 subset:function (start, end, b) { 312 var a = b || this.getAll(); 313 var c = this.constructor.create(); 314 for (var i = start; i < end; i++) { 315 c.add(a[i]); 316 } 317 return c; 318 }, 319 320 /** 321 * Get the object at the index specified. If the container has been 322 * sorted, objects might not be in the position you'd expect. 323 * 324 * @param idx {Number} The index of the object to get 325 * @return {Object} The object at the index within the container 326 * @throws {Error} Index out of bounds if the index is out of the list of objects 327 */ 328 get:function (idx) { 329 if (idx < 0 || idx > this.size()) { 330 throw new Error("Index out of bounds"); 331 } 332 return this.objects[idx]; 333 }, 334 335 /** 336 * Get an array of all of the objects in this container. 337 * @return {Array} An array of all of the objects in the container 338 */ 339 getAll:function () { 340 return this.objects; 341 }, 342 343 /** 344 * For each object in the container, the function will be executed. 345 * The function takes one argument: the object being processed. 346 * Unless otherwise specified, <code>this</code> refers to the container. 347 * <p/> 348 * Returning <tt>false</tt> from <tt>fn</tt> will immediately halt any 349 * further iteration over the container. 350 * 351 * @param fn {Function} The function to execute for each object 352 * @param [thisp] {Object} The object to use as <code>this</code> inside the function 353 */ 354 forEach:function (fn, thisp) { 355 var itr = this.iterator(); 356 var result = true; 357 var hasMethod = !!(thisp && thisp.isDestroyed); 358 while ((hasMethod ? !thisp.isDestroyed() && result : result) && itr.hasNext()) { 359 result = fn.call(thisp || this, itr.next()); 360 result = (result == undefined ? true : result); 361 } 362 itr.destroy(); 363 }, 364 365 /** 366 * Filters the container with the function, returning a new <code>Container</code> 367 * with the objects that pass the test in the function. If the object should be 368 * included in the new <code>Container</code>, the function should return <code>true</code>. 369 * The function takes one argument: the object being processed. 370 * Unless otherwise specified, <code>this</code> refers to the container. 371 * 372 * @param fn {Function} The function to execute for each object 373 * @param [thisp] {Object} The object to use as <code>this</code> inside the function 374 * @return {R.struct.Container} 375 */ 376 filter:function (fn, thisp) { 377 var arr = R.engine.Support.filter(this.getAll(), fn, thisp || this); 378 var c = this.constructor.create(); 379 c.objects = arr; 380 return c; 381 }, 382 383 /** 384 * Remove all references to objects in the container. None of the objects are 385 * actually destroyed. Use {@link #cleanUp} to remove and destroy all objects. 386 */ 387 clear:function () { 388 this.objects = []; 389 this.length = 0; 390 }, 391 392 /** 393 * Remove and destroy all objects in the container. 394 */ 395 cleanUp:function () { 396 var a = this.getAll(), h; 397 while (a.length > 0) { 398 h = a.shift(); 399 if (h.destroy) { 400 h.destroy(); 401 } 402 } 403 this.clear(); 404 }, 405 406 /** 407 * Get the array of all objects within this container. If a filtering 408 * function is provided, only objects matching the filter will be 409 * returned from the object collection. 410 * <p/> 411 * The filter function needs to return <tt>true</tt> for each element 412 * that should be contained in the filtered set. The function will be 413 * passed the following arguments: 414 * <ul> 415 * <li>element - The array element being operated upon</li> 416 * <li>index - The index of the element in the array</li> 417 * <li>array - The entire array of elements in the container</li> 418 * </ul> 419 * Say you wanted to filter a host objects components based on a 420 * particular type. You might do something like the following: 421 * <pre> 422 * var logicComponents = host.getObjects(function(el, idx) { 423 * if (el.getType() == BaseComponent.TYPE_LOGIC) { 424 * return true; 425 * } 426 * }); 427 * </pre> 428 * 429 * @param filterFn {Function} A function to filter the set of 430 * elements with. If you pass <tt>null</tt> the 431 * entire set of objects will be returned. 432 * @return {Array} The array of filtered objects 433 */ 434 getObjects:function (filterFn) { 435 var a = this.getAll(); 436 if (filterFn) { 437 return R.engine.Support.filter(a, filterFn); 438 } else { 439 return a; 440 } 441 }, 442 443 /** 444 * Sort the objects within the container, using the provided function. 445 * The function will be provided object A and B. If the result of the 446 * function is less than zero, A will be sorted before B. If the result is zero, 447 * A and B retain their order. If the result is greater than zero, A will 448 * be sorted after B. 449 * 450 * @param [fn] {Function} The function to sort with. If <tt>null</tt> the objects 451 * will be sorted in "natural" order. 452 */ 453 sort:function (fn) { 454 R.debug.Console.log("Sorting ", this.getName(), "[" + this.getId() + "]"); 455 this.objects.sort(fn); 456 }, 457 458 /** 459 * Returns a property object with accessor methods to modify the property. 460 * @return {Object} The properties object 461 */ 462 getProperties:function () { 463 var self = this; 464 var prop = this.base(self); 465 return $.extend(prop, { 466 "Size":[function () { 467 return self.size(); 468 }, 469 null, false] 470 }); 471 }, 472 473 /** 474 * Serializes a container to XML. 475 * @return {String} The XML string 476 */ 477 toXML:function (indent) { 478 indent = indent ? indent : ""; 479 var props = this.getProperties(); 480 var xml = indent + "<" + this.constructor.getClassName(); 481 for (var p in props) { 482 // If the value should be serialized, call it's getter 483 if (props[p][2]) { 484 xml += " " + p.toLowerCase() + "=\"" + props[p][0]().toString() + "\""; 485 } 486 } 487 xml += ">\n"; 488 489 // Dump children 490 var all = this.getAll(); 491 for (var o in all) { 492 xml += all[o].toXML(indent + " "); 493 } 494 495 // Closing tag 496 xml += indent + "</" + this.constructor.getClassName() + ">\n"; 497 return xml; 498 }, 499 500 /** 501 * Returns an iterator over the collection. 502 * @return {R.lang.Iterator} An iterator 503 */ 504 iterator:function () { 505 return R.lang.Iterator.create(this.objects, this); 506 } 507 508 }, /** @scope R.struct.Container.prototype */{ 509 /** 510 * Get the class name of this object 511 * 512 * @return {String} "R.struct.Container" 513 */ 514 getClassName:function () { 515 return "R.struct.Container"; 516 }, 517 518 /** @private */ 519 resolved:function () { 520 R.struct.Container.EMPTY = new R.struct.Container("EMPTY"); 521 }, 522 523 /** 524 * Create a new <code>R.struct.Container</code> from an <code>Array</code>. 525 * @param array {Array} An array of objects 526 * @return {R.struct.Container} 527 * @static 528 */ 529 fromArray:function (array) { 530 var c = R.struct.Container.create(); 531 c.addAll(array); 532 return c; 533 }, 534 535 /** 536 * An empty container - DO NOT MODIFY!! 537 * @type {R.struct.Container} 538 */ 539 EMPTY:null 540 541 }); 542 543 };