/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.collections.ints;

import java.util.*;
import java.io.*;

/**
 * Convenience subclass for sorted int sets.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractIntSortedSet extends AbstractIntSet
                                            implements IntSortedSet {

    public boolean isEmpty() {
        return !intervalIterator().hasNext();
    }

    public int size64() {                         
//    public int size() {                         // PREPROC: except Int,Int
        int size=0;
        for (Iterator itr = intervalIterator(); itr.hasNext();) {
            size += ((IntInterval)itr.next()).size();
        }
        return size;
    }

    public int intervalCount() {
        int count = 0;
        for (Iterator itr = intervalIterator(); itr.hasNext();) count++;
        return count;
    }

    public int first() {
        if (isEmpty()) throw new NoSuchElementException();
        return firstInterval().first();
    }

    public int last() {
        if (isEmpty()) throw new NoSuchElementException();
        return lastInterval().last();
    }

    public int pollFirst() {
        int first = first();
        remove(first);
        return first;
    }

    public int pollLast() {
        int last = last();
        remove(last);
        return last;
    }

    public IntInterval firstInterval() {
        Iterator itr = intervalIterator();
        if (!itr.hasNext()) return null;
        return (IntInterval)itr.next();
    }

    public IntInterval lastInterval() {
        Iterator itr = descendingIntervalIterator();
        if (!itr.hasNext()) return null;
        return (IntInterval)itr.next();
    }

    public IntInterval pollFirstInterval() {
        Iterator itr = intervalIterator();
        if (!itr.hasNext()) return null;
        IntInterval r = (IntInterval)itr.next();
        itr.remove();
        return r;
    }

    public IntInterval pollLastInterval() {
        Iterator itr = descendingIntervalIterator();
        if (!itr.hasNext()) return null;
        IntInterval r = (IntInterval)itr.next();
        itr.remove();
        return r;
    }

    public boolean retainAll(IntCollection c) {
        if (c instanceof IntSortedSet) {
            IntSortedSet s = (IntSortedSet)c;
            boolean modified = false;
            modified |= removeAll(s.complementSet());
            if (s.min() > min()) {
                modified |= removeInterval(min(), (int)(s.min()-1));
            }
            if (s.max() < max()) {
                modified |= removeInterval((int)(s.max()+1), max());
            }
            return modified;
        }
        return super.retainAll(c);
    }

    public boolean retainInterval(int first, int last) {
        boolean modified = false;
        int min = min(), max = max();
        if (first > min) {
            modified |= removeInterval(min, (int)(first-1));
        }
        if (last < max) {
            modified |= removeInterval((int)(last+1), max);
        }
        return modified;
    }

    public int higher(int e) {
        if (e == Integer.MAX_VALUE) throw new NoSuchElementException();
        return tailSet((int)(e+1)).first();
    }

    public int ceiling(int e) {
        return tailSet(e).first();
    }

    public int lower(int e) {
        if (e == Integer.MIN_VALUE) throw new NoSuchElementException();
        return headSet((int)(e-1)).last();
    }

    public int floor(int e) {
        return headSet(e).last();
    }

    public IntSortedSet headSet(int last) {
        return subSet(Integer.MIN_VALUE, last);
    }

    public IntSortedSet tailSet(int first) {
        return subSet(first, Integer.MAX_VALUE);
    }

    public IntIterator iterator() {
        return new ForwardIntervalItemIterator(intervalIterator());
    }

    public IntIterator descendingIterator() {
        return new ReverseIntervalItemIterator(descendingIntervalIterator());
    }

    public String toCompactString() {
        Iterator itr = intervalIterator();
        StringBuffer buf = new StringBuffer();
        buf.append('[');
        while (itr.hasNext()) {
            buf.append(itr.next());
            if (itr.hasNext()) buf.append(',');
        }
        buf.append(']');
        return buf.toString();
    }

    protected static class ForwardIntervalItemIterator implements IntIterator {
        Iterator it;
        IntInterval currInterval;
        protected int cursor;
        protected int lastRet;
        protected boolean lastRetValid = false;
        ForwardIntervalItemIterator(Iterator it) {
            this.it = it;
        }
        public boolean hasNext() {
            return it.hasNext() || currInterval != null;
        }
        public int next() {
            if (currInterval == null) {
                // bootstrap, or eof
                // if eof, the following will throw NSE (as this method should)
                currInterval = (IntInterval)it.next();
                cursor = currInterval.first();
            }

            lastRet = cursor;
            lastRetValid = true;
            if (cursor < currInterval.last()) {
                cursor++;
            }
            else {
                if (it.hasNext()) {
                    currInterval = (IntInterval)it.next();
                    cursor = currInterval.first();
                }
                else {
                    currInterval = null;
                }
            }
            return lastRet;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    protected static class ReverseIntervalItemIterator implements IntIterator {
        Iterator it;
        IntInterval currInterval;
        protected int cursor;
        protected int lastRet;
        protected boolean lastRetValid = false;
        ReverseIntervalItemIterator(Iterator it) {
            this.it = it;
        }
        public boolean hasNext() {
            return it.hasNext() || currInterval != null;
        }
        public int next() {
            if (currInterval == null) {
                // bootstrap, or eof
                // if eof, the following will throw NSE (as this method should)
                currInterval = (IntInterval)it.next();
                cursor = currInterval.last();
            }

            lastRet = cursor;
            lastRetValid = true;
            if (cursor > currInterval.first()) {
                cursor--;
            }
            else {
                if (it.hasNext()) {
                    currInterval = (IntInterval)it.next();
                    cursor = currInterval.last();
                }
                else {
                    currInterval = null;
                }
            }
            return lastRet;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    protected abstract static class AbstractSubView extends AbstractIntSortedSet
                                                    implements Serializable {
        protected final IntSortedSet base;
        protected final int beg, end;
        protected AbstractSubView(IntSortedSet base, int beg, int end) {
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        public int min() {
            int min = base.min();
            return beg > min ? beg : min;
        }
        public int max() {
            int max = base.max();
            return end < max ? end : max;
        }
        public int size64() {                            
//        public int size() {                             // PREPROC: except Int,Int
            if (beg <= base.min() && end >= base.max()) {
                return base.size64();                     
//                return base.size();                     // PREPROC: except Int,Int
            }
            return super.size64();                        
//            return super.size();                        // PREPROC: except Int,Int
        }
        public int intervalCount() {
            if (beg <= base.min() && end >= base.max()) {
                return base.intervalCount();
            }
            return super.intervalCount();
        }
        public void clear() {
            removeInterval(beg, end);
        }
        public boolean add(int e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean addInterval(int first, int last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.addInterval(first, last);
        }
        public boolean remove(int e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean removeInterval(int first, int last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            return base.removeInterval(first, last);
        }
        public boolean contains(int e) {
            return (e < beg || e > end) ? false : base.contains(e);
        }
        public boolean containsInterval(int first, int last) {
            if (first > last) return true;
            if (first == last) return contains(first);
            if (first < this.beg || last > this.end) {
                return false;
            }
            return base.containsInterval(first, last);
        }
        public IntInterval enclosingInterval(int e) {
            if (e < beg || e > end) return null;
            return trim(base.enclosingInterval(e));
        }
        public IntInterval higherInterval(int e) {
            return trim(base.higherInterval(e));
        }
        public IntInterval ceilingInterval(int e) {
            return trim(base.ceilingInterval(e));
        }
        public IntInterval lowerInterval(int e) {
            return trim(base.lowerInterval(e));
        }
        public IntInterval floorInterval(int e) {
            return trim(base.floorInterval(e));
        }

        public abstract IntSortedSet subSet(int first, int last);

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();

        private IntInterval trim(IntInterval r) {
            int first = r.first();
            int last = r.last();
            if (first >= this.beg && last <= this.end) return r;
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return first <= last ? IntCollections.interval(first, last) : null;
        }
    }

    protected abstract static class AbstractComplementSubView extends AbstractIntSortedSet {
        protected final IntSortedSet base;
        protected final int beg, end;
        protected AbstractComplementSubView(IntSortedSet base, int beg, int end) {
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        public int min() {
            int min = base.min();
            return beg > min ? beg : min;
        }
        public int max() {
            int max = base.max();
            return end < max ? end : max;
        }
        public int size64() {                            
            if (beg <= base.min() && end >= base.max()) { 
                return end - beg + 1 - base.size64();     
            }                                             
            else {                                        
                return super.size64();                    
            }                                             
        }                                                 
        public int intervalCount() {
            if (beg <= base.min() && end >= base.max()) {
                int count = base.intervalCount();
                if (count == 0) return isEmpty() ? 0 : 1;
                count--;
                if (base.first() > min()) count++;
                if (base.last() < max()) count++;
                return count;
            }
            return super.intervalCount();
        }
        public boolean add(int e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean addInterval(int first, int last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.removeInterval(first, last);
        }
        public boolean remove(int e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean removeInterval(int first, int last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.addInterval(first, last);
        }
        public boolean contains(int e) {
            return (e < beg || e > end) ? false : !base.contains(e);
        }
        public boolean containsInterval(int first, int last) {
            if (first > last) return true;
            if (first == last) return contains(first);
            if (first < this.beg || last > this.end) return false;
            return !base.containsInterval(first, last);
        }
        public IntInterval enclosingInterval(int e) {
            if (e < beg || e > end) return null;
            if (base.contains(e)) return null;
            IntInterval l = base.lowerInterval(e);
            IntInterval h = base.higherInterval(e);
            int first = (l == null) ? Integer.MIN_VALUE : (int)(l.last()+1);
            int last = (h == null) ? Integer.MIN_VALUE : (int)(h.first()-1);
            return trim(first, last);
        }
        public IntInterval lowerInterval(int n) {
            IntInterval e = base.enclosingInterval(n);
            IntInterval l = base.lowerInterval(n);
            if (e != null) {
                int efirst = e.first();
                if (efirst == Integer.MIN_VALUE) return null;
                return trim(l == null ? Integer.MIN_VALUE : (int)(l.last()+1), (int)(efirst-1));
            }
            else {
                if (l == null) return null;
                int lfirst = l.first();
                if (lfirst == Integer.MIN_VALUE) return null;
                IntInterval ll = base.lowerInterval((int)(lfirst-1));
                return trim(ll == null ? Integer.MIN_VALUE : (int)(ll.last()+1), (int)(lfirst-1));
            }
        }
        public IntInterval floorInterval(int n) {
            IntInterval e = base.enclosingInterval(n);
            IntInterval l = base.lowerInterval(n);
            if (e != null) {
                // same as lower
                int efirst = e.first();
                if (efirst == Integer.MIN_VALUE) return null;
                return trim(l == null ? Integer.MIN_VALUE : (int)(l.last()+1), (int)(efirst-1));
            }
            else {
                int first = (l == null ? Integer.MIN_VALUE : (int)(l.last()+1));
                IntInterval h = base.higherInterval(n);
                int last = (h == null ? Integer.MAX_VALUE : (int)(h.first()-1));
                return trim(first, last);
            }
        }
        public IntInterval higherInterval(int n) {
            IntInterval e = base.enclosingInterval(n);
            IntInterval h = base.higherInterval(n);
            if (e != null) {
                int elast = e.last();
                if (elast == Integer.MAX_VALUE) return null;
                return trim((int)(elast+1), h == null ? Integer.MAX_VALUE : (int)(h.first()-1));
            }
            else {
                if (h == null) return null;
                int hlast = h.last();
                if (hlast == Integer.MAX_VALUE) return null;
                IntInterval hh = base.higherInterval((int)(hlast+1));
                return trim((int)(hlast+1), hh == null ? Integer.MAX_VALUE : (int)(hh.first()-1));
            }
        }
        public IntInterval ceilingInterval(int n) {
            IntInterval e = base.enclosingInterval(n);
            IntInterval h = base.higherInterval(n);
            if (e != null) {
                // same as lower
                int elast = e.last();
                if (elast == Integer.MAX_VALUE) return null;
                return trim((int)(elast+1), h == null ? Integer.MIN_VALUE : (int)(h.first()-1));
            }
            else {
                int last = (h == null ? Integer.MAX_VALUE : (int)(h.first()-1));
                IntInterval l = base.lowerInterval(n);
                int first = (l == null ? Integer.MIN_VALUE : (int)(l.last()+1));
                return trim(first, last);
            }
        }
        public void clear() {
            base.addInterval(beg, end);
        }

        private IntInterval trim(int first, int last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return first <= last ? IntCollections.interval(first, last) : null;
        }

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();
    }
}
