1 dojo.provide("calitha.collections.HashMap");
  2 dojo.require("calitha.collections.AbstractMap");
  3 dojo.require("calitha.collections.imap.IEntry");
  4 dojo.require("calitha.collections.hashmap.Entry");
  5 dojo.require("calitha.collections.util");
  6 dojo.require("calitha.collections.hashmap.EntrySet");
  7 dojo.require("calitha.collections.hashmap.KeySet");
  8 dojo.require("calitha.collections.hashmap.Values");
  9 dojo.require("calitha.collections.hashmap.EntryIterator");
 10 dojo.require("calitha.collections.hashmap.KeyIterator");
 11 dojo.require("calitha.collections.hashmap.ValueIterator");
 12 dojo.require("calitha.exception.IllegalArgumentException");
 13 
 14 dojo.declare("calitha.collections.HashMap", calitha.collections.AbstractMap,
 15 /** @lends calitha.collections.HashMap#*/
 16 {
 17     /**
 18      * @constructs
 19      * @extends calitha.collections.AbstractMap
 20      * @param initialCapacity optional initial capacity
 21      * @param loadFactor optional loadFactor
 22      * @description Hash table based implementation of the Map interface.
 23      * <p>This class is similar to the
 24      * <a href="http://java.sun.com/javase/6/docs/api/java/util/HashMap.html">Java HashMap class</a>
 25      * <p>Each key object must have an equals and hashCode method. This is also true for numbers and strings.
 26      * However you can use the {@link calitha.collections.makeNumberHashCompatible} and
 27      * {@link calitha.collections.makeStringHashCompatible} to use those directly.
 28      */
 29     constructor: function(/**Number?*/ initialCapacity, /**Number?*/ loadFactor)
 30     {
 31         if (initialCapacity == null)
 32         {
 33             initialCapacity = calitha.collections.HashMap._DEFAULT_INITIAL_CAPACITY;
 34         }
 35         if (loadFactor == null)
 36         {
 37             loadFactor = calitha.collections.HashMap._DEFAULT_LOAD_FACTOR;
 38         }
 39         if (initialCapacity < 0)
 40         {
 41             throw new calitha.exception.IllegalArgumentException(Error("Illegal initial capacity: " + initialCapacity));
 42         }
 43         if (initialCapacity > calitha.collections.HashMap._DEFAULT_INITIAL_CAPACITY)
 44         {
 45             initialCapacity = calitha.collections.HashMap._DEFAULT_INITIAL_CAPACITY;
 46         }
 47         if (loadFactor <= 0 || isNaN(loadFactor))
 48         {
 49             throw new calitha.exception.IllegalArgumentException(Error("Illegal load factor: " + loadFactor));
 50         }
 51 
 52         // Find a power of 2 >= initialCapacity
 53         var capacity = 1;
 54         while (capacity < initialCapacity)
 55         {
 56             capacity <<= 1;
 57         }
 58 
 59         this._loadFactor = loadFactor;
 60         this._threshold = Math.round(capacity * loadFactor);
 61         this._table = new Array(capacity);
 62         this._size = 0;
 63         this._modCount = 0;
 64         this._entrySet = null;
 65         this._init();
 66     }
 67     ,
 68     clear: function()
 69     {
 70         this._modCount++;
 71         for (var i = 0; i < this._table.length; i++)
 72         {
 73             this._table[i] = null;
 74         }
 75         this._size = 0;
 76     }
 77     ,
 78     containsKey: function(/**Object*/ key)
 79     {
 80         return this._getEntry(key) != null;
 81     }
 82     ,
 83     containsValue: function(/**Object*/ value)
 84     {
 85         for (var i = 0; i < this._table.length ; i++)
 86         {
 87             for (var entry = this._table[i]; entry != null; entry = entry.getNext())
 88             {
 89                 if (calitha.collections.util.equals(value, entry.getValue()))
 90                 {
 91                     return true;
 92                 }
 93             }
 94         }
 95     	return false;
 96     }
 97     ,
 98     entrySet: function()
 99     {
100         if (this._entrySet === null)
101         {
102             this._entrySet = new calitha.collections.hashmap.EntrySet(this);
103         }
104         return this._entrySet;
105     }
106     ,
107     get: function(/**Object*/ key)
108     {
109         if (key === null)
110         {
111             return this._getForNullKey();
112         }
113         var hash = this._hash(key.hashCode());
114         var index = this._indexFor(hash, this._table.length);
115         var entry = this._table[index];
116         while (entry != null)
117         {
118             if ((entry.getHash() === hash) && (calitha.collections.util.equals(key, entry.getKey())))
119             {
120                 return entry.getValue();
121             }
122             entry = entry.getNext();
123         }
124         return null;
125     }
126     ,
127     isEmpty: function()
128     {
129         return this._size === 0;
130     }
131     ,
132     keySet: function()
133     {
134         if (this._keySet === null)
135         {
136             this._keySet = new calitha.collections.hashmap.KeySet(this);
137         }
138         return this._keySet;
139     }
140     ,
141     put: function(/**Object*/ key, /**Object*/ value)
142     {
143         if (key === null)
144         {
145             return this._putForNullKey(value);
146         }
147         var hash = this._hash(calitha.collections.util.hashCode(key));
148         var index = this._indexFor(hash, this._table.length);
149         var entry = this._table[index];
150         while (entry != null)
151         {
152             if ((entry.getHash() === hash) && (calitha.collections.util.equals(entry.getKey(), key)))
153             {
154                 var oldValue = entry.setValue(value);
155                 entry.recordAccess(this);
156                 return oldValue;
157             }
158             entry = entry.getNext();
159         }
160         this._modCount++;
161         this._addEntry(hash, key, value, index);
162         return null;
163     }
164     ,
165     putAll: function(/**calitha.collections.IMap*/ map)
166     {
167         var numKeysToBeAdded = map.size();
168         if (numKeysToBeAdded === 0)
169         {
170             return;
171         }
172 
173         /*
174          * Expand the map if the map if the number of mappings to be added
175          * is greater than or equal to threshold.  This is conservative; the
176          * obvious condition is (m.size() + size) >= threshold, but this
177          * condition could result in a map with twice the appropriate capacity,
178          * if the keys to be added overlap with the keys already in this map.
179          * By using the conservative calculation, we subject ourself
180          * to at most one extra resize.
181          */
182         if (numKeysToBeAdded > this._threshold)
183         {
184             var targetCapacity = Math.round(numKeysToBeAdded / this._loadFactor + 1);
185             if (targetCapacity > calitha.collections.HashMap._MAXIMUM_CAPACITY)
186             {
187                 targetCapacity = calitha.collections.HashMap._MAXIMUM_CAPACITY;
188             }
189             var newCapacity = this._table.length;
190             while (newCapacity < targetCapacity)
191             {
192                 newCapacity <<= 1;
193             }
194             if (newCapacity > this._table.length)
195             {
196                 this._resize(newCapacity);
197             }
198         }
199 
200         var it = map.entrySet().iterator();
201         while (it.hasNext())
202         {
203             var entry = it.next();
204             this.put(entry.getKey(), entry.getValue());
205         }
206     }
207     ,
208     remove: function(/**Object*/ key)
209     {
210         var entry = this._removeEntryForKey(key);
211         return (entry === null ? null : entry.getValue());
212     }
213     ,
214     size: function()
215     {
216         return this._size;
217     }
218     ,
219     values: function()
220     {
221         if (this._values === null)
222         {
223             this._values = new calitha.collections.hashmap.Values(this);
224         }
225         return this._values;
226     }
227     ,
228     _addEntry: function(/**Number*/ hash, /**Object*/ key, /**Object*/ value, /**Number*/ bucketIndex)
229     {
230         this._table[bucketIndex] = new calitha.collections.hashmap.Entry(hash, key, value, this._table[bucketIndex]);
231         if (this._size++ >= this._threshold)
232         {
233             this._resize(2 * this._table.length);
234         }
235     }
236     ,
237     _getEntry: function(/**Object*/ key)
238     {
239         if ((key != null) && (key.hashCode == null))
240         {
241             return null;
242         }
243         var hash = (key === null) ? 0 : this._hash(key.hashCode());
244         var index = this._indexFor(hash, this._table.length);
245         var entry = this._table[index];
246         while (entry != null)
247         {
248             if ((entry.getHash() === hash) && (calitha.collections.util.equals(entry.getKey(), key)))
249             {
250                 return entry;
251             }
252             entry = entry.getNext();
253         }
254         return null;
255     }
256     ,
257     _getForNullKey: function()
258     {
259         var entry = this._table[0];
260         while (entry != null)
261         {
262             if (entry.getKey() === null)
263             {
264                 return entry.getValue();
265             }
266             entry = entry.getNext();
267         }
268         return null;
269     }
270     ,
271     _hash: function(/**Number*/ h)
272     {
273         h ^= (h >>> 20) ^ (h >>> 12);
274         return h ^ (h >>> 7) ^ (h >>> 4);
275     }
276     ,
277     _indexFor: function(/**Number*/ hash, /**Number*/ length)
278     {
279         return hash & (length - 1);
280     }
281     ,
282     _init: function()
283     {
284     }
285     ,
286     _newEntryIterator: function()
287     {
288         return new calitha.collections.hashmap.EntryIterator(this);
289     }
290     ,
291     _newKeyIterator: function()
292     {
293         return new calitha.collections.hashmap.KeyIterator(this);
294     }
295     ,
296     _newValueIterator: function()
297     {
298         return new calitha.collections.hashmap.ValueIterator(this);
299     }
300     ,
301     _putForNullKey: function(/**Object*/ value)
302     {
303         var entry = this._table[0];
304         while (entry != null)
305         {
306             if (entry.getKey() === null)
307             {
308                 var oldValue = entry.setValue(value);
309                 entry.recordAccess(this);
310                 return oldValue;
311             }
312         }
313         this._modCount++;
314         this._addEntry(0, null, value, 0);
315         return null;
316     }
317     ,
318     _removeEntryForKey: function(/**Object*/ key)
319     {
320         var hash = calitha.collections.util.hashCode(key);
321         hash = this._hash(hash);
322 
323         var index = this._indexFor(hash, this._table.length);
324         var prev = this._table[index];
325         var entry = prev;
326 
327         while (entry != null)
328         {
329             var next = entry.getNext();
330             if ((entry.getHash() === hash) && (calitha.collections.util.equals(entry.getKey(), key)))
331             {
332                 this._modCount++;
333                 this._size--;
334                 if (prev === entry)
335                 {
336                     this._table[index] = next;
337                 }
338                 else
339                 {
340                     prev._next = next;
341                 }
342                 entry.recordRemoval(this);
343                 return entry;
344             }
345             prev = entry;
346             entry = next;
347         }
348         if (entry === undefined)
349         {
350             return null;
351         }
352         return entry;
353     }
354     ,
355     _removeMapping: function(/**Object*/ o)
356     {
357         if (!calitha.collections.util.isObjectInstanceOf(o, calitha.collections.imap.IEntry))
358         {
359             return null;
360         }
361 
362         //noinspection UnnecessaryLocalVariableJS
363         var entry = o;
364         var key = entry.getKey();
365         var hash = calitha.collections.util.hashCode(key);
366         var index = this._indexFor(hash, this._table.length);
367         var prev = this._table[index];
368         var e = prev;
369 
370         while (e != null)
371         {
372             var next = e.getNext();
373             if (e.getHash() === hash && e.equals(entry))
374             {
375                 this._modCount++;
376                 this._size--;
377                 if (prev === e)
378                 {
379                     this._table[index] = next;
380                 }
381                 else
382                 {
383                     prev.setNext(next);
384                 }
385                 e.recordRemoval(this);
386                 return e;
387             }
388             prev = e;
389             e = next;
390         }
391         return e;
392     }
393     ,
394     _resize: function(/**Number*/ newCapacity)
395     {
396         var oldTable = this._table;
397         var oldCapacity = oldTable.length;
398         if (oldCapacity === calitha.collections.HashMap._MAXIMUM_CAPACITY)
399         {
400             this._threshold = Number.MAX_VALUE;
401             return;
402         }
403         var newTable = new Array(newCapacity);
404         this._transfer(newTable);
405         this._table = newTable;
406         this._threshold = Math.round(newCapacity * this._loadFactor);
407     }
408     ,
409     _transfer: function(/**Array*/ newTable)
410     {
411         var src = this._table;
412         var newCapacity = newTable.length;
413         for (var j = 0; j < src.length; j++)
414         {
415             var entry = src[j];
416             if (entry != null)
417             {
418                 src[j] = null;
419                 do
420                 {
421                     var next = entry.getNext();
422                     var i = this._indexFor(entry.getHash(), newCapacity);
423                     entry.setNext(newTable[i]);
424                     newTable[i] = entry;
425                     entry = next;
426                 } while (entry != null);
427             }
428         }
429     }
430 
431 });
432 
433 calitha.collections.HashMap._DEFAULT_INITIAL_CAPACITY = 16;
434 calitha.collections.HashMap._MAXIMUM_CAPACITY = 1 << 30;
435 calitha.collections.HashMap._DEFAULT_LOAD_FACTOR = 0.75;
436