1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package inc.che.common.type;
20
21
22
23 import inc.che.common.resource.ResourceManager;
24 import inc.che.common.resource.StringResources;
25
26 import org.apache.log4j.Logger;
27
28 /***
29 * A hash map mapping int values to objects. This offers the benefit of not having to use objects
30 * as keys, which can result in performance benefits.
31 * @version $Id: IntHashMap.java,v 1.1 2005/03/06 12:56:58 stevemcmee Exp $
32 * @author <address> Steve McMee <stevemcmee@users.sourceforge.net></address>
33 */
34
35 public class IntHashMap {
36
37 /*** CVS ID of this file */
38 public static final String CVS_ID = "$Id:";
39
40 /***
41 * logger instance for this class
42 */
43
44 private static Logger log = Logger.getLogger(IntHashMap.class);
45
46 /***
47 * The ResourceManager
48 */
49 private static ResourceManager resourceManager =
50 ResourceManager.getResourceManager(StringResources.TEXT_RESOURCES);
51
52 /***
53 * The default capacity for hash map instances.
54 */
55
56 public static final int DEFAULT_CAPACITY = 17;
57
58 /***
59 * The maximum allowed capacity for hash map instances.
60 */
61
62 public static final int MAXIMUM_CAPACITY = 1 << 30;
63
64 /***
65 * The default load factor for hash map instances.
66 */
67
68 public static final float DEFAULT_LOADFACTOR = 0.75f;
69
70 private MapElement[] map = null;
71 private int[] count = null;
72 private int contents = 0;
73 private int objectCounter = 0;
74 private int capacity = DEFAULT_CAPACITY;
75 private int initialCap = DEFAULT_CAPACITY;
76 private float loadFactor = DEFAULT_LOADFACTOR;
77 private int maxLoad = 0;
78 private boolean rehashing = true;
79
80 /***
81 * Constructs an empty instance with the default initial capacity and the default load factor
82 */
83
84 public IntHashMap() {
85 this(DEFAULT_CAPACITY, DEFAULT_LOADFACTOR);
86 }
87
88 /***
89 * Constructs an empty instance with the given initial capacity and the default load factor
90 * <p>
91 * @param initialCapacity The initial capacity for this hash map.
92 */
93
94 public IntHashMap(int initialCapacity) {
95 this(initialCapacity, DEFAULT_LOADFACTOR);
96 }
97
98 /***
99 * Constructs an empty instance with the given initial capacity and the given load factor
100 * <p>
101 * @param initialCapacity The initial capacity for this hash map.
102 * @param loadFactor The load factor for this hash map.
103 */
104
105 public IntHashMap(int initialCapacity, float loadFactor) {
106 construct(initialCapacity, loadFactor);
107 }
108
109 /***
110 * Constructs a new HashMap with the same mappings as the specified Map. The HashMap
111 * is created with default load factor and an initial capacity sufficient to hold the
112 * mappings in the specified Map.
113 * <p>
114 * @param m The map whose mappings are to be placed in this map. Throws:
115 * <p>
116 * @throws NullPointerException if the specified map is <code>null</code>.
117 */
118
119 public IntHashMap(IntHashMap m) {
120
121 if (m == null) {
122 throw new IllegalArgumentException("m may not be null");
123 }
124
125
126
127 loadFactor = DEFAULT_LOADFACTOR;
128
129 capacity = (int) (m.size() / loadFactor);
130 if (capacity < DEFAULT_CAPACITY) {
131 capacity = DEFAULT_CAPACITY;
132 } else if (capacity % 2 == 0) {
133 capacity++;
134 }
135
136
137
138 maxLoad = (int) (loadFactor * capacity + 0.5f);
139
140 initialCap = capacity;
141
142 objectCounter += 2;
143 map = new MapElement[capacity];
144 count = new int[capacity];
145
146
147
148 int[] keys = m.keySet();
149 for (int i = 0; i < m.size(); i++) {
150 put(keys[i], m.get(keys[i]));
151 }
152
153 }
154
155 /***
156 * Return the current number of mappings in the hash map.
157 * <p>
158 * @return The current number of mappings in the hash map.
159 */
160
161 public int size() {
162 return contents;
163 }
164
165 /***
166 * Returns <code>true</code> if this map contains no key-value mappings.
167 */
168
169 public boolean isEmpty() {
170 return contents == 0 ? true : false;
171 }
172
173 /***
174 * Removes all mappings from this map.
175 */
176
177 public void clear() {
178 construct(initialCap, loadFactor);
179 }
180
181 /***
182 * Return the number of objects created in / by this instance
183 * <p>
184 * @return The number of objects created
185 */
186
187 public int getObjectCounter() {
188 return objectCounter;
189 }
190
191 /***
192 * Return the current capacity of the instance. If rehashing is enabled (which it is per
193 * default), the capacity may have been increased as necessary from the initial value.
194 * <p>
195 * @return The current capacity for this hash map.
196 */
197
198 public int getCapacity() {
199 return capacity;
200 }
201
202 /***
203 * Return the load factor of the instance.
204 * <p>
205 * @return The load factor for this hash map.
206 */
207
208 public float getLoadFactor() {
209 return loadFactor;
210 }
211
212 /***
213 * Return the keys in the hash map
214 * <p>
215 * @return An array containing the keys for which mappings are stored in this hash map.
216 */
217
218 public int[] keySet() {
219
220 objectCounter++;
221 int[] keys = new int[contents];
222 int cnt = 0;
223 MapElement me = null;
224
225 for (int i = 0; i < capacity; i++) {
226 if (map[i] != null) {
227 me = map[i];
228 for (int j = 0; j < count[i]; j++) {
229 keys[cnt++] = me.getKey();
230 me = me.getNext();
231 }
232 }
233 }
234
235 return keys;
236
237 }
238
239 /***
240 * Enable/disable rehashing (defaults to <code>true</code>).
241 * <p>
242 * @param rehashing A boolean indicating the desired rehashing status.
243 */
244
245 public void setRehash(boolean rehash) {
246 this.rehashing = rehash;
247 }
248
249 /***
250 * Associates the specified value with the specified key in this map. If
251 * the map previously contained a mapping for this key, the old value is replaced.
252 * <p>
253 * @param key The key with which the specified value is to be associated.
254 * @param value The value to be associated with the specified key.
255 * <p>
256 * @return Previous value associated with specified key, or <code>null</code> if there was no mapping
257 * for key. A <code>null</code> return can also indicate that the HashMap previously associated <code>null</code>
258 * with the specified key.
259 */
260
261 public Object put(int key, Object value) {
262
263 if (log.isDebugEnabled()) {
264 log.debug("put(" + key + "," + value + ")");
265 }
266
267 int index = key % capacity;
268 if (index < 0) {
269 index = -index;
270 }
271
272
273
274 if (map[index] == null) {
275 objectCounter++;
276 map[index] = new MapElement(key, value);
277 count[index]++;
278 contents++;
279 if (contents > maxLoad) {
280 rehash();
281 }
282 return null;
283
284
285
286 } else {
287
288 MapElement me = map[index];
289
290 while (true) {
291 if (me.getKey() == key) {
292
293 Object previous = me.getValue();
294
295 me.setValue(value);
296 return previous;
297 } else {
298 if (me.getNext() == null) {
299
300 objectCounter++;
301 me.setNext(new MapElement(key, value));
302 count[index]++;
303 contents++;
304 if (contents > maxLoad) {
305 rehash();
306 }
307 return null;
308 } else {
309 me = me.getNext();
310 }
311 }
312 }
313
314 }
315
316 }
317
318 /***
319 * Returns the value to which the specified key is mapped in this identity
320 * hash map, or <code>null</code> if the map contains no mapping for this key. A return
321 * value of <code>null</code> does not necessarily indicate that the map contains no
322 * mapping for the key; it is also possible that the map explicitly maps
323 * the key to <code>null</code>. The <code>containsKey</code>
324 * method may be used to distinguish these two cases.
325 * <p>
326 * @param key The key whose associated value is to be returned.
327 * <p>
328 * @return The value to which this map maps the specified key, or
329 * <code>null</code> if the map contains no mapping for this key.
330 */
331
332 public Object get(int key) {
333 MapElement me = exists(key);
334 if (me == null) {
335 return null;
336 } else {
337 return me.getValue();
338 }
339 }
340
341 /***
342 * Returns <code>true</code> if this map contains a mapping for the specified key.
343 * <p>
344 * @param key The key whose presence in this map is to be tested.
345 * <p>
346 * @return <code>true</code> if this map contains a mapping for the specified key.
347 */
348
349 public boolean containsKey(int key) {
350 if (exists(key) == null) {
351 return false;
352 } else {
353 return true;
354 }
355 }
356
357 /***
358 * Removes the mapping for this key from this map if present.
359 * <p>
360 * @param key The key whose mapping is to be removed from the map.
361 * <p>
362 * @return Previous value associated with specified key, or
363 * <code>null</code> if there was no mapping for key. A <code>null</code> return can
364 * also indicate that the map previously associated <code>null</code> with the specified key.
365 */
366
367 public Object remove(int key) {
368
369 int index = key % capacity;
370 if (index < 0) {
371 index = -index;
372 }
373
374 if (map[index] == null) {
375
376 return null;
377
378 } else {
379
380 MapElement me = map[index];
381 MapElement prev = null;
382
383 while (true) {
384
385 if (me.getKey() == key) {
386
387 if (prev == null) {
388
389 map[index] = me.getNext();
390 } else {
391
392 prev.setNext(me.getNext());
393 }
394 count[index]--;
395 contents--;
396 return me.getValue();
397
398 } else {
399
400 prev = me;
401 me = me.getNext();
402 if (me == null) {
403 return null;
404 }
405
406 }
407
408 }
409
410 }
411
412 }
413
414 /***
415 * Helper method: returns the element matching the key, or <code>null</code> if no such element exists
416 */
417
418 private MapElement exists(int key) {
419
420 int index = key % capacity;
421 if (index < 0) {
422 index = -index;
423 }
424
425 if (map[index] == null) {
426 return null;
427 } else {
428 MapElement me = map[index];
429 while (true) {
430 if (me.getKey() == key) {
431 return me;
432 } else {
433 me = me.getNext();
434 if (me == null) {
435 return null;
436 }
437 }
438 }
439 }
440
441 }
442
443 /***
444 * Increase the capacity of the map to improve performance
445 */
446
447 private void rehash() {
448
449 if (rehashing) {
450
451 int newCapacity = 2 * capacity + 1;
452 if (newCapacity > MAXIMUM_CAPACITY) {
453 return;
454 }
455
456 objectCounter += 2;
457 MapElement[] newMap = new MapElement[newCapacity];
458 int[] newCount = new int[newCapacity];
459
460 MapElement me = null;
461 MapElement t = null;
462 MapElement next = null;
463 int newIndex = 0;
464
465 for (int index = 0; index < capacity; index++) {
466 me = map[index];
467 while (me != null) {
468 next = me.getNext();
469 newIndex = me.getKey() % newCapacity;
470 if (newIndex < 0) {
471 newIndex = -newIndex;
472 }
473 newCount[newIndex]++;
474 if (newMap[newIndex] == null) {
475
476 newMap[newIndex] = me;
477 me.setNext(null);
478 } else {
479 t = newMap[newIndex];
480 newMap[newIndex] = me;
481 me.setNext(t);
482 }
483 me = next;
484 }
485 }
486
487 map = newMap;
488 count = newCount;
489 capacity = newCapacity;
490 maxLoad = (int) (loadFactor * capacity + 0.5f);
491
492
493 newMap = null;
494
495 }
496
497 }
498
499 /***
500 * Construction helper method
501 */
502
503 private void construct(int initialCapacity, float aLoadFactor) {
504 if (initialCapacity < 0) {
505 throw new IllegalArgumentException(
506 "Invalid initial capacity: " + initialCapacity);
507 }
508 if (initialCapacity < DEFAULT_CAPACITY) {
509 initialCapacity = DEFAULT_CAPACITY;
510 }
511 if (initialCapacity > MAXIMUM_CAPACITY) {
512 initialCapacity = MAXIMUM_CAPACITY;
513 }
514 if (aLoadFactor <= 0.0f || Float.isNaN(aLoadFactor)) {
515 throw new IllegalArgumentException(
516 "Invalid load factor: " + aLoadFactor);
517 }
518
519 this.initialCap = initialCapacity;
520 this.capacity = initialCapacity;
521 this.loadFactor = loadFactor;
522
523 objectCounter += 2;
524 maxLoad = (int) (aLoadFactor * capacity + 0.5f);
525
526 map = new MapElement[capacity];
527 count = new int[capacity];
528 contents = 0;
529 }
530
531 /***
532 * Statistical output for this map.
533 * <p>
534 * @param full A boolean indicating whether just a short of the full information should be printed.
535 */
536
537 public void printStatistics(boolean full) {
538 if (full) {
539 for (int i = 0; i < capacity; i++) {
540 System.out.println("Count[" + i + "] = " + count[i]);
541 }
542 }
543 System.out.println(
544 resourceManager.getText(
545 "initial_capacity",
546 new String[] {String.valueOf(initialCap)}));
547 System.out.println(
548 resourceManager.getText(
549 "capacity",
550 new String[] {String.valueOf(capacity)}));
551 System.out.println(
552 resourceManager.getText(
553 "number_of_elements",
554 new String[] {String.valueOf(contents)}));
555 }
556
557 /***
558 *
559 */
560
561 class MapElement {
562
563 private int key = 0;
564 private Object value = null;
565 private MapElement next = null;
566
567 /***
568 * Constructor
569 */
570
571 public MapElement(int key, Object value) {
572 this.key = key;
573 this.value = value;
574 }
575
576 /***
577 * Getter method for <code>key</code> property
578 * <p>
579 * @return The value for the <code>key</code> property
580 */
581
582 public int getKey() {
583 return key;
584 }
585
586 /***
587 * Setter method for <code>value</code> property
588 * <p>
589 * @param value The value for the <code>value</code> property
590 */
591
592 public void setValue(Object value) {
593 this.value = value;
594 }
595
596 /***
597 * Getter method for <code>value</code> property
598 * <p>
599 * @return The value for the <code>value</code> property
600 */
601
602 public Object getValue() {
603 return value;
604 }
605
606 /***
607 * Setter method for <code>next</code> property
608 * <p>
609 * @param next The value for the <code>next</code> property
610 */
611
612 public void setNext(MapElement next) {
613 this.next = next;
614 }
615
616 /***
617 * Getter method for <code>next</code> property
618 * <p>
619 * @return The value for the <code>next</code> property
620 */
621
622 public MapElement getNext() {
623 return next;
624 }
625
626 }
627
628 }