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

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

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

/**
 * Convenience subclass for sorted long sets.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractLongSortedSet extends AbstractLongSet
                                            implements LongSortedSet {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    public LongSortedSet headSet(long last) {
        return subSet(Long.MIN_VALUE, last);
    }

    public LongSortedSet tailSet(long first) {
        return subSet(first, Long.MAX_VALUE);
    }

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

    public LongIterator 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 LongIterator {
        Iterator it;
        LongInterval currInterval;
        protected long cursor;
        protected long lastRet;
        protected boolean lastRetValid = false;
        ForwardIntervalItemIterator(Iterator it) {
            this.it = it;
        }
        public boolean hasNext() {
            return it.hasNext() || currInterval != null;
        }
        public long next() {
            if (currInterval == null) {
                // bootstrap, or eof
                // if eof, the following will throw NSE (as this method should)
                currInterval = (LongInterval)it.next();
                cursor = currInterval.first();
            }

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

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

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

    protected abstract static class AbstractSubView extends AbstractLongSortedSet
                                                    implements Serializable {
        protected final LongSortedSet base;
        protected final long beg, end;
        protected AbstractSubView(LongSortedSet base, long beg, long end) {
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        public long min() {
            long min = base.min();
            return beg > min ? beg : min;
        }
        public long max() {
            long max = base.max();
            return end < max ? end : max;
        }
        public long size64() {                            // PREPROC: Long,Int only
//        public int size() {                             // PREPROC: except Long,Int
            if (beg <= base.min() && end >= base.max()) {
                return base.size64();                     // PREPROC: Long,Int only
//                return base.size();                     // PREPROC: except Long,Int
            }
            return super.size64();                        // PREPROC: Long,Int only
//            return super.size();                        // PREPROC: except Long,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(long e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean addInterval(long first, long 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(long e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean removeInterval(long first, long 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(long e) {
            return (e < beg || e > end) ? false : base.contains(e);
        }
        public boolean containsInterval(long first, long 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 LongInterval enclosingInterval(long e) {
            if (e < beg || e > end) return null;
            return trim(base.enclosingInterval(e));
        }
        public LongInterval higherInterval(long e) {
            return trim(base.higherInterval(e));
        }
        public LongInterval ceilingInterval(long e) {
            return trim(base.ceilingInterval(e));
        }
        public LongInterval lowerInterval(long e) {
            return trim(base.lowerInterval(e));
        }
        public LongInterval floorInterval(long e) {
            return trim(base.floorInterval(e));
        }

        public abstract LongSortedSet subSet(long first, long last);

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();

        private LongInterval trim(LongInterval r) {
            long first = r.first();
            long 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 ? LongCollections.interval(first, last) : null;
        }
    }

    protected abstract static class AbstractComplementSubView extends AbstractLongSortedSet {
        protected final LongSortedSet base;
        protected final long beg, end;
        protected AbstractComplementSubView(LongSortedSet base, long beg, long end) {
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        public long min() {
            long min = base.min();
            return beg > min ? beg : min;
        }
        public long max() {
            long max = base.max();
            return end < max ? end : max;
        }
        public long size64() {                            // PREPROC: Int,Long only
            if (beg <= base.min() && end >= base.max()) { // PREPROC: Int,Long only
                return end - beg + 1 - base.size64();     // PREPROC: Int,Long only
            }                                             // PREPROC: Int,Long only
            else {                                        // PREPROC: Int,Long only
                return super.size64();                    // PREPROC: Int,Long only
            }                                             // PREPROC: Int,Long only
        }                                                 // PREPROC: Int,Long only
        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(long e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean addInterval(long first, long 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(long e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean removeInterval(long first, long 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(long e) {
            return (e < beg || e > end) ? false : !base.contains(e);
        }
        public boolean containsInterval(long first, long 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 LongInterval enclosingInterval(long e) {
            if (e < beg || e > end) return null;
            if (base.contains(e)) return null;
            LongInterval l = base.lowerInterval(e);
            LongInterval h = base.higherInterval(e);
            long first = (l == null) ? Long.MIN_VALUE : (long)(l.last()+1);
            long last = (h == null) ? Long.MIN_VALUE : (long)(h.first()-1);
            return trim(first, last);
        }
        public LongInterval lowerInterval(long n) {
            LongInterval e = base.enclosingInterval(n);
            LongInterval l = base.lowerInterval(n);
            if (e != null) {
                long efirst = e.first();
                if (efirst == Long.MIN_VALUE) return null;
                return trim(l == null ? Long.MIN_VALUE : (long)(l.last()+1), (long)(efirst-1));
            }
            else {
                if (l == null) return null;
                long lfirst = l.first();
                if (lfirst == Long.MIN_VALUE) return null;
                LongInterval ll = base.lowerInterval((long)(lfirst-1));
                return trim(ll == null ? Long.MIN_VALUE : (long)(ll.last()+1), (long)(lfirst-1));
            }
        }
        public LongInterval floorInterval(long n) {
            LongInterval e = base.enclosingInterval(n);
            LongInterval l = base.lowerInterval(n);
            if (e != null) {
                // same as lower
                long efirst = e.first();
                if (efirst == Long.MIN_VALUE) return null;
                return trim(l == null ? Long.MIN_VALUE : (long)(l.last()+1), (long)(efirst-1));
            }
            else {
                long first = (l == null ? Long.MIN_VALUE : (long)(l.last()+1));
                LongInterval h = base.higherInterval(n);
                long last = (h == null ? Long.MAX_VALUE : (long)(h.first()-1));
                return trim(first, last);
            }
        }
        public LongInterval higherInterval(long n) {
            LongInterval e = base.enclosingInterval(n);
            LongInterval h = base.higherInterval(n);
            if (e != null) {
                long elast = e.last();
                if (elast == Long.MAX_VALUE) return null;
                return trim((long)(elast+1), h == null ? Long.MAX_VALUE : (long)(h.first()-1));
            }
            else {
                if (h == null) return null;
                long hlast = h.last();
                if (hlast == Long.MAX_VALUE) return null;
                LongInterval hh = base.higherInterval((long)(hlast+1));
                return trim((long)(hlast+1), hh == null ? Long.MAX_VALUE : (long)(hh.first()-1));
            }
        }
        public LongInterval ceilingInterval(long n) {
            LongInterval e = base.enclosingInterval(n);
            LongInterval h = base.higherInterval(n);
            if (e != null) {
                // same as lower
                long elast = e.last();
                if (elast == Long.MAX_VALUE) return null;
                return trim((long)(elast+1), h == null ? Long.MIN_VALUE : (long)(h.first()-1));
            }
            else {
                long last = (h == null ? Long.MAX_VALUE : (long)(h.first()-1));
                LongInterval l = base.lowerInterval(n);
                long first = (l == null ? Long.MIN_VALUE : (long)(l.last()+1));
                return trim(first, last);
            }
        }
        public void clear() {
            base.addInterval(beg, end);
        }

        private LongInterval trim(long first, long last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return first <= last ? LongCollections.interval(first, last) : null;
        }

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();
    }
}
