bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/OpenHashMap.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.felix.resolver.util;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;

/**
 * Based on fastutil Object2ObjectLinkedOpenHashMap
 */
public class OpenHashMap<K, V> implements Serializable, Cloneable, SortedMap<K, V> {

    private static final long serialVersionUID = 0L;
    protected transient Object[] key;
    protected transient Object[] value;
    protected transient int mask;
    protected transient boolean containsNullKey;
    protected transient int first;
    protected transient int last;
    protected transient long[] link;
    protected transient int n;
    protected transient int maxFill;
    protected int size;
    protected final float f;
    protected V defRetValue;

    protected transient Iterable<Map.Entry<K, V>> fast;
    protected transient SortedSet<Map.Entry<K, V>> entries;
    protected transient SortedSet<K> keys;
    protected transient Collection<V> values;

    public OpenHashMap(int expected, float f) {
        this.first = -1;
        this.last = -1;
        if (f > 0.0F && f <= 1.0F) {
            if (expected < 0) {
                throw new IllegalArgumentException("The expected number of elements must be nonnegative");
            } else {
                this.f = f;
                this.n = arraySize(expected, f);
                this.mask = this.n - 1;
                this.maxFill = maxFill(this.n, f);
                this.key = new Object[this.n + 1];
                this.value = new Object[this.n + 1];
                this.link = new long[this.n + 1];
            }
        } else {
            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
        }
    }

    public OpenHashMap(int expected) {
        this(expected, 0.75F);
    }

    public OpenHashMap() {
        this(16, 0.75F);
    }

    public OpenHashMap(Map<? extends K, ? extends V> m, float f) {
        this(m.size(), f);
        this.putAll(m);
    }

    public OpenHashMap(Map<? extends K, ? extends V> m) {
        this(m, 0.75F);
    }

    public OpenHashMap(K[] k, V[] v, float f) {
        this(k.length, f);
        if (k.length != v.length) {
            throw new IllegalArgumentException("The key array and the value array have different lengths (" + k.length + " and " + v.length + ")");
        } else {
            for (int i = 0; i < k.length; ++i) {
                this.put(k[i], v[i]);
            }

        }
    }

    public OpenHashMap(K[] k, V[] v) {
        this(k, v, 0.75F);
    }

    public void defaultReturnValue(V rv) {
        this.defRetValue = rv;
    }

