/*******************************************************************************
 * Copyright (c) 2016 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:
 *     Semantum Oy - initial API and implementation
 *******************************************************************************/
package org.simantics.utils.datastructures;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * A space-optimized immutable Map implementation where keys and values are
 * interlaced in one Object array.
 * 
 * <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.
 * 
 * The nested class {@link InterlacedArrayMapBuilder} allows easy and
 * minimal-allocation construction of an {@link InterlacedArrayMap}. Use
 * {@link InterlacedArrayMap#builder()} or
 * {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to
 * minimize the space allocated for the {@link #data} field in the built map
 * instance. If the builder is completely filled up, i.e. its capacity matches
 * added key, value pair count, the array it contains is directly transferred to
 * the built map instance without creating any extra copies. So if possible, set
 * the correct initial capacity for the builder.
 * 
 * @author Tuukka Lehtonen
 * 
 * @param <K>
 *            key class
 * @param <V>
 *            value class
 */
public class InterlacedArrayMap<K, V> implements Map<K, V> {

    final Object[] data;
    Set<Map.Entry<K, V>> entrySet;
    Set<K> keySet;
    Collection<V> valueSet;

    public static class InterlacedArrayMapBuilder<K, V> {

        private Object[] elementData;
        private int count = 0;

        private InterlacedArrayMapBuilder(int initialCapacity) {
            this.elementData = new Object[initialCapacity*2];
        }

        public void add(K key, V v) {
            ensureCapacityInternal(count + 2);
            elementData[count] = key;
            elementData[count+1] = v;
            count += 2;
        }

        private void ensureCapacityInternal(int minCapacity) {
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

        /**
         * The maximum size of array to allocate.
         * Some VMs reserve some header words in an array.
         * Attempts to allocate larger arrays may result in
         * OutOfMemoryError: Requested array size exceeds VM limit
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

        /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

        public InterlacedArrayMap<K, V> build() {
            return count == elementData.length
                    ? new InterlacedArrayMap<>(elementData)
                    : new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));
        }

    }

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * @return a map builder with the default initial capacity of
     *         {@value #DEFAULT_CAPACITY} key,value pairs.
     */
    public static <K, V> InterlacedArrayMapBuilder<K, V> builder() {
        return new InterlacedArrayMapBuilder<K, V>(DEFAULT_CAPACITY);
    }

    /**
     * @param initialCapacity
     *            the amount of key,value pairs to fit into the builder
     *            initially without having to reallocate anything
     * @return a map builder with the specified initial key,value pair capacity
     */
    public static <K, V> InterlacedArrayMapBuilder<K, V> builder(int initialCapacity) {
        return new InterlacedArrayMapBuilder<K, V>(initialCapacity);
    }

    /**
     * Just like {@link #InterlacedArrayMap(Object[])} but takes the array of
     * objects as a collection.
     * 
     * @param keysAndValues
     *            an interlaced array where where (key, value) pairs are
     *            repeated in consecutive indexes of the array
     * @throws IllegalArgumentException
     *             if the array size is not divisible by two
     * @throws NullPointerException
     *             if either parameter is <code>null</code>
     */
    public InterlacedArrayMap(List<?> keysAndValues) {
        this(keysAndValues.toArray());
    }

    /**
     * Constructs new ArrayMap based on an interlaced array of keys and values.
     * The array size must be divisible by two.
     * 
     * @param keysAndValues
     *            an interlaced array where where (key, value) pairs are
     *            repeated in consecutive indexes of the array
     * @throws IllegalArgumentException
     *             if the array size is not divisible by two
     * @throws NullPointerException
     *             if either parameter is <code>null</code>
     */
    public InterlacedArrayMap(Object[] keysAndValues) {
        // NPE is caught by this.
        if ((keysAndValues.length & 1) != 0)
            throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");
        this.data = keysAndValues;
    }

    @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 contains(0, key);
    }

    @Override
    public boolean containsValue(Object value) {
        return contains(1, value);
    }

    @SuppressWarnings("unchecked")
    @Override
    public V get(Object key) {
        if (key == null) {
            for (int i = 0; i < data.length; i += 2) {
                if (data[i] == null) {
                    return (V) data[i+1];
                }
            }
            return null;
        }
        int hash = key.hashCode();
        for (int i = 0; i < data.length; i += 2) {
            Object k = data[i];
            if (k == key || (hash == k.hashCode() && key.equals(k))) {
                return (V) data[i+1];
            }
        }
        return null;
    }

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

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

    @SuppressWarnings("unchecked")
    @Override
    public V put(K key, V value) {
        if (key == null) {
            for (int i = 0; i < data.length; i += 2) {
                if (data[i] == null) {
                    V old = (V) data[i+1];
                    data[i+1] = value;
                    return old;
                }
            }
            throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
        }
        int hash = key.hashCode();
        for (int i = 0; i < data.length; i += 2) {
            K k = (K) data[i];
            if (k == key || (hash == k.hashCode() && key.equals(k))) {
                V old = (V) data[i+1];
                data[i+1] = 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 data.length >> 1;
    }

    @Override
    public Collection<V> values() {
        return valueSet != null ? valueSet : (valueSet = new OffsetSet<V>(1));
    }

    private boolean contains(int offset, Object o) {
        int len = data.length;
        if (o == null) {
            for (int i = offset; i < len; i += 2)
                if (data[i] == null)
                    return true;
            return false;
        }
        int hash = o.hashCode();
        for (int i = offset; i < len; i += 2) {
            Object k = data[i];
            if (o == k || (hash == k.hashCode() && o.equals(k)))
                return true;
        }
        return false;
    }

    class OffsetSet<T> extends ImmutableSet<T> implements Set<T> {

        private final int offset;

        public OffsetSet(int offset) {
            this.offset = offset;
        }

        @Override
        public boolean contains(Object o) {
            return InterlacedArrayMap.this.contains(offset, o);
        }

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

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

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

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

                @Override
                public T next() {
                    if (i >= data.length)
                        throw new NoSuchElementException("no more elements (" + data.length + " walked)");
                    @SuppressWarnings("unchecked")
                    T t = (T) data[i];
                    ++i;
                    return t;
                }
            };
        }

        @Override
        public int size() {
            return data.length >> 1;
        }

        @Override
        public Object[] toArray() {
            int len = data.length >> 1;
            Object[] a = new Object[len];
            for (int i = 0; i < len; ++i)
                a[i] = data[i*2+offset];
            return a;
        }

        @SuppressWarnings("unchecked")
        @Override
        public <TT> TT[] toArray(TT[] a) {
            int len = data.length >> 1;
            if (a.length < len) {
                Class<?> clazz = a.getClass();
                // Make a new array of a's runtime type, but my contents:
                a = ((Object)clazz == (Object)Object[].class)
                ? (TT[]) new Object[len]
                : (TT[]) Array.newInstance(clazz.getComponentType(), len);
            }
            for (int i = 0; i < len; ++i)
                a[i] = (TT) data[i*2+offset];
            if (a.length > len)
                a[len] = 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 data.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 < data.length;
                }

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

        @Override
        public int size() {
            return data.length >> 1;
        }

    }

    /**
     * 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
    @SuppressWarnings("unchecked")
    public int hashCode() {
        int h = 0;
        int l = data.length;
        for (int i = 0; i < l; i += 2) {
            K key = (K) data[i];
            V value = (V) data[i+1];
            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 = data.length;
            for (int i = 0; i < l; i += 2) {
                K key = (K) data[i];
                V value = (V) data[i+1];
                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(", ");
        }
    }
}