/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.db.impl.query;

///////////////////////////////////////////////////////////////////////////////
//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.
///////////////////////////////////////////////////////////////////////////////

import gnu.trove.function.TObjectFunction;
import gnu.trove.procedure.TObjectObjectProcedure;
import gnu.trove.procedure.TObjectProcedure;

import java.io.Externalizable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * An implementation of the Map interface which uses an open addressed
 * hash table to store its contents.
 *
 * Created: Sun Nov  4 08:52:45 2001
 *
 * @author Eric D. Friedman
 * @version $Id: THashMap.java,v 1.33 2008/05/08 17:42:55 robeden Exp $
 */
public class StableHashMap<K,V> extends StableObjectHash<K> implements Map<K,V>, Externalizable {
    static final long serialVersionUID = 1L;

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

    /**
     * Creates a new <code>THashMap</code> instance with the default
     * capacity and load factor.
     */
    public StableHashMap() {
        super();
    }

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

//    /**
//     * Creates a new <code>THashMap</code> instance with a prime
//     * capacity equal to or greater than <tt>initialCapacity</tt> and
//     * with the default load factor.
//     *
//     * @param initialCapacity an <code>int</code> value
//     * @param strategy used to compute hash codes and to compare objects.
//     */
//    public StableHashMap(int initialCapacity, TObjectHashingStrategy<K> strategy) {
//        super(initialCapacity, strategy);
//    }

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

//    /**
//     * Creates a new <code>THashMap</code> instance with a prime
//     * capacity equal to or greater than <tt>initialCapacity</tt> and
//     * with the specified load factor.
//     *
//     * @param initialCapacity an <code>int</code> value
//     * @param loadFactor a <code>float</code> value
//     * @param strategy used to compute hash codes and to compare objects.
//     */
//    public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy<K> strategy) {
//        super(initialCapacity, loadFactor, strategy);
//    }

//    /**
//     * Creates a new <code>THashMap</code> instance which contains the
//     * key/value pairs in <tt>map</tt>.
//     *
//     * @param map a <code>Map</code> value
//     */
//    public StableHashMap(Map<K,V> map) {
//        this(map.size());
//        putAll(map);
//    }
//
//    /**
//     * Creates a new <code>THashMap</code> instance which contains the
//     * key/value pairs in <tt>map</tt>.
//     *
//     * @param map a <code>Map</code> value
//     * @param strategy used to compute hash codes and to compare objects.
//     */
//    public StableHashMap(Map<K,V> map, TObjectHashingStrategy<K> strategy) {
//        this(map.size(), strategy);
//        putAll(map);
//    }

    /**
     * @return a shallow clone of this collection
     */
    public StableHashMap<K,V> clone() {
        StableHashMap<K,V> m = (StableHashMap<K,V>)super.clone();
        m._values = this._values.clone();
        return m;
    }

