manifoldapi/static/js/hashtable.js

   1 /**\r
   2  * @license jahashtable, a JavaScript implementation of a hash table. It creates a single constructor function called\r
   3  * Hashtable in the global scope.\r
   4  *\r
   5  * http://www.timdown.co.uk/jshashtable/\r
   6  * Copyright %%build:year%% Tim Down.\r
   7  * Version: %%build:version%%\r
   8  * Build date: %%build:date%%\r
   9  *\r
  10  * Licensed under the Apache License, Version 2.0 (the "License");\r
  11  * you may not use this file except in compliance with the License.\r
  12  * You may obtain a copy of the License at\r
  13  *\r
  14  *      http://www.apache.org/licenses/LICENSE-2.0\r
  15  *\r
  16  * Unless required by applicable law or agreed to in writing, software\r
  17  * distributed under the License is distributed on an "AS IS" BASIS,\r
  18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  19  * See the License for the specific language governing permissions and\r
  20  * limitations under the License.\r
  21  */\r
  22 var Hashtable = (function(UNDEFINED) {\r
  23     var FUNCTION = "function", STRING = "string", UNDEF = "undefined";\r
  24 \r
  25     // Require Array.prototype.splice, Object.prototype.hasOwnProperty and encodeURIComponent. In environments not\r
  26     // having these (e.g. IE <= 5), we bail out now and leave Hashtable null.\r
  27     if (typeof encodeURIComponent == UNDEF ||\r
  28             Array.prototype.splice === UNDEFINED ||\r
  29             Object.prototype.hasOwnProperty === UNDEFINED) {\r
  30         return null;\r
  31     }\r
  32 \r
  33     function toStr(obj) {\r
  34         return (typeof obj == STRING) ? obj : "" + obj;\r
  35     }\r
  36 \r
  37     function hashObject(obj) {\r
  38         var hashCode;\r
  39         if (typeof obj == STRING) {\r
  40             return obj;\r
  41         } else if (typeof obj.hashCode == FUNCTION) {\r
  42             // Check the hashCode method really has returned a string\r
  43             hashCode = obj.hashCode();\r
  44             return (typeof hashCode == STRING) ? hashCode : hashObject(hashCode);\r
  45         } else {\r
  46             return toStr(obj);\r
  47         }\r
  48     }\r
  49     \r
  50     function merge(o1, o2) {\r
  51         for (var i in o2) {\r
  52             if (o2.hasOwnProperty(i)) {\r
  53                 o1[i] = o2[i];\r
  54             }\r
  55         }\r
  56     }\r
  57 \r
  58     function equals_fixedValueHasEquals(fixedValue, variableValue) {\r
  59         return fixedValue.equals(variableValue);\r
  60     }\r
  61 \r
  62     function equals_fixedValueNoEquals(fixedValue, variableValue) {\r
  63         return (typeof variableValue.equals == FUNCTION) ?\r
  64             variableValue.equals(fixedValue) : (fixedValue === variableValue);\r
  65     }\r
  66 \r
  67     function createKeyValCheck(kvStr) {\r
  68         return function(kv) {\r
  69             if (kv === null) {\r
  70                 throw new Error("null is not a valid " + kvStr);\r
  71             } else if (kv === UNDEFINED) {\r
  72                 throw new Error(kvStr + " must not be undefined");\r
  73             }\r
  74         };\r
  75     }\r
  76 \r
  77     var checkKey = createKeyValCheck("key"), checkValue = createKeyValCheck("value");\r
  78 \r
  79     /*----------------------------------------------------------------------------------------------------------------*/\r
  80 \r
  81     function Bucket(hash, firstKey, firstValue, equalityFunction) {\r
  82         this[0] = hash;\r
  83         this.entries = [];\r
  84         this.addEntry(firstKey, firstValue);\r
  85 \r
  86         if (equalityFunction !== null) {\r
  87             this.getEqualityFunction = function() {\r
  88                 return equalityFunction;\r
  89             };\r
  90         }\r
  91     }\r
  92 \r
  93     var EXISTENCE = 0, ENTRY = 1, ENTRY_INDEX_AND_VALUE = 2;\r
  94 \r
  95     function createBucketSearcher(mode) {\r
  96         return function(key) {\r
  97             var i = this.entries.length, entry, equals = this.getEqualityFunction(key);\r
  98             while (i--) {\r
  99                 entry = this.entries[i];\r
 100                 if ( equals(key, entry[0]) ) {\r
 101                     switch (mode) {\r
 102                         case EXISTENCE:\r
 103                             return true;\r
 104                         case ENTRY:\r
 105                             return entry;\r
 106                         case ENTRY_INDEX_AND_VALUE:\r
 107                             return [ i, entry[1] ];\r
 108                     }\r
 109                 }\r
 110             }\r
 111             return false;\r
 112         };\r
 113     }\r
 114 \r
 115     function createBucketLister(entryProperty) {\r
 116         return function(aggregatedArr) {\r
 117             var startIndex = aggregatedArr.length;\r
 118             for (var i = 0, entries = this.entries, len = entries.length; i < len; ++i) {\r
 119                 aggregatedArr[startIndex + i] = entries[i][entryProperty];\r
 120             }\r
 121         };\r
 122     }\r
 123 \r
 124     Bucket.prototype = {\r
 125         getEqualityFunction: function(searchValue) {\r
 126             return (typeof searchValue.equals == FUNCTION) ? equals_fixedValueHasEquals : equals_fixedValueNoEquals;\r
 127         },\r
 128 \r
 129         getEntryForKey: createBucketSearcher(ENTRY),\r
 130 \r
 131         getEntryAndIndexForKey: createBucketSearcher(ENTRY_INDEX_AND_VALUE),\r
 132 \r
 133         removeEntryForKey: function(key) {\r
 134             var result = this.getEntryAndIndexForKey(key);\r
 135             if (result) {\r
 136                 this.entries.splice(result[0], 1);\r
 137                 return result[1];\r
 138             }\r
 139             return null;\r
 140         },\r
 141 \r
 142         addEntry: function(key, value) {\r
 143             this.entries.push( [key, value] );\r
 144         },\r
 145 \r
 146         keys: createBucketLister(0),\r
 147 \r
 148         values: createBucketLister(1),\r
 149 \r
 150         getEntries: function(destEntries) {\r
 151             var startIndex = destEntries.length;\r
 152             for (var i = 0, entries = this.entries, len = entries.length; i < len; ++i) {\r
 153                 // Clone the entry stored in the bucket before adding to array\r
 154                 destEntries[startIndex + i] = entries[i].slice(0);\r
 155             }\r
 156         },\r
 157 \r
 158         containsKey: createBucketSearcher(EXISTENCE),\r
 159 \r
 160         containsValue: function(value) {\r
 161             var entries = this.entries, i = entries.length;\r
 162             while (i--) {\r
 163                 if ( value === entries[i][1] ) {\r
 164                     return true;\r
 165                 }\r
 166             }\r
 167             return false;\r
 168         }\r
 169     };\r
 170 \r
 171     /*----------------------------------------------------------------------------------------------------------------*/\r
 172 \r
 173     // Supporting functions for searching hashtable buckets\r
 174 \r
 175     function searchBuckets(buckets, hash) {\r
 176         var i = buckets.length, bucket;\r
 177         while (i--) {\r
 178             bucket = buckets[i];\r
 179             if (hash === bucket[0]) {\r
 180                 return i;\r
 181             }\r
 182         }\r
 183         return null;\r
 184     }\r
 185 \r
 186     function getBucketForHash(bucketsByHash, hash) {\r
 187         var bucket = bucketsByHash[hash];\r
 188 \r
 189         // Check that this is a genuine bucket and not something inherited from the bucketsByHash's prototype\r
 190         return ( bucket && (bucket instanceof Bucket) ) ? bucket : null;\r
 191     }\r
 192 \r
 193     /*----------------------------------------------------------------------------------------------------------------*/\r
 194 \r
 195     function Hashtable() {\r
 196         var buckets = [];\r
 197         var bucketsByHash = {};\r
 198         var properties = {\r
 199             replaceDuplicateKey: true,\r
 200             hashCode: hashObject,\r
 201             equals: null\r
 202         };\r
 203 \r
 204         var arg0 = arguments[0], arg1 = arguments[1];\r
 205         if (arg1 !== UNDEFINED) {\r
 206             properties.hashCode = arg0;\r
 207             properties.equals = arg1;\r
 208         } else if (arg0 !== UNDEFINED) {\r
 209             merge(properties, arg0);\r
 210         }\r
 211 \r
 212         var hashCode = properties.hashCode, equals = properties.equals;\r
 213 \r
 214         this.properties = properties;\r
 215 \r
 216         this.put = function(key, value) {\r
 217             checkKey(key);\r
 218             checkValue(value);\r
 219             var hash = hashCode(key), bucket, bucketEntry, oldValue = null;\r
 220 \r
 221             // Check if a bucket exists for the bucket key\r
 222             bucket = getBucketForHash(bucketsByHash, hash);\r
 223             if (bucket) {\r
 224                 // Check this bucket to see if it already contains this key\r
 225                 bucketEntry = bucket.getEntryForKey(key);\r
 226                 if (bucketEntry) {\r
 227                     // This bucket entry is the current mapping of key to value, so replace the old value.\r
 228                     // Also, we optionally replace the key so that the latest key is stored.\r
 229                     if (properties.replaceDuplicateKey) {\r
 230                         bucketEntry[0] = key;\r
 231                     }\r
 232                     oldValue = bucketEntry[1];\r
 233                     bucketEntry[1] = value;\r
 234                 } else {\r
 235                     // The bucket does not contain an entry for this key, so add one\r
 236                     bucket.addEntry(key, value);\r
 237                 }\r
 238             } else {\r
 239                 // No bucket exists for the key, so create one and put our key/value mapping in\r
 240                 bucket = new Bucket(hash, key, value, equals);\r
 241                 buckets.push(bucket);\r
 242                 bucketsByHash[hash] = bucket;\r
 243             }\r
 244             return oldValue;\r
 245         };\r
 246 \r
 247         this.get = function(key) {\r
 248             checkKey(key);\r
 249 \r
 250             var hash = hashCode(key);\r
 251 \r
 252             // Check if a bucket exists for the bucket key\r
 253             var bucket = getBucketForHash(bucketsByHash, hash);\r
 254             if (bucket) {\r
 255                 // Check this bucket to see if it contains this key\r
 256                 var bucketEntry = bucket.getEntryForKey(key);\r
 257                 if (bucketEntry) {\r
 258                     // This bucket entry is the current mapping of key to value, so return the value.\r
 259                     return bucketEntry[1];\r
 260                 }\r
 261             }\r
 262             return null;\r
 263         };\r
 264 \r
 265         this.containsKey = function(key) {\r
 266             checkKey(key);\r
 267             var bucketKey = hashCode(key);\r
 268 \r
 269             // Check if a bucket exists for the bucket key\r
 270             var bucket = getBucketForHash(bucketsByHash, bucketKey);\r
 271 \r
 272             return bucket ? bucket.containsKey(key) : false;\r
 273         };\r
 274 \r
 275         this.containsValue = function(value) {\r
 276             checkValue(value);\r
 277             var i = buckets.length;\r
 278             while (i--) {\r
 279                 if (buckets[i].containsValue(value)) {\r
 280                     return true;\r
 281                 }\r
 282             }\r
 283             return false;\r
 284         };\r
 285 \r
 286         this.clear = function() {\r
 287             buckets.length = 0;\r
 288             bucketsByHash = {};\r
 289         };\r
 290 \r
 291         this.isEmpty = function() {\r
 292             return !buckets.length;\r
 293         };\r
 294 \r
 295         var createBucketAggregator = function(bucketFuncName) {\r
 296             return function() {\r
 297                 var aggregated = [], i = buckets.length;\r
 298                 while (i--) {\r
 299                     buckets[i][bucketFuncName](aggregated);\r
 300                 }\r
 301                 return aggregated;\r
 302             };\r
 303         };\r
 304 \r
 305         this.keys = createBucketAggregator("keys");\r
 306         this.values = createBucketAggregator("values");\r
 307         this.entries = createBucketAggregator("getEntries");\r
 308 \r
 309         this.remove = function(key) {\r
 310             checkKey(key);\r
 311 \r
 312             var hash = hashCode(key), bucketIndex, oldValue = null;\r
 313 \r
 314             // Check if a bucket exists for the bucket key\r
 315             var bucket = getBucketForHash(bucketsByHash, hash);\r
 316 \r
 317             if (bucket) {\r
 318                 // Remove entry from this bucket for this key\r
 319                 oldValue = bucket.removeEntryForKey(key);\r
 320                 if (oldValue !== null) {\r
 321                     // Entry was removed, so check if bucket is empty\r
 322                     if (bucket.entries.length == 0) {\r
 323                         // Bucket is empty, so remove it from the bucket collections\r
 324                         bucketIndex = searchBuckets(buckets, hash);\r
 325                         buckets.splice(bucketIndex, 1);\r
 326                         delete bucketsByHash[hash];\r
 327                     }\r
 328                 }\r
 329             }\r
 330             return oldValue;\r
 331         };\r
 332 \r
 333         this.size = function() {\r
 334             var total = 0, i = buckets.length;\r
 335             while (i--) {\r
 336                 total += buckets[i].entries.length;\r
 337             }\r
 338             return total;\r
 339         };\r
 340     }\r
 341 \r
 342     Hashtable.prototype = {\r
 343         each: function(callback) {\r
 344             var entries = this.entries(), i = entries.length, entry;\r
 345             while (i--) {\r
 346                 entry = entries[i];\r
 347                 callback(entry[0], entry[1]);\r
 348             }\r
 349         },\r
 350 \r
 351         equals: function(hashtable) {\r
 352             var keys, key, val, count = this.size();\r
 353             if (count == hashtable.size()) {\r
 354                 keys = this.keys();\r
 355                 while (count--) {\r
 356                     key = keys[count];\r
 357                     val = hashtable.get(key);\r
 358                     if (val === null || val !== this.get(key)) {\r
 359                         return false;\r
 360                     }\r
 361                 }\r
 362                 return true;\r
 363             }\r
 364             return false;\r
 365         },\r
 366 \r
 367         putAll: function(hashtable, conflictCallback) {\r
 368             var entries = hashtable.entries();\r
 369             var entry, key, value, thisValue, i = entries.length;\r
 370             var hasConflictCallback = (typeof conflictCallback == FUNCTION);\r
 371             while (i--) {\r
 372                 entry = entries[i];\r
 373                 key = entry[0];\r
 374                 value = entry[1];\r
 375 \r
 376                 // Check for a conflict. The default behaviour is to overwrite the value for an existing key\r
 377                 if ( hasConflictCallback && (thisValue = this.get(key)) ) {\r
 378                     value = conflictCallback(key, thisValue, value);\r
 379                 }\r
 380                 this.put(key, value);\r
 381             }\r
 382         },\r
 383 \r
 384         clone: function() {\r
 385             var clone = new Hashtable(this.properties);\r
 386             clone.putAll(this);\r
 387             return clone;\r
 388         }\r
 389     };\r
 390 \r
 391     Hashtable.prototype.toQueryString = function() {\r
 392         var entries = this.entries(), i = entries.length, entry;\r
 393         var parts = [];\r
 394         while (i--) {\r
 395             entry = entries[i];\r
 396             parts[i] = encodeURIComponent( toStr(entry[0]) ) + "=" + encodeURIComponent( toStr(entry[1]) );\r
 397         }\r
 398         return parts.join("&");\r
 399     };\r
 400 \r
 401     return Hashtable;\r
 402 })();\r