https://www.graziosiaround.it/themes/graziosi/js/tema/jshashtable-2.1_src.js?v=1.0

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 <[email protected]>
24 * Version: 2.1
25 * Build date: 21 March 2010
26 * Website: http://www.timdown.co.uk/jshashtable
27 */
28
29var 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})();