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

import net.ranides.assira.collection.sets.AIntSortedSet;
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.sets.ASortedSet;
import net.ranides.assira.collection.IntComparator;
import net.ranides.assira.collection.iterators.IntListIterator;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.collection.sets.IntSortedSet;
import net.ranides.assira.generic.CompareUtils;

/**
 * An abstract base class for sorted maps with primitive int key. 
 * Designed to avoid autoboxing.
 */
public abstract class AIntSortedMap<V> extends AIntMap<V> implements IntSortedMap<V> {

    private static final long serialVersionUID = 2L;
    
    /**
     * This map's comparator, as provided in the constructor.
     */
    private final Comparator<? super Integer> scmp;
    /**
     * This map's actual comparator; it may differ from
     * {@link #scmp} because it is always a type-specific
     * comparator, so it could be derived from the former by wrapping.
     */
    private transient IntComparator acmp;
    
    /**
     * The value of this variable remembers, after a
     * <code>put()</code> or a
     * <code>remove()</code>, whether the <em>domain</em> of the map has been
     * modified.
     */
    protected transient boolean modified;

    protected AIntSortedMap(Comparator<? super Integer> comparator) {
        scmp = comparator;
        acmp = IntComparator.wrap(scmp);
    }
    
        
    /**
     * Returns the entry corresponding to the given key, if it is in the tree;
     * <code>null</code>, otherwise.
     *
     * @param k the key to search for.
     * @return the corresponding entry, or <code>null</code> if no entry with
     * the given key exists.
     */
    protected abstract IntEntry<V> findEntry(int k);

    /**
     * Locates a 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 IntEntry<V> locateEntry(int k);
    
    protected abstract IntEntry<V> firstEntry();

    protected abstract IntEntry<V> lastEntry();
    
    protected abstract ListIterator<IntEntry<V>> entryIterator();
    
    protected abstract ListIterator<IntEntry<V>> entryIterator(int key);

    protected abstract IntSortedMap<V> submap(int begin, boolean bottom, int end, boolean top);

    
    protected final int compare(int a, int b) {
        return CompareUtils.cmp(acmp, a, b);
    }
    
    protected final int lower(boolean ia, int a, boolean ib, int b) {
        if(!ia) {
            return b;
        }
        if(!ib) {
            return a;
        }
        return CompareUtils.lower(acmp, a, b);
    }
    
    protected final int higher(boolean ia, int a, boolean ib, int b) {
        if(!ia) {
            return b;
        }
        if(!ib) {
            return a;
        }
        return CompareUtils.higher(acmp, a, b);
    }
    
    @Override
    public final IntComparator comparator() {
        return acmp;
    }
    
    /**
     * Returns a view of the portion of this sorted map whose keys are strictly
     * less than <code>toKey</code>.
     *
     * @see SortedMap#headMap(Object)
     */
    @Override
    public IntSortedMap<V> headMap(int end) {
        return submap(0, true, end, false);
    }

    /**
     * Returns a view of the portion of this sorted map whose keys are greater
     * than or equal to <code>fromKey</code>.
     *
     * @see SortedMap#tailMap(Object)
     */
    @Override
    public IntSortedMap<V> tailMap(int begin) {
        return submap(begin, false, 0, true);
    }
    
    /**
     * Returns a view of the portion of this sorted map whose keys range from
     * <code>fromKey</code>, inclusive, to <code>toKey</code>, exclusive.
     *
     * @see SortedMap#subMap(Object,Object)
     */
    @Override
    public IntSortedMap<V> subMap(int begin, int end) {
        return submap(begin, false, end, false);
    }

    
    @Override
    public final IntSortedMap<V> headMap(Integer end) {
        return submap(0, true, end, false);
    }

    @Override
    public final IntSortedMap<V> tailMap(Integer begin) {
        return submap(begin, false, 0, true);
    }

    @Override
    public final IntSortedMap<V> subMap(Integer begin, Integer end) {
        return submap(begin, false, end, false);
    }
    
    /**
     * @see SortedMap#firstKey()
     */
    @Override
    public final int firstIntKey() {
        IntEntry<V> entry = firstEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
        return entry.getIntKey();
    }

    /**
     * @see SortedMap#lastKey()
     */
    @Override
    public final int lastIntKey() {
        IntEntry<V> entry = lastEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
        return entry.getKey();
    }
    

