/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.collections.ints;

import java.util.*;
import java.lang.reflect.*;
import java.io.IOException;
import java.io.*;
import edu.emory.mathcs.util.collections.*;

/**
 * Hash map with int keys. It uses open addressing with quadratic residue
 * search to avoid clustering. No additional memory per entry is needed, there
 * is therefore no memory allocation on put() unless rehashing is required.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public class IntRadkeHashMap implements IntMap, Cloneable, java.io.Serializable {

    transient int[] keys;
    transient Object[] values;
    transient int size;
    transient int fill;
    int treshold;

    final int minKey, maxKey;
    final float loadFactor;
    final float resizeTreshold;
    transient KeySet keySet;
    transient EntrySet entrySet;
    transient Values valueCollection;

    // value == NULL := mapping set for value null
    private final static Object NULL    = new Object();
    // value == REMOVED or value == null := no mapping
    private final static Object REMOVED = new Object();

    public IntRadkeHashMap() {
        this(19);
    }

    public IntRadkeHashMap(int minInitialCapacity) {
        this(minInitialCapacity, 0.75f, 0.3f);
    }

    public IntRadkeHashMap(int minInitialCapacity, int minKey, int maxKey) {
        this(minInitialCapacity, minKey, maxKey, 0.75f, 0.3f);
    }

    public IntRadkeHashMap(int minInitialCapacity, float loadFactor, float resizeTreshold) {
        this(minInitialCapacity, Integer.MIN_VALUE, Integer.MAX_VALUE,
             loadFactor, resizeTreshold);
    }

    public IntRadkeHashMap(int minInitialCapacity, int minKey, int maxKey,
                            float loadFactor, float resizeTreshold) {
        int initialCapacity = RadkeHashMap.radkeAtLeast(minInitialCapacity);
        if (minKey > maxKey) throw new IllegalArgumentException();
        this.minKey = minKey;
        this.maxKey = maxKey;
        if (loadFactor <= 0 || loadFactor > 1) {
            throw new IllegalArgumentException("Load factor must be betweeen 0 and 1");
        }
        if (resizeTreshold <= 0 || resizeTreshold > 1) {
            throw new IllegalArgumentException("Fill treshold must be betweeen 0 and 1");
        }
        keys = new int[initialCapacity];
        values = new Object[initialCapacity];
        size = 0;
        fill = 0;
        this.loadFactor = loadFactor;
        this.resizeTreshold = resizeTreshold;
        treshold = (int)(loadFactor * initialCapacity);
    }

    public IntRadkeHashMap(IntMap m) {
        this(Math.max((int) (m.size() / 0.75) + 1, 19), m.keySet().min(), m.keySet().max());
        putAll(m);
    }

    public Object put(int key, Object value) {

        if (key < minKey || key > maxKey) return null;
        int hsize = keys.length;
        int start = phash(key) % hsize;
        int refill = -1;
        value = maskNull(value);

        // initial guess

        Object oldval = values[start];
        if (oldval == null) {
            keys[start] = key;
            values[start] = value;
            size++;
            fill++;
            if (fill >= treshold) rehash();
            return null;
        }
        else if (oldval == REMOVED) {
            refill = start;
        }
        else if (keys[start] == key) {
            values[start] = value;
            return oldval;
        }

        int p;

        // collision handling

        p = start+1;
        if (p >= hsize) p -= hsize;
        oldval = values[p];
        if (oldval == null) {
            if (refill >= 0) {
                keys[refill] = key;
                values[refill] = value;
                size++;
                return null;
            }
            else {
                keys[p] = key;
                values[p] = value;
                size++;
                fill++;
                if (fill >= treshold) rehash();
                return null;
            }
        }
        else if (oldval == REMOVED) {
            if (refill < 0) refill = p;
        }
        else if (keys[p] == key) {
            // replace
            values[p] = value;
            return oldval;
        }

        p = start-1;
        if (p < 0) p += hsize;
        oldval = values[p];
        if (oldval == null) {
            if (refill >= 0) {
                keys[refill] = key;
                values[refill] = value;
                size++;
                return null;
            }
            else {
                keys[p] = key;
                values[p] = value;
                size++;
                fill++;
                if (fill >= treshold) rehash();
                return null;
            }
        }
        else if (oldval == REMOVED) {
            if (refill < 0) refill = p;
        }
        else if (keys[p] == key) {
            // replace
            values[p] = value;
            return oldval;
        }

        // loop for the rest
        int j=5;
        int pu=start+4, pd=start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;

            oldval = values[pu];
            if (oldval == null) {
                if (refill >= 0) {
                    keys[refill] = key;
                    values[refill] = value;
                    size++;
                    return null;
                }
                else {
                    keys[pu] = key;
                    values[pu] = value;
                    size++;
                    fill++;
                    if (fill >= treshold) rehash();
                    return null;
                }
            }
            else if (oldval == REMOVED) {
                if (refill < 0) refill = pu;
            }
            else if (keys[pu] == key) {
                // replace
                values[pu] = value;
                return oldval;
            }

            if (pd < 0) pd += hsize;

            oldval = values[pd];
            if (oldval == null) {
                if (refill >= 0) {
                    keys[refill] = key;
                    values[refill] = value;
                    size++;
                    return null;
                }
                else {
                    keys[pd] = key;
                    values[pd] = value;
                    size++;
                    fill++;
                    if (fill >= treshold) rehash();
                    return null;
                }
            }
            else if (oldval == REMOVED) {
                if (refill < 0) refill = pd;
            }
            else if (keys[pd] == key) {
                // replace
                values[pd] = value;
                return oldval;
            }

            pu+=j;
            pd-=j;
            j+=2;
        }
        throw new RuntimeException("hash map is full");
    }

    public Object get(int key) {
//        int p = find(key);
//        return (p >= 0 ? unmaskNull(values[p]) : null);

        if (key < minKey || key > maxKey) return null;
        int hsize = keys.length;
        int start = phash(key) % hsize;

        Object oldval = values[start];
        if (oldval == null) return null;
        else if (oldval != REMOVED && keys[start] == key) return unmaskNull(oldval);

        int p;
        p = start+1; if (p >= hsize) p -= hsize;
        oldval = values[p];
        if (oldval == null) return null;
        else if (oldval != REMOVED && keys[p] == key) return unmaskNull(oldval);

        p = start-1; if (p < 0) p += hsize;
        oldval = values[p];
        if (oldval == null) return null;
        else if (oldval != REMOVED && keys[p] == key) return unmaskNull(oldval);

        int j=5;
        int pu= start+4;
        int pd = start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;
            oldval = values[pu];
            if (oldval == null) return null;
            else if (oldval != REMOVED && keys[pu] == key) return unmaskNull(oldval);

            if (pd < 0) pd += hsize;
            oldval = values[pd];
            if (oldval == null) return null;
            else if (oldval != REMOVED && keys[pd] == key) return unmaskNull(oldval);

            pu += j;
            pd -= j;
            j+=2;
        }
        return null;
    }

    public boolean containsKey(int key) {
        return find(key) >= 0;
    }

    private boolean containsMapping(int key, Object value) {
        int p = find(key);
        if (p < 0) return false;
        return equals(value, values[p]);
    }

    public Object remove(int key) {
        int p = find(key);
        if (p < 0) return null;
        Object removed = values[p];
        values[p] = REMOVED;
        size--;
        return unmaskNull(removed);
    }

    private boolean removeMapping(int key, Object value) {
        int p = find(key);
        if (p < 0) return false;
        Object val = unmaskNull(values[p]);
        if (!equals(value, val)) return false;
        values[p] = REMOVED;
        size--;
        return true;
    }

    // find index of a mapping for a given key, or -1 if not found
    private int find(int key) {
        if (key < minKey || key > maxKey) return -1;
        int hsize = keys.length;
        int start = phash(key) % hsize;

        Object oldval = values[start];
        if (oldval == null) return -1;
        else if (oldval != REMOVED && keys[start] == key) return start;

        int p;
        p = start+1; if (p >= hsize) p -= hsize;
        oldval = values[p];
        if (oldval == null) return -1;
        else if (oldval != REMOVED && keys[p] == key) return p;

        p = start-1; if (p < 0) p += hsize;
        oldval = values[p];
        if (oldval == null) return -1;
        else if (oldval != REMOVED && keys[p] == key) return p;

        int j=5;
        int pu= start+4;
        int pd = start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;
            oldval = values[pu];
            if (oldval == null) return -1;
            else if (oldval != REMOVED && keys[pu] == key) return pu;

            if (pd < 0) pd += hsize;
            oldval = values[pd];
            if (oldval == null) return -1;
            else if (oldval != REMOVED && keys[pd] == key) return pd;

            pu += j;
            pd -= j;
            j+=2;
        }
        return -1;
    }

    public boolean containsValue(Object val) {
        int p = findVal(val);
        return (p >= 0);
    }

    private int findVal(Object value) {
        value = maskNull(value);
        for (int i=0; i<values.length; i++) {
            if (equals(values[i], value)) return i;
        }
        return -1;
    }

    private void rehash() {
        if (size >= fill*resizeTreshold) {
            rehash(RadkeHashMap.radkeAtLeast(keys.length+1));
        }
        else {
            // only rehash (to remove "REMOVED"), but do not
            // resize
            rehash(keys.length);
        }
    }

    private void rehash(int newcapacity) {
        int[] oldkeys = this.keys;
        Object[] oldvals = this.values;
        this.keys = new int[newcapacity];
        this.values = new Object[newcapacity];
        size = 0;
        fill = 0;
        treshold = (int)(loadFactor * newcapacity);
        for (int i=0; i<oldkeys.length; i++) {
            if (oldvals[i] == null || oldvals[i] == REMOVED) continue;
            // theoretically should unmask null, but this way is faster and
            // works as well: NULLs are not re-masked, and the user cannot
            // pass them here anyway
            put(oldkeys[i], oldvals[i]);
        }
    }

    public void clear() {
        Arrays.fill(values, null);
        size = 0;
        fill = 0;
    }

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

    public int size() {
        return size;
    }

    public int size64() {  
        return size;        
    }                       
                            
    public void putAll(IntMap map) {
        for (Iterator itr = map.entrySet().iterator(); itr.hasNext();) {
            Entry entry = (Entry)itr.next();
            put(entry.getKey(), entry.getValue());
        }
    }

    public IntSet keySet() {
        if (keySet == null) {
            keySet = new KeySet();
        }
        return keySet;
    }

    public Set entrySet() {
        if (entrySet == null) {
            entrySet = new EntrySet();
        }
        return entrySet;
    }

    public Collection values() {
        if (valueCollection == null) valueCollection = new Values();
        return valueCollection;
    }

    public boolean equals(Object other) {
        if (other == this) return true;

        if (!(other instanceof IntMap)) return false;
        IntMap that = (IntMap)other;
        if (that.size() != size()) return false;
        for (int i=0; i<keys.length; i++) {
            Object val = values[i];
            if (val == null || val == REMOVED) continue;
            Object val2 = that.get(keys[i]);
            if (val2 == null || !val.equals(val2)) return false;
        }

        return true;
    }

    public int hashCode() {
        int hash = 0;
        for (int i=0; i<keys.length; i++) {
            Object val = values[i];
            if (val == null || val == REMOVED) continue;
            hash += (hash(keys[i]) ^ (val == NULL ? 0 : val.hashCode()));
        }
        return hash;
    }

    public Object clone() {
        IntRadkeHashMap result;
        try {
            result = (IntRadkeHashMap)super.clone();
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException(e);
        }

        result.keys = new int[keys.length];
        result.values = new Object[values.length];
        result.keySet = null;
        result.entrySet = null;
        result.valueCollection = null;
        result.fill = 0;
        result.size = 0;
        result.putAll(this);
        return result;
    }

    private class HashIterator {
        int curr;
        int next;
        HashIterator() {
            this.curr = 0;
            this.next = 0;
            findNext();
        }
        public boolean hasNext() {
            return next < keys.length;
        }
        protected void goNext() {
            if (next >= keys.length) {
                throw new NoSuchElementException();
            }
            curr = next++;
            findNext();
        }
        private void findNext() {
            while (next < keys.length && (values[next] == null || values[next] == REMOVED)) {
                next++;
            }
        }
        public void remove() {
            if (values[curr] != REMOVED) {
                values[curr] = REMOVED;
                size--;
            }
        }
    }

    private class KeyIterator extends HashIterator implements IntIterator {
        public int next() {
            goNext();
            return keys[curr];
        }
    }

    private class Entry implements IntMap.Entry {
        final int p;
        Entry(int p) {
            this.p = p;
        }
        public int getKey() {
            if (values[p] == null || values[p] == REMOVED) {
                throw new IllegalStateException("Mapping was removed");
            }
            return keys[p];
        }
        public Object getValue() {
            if (values[p] == null || values[p] == REMOVED) {
                throw new IllegalStateException("Mapping was removed");
            }
            return unmaskNull(values[p]);
        }
        public Object setValue(Object value) {
            Object old = values[p];
            if (old == null || old == REMOVED) {
                throw new IllegalStateException("Mapping was removed");
            }
            values[p] = maskNull(value);
            return unmaskNull(old);
        }
        public boolean equals(Object other) {
            if (!(other instanceof IntMap.Entry)) return false;
            IntMap.Entry that = (IntMap.Entry)other;
            if (this.getKey() != that.getKey()) return false;
            if (!IntRadkeHashMap.equals(getValue(), that.getValue())) return false;
            return true;
        }
        public int hashCode() {
            Object val = values[p];
            if (val == REMOVED || val == null) return 0;
            int key = keys[p];
            return hash(key) ^ (val == NULL ? 0 : val.hashCode());
        }
        public String toString() {
            Object val = values[p];
            if (val == REMOVED || val == null) return "REMOVED";
            return keys[p] + "=" + unmaskNull(val);
        }
    }

    private class EntryIterator extends HashIterator implements Iterator {
        public Object next() {
            goNext();
            return new Entry(curr);
        }
    }

    private class ValueIterator extends HashIterator implements Iterator {
        public Object next() {
            goNext();
            return unmaskNull(values[curr]);
        }
    }

    private class KeySet extends AbstractIntSet implements IntSet {
        public int min() {
            return minKey;
        }
        public int max() {
            return maxKey;
        }
        public boolean add(int e) {
            throw new UnsupportedOperationException();
        }
        public boolean addAll(IntCollection c) {
            throw new UnsupportedOperationException();
        }
        public void clear() {
            IntRadkeHashMap.this.clear();
        }
        public int size64() {                     
            return IntRadkeHashMap.this.size64(); 
        }                                          
        public boolean isEmpty() {
            return IntRadkeHashMap.this.isEmpty();
        }
        public boolean contains(int e) {
            return IntRadkeHashMap.this.containsKey(e);
        }
        public boolean containsAll(IntCollection c) {
            return IntRadkeHashMap.this.keySetContainsAll(c);
        }
        public boolean remove(int e) {
            return IntRadkeHashMap.this.keySetRemoveMapping(e);
        }
        public boolean removeAll(IntCollection c) {
            return IntRadkeHashMap.this.keySetRemoveAll(c);
        }
        public boolean retainAll(IntCollection c) {
            return IntRadkeHashMap.this.keySetRetainAll(c);
        }
        public int[] toArray() {
            return IntRadkeHashMap.this.keySetToArray();
        }
        public int[] toArray(int[] a) {
            return IntRadkeHashMap.this.keySetToArray(a);
        }
        public IntIterator iterator() {
            return new KeyIterator();
        }
    }

    private class EntrySet implements Set {
        public boolean add(Object o) {
            throw new UnsupportedOperationException();
        }
        public boolean addAll(Collection c) {
            throw new UnsupportedOperationException();
        }
        public void clear() {
            IntRadkeHashMap.this.clear();
        }
        public int size() {
            return IntRadkeHashMap.this.size();
        }
        public boolean isEmpty() {
            return IntRadkeHashMap.this.isEmpty();
        }
        public boolean contains(Object o) {
            return IntRadkeHashMap.this.entrySetContainsEntry(o);
        }
        public boolean containsAll(Collection c) {
            return IntRadkeHashMap.this.entrySetContainsAll(c);
        }
        public boolean remove(Object o) {
            return IntRadkeHashMap.this.entrySetRemoveMapping(o);
        }
        public boolean removeAll(Collection c) {
            return IntRadkeHashMap.this.entrySetRemoveAll(c);
        }
        public boolean retainAll(Collection c) {
            return IntRadkeHashMap.this.entrySetRetainAll(c);
        }
        public Object[] toArray() {
            return IntRadkeHashMap.this.entrySetToArray();
        }
        public Object[] toArray(Object[] a) {
            return IntRadkeHashMap.this.entrySetToArray(a);
        }
        public Iterator iterator() {
            return new EntryIterator();
        }
    }

    // copied entry (not backed by the map)
    private static class SimpleEntry implements IntMap.Entry {
        final int key;
        final Object value;
        SimpleEntry(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public int getKey() {
            return key;
        }
        public Object getValue() {
            return value;
        }
        public Object setValue(Object value) {
            throw new UnsupportedOperationException("Immutable object");
        }
        public boolean equals(Object other) {
            if (!(other instanceof IntMap.Entry)) return false;
            IntMap.Entry that = (IntMap.Entry)other;
            if (getKey() != that.getKey()) return false;
            if (!IntRadkeHashMap.equals(getValue(), that.getValue())) return false;
            return true;
        }
        public int hashCode() {
            int key = getKey();
            Object val = getValue();
            return hash(key)  ^ (val == null ? 0 : val.hashCode());
        }
        public String toString() {
            return getKey() + "=" + getValue();
        }
    }

    private class Values implements Collection {
        public boolean add(Object o) {
            throw new UnsupportedOperationException();
        }
        public boolean addAll(Collection c) {
            throw new UnsupportedOperationException();
        }
        public void clear() {
            IntRadkeHashMap.this.clear();
        }
        public int size() {
            return IntRadkeHashMap.this.size();
        }
        public boolean isEmpty() {
            return IntRadkeHashMap.this.isEmpty();
        }
        public boolean contains(Object o) {
            return IntRadkeHashMap.this.containsValue(o);
        }
        public boolean containsAll(Collection c) {
            return IntRadkeHashMap.this.valuesContainsAll(c);
        }
        public boolean remove(Object o) {
            return IntRadkeHashMap.this.valuesRemoveMapping(o);
        }
        public boolean removeAll(Collection c) {
            return IntRadkeHashMap.this.valuesRemoveAll(c);
        }
        public boolean retainAll(Collection c) {
            return IntRadkeHashMap.this.valuesRetainAll(c);
        }
        public Object[] toArray() {
            return IntRadkeHashMap.this.valuesToArray();
        }
        public Object[] toArray(Object[] a) {
            return IntRadkeHashMap.this.valuesToArray(a);
        }
        public Iterator iterator() {
            return new ValueIterator();
        }
    }

    private boolean keySetContainsAll(IntCollection c) {
        for (IntIterator itr = c.iterator(); itr.hasNext();) {
            if (!containsKey(itr.next())) return false;
        }
        return true;
    }

    private boolean keySetRemoveMapping(int key) {
        int p = find(key);
        if (p < 0) return false;
        Object removed = values[p];
        values[p] = REMOVED;
        size--;
        return true;
    }

    private boolean keySetRemoveAll(IntCollection c) {
        boolean modified = false;
        if (keys.length*2 < c.size()) {
            for (int i=0; i<keys.length; i++) {
                Object val = values[i];
                if (val == null || val == REMOVED) continue;
                if (c.contains(keys[i])) {
                    values[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            for (IntIterator itr = c.iterator(); itr.hasNext();) {
                modified |= keySetRemoveMapping(itr.next());
            }
        }
        return modified;
    }

    private boolean keySetRetainAll(IntCollection c) {
        boolean modified = false;
        if (keys.length*4 < c.size()) {
            for (int i=0; i<keys.length; i++) {
                Object val = values[i];
                if (val == null || val == REMOVED) continue;
                if (!c.contains(keys[i])) {
                    values[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            IntRadkeHashMap tmp =
                new IntRadkeHashMap(keys.length, loadFactor, resizeTreshold);
            for (IntIterator itr = c.iterator(); itr.hasNext();) {
                int key = itr.next();
                int p = find(key);
                if (p < 0) continue;
                tmp.put(key, values[p]);
                modified = true;
            }
            if (modified) {
                this.keys = tmp.keys;
                this.values = tmp.values;
                this.size = tmp.size;
                this.fill = tmp.fill;
            }
        }
        return modified;
    }

    private int[] keySetToArray(int a[]) {
        int size = size();
        if (a.length < size) a = new int[size];

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = keys[j];
        }

        return a;
    }

    private int[] keySetToArray() {
        int[] a = new int[size()];

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = keys[j];
        }

        return a;
    }


    private boolean entrySetContainsEntry(Object o) {
        if (!(o instanceof IntMap.Entry)) return false;
        IntMap.Entry e = (IntMap.Entry)o;
        return containsMapping(e.getKey(), e.getValue());
    }

    private boolean entrySetContainsAll(Collection c) {
        for (Iterator itr = c.iterator(); itr.hasNext();) {
            Object o = itr.next();
            if (!(o instanceof IntMap.Entry)) continue;
            IntMap.Entry e = (IntMap.Entry)o;
            if (!containsMapping(e.getKey(), e.getValue())) return false;
        }
        return true;
    }

    private boolean entrySetRemoveMapping(Object o) {
        if (!(o instanceof IntMap.Entry)) return false;
        IntMap.Entry e = (IntMap.Entry)o;
        return removeMapping(e.getKey(), e.getValue());
    }

    private boolean entrySetRemoveAll(Collection c) {
        boolean modified = false;
        if (keys.length < c.size()) {
            for (int i=0; i<keys.length; i++) {
                Object val = values[i];
                if (val == null || val == REMOVED) continue;
                if (c.contains(new SimpleEntry(keys[i], unmaskNull(val)))) {
                    values[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            for (Iterator itr = c.iterator(); itr.hasNext();) {
                modified |= entrySetRemoveMapping(itr.next());
            }
        }
        return modified;
    }

    private boolean entrySetRetainAll(Collection c) {
        boolean modified = false;
        if (keys.length*4 < c.size()) {
            for (int i=0; i<keys.length; i++) {
                Object val = values[i];
                if (val == null || val == REMOVED) continue;
                if (!c.contains(new SimpleEntry(keys[i], unmaskNull(val)))) {
                    values[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            IntRadkeHashMap tmp =
                new IntRadkeHashMap(keys.length, loadFactor, resizeTreshold);
            for (Iterator itr = c.iterator(); itr.hasNext();) {
                Object o = itr.next();
                if (!(o instanceof IntMap.Entry)) continue;
                IntMap.Entry e = (IntMap.Entry)o;
                int p = find(e.getKey());
                if (p < 0) continue;
                Object val = unmaskNull(values[p]);
                if (equals(e.getValue(), val)) {
                    tmp.put(e.getKey(), val);
                }
            }
            modified = (size != tmp.size);
            if (modified) {
                this.keys = tmp.keys;
                this.values = tmp.values;
                this.size = tmp.size;
                this.fill = tmp.fill;
            }
        }
        return modified;
    }

    private Object[] entrySetToArray(Object a[]) {
        int size = size();
        if (a.length < size) {
            a = (Object[])Array.newInstance(a.getClass().getComponentType(), size);
        }

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = new SimpleEntry(keys[j], unmaskNull(val));
        }

        return a;
    }

    private Object[] entrySetToArray() {
        Object[] a = new Object[size()];

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = new SimpleEntry(keys[j], unmaskNull(val));
        }

        return a;
    }

    private boolean valuesContainsAll(Collection c) {
        // todo optimize for large sizes
        for (Iterator itr = c.iterator(); itr.hasNext();) {
            if (!containsValue(itr.next())) return false;
        }
        return true;
    }

    private boolean valuesRemoveMapping(Object value) {
        int p = findVal(value);
        if (p < 0) return false;
        Object removed = values[p];
        values[p] = REMOVED;
        size--;
        return true;
    }

    private boolean valuesRemoveAll(Collection c) {
        boolean modified = false;
        for (int i=0; i<keys.length; i++) {
            Object val = values[i];
            if (val == null || val == REMOVED) continue;
            if (c.contains(unmaskNull(val))) {
                values[i] = REMOVED;
                size--;
                modified = true;
            }
        }
        return modified;
    }

    private boolean valuesRetainAll(Collection c) {
        boolean modified = false;
        for (int i=0; i<keys.length; i++) {
            Object val = values[i];
            if (val == null || val == REMOVED) continue;
            if (!c.contains(unmaskNull(val))) {
                values[i] = REMOVED;
                size--;
                modified = true;
            }
        }
        return modified;
    }

    private Object[] valuesToArray(Object a[]) {
        int size = size();
        if (a.length < size) {
            a = (Object[])Array.newInstance(a.getClass().getComponentType(), size);
        }

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = unmaskNull(val);
        }

        return a;
    }

    private Object[] valuesToArray() {
        Object[] a = new Object[size()];

        int i=0;

        for (int j=0; j<keys.length; j++) {
            Object val = values[j];
            if (val == null || val == REMOVED) continue;
            a[i++] = unmaskNull(val);
        }

        return a;
    }

    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("{");

        HashIterator itr = new HashIterator();
        while (itr.hasNext()) {
            itr.goNext();
            int k  = keys[itr.curr];
            Object v = unmaskNull(values[itr.curr]);
            buf.append(k).append("=").append((v == this ? "(this Map)": v));

            if (itr.hasNext())
                buf.append(", ");
        }

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

    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(keys.length); // the capacity
        out.writeInt(size);        // number of entries

        for (int i=0; i<keys.length; i++) {
            Object val = values[i];
            if (val == null || val == REMOVED) continue;
            out.writeInt(keys[i]);
            out.writeObject(unmaskNull(val));
        }
    }

    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        int capacity = in.readInt();
        this.keys = new int[capacity];
        this.values = new Object[capacity];

        // number of entries
        int size = in.readInt();

        for (int i=0; i<size; i++) {
            int key = in.readInt();
            Object value = in.readObject();
            put(key, value);
        }
    }

    private final static boolean equals(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }

    private static final Object maskNull(Object obj) {
        return obj == null ? NULL : obj;
    }

    private static final Object unmaskNull(Object obj) {
        return obj == NULL ? null : obj;
    }

    private final static int hash(int e) {
        return e;                                  
    }

    private final static int phash(int e) {
        return e & 0x7fffffff;                     
    }
}