    public V defaultReturnValue() {
        return this.defRetValue;
    }

    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } else if (!(o instanceof Map)) {
            return false;
        } else {
            Map<?, ?> m = (Map<?, ?>) o;
            int n = m.size();
            if (this.size() != n) {
                return false;
            }
            Iterator<? extends Entry<?, ?>> i = this.fast().iterator();
            while (n-- > 0) {
                Entry<?, ?> e = i.next();
                Object k = e.getKey();
                Object v = e.getValue();
                Object v2 = m.get(k);
                if (v == null) {
                    if (v2 != null) {
                        return false;
                    }
                } else if (!v.equals(v2)) {
                    return false;
                }
            }
            return true;
        }
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        Iterator<Map.Entry<K, V>> i = this.fast().iterator();
        int n = this.size();
        boolean first = true;
        s.append("{");

        while (n-- != 0) {
            if (first) {
                first = false;
            } else {
                s.append(", ");
            }

            Map.Entry<K, V> e = i.next();
            if (this == e.getKey()) {
                s.append("(this map)");
            } else {
                s.append(String.valueOf(e.getKey()));
            }

            s.append("=>");
            if (this == e.getValue()) {
                s.append("(this map)");
            } else {
                s.append(String.valueOf(e.getValue()));
            }
        }

        s.append("}");
        return s.toString();
    }

    private int realSize() {
        return this.containsNullKey ? this.size - 1 : this.size;
    }

    private void ensureCapacity(int capacity) {
        int needed = arraySize(capacity, this.f);
        if (needed > this.n) {
            this.rehash(needed);
        }

    }

    private void tryCapacity(long capacity) {
        int needed = (int) Math.min(1073741824L, Math.max(2L, nextPowerOfTwo((long) Math.ceil((double) ((float) capacity / this.f)))));
        if (needed > this.n) {
            this.rehash(needed);
        }

    }

    @SuppressWarnings("unchecked")
    private V removeEntry(int pos) {
        Object oldValue = this.value[pos];
        this.value[pos] = null;
        --this.size;
        this.fixPointers(pos);
        this.shiftKeys(pos);
        if (this.size < this.maxFill / 4 && this.n > 16) {
            this.rehash(this.n / 2);
        }

        return (V) oldValue;
    }

    @SuppressWarnings("unchecked")
    private V removeNullEntry() {
        this.containsNullKey = false;
        Object oldValue = this.value[this.n];
        this.value[this.n] = null;
        --this.size;
        this.fixPointers(this.n);
        if (this.size < this.maxFill / 4 && this.n > 16) {
            this.rehash(this.n / 2);
        }

        return (V) oldValue;
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        if ((double) this.f <= 0.5D) {
            this.ensureCapacity(m.size());
        } else {
            this.tryCapacity((long) (this.size() + m.size()));
        }

        int n = m.size();
        if (m instanceof OpenHashMap) {
            Iterator<? extends Map.Entry<? extends K, ? extends V>> i = ((OpenHashMap<? extends K, ? extends V>) m).fast().iterator();
            while (n-- != 0) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                this.put(e.getKey(), e.getValue());
            }
        } else {
            Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator();
            while (n-- != 0) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                this.put(e.getKey(), e.getValue());
            }
        }
    }

    private int insert(K k, V v) {
        int pos;
        if (k == null) {
            if (this.containsNullKey) {
                return this.n;
            }

            this.containsNullKey = true;
            pos = this.n;
        } else {
            Object[] key = this.key;
            Object curr;
            if ((curr = key[pos = mix(k.hashCode()) & this.mask]) != null) {
                if (curr.equals(k)) {
                    return pos;
                }

                while ((curr = key[pos = pos + 1 & this.mask]) != null) {
                    if (curr.equals(k)) {
                        return pos;
                    }
                }
            }

            key[pos] = k;
        }

        this.value[pos] = v;
        if (this.size == 0) {
            this.first = this.last = pos;
            this.link[pos] = -1L;
        } else {
            this.link[this.last] ^= (this.link[this.last] ^ (long) pos & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            this.link[pos] = ((long) this.last & 0xFFFFFFFFL) << 32 | 0xFFFFFFFFL;
            this.last = pos;
        }

        if (this.size++ >= this.maxFill) {
            this.rehash(arraySize(this.size + 1, this.f));
        }

        return -1;
    }

    @SuppressWarnings("unchecked")
    public V put(K k, V v) {
        int pos = this.insert(k, v);
        if (pos < 0) {
            return this.defRetValue;
        } else {
            Object oldValue = this.value[pos];
            this.value[pos] = v;
            return (V) oldValue;
        }
    }

    @SuppressWarnings("unchecked")
    public V getOrCompute(K k) {
        int pos;
        if (k == null) {
            if (this.containsNullKey) {
                return (V) this.value[this.n];
            }

            this.containsNullKey = true;
            pos = this.n;
        } else {
            Object[] key = this.key;
            Object curr;
            if ((curr = key[pos = mix(k.hashCode()) & this.mask]) != null) {
                if (curr.equals(k)) {
                    return (V) this.value[pos];
                }

                while ((curr = key[pos = pos + 1 & this.mask]) != null) {
                    if (curr.equals(k)) {
                        return (V) this.value[pos];
                    }
                }
            }

            key[pos] = k;
        }

        Object v;
        this.value[pos] = (v = compute(k));
        if (this.size == 0) {
            this.first = this.last = pos;
            this.link[pos] = -1L;
        } else {
            this.link[this.last] ^= (this.link[this.last] ^ (long) pos & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            this.link[pos] = ((long) this.last & 0xFFFFFFFFL) << 32 | 0xFFFFFFFFL;
            this.last = pos;
        }

        if (this.size++ >= this.maxFill) {
            this.rehash(arraySize(this.size + 1, this.f));
        }

        return (V) v;
    }

    protected V compute(K k) {
        throw new UnsupportedOperationException();
    }

    protected final void shiftKeys(int pos) {
        Object[] key = this.key;

        label32:
        while (true) {
            int last = pos;

            Object curr;
            for (pos = pos + 1 & this.mask; (curr = key[pos]) != null; pos = pos + 1 & this.mask) {
                int slot = mix(curr.hashCode()) & this.mask;
                if (last <= pos) {
                    if (last < slot && slot <= pos) {
                        continue;
                    }
                } else if (last < slot || slot <= pos) {
                    continue;
                }

                key[last] = curr;
                this.value[last] = this.value[pos];
                this.fixPointers(pos, last);
                continue label32;
            }

            key[last] = null;
            this.value[last] = null;
            return;
        }
    }

    public V remove(Object k) {
        if (k == null) {
            return this.containsNullKey ? this.removeNullEntry() : this.defRetValue;
        } else {
            Object[] key = this.key;
            Object curr;
            int pos;
            if ((curr = key[pos = mix(k.hashCode()) & this.mask]) == null) {
                return this.defRetValue;
            } else if (k.equals(curr)) {
                return this.removeEntry(pos);
            } else {
                while ((curr = key[pos = pos + 1 & this.mask]) != null) {
                    if (k.equals(curr)) {
                        return this.removeEntry(pos);
                    }
                }

                return this.defRetValue;
            }
        }
    }

    @SuppressWarnings("unchecked")
    public V removeFirst() {
        if (this.size == 0) {
            throw new NoSuchElementException();
        } else {
            int pos = this.first;
            this.first = (int) this.link[pos];
            if (0 <= this.first) {
                this.link[this.first] |= 0xFFFFFFFF00000000L;
            }

            --this.size;
            Object v = this.value[pos];
            if (pos == this.n) {
                this.containsNullKey = false;
                this.value[this.n] = null;
            } else {
                this.shiftKeys(pos);
            }

            if (this.size < this.maxFill / 4 && this.n > 16) {
                this.rehash(this.n / 2);
            }

            return (V) v;
        }
    }

    @SuppressWarnings("unchecked")
    public V removeLast() {
        if (this.size == 0) {
            throw new NoSuchElementException();
        } else {
            int pos = this.last;
            this.last = (int) (this.link[pos] >>> 32);
            if (0 <= this.last) {
                this.link[this.last] |= 0xFFFFFFFFL;
            }

            --this.size;
            Object v = this.value[pos];
            if (pos == this.n) {
                this.containsNullKey = false;
                this.value[this.n] = null;
            } else {
                this.shiftKeys(pos);
            }

            if (this.size < this.maxFill / 4 && this.n > 16) {
                this.rehash(this.n / 2);
            }

            return (V) v;
        }
    }

    @SuppressWarnings("unchecked")
    public V get(Object k) {
        if (k == null) {
            return containsNullKey ? (V) value[n] : defRetValue;
        }

        final Object[] key = this.key;
        Object curr;
        int pos;

        // The starting point
        if ((curr = key[pos = mix(k.hashCode()) & mask]) == null) {
            return defRetValue;
        }
        if (k.equals(curr)) {
            return (V) value[pos];
        }

        // There's always an usused entry
        while (true) {
            if ((curr = key[pos = (pos + 1) & mask]) == null) {
                return defRetValue;
            }
            if (k.equals(curr)) {
                return (V) value[pos];
            }
        }
    }

    public boolean containsKey(Object k) {
        if (k == null) {
            return this.containsNullKey;
        } else {
            Object[] key = this.key;
            Object curr;
            int pos;
            if ((curr = key[pos = mix(k.hashCode()) & this.mask]) == null) {
                return false;
            } else if (k.equals(curr)) {
                return true;
            } else {
                while ((curr = key[pos = pos + 1 & this.mask]) != null) {
                    if (k.equals(curr)) {
                        return true;
                    }
                }

                return false;
            }
        }
    }

    public boolean containsValue(Object v) {
        Object[] value = this.value;
        Object[] key = this.key;
        if (containsNullKey && (value[n] == null && v == null) || value[n].equals(v)) {
            return true;
        }
        for (int i = n; i-- != 0;) {
            if (!(key[i] == null) && (value[i] == null && v == null) || value[i].equals(v)) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        if (size != 0) {
            size = 0;
            containsNullKey = false;
            Arrays.fill(key, (Object) null);
            Arrays.fill(value, (Object) null);
            first = last = -1;
        }
    }

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

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

    protected void fixPointers(int i) {
        if (size == 0) {
            first = last = -1;
        } else if (first == i) {
            first = (int) link[i];
            if (0 <= first) {
                link[first] |= 0xFFFFFFFF00000000L;
            }
        } else if (last == i) {
            last = (int) (link[i] >>> 32);
            if (0 <= last) {
                link[last] |= 0xFFFFFFFFL;
            }
        } else {
            long linki = link[i];
            int prev = (int) (linki >>> 32);
            int next = (int) linki;
            link[prev] ^= (link[prev] ^ linki & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            link[next] ^= (link[next] ^ linki & 0xFFFFFFFF00000000L) & 0xFFFFFFFF00000000L;
        }
    }

    protected void fixPointers(int s, int d) {
        if (size == 1) {
            first = last = d;
            link[d] = -1L;
        } else if (first == s) {
            first = d;
            link[(int) link[s]] ^= (link[(int) link[s]] ^ ((long) d & 0xFFFFFFFFL) << 32) & 0xFFFFFFFF00000000L;
            link[d] = link[s];
        } else if (last == s) {
            last = d;
            link[(int) (link[s] >>> 32)] ^= (link[(int) (link[s] >>> 32)] ^ (long) d & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            link[d] = link[s];
        } else {
            long links = link[s];
            int prev = (int) (links >>> 32);
            int next = (int) links;
            link[prev] ^= (link[prev] ^ (long) d & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            link[next] ^= (link[next] ^ ((long) d & 0xFFFFFFFFL) << 32) & 0xFFFFFFFF00000000L;
            link[d] = links;
        }
    }

    @SuppressWarnings("unchecked")
    public K firstKey() {
        if (size == 0) {
            throw new NoSuchElementException();
        } else {
            return (K) key[first];
        }
    }

    @SuppressWarnings("unchecked")
    public K lastKey() {
        if (size == 0) {
            throw new NoSuchElementException();
        } else {
            return (K) key[last];
        }
    }

    public Comparator<? super K> comparator() {
        return null;
    }

    public SortedMap<K, V> tailMap(K from) {
        throw new UnsupportedOperationException();
    }

    public SortedMap<K, V> headMap(K to) {
        throw new UnsupportedOperationException();
    }

    public SortedMap<K, V> subMap(K from, K to) {
        throw new UnsupportedOperationException();
    }

    public Iterable<Map.Entry<K, V>> fast() {
        if (fast == null) {
            fast = new Iterable<Entry<K, V>>() {
                public Iterator<Entry<K, V>> iterator() {
                    return new FastEntryIterator();
                }
            };
        }

        return fast;
    }

    public SortedSet<Map.Entry<K, V>> entrySet() {
        if (entries == null) {
            entries = new MapEntrySet();
        }

        return this.entries;
    }

    public SortedSet<K> keySet() {
        if (keys == null) {
            keys = new KeySet();
        }

        return keys;
    }

    public Collection<V> values() {
        if (values == null) {
            values = new AbstractObjectCollection<V>() {
                public Iterator<V> iterator() {
                    return new ValueIterator();
                }

                public int size() {
                    return size;
                }

                public boolean contains(Object v) {
                    return containsValue(v);
                }

                public void clear() {
                    OpenHashMap.this.clear();
                }
            };
        }

        return values;
    }

    /** Rehashes the map, making the table as small as possible.
     *
     * <P>This method rehashes the table to the smallest size satisfying the
     * load factor. It can be used when the set will not be changed anymore, so
     * to optimize access speed and size.
     *
     * <P>If the table size is already the minimum possible, this method
     * does nothing.
     *
     * @return true if there was enough memory to trim the map.
     * @see #trim(int)
     */
    public boolean trim() {
        int l = arraySize(size, f);
        if (l >= n) {
            return true;
        } else {
            try {
                rehash(l);
                return true;
            } catch (OutOfMemoryError cantDoIt) {
                return false;
            }
        }
    }

    /** Rehashes this map if the table is too large.
     *
     * <P>Let <var>N</var> be the smallest table size that can hold
     * <code>max(n,{@link #size()})</code> entries, still satisfying the load factor. If the current
     * table size is smaller than or equal to <var>N</var>, this method does
     * nothing. Otherwise, it rehashes this map in a table of size
     * <var>N</var>.
     *
     * <P>This method is useful when reusing maps.  {@linkplain #clear() Clearing a
     * map} leaves the table size untouched. If you are reusing a map
     * many times, you can call this method with a typical
     * size to avoid keeping around a very large table just
     * because of a few large transient maps.
     *
     * @param n the threshold for the trimming.
     * @return true if there was enough memory to trim the map.
     * @see #trim()
     */
    public boolean trim(int n) {
        int l = nextPowerOfTwo((int) Math.ceil((double) ((float) n / f)));
        if (n <= l) {
            return true;
        } else {
            try {
                rehash(l);
                return true;
            } catch (OutOfMemoryError cantDoIt) {
                return false;
            }
        }
    }

    /** Rehashes the map.
     *
     * <P>This method implements the basic rehashing strategy, and may be
     * overriden by subclasses implementing different rehashing strategies (e.g.,
     * disk-based rehashing). However, you should not override this method
     * unless you understand the internal workings of this class.
     *
     * @param newN the new size
     */
    protected void rehash(int newN) {
        Object[] key = this.key;
        Object[] value = this.value;

        int mask = newN - 1;
        Object[] newKey = new Object[newN + 1];
        Object[] newValue = new Object[newN + 1];

        int i = first, prev = -1, newPrev = -1, t, pos;
        final long[] link = this.link;
        final long[] newLink = new long[newN + 1];
        first = -1;

        for (int j = size; j-- != 0;) {
            if (key[i] == null) {
                pos = newN;
            } else {
                pos = mix(key[i].hashCode()) & mask;
                while (newKey[pos] != null) {
                    pos = ( pos + 1 ) & mask;
                }
                newKey[pos] = key[i];
            }

            newValue[pos] = value[i];

            if (prev != -1) {
                newLink[newPrev] ^= (newLink[newPrev] ^ (long) pos & 0xFFFFFFFFL) & 0xFFFFFFFFL;
                newLink[pos] ^= (newLink[pos] ^ ((long) newPrev & 0xFFFFFFFFL) << 32) & 0xFFFFFFFF00000000L;
                newPrev = pos;
            } else {
                newPrev = first = pos;
                newLink[pos] = -1L;
            }

            t = i;
            i = (int) link[i];
            prev = t;
        }

        this.link = newLink;
        this.last = newPrev;
        if (newPrev != -1) {
            newLink[newPrev] |= -1 & 0xFFFFFFFFL;
        }

        n = newN;
        this.mask = mask;
        maxFill = maxFill(n, f);
        this.key = newKey;
        this.value = newValue;
    }

    @SuppressWarnings("unchecked")
    public OpenHashMap<K, V> clone() {
        OpenHashMap<K, V> c;
        try {
            c = (OpenHashMap<K, V>) super.clone();
        } catch (CloneNotSupportedException cantHappen) {
            throw new InternalError();
        }

        c.fast = null;
        c.keys = null;
        c.values = null;
        c.entries = null;
        c.containsNullKey = containsNullKey;
        c.key = key.clone();
        c.value = value.clone();
        c.link = link.clone();
        return c;
    }

    public int hashCode() {
        int h = 0;
        for( int j = realSize(), i = 0, t = 0; j-- != 0; ) {
            while (key[i] == null) {
                ++i;
            }

            if (this != key[i]) {
                t = key[i].hashCode();
            }

            if (this != value[i]) {
                t ^= value[i] == null ? 0 : value[i].hashCode();
            }

            h += t;
            i++;
        }

        if (containsNullKey) {
            h += value[n] == null ? 0 : value[n].hashCode();
        }

        return h;
    }

    private void writeObject(ObjectOutputStream s) throws IOException {
        Object[] key = this.key;
        Object[] value = this.value;
        OpenHashMap<K, V>.MapIterator i = new MapIterator();
        s.defaultWriteObject();
        int j = this.size;

        while (j-- != 0) {
            int e = i.nextEntry();
            s.writeObject(key[e]);
            s.writeObject(value[e]);
        }

    }

    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
        s.defaultReadObject();
        this.n = arraySize(this.size, this.f);
        this.maxFill = maxFill(this.n, this.f);
        this.mask = this.n - 1;
        Object[] key = this.key = new Object[this.n + 1];
        Object[] value = this.value = new Object[this.n + 1];
        long[] link = this.link = new long[this.n + 1];
        int prev = -1;
        this.first = this.last = -1;
        int i = this.size;

        while (i-- != 0) {
            Object k = s.readObject();
            Object v = s.readObject();
            int pos;
            if (k == null) {
                pos = this.n;
                this.containsNullKey = true;
            } else {
                for (pos = mix(k.hashCode()) & this.mask; key[pos] != null; pos = pos + 1 & this.mask) {
                    ;
                }

                key[pos] = k;
            }

            value[pos] = v;
            if (this.first != -1) {
                link[prev] ^= (link[prev] ^ (long) pos & 0xFFFFFFFFL) & 0xFFFFFFFFL;
                link[pos] ^= (link[pos] ^ ((long) prev & 0xFFFFFFFFL) << 32) & 0xFFFFFFFF00000000L;
                prev = pos;
            } else {
                prev = this.first = pos;
                link[pos] |= 0xFFFFFFFF00000000L;
            }
        }

        this.last = prev;
        if (prev != -1) {
            link[prev] |= 0xFFFFFFFFL;
        }

    }

    private final class ValueIterator extends MapIterator implements Iterator<V> {
        public ValueIterator() {
            super();
        }

        @SuppressWarnings("unchecked")
        public V next() {
            return (V) value[this.nextEntry()];
        }
    }

    private final class KeySet extends AbstractObjectSet<K> implements SortedSet<K> {
        private KeySet() {
        }

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

        public int size() {
            return size;
        }

        public boolean contains(Object k) {
            return containsKey(k);
        }

        public boolean remove(Object k) {
            int oldSize = size;
            OpenHashMap.this.remove(k);
            return size != oldSize;
        }

        public void clear() {
            OpenHashMap.this.clear();
        }

        @SuppressWarnings("unchecked")
        public K first() {
            if (size == 0) {
                throw new NoSuchElementException();
            } else {
                return (K) key[first];
            }
        }

        @SuppressWarnings("unchecked")
        public K last() {
            if (size == 0) {
                throw new NoSuchElementException();
            } else {
                return (K) key[last];
            }
        }

        public Comparator<? super K> comparator() {
            return null;
        }

        public final SortedSet<K> tailSet(K from) {
            throw new UnsupportedOperationException();
        }

        public final SortedSet<K> headSet(K to) {
            throw new UnsupportedOperationException();
        }

        public final SortedSet<K> subSet(K from, K to) {
            throw new UnsupportedOperationException();
        }
    }

    private final class KeyIterator extends MapIterator implements Iterator<K> {
        public KeyIterator() {
            super();
        }

        @SuppressWarnings("unchecked")
        public K next() {
            return (K) key[this.nextEntry()];
        }
    }

    private final class MapEntrySet extends AbstractObjectSet<Entry<K, V>> implements SortedSet<Entry<K, V>> {
        private MapEntrySet() {
        }

        public EntryIterator iterator() {
            return new EntryIterator();
        }

        public Comparator<? super Entry<K, V>> comparator() {
            return null;
        }

        public SortedSet<Entry<K, V>> subSet(Entry<K, V> fromElement, Entry<K, V> toElement) {
            throw new UnsupportedOperationException();
        }

        public SortedSet<Entry<K, V>> headSet(Entry<K, V> toElement) {
            throw new UnsupportedOperationException();
        }

        public SortedSet<Entry<K, V>> tailSet(Entry<K, V> fromElement) {
            throw new UnsupportedOperationException();
        }

        public Entry<K, V> first() {
            if (size == 0) {
                throw new NoSuchElementException();
            } else {
                return new MapEntry(first);
            }
        }

        public Entry<K, V> last() {
            if (size == 0) {
                throw new NoSuchElementException();
            } else {
                return new MapEntry(last);
            }
        }

        public boolean contains(Object o) {
            if (!(o instanceof java.util.Map.Entry)) {
                return false;
            } else {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                Object k = e.getKey();
                if (k == null) {
                    if (containsNullKey) {
                        if (value[n] == null) {
                            if (e.getValue() != null) {
                                return false;
                            }
                        } else if (!value[n].equals(e.getValue())) {
                            return false;
                        }

                        return true;
                    }

                    return false;
                } else {
                    Object[] key = OpenHashMap.this.key;
                    Object curr;
                    int pos;
                    if ((curr = key[pos = mix(k.hashCode()) & mask]) == null) {
                        return false;
                    } else if (k.equals(curr)) {
                        return value[pos] == null ? e.getValue() == null : value[pos].equals(e.getValue());
                    } else {
                        while ((curr = key[pos = pos + 1 & mask]) != null) {
                            if (k.equals(curr)) {
                                return value[pos] == null ? e.getValue() == null : value[pos].equals(e.getValue());
                            }
                        }

                        return false;
                    }
                }
            }
        }

        public boolean remove(Object o) {
            if (!(o instanceof java.util.Map.Entry)) {
                return false;
            } else {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                Object k = e.getKey();
                Object v = e.getValue();
                if (k == null) {
                    if (containsNullKey) {
                        if (value[n] == null) {
                            if (v != null) {
                                return false;
                            }
                        } else if (!value[n].equals(v)) {
                            return false;
                        }

                        removeNullEntry();
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    Object[] key = OpenHashMap.this.key;
                    Object curr;
                    int pos;
                    if ((curr = key[pos = mix(k.hashCode()) & mask]) == null) {
                        return false;
                    } else if (curr.equals(k)) {
                        if (value[pos] == null) {
                            if (v != null) {
                                return false;
                            }
                        } else if (!value[pos].equals(v)) {
                            return false;
                        }

                        removeEntry(pos);
                        return true;
                    } else {
                        while (true) {
                            do {
                                if ((curr = key[pos = pos + 1 & mask]) == null) {
                                    return false;
                                }
                            } while (!curr.equals(k));

                            if (value[pos] == null) {
                                if (v == null) {
                                    break;
                                }
                            } else if (value[pos].equals(v)) {
                                break;
                            }
                        }

                        removeEntry(pos);
                        return true;
                    }
                }
            }
        }

        public int size() {
            return size;
        }

        public void clear() {
            OpenHashMap.this.clear();
        }
    }

    private class FastEntryIterator extends MapIterator implements Iterator<Entry<K, V>> {
        final MapEntry entry;

        public FastEntryIterator() {
            super();
            this.entry = new MapEntry();
        }

        public MapEntry next() {
            this.entry.index = this.nextEntry();
            return this.entry;
        }
    }

    private class EntryIterator extends MapIterator implements Iterator<Entry<K, V>> {
        private MapEntry entry;

        public EntryIterator() {
            super();
        }

        public MapEntry next() {
            return this.entry = new MapEntry(this.nextEntry());
        }

        public void remove() {
            super.remove();
            this.entry.index = -1;
        }
    }

    public static abstract class AbstractObjectSet<K> extends AbstractObjectCollection<K> implements Cloneable {
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            } else if (!(o instanceof Set)) {
                return false;
            } else {
                Set<?> s = (Set<?>) o;
                return s.size() == this.size() && this.containsAll(s);
            }
        }

        public int hashCode() {
            int h = 0;
            int n = this.size();

            Object k;
            for (Iterator<K> i = this.iterator(); n-- != 0; h += k == null ? 0 : k.hashCode()) {
                k = i.next();
            }

            return h;
        }
    }

    private class MapIterator {
        /**
         * The entry that will be returned by the next call to {@link java.util.ListIterator#previous()} (or <code>null</code> if no previous entry exists).
         */
        int prev = -1;
        /**
         * The entry that will be returned by the next call to {@link java.util.ListIterator#next()} (or <code>null</code> if no next entry exists).
         */
        int next = -1;
        /**
         * The last entry that was returned (or -1 if we did not iterate or used {@link java.util.Iterator#remove()}).
         */
        int curr = -1;
        /**
         * The current index (in the sense of a {@link java.util.ListIterator}). Note that this value is not meaningful when this iterator has been created using the nonempty constructor.
         */
        int index = -1;

        private MapIterator() {
            this.next = first;
            this.index = 0;
        }

        public boolean hasNext() {
            return this.next != -1;
        }

        private void ensureIndexKnown() {
            if (index < 0) {
                if (prev == -1) {
                    index = 0;
                } else if (next == -1) {
                    index = size;
                } else {
                    int pos = first;
                    for (index = 1; pos != prev; ++index) {
                        pos = (int) link[pos];
                    }
                }
            }
        }

        public int nextEntry() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            } else {
                curr = next;
                next = (int) link[curr];
                prev = curr;
                if (index >= 0) {
                    ++index;
                }
                return curr;
            }
        }

        public void remove() {
            this.ensureIndexKnown();
            if (curr == -1) throw new IllegalStateException();

            if (curr == prev) {
                    /* If the last operation was a next(), we are removing an entry that preceeds
                     * the current index, and thus we must decrement it. */
                index--;
                prev = (int) (link[curr] >>> 32);
            } else {
                next = (int) link[curr];
            }

            size--;
            /* Now we manually fix the pointers. Because of our knowledge of next
             * and prev, this is going to be faster than calling fixPointers(). */
            if (prev == -1) {
                first = next;
            } else {
                link[prev] ^= (link[prev] ^ (long) next & 0xFFFFFFFFL) & 0xFFFFFFFFL;
            }
            if (next == -1) {
                last = prev;
            } else {
                link[next] ^= (link[next] ^ ((long) prev & 0xFFFFFFFFL) << 32) & 0xFFFFFFFF00000000L;
            }

            int last, slot, pos = curr;
            curr = -1;

            if (pos == n) {
                containsNullKey = false;
                value[n] = null;
            } else {
                Object curr;
                Object[] key = OpenHashMap.this.key;
                // We have to horribly duplicate the shiftKeys() code because we need to update next/prev.
                for (; ; ) {
                    pos = ((last = pos) + 1) & mask;
                    for (; ; ) {
                        if ((curr = key[pos]) == null) {
                            key[last] = null;
                            value[last] = null;
                            return;
                        }
                        slot = mix(curr.hashCode()) & mask;
                        if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) break;
                        pos = (pos + 1) & mask;
                    }
                    key[last] = curr;
                    value[last] = value[pos];
                    if (next == pos) next = last;
                    if (prev == pos) prev = last;
                    fixPointers(pos, last);
                }
            }
        }
    }

    final class MapEntry implements Entry<K, V> {
        int index;

        MapEntry(int index) {
            this.index = index;
        }

        MapEntry() {
        }

        @SuppressWarnings("unchecked")
        public K getKey() {
            return (K) key[this.index];
        }

        @SuppressWarnings("unchecked")
        public V getValue() {
            return (V) value[this.index];
        }

        @SuppressWarnings("unchecked")
        public V setValue(V v) {
            Object oldValue = value[this.index];
            value[this.index] = v;
            return (V) oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Entry)) {
                return false;
            } else {
                Entry<?, ?> e = (Entry<?, ?>) o;
                if (key[this.index] == null) {
                    if (e.getKey() != null) {
                        return false;
                    }
                } else if (!key[this.index].equals(e.getKey())) {
                    return false;
                }

                if (value[this.index] == null) {
                    if (e.getValue() != null) {
                        return false;
                    }
                } else if (!value[this.index].equals(e.getValue())) {
                    return false;
                }

                return true;
            }
        }

        public int hashCode() {
            return (key[this.index] == null ? 0 :
                    key[this.index].hashCode()) ^ (value[this.index] == null ? 0 :
                    value[this.index].hashCode());
        }

        public String toString() {
            return key[this.index] + "=>" + value[this.index];
        }
    }


    public static abstract class AbstractObjectCollection<K> extends AbstractCollection<K> {
        protected AbstractObjectCollection() {
        }

        public Object[] toArray() {
            Object[] a = new Object[this.size()];
            unwrap(this.iterator(), a);
            return a;
        }

        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            if (a.length < this.size()) {
                a = (T[]) Array.newInstance(a.getClass().getComponentType(), this.size());
            }
            unwrap(this.iterator(), a);
            return a;
        }

        public boolean addAll(Collection<? extends K> c) {
            boolean retVal = false;
            Iterator<? extends K> i = c.iterator();
            int n = c.size();

            while (n-- != 0) {
                if (this.add(i.next())) {
                    retVal = true;
                }
            }

            return retVal;
        }

        public boolean add(K k) {
            throw new UnsupportedOperationException();
        }

        public boolean containsAll(Collection<?> c) {
            int n = c.size();
            Iterator<?> i = c.iterator();

            do {
                if (n-- == 0) {
                    return true;
                }
            } while (this.contains(i.next()));

            return false;
        }

        public boolean retainAll(Collection<?> c) {
            boolean retVal = false;
            int n = this.size();
            Iterator<K> i = this.iterator();

            while (n-- != 0) {
                if (!c.contains(i.next())) {
                    i.remove();
                    retVal = true;
                }
            }

            return retVal;
        }

        public boolean removeAll(Collection<?> c) {
            boolean retVal = false;
            int n = c.size();
            Iterator<?> i = c.iterator();

            while (n-- != 0) {
                if (this.remove(i.next())) {
                    retVal = true;
                }
            }

            return retVal;
        }

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

        public String toString() {
            StringBuilder s = new StringBuilder();
            Iterator<K> i = this.iterator();
            int n = this.size();
            boolean first = true;
            s.append("{");

            while (n-- != 0) {
                if (first) {
                    first = false;
                } else {
                    s.append(", ");
                }

                Object k = i.next();
                if (this == k) {
                    s.append("(this collection)");
                } else {
                    s.append(String.valueOf(k));
                }
            }

            s.append("}");
            return s.toString();
        }
    }

    private static int arraySize(int expected, float f) {
        long s = Math.max(2L, nextPowerOfTwo((long) Math.ceil((double) ((float) expected / f))));
        if (s > 0x40000000L) {
            throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")");
        } else {
            return (int) s;
        }
    }

    private static int maxFill(int n, float f) {
        return Math.min((int) Math.ceil((double) ((float) n * f)), n - 1);
    }

    private static int nextPowerOfTwo(int x) {
        if (x == 0) {
            return 1;
        } else {
            --x;
            x |= x >> 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            return (x | x >> 16) + 1;
        }
    }

    private static long nextPowerOfTwo(long x) {
        if (x == 0L) {
            return 1L;
        } else {
            --x;
            x |= x >> 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            x |= x >> 16;
            return (x | x >> 32) + 1L;
        }
    }

    private static int mix(int x) {
        int h = x * -1640531527;
        return h ^ h >>> 16;
    }

    private static <K> int unwrap(Iterator<? extends K> i, K[] array, int offset, int max) {
        if (max < 0) {
            throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative");
        } else if (offset >= 0 && offset + max <= array.length) {
            int j;
            for (j = max; j-- != 0 && i.hasNext(); array[offset++] = i.next()) {
                ;
            }

            return max - j - 1;
        } else {
            throw new IllegalArgumentException();
        }
    }

    private static <K> int unwrap(Iterator<? extends K> i, K[] array) {
        return unwrap(i, array, 0, array.length);
    }
}