    @Override
    public final Integer firstKey() {
        return firstIntKey();
    }

    @Override
    public final Integer lastKey() {
        return lastIntKey();
    }
    

    @Override
    public final IntSortedSet keySet() {
        return new KeySet();
    }

    @Override
    public final Collection<V> values() {
        return new ValuesCollection();
    }
    
    /**
     * Returns a type-specific sorted-set view of the mappings contained in this
     * map. Note that this specification strengthens the one given in the
     * corresponding type-specific unsorted map.
     *
     * @return a type-specific sorted-set view of the mappings contained in this
     * map.
     * @see #entrySet()
     */
    @Override
    public final ASortedSet<IntMap.IntEntry<V>> fastEntrySet() {
        return new IntEntrySet();
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    @Override
    public final ASortedSet<Map.Entry<Integer, V>> entrySet() {
        return new EntrySet();
    }

    @Override
    public final boolean containsKey(int key) {
        return null != findEntry(key);
    }
    
    @Override
    public final boolean containsValue(Object value) {
        final Iterator<IntEntry<V>> i = entryIterator();
        int j = size();
        while (j-- != 0) {
            IntEntry<V> entry = i.next();
            if( CompareUtils.equals(value, entry.getValue())) {
                return true;
            }
        }
        return false;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public final V get(int key) {
        IntEntry<V> entry = findEntry(key);
        return entry == null ? null : entry.getValue();
    }
    
    @Override
    public boolean remove(int key, Object value) {
        Predicate<Object> ev = CompareUtils.predicate(value);
        
        Iterator<IntEntry<V>> i = entryIterator(key);
        
        while (i.hasNext()) {
            IntEntry<V> e = i.next();
            if( key != e.getIntKey() ) {
                return false;
            }
            if( ev.test(e.getValue()) ) {
                i.remove();
                return true;
            }
        }
        return false;
    }
    
    private void readObject(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        istream.defaultReadObject();
        // we must restore on-the-fly the actualComparator
        acmp = IntComparator.wrap(scmp);
    }

    /**
     * A wrapper exhibiting the keys of a map.
     */
    protected class KeySet extends AIntSortedSet {

		public KeySet() {
			super(AIntSortedMap.this.acmp);
		}

        @Override
        public boolean contains(int k) {
            return containsKey(k);
        }

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

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

        @Override
        public int firstInt() {
            return firstIntKey();
        }

        @Override
        public int lastInt() {
            return lastIntKey();
        }

		@Override
		protected IntSortedSet subset(int begin, boolean bottom, int end, boolean top) {
			return AIntSortedMap.this.submap(begin, bottom, end, top).keySet();
		}

        @Override
        public IntListIterator iterator(int from) {
            return new KeySetIterator<>(entrySet().iterator(new BasicEntry<>(from, null)));
        }

        @Override
        public IntListIterator iterator() {
            return new KeySetIterator<>(entrySet().iterator());
        }
        
        @Override
        public boolean remove(int k) {
            int prev = AIntSortedMap.this.size();
            AIntSortedMap.this.remove(k);
            return prev != AIntSortedMap.this.size();
        }
    }

    /**
     * A wrapper exhibiting a map iterator as an iterator on keys.
     *
     * <P>To provide an iterator on keys, just create an instance of this class
     * using the corresponding iterator on entries.
     */
    protected static class KeySetIterator<V> implements IntListIterator {

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

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

        @Override
        public int nextInt() {
            return adapter.next().getKey();
        }

        @Override
        public boolean hasNext() {
            return adapter.hasNext();
        }
        
        @Override
        public int previousInt() {
            return adapter.previous().getKey();
        }

        @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();
        }
        
    }

    /**
     * A wrapper exhibiting the values of a map.
     */
    protected class ValuesCollection extends ACollection<V> {

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

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

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

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

    /**
     * A wrapper exhibiting a map iterator as an iterator on values.
     *
     * <P>To provide an iterator on values, just create an instance of this
     * class using the corresponding iterator on entries.
     */
    protected static class ValuesIterator<V> implements ListIterator<V> {

        private final ListIterator<IntEntry<V>> adapter;

        public ValuesIterator(ListIterator<IntEntry<V>> riv) {
            this.adapter = riv;
        }

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

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

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

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

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

        @Override
        public void set(V value) {
            throw new UnsupportedOperationException();
        }

        @Override
        public void add(V value) {
            throw new UnsupportedOperationException();
        }
        
        @Override
        public void remove() {
            adapter.remove();
        }
    }
    
    protected class IntEntrySet extends ASortedSet<IntEntry<V>> {
        
        protected IntEntrySet(AIntSortedMap<V> that) {
			super((a,b) -> that.compare(a.getIntKey(), b.getIntKey()));
		}

		public IntEntrySet() {
			this(AIntSortedMap.this);
		}

        @Override
        public ListIterator<IntEntry<V>> iterator() {
            return AIntSortedMap.this.entryIterator();
        }

        @Override
        public ListIterator<IntEntry<V>> iterator(IntEntry<V> from) {
            return AIntSortedMap.this.entryIterator(from.getIntKey());
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<Integer, V> entry = (Map.Entry<Integer, 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<Integer, V> entry = (Map.Entry<Integer, V>) object;
            final Entry<Integer, V> found = findEntry(entry.getKey());
            if (found != null && CompareUtils.equals(entry.getValue(), found.getValue())) {
                AIntSortedMap.this.remove(found.getKey());
                return true;
            }
            return false;
        }

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

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

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

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

		@Override
		protected ASortedSet<IntEntry<V>> subset(IntEntry<V> begin, boolean bottom, IntEntry<V> end, boolean top) {
			int begkey = bottom ? 0 : begin.getIntKey();
			int endkey = top ? 0 : end.getIntKey();
			return submap(begkey, bottom, endkey, top).fastEntrySet();
		}
		
    }
    
    protected class EntrySet extends ASortedSet<Entry<Integer, V>> {
        
        protected EntrySet(AIntSortedMap<V> that) {
			super((a,b) -> that.compare(a.getKey(), b.getKey()));
		}

		public EntrySet() {
			this(AIntSortedMap.this);
		}

        @SuppressWarnings("unchecked")
        @Override
        public ListIterator<Entry<Integer,V>> iterator() {
            return (ListIterator)AIntSortedMap.this.entryIterator();
        }

        @SuppressWarnings("unchecked")
        @Override
        public ListIterator<Entry<Integer,V>> iterator(Entry<Integer,V> from) {
            return (ListIterator)AIntSortedMap.this.entryIterator(from.getKey());
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<Integer, V> entry = (Map.Entry<Integer, 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<Integer, V> entry = (Map.Entry<Integer, V>) object;
            final Entry<Integer, V> found = findEntry(entry.getKey());
            if (found != null && CompareUtils.equals(entry.getValue(), found.getValue())) {
                AIntSortedMap.this.remove(found.getKey());
                return true;
            }
            return false;
        }

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

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

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

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

		@Override
		protected ASortedSet<Entry<Integer,V>> subset(Entry<Integer,V> begin, boolean bottom, Entry<Integer,V> end, boolean top) {
			int begkey = bottom ? 0 : begin.getKey();
			int endkey = top ? 0 : end.getKey();
			return 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 AIntSortedMap<V> implements java.io.Serializable {

        private static final long serialVersionUID = 1L;
        
        /**
         * The start of the submap range, unless {@link #bottom} is true.
         */
        int begin;
        /**
         * The end of the submap range, unless {@link #top} is true.
         */
        int 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(int begin, boolean bottom, int end, boolean top) {
            super(AIntSortedMap.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 IntEntry<V> findEntry(int key);

        @Override
        protected abstract IntEntry<V> locateEntry(int key);
        
        @Override
        protected abstract IntEntry<V> firstEntry();

        @Override
        protected abstract IntEntry<V> lastEntry();
        
        @Override
        protected abstract ListIterator<IntEntry<V>> entryIterator();
        
        @Override
        protected abstract ListIterator<IntEntry<V>> entryIterator(int begin);

        protected final boolean inside(int key) {
            return (bottom || compare(key, begin) >= 0) && (top || compare(key, end) < 0);
        }

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

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

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

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

        @Override
        public final boolean isEmpty() {
            return !entryIterator().hasNext();
        }
        
        @Override
        protected final IntSortedMap<V> submap(int begin, boolean bottom_, int 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(!top_, end, !top, this.end);
            }
            if (!rbottom) {
                begin = higher(!bottom_, begin, !bottom, 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 IntSortedMap<V> ssubmap(int begin, boolean bottom, int end, boolean top) {
            return AIntSortedMap.this.submap(begin, bottom, end, top);
        }
        
    }
  
}
