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

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

import java.util.*;

/**
 * Base class for (possibly mutable) interval classes.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractShortInterval extends AbstractShortSortedSet
                                           implements ShortInterval {

    protected abstract short getFirst();
    protected abstract short getLast();

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

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

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

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

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

    public ShortInterval lowerInterval(short n) {
        return (n > getLast()) ? this : null;
    }

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

    public ShortInterval higherInterval(short n) {
        return (n < getFirst()) ? this : null;
    }

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

    public int size() {                            
        short first = getFirst(), last = getLast(); 
        if (first > last) return 0;                
        return (int)(last - first + 1);            
    }                                              
                                                   
    public boolean isEmpty() {
        return getFirst() > getLast();
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    public ShortSortedSet subSet(short first, short last) {
        return new ConstrainedView(this, first, last);
    }

    public ShortSet complementSet() {
        return new ComplementView(this, Short.MIN_VALUE, Short.MAX_VALUE);
    }

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

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

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

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

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

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

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