001 package org.maltparser.core.helper;
002
003 /*
004 * Copyright 2009 Google Inc.
005 *
006 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
007 * use this file except in compliance with the License. You may obtain a copy of
008 * the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
014 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
015 * License for the specific language governing permissions and limitations under
016 * the License.
017 */
018
019 import java.io.IOException;
020 import java.io.ObjectInputStream;
021 import java.io.ObjectOutputStream;
022 import java.io.Serializable;
023 import java.util.AbstractCollection;
024 import java.util.AbstractSet;
025 import java.util.Collection;
026 import java.util.Iterator;
027 import java.util.Map;
028 import java.util.NoSuchElementException;
029 import java.util.Set;
030
031 /**
032 * A memory-efficient hash map.
033 *
034 * @param <K> the key type
035 * @param <V> the value type
036 */
037 public class HashMap<K, V> implements Map<K, V>, Serializable {
038 private static final long serialVersionUID = 7526471155622776147L;
039 /**
040 * In the interest of memory-savings, we start with the smallest feasible
041 * power-of-two table size that can hold three items without rehashing. If we
042 * started with a size of 2, we'd have to expand as soon as the second item
043 * was added.
044 */
045 private static final int INITIAL_TABLE_SIZE = 4;
046
047 private class EntryIterator implements Iterator<Entry<K, V>> {
048 private int index = 0;
049 private int last = -1;
050
051 {
052 advanceToItem();
053 }
054
055 public boolean hasNext() {
056 return index < keys.length;
057 }
058
059 public Entry<K, V> next() {
060 if (!hasNext()) {
061 throw new NoSuchElementException();
062 }
063 last = index;
064 Entry<K, V> toReturn = new HashEntry(index++);
065 advanceToItem();
066 return toReturn;
067 }
068
069 public void remove() {
070 if (last < 0) {
071 throw new IllegalStateException();
072 }
073 internalRemove(last);
074 if (keys[last] != null) {
075 index = last;
076 }
077 last = -1;
078 }
079
080 private void advanceToItem() {
081 for (; index < keys.length; ++index) {
082 if (keys[index] != null) {
083 return;
084 }
085 }
086 }
087 }
088
089 private class EntrySet extends AbstractSet<Entry<K, V>> {
090 @Override
091 public boolean add(Entry<K, V> entry) {
092 boolean result = !HashMap.this.containsKey(entry.getKey());
093 HashMap.this.put(entry.getKey(), entry.getValue());
094 return result;
095 }
096
097 @Override
098 public boolean addAll(Collection<? extends Entry<K, V>> c) {
099 HashMap.this.ensureSizeFor(size() + c.size());
100 return super.addAll(c);
101 }
102
103 @Override
104 public void clear() {
105 HashMap.this.clear();
106 }
107
108 @Override
109 @SuppressWarnings("unchecked")
110 public boolean contains(Object o) {
111 if (!(o instanceof Entry)) {
112 return false;
113 }
114 Entry<K, V> entry = (Entry<K, V>) o;
115 V value = HashMap.this.get(entry.getKey());
116 return HashMap.this.valueEquals(value, entry.getValue());
117 }
118
119 @Override
120 public int hashCode() {
121 return HashMap.this.hashCode();
122 }
123
124 @Override
125 public Iterator<java.util.Map.Entry<K, V>> iterator() {
126 return new EntryIterator();
127 }
128
129 @Override
130 @SuppressWarnings("unchecked")
131 public boolean remove(Object o) {
132 if (!(o instanceof Entry)) {
133 return false;
134 }
135 Entry<K, V> entry = (Entry<K, V>) o;
136 int index = findKey(entry.getKey());
137 if (index >= 0 && valueEquals(values[index], entry.getValue())) {
138 internalRemove(index);
139 return true;
140 }
141 return false;
142 }
143
144 @Override
145 public boolean removeAll(Collection<?> c) {
146 boolean didRemove = false;
147 for (Object o : c) {
148 didRemove |= remove(o);
149 }
150 return didRemove;
151 }
152
153 @Override
154 public int size() {
155 return HashMap.this.size;
156 }
157 }
158
159 private class HashEntry implements Entry<K, V> {
160 private final int index;
161
162 public HashEntry(int index) {
163 this.index = index;
164 }
165
166 @Override
167 @SuppressWarnings("unchecked")
168 public boolean equals(Object o) {
169 if (!(o instanceof Entry)) {
170 return false;
171 }
172 Entry<K, V> entry = (Entry<K, V>) o;
173 return keyEquals(getKey(), entry.getKey())
174 && valueEquals(getValue(), entry.getValue());
175 }
176
177 @SuppressWarnings("unchecked")
178 public K getKey() {
179 return (K) unmaskNullKey(keys[index]);
180 }
181
182 @SuppressWarnings("unchecked")
183 public V getValue() {
184 return (V) values[index];
185 }
186
187 @Override
188 public int hashCode() {
189 return keyHashCode(getKey()) ^ valueHashCode(getValue());
190 }
191
192 @SuppressWarnings("unchecked")
193 public V setValue(V value) {
194 V previous = (V) values[index];
195 values[index] = value;
196 return previous;
197 }
198
199 @Override
200 public String toString() {
201 return getKey() + "=" + getValue();
202 }
203 }
204
205 private class KeyIterator implements Iterator<K> {
206 private int index = 0;
207 private int last = -1;
208
209 {
210 advanceToItem();
211 }
212
213 public boolean hasNext() {
214 return index < keys.length;
215 }
216
217 @SuppressWarnings("unchecked")
218 public K next() {
219 if (!hasNext()) {
220 throw new NoSuchElementException();
221 }
222 last = index;
223 Object toReturn = unmaskNullKey(keys[index++]);
224 advanceToItem();
225 return (K) toReturn;
226 }
227
228 public void remove() {
229 if (last < 0) {
230 throw new IllegalStateException();
231 }
232 internalRemove(last);
233 if (keys[last] != null) {
234 index = last;
235 }
236 last = -1;
237 }
238
239 private void advanceToItem() {
240 for (; index < keys.length; ++index) {
241 if (keys[index] != null) {
242 return;
243 }
244 }
245 }
246 }
247
248 private class KeySet extends AbstractSet<K> {
249 @Override
250 public void clear() {
251 HashMap.this.clear();
252 }
253
254 @Override
255 public boolean contains(Object o) {
256 return HashMap.this.containsKey(o);
257 }
258
259 @Override
260 public int hashCode() {
261 int result = 0;
262 for (int i = 0; i < keys.length; ++i) {
263 Object key = keys[i];
264 if (key != null) {
265 result += keyHashCode(unmaskNullKey(key));
266 }
267 }
268 return result;
269 }
270
271 @Override
272 public Iterator<K> iterator() {
273 return new KeyIterator();
274 }
275
276 @Override
277 public boolean remove(Object o) {
278 int index = findKey(o);
279 if (index >= 0) {
280 internalRemove(index);
281 return true;
282 }
283 return false;
284 }
285
286 @Override
287 public boolean removeAll(Collection<?> c) {
288 boolean didRemove = false;
289 for (Object o : c) {
290 didRemove |= remove(o);
291 }
292 return didRemove;
293 }
294
295 @Override
296 public int size() {
297 return HashMap.this.size;
298 }
299 }
300
301 private class ValueIterator implements Iterator<V> {
302 private int index = 0;
303 private int last = -1;
304
305 {
306 advanceToItem();
307 }
308
309 public boolean hasNext() {
310 return index < keys.length;
311 }
312
313 @SuppressWarnings("unchecked")
314 public V next() {
315 if (!hasNext()) {
316 throw new NoSuchElementException();
317 }
318 last = index;
319 Object toReturn = values[index++];
320 advanceToItem();
321 return (V) toReturn;
322 }
323
324 public void remove() {
325 if (last < 0) {
326 throw new IllegalStateException();
327 }
328 internalRemove(last);
329 if (keys[last] != null) {
330 index = last;
331 }
332 last = -1;
333 }
334
335 private void advanceToItem() {
336 for (; index < keys.length; ++index) {
337 if (keys[index] != null) {
338 return;
339 }
340 }
341 }
342 }
343
344 private class Values extends AbstractCollection<V> {
345 @Override
346 public void clear() {
347 HashMap.this.clear();
348 }
349
350 @Override
351 public boolean contains(Object o) {
352 return HashMap.this.containsValue(o);
353 }
354
355 @Override
356 public int hashCode() {
357 int result = 0;
358 for (int i = 0; i < keys.length; ++i) {
359 if (keys[i] != null) {
360 result += valueHashCode(values[i]);
361 }
362 }
363 return result;
364 }
365
366 @Override
367 public Iterator<V> iterator() {
368 return new ValueIterator();
369 }
370
371 @Override
372 public boolean remove(Object o) {
373 if (o == null) {
374 for (int i = 0; i < keys.length; ++i) {
375 if (keys[i] != null && values[i] == null) {
376 internalRemove(i);
377 return true;
378 }
379 }
380 } else {
381 for (int i = 0; i < keys.length; ++i) {
382 if (valueEquals(values[i], o)) {
383 internalRemove(i);
384 return true;
385 }
386 }
387 }
388 return false;
389 }
390
391 @Override
392 public boolean removeAll(Collection<?> c) {
393 boolean didRemove = false;
394 for (Object o : c) {
395 didRemove |= remove(o);
396 }
397 return didRemove;
398 }
399
400 @Override
401 public int size() {
402 return HashMap.this.size;
403 }
404 }
405
406 private static final Object NULL_KEY = new Serializable() {
407 Object readResolve() {
408 return NULL_KEY;
409 }
410 };
411
412 static Object maskNullKey(Object k) {
413 return (k == null) ? NULL_KEY : k;
414 }
415
416 static Object unmaskNullKey(Object k) {
417 return (k == NULL_KEY) ? null : k;
418 }
419
420 /**
421 * Backing store for all the keys; transient due to custom serialization.
422 * Default access to avoid synthetic accessors from inner classes.
423 */
424 transient Object[] keys;
425
426 /**
427 * Number of pairs in this set; transient due to custom serialization. Default
428 * access to avoid synthetic accessors from inner classes.
429 */
430 transient int size = 0;
431
432 /**
433 * Backing store for all the values; transient due to custom serialization.
434 * Default access to avoid synthetic accessors from inner classes.
435 */
436 transient Object[] values;
437
438 public HashMap() {
439 initTable(INITIAL_TABLE_SIZE);
440 }
441
442 public HashMap(Map<? extends K, ? extends V> m) {
443 int newCapacity = INITIAL_TABLE_SIZE;
444 int expectedSize = m.size();
445 while (newCapacity * 3 < expectedSize * 4) {
446 newCapacity <<= 1;
447 }
448
449 initTable(newCapacity);
450 internalPutAll(m);
451 }
452
453 public void clear() {
454 initTable(INITIAL_TABLE_SIZE);
455 size = 0;
456 }
457
458 public boolean containsKey(Object key) {
459 return findKey(key) >= 0;
460 }
461
462 public boolean containsValue(Object value) {
463 if (value == null) {
464 for (int i = 0; i < keys.length; ++i) {
465 if (keys[i] != null && values[i] == null) {
466 return true;
467 }
468 }
469 } else {
470 for (Object existing : values) {
471 if (valueEquals(existing, value)) {
472 return true;
473 }
474 }
475 }
476 return false;
477 }
478
479 public Set<Entry<K, V>> entrySet() {
480 return new EntrySet();
481 }
482
483 @Override
484 @SuppressWarnings("unchecked")
485 public boolean equals(Object o) {
486 if (!(o instanceof Map)) {
487 return false;
488 }
489 Map<K, V> other = (Map<K, V>) o;
490 return entrySet().equals(other.entrySet());
491 }
492
493 @SuppressWarnings("unchecked")
494 public V get(Object key) {
495 int index = findKey(key);
496 return (index < 0) ? null : (V) values[index];
497 }
498
499 @Override
500 public int hashCode() {
501 int result = 0;
502 for (int i = 0; i < keys.length; ++i) {
503 Object key = keys[i];
504 if (key != null) {
505 result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
506 }
507 }
508 return result;
509 }
510
511 public boolean isEmpty() {
512 return size == 0;
513 }
514
515 public Set<K> keySet() {
516 return new KeySet();
517 }
518
519 @SuppressWarnings("unchecked")
520 public V put(K key, V value) {
521 ensureSizeFor(size + 1);
522 int index = findKeyOrEmpty(key);
523 if (keys[index] == null) {
524 ++size;
525 keys[index] = maskNullKey(key);
526 values[index] = value;
527 return null;
528 } else {
529 Object previousValue = values[index];
530 values[index] = value;
531 return (V) previousValue;
532 }
533 }
534
535 public void putAll(Map<? extends K, ? extends V> m) {
536 ensureSizeFor(size + m.size());
537 internalPutAll(m);
538 }
539
540 @SuppressWarnings("unchecked")
541 public V remove(Object key) {
542 int index = findKey(key);
543 if (index < 0) {
544 return null;
545 }
546 Object previousValue = values[index];
547 internalRemove(index);
548 return (V) previousValue;
549 }
550
551 public int size() {
552 return size;
553 }
554
555 @Override
556 public String toString() {
557 if (size == 0) {
558 return "{}";
559 }
560 StringBuilder buf = new StringBuilder(32 * size());
561 buf.append('{');
562
563 boolean needComma = false;
564 for (int i = 0; i < keys.length; ++i) {
565 Object key = keys[i];
566 if (key != null) {
567 if (needComma) {
568 buf.append(',').append(' ');
569 }
570 key = unmaskNullKey(key);
571 Object value = values[i];
572 buf.append(key == this ? "(this Map)" : key).append('=').append(
573 value == this ? "(this Map)" : value);
574 needComma = true;
575 }
576 }
577 buf.append('}');
578 return buf.toString();
579 }
580
581 public Collection<V> values() {
582 return new Values();
583 }
584
585 /**
586 * Adapted from org.apache.commons.collections.map.AbstractHashedMap.
587 */
588 @SuppressWarnings("unchecked")
589 protected void doReadObject(ObjectInputStream in) throws IOException,
590 ClassNotFoundException {
591 int capacity = in.readInt();
592 initTable(capacity);
593 int items = in.readInt();
594 for (int i = 0; i < items; i++) {
595 Object key = in.readObject();
596 Object value = in.readObject();
597 put((K) key, (V) value);
598 }
599 }
600
601 /**
602 * Adapted from org.apache.commons.collections.map.AbstractHashedMap.
603 */
604 protected void doWriteObject(ObjectOutputStream out) throws IOException {
605 out.writeInt(keys.length);
606 out.writeInt(size);
607 for (int i = 0; i < keys.length; ++i) {
608 Object key = keys[i];
609 if (key != null) {
610 out.writeObject(unmaskNullKey(key));
611 out.writeObject(values[i]);
612 }
613 }
614 }
615
616 /**
617 * Returns whether two keys are equal for the purposes of this set.
618 */
619 protected boolean keyEquals(Object a, Object b) {
620 return (a == null) ? (b == null) : a.equals(b);
621 }
622
623 /**
624 * Returns the hashCode for a key.
625 */
626 protected int keyHashCode(Object k) {
627 return (k == null) ? 0 : k.hashCode();
628 }
629
630 /**
631 * Returns whether two values are equal for the purposes of this set.
632 */
633 protected boolean valueEquals(Object a, Object b) {
634 return (a == null) ? (b == null) : a.equals(b);
635 }
636
637 /**
638 * Returns the hashCode for a value.
639 */
640 protected int valueHashCode(Object v) {
641 return (v == null) ? 0 : v.hashCode();
642 }
643
644 /**
645 * Ensures the map is large enough to contain the specified number of entries.
646 * Default access to avoid synthetic accessors from inner classes.
647 */
648 void ensureSizeFor(int expectedSize) {
649 if (keys.length * 3 >= expectedSize * 4) {
650 return;
651 }
652
653 int newCapacity = keys.length << 1;
654 while (newCapacity * 3 < expectedSize * 4) {
655 newCapacity <<= 1;
656 }
657
658 Object[] oldKeys = keys;
659 Object[] oldValues = values;
660 initTable(newCapacity);
661 for (int i = 0; i < oldKeys.length; ++i) {
662 Object k = oldKeys[i];
663 if (k != null) {
664 int newIndex = getKeyIndex(unmaskNullKey(k));
665 while (keys[newIndex] != null) {
666 if (++newIndex == keys.length) {
667 newIndex = 0;
668 }
669 }
670 keys[newIndex] = k;
671 values[newIndex] = oldValues[i];
672 }
673 }
674 }
675
676 /**
677 * Returns the index in the key table at which a particular key resides, or -1
678 * if the key is not in the table. Default access to avoid synthetic accessors
679 * from inner classes.
680 */
681 int findKey(Object k) {
682 int index = getKeyIndex(k);
683 while (true) {
684 Object existing = keys[index];
685 if (existing == null) {
686 return -1;
687 }
688 if (keyEquals(k, unmaskNullKey(existing))) {
689 return index;
690 }
691 if (++index == keys.length) {
692 index = 0;
693 }
694 }
695 }
696
697 /**
698 * Returns the index in the key table at which a particular key resides, or
699 * the index of an empty slot in the table where this key should be inserted
700 * if it is not already in the table. Default access to avoid synthetic
701 * accessors from inner classes.
702 */
703 int findKeyOrEmpty(Object k) {
704 int index = getKeyIndex(k);
705 while (true) {
706 Object existing = keys[index];
707 if (existing == null) {
708 return index;
709 }
710 if (keyEquals(k, unmaskNullKey(existing))) {
711 return index;
712 }
713 if (++index == keys.length) {
714 index = 0;
715 }
716 }
717 }
718
719 /**
720 * Removes the entry at the specified index, and performs internal management
721 * to make sure we don't wind up with a hole in the table. Default access to
722 * avoid synthetic accessors from inner classes.
723 */
724 void internalRemove(int index) {
725 keys[index] = null;
726 values[index] = null;
727 --size;
728 plugHole(index);
729 }
730
731 private int getKeyIndex(Object k) {
732 int h = keyHashCode(k);
733 // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions.
734 h += ~(h << 9);
735 h ^= (h >>> 14);
736 h += (h << 4);
737 h ^= (h >>> 10);
738 // Power of two trick.
739 return h & (keys.length - 1);
740 }
741
742 private void initTable(int capacity) {
743 keys = new Object[capacity];
744 values = new Object[capacity];
745 }
746
747 private void internalPutAll(Map<? extends K, ? extends V> m) {
748 for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
749 K key = entry.getKey();
750 V value = entry.getValue();
751 int index = findKeyOrEmpty(key);
752 if (keys[index] == null) {
753 ++size;
754 keys[index] = maskNullKey(key);
755 values[index] = value;
756 } else {
757 values[index] = value;
758 }
759 }
760 }
761
762 /**
763 * Tricky, we left a hole in the map, which we have to fill. The only way to
764 * do this is to search forwards through the map shuffling back values that
765 * match this index until we hit a null.
766 */
767 private void plugHole(int hole) {
768 int index = hole + 1;
769 if (index == keys.length) {
770 index = 0;
771 }
772 while (keys[index] != null) {
773 int targetIndex = getKeyIndex(unmaskNullKey(keys[index]));
774 if (hole < index) {
775 /*
776 * "Normal" case, the index is past the hole and the "bad range" is from
777 * hole (exclusive) to index (inclusive).
778 */
779 if (!(hole < targetIndex && targetIndex <= index)) {
780 // Plug it!
781 keys[hole] = keys[index];
782 values[hole] = values[index];
783 keys[index] = null;
784 values[index] = null;
785 hole = index;
786 }
787 } else {
788 /*
789 * "Wrapped" case, the index is before the hole (we've wrapped) and the
790 * "good range" is from index (exclusive) to hole (inclusive).
791 */
792 if (index < targetIndex && targetIndex <= hole) {
793 // Plug it!
794 keys[hole] = keys[index];
795 values[hole] = values[index];
796 keys[index] = null;
797 values[index] = null;
798 hole = index;
799 }
800 }
801 if (++index == keys.length) {
802 index = 0;
803 }
804 }
805 }
806
807 private void readObject(ObjectInputStream in) throws IOException,
808 ClassNotFoundException {
809 in.defaultReadObject();
810 doReadObject(in);
811 }
812
813 private void writeObject(ObjectOutputStream out) throws IOException {
814 out.defaultWriteObject();
815 doWriteObject(out);
816 }
817 }