    /**
     * initialize the value array of the map.
     *
     * @param initialCapacity an <code>int</code> value
     * @return an <code>int</code> value
     */
    protected int setUp(int initialCapacity) {
        int capacity;

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

    /**
     * Inserts a key/value pair into the map.
     *
     * @param key an <code>Object</code> value
     * @param value an <code>Object</code> value
     * @return the previous value associated with <tt>key</tt>,
     * or {@code null} if none was found.
     */
    public V put(K key, V value) {
        int index = insertionIndex(key);
        return doPut(key, value, index);
    }

    public V put(K key, V value, int hash) {
        int index = insertionIndex(key, hash);
        return doPut(key, value, index);
    }
    
    /**
     * Inserts a key/value pair into the map if the specified key is not already
     * associated with a value.
     * 
     * @param key an <code>Object</code> value
     * @param value an <code>Object</code> value
     * @return the previous value associated with <tt>key</tt>,
     * or {@code null} if none was found.
     */
    public V putIfAbsent(K key, V value) {
        int index = insertionIndex(key);
        if (index < 0)
            return _values[-index - 1];
        return doPut(key, value, index);
    }

    private V doPut(K key, V value, int index) {
        V previous = null;
        Object oldKey;
        boolean isNewMapping = true;
        if (index < 0) {
            index = -index -1;
            previous = _values[index];
            isNewMapping = false;
        }
        oldKey = _set[index];
        _set[index] = key;
        _values[index] = value;
        if (isNewMapping) {
            postInsertHook(oldKey == FREE);
        }

        return previous;
    }

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

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

    public String toString() {
        final StringBuilder buf = new StringBuilder("{");
        forEachEntry(new TObjectObjectProcedure<K,V>() {
            private boolean first = true;
            public boolean execute(K key, V value) {
                if ( first ) first = false;
                else buf.append( "," );

                buf.append(key);
                buf.append("=");
                buf.append(value);
                return true;
            }
        });
        buf.append("}");
        return buf.toString();
    }

    private final class HashProcedure implements TObjectObjectProcedure<K,V> {
        private int h = 0;

        public int getHashCode() {
            return h;
        }

        public final boolean execute(K key, V value) {
            h += _hashingStrategy.computeHashCode(key) ^ (value == null ? 0 : value.hashCode());
            return true;
        }
    }

    private static final class EqProcedure<K,V> implements TObjectObjectProcedure<K,V> {
        private final Map<K,V> _otherMap;

        EqProcedure(Map<K,V> otherMap) {
            _otherMap = otherMap;
        }

        public final boolean execute(K key, V value) {
            // Check to make sure the key is there. This avoids problems that come up with
            // null values. Since it is only caused in that cause, only do this when the
            // value is null (to avoid extra work).
            if (value == null && !_otherMap.containsKey(key)) return false;

            V oValue = _otherMap.get(key);
            return oValue == value || (oValue != null && oValue.equals(value));
        }
    }

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

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

    /**
     * Executes <tt>procedure</tt> for each key/value entry in the
     * map.
     *
     * @param procedure a <code>TObjectObjectProcedure</code> value
     * @return false if the loop over the entries terminated because
     * the procedure returned false for some entry.
     */
    public boolean forEachEntry(TObjectObjectProcedure<K,V> procedure) {
        Object[] keys = _set;
        V[] values = _values;
        for (int i = keys.length; i-- > 0;) {
            if (keys[i] != FREE
                    && keys[i] != REMOVED
                    && ! procedure.execute((K) 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(TObjectObjectProcedure<K,V> procedure) {
        boolean modified = false;
        Object[] keys = _set;
        V[] values = _values;

        // Temporarily disable compaction. This is a fix for bug #1738760
        tempDisableAutoCompaction();
        try {
            for (int i = keys.length; i-- > 0;) {
                if (keys[i] != FREE
                        && keys[i] != REMOVED
                        && ! procedure.execute((K) keys[i],values[i])) {
                    removeAt(i);
                    modified = true;
                }
            }
        }
        finally {
            reenableAutoCompaction(true);
        }

        return modified;
    }

    /**
     * Transform the values in this map using <tt>function</tt>.
     *
     * @param function a <code>TObjectFunction</code> value
     */
    public void transformValues(TObjectFunction<V,V> function) {
        V[] values = _values;
        Object[] set = _set;
        for (int i = values.length; i-- > 0;) {
            if (set[i] != FREE && set[i] != REMOVED) {
                values[i] = function.execute(values[i]);
            }
        }
    }

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

        _set = new Object[newCapacity];
        Arrays.fill(_set, FREE);
        _values = (V[]) new Object[newCapacity];

        for (int i = oldCapacity; i-- > 0;) {
            if(oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
                Object o = oldKeys[i];
                int index = insertionIndex((K) o);
                if (index < 0) {
                    throwObjectContractViolation(_set[(-index -1)], o);
                }
                _set[index] = o;
                _values[index] = oldVals[i];
            }
        }
    }

    /**
     * retrieves the value for <tt>key</tt>
     *
     * @param key an <code>Object</code> value
     * @return the value of <tt>key</tt> or null if no such mapping exists.
     */
    public V get(Object key) {
        Object[] set = _set;
        V[] values = _values;
        int index = index((K) key, set);
        return index < 0 ? null : values[index];
    }

    public V get(Object key, int hash) {
        Object[] set = _set;
        V[] values = _values;
        int index = index((K) key, hash, set);
        return index < 0 ? null : values[index];
    }
    
    /**
     * Empties the map.
     *
     */
    public void clear() {
        if (size() == 0) return; // optimization

        super.clear();

        Arrays.fill(_set, 0, _set.length, FREE);
        Arrays.fill(_values, 0, _values.length, null);
    }

    /**
     * Deletes a key/value pair from the map.
     *
     * @param key an <code>Object</code> value
     * @return an <code>Object</code> value
     */
    public V remove(Object key) {
        Object[] set = _set;
        V[] values = _values;
        V prev = null;
        int index = index((K) key, set);
        if (index >= 0) {
            prev = values[index];
            removeAt(index);    // clear key,state; adjust size
        }
        return prev;
    }
    
    protected void removeAt(int index) {
        _values[index] = null;
        super.removeAt(index);  // clear key, state; adjust size
    }

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

    public void values(int level, CacheCollectionResult result) {

    	for (int i = _set.length; i-- > 0;) {
    		if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
    			CacheEntryBase e = (CacheEntryBase)_values[i];
    			if(e.getLevel() <= level)
    				result.add(e);
    		}
    	}

    }
    
    /**
     * Returns a view on the values of the map.
     *
     * @return a <code>Collection</code> value
     */
    public Collection<V> values() {

    	Collection<V> result = new ArrayList<V>();

    	for (int i = _set.length; i-- > 0;) {
    		if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
    			result.add((V)_values[i]);
    		}
    	}

    	return result;
    	
    }

    /**
     * returns a Set view on the keys of the map.
     *
     * @return a <code>Set</code> value
     */
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    /**
     * Returns a Set view on the entries of the map.
     *
     * @return a <code>Set</code> value
     */
    public Set<Map.Entry<K,V>> entrySet() {
        throw new UnsupportedOperationException();
    }

    /**
     * checks for the presence of <tt>val</tt> in the values of the map.
     *
     * @param val an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean containsValue(Object val) {
        Object[] set = _set;
        V[] 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 ((set[i] != FREE && set[i] != REMOVED) &&
                        val == vals[i]) {
                    return true;
                }
            }
        } else {
            for (int i = vals.length; i-- > 0;) {
                if ((set[i] != FREE && set[i] != REMOVED) &&
                        (val == vals[i] || val.equals(vals[i]))) {
                    return true;
                }
            }
        } // end of else
        return false;
    }

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

    /**
     * copies the key/value mappings in <tt>map</tt> into this map.
     *
     * @param map a <code>Map</code> value
     */
    public void putAll(Map<? extends K, ? extends V> map) {
        ensureCapacity(map.size());
        // could optimize this for cases when map instanceof THashMap
        for (Iterator<? extends Map.Entry<? extends K,? extends V>> i = map.entrySet().iterator(); i.hasNext();) {
            Map.Entry<? extends K,? extends V> e = i.next();
            put(e.getKey(),e.getValue());
        }
    }
    
} // THashMap