/*******************************************************************************
 * 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.utils.datastructures;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * A space-optimized immutable Map implementation.
 * 
 * <p>
 * Both map keys and values are specified as separate typed arrays that must be
 * equally sized. This provides for space-optimization by allowing reusable key
 * array instances since the keys cannot be modified.
 * 
 * <p>
 * The map should be considered immutable, but it does allow modification of a
 * value for an existing key as this only changes the value, the key will remain
 * untouched.
 * 
 * @author Tuukka Lehtonen
 * 
 * @param <K> key class
 * @param <V> value class
 */
public class ArrayMap<K, V> implements Map<K, V> {

    K[] keys;
    V[] values;
    Set<Map.Entry<K, V>> entrySet;
    Set<K> keySet;
    Collection<V> valueSet;

    public static class ArrayMapBuilder<K2, V2> {

        final private K2[] keys;

        ArrayMapBuilder(K2[] keys) {
            this.keys = keys;
        }

        public ArrayMap<K2, V2> values(@SuppressWarnings("unchecked") V2 ... values) {
            return new ArrayMap<K2, V2>(keys, values);
        }

    }

    public static <K2, V2>ArrayMapBuilder<K2, V2> keys(@SuppressWarnings("unchecked") K2 ... keys) {
        return new ArrayMapBuilder<K2, V2>(keys);
    }

    public static <K2, V2> ArrayMap<K2, V2> make(K2[] keys, @SuppressWarnings("unchecked") V2... values) {
        return new ArrayMap<K2, V2>(keys, values);
    }

