/*
 *  @author Ranides Atterwim <ranides@gmail.com>
 *  @copyright Ranides Atterwim
 *  @license WTFPL
 *  @url http://ranides.net/projects/assira
 */

package net.ranides.assira.collection.map;

import java.util.Map.Entry;
import java.util.*;
import net.ranides.assira.collection.ArrayUtils;

/**
 * Mapa używana do wyszukiwania po kluczu w czasie O(logN) przy minimalnym narzucie
 * pamięciowym. Dodawanie kluczy do mapy jest niedozwolone. Mapa wolniejsza od HashMap
 * ale <b>ekstremalnie</b> efektywniejsza pamięciowo.
 * @param <K>
 * @param <V>
 * @author ranides
 */
public final class SwitchMap<K extends Comparable<K>,V> implements Map<K,V> {
    private static final String TEXT_IMMUTABLE = "list of keys is immutable.";
    private final K[] keys;
    private final V[] values;

    @SuppressWarnings("unchecked")
    private SwitchMap(int keys, int values) {
        if(keys != values) {
            throw new IllegalArgumentException("length of keys & values must be equal");
        }
        this.keys   = (K[])new Comparable[keys];
        this.values = (V[])new Comparable[values];
    }

    /**
     * Tworzy nową mapę wypełniając wskazanymi kluczami i przyporządkowując im
     * wskazane wartości.
     * @param keys
     * @param values
     */
    public SwitchMap(K[] keys, V[] values) {
        this(keys.length, values.length);

        System.arraycopy(keys, 0, this.keys, 0, keys.length);
        System.arraycopy(values, 0, this.values, 0, values.length);

        ArrayUtils.sort(this.values, this.keys);
    }

    /**
     * Tworzy nową mapę wypełniając wskazanymi kluczami i przyporządkowując im
     * wskazane wartości.
     * @param entries
     */
    public SwitchMap(Entry<K,V>[] entries) {
        this(entries.length, entries.length);
        int index = 0;
        for(Entry<K,V> entry : entries) {
            keys[index] = entry.getKey();
            values[index] = entry.getValue();
            index++;
        }
        ArrayUtils.sort(this.values, this.keys);
    }

    /**
     * Tworzy nową mapę wypełniając wskazanymi danymi.
     * @param tree
     */
    public SwitchMap(SortedMap<? extends K, ? extends V> tree) {
        this(tree.size(),tree.size());
        int i = 0;
        for(Entry<? extends K, ? extends V> entry : tree.entrySet()) {
            this.keys[i]    = entry.getKey();
            this.values[i]  = entry.getValue();
            i++;
        }
    }

    /**
     * Tworzy nową mapę wypełniając podanymi kluczami. Wartości przypisane
     * kluczom można modyfikować w późniejszym czasie.
     * @param keys
     */
    public SwitchMap(K[] keys) {
        this(keys.length, keys.length);
        System.arraycopy(keys, 0, this.keys, 0, keys.length);
        Arrays.sort(this.keys);
    }

