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