/**
 * This file is part of the smilText parser implemented in JavaScript,
 *
 * Copyright (C) 2003-2009 Stichting CWI, 
 * Science Park 123, 1098 XG Amsterdam, The Netherlands.
 *
 * smilText parser in JavaScript is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * smilText parser in JavaScript is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with smilText parser in JavaScript; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

Namespace("cwi.adt");cwi.adt.Hashtable=function(){JSINER.extend(this);this.hash=new Array();this.keys=new Array()};cwi.adt.Hashtable.prototype.put=function(a,b){if(b==null){return}if(this.hash[a]==null){this.keys[this.keys.length]=a}this.hash[a]=b};cwi.adt.Hashtable.prototype.get=function(a){return this.hash[a]};cwi.adt.Hashtable.prototype.remove=function(c){var a=null;for(var b=0;b<this.keys.length;b++){if(c==this.keys[b]){a=this.hash[this.keys[b]];this.hash[this.keys[b]]=null;this.keys.splice(b,1);break}}return a};cwi.adt.Hashtable.prototype.getSize=function(){return this.keys.length};cwi.adt.Hashtable.prototype.toString=function(){try{var c=new Array(this.keys.length);c[c.length]=" { ";for(var b=0;b<this.keys.length;b++){c[c.length]=this.keys[b];c[c.length]="=";var a=this.hash[this.keys[b]];if(a){c[c.length]=a.toString()}else{c[c.length]="null"}if(b!=this.keys.length-1){c[c.length]=" ; "}}}catch(d){}finally{c[c.length]=" } "}return c.join("")};var Node=function(a){this.data=a;this.prev=null;this.next=null};cwi.adt.DoubleLinkedList=function(){JSINER.extend(this);this.firstNode=null;this.lastNode=null;this.iterator=null;this.size=0};cwi.adt.DoubleLinkedList.prototype.insertBefore=function(b,a){a.prev=b.prev;a.next=b;if(b.prev==null){this.firstNode=a}else{b.prev.next=a}b.prev=a;this.iterator=a;this.size++};cwi.adt.DoubleLinkedList.prototype.insertAfter=function(b,a){a.prev=b;a.next=b.next;if(b.next==null){this.lastNode=a}else{b.next.prev=a}b.next=a;this.iterator=a;this.size++};cwi.adt.DoubleLinkedList.prototype.insertBegin=function(b){var a=new Node(b);if(this.firstNode==null){this.firstNode=a;this.lastNode=a;a.prev=null;a.next=null;this.iterator=a;this.size++}else{this.insertBefore(this.firstNode,a)}};cwi.adt.DoubleLinkedList.prototype.insertEnd=function(b){if(this.lastNode==null){this.insertBegin(b)}else{var a=new Node(b);this.insertAfter(this.lastNode,a)}};cwi.adt.DoubleLinkedList.prototype.insert=function(b){if(this.iterator!=null){var a=new Node(b);this.insertAfter(this.iterator,a)}else{if(this.firstNode==null){this.insertBegin(b)}else{this.insertEnd(b)}}};cwi.adt.DoubleLinkedList.prototype.removeNode=function(a){if(!a){return}if(a.prev==null){this.firstNode=a.next;if(a.next!=null){a.next.prev=null}}else{a.prev.next=a.next}if(a.next==null){this.lastNode=a.prev;if(a.prev!=null){a.prev.next=null}}else{a.next.prev=a.prev}this.iterator=a.next;this.size--};cwi.adt.DoubleLinkedList.prototype.remove=function(){var a=null;if(this.iterator!=null){a=this.iterator.data;this.removeNode(this.iterator)}return a};cwi.adt.DoubleLinkedList.prototype.resetIterator=function(){this.iterator=this.firstNode};cwi.adt.DoubleLinkedList.prototype.moveToPrevious=function(){if(this.iterator!=null){this.iterator=this.iterator.prev}};cwi.adt.DoubleLinkedList.prototype.moveToNext=function(){if(this.iterator!=null){this.iterator=this.iterator.next}};cwi.adt.DoubleLinkedList.prototype.hasNext=function(){return(this.iterator!=null)};cwi.adt.DoubleLinkedList.prototype.getCurrent=function(){if(this.iterator){return this.iterator.data}return this.iterator};cwi.adt.DoubleLinkedList.prototype.getSize=function(){return this.size};cwi.adt.DoubleLinkedList.prototype.toString=function(){var b=" { ";var c=true;this.resetIterator();while(this.hasNext()){if(c){c=false}else{b+=" ; "}var a=this.getCurrent();b+=a;this.moveToNext()}return b+" } "};cwi.adt.DoubleLinkedList.prototype.merge=function(a){if(this.lastNode==null){this.firstNode=a.firstNode;this.lastNode=a.lastNode;this.size=a.size}else{this.lastNode.next=a.firstNode;if(a.lastNode){a.firstNode.prev=this.lastNode;this.lastNode=a.lastNode}this.size+=a.size}};Import("cwi.adt.DoubleLinkedList");var Elem=function(a,b){this.weight=a;this.data=b};cwi.adt.PriorityQueue=function(){JSINER.extend(this);this.list=new DoubleLinkedList()};cwi.adt.PriorityQueue.prototype.push=function(a,b){if(this.list.getCurrent()==null||this.list.getCurrent().weight>a){this.list.resetIterator()}while(this.list.hasNext()){var c=this.list.getCurrent();if(a<c.weight){this.list.moveToPrevious();if(this.list.getCurrent()==null){this.list.insertBegin(new Elem(a,b))}else{this.list.insert(new Elem(a,b))}return}this.list.moveToNext()}this.list.insertEnd(new Elem(a,b))};cwi.adt.PriorityQueue.prototype.pop=function(){this.list.resetIterator();var a=this.list.remove();if(a){return a.data}else{a}};cwi.adt.PriorityQueue.prototype.lookFirst=function(){this.list.resetIterator();var a=this.list.getCurrent();if(a){return a.weight}return a};cwi.adt.PriorityQueue.prototype.clear=function(){this.list=new DoubleLinkedList()};cwi.adt.PriorityQueue.prototype.getSize=function(){return this.list.getSize()};cwi.adt.PriorityQueue.prototype.isEmpty=function(){return this.list.getSize()==0};cwi.adt.PriorityQueue.prototype.toString=function(){var c=" { ";var e=true;this.list.resetIterator();while(this.list.hasNext()){if(e){e=false}else{c+=" ; "}var a=this.list.getCurrent().weight;var b=this.list.getCurrent().data;c+=a+":"+b;this.list.moveToNext()}return c+" } "};cwi.adt.PriorityQueue.prototype.merge=function(c){if(this.list.lastNode!=null&&c.list.firstNode!=null&&this.list.lastNode.data.weight>c.list.firstNode.data.weight){this.list.resetIterator();c.list.resetIterator();while(this.list.hasNext()&&c.list.hasNext()){var b=this.list.getCurrent();var a=c.list.getCurrent();if(b.weight<=a.weight){this.list.moveToNext()}else{if(this.list.firstNode==this.list.iterator){this.list.insertBegin(c.list.remove())}else{this.list.moveToPrevious();this.list.insert(c.list.remove())}}}}return this.list.merge(c.list)};