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

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import java.util.function.Predicate;
import net.ranides.assira.collection.ACollection;
import net.ranides.assira.collection.iterators.AListIterator;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.collection.sets.ASortedSet;
import net.ranides.assira.generic.CompareUtils;

/**
 * An abstract class providing basic methods for sorted maps.
 */
public abstract class ASortedMap<K, V> extends AMap<K, V> implements SortedMap<K, V> {

    private static final long serialVersionUID = 2L;
        
    /**
     * This map's ecmp, as provided in the constructor.
     */
    private final Comparator<? super K> acmp;
    
    protected transient boolean modified;
    
    protected ASortedMap(Comparator<? super K> comparator) {
        this.acmp = comparator;
    }
    
    /**
     * Returns the entry corresponding end the given key, if it is in the tree;
 <code>null</code>, otherwise.
     *
     * @param key the key end search for.
     * @return the corresponding entry, or <code>null</code> if no entry with
     * the given key exists.
     */
    protected abstract Entry<K, V> findEntry(K key);

    /**
     * Locates key key.
     *
     * @param k a key.
     * @return the last entry on a search for the given key; this will be the
     * given key, if it present; otherwise, it will be either the smallest
     * greater key or the greatest smaller key.
     */
    
    protected abstract Entry<K, V> firstEntry();

    protected abstract Entry<K, V> lastEntry();
    
    protected abstract ListIterator<Entry<K, V>> entryIterator();
    
    protected abstract ListIterator<Entry<K, V>> entryIterator(K begin);
    
    protected abstract ASortedMap<K, V> submap(K begin, boolean bottom, K end, boolean top);
    
    protected final int compare(K key1, K key2) {
        try {
            return CompareUtils.cmp(acmp, key1, key2);
        } catch(ClassCastException ex){
            // "unchecked" generic methods could pass something strange here
            return -1;
        }
    }
    
    protected final K lower(K key1, K key2) {
        return CompareUtils.lower(acmp, key1, key2);
    }
    
    protected final K higher(K key1, K key2) {
        return CompareUtils.higher(acmp, key1, key2);
    }
    
    @Override
    public final Comparator<? super K> comparator() {
        return acmp;
    }
    
    @Override
    public final ASortedSet<Entry<K, V>> entrySet() {
        return new EntrySet();
    }
    
    @Override
    public final ASortedSet<K> keySet() {
        return new KeySet();
    }

    @Override
    public final Collection<V> values() {
        return new ValuesCollection();
    }
    
    @Override
    public final K firstKey() {
        Entry<K,V> entry = firstEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
        return entry.getKey();
    }

