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

/**
 * Set of short numbers that is optimized towards clustered distributions.
 * The implementation keeps the atomic information about intervals of numbers,
 * hence this set can hold billions of elements as short as
 * they form clusters (short consecutive runs). The main application of this
 * class is in collision detection arrays, e.g. to aid in generation of unique
 * IDs that are roughly sequential but possibly cyclic (process IDs, packet IDs)
 * with ID recycling and gap filling.
 * <p>
 * Caution: descending iterators aren't particularly well tested.
 *
 * @author Dawid Kurzyniec
 */

public class ShortIntervalSet extends AbstractShortSortedSet implements Serializable {

    private static class Entry extends AbstractShortInterval {

        private static final boolean RED = false;
        private static final boolean BLACK = true;

        private short first;
        private short last;
        private Entry parent, left, right;
        private boolean color;

        Entry(short first, short last) {
            //assert (first <= last);
            this.first = first;
            this.last = last;
        }

        protected short getFirst() { return first; }
        protected short getLast() { return last; }

        // entry is never empty
        public short first() { return first; }
        public short last() { return last; }

        // like simple interval (complement = empty set)
        public short min() { return first; }
        public short max() { return last; }
    }

    transient Entry root;
    transient short size;
    transient int intervalCount;
    transient int modCount;

    final short min, max;

    /**
     * Creates a new set of shorts.
     */
    public ShortIntervalSet() {
        this(Short.MIN_VALUE, Short.MAX_VALUE);
    }

    public ShortIntervalSet(short min, short max) {
        this.min = min;
        this.max = max;
    }

    public ShortIntervalSet(ShortCollection c) {
        this();
        addAll(c);
    }

    public ShortIntervalSet(ShortSet c) {
        this(c.min(), c.max());
        addAll(c);
    }

    public short min() {
        return min;
    }

    public short max() {
        return max;
    }

    public int intervalCount() {
        return intervalCount;
    }

    public short size64() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Removes all elements from the set.
     */
    public void clear() {
        root = null;
        intervalCount = 0;
        size = 0;
    }

//    /**
//     * Find the first interval that is either adjacent to the l, contains it,
//     * or have all values less than it, and return all the intervals to the
//     * right of the found one, including the found one. If "l" is bigger than
//     * any number in the set, the whole set will be returned.
//     */
//    private SortedSet getInsertionPoint(short e) {
//        Short eobj = new Short(e);
//        return baseReverseSet.tailSet(eobj);
//    }
//
    /**
     * Adds an element to the set if it is not already present.
     * @param e the element to add
     *
     * @return true is the element was added
     */
    public boolean add(short n) {
        if (n < min || n > max) return false;

        Entry e = getInsertionPoint(n);
        if (e == null) {
            // n is greater than any number currently in the set
            // [1234]..n=7 -> [1234]..[7]
            insertRight(new Entry(n, n), getLastEntry());
            size++;
            return true;
        }

        if (n < e.first-1) {
            // n=4.[789] -> [4]..[789]
            insertLeft(new Entry(n, n), e);
            size++;
            return true;
        }
        else if (n == e.first-1) {
            // n=4[567] -> [4567]
            e.first--;
            size++;
            return true;
        }
        else if (n <= e.last) {
            // [5 n=6 7] -> no change
            return false;
        }

        // so, n is at the left of the first interval. Maybe join is needed.
        Entry next = successor(e);
        if (next != null && n == next.first-1) {
            // [234]n=5[678] -> [2345678]
            e.last = next.last;
            delete(next);
            size++;
            return true;
        }
        else {
            // [234]n=5 -> [2345]
            // [234]n=5.[78] -> [2345].[78]
            e.last++;
            size++;
            return true;
        }
    }

