    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    }