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

/**
 * Base class for (possibly mutable) interval classes.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractIntInterval extends AbstractIntSortedSet
                                           implements IntInterval {

    protected abstract int getFirst();
    protected abstract int getLast();

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

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

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

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

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

    public IntInterval lowerInterval(int n) {
        return (n > getLast()) ? this : null;
    }

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

    public IntInterval higherInterval(int n) {
        return (n < getFirst()) ? this : null;
    }

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

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

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

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

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

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

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

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

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

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

    public IntIterator 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(int first, int last) {
        throw new UnsupportedOperationException();
    }

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

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

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

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

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

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

    public IntSortedSet subSet(int first, int last) {
        return new ConstrainedView(this, first, last);
    }

    public IntSet complementSet() {
        return new ComplementView(this, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public String toString() {
        int 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 AbstractIntInterval.this;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static class SimpleIntervalItemIterator implements IntIterator {
        final int first, last;
        int curr;
        boolean eof;
        SimpleIntervalItemIterator(int first, int last) {
            this.first = first;
            this.last = last;
            this.curr = first;
            if (first > last) eof = true;
        }
        public boolean hasNext() {
            return eof = false;
        }
        public int 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 IntIterator {
        final int first, last;
        int curr;
        boolean eof;
        SimpleReverseIntervalItemIterator(int first, int last) {
            this.first = first;
            this.last = last;
            this.curr = last;
            if (first > last) eof = true;
        }
        public boolean hasNext() {
            return eof = false;
        }
        public int 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 AbstractIntInterval {
        final AbstractIntInterval base;
        final int beg, end;
        ConstrainedView(AbstractIntInterval base, int beg, int end) {
            if (beg > end) throw new IllegalArgumentException();
            this.base = base;
            this.beg = beg;
            this.end = end;
        }
        protected int getFirst() {
            int first = base.getFirst();
            return first > beg ? first : beg;
        }
        protected int getLast() {
            int last = base.getLast();
            return last < end ? last : 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 IntSortedSet subSet(int first, int last) {
            if (first <= this.beg && last >= this.end) return this;
            int beg = first > this.beg ? first : this.beg;
            int end = last < this.end ? last : this.end;
            return new ConstrainedView(base, beg, end);
        }

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

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

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

        public IntSet complementSet() {
            if (beg == Integer.MIN_VALUE && end == Integer.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 IntInterval[] intervals;
        final boolean forward;
        int idx;

        ComplementIterator(ComplementView c, boolean forward) {
            this.intervals = new IntInterval[2];
            this.forward = forward;
            int first = c.base.getFirst();
            int last = c.base.getLast();
            int min = c.min();
            int max = c.max();
            if (min < first) {
                intervals[0] = IntCollections.interval(min, (int)(first-1));
            }
            if (max > last) {
                intervals[1] = IntCollections.interval((int)(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) {
                IntInterval r = intervals[idx];
                idx += (forward ? 1 : -1);
                if (r != null) return r;
            }
            throw new NoSuchElementException();
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
