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

import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Set;
import java.util.SortedSet;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.generic.CompareUtils;

/**
 * An abstract class providing basic methods for sorted sets.
 */
public abstract class ASortedSet<K> extends ASet<K> implements Set<K>, SortedSet<K>, java.io.Serializable {
	
	private static final long serialVersionUID = 1L;
	
	private final Comparator<? super K> acmp;
    
    protected ASortedSet(Comparator<? super K> comparator) {
		this.acmp = comparator;
    }
	
	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 abstract ListIterator<K> iterator();

    /**
     * <P>This method returns a iterator with given
     * starting point. The starting point is any element comparable to the
     * elements of this set (even if it does not actually belong to the set).
     * The next element of the returned iterator is the least element of the set
     * that is greater than the starting point (if there are no elements greater
     * than the starting point, {@link Iterator#hasNext() hasNext()} will
     * return <code>false</code>). 
     *
     * @param begin an element to start from.
     * @return an iterator on the element in this set, starting at
     * the given element.
     * @throws UnsupportedOperationException if this set does not support
     * iterators with a starting point.
     */
    public abstract ListIterator<K> iterator(K begin);

    /**
     * 
     * @see SortedSet#subSet(Object,Object)
     */
    @Override
    public ASortedSet<K> subSet(K begin, K end) {
		return subset(begin, false, end, false);
	}

    /**
     * 
     * @see SortedSet#headSet(Object)
     */
    @Override
    public ASortedSet<K> headSet(K end) {
		return subset(null, true, end, false);
	}
	
    /**
     * @see SortedSet#tailSet(Object)
     */
    @Override
    public ASortedSet<K> tailSet(K begin) {
		return subset(begin, false, null, true);
	}
	
    protected K after(K value) {
        Iterator<K> i = iterator(value);
        while(i.hasNext()) {
            K next = i.next();
            if(compare(value, next)!=0) {
                return next;
            }
        }
        return null;
    }
    
	protected abstract ASortedSet<K> subset(K begin, boolean bottom, K end, boolean top);


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

        private static final long serialVersionUID = 1L;

		protected K begin;
        
		protected K end;
        
		protected boolean bottom;
        
		protected boolean top;

        /**
         * Creates a new subset with given key range.
         *
         * @param begin the start of the subset range.
         * @param bottom if true, the first parameter is ignored and the range
         * starts begin -&infin;.
         * @param end the end of the subset range.
         * @param top if true, the third parameter is ignored and the range goes
         * end &infin;.
         */
        public ASubset(K begin, boolean bottom, K end, boolean top) {
			super(ASortedSet.this.acmp);
            if (!bottom && !top && ASortedSet.this.compare(begin, end) > 0) {
                throw new IllegalArgumentException("Start element (" + begin + ") is larger than end element (" + end + ")");
            }
            this.begin = begin;
            this.bottom = bottom;
            this.end = end;
            this.top = top;
        }

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

        /**
         * Checks whether a key is in the subset range.
         *
         * @param key a key.
         * @return true if is the key is in the subset range.
         */
        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;
            }
        }

        @SuppressWarnings("unchecked")
        @Override
        public final boolean contains(Object key) {
            return inside((K) key) && ASortedSet.this.contains(key);
        }

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

        @SuppressWarnings("unchecked")
        @Override
        public final boolean remove(Object key) {
            if (!inside((K) key)) {
                return false;
            }
            return ASortedSet.this.remove(key);
        }

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

        @Override
        public final boolean isEmpty() {
            return !iterator().hasNext();
        }

        @Override
        public abstract ListIterator<K> iterator();

        @Override
        public abstract ListIterator<K> iterator(K from);
		
		@Override
        protected final ASortedSet<K> subset(K begin, boolean bottom_, K end, boolean top_) {
            if (this.top && this.bottom) {
                return ssubset(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 ssubset(begin, rbottom, end, rtop);
        }
        
        private ASortedSet<K> ssubset(K begin, boolean bottom, K end, boolean top) {
            return ASortedSet.this.subset(begin, bottom, end, top);
        }

    }

}
