source: gs3-extensions/seaweed-debug/trunk/src/collections/DoublyLinkedList.js@ 25160

Last change on this file since 25160 was 25160, checked in by sjm84, 12 years ago

Initial cut at a version of seaweed for debugging purposes. Check it out live into the web/ext folder
File size: 8.7 KB
Line 
1/*
2 * file: DoublyLinkedList.js
3 *
4 * @BEGINLICENSE
5 * Copyright 2010 Brook Novak (email : [email protected])
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 * @ENDLICENSE
18 */
19bootstrap.provides("collections.DoublyLinkedList");
20
21/**
22 * @class
23 *
24 * A Doubly Linked List. Supports all data types.
25 * Because this collection creates cyclic references, you should explicitely
26 * call de.collections.DoublyLinkedList.clear when finished with a doubly linked
27 * list to avoid memory leaks in browsers which uses reference counting garbage collections
28 * (e.g. IE and FF).
29 *
30 * @author Brook Novak
31 */
32var _DoublyLinkedList = function(){
33
34 var cls = function(){
35
36 /**
37 * @memberOf de.collections.DoublyLinkedList
38 * Read only member that is the current length of the linked list.
39 * @type Number
40 */
41 this.length = 0;
42
43 /**
44 * @memberOf de.collections.DoublyLinkedList
45 * Read only member that is the current head node of the linked list.
46 * @type de.collections.DLLNode
47 */
48 this.head = null;
49
50 /**
51 * @memberOf de.collections.DoublyLinkedList
52 * Read only member that is the current tail node of the linked list.
53 * @type de.collections.DLLNode
54 */
55 this.tail = null;
56 };
57
58 // Define the class body
59 cls.prototype = {
60
61 /**
62 * Adds data to the end of the linked list
63 *YYY
64 * @param {Object} data Data to add
65 */
66 add: function(data){
67
68 //create a new item object, place data in
69 var node = {
70 data: data,
71 next: null,
72 prev: null
73 };
74
75 //special case: no items in the list yet
76 if (this.length == 0) {
77 this.head = node;
78 this.tail = node;
79 } else {
80
81 //attach to the tail node
82 this.tail.next = node;
83 node.prev = this.tail;
84 this.tail = node;
85 }
86
87 //don't forget to update the count
88 this.length++;
89
90 },
91
92 /**
93 * Removes an item from the list.
94 * @param {Object} item An item to remove.
95 * @return {Boolean} True if item existed and was removed. False if the item did not exist.
96 */
97 remove: function(item){
98 var current = this.head;
99 while (current) {
100 if (current.data == item) {
101 removeNode(this, current);
102 return true;
103 }
104 current = current.next;
105 }
106 return false;
107 },
108
109 /**
110 * Removes a node at the given index.
111 *
112 * @param {Number} index The index to remove at.
113 *
114 * @return {Object} The removed data. Otherwise null if index out of bounds. Note that
115 * if data is null, null will also be returned.
116 */
117 removeAtIndex: function(index){
118
119 //check for out-of-bounds values
120 if (index > -1 && index < this.length) {
121
122 var current;
123
124 // Choose faster scan direction
125 if (index < (this.length / 2)) { // Head to tail
126 current = this.head;
127 for (var i = 0; i < index; i++) {
128 current = current.next;
129 }
130 } else { // Tail to head
131 current = this.tail;
132 for (var i = this.length - 1; i > index; i--) {
133 current = current.prev;
134 }
135 }
136
137 removeNode(this, current);
138
139 return current.data;
140 }
141
142 return null;
143 },
144
145 /**
146 * Removes the last node in the list and returns the item. O(1) operation
147 * @return {Object} The last item in the list.
148 */
149 pop: function(){
150 return this.removeAtIndex(this.length - 1);
151 },
152
153 /**
154 * Removes proceding items after atNode. I.E. atNode becomes the new tail.
155 *
156 * @param {Object} atNode The which will become the new tail.
157 *
158 * @return {Boolean} True if the operation succeeded (atNode is a node in this linked list),
159 * False if the operation failed (atNode is not a node in this linked list).
160 */
161 chop: function(atNode){
162
163 var current = this.tail,
164 newLength = this.length;
165
166 // Search for atNode... count how far it is from the tail
167 while (current && current != atNode) {
168 current = current.prev;
169 newLength--;
170 }
171
172 // If atNode doesn't exist, return false
173 if (!current)
174 return false;
175
176 // If atNode has a next-node (i.e. not the tail) then
177 // chop off the proceeding nodes
178 if (current.next) {
179
180 var removedNodes = current.next;
181 while (removedNodes) { // Kill all ref n removed nodes
182 removedNodes.prev.next = null;
183 removedNodes.prev = null;
184 removedNodes = removedNodes.next;
185 }
186
187 // Set the new tail
188 this.tail = current;
189
190 // Be sure to update the length
191 this.length = newLength;
192 }
193
194 return true;
195
196 },
197
198 /**
199 * Clears the linked list.. so list becomes empty.
200 * Call this whenever you are finished with a Doubly linked list to avoid memory
201 * leaks caused by cyclic references.
202 */
203 clear: function(){
204 while (this.head) {
205 var node = this.head;
206 this.head = node.next;
207 node.prev = node.next = null;
208 }
209 this.tail = null;
210 this.length = 0;
211 },
212
213 /**
214 * Applies a function to all items in this list from the head to the tail.
215 *
216 * @param {Function} func A function to apply to each item. Takes one argument: the item.
217 * Return false to abort iteration.
218 */
219 iterate: function(func){
220 var current = this.head;
221 while (current) {
222 var res = func(current.data);
223 if (res === false) break;
224 current = current.next;
225 }
226 }
227
228 }; // End clas prototype
229
230 /**
231 * @function
232 * @description
233 * An alias for de.collections.DoublyLinkedList#add
234 *
235 * @see de.collections.DoublyLinkedList#add
236 */
237 cls.prototype.push = cls.prototype.add;
238
239
240 /**
241 * @private
242 * Removes a node from a doubly linked list
243 *
244 * @param {de.collections.DoublyLinkedList} dll The DLL to remove from
245 *
246 * @param {de.collections.DLLNode} node The node to remove - must be a node in the DLL.
247 */
248 function removeNode(dll, node){
249
250 if (dll.length == 1) {
251 dll.clear();
252 return;
253 }
254
255 if (node == dll.head) {
256 dll.head = node.next;
257 dll.head.prev = null;
258 node.next = null; // Avoid cyclic reference
259 } else if (node == dll.tail) {
260 dll.tail = node.prev;
261 dll.tail.next = null;
262 node.prev = null; // Avoid cyclic reference
263 } else {
264 node.prev.next = node.next;
265 node.next.prev = node.prev;
266 node.next = node.prev = null; // Avoid cyclic reference
267 }
268
269 dll.length--;
270 }
271
272 return cls;
273}();
274
275/**
276 * Exposure of _DoublyLinkedList internal
277 * @see _DoublyLinkedList
278 */
279de.collections.DoublyLinkedList = _DoublyLinkedList;
Note: See TracBrowser for help on using the repository browser.