    public boolean addInterval(short first, short last) {
        if (first > last) return false;
        if (first == last) return add(first);
        if (first < min) first = min;
        if (last > max) last = max;

        Entry e = getInsertionPoint(first);
        if (e == null) {
            // interval is greater than any number currently in the set
            // [1234]..{789} -> [1234]..[789]
            insertRight(new Entry(first, last), getLastEntry());
            size += (short)(last-first+1);
            return true;
        }

        if (last < e.first-1) {
            // first=2 . last=4.[789] -> [234]..[789]
            insertLeft(new Entry(first, last), e);
            size += (short)(last-first+1);
            return true;
        }
        else if (last <= e.last) {
            if (first >= e.first) {
                // [5 first=6 .. last=8 9] -> no change
                return false;
            }
            else {
                // first=2 .. [4 last=5 6] -> [2..6]
                size += (short)(e.first-first);
                e.first = first;
                return true;
            }
        }

        // so, last is at the left of the first interval. we need to remove
        // all offending intervals and resize the first interval. Let's start by
        // expanding it to the left, then we will have to worry only about
        // the right hand side
        Entry base = e;
        if (first < base.first) {
            size += (base.first-first);
            base.first = first;
        }

        e = successor(e);
        while (e != null) {
            if (last < e.first-1) {
                // .. last . [567] . -> last] . [567]
                size += (short)(last-base.last);
                base.last = last;
                return true;
            }
            size -= (short)(e.last-e.first+1);
            if (last <= e.last) {
                // .. [56 last=7 8] -> [ ... 5678]
                size += (short)(e.last-base.last);
                base.last = e.last;
                delete(e);
                return true;
            }
            else {
                e = deleteAndAdvance(e);
            }
        }

        size += (short)(last-base.last);
        base.last = last;
        return true;
    }

    public boolean addAll(ShortCollection c) {
        if (c == this) return false;
        if (c instanceof SubView) {
            SubView s = (SubView)c;
            if (s.base == this) return false;
        }
        else if (c instanceof ComplementSubView) {
            ComplementSubView s = (ComplementSubView)c;
            if (s.base == this) {
                return addInterval(s.min(), s.max());
            }
        }
        return super.addAll(c);
    }

    public boolean remove(short n) {
        if (n < min || n > max) return false;
        Entry e = getEntry(n);
        if (e == null) return false;
        if (e.first == e.last) {
            delete(e);
        }
        else if (n == e.first) {
            // shrink from the left
            e.first++;
        }
        else if (n == e.last) {
            // shrink from the right
            e.last--;
        }
        else {
            // need to split
            short last = e.last;
            e.last = (short)(n-1);
            insertRight(new Entry((short)(n+1), last), e);
        }
        size--;
        return true;
    }

    public boolean removeInterval(short first, short last) {
        if (first > last) return false;
        if (first < min) first = min;
        if (last > max) last = max;
        if (first == last) return remove(first);
        Entry e = getCeilingEntry(first);
        if (e == null) return false;
        boolean modified = false;
        if (first > e.first) {
            if (last < e.last) {
                // [23 first=4 last=6 7] -> [23]..[7]  (cut from the middle)
                Entry newe = new Entry((short)(last+1), e.last);
                e.last = (short)(first-1);
                insertRight(newe, e);
                size -= (short)(last-first+1);
                return true;
            }
            else {
                // [23 first=4 last=6] -> [23] (chop off the tail)
                size -= (short)(first-e.last);
                e.last = (short)(first-1);
                e = successor(e);
                if (e == null) return true;
                modified = true;
            }
        }
        while (last >= e.last) {
            e = deleteAndAdvance(e);
            if (e == null) return true;
            modified = true;
        }

        if (last >= e.first) {
            size -= (short)(last-e.first+1);
            e.first = (short)(last+1);
            return true;
        }

        return modified;
    }

    public boolean removeAll(ShortCollection c) {
        if (c == this) {
            boolean modified = !isEmpty();
            clear();
            return modified;
        }
        else if (c instanceof SubView) {
            SubView s = (SubView)c;
            if (s.base == this) {
                return removeInterval(s.min(), s.max());
            }
        }
        else if (c instanceof ComplementSubView) {
            ComplementSubView s = (ComplementSubView)c;
            if (s.base == this) {
                return false;
            }
        }
        return super.removeAll(c);
    }

