1 /**
  2  * This file is part of the smilText parser implemented in JavaScript,
  3  *
  4  * Copyright (C) 2003-2009 Stichting CWI, 
  5  * Science Park 123, 1098 XG Amsterdam, The Netherlands.
  6  *
  7  * smilText parser in JavaScript is free software; you can redistribute it and/or modify
  8  * it under the terms of the GNU Lesser General Public License as published by
  9  * the Free Software Foundation; either version 2.1 of the License, or
 10  * (at your option) any later version.
 11  *
 12  * smilText parser in JavaScript is distributed in the hope that it will be useful,
 13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 15  * GNU Lesser General Public License for more details.
 16  *
 17  * You should have received a copy of the GNU Lesser General Public License
 18  * along with smilText parser in JavaScript; if not, write to the Free Software
 19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 20  */
 21 
 22 /**
 23  @name cwi.adt
 24  @namespace Hold abstract data types.
 25  @version 1.0
 26  @author <a href="mailto:rlaiola@cwi.nl">Rodrigo Laiola Guimaraes</a>
 27 */
 28 Namespace("cwi.adt");
 29 
 30 
 31 
 32 
 33 
 34 /**
 35  * Implementation of Hashtable
 36  * @constructor
 37  * @author Uzi Refaeli
 38  * @see <a href='http://code.google.com/p/magic-table/source/browse/trunk/magic-table/javascript/Hashtable.js?r=37'>reference</a>
 39 */
 40 cwi.adt.Hashtable = function()
 41 {
 42 	JSINER.extend(this);
 43 	
 44 	//============= Propertiess =================
 45 	this.hash	 	= new Array();
 46 	this.keys		= new Array();
 47 };
 48 
 49 /**
 50  * Store an element related to a given key.
 51  * @param {string} key key name
 52  * @param {Object} value the object to be inserted
 53  */
 54 cwi.adt.Hashtable.prototype.put = function (key, value)
 55 {
 56 	if (value == null)
 57 		return;
 58 
 59 	if (this.hash[key] == null)
 60 		this.keys[this.keys.length] = key;
 61 
 62 	this.hash[key] = value;
 63 }
 64 
 65 /**
 66  * Return an element related to a given key.
 67  * @param {string} key key name
 68  * @return {Object} The object related to the given key
 69  */
 70 cwi.adt.Hashtable.prototype.get = function (key)
 71 {
 72 	return this.hash[key];
 73 }
 74 
 75 /**
 76  * Remove and return the element given its key.
 77  * @param {string} key key name
 78  * @return {Object}
 79  */
 80 cwi.adt.Hashtable.prototype.remove = function (key) 
 81 {
 82 	var old = null;
 83 	for (var i = 0; i < this.keys.length; i++){
 84 		//did we found our key?
 85 		if (key == this.keys[i]){
 86 			// Store old value
 87 			old = this.hash[this.keys[i]];
 88 			//remove it from the hash
 89 			this.hash[this.keys[i]] = null;
 90 			//and throw away the key...
 91 			this.keys.splice(i ,1);
 92 			break;
 93 		}
 94 	}
 95 	return old;
 96 }
 97 
 98 /**
 99  * Return the number of elements in the Hashtable.
100  * @return {integer}
101  */
102 cwi.adt.Hashtable.prototype.getSize = function ()
103 {
104     return this.keys.length;
105 }
106 
107 /**
108  * Return a string representation of the Hashtable object in the form of a set of entries,
109  * enclosed in braces and separated by the ASCII characters " ; " (semicolon and space).
110  * Each entry is rendered as the key, an equals sign =, and the associated element,
111  * where the toString method is used to convert the key and element to strings.
112  * @return {string}
113  */
114 cwi.adt.Hashtable.prototype.toString = function ()
115 {
116 	try {
117 		var s = new Array(this.keys.length);
118 		s[s.length] = " { ";
119 
120 		for (var i = 0; i < this.keys.length; i++){
121 			s[s.length] = this.keys[i];
122 			s[s.length] = "=";
123 			var v = this.hash[this.keys[i]];
124 			if (v)
125 				s[s.length] = v.toString();
126 			else
127 				s[s.length] = "null";
128 
129 			if (i != this.keys.length-1)
130 				s[s.length] = " ; ";
131 		}
132 	} catch(e) {
133 		//do nothing here :-)
134 	} finally{
135 		s[s.length] = " } ";
136 	}
137 
138 	return s.join("");
139 }
140 
141 
142 
143 
144 /**
145 * Node Implementation
146 * @private
147 */
148 var Node = function(d)
149 {
150 	this.data = d;		// Data
151 	this.prev = null;	// Previous node
152 	this.next = null;	// Next node
153 }
154 
155 /**
156  * DoubleLinkedList Implementation
157  * @constructor
158  * @author <a href="mailto:rlaiola@cwi.nl">Rodrigo Laiola Guimaraes</a>
159  */
160 cwi.adt.DoubleLinkedList = function()
161 {
162 	JSINER.extend(this);
163 	
164 	/**
165 	* Variables
166 	* @private
167 	*/		
168 	this.firstNode = null;
169 	this.lastNode  = null;
170 	this.iterator  = null;
171 	this.size	   = 0;	
172 }
173 
174 /**
175 * Insert newNode right before node and point iterator to the newNode.
176 * @private
177 */
178 cwi.adt.DoubleLinkedList.prototype.insertBefore = function(node, newNode)
179 {
180 	newNode.prev = node.prev;
181 	newNode.next = node;
182 	
183 	if (node.prev == null)
184 		this.firstNode = newNode;
185 	else
186 		node.prev.next = newNode;
187 	node.prev = newNode;
188 	
189 	this.iterator = newNode;
190 	this.size++;
191 }
192 
193 /**
194 * Insert newNode right after node and point iterator to the newNode.
195 * @private
196 */
197 cwi.adt.DoubleLinkedList.prototype.insertAfter = function(node, newNode)
198 {
199 	newNode.prev = node;
200 	newNode.next = node.next;
201 	if (node.next == null)
202 	    this.lastNode = newNode;
203 	else
204 	    node.next.prev = newNode;
205 	node.next = newNode;
206 	
207 	this.iterator = newNode;
208 	this.size++;
209 }
210 
211 /**
212 * Insert an object in the beginning of the list and change the iterator to this new element.
213 * @param {Object} data Element to be inserted
214 */
215 cwi.adt.DoubleLinkedList.prototype.insertBegin = function(data)
216 {
217 	var newNode = new Node(data);
218 	
219 	if (this.firstNode == null) {
220          this.firstNode = newNode;
221          this.lastNode = newNode;
222          newNode.prev = null;
223          newNode.next = null;
224          
225          this.iterator = newNode;
226          this.size++;
227 	} else {
228          this.insertBefore(this.firstNode, newNode);
229 	}
230 }
231 
232 /**
233 * Insert an object in the end of the list and change the iterator to this new element.
234 * @param {Object} data Element to be inserted
235 */
236 cwi.adt.DoubleLinkedList.prototype.insertEnd = function(data)
237 {
238 	if (this.lastNode == null)
239          this.insertBegin(data);
240      else {
241      	var newNode = new Node(data);
242      	this.insertAfter(this.lastNode, newNode);
243      }
244 }
245 
246 /**
247 * Insert an object right after the element pointed by the iterator and change 
248 * the iterator to this new element. If the iterator is undefined, insert the
249 * object in the end of the list.
250 * @param {Object} data Element to be inserted
251 */
252 cwi.adt.DoubleLinkedList.prototype.insert = function(data)
253 {	
254 	if (this.iterator != null) {
255 		var newNode = new Node(data);
256 		this.insertAfter(this.iterator, newNode);
257 	}
258 	else if (this.firstNode == null)
259 		this.insertBegin(data);
260 	else 
261 		this.insertEnd(data);
262 }
263 
264 /**
265 * Remove a given node.
266 * @private
267 */
268 cwi.adt.DoubleLinkedList.prototype.removeNode = function(node)
269 {
270 	if (!node)
271 		return;
272 		
273 	if (node.prev == null) {
274        this.firstNode = node.next;
275        if (node.next != null)
276            node.next.prev = null;
277 	}
278 	else
279 	    node.prev.next = node.next;
280 	
281 	if (node.next == null) {
282 	    this.lastNode = node.prev;
283 	    if (node.prev != null)
284 	        node.prev.next = null;
285 	}
286 	else
287 	    node.next.prev = node.prev;
288 	    
289 	this.iterator = node.next;
290 	this.size--;
291 }
292 
293 /**
294 * Remove and return the element before pointed by the iterator. Then, the iterator 
295 * is moved to the next element of the list.
296 * @return {Object}
297 */
298 cwi.adt.DoubleLinkedList.prototype.remove = function()
299 {
300 	var result = null;
301 	if (this.iterator != null) {
302 		result = this.iterator.data;
303 		this.removeNode(this.iterator);
304 	}
305 	
306 	return result;
307 }
308 
309 /**
310 * Point the iterator to the first element.
311 */
312 cwi.adt.DoubleLinkedList.prototype.resetIterator = function()
313 {
314 	this.iterator = this.firstNode;
315 }
316 
317 /**
318 * Move the iterator to the previous element.
319 */
320 cwi.adt.DoubleLinkedList.prototype.moveToPrevious = function()
321 {
322 	if (this.iterator != null) {
323 		this.iterator = this.iterator.prev;
324 	}
325 }
326 
327 /**
328 * Move the iterator to the next element.
329 */
330 cwi.adt.DoubleLinkedList.prototype.moveToNext = function()
331 {
332 	if (this.iterator != null) {
333 		this.iterator = this.iterator.next;
334 	}
335 }
336 
337 /**
338 * Return true if the iterator points to an element, otherwise, false.
339 * @return {boolean}
340 */
341 cwi.adt.DoubleLinkedList.prototype.hasNext = function()
342 {
343 	return (this.iterator != null);
344 }
345 
346 /**
347 * Return the element pointed by the iterator.
348 * @return {Object}
349 */
350 cwi.adt.DoubleLinkedList.prototype.getCurrent = function()
351 {
352 	if (this.iterator) {
353 		return this.iterator.data;
354 	}
355 	return this.iterator;
356 }
357 
358 /**
359 * Return the size of the list.
360 * @return {integer}
361 */
362 cwi.adt.DoubleLinkedList.prototype.getSize = function()
363 {
364 	return this.size;
365 }
366 
367 /**
368 * Return the string representation of the list.
369 * @return {string}
370 */
371 cwi.adt.DoubleLinkedList.prototype.toString = function()
372 {
373 	var str = " { ";
374 	var firstTime = true;
375 	this.resetIterator();
376 	while(this.hasNext())
377 	{
378 		if (firstTime) {
379 			firstTime = false;
380 		} else {
381 			str += " ; "	
382 		}
383 		var data = this.getCurrent();
384 		str += data;
385 		this.moveToNext();
386 	}
387 
388 	return str + " } ";
389 }
390 
391 /**
392 * Add a given list after the current list.
393 * @param {cwi.adt.DoubleLinkedList} l the list that will be added after the current list
394 */
395 cwi.adt.DoubleLinkedList.prototype.merge = function(l) 
396 {
397 	if (this.lastNode == null) {
398         this.firstNode = l.firstNode;
399 		this.lastNode = l.lastNode;
400 		this.size = l.size;
401 	}
402     else {
403     	this.lastNode.next = l.firstNode;
404     	if (l.lastNode) {
405     		l.firstNode.prev = this.lastNode;
406     		this.lastNode = l.lastNode;
407     	}
408     	this.size += l.size;
409     }
410 }
411 
412 
413 
414 
415 
416 /* Solve library dependency */ 
417 Import ("cwi.adt.DoubleLinkedList");
418 
419 /**
420 * Elem Implementation
421 * @private
422 */
423 var Elem = function(w, d)
424 {
425 	this.weight = w;	// Elem weight
426 	this.data = d;		// Data
427 }
428 
429 /**
430  * PriorityQueue Implementation
431  * @constructor
432  * @author <a href="mailto:rlaiola@cwi.nl">Rodrigo Laiola Guimaraes</a>
433  */
434 cwi.adt.PriorityQueue = function()
435 {
436 	JSINER.extend(this);
437 	
438 	/** 
439 	* Variables
440 	* @private
441 	*/
442 	this.list = new DoubleLinkedList();	// List that implements PriorityQueue.	
443 }
444 
445 /**
446 * Insert a given element in the PriorityQueue based on its weight.
447 * @param {number} w Element weight
448 * @param {Object} d Element data
449 */
450 cwi.adt.PriorityQueue.prototype.push = function(w, d)
451 {
452 	// Try to save time
453 	if (this.list.getCurrent() == null || this.list.getCurrent().weight > w)
454 		this.list.resetIterator();
455 		
456 	while(this.list.hasNext())
457 	{
458 		var n = this.list.getCurrent();
459 		if (w < n.weight) {
460 			this.list.moveToPrevious();
461 			if (this.list.getCurrent() == null) // n is the first
462 				this.list.insertBegin(new Elem(w, d));
463 			else this.list.insert(new Elem(w, d));
464 			return;
465 		}
466 		this.list.moveToNext();
467 	}
468 	this.list.insertEnd(new Elem(w, d));
469 }
470 
471 /**
472 * Remove and return the first element of the PriorityQueue.
473 * @return {Object}
474 */
475 cwi.adt.PriorityQueue.prototype.pop = function()
476 {
477 	this.list.resetIterator();
478 	var res = this.list.remove();
479 	if (res)
480 		return res.data;
481 	else res;
482 }
483 
484 /**
485 * Return the weight of the first element and the PriorityQueue keeps unchanged.
486 * @return {number}
487 */
488 cwi.adt.PriorityQueue.prototype.lookFirst = function()
489 {
490 	this.list.resetIterator();
491 	var result = this.list.getCurrent();
492 	if (result)
493 		return result.weight;
494 	return result;
495 }
496 
497 /**
498 * Remove all elements of the PriorityQueue.
499 */
500 cwi.adt.PriorityQueue.prototype.clear = function()
501 {
502 	this.list = new DoubleLinkedList();
503 }
504  
505 /**
506 * Return the number of elements of the PriorityQueue.
507 * @return {integer}
508 */
509 cwi.adt.PriorityQueue.prototype.getSize = function()
510 {
511  	return this.list.getSize();
512 }
513  
514 /**
515 * Return true if the PriorityQueue is empty, otherwise, false.
516 * @return {boolean}
517 */
518 cwi.adt.PriorityQueue.prototype.isEmpty = function()
519 {
520  	return this.list.getSize() == 0;
521 }
522 
523 /**
524 * Return the string representation of the PriorityQueue.
525 * @return {string}
526 */
527 cwi.adt.PriorityQueue.prototype.toString = function()
528 {
529  	var str = " { ";
530 	var firstTime = true;
531 	this.list.resetIterator();
532 	while(this.list.hasNext())
533 	{
534 		if (firstTime) {
535 			firstTime = false;
536 		} else {
537 			str += " ; "	
538 		}
539 		var w = this.list.getCurrent().weight;
540 		var d = this.list.getCurrent().data;
541 		str += w + ":" + d;
542 		this.list.moveToNext();
543 	}
544 
545 	return str + " } ";
546 }
547 
548 /**
549 * Add a given queue after the current queue.
550 * @param {cwi.adt.PriorityQueue} q the priority queue that will be added after the current queue
551 */
552 cwi.adt.PriorityQueue.prototype.merge = function(q)
553 {
554 	if (this.list.lastNode != null && 
555 		q.list.firstNode != null &&
556 		this.list.lastNode.data.weight > q.list.firstNode.data.weight) {
557 		
558 		// tough work
559 		this.list.resetIterator();
560 		q.list.resetIterator();
561 		
562 		while(this.list.hasNext() && q.list.hasNext())
563 		{
564 			var c1 = this.list.getCurrent();
565 			var c2 = q.list.getCurrent();
566 			
567 			if (c1.weight <= c2.weight) {
568 				this.list.moveToNext();
569 			}
570 			else {
571 				if (this.list.firstNode == this.list.iterator) {
572 					this.list.insertBegin(q.list.remove());
573 				}
574 				else {
575 					this.list.moveToPrevious();
576 					this.list.insert(q.list.remove());
577 				}
578 			}
579 		}
580 		
581 	}
582  	
583  	return this.list.merge(q.list);
584 }
585