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

import java.util.Comparator;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import net.ranides.assira.collection.sets.ASortedSet;
import net.ranides.assira.collection.AIntCollection;
import net.ranides.assira.collection.IntCollection;
import net.ranides.assira.collection.iterators.IntIterator;
import net.ranides.assira.collection.iterators.IntListIterator;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.generic.CompareUtils;

/**
 * An abstract class for sorted maps with primitive int values.
 */
public abstract class ASortedLookup<K> extends ALookup<K> implements SortedLookup<K> {

    private static final long serialVersionUID = 2L;
	
    private final Comparator<? super K> 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 ASortedLookup(Comparator<? super K> comparator) {
        this.acmp = comparator;
    }
	
	protected abstract LookupEntry<K> findEntry(K key);
	
	protected abstract LookupEntry<K> locateEntry(K key);
	
	protected abstract LookupEntry<K> firstEntry();
	
	protected abstract LookupEntry<K> lastEntry();
	
	protected abstract ListIterator<LookupEntry<K>> entryIterator();
	
	protected abstract ListIterator<LookupEntry<K>> entryIterator(K begin);
	
	protected abstract SortedLookup<K> 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);
    }
	
	/**
     * Returns the comparator associated with this sorted set, or null if it
     * uses its keys' natural ordering.
     *
     * <P>Note that this specification strengthens the one given in
     * {@link SortedMap#comparator()}.
     *
     * @see SortedMap#comparator()
     */
    @Override
    public final Comparator<? super K> comparator() {
		return acmp;
	}
	
	@SuppressWarnings({"unchecked", "rawtypes"})
    @Override
    public final ASortedSet<Entry<K, Integer>> entrySet() {
        return new EntrySetAdapter<>(this);
    }

    /**
     * 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<LookupEntry<K>> fastEntrySet() {
		return new EntrySet<>(this);
	} 
	
	@Override
    public final ASortedSet<K> keySet() {
        return new KeySet();
    }

    /**
     * Returns a type-specific sorted collection.
     * @return a type-specific collection view of the values contained in this map
     */
    @Override
    public final IntCollection values() {
        return new ValuesCollection();
    }
	
	@Override
	public final K firstKey() {
        LookupEntry<K> entry = firstEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
		return entry.getKey();
	}

	@Override
	public final K lastKey() {
        LookupEntry<K> entry = lastEntry();
        if(null == entry) {
            throw new NoSuchElementException();
        }
		return entry.getKey();
	}
	
	@Override
    public final boolean containsValue(int value) {
        ValueIterator iterator = new ValueIterator();
        int max = size();
        while (max-- != 0) {
            if (iterator.nextInt() == value) {
                return true;
            }
        }
        return false;
    }

    
	
	@SuppressWarnings("unchecked")
    @Override
    public final boolean containsKey(Object key) {
        return findEntry( (K)key) != null;
    }
	
	/**
     * Returns a view of the portion of this sorted map whose keys range from
     * <code>fromKey</code>, inclusive, to
     * <code>toKey</code>, exclusive.
     *
     * <P>Note that this specification strengthens the one given in
     * {@link SortedMap#subMap(Object,Object)}.
     *
     * @see SortedMap#subMap(Object,Object)
     */
    @Override
    public SortedLookup<K> subMap(K begin, K end) {
		return submap(begin, false, end, false);
	}

    /**
     * Returns a view of the portion of this sorted map whose keys are strictly
     * less than <code>toKey</code>.
     *
     * <P>Note that this specification strengthens the one given in
     * {@link SortedMap#headMap(Object)}.
     *
     * @see SortedMap#headMap(Object)
     */
    @Override
    public SortedLookup<K> headMap(K end) {
		return submap(null, true, end, false);
	}

    /**
     * Returns a view of the portion of this sorted map whose keys are greater
     * than or equal to
     * <code>fromKey</code>.
     *
     * <P>Note that this specification strengthens the one given in
     * {@link SortedMap#tailMap(Object)}.
     *
     * @see SortedMap#tailMap(Object)
     */
    @Override
    public SortedLookup<K> tailMap(K begin) {
		return submap(begin, false, null, true);
	}
	
	@SuppressWarnings("unchecked")
    @Override
    public final int getInt(Object key) {
        LookupEntry<K> entry = findEntry((K) key);
        return entry == null ? defRetValue : entry.getIntValue();
    }
	
    @SuppressWarnings("unchecked")
    @Override
    public final Integer get(Object key) {
        LookupEntry<K> entry = findEntry((K) key);
        return entry == null ? null : entry.getValue();
    }
	
	
	@Override
    public final Integer put(K key, Integer value) {
        int oldValue = put(key, value.intValue());
        return modified ? null : oldValue;
    }
    
	
	@Override
    public final Integer remove(Object key) {
        int oldValue = removeInt(key);
        return modified ? oldValue : null;
    }

    /**
     * A wrapper exhibiting the keys of a map.
     */
    protected class KeySet extends ASortedSet<K> {

		public KeySet() {
			super(ASortedLookup.this.comparator());
		}

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

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

        @Override
        public void clear() {
            ASortedLookup.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), e -> e.getKey());
        }

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

        @Override
        public boolean remove(Object value) {
            int prev = ASortedLookup.this.size();
            ASortedLookup.this.remove(value);
            return prev != ASortedLookup.this.size();
        }
        
        
    }
    
    /**
     * A wrapper exhibiting the values of a map.
     */
    protected class ValuesCollection extends AIntCollection {

        @Override
        public IntIterator iterator() {
            return new ValueIterator();
        }

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

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

        @Override
        public void clear() {
            ASortedLookup.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 class ValueIterator implements IntListIterator {

        private final ListIterator<LookupEntry<K>> delegate;

        public ValueIterator() {
            this.delegate = ASortedLookup.this.entryIterator();
        }

		@Override
        public int nextInt() {
            return delegate.next().getIntValue();
        }

        @Override
        public int previousInt() {
            return delegate.previous().getIntValue();
        }

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

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

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

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

        @Override
        public void remove() {
            delegate.remove();
        }
		
    }
    
    protected static class EntrySetAdapter<K> extends ASortedSet<Map.Entry<K, Integer>> {
        
        private final ASortedLookup<K> that;

        public EntrySetAdapter(ASortedLookup<K> that) {
            super((a,b) -> that.acmp.compare(a.getKey(), b.getKey()));
            this.that = that;
        }
        
        @SuppressWarnings("unchecked")
        @Override
		public ListIterator<Map.Entry<K, Integer>> iterator() {
			return (ListIterator)that.entryIterator();
		}

        @SuppressWarnings("unchecked")
		@Override
		public ListIterator<Map.Entry<K, Integer>> iterator(Map.Entry<K, Integer> from) {
			return (ListIterator)that.entryIterator(from.getKey());
		}

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

		@SuppressWarnings("unchecked")
		@Override
		public boolean remove(Object object) {
			if (!(object instanceof Map.Entry)) {
				return false;
			}
			Map.Entry<K, Integer> entry = (Map.Entry<K, Integer>) object;
            if(null == entry.getValue()) {
                return false;
            }
			LookupEntry<K> found = that.findEntry(entry.getKey());
			if (found != null && found.getIntValue()==entry.getValue()) {
				that.removeInt(found.getKey());
                return true;
			}
			return false;
		}

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

		@Override
		public boolean isEmpty() {
			return !that.entryIterator().hasNext();
		}

		@Override
		public void clear() {
			that.clear();
		}

		@Override
		public LookupEntry<K> first() {
            LookupEntry<K> entry = that.firstEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
			return entry;
		}

		@Override
		public LookupEntry<K> last() {
            LookupEntry<K> entry = that.lastEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
			return entry;
		}

		@Override
		public ASortedSet<Map.Entry<K,Integer>> subSet(Map.Entry<K,Integer> begin, Map.Entry<K,Integer> end) {
            return subset(begin, false, end, false);
		}

		@Override
		public ASortedSet<Map.Entry<K,Integer>> headSet(Map.Entry<K,Integer> end) {
			return that.headMap(end.getKey()).entrySet();
		}

		@Override
		public ASortedSet<Map.Entry<K,Integer>> tailSet(Map.Entry<K,Integer> begin) {
			return that.tailMap(begin.getKey()).entrySet();
		}
		
		@Override
		protected ASortedSet<Map.Entry<K,Integer>> subset(Map.Entry<K,Integer> begin, boolean bottom, Map.Entry<K,Integer> end, boolean top) {
			K begkey = (null == begin) ? null : begin.getKey();
			K endkey = (null == end) ? null : end.getKey();
			return that.submap(begkey, bottom, endkey, top).entrySet();
		}
        
    }

	protected static class EntrySet<K> extends ASortedSet<LookupEntry<K>> {
        
        private final ASortedLookup<K> that;

		public EntrySet(ASortedLookup<K> that) {
            super((a,b) -> that.acmp.compare(a.getKey(), b.getKey()));
            this.that = that;
		}
		
		@Override
		public ListIterator<LookupEntry<K>> iterator() {
			return that.entryIterator();
		}

		@Override
		public ListIterator<LookupEntry<K>> iterator(LookupEntry<K> from) {
			return that.entryIterator(from.getKey());
		}

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

		@SuppressWarnings("unchecked")
		@Override
		public boolean remove(Object object) {
			if (!(object instanceof Map.Entry)) {
				return false;
			}
			Map.Entry<K, Integer> entry = (Map.Entry<K, Integer>) object;
            if(null == entry.getValue()) {
                return false;
            }
			LookupEntry<K> found = that.findEntry(entry.getKey());
			if (found != null && found.getIntValue()==entry.getValue()) {
				that.removeInt(found.getKey());
                return true;
			}
			return false;
		}

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

		@Override
		public boolean isEmpty() {
			return !that.entryIterator().hasNext();
		}

		@Override
		public void clear() {
			that.clear();
		}

		@Override
		public LookupEntry<K> first() {
            LookupEntry<K> entry = that.firstEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
			return entry;
		}

		@Override
		public LookupEntry<K> last() {
            LookupEntry<K> entry = that.lastEntry();
            if(null == entry) {
                throw new NoSuchElementException();
            }
			return entry;
		}

		@Override
		public ASortedSet<LookupEntry<K>> subSet(LookupEntry<K> begin, LookupEntry<K> end) {
            return subset(begin, false, end, false);
		}

		@Override
		public ASortedSet<LookupEntry<K>> headSet(LookupEntry<K> end) {
			return that.headMap(end.getKey()).fastEntrySet();
		}

		@Override
		public ASortedSet<LookupEntry<K>> tailSet(LookupEntry<K> begin) {
			return that.tailMap(begin.getKey()).fastEntrySet();
		}
		
		@Override
		protected ASortedSet<LookupEntry<K>> subset(LookupEntry<K> begin, boolean bottom, LookupEntry<K> end, boolean top) {
			K begkey = (null == begin) ? null : begin.getKey();
			K endkey = (null == end) ? null : end.getKey();
			return that.submap(begkey, bottom, endkey, top).fastEntrySet();
		}
	}
	
	/**
     * A submap with given range.
     *
     * <P>This class represents a submap. One has to specify the left/right
     * limits (which can be set to -&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 ASortedLookup<K> implements java.io.Serializable {

        private static final long serialVersionUID = 2L;
        /**
         * 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 from -&infin;.
         */
        boolean bottom;
        /**
         * If true, the submap range goes to &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 from -&infin;.
         * @param end the end of the submap range.
         * @param top if true, the third parameter is ignored and the range goes
         * to &infin;.
         */
        public ASubmap(K begin, boolean bottom, K end, boolean top) {
			super(ASortedLookup.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;
            this.defRetValue = ASortedLookup.this.defRetValue;
        }

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

        /**
         * Checks whether a key is in the submap range.
         *
         * @param key a key.
         * @return true if is the key is in the submap range.
         */
        protected final boolean inside(K key) {
            try {
                return (bottom || CompareUtils.cmp(acmp, key, begin) >= 0)
                    && (top || CompareUtils.cmp(acmp, key, end) < 0);
            } catch(ClassCastException ex) {
                // "unchecked" generic methods could pass something strange here
                return false;
            }
        }

		@Override
		protected abstract ListIterator<LookupEntry<K>> entryIterator();
		
		@Override
		protected abstract ListIterator<LookupEntry<K>> entryIterator(K begin);
		
		@Override
        protected abstract LookupEntry<K> findEntry(K key);

        @Override
        protected abstract LookupEntry<K> locateEntry(K key);
        
        @Override
        protected abstract LookupEntry<K> firstEntry();

        @Override
        protected abstract LookupEntry<K> lastEntry();

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

        @SuppressWarnings("unchecked")
        @Override
        public final int removeInt(Object key) {
            if (!inside((K) key)) {
				modified = false;
                return this.defRetValue;
            }
            int ret = ASortedLookup.this.removeInt(key);
            modified = ASortedLookup.this.modified;
            return ret;
        }
		
        @Override
        public final int size() {
            return IteratorUtils.size(entryIterator());
        }
		
		@Override
        public final boolean isEmpty() {
            return !entryIterator().hasNext();
        }

        @Override
        public final SortedLookup<K> headMap(K end) {
            if (top) {
                return submap(begin, bottom, end, false);
            }
            return CompareUtils.cmp(acmp, end, this.end) < 0 ? submap(begin, bottom, end, false) : this;
        }

        @Override
        public final SortedLookup<K> tailMap(K from) {
            if (bottom) {
                return submap(from, false, end, top);
            }
            return CompareUtils.cmp(acmp, from, this.begin) > 0 ? submap(from, false, end, top) : this;
        }

        @Override
        public final SortedLookup<K> subMap(K begin, K end) {
            return submap(begin, false, end, false);
        }
            
        @Override
		protected final SortedLookup<K> 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);
        }
        
        protected abstract SortedLookup<K> ssubmap(K begin, boolean bottom, K end, boolean top);

    }

}
