JAVASCRIPT   6

jshashtable-2.1_src.js

Guest on 9th June 2021 04:09:23 AM

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

Raw Paste


Login or Register to edit or fork this paste. It's free.