std/collection.js

   1 /*
   2     Pitchfork Music Player Daemon Client
   3     Copyright (C) 2007  Roger Bystrøm
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; version 2 of the License.
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License along
  15     with this program; if not, write to the Free Software Foundation, Inc.,
  16     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  17 */
  18
  19 /* HashMap implementation, guess it's more of a key-lookup-linked-list though */
  20
  21 function HashNode(key, val) {
  22         this.key = key;
  23         this.value = val;
  24         this.next = null;
  25 }
  26 function HashMap() {
  27         this.header = null;
  28 }
  29
  30 /*
  31  * Usage: var it = hashmap.iterator();
  32  * var tmp;
  33  * while(tmp = it.next());
  34  */
  35 function HashMapIterator(first) {
  36         this.c = first;
  37 }
  38
  39 HashMapIterator.prototype.next = function() {
  40         var ret = this.c;
  41         if(this.c != null) {
  42                 ret = ret.value;
  43                 this.c = this.c.next;
  44         }
  45         return ret;
  46 }
  47
  48 /* get an entry from the list */
  49 HashMap.prototype.get = function(key) {
  50         var n = this.header;
  51         while(n!=null) {
  52                 if(n.key==key)
  53                         return n.value;
  54                 n = n.next;
  55         }
  56         return null;
  57 }
  58
  59 /* Removes an entry from the list and returns it */
  60 HashMap.prototype.remove = function(key) {
  61         if(this.header==null)
  62                 debug("wops, header null");
  63         if(key==this.header.key) {
  64                 var tmp = this.header;
  65                 this.header = this.header.next;
  66                 return tmp.value;
  67         }
  68         else {
  69                 var n = this.header;
  70                 while(n.next != null) {
  71                         if(n.next.key == key) {
  72                                 var ret = n.next;
  73                                 n.next = n.next.next;
  74                                 return ret.value;
  75                         }
  76                         n = n.next;
  77                 }
  78         }
  79         return null;
  80 }
  81
  82 /* put a new entry in the list */
  83 HashMap.prototype.put = function(key, value) {
  84         var node = new HashNode(key,value);
  85         var next = this.header;
  86         if(next==null) {
  87                 this.header = node;
  88         }
  89         else {
  90                 while(next.next!=null)
  91                         next = next.next;
  92                 next.next = node;
  93         }
  94 }
  95
  96 HashMap.prototype.insert = function(key, value) {
  97         var node = new HashNode(key,value);
  98         node.next = this.header;
  99         this.header = node;
 100 }
 101
 102 HashMap.prototype.iterator = function() {
 103         return new HashMapIterator(this.header);
 104 }
 105
 106
 107 /* A proper hashtable implementation
 108 */
 109 function Hashtable() {
 110         this.data = new Object();
 111         this._size = 0;
 112 }
 113
 114 /* clears the hashtable */
 115 Hashtable.prototype.clear = function() {
 116         for(var key in this.data)
 117                 delete this.data[key];
 118         this._size = 0;
 119 }
 120
 121 /* tests whether the specified value is in this hashtable
 122   returns true if it does, falseotherwise */
 123 Hashtable.prototype.contains = function(obj) {
 124         if(obj==null) return false;
 125
 126         for(var opt in this.data) {
 127                 if(obj == this.data[opt])
 128                         return true;
 129         }
 130         return false;
 131 }
 132
 133 /* Tests whether the specified key is in this hashtable
 134    returns true if it does, false otherwise*/
 135 Hashtable.prototype.containsKey = function(key) {
 136         return typeof this.data[key] != "undefined" && this.data[key] != null;
 137 }
 138
 139 Hashtable.prototype.put = function (key, value) {
 140         this.data[key] = value;
 141         this._size++;
 142 }
 143
 144 /** puts all the in to this hashtable */
 145 Hashtable.prototype.putAll = function(map) {
 146         for(var key in map) {
 147                 this.data[key] = map[key];
 148                 this._size++;
 149         }
 150 }
 151
 152 Hashtable.prototype.get = function (key) {
 153         return this.data[key];
 154 }
 155
 156 Hashtable.prototype.isEmpty = function() {
 157         return this._size == 0;
 158 }
 159 /**
 160  remove the object and key from this hashtable,
 161  returns the object if it's there, null otherwise
 162  */
 163 Hashtable.prototype.remove = function(key) {
 164         if(!this.containsKey(key))
 165                 return null;
 166         var ret = this.data[key];
 167         delete this.data[key];
 168         this._size--;
 169         return ret;
 170 }
 171 /** Returns the number of keys in this hashtable */
 172 Hashtable.prototype.size = function() {
 173         return this._size;
 174 }
 175
 176 /** Returns an array with all the values in this hashtable */
 177 Hashtable.prototype.elements = function() {
 178         var ret = new Array();
 179         for (var key  in this.data) {
 180                 ret.push(this.data[key]);
 181         }
 182         return ret;
 183 }
 184
 185 /** Returns an array with all the keys in this hashtable */
 186 Hashtable.prototype.keys = function() {
 187         var ret = new Array();
 188         for (var key  in this.data) {
 189                 ret.push(key);
 190         }
 191         return ret;
 192 }
 193
 194 /** Returns a string with the keys and values */
 195 Hashtable.prototype.toString = function() {
 196         var ret = "";
 197         for(var key in this.data) {
 198                 ret +="{" + key + "," + value + "}";
 199         }
 200         return ret;
 201 }