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