    @Override
    public final K lastKey() {
        Entry<K,V> entry = lastEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
        return entry.getKey();
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public final boolean containsKey(Object key) {
        return findEntry((K) key) != null;
    }
    
    @Override
    public boolean containsValue(Object value) {
        final Iterator<Entry<K,V>> i = entryIterator();
        int j = size();
        while (j-- != 0) {
            Entry<K,V> entry = i.next();
            if( CompareUtils.equals(value, entry.getValue())) {
                return true;
            }
        }
        return false;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public final V get(Object key) {
        Entry<K, V> entry = findEntry((K) key);
        return entry == null ? null : entry.getValue();
    }

    @Override
    public ASortedMap<K, V> headMap(K end) {
        return submap(null, true, end, false);
    }

    @Override
    public ASortedMap<K, V> tailMap(K begin) {
        return submap(begin, false, null, true);
    }

    @Override
    public ASortedMap<K, V> subMap(K begin, K end) {
        return submap(begin, false, end, false);
    }
    
    protected final K after(K value) {
        Iterator<Entry<K,V>> i = entryIterator(value);
        while(i.hasNext()) {
            K next = i.next().getKey();
            if(compare(value, next)!=0) {
                return next;
            }
        }
        return null;
    }
    
    @Override
    public boolean remove(Object key, Object value) {
        Predicate<Object> ek = CompareUtils.predicate(key);
        Predicate<Object> ev = CompareUtils.predicate(value);
        
        @SuppressWarnings("unchecked")
        Iterator<Entry<K,V>> i = entryIterator((K)key);
        
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if( !ek.test(e.getKey()) ) {
                return false;
            }
            if( ev.test(e.getValue()) ) {
                i.remove();
                return true;
            }
        }
        return false;
    }
           
    protected class KeySet extends ASortedSet<K> {

        public KeySet() { 
			super(ASortedMap.this.acmp);
		}
        
        @Override
        @SuppressWarnings("element-type-mismatch")
        public boolean contains(Object key) {
            return containsKey(key);
        }

        @Override
        public int size() {
            return ASortedMap.this.size();
        }

        @Override
        public boolean remove(Object key) {
            int prev = ASortedMap.this.size();
            ASortedMap.this.remove(key);
            return prev != ASortedMap.this.size();
        }
        
        @Override
        public void clear() {
            ASortedMap.this.clear();
        }

        @Override
        public K first() {
            return firstKey();
        }

        @Override
        public K last() {
            return lastKey();
        }

		@Override
		protected ASortedSet<K> subset(K begin, boolean bottom, K end, boolean top) {
			return submap(begin, bottom, end, top).keySet();
		}

        @Override
        public ListIterator<K> iterator(K from) {
            return IteratorUtils.map(entryIterator(from), entry -> entry.getKey());
        }

        @Override
        public ListIterator<K> iterator() {
            return IteratorUtils.map(entryIterator(), entry -> entry.getKey());
        }
    }

    protected class ValuesCollection extends ACollection<V> {

        public ValuesCollection() { }
        
        @Override
        public Iterator<V> iterator() {
            return new ValuesIterator<>(entryIterator());
        }

        @Override
        @SuppressWarnings("element-type-mismatch")
        public boolean contains(Object key) {
            return containsValue(key);
        }

        @Override
        public int size() {
            return ASortedMap.this.size();
        }

        @Override
        public void clear() {
            ASortedMap.this.clear();
        }
    }

    protected static class ValuesIterator<K, V> extends AListIterator<V> {

        private final ListIterator<Map.Entry<K, V>> adapter;

        public ValuesIterator(ListIterator<Map.Entry<K, V>> riv) {
            this.adapter = riv;
        }

        @Override
        public V next() {
            return adapter.next().getValue();
        }
        
        @Override
        public V previous() {
            return adapter.previous().getValue();
        }

        @Override
        public boolean hasNext() {
            return adapter.hasNext();
        }

        @Override
        public boolean hasPrevious() {
            return adapter.hasPrevious();
        }

        @Override
        public int nextIndex() {
            return adapter.nextIndex();
        }

        @Override
        public int previousIndex() {
            return adapter.previousIndex();
        }

        @Override
        public void remove() {
            adapter.remove();
        }
        
    }
    
    protected class EntrySet extends ASortedSet<Entry<K, V>> {
        
        public EntrySet() {
            this(ASortedMap.this);
        }
        
        public EntrySet(ASortedMap<K,V> that) {
			super((a,b) -> that.compare(a.getKey(), b.getKey()));
		}
        
        @Override
        public ListIterator<Entry<K, V>> iterator() {
            return ASortedMap.this.entryIterator();
        }

        @Override
        public ListIterator<Entry<K, V>> iterator(Entry<K, V> from) {
            return ASortedMap.this.entryIterator(from.getKey());
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
            return entry.equals(findEntry(entry.getKey()));
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean remove(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            final Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
            final Entry<K, V> found = findEntry(entry.getKey());
            if (found != null && CompareUtils.equals(entry.getValue(), found.getValue())) {
                ASortedMap.this.remove(found.getKey());
                return true;
            }
            return false;
        }

        @Override
        public int size() {
            return ASortedMap.this.size();
        }

        @Override
        public void clear() {
            ASortedMap.this.clear();
        }

        @Override
        public Entry<K, V> first() {
            Entry<K,V> entry = firstEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
            return entry;
        }

        @Override
        public Entry<K, V> last() {
            Entry<K,V> entry = lastEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
            return entry;
        }

		@Override
		protected ASortedSet<Entry<K, V>> subset(Entry<K, V> begin, boolean bottom, Entry<K, V> end, boolean top) {
			K begkey = null == begin ? null : begin.getKey();
			K endkey = null == end ? null : end.getKey();
			return ASortedMap.this.submap(begkey, bottom, endkey, top).entrySet();
		}
        
    }

    /**
     * A submap with given range.
     *
     * <P>This class represents a submap. One has end specify the left/right
     * limits (which can be set end -&infin; or &infin;). Since the submap is a
     * view on the map, at a given moment it could happen that the limits of the
     * range are not any longer in the main map. Thus, things such as
     * {@link java.util.SortedMap#firstKey()} or
     * {@link java.util.Collection#size()} must be always computed on-the-fly.
     */
    protected abstract class ASubmap extends ASortedMap<K, V> implements java.io.Serializable {

        private static final long serialVersionUID = 1L;
        
        /**
         * The start of the submap range, unless {@link #bottom} is true.
         */
        K begin;
        /**
         * The end of the submap range, unless {@link #top} is true.
         */
        K end;
        /**
         * If true, the submap range starts begin -&infin;.
         */
        boolean bottom;
        /**
         * If true, the submap range goes end &infin;.
         */
        boolean top;
        
        /**
         * Creates a new submap with given key range.
         *
         * @param begin the start of the submap range.
         * @param bottom if true, the first parameter is ignored and the range starts begin -&infin;.
         * @param end the end of the submap range.
         * @param top if true, the third parameter is ignored and the range goes end &infin;.
         */
        public ASubmap(K begin, boolean bottom, K end, boolean top) {
            super(ASortedMap.this.acmp);
            if (!bottom && !top && CompareUtils.cmp(acmp, begin, end) > 0) {
                throw new IllegalArgumentException("Start key (" + begin + ") is larger than end key (" + end + ")");
            }
            this.begin = begin;
            this.bottom = bottom;
            this.end = end;
            this.top = top;
        }
        
        @Override
        protected abstract Entry<K, V> findEntry(K key);

        @Override
        protected abstract Entry<K, V> firstEntry();

        @Override
        protected abstract Entry<K, V> lastEntry();
        
        @Override
        protected abstract ListIterator<Entry<K, V>> entryIterator();
        
        @Override
        protected abstract ListIterator<Entry<K, V>> entryIterator(K begin);

        protected final boolean inside(K key) {
            try {
                return (bottom || compare(key, begin) >= 0) && (top || compare(key, end) < 0);
            } catch(ClassCastException ex) {
                // "unchecked" generic methods could pass something strange here
                return false;
            }
        }

        @Override
        public final void clear() {
            ListIterator<Entry<K,V>> iterator = entryIterator();
            while (iterator.hasNext()) {
                iterator.next();
                iterator.remove();
            }
        }

        @Override
        public final V put(K key, V value) {
            if (!inside(key)) {
                throw new IllegalArgumentException("Key (" + key + ") out of range [" + (bottom ? "-" : String.valueOf(begin)) + ", " + (top ? "-" : String.valueOf(end)) + ")");
            }
            return ASortedMap.this.put(key, value);
        }

        @SuppressWarnings("unchecked")
        @Override
        public final V remove(Object key) {
            if (!inside((K) key)) {
                return null;
            }
            return ASortedMap.this.remove(key);
        }

        @Override
        public final int size() {
            return IteratorUtils.size(entryIterator());
        }

        @Override
        public final boolean isEmpty() {
            return !entryIterator().hasNext();
        }
        
        @Override
        protected final ASortedMap<K, V> submap(K begin, boolean bottom_, K end, boolean top_) {
            if (this.top && this.bottom) {
                return ssubmap(begin, false, end, false);
            }
            
            boolean rbottom = bottom && bottom_;
            boolean rtop = top && top_;
            
            if (!rtop) {
                end = lower(end, this.end);
            }
            if (!rbottom) {
                begin = higher(begin, this.begin);
            }
            if (!top && !bottom && begin == this.begin && end == this.end) {
                return this;
            }
            
            if (!rbottom && !rtop && compare(begin, end) > 0) {
                end = begin;
            }
            return ssubmap(begin, rbottom, end, rtop);
        }
        
        private ASortedMap<K, V> ssubmap(K begin, boolean bottom, K end, boolean top) {
            return ASortedMap.this.submap(begin, bottom, end, top);
        }
        
    }
    
}