    /**
     * Checks whether the set contains a given element
     *
     * @param n the element
     * @return true if the set contains n, false otherwise
     */
    public boolean contains(short n) {
        if (n < min || n > max) return false;
        return getEntry(n) != null;
    }

    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;
        // find a interval that may possibly contain it, and check if it does
        Entry e = getEntry(first);
        return (e != null && e.last >= last);
    }

    public ShortInterval enclosingInterval(short e) {
        if (e < min || e > max) return null;
        return getEntry(e);
    }

    public short lower(short n) {
        if (n == min) throw new NoSuchElementException();
        return floor((short)(n-1));
    }

    public short floor(short n) {
        if (n < min) throw new NoSuchElementException();
        Entry e = getFloorEntry(n);
        if (e == null) throw new NoSuchElementException();
        return (n <= e.last) ? n : e.last;
    }

    public short higher(short n) {
        if (n == max) throw new NoSuchElementException();
        return ceiling((short)(n+1));
    }

    public short ceiling(short n) {
        if (n > max) throw new NoSuchElementException();
        Entry e = getCeilingEntry(n);
        if (e == null) throw new NoSuchElementException();
        return (n >= e.first) ? n : e.first;
    }

    public Iterator intervalIterator() {
        return new ForwardIntervalIterator(getFirstEntry());
    }

    private class ForwardIntervalIterator implements Iterator {
        Entry cursor;
        Entry lastRet;
        ForwardIntervalIterator(Entry cursor) {
            this.cursor = cursor;
        }
        public boolean hasNext() {
            return cursor != null;
        }
        public Object next() {
            if (cursor == null) throw new NoSuchElementException();
            lastRet = cursor;
            cursor = successor(cursor);
            return lastRet;
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            // if removal strictly internal, it swaps places with a successor
            size += (short)(cursor.last-cursor.first+1);
            if (lastRet.left != null && lastRet.right != null) cursor = lastRet;
            delete(lastRet);
            lastRet = null;
        }
    }

    // overrides remove()
    public ShortIterator iterator() {
        return new ForwardItemIterator();
    }

    private class ForwardItemIterator extends ForwardIntervalItemIterator {
        ForwardItemIterator() {
            super(new ForwardIntervalIterator(getFirstEntry()));
        }

        public void remove() {
            if (!lastRetValid) throw new IllegalStateException();
            // if last elem from prev interval, or first elem of curr
            // interval, then no structural changes to the RBTree
            boolean restructured = (currInterval != null && lastRet > currInterval.first());
            ShortIntervalSet.this.remove(lastRet);
            lastRetValid = false;
            if (restructured) {
                it = new ForwardIntervalIterator(getHigherEntry(lastRet));
            }
        }
    }

    public Iterator descendingIntervalIterator() {
        return new ReverseIntervalIterator(getLastEntry());
    }

    private class ReverseIntervalIterator implements Iterator {
        Entry cursor;
        Entry lastRet;
        ReverseIntervalIterator(Entry cursor) {
            this.cursor = cursor;
        }
        public boolean hasNext() {
            return cursor != null;
        }
        public Object next() {
            if (cursor == null) throw new NoSuchElementException();
            lastRet = cursor;
            cursor = predecessor(cursor);
            return lastRet;
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            // if removal strictly internal, it swaps places with a successor
            size += (cursor.last-cursor.first+1);
            if (lastRet.left != null && lastRet.right != null) cursor = lastRet;
            delete(lastRet);
            lastRet = null;
        }
    }

    // overrides remove()
    public ShortIterator descendingIterator() {
        return new ReverseItemIterator();
    }

    private class ReverseItemIterator extends ReverseIntervalItemIterator {
        ReverseItemIterator() {
            super(new ReverseIntervalIterator(getLastEntry()));
        }

        public void remove() {
            if (!lastRetValid) throw new IllegalStateException();
            // if last elem from prev interval, or first elem of curr
            // interval, then no structural changes to the RBTree
            boolean restructured = (currInterval != null && lastRet < currInterval.last());
            ShortIntervalSet.this.remove(lastRet);
            lastRetValid = false;
            if (restructured) {
                it = new ReverseIntervalIterator(getLowerEntry(lastRet));
            }
        }
    }

    public short first() {
        Entry r = getFirstEntry();
        if (r == null) throw new NoSuchElementException();
        return r.first;
    }

    public short last() {
        Entry r = getLastEntry();
        if (r == null) throw new NoSuchElementException();
        return r.last;
    }

    public short pollFirst() {
        Entry e = getFirstEntry();
        if (e == null) throw new NoSuchElementException();
        short first = e.first;
        if (e.first == e.last) {
            delete(e);
        }
        else {
            e.first++;
        }
        size--;
        return first;
    }

    public short pollLast() {
        Entry e = getLastEntry();
        if (e == null) throw new NoSuchElementException();
        short last = e.last;
        if (e.first == e.last) {
            delete(e);
        }
        else {
            e.last--;
        }
        size--;
        return last;
    }

    public ShortInterval firstInterval() {
        return getFirstEntry();
    }

    public ShortInterval lastInterval() {
        return getLastEntry();
    }

    public ShortInterval ceilingInterval(short n) {
        return getCeilingEntry(n);
    }

    public ShortInterval floorInterval(short n) {
        return getFloorEntry(n);
    }

    public ShortInterval higherInterval(short n) {
        return getHigherEntry(n);
    }

    public ShortInterval lowerInterval(short n) {
        return getLowerEntry(n);
    }

    public ShortInterval pollFirstInterval() {
        Entry e = getFirstEntry();
        if (e == null) return null;
        short first = e.first, last = e.last;
        delete(e);
        size -= (last-first+1);
        return ShortCollections.interval(first, last);
    }

    public ShortInterval pollLastInterval() {
        Entry e = getLastEntry();
        if (e == null) return null;
        short first = e.first, last = e.last;
        delete(e);
        size -= (last-first+1);
        return ShortCollections.interval(first, last);
    }

    public ShortSortedSet subSet(short first, short last) {
        if (first == min && last == max) return this;
        if (first < min) first = min;
        if (last > max) last = max;
        return new SubView(this, first, last);
    }

    public ShortSet complementSet() {
        return new ComplementSubView(this, min, max);
    }

    static class SubView extends AbstractSubView implements Serializable {
        SubView(ShortIntervalSet base, short min, short max) {
            super(base, min, max);
        }
        public boolean addAll(ShortCollection c) {
            if (c == this) {
                return false;
            }
            else if (c instanceof ShortIntervalSet) {
                if (c == base) return false;
            }
            else if (c instanceof SubView) {
                SubView s = (SubView)c;
                if (s.base == this) {
                    return false;
                }
            }
            else if (c instanceof ComplementSubView) {
                ComplementSubView s = (ComplementSubView)c;
                if (s.base == this.base) {
                    return addInterval(s.min(), s.max());
                }
            }
            return super.addAll(c);
        }
        public boolean removeAll(ShortCollection c) {
            if (c == this) {
                boolean modified = !isEmpty();
                clear();
                return modified;
            }
            else if (c instanceof ShortIntervalSet) {
                if (c == base) return removeInterval(min(), max());
            }
            else if (c instanceof SubView) {
                SubView s = (SubView)c;
                if (s.base == this) {
                    return removeInterval(s.min(), s.max());
                }
            }
            else if (c instanceof ComplementSubView) {
                ComplementSubView s = (ComplementSubView)c;
                if (s.base == this.base) {
                    return false;
                }
            }
            return super.removeAll(c);
        }
        public Iterator intervalIterator() {
            ShortIntervalSet lbase = (ShortIntervalSet)base;
            return new ForwardSubIntervalIterator(lbase, beg, end,
                                                  lbase.getCeilingEntry(beg));
        }
        public ShortIterator iterator() {
            ShortIntervalSet lbase = (ShortIntervalSet)base;
            return new ForwardSubItemIterator(lbase, beg, end);
        }
        public Iterator descendingIntervalIterator() {
            ShortIntervalSet lbase = (ShortIntervalSet)base;
            return new ReverseSubIntervalIterator(lbase, beg, end,
                                                  lbase.getFloorEntry(end));
        }
        public ShortIterator descendingIterator() {
            ShortIntervalSet lbase = (ShortIntervalSet)base;
            return new ReverseSubItemIterator(lbase, beg, end);
        }
        public ShortSet complementSet() {
            return new ComplementSubView((ShortIntervalSet)base, beg, end);
        }
        public ShortSortedSet subSet(short first, short last) {
            if (first == this.beg && last == this.end) return this;
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return base.subSet(first, last);
        }
    }

    static class ComplementSubView extends AbstractComplementSubView
                                   implements Serializable {
        ComplementSubView(ShortIntervalSet base, short beg, short end) {
            super(base, beg, end);
        }
        public boolean addAll(ShortCollection c) {
            if (c == this) {
                return false;
            }
            else if (c instanceof ShortIntervalSet) {
                if (c == base) return addInterval(beg, end);
            }
            else if (c instanceof SubView) {
                SubView s = (SubView)c;
                if (s.base == this) {
                    return addInterval(s.min(), s.max());
                }
            }
            else if (c instanceof ComplementSubView) {
                ComplementSubView s = (ComplementSubView)c;
                if (s.base == this.base) {
                    return false;
                }
            }
            return super.addAll(c);
        }
        public boolean removeAll(ShortCollection c) {
            if (c == this) {
                boolean modified = !isEmpty();
                clear();
                return modified;
            }
            else if (c instanceof ShortIntervalSet) {
                if (c == base) return removeInterval(min(), max());
            }
            else if (c instanceof SubView) {
                SubView s = (SubView)c;
                if (s.base == this) {
                    return removeInterval(s.min(), s.max());
                }
            }
            else if (c instanceof ComplementSubView) {
                ComplementSubView s = (ComplementSubView)c;
                if (s.base == this.base) {
                    return false;
                }
            }
            return super.removeAll(c);
        }
        public Iterator intervalIterator() {
            return new ForwardComplementSubIntervalIterator((ShortIntervalSet)base, beg, end);
        }
        public Iterator descendingIntervalIterator() {
            return new ReverseComplementSubIntervalIterator((ShortIntervalSet)base, beg, end);
        }
        public ShortSortedSet subSet(short first, short last) {
            if (first == this.beg && last == this.end) return this;
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return new ComplementSubView((ShortIntervalSet)base, first, last);
        }
        public ShortSet complementSet() {
            if (beg == Short.MIN_VALUE && end == Short.MAX_VALUE) return base;
            else return base.subSet(beg, end);
        }
    }

    private abstract static class AbstractSubIntervalIterator implements Iterator {
        protected final ShortIntervalSet base;
        protected final short min, max;
        protected ShortInterval curr, next;
        AbstractSubIntervalIterator(ShortIntervalSet base, short min, short max) {
            this.base = base;
            this.min = min;
            this.max = max;
        }
        public boolean hasNext() {
            return (next != null);
        }
        public Object next() {
            if (next == null) throw new NoSuchElementException();
            curr = next;
            next = fetchNext();
            return curr;
        }
        protected abstract ShortInterval fetchNext();

        protected ShortInterval fix(ShortInterval r) {
            short first = r.first();
            short last = r.last();
            if (first >= this.min && last <= this.max) {
                return r;
            }
            else {
                if (first < this.min) first = this.min;
                if (last > this.max) last = this.max;
                return ShortCollections.interval(first, last);
            }
        }
    }

    private static ShortInterval fix(ShortInterval r, short min, short max) {
        short first = r.first();
        short last = r.last();
        if (first >= min && last <= max) {
            return r;
        }
        else {
            if (first < min) first = min;
            if (last > max) last = max;
            return ShortCollections.interval(first, last);
        }
    }

    private static class ForwardSubIntervalIterator implements Iterator {
        final ShortIntervalSet base;
        Entry cursor;
        short first, last;
        Entry lastRet;
        ForwardSubIntervalIterator(ShortIntervalSet base, short first, short last,
                                   Entry e) {
            this.base = base;
            this.first = first;
            this.last = last;
            this.cursor = e;
        }
        public boolean hasNext() {
            return cursor != null && cursor.first <= last;
        }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            lastRet = cursor;
            cursor = successor(cursor);
            return fix(lastRet, first, last);
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            if (lastRet.last <= last) {
                // internal
                if (lastRet.left != null && lastRet.right != null) cursor = lastRet;
                base.delete(lastRet);
                lastRet = null;
            }
            else {
                // terminal
                cursor = null;
                base.removeInterval(lastRet.first, lastRet.last);
                lastRet = null;
            }
        }
    }

    private static class ForwardSubItemIterator extends ForwardIntervalItemIterator {
        ForwardSubItemIterator(ShortIntervalSet base, short first, short last) {
            super(new ForwardSubIntervalIterator(base, first, last,
                                                 base.getCeilingEntry(first)));
        }
        public void remove() {
            if (!lastRetValid) throw new IllegalStateException();
            // if last elem from prev interval, or first elem of curr
            // interval, then no structural changes to the RBTree
            ForwardSubIntervalIterator s = (ForwardSubIntervalIterator) it;
            boolean restructured;
            if (currInterval != null) {
                short cfirst = currInterval.first();
                short clast = currInterval.last();
                restructured = (lastRet > cfirst ||
                                cfirst == s.first || clast == s.last);
            }
            else {
                restructured = false;
            }
            s.base.remove(lastRet);
            lastRetValid = false;
            if (restructured) {
                it = new ForwardSubIntervalIterator(s.base, s.first, s.last,
                                                    s.base.getHigherEntry(lastRet));
            }
        }
    }

    private static class ReverseSubIntervalIterator implements Iterator {
        final ShortIntervalSet base;
        Entry cursor;
        short first, last;
        Entry lastRet;
        ReverseSubIntervalIterator(ShortIntervalSet base, short first, short last,
                                   Entry e) {
            this.base = base;
            this.first = first;
            this.last = last;
            this.cursor = e;
        }
        public boolean hasNext() {
            return cursor != null && cursor.last >= first;
        }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            lastRet = cursor;
            cursor = predecessor(cursor);
            return fix(lastRet, first, last);
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            if (lastRet.first >= first) {
                // internal
                if (lastRet.left != null && lastRet.right != null) cursor = lastRet;
                base.delete(lastRet);
                lastRet = null;
            }
            else {
                // terminal
                cursor = null;
                base.removeInterval(lastRet.first, lastRet.last);
                lastRet = null;
            }
        }
    }

    private static class ReverseSubItemIterator extends ReverseIntervalItemIterator {
        ReverseSubItemIterator(ShortIntervalSet base, short first, short last) {
            super(new ReverseSubIntervalIterator(base, first, last,
                                                 base.getFloorEntry(last)));
        }
        public void remove() {
            if (!lastRetValid) throw new IllegalStateException();
            // if last elem from prev interval, or first elem of curr
            // interval, then no structural changes to the RBTree
            ReverseSubIntervalIterator s = (ReverseSubIntervalIterator) it;
            boolean restructured;
            if (currInterval != null) {
                short cfirst = currInterval.first();
                short clast = currInterval.last();
                restructured = (lastRet < clast ||
                                cfirst == s.first || clast == s.last);
            }
            else {
                restructured = false;
            }
            s.base.remove(lastRet);
            lastRetValid = false;
            if (restructured) {
                it = new ReverseSubIntervalIterator(s.base, s.first, s.last,
                                                    s.base.getLowerEntry(lastRet));
            }
        }
    }

    private static class ForwardComplementSubIntervalIterator implements Iterator {
        final ShortIntervalSet base;
        final short min, max;
        ShortInterval prev;
        short cursor;
        Entry next;
        ShortInterval lastRet;
        ForwardComplementSubIntervalIterator(ShortIntervalSet base, short min, short max) {
            this.base = base;
            this.min = min;
            this.max = max;
            this.cursor = min;
            Entry e = base.getFloorEntry(min);
            if (e != null) {
                this.cursor = e.last > min ? e.last : min;
                this.next = successor(e);
            }
            else {
                this.cursor = min;
                this.next = base.getHigherEntry(min);
            }
        }
        public boolean hasNext() {
            return cursor < max;
        }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            short first = cursor > min ? (short)(cursor+1) : min;
            short last;
            if (next == null) {
                last = max;
                cursor = last;
            }
            else {
                last = (short)(next.first-1);
                if (last > max) last = max;
                cursor = next.last;
                next = successor(next);
            }
            lastRet = ShortCollections.interval(first, last);
            return lastRet;
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            base.addInterval(lastRet.first(), lastRet.last());
            lastRet = null;
            // tree structure may have changed
            next = base.getHigherEntry(cursor);
        }
    }

    private static class ReverseComplementSubIntervalIterator implements Iterator {
        final ShortIntervalSet base;
        final short min, max;
        ShortInterval prev;
        short cursor;
        Entry next;
        ShortInterval lastRet;
        ReverseComplementSubIntervalIterator(ShortIntervalSet base, short min, short max) {
            this.base = base;
            this.min = min;
            this.max = max;
            Entry e = base.getCeilingEntry(max);
            if (e != null) {
                this.cursor = e.first < max ? e.first : max;
                this.next = predecessor(e);
            }
            else {
                this.cursor = max;
                this.next = base.getLowerEntry(max);
            }
        }
        public boolean hasNext() {
            return cursor > min;
        }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            short first;
            short last = cursor < max ? (short)(cursor-1) : max;
            if (next == null) {
                first = min;
                cursor = first;
            }
            else {
                first = (short)(next.last+1);
                if (first < min) first = min;
                cursor = next.first;
                next = predecessor(next);
            }
            lastRet = ShortCollections.interval(first, last);
            return lastRet;
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            base.addInterval(lastRet.first(), lastRet.last());
            lastRet = null;
            // tree structure may have changed
            next = base.getLowerEntry(cursor);
        }
    }

    // internal RBTree stuff

    private Entry getEntry(short n) {
        Entry t = root;
        for (;;) {
            if (t == null) return null;
            if (n < t.first) t = t.left;
            else if (n > t.last) t = t.right;
            else return t;
        }
    }

    // returns the smallest entry that is either adjacent to n, includes n,
    // or is greater than n. (the first entry that may possibly be affected
    // by adding n into the tree).
    private Entry getInsertionPoint(short n) {
        return (n > Short.MIN_VALUE) ? getCeilingEntry((short)(n-1)) : getFirstEntry();
    }

    private Entry getHigherEntry(short n) {
        Entry t = root;
        if (t == null) return null;
        for (;;) {
            if (n < t.first) {
                if (t.left != null) t = t.left; else return t;
            }
            else {
                if (t.right != null) {
                    t = t.right;
                }
                else {
                    Entry parent = t.parent;
                    while (parent != null && t == parent.right) {
                        t = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
    }

    private Entry getFirstEntry() {
        Entry e = root;
        if (e == null) return null;
        while (e.left != null) e = e.left;
        return e;
    }

    private Entry getLastEntry() {
        Entry e = root;
        if (e == null) return null;
        while (e.right != null) e = e.right;
        return e;
    }
    private Entry getCeilingEntry(short n) {
        Entry e = root;
        if (e == null) return null;
        for (;;) {
            if (n < e.first) {
                if (e.left != null) e = e.left; else return e;
            }
            else if (n > e.last) {
                if (e.right != null) {
                    e = e.right;
                }
                else {
                    Entry p = e.parent;
                    while (p != null && e == p.right) {
                        e = p;
                        p = p.parent;
                    }
                    return p;
                }
            }
            else return e;
        }
    }

    private Entry getLowerEntry(short n) {
        Entry e = root;
        if (e == null) return null;
        for (;;) {
            if (n > e.last) {
                if (e.right != null) e = e.right; else return e;
            }
            else {
                if (e.left != null) {
                    e = e.left;
                }
                else {
                    Entry p = e.parent;
                    while (p != null && e == p.left) {
                        e = p;
                        p = p.parent;
                    }
                    return p;
                }
            }
        }
    }

    private Entry getFloorEntry(short n) {
        Entry e = root;
        if (e == null) return null;
        for (;;) {
            if (n > e.last) {
                if (e.right != null) e = e.right; else return e;
            }
            else if (n < e.first) {
                if (e.left != null) {
                    e = e.left;
                }
                else {
                    Entry p = e.parent;
                    while (p != null && e == p.left) {
                        e = p;
                        p = p.parent;
                    }
                    return p;
                }
            }
            else return e;
        }
    }



    private void insertLeft(Entry e, Entry where) {
        if (where == null) {
            root = e;
            intervalCount = 1;
            return;
        }
        else if (where.left == null) {
            where.left = e;
        }
        else {
            where = where.left;
            while (where.right != null) where = where.right;
            where.right = e;
        }
        e.parent = where;
        fixAfterInsertion(e);
        intervalCount++;
    }

    private void insertRight(Entry e, Entry where) {
        if (where == null) {
            root = e;
            intervalCount = 1;
            return;
        }
        else if (where.right == null) {
            where.right = e;
        }
        else {
            where = where.right;
            while (where.left != null) where = where.left;
            where.left = e;
        }
        e.parent = where;
        fixAfterInsertion(e);
        intervalCount++;
    }

    /**
     * Return the inorder successor, or null if no such
     */
    private static Entry successor(Entry e) {
        if (e.right != null) {
            for (e = e.right; e.left != null; e = e.left) {}
            return e;
        } else {
            Entry p = e.parent;
            while (p != null && e == p.right) {
                e = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * Return the inorder predecessor, or null if no such
     */
    private static Entry predecessor(Entry e) {
        if (e.left != null) {
            for (e = e.left; e.right != null; e = e.right) {}
            return e;
        }
        else {
            Entry p = e.parent;
            while (p != null && e == p.left) {
                e = p;
                p = p.parent;
            }
            return p;
        }
    }

    private Entry deleteAndAdvance(Entry e) {
        Entry next = (e.left == null || e.right == null) ? successor(e) : e;
        delete(e);
        return next;
    }

    /**
     * Delete the current node, and then rebalance the tree it is in
     * @param root the root of the current tree
     * @return the new root of the current tree. (Rebalancing
     * can change the root!)
     */
    private void delete(Entry e) {

        // handle case where we are only node
        if (e.left == null && e.right == null && e.parent == null) {
            root = null;
            intervalCount = 0;
            return;
        }
        // if strictly internal, swap places with a successor
        if (e.left != null && e.right != null) {
            Entry s = successor(e);
            e.first = s.first;
            e.last = s.last;
            e = s;
        }

        // Start fixup at replacement node (normally a child).
        // But if no children, fake it by using self

        if (e.left == null && e.right == null) {

            if (e.color == Entry.BLACK)
                fixAfterDeletion(e);

            // Unlink  (Couldn't before since fixAfterDeletion needs parent ptr)

            if (e.parent != null) {
                if (e == e.parent.left)
                    e.parent.left = null;
                else if (e == e.parent.right)
                    e.parent.right = null;
                e.parent = null;
            }

        }
        else {
            Entry replacement = e.left;
            if (replacement == null)
                replacement = e.right;

            // link replacement to parent
            replacement.parent = e.parent;

            if (e.parent == null)
                root = replacement;
            else if (e == e.parent.left)
                e.parent.left = replacement;
            else
                e.parent.right = replacement;

            e.left = null;
            e.right = null;
            e.parent = null;

            // fix replacement
            if (e.color == Entry.BLACK)
                fixAfterDeletion(replacement);

        }

        intervalCount--;
    }

    /**
     * Return color of node p, or BLACK if p is null
     * (In the CLR version, they use
     * a special dummy `nil' node for such purposes, but that doesn't
     * work well here, since it could lead to creating one such special
     * node per real node.)
     *
     */
    static boolean colorOf(Entry p) {
        return (p == null) ? Entry.BLACK : p.color;
    }

    /**
     * return parent of node p, or null if p is null
     */
    static Entry parentOf(Entry p) {
        return (p == null) ? null : p.parent;
    }

    /**
     * Set the color of node p, or do nothing if p is null
     */
    private static void setColor(Entry p, boolean c) {
        if (p != null) p.color = c;
    }

    /**
     * return left child of node p, or null if p is null
     */
    private static Entry leftOf(Entry p) {
        return (p == null) ? null : p.left;
    }

    /**
     * return right child of node p, or null if p is null
     */
    private static Entry rightOf(Entry p) {
        return (p == null) ? null : p.right;
    }

    /** From CLR */
    private final void rotateLeft(Entry e) {
        Entry r = e.right;
        e.right = r.left;
        if (r.left != null)
            r.left.parent = e;
        r.parent = e.parent;
        if (e.parent == null) root = r;
        else if (e.parent.left == e)
            e.parent.left = r;
        else
            e.parent.right = r;
        r.left = e;
        e.parent = r;
    }

    /** From CLR */
    private final void rotateRight(Entry e) {
        Entry l = e.left;
        e.left = l.right;
        if (l.right != null)
            l.right.parent = e;
        l.parent = e.parent;
        if (e.parent == null) root = l;
        else if (e.parent.right == e)
            e.parent.right = l;
        else
            e.parent.left = l;
        l.right = e;
        e.parent = l;
    }

    /** From CLR */
    private final void fixAfterInsertion(Entry e) {
        e.color = Entry.RED;
        Entry x = e;

        while (x != null && x != root && x.parent.color == Entry.RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == Entry.RED) {
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(y, Entry.BLACK);
                    setColor(parentOf(parentOf(x)), Entry.RED);
                    x = parentOf(parentOf(x));
                }
                else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(parentOf(parentOf(x)), Entry.RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateRight(parentOf(parentOf(x)));
                }
            }
            else {
                Entry y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == Entry.RED) {
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(y, Entry.BLACK);
                    setColor(parentOf(parentOf(x)), Entry.RED);
                    x = parentOf(parentOf(x));
                }
                else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(parentOf(parentOf(x)), Entry.RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = Entry.BLACK;
    }

    /** From CLR */
    private final Entry fixAfterDeletion(Entry e) {
        Entry x = e;
        while (x != root && colorOf(x) == Entry.BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry sib = rightOf(parentOf(x));
                if (colorOf(sib) == Entry.RED) {
                    setColor(sib, Entry.BLACK);
                    setColor(parentOf(x), Entry.RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }
                if (colorOf(leftOf(sib)) == Entry.BLACK &&
                    colorOf(rightOf(sib)) == Entry.BLACK) {
                    setColor(sib, Entry.RED);
                    x = parentOf(x);
                }
                else {
                    if (colorOf(rightOf(sib)) == Entry.BLACK) {
                        setColor(leftOf(sib), Entry.BLACK);
                        setColor(sib, Entry.RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(rightOf(sib), Entry.BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            }
            else {
                Entry sib = leftOf(parentOf(x));
                if (colorOf(sib) == Entry.RED) {
                    setColor(sib, Entry.BLACK);
                    setColor(parentOf(x), Entry.RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }
                if (colorOf(rightOf(sib)) == Entry.BLACK &&
                    colorOf(leftOf(sib)) == Entry.BLACK) {
                    setColor(sib, Entry.RED);
                    x = parentOf(x);
                }
                else {
                    if (colorOf(leftOf(sib)) == Entry.BLACK) {
                        setColor(rightOf(sib), Entry.BLACK);
                        setColor(sib, Entry.RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), Entry.BLACK);
                    setColor(leftOf(sib), Entry.BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }
        setColor(x, Entry.BLACK);
        return root;
    }

    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(intervalCount);
        for (Iterator itr = intervalIterator(); itr.hasNext();) {
            ShortInterval iv = (ShortInterval)itr.next();
            out.writeShort(iv.first());
            out.writeShort(iv.last());
        }
    }

    private void readObject(ObjectInputStream in)
        throws IOException, ClassNotFoundException
    {
        in.defaultReadObject();
        int intervalCount = in.readInt();
        for (int i=0; i<intervalCount; i++) {
            short first = in.readShort();
            short last = in.readShort();
            addInterval(first, last);
        }
    }
}