    /**
     * Constructs new ArrayMap based on a key and value array. Both arrays must
     * be of the same size.
     * 
     * @param keys key array
     * @param values value array
     * @throws IllegalArgumentException if the arrays are of different size
     * @throws NullPointerException if either parameter is <code>null</code>
     */
    public ArrayMap(K[] keys, V[] values) {
        // NPE is caught by this.
        if (keys.length != values.length)
            throw new IllegalArgumentException("key array size (" + keys.length + ") != value array size (" + values.length + ")");
        this.keys = keys;
        this.values = values;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return (entrySet != null) ? entrySet : (entrySet = new EntrySet());
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean containsKey(Object key) {
        return keySet().contains(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return values().contains(value);
    }

    @Override
    public V get(Object key) {
        if (key == null) {
            for (int i = 0; i < keys.length; i++) {
                if (keys[i] == null) {
                    return values[i];
                }
            }
            return null;
        }
        int hash = key.hashCode();
        for (int i = 0; i < keys.length; i++) {
            K k = keys[i];
            if (k == key || (hash == k.hashCode() && key.equals(k))) {
                return values[i];
            }
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return keys.length == 0;
    }

    @Override
    public Set<K> keySet() {
        return (keySet != null) ? keySet : (keySet =  new KeySet());
    }

    @Override
    public V put(K key, V value) {
        if (key == null) {
            for (int i = 0; i < keys.length; i++) {
                if (keys[i] == null) {
                    V old = values[i];
                    values[i] = value;
                    return old;
                }
            }
            throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
        }
        int hash = key.hashCode();
        for (int i = 0; i < keys.length; i++) {
            K k = keys[i];
            if (k == key || (hash == k.hashCode() && key.equals(k))) {
                V old = values[i];
                values[i] = value;
                return old;
            }
        }
        throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (K k : m.keySet()) {
            if (!containsKey(k))
                throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");
        }
        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public V remove(Object key) {
        throw new UnsupportedOperationException();
    }

    @Override
    public int size() {
        return keys.length;
    }

    @Override
    public Collection<V> values() {
        return valueSet != null ? valueSet : (valueSet = Collections.unmodifiableCollection(Arrays.asList(values)));
    }

    class KeySet extends ImmutableSet<K> implements Set<K> {

        @Override
        public boolean contains(Object o) {
            if (o == null) {
                for (K k : keys)
                    if (k == null)
                        return true;
                return false;
            }
            int hash = o.hashCode();
            for (K k : keys)
                if (o == k || (hash == k.hashCode() && o.equals(k)))
                    return true;
            return false;
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            for (Object o : c)
                if (!contains(o))
                    return false;
            return true;
        }

        @Override
        public boolean isEmpty() {
            return keys.length == 0;
        }

        @Override
        public Iterator<K> iterator() {
            return new ImmutableIterator<K>() {
                int i = 0;

                @Override
                public boolean hasNext() {
                    return i < keys.length;
                }

                @Override
                public K next() {
                    if (i >= keys.length)
                        throw new NoSuchElementException("no more elements (" + keys.length + " walked)");
                    K k = keys[i];
                    ++i;
                    return k;
                }
            };
        }

        @Override
        public int size() {
            return keys.length;
        }

        @Override
        public Object[] toArray() {
            return keys;
        }

        @SuppressWarnings("unchecked")
        @Override
        public <T> T[] toArray(T[] a) {
            if (a.length < keys.length)
                // Make a new array of a's runtime type, but my contents:
                return (T[]) Arrays.copyOf(keys, keys.length, a.getClass());
            System.arraycopy(keys, 0, a, 0, keys.length);
            if (a.length > keys.length)
                a[keys.length] = null;
            return a;
        }
    }

    class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {

        @Override
        public boolean contains(Object o) {
            throw new UnsupportedOperationException("TODO");
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            for (Object o : c)
                if (!contains(o))
                    return false;
            return true;
        }

        @Override
        public boolean isEmpty() {
            return keys.length == 0;
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new ImmutableIterator<Map.Entry<K, V>>() {
                int i = 0;

                @Override
                public boolean hasNext() {
                    return i < keys.length;
                }

                @Override
                public Map.Entry<K, V> next() {
                    if (i >= keys.length)
                        throw new NoSuchElementException("no more elements (" + keys.length + " walked)");
                    Map.Entry<K, V> entry = new Entry<K, V>(i, keys[i], values[i]);
                    ++i;
                    return entry;
                }
            };
        }

        @Override
        public int size() {
            return keys.length;
        }

    }

    static class Entry<K, V> implements Map.Entry<K, V> {
        final K key;
        V value;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v) {
            value = v;
            key = k;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry<?, ?>))
                return false;
            Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        @Override
        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
            (value==null ? 0 : value.hashCode());
        }

        @Override
        public final String toString() {
            return getKey() + "=" + getValue();
        }
    }

    /**
     * Returns the hash code value for this map.  The hash code of a map is
     * defined to be the sum of the hash codes of each entry in the map's
     * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
     * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
     * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
     * {@link Object#hashCode}.
     *
     * <p>This implementation iterates over <tt>entrySet()</tt>, calling
     * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
     * set, and adding up the results.
     *
     * @return the hash code value for this map
     * @see Map.Entry#hashCode()
     * @see Object#equals(Object)
     * @see Set#equals(Object)
     */
    @Override
    public int hashCode() {
        int h = 0;
        int l = keys.length;
        for (int i = 0; i < l; i++) {
            K key = keys[i];
            V value = values[i];
            int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
            h += hash;
        }
        return h;
    }

    /**
     * Compares the specified object with this map for equality.  Returns
     * <tt>true</tt> if the given object is also a map and the two maps
     * represent the same mappings.  More formally, two maps <tt>m1</tt> and
     * <tt>m2</tt> represent the same mappings if
     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
     * <tt>equals</tt> method works properly across different implementations
     * of the <tt>Map</tt> interface.
     *
     * <p>This implementation first checks if the specified object is this map;
     * if so it returns <tt>true</tt>.  Then, it checks if the specified
     * object is a map whose size is identical to the size of this map; if
     * not, it returns <tt>false</tt>.  If so, it iterates over this map's
     * <tt>entrySet</tt> collection, and checks that the specified map
     * contains each mapping that this map contains.  If the specified map
     * fails to contain such a mapping, <tt>false</tt> is returned.  If the
     * iteration completes, <tt>true</tt> is returned.
     *
     * @param o object to be compared for equality with this map
     * @return <tt>true</tt> if the specified object is equal to this map
     */
    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof Map))
            return false;
        Map<K, V> m = (Map<K, V>) o;
        if (m.size() != size())
            return false;

        try {
            int l = keys.length;
            for (int i = 0; i < l; i++) {
                K key = keys[i];
                V value = values[i];
                if (value == null) {
                    if (!(m.get(key)==null && m.containsKey(key)))
                        return false;
                } else {
                    if (!value.equals(m.get(key)))
                        return false;
                }
            }
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }

    @Override
    public String toString() {
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        if (! i.hasNext())
            return "{}";

        StringBuilder sb = new StringBuilder();
        sb.append('{');
        for (;;) {
            Map.Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue();
            sb.append(key   == this ? "(this Map)" : key);
            sb.append('=');
            sb.append(value == this ? "(this Map)" : value);
            if (! i.hasNext())
                return sb.append('}').toString();
            sb.append(", ");
        }
    }
}