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
 * Author: Tim Down <[email protected]>
17
 * Version: 2.1
18
 * Build date: 21 March 2010
19
 * Website: http://www.timdown.co.uk/jshashtable
20
 *
21
 * (Slight mod to add to gamecore namespace -- [email protected])
22
 */
23

24
/**
25
 * jshashtable
26
 *
27
 * jshashtable is a JavaScript implementation of a hash table. It creates a single constructor function called Hashtable
28
 * in the global scope.
29
 * Example:
30
 * <code>
31
 *     var map = new gamecore.Hashtable();
32
 *     map.put('test1', obj);
33
 *     var obj = map.get('test1');
34
 * </code>
35
 */
36

37
gamecore.Hashtable = (function ()
38
{
39
    var FUNCTION = "function";
40

41
    var arrayRemoveAt = (typeof Array.prototype.splice == FUNCTION) ?
42
        function (arr, idx)
43
        {
44
            arr.splice(idx, 1);
45
        } :
46

47
        function (arr, idx)
48
        {
49
            var itemsAfterDeleted, i, len;
50
            if (idx === arr.length - 1)
51
            {
52
                arr.length = idx;
53
            } else
54
            {
55
                itemsAfterDeleted = arr.slice(idx + 1);
56
                arr.length = idx;
57
                for (i = 0, len = itemsAfterDeleted.length; i < len; ++i)
58
                {
59
                    arr[idx + i] = itemsAfterDeleted[i];
60
                }
61
            }
62
        };
63

64
    function hashObject(obj)
65
    {
66
        var hashCode;
67
        if (typeof obj == "string")
68
        {
69
            return obj;
70
        } else if (typeof obj.hashCode == FUNCTION)
71
        {
72
            // Check the hashCode method really has returned a string
73
            hashCode = obj.hashCode();
74
            return (typeof hashCode == "string") ? hashCode : hashObject(hashCode);
75
        } else if (typeof obj.toString == FUNCTION)
76
        {
77
            return obj.toString();
78
        } else
79
        {
80
            try
81
            {
82
                return String(obj);
83
            }
84
            catch (ex)
85
            {
86
                // For host objects (such as ActiveObjects in IE) that have no toString() method and throw an error when
87
                // passed to String()
88
                return Object.prototype.toString.call(obj);
89
            }
90
        }
91
    }
92

93
    function equals_fixedValueHasEquals(fixedValue, variableValue)
94
    {
95
        return fixedValue.equals(variableValue);
96
    }
97

98
    function equals_fixedValueNoEquals(fixedValue, variableValue)
99
    {
100
        return (typeof variableValue.equals == FUNCTION) ?
101
            variableValue.equals(fixedValue) : (fixedValue === variableValue);
102
    }
103

104
    function createKeyValCheck(kvStr)
105
    {
106
        return function (kv)
107
        {
108
            if (kv === null)
109
            {
110
                throw new Error("null is not a valid " + kvStr);
111
            } else if (typeof kv == "undefined")
112
            {
113
                throw new Error(kvStr + " must not be undefined");
114
            }
115
        };
116
    }
117

118
    var checkKey = createKeyValCheck("key"), checkValue = createKeyValCheck("value");
119

120
    /*----------------------------------------------------------------------------------------------------------------*/
121

122
    function Bucket(hash, firstKey, firstValue, equalityFunction)
123
    {
124
        this[0] = hash;
125
        this.entries = [];
126
        this.addEntry(firstKey, firstValue);
127

128
        if (equalityFunction !== null)
129
        {
130
            this.getEqualityFunction = function ()
131
            {
132
                return equalityFunction;
133
            };
134
        }
135
    }
136

137
    var EXISTENCE = 0, ENTRY = 1, ENTRY_INDEX_AND_VALUE = 2;
138

139
    function createBucketSearcher(mode)
140
    {
141
        return function (key)
142
        {
143
            var i = this.entries.length, entry, equals = this.getEqualityFunction(key);
144
            while (i--)
145
            {
146
                entry = this.entries[i];
147
                if (equals(key, entry[0]))
148
                {
149
                    switch (mode)
150
                    {
151
                        case EXISTENCE:
152
                            return true;
153
                        case ENTRY:
154
                            return entry;
155
                        case ENTRY_INDEX_AND_VALUE:
156
                            return [ i, entry[1] ];
157
                    }
158
                }
159
            }
160
            return false;
161
        };
162
    }
163

164
    function createBucketLister(entryProperty)
165
    {
166
        return function (aggregatedArr)
167
        {
168
            var startIndex = aggregatedArr.length;
169
            for (var i = 0, len = this.entries.length; i < len; ++i)
170
            {
171
                aggregatedArr[startIndex + i] = this.entries[i][entryProperty];
172
            }
173
        };
174
    }
175

176
    Bucket.prototype = {
177
        getEqualityFunction:function (searchValue)
178
        {
179
            return (typeof searchValue.equals == FUNCTION) ? equals_fixedValueHasEquals : equals_fixedValueNoEquals;
180
        },
181

182
        getEntryForKey:createBucketSearcher(ENTRY),
183

184
        getEntryAndIndexForKey:createBucketSearcher(ENTRY_INDEX_AND_VALUE),
185

186
        removeEntryForKey:function (key)
187
        {
188
            var result = this.getEntryAndIndexForKey(key);
189
            if (result)
190
            {
191
                arrayRemoveAt(this.entries, result[0]);
192
                return result[1];
193
            }
194
            return null;
195
        },
196

197
        addEntry:function (key, value)
198
        {
199
            this.entries[this.entries.length] = [key, value];
200
        },
201

202
        keys:createBucketLister(0),
203

204
        values:createBucketLister(1),
205

206
        getEntries:function (entries)
207
        {
208
            var startIndex = entries.length;
209
            for (var i = 0, len = this.entries.length; i < len; ++i)
210
            {
211
                // Clone the entry stored in the bucket before adding to array
212
                entries[startIndex + i] = this.entries[i].slice(0);
213
            }
214
        },
215

216
        containsKey:createBucketSearcher(EXISTENCE),
217

218
        containsValue:function (value)
219
        {
220
            var i = this.entries.length;
221
            while (i--)
222
            {
223
                if (value === this.entries[i][1])
224
                {
225
                    return true;
226
                }
227
            }
228
            return false;
229
        }
230
    };
231

232
    /*----------------------------------------------------------------------------------------------------------------*/
233

234
    // Supporting functions for searching hashtable buckets
235

236
    function searchBuckets(buckets, hash)
237
    {
238
        var i = buckets.length, bucket;
239
        while (i--)
240
        {
241
            bucket = buckets[i];
242
            if (hash === bucket[0])
243
            {
244
                return i;
245
            }
246
        }
247
        return null;
248
    }
249

250
    function getBucketForHash(bucketsByHash, hash)
251
    {
252
        var bucket = bucketsByHash[hash];
253

254
        // Check that this is a genuine bucket and not something inherited from the bucketsByHash's prototype
255
        return ( bucket && (bucket instanceof Bucket) ) ? bucket : null;
256
    }
257

258
    /*----------------------------------------------------------------------------------------------------------------*/
259

260
    function Hashtable(hashingFunctionParam, equalityFunctionParam)
261
    {
262
        var that = this;
263
        var buckets = [];
264
        var bucketsByHash = {};
265

266
        var hashingFunction = (typeof hashingFunctionParam == FUNCTION) ? hashingFunctionParam : hashObject;
267
        var equalityFunction = (typeof equalityFunctionParam == FUNCTION) ? equalityFunctionParam : null;
268

269
        this.put = function (key, value)
270
        {
271
            checkKey(key);
272
            checkValue(value);
273
            var hash = hashingFunction(key), bucket, bucketEntry, oldValue = null;
274

275
            // Check if a bucket exists for the bucket key
276
            bucket = getBucketForHash(bucketsByHash, hash);
277
            if (bucket)
278
            {
279
                // Check this bucket to see if it already contains this key
280
                bucketEntry = bucket.getEntryForKey(key);
281
                if (bucketEntry)
282
                {
283
                    // This bucket entry is the current mapping of key to value, so replace old value and we're done.
284
                    oldValue = bucketEntry[1];
285
                    bucketEntry[1] = value;
286
                } else
287
                {
288
                    // The bucket does not contain an entry for this key, so add one
289
                    bucket.addEntry(key, value);
290
                }
291
            } else
292
            {
293
                // No bucket exists for the key, so create one and put our key/value mapping in
294
                bucket = new Bucket(hash, key, value, equalityFunction);
295
                buckets[buckets.length] = bucket;
296
                bucketsByHash[hash] = bucket;
297
            }
298
            return oldValue;
299
        };
300

301
        this.get = function (key)
302
        {
303
            checkKey(key);
304

305
            var hash = hashingFunction(key);
306

307
            // Check if a bucket exists for the bucket key
308
            var bucket = getBucketForHash(bucketsByHash, hash);
309
            if (bucket)
310
            {
311
                // Check this bucket to see if it contains this key
312
                var bucketEntry = bucket.getEntryForKey(key);
313
                if (bucketEntry)
314
                {
315
                    // This bucket entry is the current mapping of key to value, so return the value.
316
                    return bucketEntry[1];
317
                }
318
            }
319
            return null;
320
        };
321

322
        this.containsKey = function (key)
323
        {
324
            checkKey(key);
325
            var bucketKey = hashingFunction(key);
326

327
            // Check if a bucket exists for the bucket key
328
            var bucket = getBucketForHash(bucketsByHash, bucketKey);
329

330
            return bucket ? bucket.containsKey(key) : false;
331
        };
332

333
        this.containsValue = function (value)
334
        {
335
            checkValue(value);
336
            var i = buckets.length;
337
            while (i--)
338
            {
339
                if (buckets[i].containsValue(value))
340
                {
341
                    return true;
342
                }
343
            }
344
            return false;
345
        };
346

347
        this.clear = function ()
348
        {
349
            buckets.length = 0;
350
            bucketsByHash = {};
351
        };
352

353
        this.isEmpty = function ()
354
        {
355
            return !buckets.length;
356
        };
357

358
        var createBucketAggregator = function (bucketFuncName)
359
        {
360
            return function ()
361
            {
362
                var aggregated = [], i = buckets.length;
363
                while (i--)
364
                {
365
                    buckets[i][bucketFuncName](aggregated);
366
                }
367
                return aggregated;
368
            };
369
        };
370

371
        this.keys = createBucketAggregator("keys");
372
        this.values = createBucketAggregator("values");
373
        this.entries = createBucketAggregator("getEntries");
374

375
        this.remove = function (key)
376
        {
377
            checkKey(key);
378

379
            var hash = hashingFunction(key), bucketIndex, oldValue = null;
380

381
            // Check if a bucket exists for the bucket key
382
            var bucket = getBucketForHash(bucketsByHash, hash);
383

384
            if (bucket)
385
            {
386
                // Remove entry from this bucket for this key
387
                oldValue = bucket.removeEntryForKey(key);
388
                if (oldValue !== null)
389
                {
390
                    // Entry was removed, so check if bucket is empty
391
                    if (!bucket.entries.length)
392
                    {
393
                        // Bucket is empty, so remove it from the bucket collections
394
                        bucketIndex = searchBuckets(buckets, hash);
395
                        arrayRemoveAt(buckets, bucketIndex);
396
                        delete bucketsByHash[hash];
397
                    }
398
                }
399
            }
400
            return oldValue;
401
        };
402

403
        this.size = function ()
404
        {
405
            var total = 0, i = buckets.length;
406
            while (i--)
407
            {
408
                total += buckets[i].entries.length;
409
            }
410
            return total;
411
        };
412

413
        this.each = function (callback)
414
        {
415
            var entries = that.entries(), i = entries.length, entry;
416
            while (i--)
417
            {
418
                entry = entries[i];
419
                callback(entry[0], entry[1]);
420
            }
421
        };
422

423
        this.putAll = function (hashtable, conflictCallback)
424
        {
425
            var entries = hashtable.entries();
426
            var entry, key, value, thisValue, i = entries.length;
427
            var hasConflictCallback = (typeof conflictCallback == FUNCTION);
428
            while (i--)
429
            {
430
                entry = entries[i];
431
                key = entry[0];
432
                value = entry[1];
433

434
                // Check for a conflict. The default behaviour is to overwrite the value for an existing key
435
                if (hasConflictCallback && (thisValue = that.get(key)))
436
                {
437
                    value = conflictCallback(key, thisValue, value);
438
                }
439
                that.put(key, value);
440
            }
441
        };
442

443
        this.clone = function ()
444
        {
445
            var clone = new Hashtable(hashingFunctionParam, equalityFunctionParam);
446
            clone.putAll(that);
447
            return clone;
448
        };
449

450
        /**
451
         * Added by [email protected] to support debug dumping of hash arrays
452
         */
453
        this.toString = function ()
454
        {
455
            var result = '';
456
            var keys = this.keys();
457
            for (var i = 0; i < keys.length; i++)
458
            {
459
                var obj = this.get(keys[i]);
460
                result += keys[i].toString() + ' = ' + obj.toString() + '\n';
461
            }
462

463
            return result;
464
        }
465
    }
466

467
    return Hashtable;
468
})();
469