/*
 * 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.*;

/**
 * Base class for (possibly mutable) interval classes.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractLongInterval extends AbstractLongSortedSet
                                           implements LongInterval {

    protected abstract long getFirst();
    protected abstract long getLast();

    public long min() { return getFirst(); }
    public long max() { return getLast(); }

    public long first() {
        long first = getFirst();
        long last = getLast();
        if (first > last) throw new NoSuchElementException();
        return first;
    }
    public long last() {
        long first = getFirst();
        long last = getLast();
        if (first > last) throw new NoSuchElementException();
        return last;
    }

    public int intervalCount() { return isEmpty() ? 0 : 1; }

    public LongInterval firstInterval() {
        if (isEmpty()) throw new NoSuchElementException();
        return this;
    }

    public LongInterval lastInterval() {
        if (isEmpty()) throw new NoSuchElementException();
        return this;
    }

    public LongInterval lowerInterval(long n) {
        return (n > getLast()) ? this : null;
    }

    public LongInterval floorInterval(long n) {
        return (n >= getFirst()) ? this : null;
    }

    public LongInterval higherInterval(long n) {
        return (n < getFirst()) ? this : null;
    }

    public LongInterval ceilingInterval(long n) {
        return (n <= getLast()) ? this : null;
    }

    public long size64() {                         // PREPROC: Long,Int only
        long first = getFirst(), last = getLast(); // PREPROC: Long,Int only
        if (first > last) return 0;                // PREPROC: Long,Int only
        return last - first + 1;                   // PREPROC: Long,Int only
    }                                              // PREPROC: Long,Int only
                                                   // PREPROC: Long,Int only
//    public int size() {                            // PREPROC: except Long,Int
//        long first = getFirst(), last = getLast(); // PREPROC: except Long,Int
//        if (first > last) return 0;                // PREPROC: except Long,Int
//        return (int)(last - first + 1);            // PREPROC: except Long,Int
//    }                                              // PREPROC: except Long,Int
//                                                   // PREPROC: except Long,Int
    public boolean isEmpty() {
        return getFirst() > getLast();
    }

    public boolean contains(long e) {
        return (e >= getFirst() && e <= getLast());
    }

    public long higher(long e) {
        long first = getFirst();
        long last = getLast();
        if (e >= last || first > last) throw new NoSuchElementException();
        if (e < first) return first;
        return (long)(e+1);
    }

    public long ceiling(long e) {
        long first = getFirst();
        long last = getLast();
        if (e > last || first > last) throw new NoSuchElementException();
        if (e < first) return first;
        return e;
    }

    public long lower(long e) {
        long first = getFirst();
        long last = getLast();
        if (e <= first || first > last) throw new NoSuchElementException();
        if (e > last) return last;
        return (long)(e-1);
    }

    public long floor(long e) {
        long first = getFirst();
        long last = getLast();
        if (e < first || first > last) throw new NoSuchElementException();
        if (e > last) return last;
        return e;
    }

    public boolean containsInterval(long first, long last) {
        return first >= getFirst() && last <= getLast();
    }

    public LongInterval enclosingInterval(long e) {
        if (!contains(e)) throw new NoSuchElementException();
        return this;
    }

    public LongIterator iterator() {
        return new SimpleIntervalItemIterator(getFirst(), getLast());
    }

    public LongIterator descendingIterator() {
        return new SimpleReverseIntervalItemIterator(getFirst(), getLast());
    }

    public Iterator intervalIterator() {
        return new IntervalIterator();
    }

    public Iterator descendingIntervalIterator() {
        return new IntervalIterator();
    }

    public void clear() {
        throw new UnsupportedOperationException();
    }

    public boolean addInterval(long first, long last) {
        throw new UnsupportedOperationException();
    }

    public boolean removeInterval(long first, long last) {
        throw new UnsupportedOperationException();
    }

    public boolean retainInterval(long first, long last) {
        throw new UnsupportedOperationException();
    }

    public long pollFirst() {
        throw new UnsupportedOperationException();
    }

    public long pollLast() {
        throw new UnsupportedOperationException();
    }

    public LongInterval pollFirstInterval() {
        throw new UnsupportedOperationException();
    }

    public LongInterval pollLastInterval() {
        throw new UnsupportedOperationException();
    }

    public LongSortedSet subSet(long first, long last) {
        return new ConstrainedView(this, first, last);
    }

    public LongSet complementSet() {
        return new ComplementView(this, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public String toString() {
        long first = getFirst(), last = getLast();
        if (first > last) return "_";
        if (first == last) return String.valueOf(first);
        return "" + first + ".." + last;
    }

    class IntervalIterator implements Iterator {
        boolean eof;
        IntervalIterator() {
            if (getFirst() > getLast()) eof = true;
        }
        public boolean hasNext() { return !eof; }
        public Object next() {
            if (eof) throw new NoSuchElementException();
            eof = true;
            return AbstractLongInterval.this;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static class SimpleIntervalItemIterator implements LongIterator {
        final long first, last;
        long curr;
        boolean eof;
        SimpleIntervalItemIterator(long first, long last) {
            this.first = first;
            this.last = last;
            this.curr = first;
            if (first > last) eof = true;
        }
        public boolean hasNext() {
            return eof = false;
        }
        public long next() {
            if (eof) throw new NoSuchElementException();
            if (curr == last) {
                eof = true;
                return curr;
            }
            else {
                return curr++;
            }
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static class SimpleReverseIntervalItemIterator implements LongIterator {
        final long first, last;
        long curr;
        boolean eof;
        SimpleReverseIntervalItemIterator(long first, long last) {
            this.first = first;
            this.last = last;
            this.curr = last;
            if (first > last) eof = true;
        }
        public boolean hasNext() {
            return eof = false;
        }
        public long next() {
            if (eof) throw new NoSuchElementException();
            if (curr == first) {
                eof = true;
                return curr;
            }
            else {
                return curr--;
            }
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    protected static class ConstrainedView extends AbstractLongInterval {
        final AbstractLongInterval base;
        final long beg, end;
        ConstrainedView(AbstractLongInterval base, long beg, long end) {
            if (beg > end) throw new IllegalArgumentException();
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        protected long getFirst() {
            long first = base.getFirst();
            return first > beg ? first : beg;
        }
        protected long getLast() {
            long last = base.getLast();
            return last < end ? last : 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 LongSortedSet subSet(long first, long last) {
            if (first <= this.beg && last >= this.end) return this;
            long beg = first > this.beg ? first : this.beg;
            long end = last < this.end ? last : this.end;
            return new ConstrainedView(base, beg, end);
        }

        public LongSet complementSet() {
            return new ComplementView(base, beg, end);
        }
    }

    // up to two intervals
    protected static class ComplementView extends AbstractLongSortedSet {
        final AbstractLongInterval base;
        final long beg, end;
        ComplementView(AbstractLongInterval base, long beg, long end) {
            if (beg > end) throw new IllegalArgumentException();
            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 first() {
            long min = min();
            if (min < base.getFirst()) return min;
            long max = max();
            long last = base.getLast();
            if (last < max) return (long)(last+1);
            throw new NoSuchElementException();
        }
        public long last() {
            long max = max();
            if (max > base.getLast()) return max;
            long min = min();
            long first = base.getFirst();
            if (first > min) return (long)(first-1);
            throw new NoSuchElementException();
        }
        public boolean contains(long e) {
            return (e >= min() && e <= max() && !base.contains(e));
        }
        public boolean containsInterval(long first, long last) {
            if (first > last) return true;
            if (first == last) return contains(first);
            if (first < min() || last > max()) return false;
            long bfirst = base.getFirst();
            long blast = base.getLast();
            return (last < bfirst || blast < first);
        }
        public LongInterval enclosingInterval(long e) {
            if (!contains(e)) return null;
            // so must be beg <= e <= end, and (e < bfirst or e > blast)
            long bfirst = base.getFirst();
            long blast = base.getLast();
            if (e < bfirst) return LongCollections.interval(min(), (long)(bfirst-1));
            if (e > blast) return LongCollections.interval((long)(blast+1), max());
            return null;
        }
        public LongInterval higherInterval(long n) {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (bfirst > Long.MIN_VALUE && n < min && min<(long)(bfirst-1))
                return LongCollections.interval(min, (long)(bfirst-1));
            else if (blast < Long.MAX_VALUE && n <= blast && (long)(blast+1)<max)
                return LongCollections.interval((long)(blast+1), max);
            else return null;
        }
        public LongInterval ceilingInterval(long n) {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (bfirst > Long.MIN_VALUE && n < bfirst && (long)(bfirst-1)>min)
                return LongCollections.interval(min, (long)(bfirst-1));
            else if (blast < Long.MAX_VALUE && n <= max && end>(long)(blast+1))
                return LongCollections.interval((long)(blast+1), max);
            else return null;
        }
        public LongInterval lowerInterval(long n) {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (blast < Long.MAX_VALUE && n > max && max>(long)(blast+1))
                return LongCollections.interval((long)(blast+1), max);
            else if (bfirst > Long.MIN_VALUE && n >= bfirst && (long)(bfirst-1)>min)
                return LongCollections.interval(min, (long)(bfirst-1));
            else return null;
        }
        public LongInterval floorInterval(long n) {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (blast < Long.MAX_VALUE && n > blast && (long)(blast+1)<max)
                return LongCollections.interval((long)(blast+1), max);
            else if (bfirst > Long.MIN_VALUE && n >= min && min<(long)(bfirst-1))
                return LongCollections.interval(min, (long)(bfirst-1));
            else return null;
        }
        public LongInterval firstInterval() {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (bfirst > Long.MIN_VALUE && min < (long)(bfirst-1))
                return LongCollections.interval(min, (long)(bfirst-1));
            else if (blast < Long.MAX_VALUE && (long)(blast+1) < max)
                return LongCollections.interval((long)(blast+1), max);
            else return null;
        }
        public LongInterval lastInterval() {
            long bfirst = base.getFirst();
            long blast = base.getLast();
            long min = min();
            long max = max();
            if (blast < Long.MAX_VALUE && (long)(blast+1) < max)
                return LongCollections.interval((long)(blast+1), max);
            else if (bfirst > Long.MIN_VALUE && min < (long)(bfirst-1))
                return LongCollections.interval(min, (long)(bfirst-1));
            else return null;
        }
        public LongInterval pollFirstInterval() {
            throw new UnsupportedOperationException();
        }
        public LongInterval pollLastInterval() {
            throw new UnsupportedOperationException();
        }
        public int intervalCount() {
            int count = 0;
            if (min() < base.getFirst()) count++;
            if (max() > base.getLast()) count++;
            return count;
        }

        public LongSortedSet subSet(long first, long last) {
            if (first <= this.beg && last >= this.end) return this;
            long beg = first > this.beg ? first : this.beg;
            long end = last < this.end ? last : this.end;
            return new ComplementView(base, beg, end);
        }

        public LongSet complementSet() {
            if (beg == Long.MIN_VALUE && end == Long.MAX_VALUE) return base;
            else return new ConstrainedView(base, beg, end);
        }

        public Iterator intervalIterator() {
            return new ComplementIterator(this, true);
        }
        public Iterator descendingIntervalIterator() {
            return new ComplementIterator(this, false);
        }
    }

    private static class ComplementIterator implements Iterator {
        final LongInterval[] intervals;
        final boolean forward;
        int idx;

        ComplementIterator(ComplementView c, boolean forward) {
            this.intervals = new LongInterval[2];
            this.forward = forward;
            long first = c.base.getFirst();
            long last = c.base.getLast();
            long min = c.min();
            long max = c.max();
            if (min < first) {
                intervals[0] = LongCollections.interval(min, (long)(first-1));
            }
            if (max > last) {
                intervals[1] = LongCollections.interval((long)(last+1), max);
            }
            idx = (forward ? 0 : 1);
        }
        public boolean hasNext() {
            int nextIdx = this.idx;
            while (nextIdx >= 0 || nextIdx <= 2) {
                if (intervals[nextIdx] != null) return true;
                nextIdx += (forward ? 1 : -1);
            }
            return false;
        }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            while (idx >= 0 && idx <= 1) {
                LongInterval r = intervals[idx];
                idx += (forward ? 1 : -1);
                if (r != null) return r;
            }
            throw new NoSuchElementException();
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