    /**
     * Tworzy nową mapę wypełniając podanymi kluczami. Wartości przypisane
     * kluczom można modyfikować w późniejszym czasie.
     * @param keys
     */
    public SwitchMap(Collection<K> keys) {
        this(keys.size(), keys.size());
        int index = 0;
        for(K key : keys) {
            this.keys[index++] = key;
        }
        Arrays.sort(this.keys);
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(1)</p>
     * @return
     */
    @Override
    public int size() {
        return keys.length;
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(1)</p>
     * @return
     */
    @Override
    public boolean isEmpty() {
        return keys.length == 0;
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(logN)</p>
     * @return
     */
    @Override
    public boolean containsKey(Object key) {
        return Arrays.binarySearch(keys, key) >= 0;
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(N)</p>
     * @return
     */
    @Override
    public boolean containsValue(Object value) {
        if (value==null) {
            for (int i=0; i<values.length; i++) {
                if (values[i]==null) { return true; }
            }
        } else {
            for(int i=0; i<values.length; i++) {
                if( value.equals(values[i]) ) { return true; }
            }
        }
        return false;
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(logN)</p>
     * @return
     */
    @Override
    public V get(Object key) {
        int index = Arrays.binarySearch(keys, key);
        return index<0 ? null : values[index];
    }

    /**
     * Replaces the old value associated with key by the specified value.
     * If the map previously didn't contain a mapping for the key, exception is thrown.
     * (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)
     * <p><b>Złożoność:</b> O(logN)</p>
     *
     * @param key existing key in the map, with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>
     *
     * @throws UnsupportedOperationException if the specified key does not exist
     * in the map
     */
    @Override
    public V put(K key, V value) {
        int index = Arrays.binarySearch(keys, key);
        if(index < 0) {
            throw new UnsupportedOperationException(TEXT_IMMUTABLE);
        }
        V prev = values[index];
        values[index] = value;
        return prev;
    }

    /**
     * Metoda nie obsługiwana.
     * @param key
     * @return
     * @deprecated
     * @throws UnsupportedOperationException zawsze
     */
    @Override
    public V remove(Object key) {
        throw new UnsupportedOperationException(TEXT_IMMUTABLE);
    }

    /**
     * {@inheritDoc}
     * <p><b>Złożoność:</b> O(NlogN).</p>
     * @param map
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        if( map.size() > size() ) {
            throw new UnsupportedOperationException(TEXT_IMMUTABLE);
        }
        for(Entry<? extends K,? extends V> entry : map.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Metoda nie obsługiwana.
     * @deprecated
     * @throws UnsupportedOperationException zawsze
     */
    @Override
    public void clear() {
        throw new UnsupportedOperationException(TEXT_IMMUTABLE);
    }

    @Override
    public Set<K> keySet() {
        return new KeySet();
    }

    @Override
    public Collection<V> values() {
        return Arrays.asList(values);
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new EntrySet();
    }

/* ************************************************************************** */

    private class KeyIterator implements Iterator<K> {

        private int index = -1;

        @Override
        public boolean hasNext() {
            return index+1 < keys.length;
        }
        @Override
        public K next() {
            return keys[++index];
        }
        @Override
        public void remove() {
            throw new UnsupportedOperationException(TEXT_IMMUTABLE);
        }
    }

    private class EntryIterator implements Iterator<Entry<K,V>> {

        private int index = -1;

        @Override
        public boolean hasNext() {
            return index+1 < keys.length;
        }
        @Override
        public Entry<K,V> next() {
            index++;
            return new AbstractMap.SimpleImmutableEntry<>(keys[index], values[index]);
        }
        @Override
        public void remove() {
            throw new UnsupportedOperationException(TEXT_IMMUTABLE);
        }
    }

    @SuppressWarnings({"unchecked", "element-type-mismatch"})
    private class KeySet extends AbstractSet<K> {
        @Override
        public int size() {
            return keys.length;
        }

        @Override
        public boolean contains(Object key) {
            return SwitchMap.this.containsKey(key);
        }
        @Override
        public Iterator<K> iterator() {
            return new KeyIterator();
        }
    }

    @SuppressWarnings({"unchecked", "element-type-mismatch"})
    private class EntrySet extends AbstractSet<Entry<K,V>> {
        @Override
        public int size() {
            return keys.length;
        }
        @Override
        public boolean contains(Object object) {
            if( !(object instanceof Entry) ) { return false; }

            final Entry<K,V> entry = (Entry<K,V>)object;
            final V value = SwitchMap.this.get( entry.getKey() );
            if(null == value) {
                return entry.getValue() == null;
            } else {
                return value.equals(entry.getValue());
            }
        }
        @Override
        public Iterator<Entry<K,V>> iterator() {
            return new EntryIterator();
        }
    }

}
