gistfile1.java

package org.bukkit.craftbukkit.util;

import org.apache.commons.lang.Validate;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

public class LongObjectRobinHoodHashMap<V> implements Cloneable, Serializable {
    static final long serialVersionUID = 2841597710770573462L;
    private static final int LOAD_FACTOR_PERCENT = 90;

    private transient int[] hashes;
    private transient long[] keys;
    private transient V[] values;
    private transient int modCount;
    private transient int size;
    private transient int resizeThreshold;
    private transient int mask;

    public LongObjectRobinHoodHashMap() {
        this(256);
    }

    public LongObjectRobinHoodHashMap(int initialCapacity) {
        Validate.isTrue(initialCapacity > 0);

        initialCapacity = Integer.highestOneBit(initialCapacity - 1) << 1; // Power of 2
        allocate(initialCapacity);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean containsKey(long key) {
        int index = lookup(key);
        return index != -1;
    }

    public boolean containsValue(Object value) {
        for (int i = 0; i < keys.length; i++) {
            if (hashes[i] != 0) {
                if ((values[i] == null && value == null) || (values[i] != null && values[i].equals(value))) {
                    return true;
                }
            }
        }

        return false;
    }

    public V get(long key) {
        int index = lookup(key);
        return index != -1 ? values[index] : null;
    }

    public V put(long key, V value) {
        if (++size >= resizeThreshold) {
            resize();
        }

        modCount++;
        return insert(hash(key), key, value);
    }

    public V remove(long key) {
        int hash = hash(key);
        int index = lookup(key);

        if (index == -1) {
            return null;
        }

        V old_value = values[index];
        size--;
        modCount++;

        // Loop from removed entry position swapping entries back one until we
        // find an empty entry or one with a probe distance of zero
        for (int i = 1; i < keys.length; i++) {
            int index_previous = (index + i - 1) & mask;
            int index_swap = (index + i) & mask;

            if (hashes[index_swap] == 0) {
                hashes[index_previous] = 0;
                values[index_previous] = null;
                break;
            }

            int distance = probeDistance(hashes[index_swap], index_swap);
            if (distance == 0) {
                hashes[index_previous] = 0;
                values[index_previous] = null;
                break;
            }

            hashes[index_previous] = hashes[index_swap];
            keys[index_previous] = keys[index_swap];
            values[index_previous] = values[index_swap];
        }

        return old_value;
    }

    public void putAll(Map<? extends Long, ? extends V> map) {
        for (Map.Entry entry : map.entrySet()) {
            put((Long) entry.getKey(), (V) entry.getValue());
        }
    }

    public void putAll(LongObjectRobinHoodHashMap<? extends V> map) {
        for (int i = 0; i < map.keys.length; i++) {
            if (map.hashes[i] != 0) {
                put(map.keys[i], map.values[i]);
            }
        }
    }

    public void clear() {
        if (size == 0) {
            return;
        }

        size = 0;
        modCount++;
        allocate(keys.length);
    }

    public Set<Long> keySet() {
        return new KeySet();
    }

    public Collection<V> values() {
        return new ValueCollection();
    }

    /**
     * Returns a Set of Entry objects for the HashMap. This is not how the internal
     * implementation is laid out so this constructs the entire Set when called. For
     * this reason it should be avoided if at all possible.
     *
     * @return Set of Entry objects
     * @deprecated
     */
    @Deprecated
    public Set<Map.Entry<Long, V>> entrySet() {
        HashSet<Map.Entry<Long, V>> set = new HashSet<Map.Entry<Long, V>>();
        for (long key : keySet()) {
            set.add(new Entry(key, get(key)));
        }

        return set;
    }

    public Object clone() throws CloneNotSupportedException {
        LongObjectRobinHoodHashMap clone = new LongObjectRobinHoodHashMap(size);

        // Iterate through the data normally to do a safe clone
        for (long key : keySet()) {
            final V value = get(key);
            clone.put(key, value);
        }

        return clone;
    }

    public boolean equals(Object other) {
        if (other instanceof Map) {
            Map<Long, V> that = (Map<Long, V>) other;
            if (this.size() != that.size()) {
                return false;
            }

            for (int i = 0; i < keys.length; i++) {
                if (hashes[i] != 0) {
                    V value = that.get(keys[i]);
                    if (values[i] == null && value == null) {
                        continue;
                    }

                    if (values[i] != null && values[i].equals(value)) {
                        continue;
                    }

                    return false;
                }
            }

            return true;
        } else if (other instanceof LongObjectRobinHoodHashMap) {
            LongObjectRobinHoodHashMap<V> that = (LongObjectRobinHoodHashMap<V>) other;
            if (this.size() != that.size()) {
                return false;
            }

            for (int i = 0; i < keys.length; i++) {
                if (hashes[i] != 0) {
                    V value = that.get(keys[i]);
                    if (values[i] == null && value == null) {
                        continue;
                    }

                    if (values[i] != null && values[i].equals(value)) {
                        continue;
                    }

                    return false;
                }
            }

            return true;
        }

        return false;
    }

    public int hashCode() {
        int hash = 0;
        for (int i = 0; i < keys.length; i++) {
            if (hashes[i] != 0) {
                hash += hashes[i] ^ (values[i] == null ? 0 : values[i].hashCode());
            }
        }

        return hash;
    }

    public String toString() {
        final StringBuilder builder = new StringBuilder("{");
        for (int i = 0; i < keys.length; i++) {
            if (hashes[i] != 0) {
                if (builder.length() != 1) {
                    builder.append(", ");
                }

                builder.append(keys[i]);
                builder.append("=");
                builder.append(values[i]);
            }
        }
        builder.append("}");
        return builder.toString();
    }

    private void writeObject(ObjectOutputStream outputStream) throws IOException {
        outputStream.defaultWriteObject();

        outputStream.writeInt(size);
        for (int i = 0; i < keys.length; i++) {
            if (hashes[i] != 0) {
                outputStream.writeLong(keys[i]);
                outputStream.writeObject(values[i]);
            }
        }
    }

    private void readObject(ObjectInputStream inputStream) throws ClassNotFoundException, IOException {
        inputStream.defaultReadObject();
        int size = inputStream.readInt();
        allocate(Integer.highestOneBit(size - 1) << 1); // Power of 2

        for (int i = 0; i < size; i++) {
            long key = inputStream.readLong();
            V value = (V) inputStream.readObject();
            put(key, value);
        }
    }

    private int hash(long key) {
        long hash = key;
        hash ^= hash >>> 33;
        hash *= 0xff51afd7ed558ccdL;
        hash ^= hash >>> 33;
        hash *= 0xc4ceb9fe1a85ec53L;
        hash ^= hash >>> 33;
        // Ensure we never return zero
        hash |= hash == 0 ? 1 : 0;
        return (int) hash;
    }

    private V insert(int hash, long key, V value) {
        int index = desiredIndex(hash);
        int distance = 0;

        while (true) {
            if (hashes[index] == 0 || keys[index] == key) {
                V old_value = values[index];
                hashes[index] = hash;
                keys[index] = key;
                values[index] = value;
                return old_value;
            }

            // If the existing entry has a smaller probe distance than us, swap
            int existingDistance = probeDistance(hashes[index], index);
            if (existingDistance < distance) {
                int temp = hashes[index];
                hashes[index] = hash;
                hash = temp;

                long temp2 = keys[index];
                keys[index] = key;
                key = temp2;

                V temp3 = values[index];
                values[index] = value;
                value = temp3;

                distance = existingDistance;
            }

            index = (index + 1) & mask;
            distance++;
        }
    }

    private int lookup(long key) {
        int hash = hash(key);
        int index = desiredIndex(hash);
        int distance = 0;

        while(true) {
            if (hashes[index] == 0) {
                return -1;
            } else if (distance > probeDistance(hashes[index], index)) {
                return -1;
            } else if (hashes[index] == hash && keys[index] == key) {
                return index;
            }

            index = (index + 1) & mask;
            distance++;
        }
    }

    private void allocate(int capacity) {
        hashes = new int[capacity];
        keys = new long[capacity];
        values = (V[]) new Object[capacity];

        resizeThreshold = (capacity * LOAD_FACTOR_PERCENT) / 100;
        mask = capacity - 1;
    }

    private void resize() {
        int[] old_hashes = hashes;
        long[] old_keys = keys;
        V[] old_values = values;
        allocate(keys.length * 2);

        for (int i = 0; i < keys.length; ++i) {
            if (old_hashes[i] != 0) {
                insert(old_hashes[i], old_keys[i], old_values[i]);
            }
        }
    }

    private int desiredIndex(int hash) {
        return hash & mask;
    }

    private int probeDistance(int hash, int index) {
        return (index + keys.length - desiredIndex(hash)) & mask;
    }

    private class KeySet extends AbstractSet<Long> {
        public void clear() {
            LongObjectRobinHoodHashMap.this.clear();
        }

        public int size() {
            return LongObjectRobinHoodHashMap.this.size();
        }

        public boolean contains(Object key) {
            return key instanceof Long && LongObjectRobinHoodHashMap.this.containsKey((Long) key);
        }

        public boolean remove(Object key) {
            return key instanceof Long && LongObjectRobinHoodHashMap.this.remove((Long) key) != null;
        }

        public Iterator<Long> iterator() {
            return new KeyIterator();
        }
    }

    private class ValueCollection extends AbstractCollection<V> {
        public void clear() {
            LongObjectRobinHoodHashMap.this.clear();
        }

        public int size() {
            return LongObjectRobinHoodHashMap.this.size();
        }

        public boolean contains(Object value) {
            return LongObjectRobinHoodHashMap.this.containsValue(value);
        }

        public Iterator<V> iterator() {
            return new ValueIterator();
        }
    }

    private class KeyIterator implements Iterator<Long> {
        private int count;
        private int index;
        private int expectedModCount;
        private long lastReturned;

        KeyIterator() {
            expectedModCount = LongObjectRobinHoodHashMap.this.modCount;
        }

        public boolean hasNext() {
            return count < LongObjectRobinHoodHashMap.this.size();
        }

        public void remove() {
            if (LongObjectRobinHoodHashMap.this.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (count == 0) {
                throw new IllegalStateException();
            }

            if (LongObjectRobinHoodHashMap.this.remove(lastReturned) != null) {
                count--;
            }
            expectedModCount = LongObjectRobinHoodHashMap.this.modCount;
        }

        public Long next() {
            if (LongObjectRobinHoodHashMap.this.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            count++;

            for (; index < keys.length; index++) {
                if (hashes[index] != 0) {
                    lastReturned = keys[index];
                    index++;
                    return lastReturned;
                }
            }

            throw new NoSuchElementException();
        }
    }

    private class ValueIterator implements Iterator<V> {
        private int count;
        private int index;
        private int expectedModCount;
        private long lastReturned;

        ValueIterator() {
            expectedModCount = LongObjectRobinHoodHashMap.this.modCount;
        }

        public boolean hasNext() {
            return count < LongObjectRobinHoodHashMap.this.size();
        }

        public void remove() {
            if (LongObjectRobinHoodHashMap.this.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (count == 0) {
                throw new IllegalStateException();
            }

            if (LongObjectRobinHoodHashMap.this.remove(lastReturned) != null) {
                count--;
            }
            expectedModCount = LongObjectRobinHoodHashMap.this.modCount;
        }

        public V next() {
            if (LongObjectRobinHoodHashMap.this.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            count++;

            for (; index < keys.length; index++) {
                if (hashes[index] != 0) {
                    V value = values[index];
                    lastReturned = keys[index];
                    index++;
                    return value;
                }
            }

            throw new NoSuchElementException();
        }
    }

    private class Entry implements Map.Entry<Long, V> {
        private final Long key;
        private V value;

        Entry(long k, V v) {
            key = k;
            value = v;
        }

        public Long getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V v) {
            V old = value;
            value = v;
            put(key, v);
            return old;
        }
    }
}