///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////

package gnu.trove;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

/**
 * An open addressed Map implementation for long keys and Object values.
 *
 * Created: Sun Nov  4 08:52:45 2001
 *
 * @author Eric D. Friedman
 * @version $Id: TLongObjectHashMap.java,v 1.15 2003/11/21 17:32:31 ericdf Exp $
 */
public class TLongObjectHashMap extends TLongHash implements Serializable {

    /** the values of the map */
    protected transient Object[] _values;

    /**
     * Creates a new TLongObjectHashMap instance with the default
     * capacity and load factor.
     */
    public TLongObjectHashMap() {
        super();
    }

    /**
     * Creates a new TLongObjectHashMap instance with a prime
     * capacity equal to or greater than initialCapacity and
     * with the default load factor.
     *
     * @param initialCapacity an int value
     */
    public TLongObjectHashMap(int initialCapacity) {
        super(initialCapacity);
    }

    /**
     * Creates a new TLongObjectHashMap instance with a prime
     * capacity equal to or greater than initialCapacity and
     * with the specified load factor.
     *
     * @param initialCapacity an int value
     * @param loadFactor a float value
     */
    public TLongObjectHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
    }

    /**
     * Creates a new TLongObjectHashMap instance with the default
     * capacity and load factor.
     * @param strategy used to compute hash codes and to compare keys.
     */
    public TLongObjectHashMap(TLongHashingStrategy strategy) {
        super(strategy);
    }

    /**
     * Creates a new TLongObjectHashMap instance whose capacity
     * is the next highest prime above initialCapacity + 1
     * unless that value is already prime.
     *
     * @param initialCapacity an int value
     * @param strategy used to compute hash codes and to compare keys.
     */
    public TLongObjectHashMap(int initialCapacity, TLongHashingStrategy strategy) {
        super(initialCapacity, strategy);
    }

    /**
     * Creates a new TLongObjectHashMap instance with a prime
     * value at or near the specified capacity and load factor.
     *
     * @param initialCapacity used to find a prime capacity for the table.
     * @param loadFactor used to calculate the threshold over which
     * rehashing takes place.
     * @param strategy used to compute hash codes and to compare keys.
     */
    public TLongObjectHashMap(int initialCapacity, float loadFactor, TLongHashingStrategy strategy) {
        super(initialCapacity, loadFactor, strategy);
    }

    /**
     * @return a deep clone of this collection
     */
    public Object clone() {
      TLongObjectHashMap m = (TLongObjectHashMap)super.clone();
      m._values = (Object[])this._values.clone();
      return m;
    }

    /**
     * @return a TLongObjectIterator with access to this map's keys and values
     */
    public TLongObjectIterator iterator() {
        return new TLongObjectIterator(this);
    }

    /**
     * initializes the hashtable to a prime capacity which is at least
     * initialCapacity + 1.  
     *
     * @param initialCapacity an int value
     * @return the actual capacity chosen
     */
    protected int setUp(int initialCapacity) {
        int capacity;

        capacity = super.setUp(initialCapacity);
        _values = new Object[capacity];
        return capacity;
    }

    /**
     * Inserts a key/value pair into the map.
     *
     * @param key an long value
     * @param value an Object value
     * @return the previous value associated with key,
     * or null if none was found.
     */
    public Object put(long key, Object value) {
        byte previousState;
        Object previous = null;
        int index = insertionIndex(key);
        boolean isNewMapping = true;
        if (index < 0) {
            index = -index -1;
            previous = _values[index];
            isNewMapping = false;
        }
        previousState = _states[index];
        _set[index] = key;
        _states[index] = FULL;
        _values[index] = value;
        if (isNewMapping) {
            postInsertHook(previousState == FREE);
        }

        return previous;
    }

    /**
     * rehashes the map to the new capacity.
     *
     * @param newCapacity an int value
     */
    protected void rehash(int newCapacity) {
        int oldCapacity = _set.length;
        long oldKeys[] = _set;
        Object oldVals[] = _values;
        byte oldStates[] = _states;

        _set = new long[newCapacity];
        _values = new Object[newCapacity];
        _states = new byte[newCapacity];

        for (int i = oldCapacity; i-- > 0;) {
            if(oldStates[i] == FULL) {
                long o = oldKeys[i];
                int index = insertionIndex(o);
                _set[index] = o;
                _values[index] = oldVals[i];
                _states[index] = FULL;
            }
        }
    }

    /**
     * retrieves the value for key
     *
     * @param key an long value
     * @return the value of key or null if no such mapping exists.
     */
    public Object get(long key) {
        int index = index(key);
        return index < 0 ? null : _values[index];
    }

    /**
     * Empties the map.
     *
     */
    public void clear() {
        super.clear();
        long[] keys = _set;
        Object[] vals = _values;
        byte[] states = _states;

        for (int i = keys.length; i-- > 0;) {
            keys[i] = (long)0;
            vals[i] = null;
            states[i] = FREE;
        }
    }

    /**
     * Deletes a key/value pair from the map.
     *
     * @param key an long value
     * @return an Object value, or null if no mapping for key exists
     */
    public Object remove(long key) {
        Object prev = null;
        int index = index(key);
        if (index >= 0) {
            prev = _values[index];
            removeAt(index);    // clear key,state; adjust size
        }
        return prev;
    }

    /**
     * Compares this map with another map for equality of their stored
     * entries.
     *
     * @param other an Object value
     * @return a boolean value
     */
    public boolean equals(Object other) {
        if (! (other instanceof TLongObjectHashMap)) {
            return false;
        }
        TLongObjectHashMap that = (TLongObjectHashMap)other;
        if (that.size() != this.size()) {
            return false;
        }
        return forEachEntry(new EqProcedure(that));
    }

    public int hashCode() {
        HashProcedure p = new HashProcedure();
        forEachEntry(p);
        return p.getHashCode();
    }	

    private final class HashProcedure implements TLongObjectProcedure {
        private int h = 0;
        
        public int getHashCode() {
            return h;
        }
        
        public final boolean execute(long key, Object value) {
            h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
            return true;
        }
    }

    private static final class EqProcedure implements TLongObjectProcedure {
        private final TLongObjectHashMap _otherMap;

        EqProcedure(TLongObjectHashMap otherMap) {
            _otherMap = otherMap;
        }

        public final boolean execute(long key, Object value) {
            int index = _otherMap.index(key);
            if (index >= 0 && eq(value, _otherMap.get(key))) {
                return true;
            }
            return false;
        }

        /**
         * Compare two objects for equality.
         */
        private final boolean eq(Object o1, Object o2) {
            return o1 == o2 || ((o1 != null) && o1.equals(o2));
        }

    }

    /**
     * removes the mapping at index from the map.
     *
     * @param index an int value
     */
    protected void removeAt(int index) {
        super.removeAt(index);  // clear key, state; adjust size
        _values[index] = null;
    }

    /**
     * Returns the values of the map.
     *
     * @return a Collection value
     */
    public Object[] getValues() {
        Object[] vals = new Object[size()];
        Object[] v = _values;
        byte[] states = _states;

        for (int i = v.length, j = 0; i-- > 0;) {
          if (states[i] == FULL) {
            vals[j++] = v[i];
          }
        }
        return vals;
    }

    /**
     * returns the keys of the map.
     *
     * @return a Set value
     */
    public long[] keys() {
        long[] keys = new long[size()];
        long[] k = _set;
        byte[] states = _states;

        for (int i = k.length, j = 0; i-- > 0;) {
          if (states[i] == FULL) {
            keys[j++] = k[i];
          }
        }
        return keys;
    }

    /**
     * checks for the presence of val in the values of the map.
     *
     * @param val an Object value
     * @return a boolean value
     */
    public boolean containsValue(Object val) {
        byte[] states = _states;
        Object[] vals = _values;

        // special case null values so that we don't have to
        // perform null checks before every call to equals()
        if (null == val) {
            for (int i = vals.length; i-- > 0;) {
                if (states[i] == FULL &&
                    val == vals[i]) {
                    return true;
                }
            }
        } else {
            for (int i = vals.length; i-- > 0;) {
                if (states[i] == FULL &&
                    (val == vals[i] || val.equals(vals[i]))) {
                    return true;
                }
            }
        } // end of else
        return false;
    }


    /**
     * checks for the present of key in the keys of the map.
     *
     * @param key an long value
     * @return a boolean value
     */
    public boolean containsKey(long key) {
        return contains(key);
    }

    /**
     * Executes procedure for each key in the map.
     *
     * @param procedure a TLongProcedure value
     * @return false if the loop over the keys terminated because
     * the procedure returned false for some key.
     */
    public boolean forEachKey(TLongProcedure procedure) {
        return forEach(procedure);
    }

    /**
     * Executes procedure for each value in the map.
     *
     * @param procedure a TObjectProcedure value
     * @return false if the loop over the values terminated because
     * the procedure returned false for some value.
     */
    public boolean forEachValue(TObjectProcedure procedure) {
        byte[] states = _states;
        Object[] values = _values;
        for (int i = values.length; i-- > 0;) {
            if (states[i] == FULL && ! procedure.execute(values[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * Executes procedure for each key/value entry in the
     * map.
     *
     * @param procedure a TOLongObjectProcedure value
     * @return false if the loop over the entries terminated because
     * the procedure returned false for some entry.
     */
    public boolean forEachEntry(TLongObjectProcedure procedure) {
        byte[] states = _states;
        long[] keys = _set;
        Object[] values = _values;
        for (int i = keys.length; i-- > 0;) {
            if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * Retains only those entries in the map for which the procedure
     * returns a true value.
     *
     * @param procedure determines which entries to keep
     * @return true if the map was modified.
     */
    public boolean retainEntries(TLongObjectProcedure procedure) {
        boolean modified = false;
        byte[] states = _states;
        long[] keys = _set;
        Object[] values = _values;
        for (int i = keys.length; i-- > 0;) {
            if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
                removeAt(i);
                modified = true;
            }
        }
        return modified;
    }

    /**
     * Transform the values in this map using function.
     *
     * @param function a TObjectFunction value
     */
    public void transformValues(TObjectFunction function) {
        byte[] states = _states;
        Object[] values = _values;
        for (int i = values.length; i-- > 0;) {
            if (states[i] == FULL) {
                values[i] = function.execute(values[i]);
            }
        }
    }



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

        // number of entries
        stream.writeInt(_size);

        SerializationProcedure writeProcedure = new SerializationProcedure(stream);
        if (! forEachEntry(writeProcedure)) {
            throw writeProcedure.exception;
        }
    }

    private void readObject(ObjectInputStream stream)
        throws IOException, ClassNotFoundException {
        stream.defaultReadObject();

        int size = stream.readInt();
        setUp(size);
        while (size-- > 0) {
            long key = stream.readLong();
            Object val = stream.readObject();
            put(key, val);
        }
    }
} // TLongObjectHashMap