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
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
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
14 * http://www.apache.org/licenses/LICENSE-2.0
\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
22 var Hashtable = (function(UNDEFINED) {
\r
23 var FUNCTION = "function", STRING = "string", UNDEF = "undefined";
\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
33 function toStr(obj) {
\r
34 return (typeof obj == STRING) ? obj : "" + obj;
\r
37 function hashObject(obj) {
\r
39 if (typeof obj == STRING) {
\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
50 function merge(o1, o2) {
\r
52 if (o2.hasOwnProperty(i)) {
\r
58 function equals_fixedValueHasEquals(fixedValue, variableValue) {
\r
59 return fixedValue.equals(variableValue);
\r
62 function equals_fixedValueNoEquals(fixedValue, variableValue) {
\r
63 return (typeof variableValue.equals == FUNCTION) ?
\r
64 variableValue.equals(fixedValue) : (fixedValue === variableValue);
\r
67 function createKeyValCheck(kvStr) {
\r
68 return function(kv) {
\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
77 var checkKey = createKeyValCheck("key"), checkValue = createKeyValCheck("value");
\r
79 /*----------------------------------------------------------------------------------------------------------------*/
\r
81 function Bucket(hash, firstKey, firstValue, equalityFunction) {
\r
84 this.addEntry(firstKey, firstValue);
\r
86 if (equalityFunction !== null) {
\r
87 this.getEqualityFunction = function() {
\r
88 return equalityFunction;
\r
93 var EXISTENCE = 0, ENTRY = 1, ENTRY_INDEX_AND_VALUE = 2;
\r
95 function createBucketSearcher(mode) {
\r
96 return function(key) {
\r
97 var i = this.entries.length, entry, equals = this.getEqualityFunction(key);
\r
99 entry = this.entries[i];
\r
100 if ( equals(key, entry[0]) ) {
\r
106 case ENTRY_INDEX_AND_VALUE:
\r
107 return [ i, entry[1] ];
\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
124 Bucket.prototype = {
\r
125 getEqualityFunction: function(searchValue) {
\r
126 return (typeof searchValue.equals == FUNCTION) ? equals_fixedValueHasEquals : equals_fixedValueNoEquals;
\r
129 getEntryForKey: createBucketSearcher(ENTRY),
\r
131 getEntryAndIndexForKey: createBucketSearcher(ENTRY_INDEX_AND_VALUE),
\r
133 removeEntryForKey: function(key) {
\r
134 var result = this.getEntryAndIndexForKey(key);
\r
136 this.entries.splice(result[0], 1);
\r
142 addEntry: function(key, value) {
\r
143 this.entries.push( [key, value] );
\r
146 keys: createBucketLister(0),
\r
148 values: createBucketLister(1),
\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
158 containsKey: createBucketSearcher(EXISTENCE),
\r
160 containsValue: function(value) {
\r
161 var entries = this.entries, i = entries.length;
\r
163 if ( value === entries[i][1] ) {
\r
171 /*----------------------------------------------------------------------------------------------------------------*/
\r
173 // Supporting functions for searching hashtable buckets
\r
175 function searchBuckets(buckets, hash) {
\r
176 var i = buckets.length, bucket;
\r
178 bucket = buckets[i];
\r
179 if (hash === bucket[0]) {
\r
186 function getBucketForHash(bucketsByHash, hash) {
\r
187 var bucket = bucketsByHash[hash];
\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
193 /*----------------------------------------------------------------------------------------------------------------*/
\r
195 function Hashtable() {
\r
197 var bucketsByHash = {};
\r
199 replaceDuplicateKey: true,
\r
200 hashCode: hashObject,
\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
212 var hashCode = properties.hashCode, equals = properties.equals;
\r
214 this.properties = properties;
\r
216 this.put = function(key, value) {
\r
219 var hash = hashCode(key), bucket, bucketEntry, oldValue = null;
\r
221 // Check if a bucket exists for the bucket key
\r
222 bucket = getBucketForHash(bucketsByHash, hash);
\r
224 // Check this bucket to see if it already contains this key
\r
225 bucketEntry = bucket.getEntryForKey(key);
\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
232 oldValue = bucketEntry[1];
\r
233 bucketEntry[1] = value;
\r
235 // The bucket does not contain an entry for this key, so add one
\r
236 bucket.addEntry(key, value);
\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
247 this.get = function(key) {
\r
250 var hash = hashCode(key);
\r
252 // Check if a bucket exists for the bucket key
\r
253 var bucket = getBucketForHash(bucketsByHash, hash);
\r
255 // Check this bucket to see if it contains this key
\r
256 var bucketEntry = bucket.getEntryForKey(key);
\r
258 // This bucket entry is the current mapping of key to value, so return the value.
\r
259 return bucketEntry[1];
\r
265 this.containsKey = function(key) {
\r
267 var bucketKey = hashCode(key);
\r
269 // Check if a bucket exists for the bucket key
\r
270 var bucket = getBucketForHash(bucketsByHash, bucketKey);
\r
272 return bucket ? bucket.containsKey(key) : false;
\r
275 this.containsValue = function(value) {
\r
277 var i = buckets.length;
\r
279 if (buckets[i].containsValue(value)) {
\r
286 this.clear = function() {
\r
287 buckets.length = 0;
\r
288 bucketsByHash = {};
\r
291 this.isEmpty = function() {
\r
292 return !buckets.length;
\r
295 var createBucketAggregator = function(bucketFuncName) {
\r
296 return function() {
\r
297 var aggregated = [], i = buckets.length;
\r
299 buckets[i][bucketFuncName](aggregated);
\r
305 this.keys = createBucketAggregator("keys");
\r
306 this.values = createBucketAggregator("values");
\r
307 this.entries = createBucketAggregator("getEntries");
\r
309 this.remove = function(key) {
\r
312 var hash = hashCode(key), bucketIndex, oldValue = null;
\r
314 // Check if a bucket exists for the bucket key
\r
315 var bucket = getBucketForHash(bucketsByHash, hash);
\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
333 this.size = function() {
\r
334 var total = 0, i = buckets.length;
\r
336 total += buckets[i].entries.length;
\r
342 Hashtable.prototype = {
\r
343 each: function(callback) {
\r
344 var entries = this.entries(), i = entries.length, entry;
\r
346 entry = entries[i];
\r
347 callback(entry[0], entry[1]);
\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
357 val = hashtable.get(key);
\r
358 if (val === null || val !== this.get(key)) {
\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
372 entry = entries[i];
\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
380 this.put(key, value);
\r
384 clone: function() {
\r
385 var clone = new Hashtable(this.properties);
\r
386 clone.putAll(this);
\r
391 Hashtable.prototype.toQueryString = function() {
\r
392 var entries = this.entries(), i = entries.length, entry;
\r
395 entry = entries[i];
\r
396 parts[i] = encodeURIComponent( toStr(entry[0]) ) + "=" + encodeURIComponent( toStr(entry[1]) );
\r
398 return parts.join("&");
\r