Mercurial > hg > blitz_condensed
comparison src/com/go/trove/util/IntHashMap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
1 /* ==================================================================== | |
2 * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group | |
3 * ==================================================================== | |
4 * The Tea Software License, Version 1.1 | |
5 * | |
6 * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved. | |
7 * | |
8 * Redistribution and use in source and binary forms, with or without | |
9 * modification, are permitted provided that the following conditions | |
10 * are met: | |
11 * | |
12 * 1. Redistributions of source code must retain the above copyright | |
13 * notice, this list of conditions and the following disclaimer. | |
14 * | |
15 * 2. Redistributions in binary form must reproduce the above copyright | |
16 * notice, this list of conditions and the following disclaimer in | |
17 * the documentation and/or other materials provided with the | |
18 * distribution. | |
19 * | |
20 * 3. The end-user documentation included with the redistribution, | |
21 * if any, must include the following acknowledgment: | |
22 * "This product includes software developed by the | |
23 * Walt Disney Internet Group (http://opensource.go.com/)." | |
24 * Alternately, this acknowledgment may appear in the software itself, | |
25 * if and wherever such third-party acknowledgments normally appear. | |
26 * | |
27 * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must | |
28 * not be used to endorse or promote products derived from this | |
29 * software without prior written permission. For written | |
30 * permission, please contact opensource@dig.com. | |
31 * | |
32 * 5. Products derived from this software may not be called "Tea", | |
33 * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet", | |
34 * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior | |
35 * written permission of the Walt Disney Internet Group. | |
36 * | |
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED | |
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
40 * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS | |
41 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | |
45 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
46 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
47 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
48 * ==================================================================== | |
49 * | |
50 * For more information about Tea, please see http://opensource.go.com/. | |
51 */ | |
52 | |
53 package com.go.trove.util; | |
54 | |
55 import java.util.*; | |
56 import java.io.*; | |
57 | |
58 /****************************************************************************** | |
59 * A Map that accepts int or Integer keys only. Most of the implementation for | |
60 * this class is ripped off from java.util.HashMap. | |
61 * | |
62 * @author Brian S O'Neill | |
63 * @version | |
64 * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 9/07/00 <!-- $--> | |
65 * @see java.util.HashMap | |
66 */ | |
67 public class IntHashMap extends AbstractMap | |
68 implements Map, Cloneable, Serializable { | |
69 | |
70 /** | |
71 * The hash table data. | |
72 */ | |
73 private transient Entry table[]; | |
74 | |
75 /** | |
76 * The total number of mappings in the hash table. | |
77 */ | |
78 private transient int count; | |
79 | |
80 /** | |
81 * The table is rehashed when its size exceeds this threshold. (The | |
82 * value of this field is (int)(capacity * loadFactor).) | |
83 * | |
84 * @serial | |
85 */ | |
86 private int threshold; | |
87 | |
88 /** | |
89 * The load factor for the hashtable. | |
90 * | |
91 * @serial | |
92 */ | |
93 private float loadFactor; | |
94 | |
95 /** | |
96 * The number of times this IntHashMap has been structurally modified | |
97 * Structural modifications are those that change the number of mappings in | |
98 * the IntHashMap or otherwise modify its internal structure (e.g., | |
99 * rehash). This field is used to make iterators on Collection-views of | |
100 * the IntHashMap fail-fast. (See ConcurrentModificationException). | |
101 */ | |
102 private transient int modCount = 0; | |
103 | |
104 /** | |
105 * Constructs a new, empty map with the specified initial | |
106 * capacity and the specified load factor. | |
107 * | |
108 * @param initialCapacity the initial capacity of the IntHashMap. | |
109 * @param loadFactor the load factor of the IntHashMap | |
110 * @throws IllegalArgumentException if the initial capacity is less | |
111 * than zero, or if the load factor is nonpositive. | |
112 */ | |
113 public IntHashMap(int initialCapacity, float loadFactor) { | |
114 if (initialCapacity < 0) { | |
115 throw new IllegalArgumentException("Illegal Initial Capacity: "+ | |
116 initialCapacity); | |
117 } | |
118 | |
119 if (loadFactor <= 0) { | |
120 throw new IllegalArgumentException("Illegal Load factor: "+ | |
121 loadFactor); | |
122 } | |
123 | |
124 if (initialCapacity==0) { | |
125 initialCapacity = 1; | |
126 } | |
127 | |
128 this.loadFactor = loadFactor; | |
129 table = new Entry[initialCapacity]; | |
130 threshold = (int)(initialCapacity * loadFactor); | |
131 } | |
132 | |
133 /** | |
134 * Constructs a new, empty map with the specified initial capacity | |
135 * and default load factor, which is <tt>0.75</tt>. | |
136 * | |
137 * @param initialCapacity the initial capacity of the IntHashMap. | |
138 * @throws IllegalArgumentException if the initial capacity is less | |
139 * than zero. | |
140 */ | |
141 public IntHashMap(int initialCapacity) { | |
142 this(initialCapacity, 0.75f); | |
143 } | |
144 | |
145 /** | |
146 * Constructs a new, empty map with a default capacity and load | |
147 * factor, which is <tt>0.75</tt>. | |
148 */ | |
149 public IntHashMap() { | |
150 this(101, 0.75f); | |
151 } | |
152 | |
153 /** | |
154 * Constructs a new map with the same mappings as the given map. The | |
155 * map is created with a capacity of twice the number of mappings in | |
156 * the given map or 11 (whichever is greater), and a default load factor, | |
157 * which is <tt>0.75</tt>. | |
158 */ | |
159 public IntHashMap(Map t) { | |
160 this(Math.max(2*t.size(), 11), 0.75f); | |
161 putAll(t); | |
162 } | |
163 | |
164 /** | |
165 * Returns the number of key-value mappings in this map. | |
166 * | |
167 * @return the number of key-value mappings in this map. | |
168 */ | |
169 public int size() { | |
170 return count; | |
171 } | |
172 | |
173 /** | |
174 * Returns <tt>true</tt> if this map contains no key-value mappings. | |
175 * | |
176 * @return <tt>true</tt> if this map contains no key-value mappings. | |
177 */ | |
178 public boolean isEmpty() { | |
179 return count == 0; | |
180 } | |
181 | |
182 /** | |
183 * Returns <tt>true</tt> if this map maps one or more keys to the | |
184 * specified value. | |
185 * | |
186 * @param value value whose presence in this map is to be tested. | |
187 * @return <tt>true</tt> if this map maps one or more keys to the | |
188 * specified value. | |
189 */ | |
190 public boolean containsValue(Object value) { | |
191 Entry tab[] = table; | |
192 | |
193 if (value==null) { | |
194 for (int i = tab.length ; i-- > 0 ;) { | |
195 for (Entry e = tab[i] ; e != null ; e = e.next) { | |
196 if (e.value == null) { | |
197 return true; | |
198 } | |
199 } | |
200 } | |
201 } | |
202 else { | |
203 for (int i = tab.length ; i-- > 0 ;) { | |
204 for (Entry e = tab[i] ; e != null ; e = e.next) { | |
205 if (value.equals(e.value)) { | |
206 return true; | |
207 } | |
208 } | |
209 } | |
210 } | |
211 | |
212 return false; | |
213 } | |
214 | |
215 /** | |
216 * Returns <tt>true</tt> if this map contains a mapping for the specified | |
217 * key. | |
218 * | |
219 * @return <tt>true</tt> if this map contains a mapping for the specified | |
220 * key. | |
221 * @param key key whose presence in this Map is to be tested. | |
222 */ | |
223 public boolean containsKey(Object key) { | |
224 if (key instanceof Number) { | |
225 return containsKey( ((Number)key).intValue() ); | |
226 } | |
227 else { | |
228 return false; | |
229 } | |
230 } | |
231 | |
232 /** | |
233 * Returns <tt>true</tt> if this map contains a mapping for the specified | |
234 * key. | |
235 * | |
236 * @return <tt>true</tt> if this map contains a mapping for the specified | |
237 * key. | |
238 * @param key key whose presence in this Map is to be tested. | |
239 */ | |
240 public boolean containsKey(int key) { | |
241 Entry tab[] = table; | |
242 | |
243 int index = (key & 0x7FFFFFFF) % tab.length; | |
244 for (Entry e = tab[index]; e != null; e = e.next) { | |
245 if (e.key == key) { | |
246 return true; | |
247 } | |
248 } | |
249 | |
250 return false; | |
251 } | |
252 | |
253 /** | |
254 * Returns the value to which this map maps the specified key. Returns | |
255 * <tt>null</tt> if the map contains no mapping for this key. A return | |
256 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the | |
257 * map contains no mapping for the key; it's also possible that the map | |
258 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt> | |
259 * operation may be used to distinguish these two cases. | |
260 * | |
261 * @return the value to which this map maps the specified key. | |
262 * @param key key whose associated value is to be returned. | |
263 */ | |
264 public Object get(Object key) { | |
265 if (key instanceof Number) { | |
266 return get( ((Number)key).intValue() ); | |
267 } | |
268 else { | |
269 return null; | |
270 } | |
271 } | |
272 | |
273 /** | |
274 * Returns the value to which this map maps the specified key. Returns | |
275 * <tt>null</tt> if the map contains no mapping for this key. A return | |
276 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the | |
277 * map contains no mapping for the key; it's also possible that the map | |
278 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt> | |
279 * operation may be used to distinguish these two cases. | |
280 * | |
281 * @return the value to which this map maps the specified key. | |
282 * @param key key whose associated value is to be returned. | |
283 */ | |
284 public Object get(int key) { | |
285 Entry tab[] = table; | |
286 | |
287 int index = (key & 0x7FFFFFFF) % tab.length; | |
288 for (Entry e = tab[index]; e != null; e = e.next) { | |
289 if (e.key == key) { | |
290 return e.value; | |
291 } | |
292 } | |
293 | |
294 return null; | |
295 } | |
296 | |
297 /** | |
298 * Rehashes the contents of this map into a new <tt>IntHashMap</tt> instance | |
299 * with a larger capacity. This method is called automatically when the | |
300 * number of keys in this map exceeds its capacity and load factor. | |
301 */ | |
302 private void rehash() { | |
303 int oldCapacity = table.length; | |
304 Entry oldMap[] = table; | |
305 | |
306 int newCapacity = oldCapacity * 2 + 1; | |
307 Entry newMap[] = new Entry[newCapacity]; | |
308 | |
309 modCount++; | |
310 threshold = (int)(newCapacity * loadFactor); | |
311 table = newMap; | |
312 | |
313 for (int i = oldCapacity ; i-- > 0 ;) { | |
314 for (Entry old = oldMap[i] ; old != null ; ) { | |
315 Entry e = old; | |
316 old = old.next; | |
317 | |
318 int index = (e.key & 0x7FFFFFFF) % newCapacity; | |
319 e.next = newMap[index]; | |
320 newMap[index] = e; | |
321 } | |
322 } | |
323 } | |
324 | |
325 /** | |
326 * Associates the specified value with the specified key in this map. | |
327 * If the map previously contained a mapping for this key, the old | |
328 * value is replaced. | |
329 * | |
330 * @param key key with which the specified value is to be associated. | |
331 * @param value value to be associated with the specified key. | |
332 * @return previous value associated with specified key, or <tt>null</tt> | |
333 * if there was no mapping for key. A <tt>null</tt> return can | |
334 * also indicate that the IntHashMap previously associated | |
335 * <tt>null</tt> with the specified key. | |
336 */ | |
337 public Object put(Object key, Object value) { | |
338 if (key instanceof Number) { | |
339 return put( ((Number)key).intValue(), value ); | |
340 } | |
341 else { | |
342 throw new UnsupportedOperationException | |
343 ("IntHashMap key must be a number"); | |
344 } | |
345 } | |
346 | |
347 /** | |
348 * Associates the specified value with the specified key in this map. | |
349 * If the map previously contained a mapping for this key, the old | |
350 * value is replaced. | |
351 * | |
352 * @param key key with which the specified value is to be associated. | |
353 * @param value value to be associated with the specified key. | |
354 * @return previous value associated with specified key, or <tt>null</tt> | |
355 * if there was no mapping for key. A <tt>null</tt> return can | |
356 * also indicate that the IntHashMap previously associated | |
357 * <tt>null</tt> with the specified key. | |
358 */ | |
359 public Object put(int key, Object value) { | |
360 // Makes sure the key is not already in the IntHashMap. | |
361 Entry tab[] = table; | |
362 int index = 0; | |
363 | |
364 index = (key & 0x7FFFFFFF) % tab.length; | |
365 for (Entry e = tab[index] ; e != null ; e = e.next) { | |
366 if (e.key == key) { | |
367 Object old = e.value; | |
368 e.value = value; | |
369 return old; | |
370 } | |
371 } | |
372 | |
373 modCount++; | |
374 if (count >= threshold) { | |
375 // Rehash the table if the threshold is exceeded | |
376 rehash(); | |
377 | |
378 tab = table; | |
379 index = (key & 0x7FFFFFFF) % tab.length; | |
380 } | |
381 | |
382 // Creates the new entry. | |
383 Entry e = new Entry(key, value, tab[index]); | |
384 tab[index] = e; | |
385 count++; | |
386 return null; | |
387 } | |
388 | |
389 /** | |
390 * Removes the mapping for this key from this map if present. | |
391 * | |
392 * @param key key whose mapping is to be removed from the map. | |
393 * @return previous value associated with specified key, or <tt>null</tt> | |
394 * if there was no mapping for key. A <tt>null</tt> return can | |
395 * also indicate that the map previously associated <tt>null</tt> | |
396 * with the specified key. | |
397 */ | |
398 public Object remove(Object key) { | |
399 if (key instanceof Number) { | |
400 return remove( ((Number)key).intValue() ); | |
401 } | |
402 else { | |
403 return null; | |
404 } | |
405 } | |
406 | |
407 /** | |
408 * Removes the mapping for this key from this map if present. | |
409 * | |
410 * @param key key whose mapping is to be removed from the map. | |
411 * @return previous value associated with specified key, or <tt>null</tt> | |
412 * if there was no mapping for key. A <tt>null</tt> return can | |
413 * also indicate that the map previously associated <tt>null</tt> | |
414 * with the specified key. | |
415 */ | |
416 public Object remove(int key) { | |
417 Entry tab[] = table; | |
418 | |
419 int index = (key & 0x7FFFFFFF) % tab.length; | |
420 | |
421 for (Entry e = tab[index], prev = null; e != null; | |
422 prev = e, e = e.next) { | |
423 | |
424 if (e.key == key) { | |
425 modCount++; | |
426 if (prev != null) { | |
427 prev.next = e.next; | |
428 } | |
429 else { | |
430 tab[index] = e.next; | |
431 } | |
432 | |
433 count--; | |
434 Object oldValue = e.value; | |
435 e.value = null; | |
436 return oldValue; | |
437 } | |
438 } | |
439 | |
440 return null; | |
441 } | |
442 | |
443 /** | |
444 * Copies all of the mappings from the specified map to this one. | |
445 * | |
446 * These mappings replace any mappings that this map had for any of the | |
447 * keys currently in the specified Map. | |
448 * | |
449 * @param t Mappings to be stored in this map. | |
450 */ | |
451 public void putAll(Map t) { | |
452 Iterator i = t.entrySet().iterator(); | |
453 while (i.hasNext()) { | |
454 Map.Entry e = (Map.Entry) i.next(); | |
455 put(e.getKey(), e.getValue()); | |
456 } | |
457 } | |
458 | |
459 /** | |
460 * Removes all mappings from this map. | |
461 */ | |
462 public void clear() { | |
463 Entry tab[] = table; | |
464 modCount++; | |
465 for (int index = tab.length; --index >= 0; ) { | |
466 tab[index] = null; | |
467 } | |
468 count = 0; | |
469 } | |
470 | |
471 /** | |
472 * Returns a shallow copy of this <tt>IntHashMap</tt> instance: the keys and | |
473 * values themselves are not cloned. | |
474 * | |
475 * @return a shallow copy of this map. | |
476 */ | |
477 public Object clone() { | |
478 try { | |
479 IntHashMap t = (IntHashMap)super.clone(); | |
480 t.table = new Entry[table.length]; | |
481 for (int i = table.length ; i-- > 0 ; ) { | |
482 t.table[i] = (table[i] != null) | |
483 ? (Entry)table[i].clone() : null; | |
484 } | |
485 t.keySet = null; | |
486 t.entrySet = null; | |
487 t.values = null; | |
488 t.modCount = 0; | |
489 return t; | |
490 } | |
491 catch (CloneNotSupportedException e) { | |
492 // this shouldn't happen, since we are Cloneable | |
493 throw new InternalError(); | |
494 } | |
495 } | |
496 | |
497 // Views | |
498 | |
499 private transient Set keySet = null; | |
500 private transient Set entrySet = null; | |
501 private transient Collection values = null; | |
502 | |
503 /** | |
504 * Returns a set view of the keys contained in this map. The set is | |
505 * backed by the map, so changes to the map are reflected in the set, and | |
506 * vice-versa. The set supports element removal, which removes the | |
507 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, | |
508 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
509 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
510 * <tt>addAll</tt> operations. | |
511 * | |
512 * @return a set view of the keys contained in this map. | |
513 */ | |
514 public Set keySet() { | |
515 if (keySet == null) { | |
516 keySet = new AbstractSet() { | |
517 public Iterator iterator() { | |
518 return new IntHashIterator(KEYS); | |
519 } | |
520 public int size() { | |
521 return count; | |
522 } | |
523 public boolean contains(Object o) { | |
524 return containsKey(o); | |
525 } | |
526 public boolean remove(Object o) { | |
527 return IntHashMap.this.remove(o) != null; | |
528 } | |
529 public void clear() { | |
530 IntHashMap.this.clear(); | |
531 } | |
532 }; | |
533 } | |
534 return keySet; | |
535 } | |
536 | |
537 /** | |
538 * Returns a collection view of the values contained in this map. The | |
539 * collection is backed by the map, so changes to the map are reflected in | |
540 * the collection, and vice-versa. The collection supports element | |
541 * removal, which removes the corresponding mapping from this map, via the | |
542 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
543 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
544 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
545 * | |
546 * @return a collection view of the values contained in this map. | |
547 */ | |
548 public Collection values() { | |
549 if (values==null) { | |
550 values = new AbstractCollection() { | |
551 public Iterator iterator() { | |
552 return new IntHashIterator(VALUES); | |
553 } | |
554 public int size() { | |
555 return count; | |
556 } | |
557 public boolean contains(Object o) { | |
558 return containsValue(o); | |
559 } | |
560 public void clear() { | |
561 IntHashMap.this.clear(); | |
562 } | |
563 }; | |
564 } | |
565 return values; | |
566 } | |
567 | |
568 /** | |
569 * Returns a collection view of the mappings contained in this map. Each | |
570 * element in the returned collection is a <tt>Map.Entry</tt>. The | |
571 * collection is backed by the map, so changes to the map are reflected in | |
572 * the collection, and vice-versa. The collection supports element | |
573 * removal, which removes the corresponding mapping from the map, via the | |
574 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
575 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
576 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
577 * | |
578 * @return a collection view of the mappings contained in this map. | |
579 * @see Map.Entry | |
580 */ | |
581 public Set entrySet() { | |
582 if (entrySet==null) { | |
583 entrySet = new AbstractSet() { | |
584 public Iterator iterator() { | |
585 return new IntHashIterator(ENTRIES); | |
586 } | |
587 | |
588 public boolean contains(Object o) { | |
589 if (!(o instanceof Map.Entry)) { | |
590 return false; | |
591 } | |
592 Map.Entry entry = (Map.Entry)o; | |
593 Object key = entry.getKey(); | |
594 Entry tab[] = table; | |
595 int hash = (key==null ? 0 : key.hashCode()); | |
596 int index = (hash & 0x7FFFFFFF) % tab.length; | |
597 | |
598 for (Entry e = tab[index]; e != null; e = e.next) { | |
599 if (e.key == hash && e.equals(entry)) { | |
600 return true; | |
601 } | |
602 } | |
603 return false; | |
604 } | |
605 | |
606 public boolean remove(Object o) { | |
607 if (!(o instanceof Map.Entry)) | |
608 return false; | |
609 Map.Entry entry = (Map.Entry)o; | |
610 Object key = entry.getKey(); | |
611 Entry tab[] = table; | |
612 int hash = (key==null ? 0 : key.hashCode()); | |
613 int index = (hash & 0x7FFFFFFF) % tab.length; | |
614 | |
615 for (Entry e = tab[index], prev = null; e != null; | |
616 prev = e, e = e.next) { | |
617 if (e.key == hash && e.equals(entry)) { | |
618 modCount++; | |
619 if (prev != null) { | |
620 prev.next = e.next; | |
621 } | |
622 else { | |
623 tab[index] = e.next; | |
624 } | |
625 | |
626 count--; | |
627 e.value = null; | |
628 return true; | |
629 } | |
630 } | |
631 return false; | |
632 } | |
633 | |
634 public int size() { | |
635 return count; | |
636 } | |
637 | |
638 public void clear() { | |
639 IntHashMap.this.clear(); | |
640 } | |
641 }; | |
642 } | |
643 | |
644 return entrySet; | |
645 } | |
646 | |
647 /** | |
648 * IntHashMap collision list entry. | |
649 */ | |
650 private static class Entry implements Map.Entry { | |
651 int key; | |
652 Object value; | |
653 Entry next; | |
654 private Integer objectKey; | |
655 | |
656 Entry(int key, Object value, Entry next) { | |
657 this.key = key; | |
658 this.value = value; | |
659 this.next = next; | |
660 } | |
661 | |
662 protected Object clone() { | |
663 return new Entry(key, value, | |
664 (next==null ? null : (Entry)next.clone())); | |
665 } | |
666 | |
667 // Map.Entry Ops | |
668 | |
669 public Object getKey() { | |
670 return (objectKey != null) ? objectKey : | |
671 (objectKey = new Integer(key)); | |
672 } | |
673 | |
674 public Object getValue() { | |
675 return value; | |
676 } | |
677 | |
678 public Object setValue(Object value) { | |
679 Object oldValue = this.value; | |
680 this.value = value; | |
681 return oldValue; | |
682 } | |
683 | |
684 public boolean equals(Object o) { | |
685 if (!(o instanceof Map.Entry)) { | |
686 return false; | |
687 } | |
688 Map.Entry e = (Map.Entry)o; | |
689 | |
690 return (getKey().equals(e.getKey())) && | |
691 (value==null ? e.getValue()==null : value.equals(e.getValue())); | |
692 } | |
693 | |
694 public int hashCode() { | |
695 return key ^ (value==null ? 0 : value.hashCode()); | |
696 } | |
697 | |
698 public String toString() { | |
699 return String.valueOf(key) + "=" + value; | |
700 } | |
701 } | |
702 | |
703 // Types of Iterators | |
704 private static final int KEYS = 0; | |
705 private static final int VALUES = 1; | |
706 private static final int ENTRIES = 2; | |
707 | |
708 private class IntHashIterator implements Iterator { | |
709 Entry[] table = IntHashMap.this.table; | |
710 int index = table.length; | |
711 Entry entry = null; | |
712 Entry lastReturned = null; | |
713 int type; | |
714 | |
715 /** | |
716 * The modCount value that the iterator believes that the backing | |
717 * List should have. If this expectation is violated, the iterator | |
718 * has detected concurrent modification. | |
719 */ | |
720 private int expectedModCount = modCount; | |
721 | |
722 IntHashIterator(int type) { | |
723 this.type = type; | |
724 } | |
725 | |
726 public boolean hasNext() { | |
727 while (entry == null && index > 0) { | |
728 entry = table[--index]; | |
729 } | |
730 | |
731 return entry != null; | |
732 } | |
733 | |
734 public Object next() { | |
735 if (modCount != expectedModCount) { | |
736 throw new ConcurrentModificationException(); | |
737 } | |
738 | |
739 while (entry == null && index > 0) { | |
740 entry = table[--index]; | |
741 } | |
742 | |
743 if (entry != null) { | |
744 Entry e = lastReturned = entry; | |
745 entry = e.next; | |
746 return type == KEYS ? e.getKey() : | |
747 (type == VALUES ? e.value : e); | |
748 } | |
749 throw new NoSuchElementException(); | |
750 } | |
751 | |
752 public void remove() { | |
753 if (lastReturned == null) { | |
754 throw new IllegalStateException(); | |
755 } | |
756 if (modCount != expectedModCount) { | |
757 throw new ConcurrentModificationException(); | |
758 } | |
759 | |
760 Entry[] tab = IntHashMap.this.table; | |
761 int index = (lastReturned.key & 0x7FFFFFFF) % tab.length; | |
762 | |
763 for (Entry e = tab[index], prev = null; e != null; | |
764 prev = e, e = e.next) { | |
765 if (e == lastReturned) { | |
766 modCount++; | |
767 expectedModCount++; | |
768 if (prev == null) { | |
769 tab[index] = e.next; | |
770 } | |
771 else { | |
772 prev.next = e.next; | |
773 } | |
774 count--; | |
775 lastReturned = null; | |
776 return; | |
777 } | |
778 } | |
779 throw new ConcurrentModificationException(); | |
780 } | |
781 } | |
782 | |
783 /** | |
784 * Save the state of the <tt>IntHashMap</tt> instance to a stream (i.e., | |
785 * serialize it). | |
786 * | |
787 * @serialData The <i>capacity</i> of the IntHashMap (the length of the | |
788 * bucket array) is emitted (int), followed by the | |
789 * <i>size</i> of the IntHashMap (the number of key-value | |
790 * mappings), followed by the key (Object) and value (Object) | |
791 * for each key-value mapping represented by the IntHashMap | |
792 * The key-value mappings are emitted in no particular order. | |
793 */ | |
794 private void writeObject(java.io.ObjectOutputStream s) | |
795 throws IOException | |
796 { | |
797 // Write out the threshold, loadfactor, and any hidden stuff | |
798 s.defaultWriteObject(); | |
799 | |
800 // Write out number of buckets | |
801 s.writeInt(table.length); | |
802 | |
803 // Write out size (number of Mappings) | |
804 s.writeInt(count); | |
805 | |
806 // Write out keys and values (alternating) | |
807 for (int index = table.length-1; index >= 0; index--) { | |
808 Entry entry = table[index]; | |
809 | |
810 while (entry != null) { | |
811 s.writeInt(entry.key); | |
812 s.writeObject(entry.value); | |
813 entry = entry.next; | |
814 } | |
815 } | |
816 } | |
817 | |
818 /** | |
819 * Reconstitute the <tt>IntHashMap</tt> instance from a stream (i.e., | |
820 * deserialize it). | |
821 */ | |
822 private void readObject(java.io.ObjectInputStream s) | |
823 throws IOException, ClassNotFoundException | |
824 { | |
825 // Read in the threshold, loadfactor, and any hidden stuff | |
826 s.defaultReadObject(); | |
827 | |
828 // Read in number of buckets and allocate the bucket array; | |
829 int numBuckets = s.readInt(); | |
830 table = new Entry[numBuckets]; | |
831 | |
832 // Read in size (number of Mappings) | |
833 int size = s.readInt(); | |
834 | |
835 // Read the keys and values, and put the mappings in the IntHashMap | |
836 for (int i=0; i<size; i++) { | |
837 int key = s.readInt(); | |
838 Object value = s.readObject(); | |
839 put(key, value); | |
840 } | |
841 } | |
842 | |
843 int capacity() { | |
844 return table.length; | |
845 } | |
846 | |
847 float loadFactor() { | |
848 return loadFactor; | |
849 } | |
850 } |