1 dojo.provide("calitha.collections.LinkedList");
  2 dojo.require("calitha.collections.AbstractList");
  3 dojo.require("calitha.collections.linkedlist.EntryIndexCache");
  4 dojo.require("calitha.collections.linkedlist.Entry");
  5 dojo.require("calitha.collections.linkedlist.ListIterator");
  6 dojo.require("calitha.exception.IndexOutOfBoundsException");
  7 
  8 dojo.declare("calitha.collections.LinkedList", calitha.collections.AbstractList,
  9 /** @lends calitha.collections.LinkedList#*/
 10 {
 11     /**
 12      * @constructs
 13      * @extends calitha.collections.AbstractList
 14      * @description Linked list implementation of the List interface.
 15      * <p>This class is similar to the
 16      * <a href="http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html">Java LinkedList class</a>
 17      */
 18     constructor: function()
 19     {
 20         this._first = null;
 21         this._last = null;
 22         this._size = 0;
 23         this._cache = new calitha.collections.linkedlist.EntryIndexCache();
 24     }
 25     ,
 26     clear: function()
 27     {
 28         this._modCount++;
 29         var entry = this._first;
 30         while (entry != null)
 31         {
 32             var nextEntry = entry.next;
 33             entry.prev = null;
 34             entry.next = null;
 35             entry = nextEntry;
 36         }
 37         this._first = null;
 38         this._last = null;
 39         this._size = 0;
 40         this._cache.entry = null;
 41     }
 42     ,
 43     get: function(/**Number*/ index)
 44     {
 45         return this._getEntry(index).element;
 46     }
 47     ,
 48     insert: function(/**Number*/ index, /**Object*/ element)
 49     {
 50         if (index < 0 || index > this.size())
 51         {
 52             throw new calitha.exception.IndexOutOfBoundsException(Error(), index, this._size);
 53         }
 54         this._modCount++;
 55         var newEntry;
 56         if (index === this.size())
 57         {
 58             newEntry = new calitha.collections.linkedlist.Entry(element, this._last, null);
 59         }
 60         else
 61         {
 62             var entry = this._getEntry(index);
 63             this._cache.index++; // going to insert entry at this location
 64             newEntry = new calitha.collections.linkedlist.Entry(element, entry.prev, entry);
 65         }
 66         this._updateInsertLinks(newEntry);
 67         this._size++;
 68     }
 69     ,
 70     listIterator: function(/**Number?*/ index)
 71     {
 72         return new calitha.collections.linkedlist.ListIterator(this, index);
 73     }
 74     ,
 75     del: function(/**Number*/ index)
 76     {
 77         if (index < 0 || index >= this.size())
 78         {
 79             throw new calitha.exception.IndexOutOfBoundsException(Error(), index, this._size);
 80         }
 81         this._modCount++;
 82         var entry = this._getEntry(index);
 83         return this._removeEntry(entry);
 84     }
 85     ,
 86     set: function(/**Number*/ index, /**Object*/ element)
 87     {
 88         this._modCount++;
 89         var entry = this._getEntry(index);
 90         var oldValue = entry.element;
 91         entry.element = element;
 92         return oldValue;        
 93     }
 94     ,
 95     size: function()
 96     {
 97         return this._size;
 98     }
 99     ,
100     _getEntry: function(/**Number*/ index)
101     {
102         if (index < 0 || index >= this._size)
103         {
104             throw new calitha.exception.IndexOutOfBoundsException(Error(), index, this._size);
105         }
106 
107         //noinspection UnnecessaryLocalVariableJS
108         var distanceFromFirst = index;
109         var distanceFromLast = index - (this._size - 1);
110         var distanceFromCache;
111         if (this._cache.entry === null)
112         {
113             distanceFromCache = Number.POSITIVE_INFINITY;
114         }
115         else
116         {
117             distanceFromCache = index - this._cache.index;
118         }
119 
120         var entry;
121         var distance;
122         if ((distanceFromFirst <= Math.abs(distanceFromLast)) && (distanceFromFirst <= Math.abs(distanceFromCache)))
123         {
124             entry = this._first;
125             distance = distanceFromFirst;
126         }
127         else if (Math.abs(distanceFromLast) <= Math.abs(distanceFromCache))
128         {
129             entry = this._last;
130             distance = distanceFromLast;
131         }
132         else
133         {
134             entry = this._cache.entry;
135             distance = distanceFromCache;
136         }
137 
138         entry = this._travel(entry, distance);
139         this._cache.index = index;
140         this._cache.entry = entry;
141         return entry;
142     }
143     ,
144     _removeEntry: function(/**calitha.collections.linkedlist.Entry*/ entry)
145     {
146         if (entry.prev != null)
147             entry.prev.next = entry.next;
148         if (entry.next != null)
149             entry.next.prev = entry.prev;
150         if (entry === this._first)
151             this._first = entry.next;
152         if (entry === this._last)
153             this._last = entry.prev;
154 
155         this._size--;
156         this._cache.entry = null;
157         return entry.element;
158     }
159     ,
160     _travel: function(/**calitha.collections.linkedlist.Entry*/ entry, /**Number*/ distance)
161     {
162         var i;
163         if (distance >= 0)
164         {
165             for (i = 0; i < distance; i++)
166             {
167                 entry = entry.next;
168             }
169             return entry;
170         }
171         else
172         {
173             distance = Math.abs(distance);
174             for (i = 0; i < distance; i++)
175             {
176                 entry = entry.prev;
177             }
178             return entry;
179         }
180     }
181     ,
182     _updateInsertLinks: function(/**calitha.collections.linkedlist.Entry*/ entry)
183     {
184         if (entry.prev === null)
185         {
186             this._first = entry;
187         }
188         else
189         {
190             entry.prev.next = entry;
191         }
192         if (entry.next === null)
193         {
194             this._last = entry;
195         }
196         else
197         {
198             entry.next.prev = entry;
199         }
200     }
201 
202 });
203