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    }