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

/**
 * Convenience subclass for sorted short sets.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractShortSortedSet extends AbstractShortSet
                                            implements ShortSortedSet {

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

    public int size() {                         
        short size=0;
        for (Iterator itr = intervalIterator(); itr.hasNext();) {
            size += ((ShortInterval)itr.next()).size();
        }
        return size;
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    public ShortSortedSet headSet(short last) {
        return subSet(Short.MIN_VALUE, last);
    }

    public ShortSortedSet tailSet(short first) {
        return subSet(first, Short.MAX_VALUE);
    }

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

    public ShortIterator descendingIterator() {
        return new ReverseIntervalItemIterator(descendingIntervalIterator());
    }

    public String toCompactString() {
        Iterator itr = intervalIterator();
        StringBuffer buf = new StringBuffer();
        buf.append('[');
        while (itr.hasNext()) {
            buf.append(itr.next());
            if (itr.hasNext()) buf.append(',');
        }
        buf.append(']');
        return buf.toString();
    }

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

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

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

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

    protected abstract static class AbstractSubView extends AbstractShortSortedSet
                                                    implements Serializable {
        protected final ShortSortedSet base;
        protected final short beg, end;
        protected AbstractSubView(ShortSortedSet base, short beg, short end) {
            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 int size() {                             
            if (beg <= base.min() && end >= base.max()) {
                return base.size();                     
            }
            return super.size();                        
        }
        public int intervalCount() {
            if (beg <= base.min() && end >= base.max()) {
                return base.intervalCount();
            }
            return super.intervalCount();
        }
        public void clear() {
            removeInterval(beg, end);
        }
        public boolean add(short e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean addInterval(short first, short last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.addInterval(first, last);
        }
        public boolean remove(short e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean removeInterval(short first, short last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            return base.removeInterval(first, last);
        }
        public boolean contains(short e) {
            return (e < beg || e > end) ? false : base.contains(e);
        }
        public boolean containsInterval(short first, short last) {
            if (first > last) return true;
            if (first == last) return contains(first);
            if (first < this.beg || last > this.end) {
                return false;
            }
            return base.containsInterval(first, last);
        }
        public ShortInterval enclosingInterval(short e) {
            if (e < beg || e > end) return null;
            return trim(base.enclosingInterval(e));
        }
        public ShortInterval higherInterval(short e) {
            return trim(base.higherInterval(e));
        }
        public ShortInterval ceilingInterval(short e) {
            return trim(base.ceilingInterval(e));
        }
        public ShortInterval lowerInterval(short e) {
            return trim(base.lowerInterval(e));
        }
        public ShortInterval floorInterval(short e) {
            return trim(base.floorInterval(e));
        }

        public abstract ShortSortedSet subSet(short first, short last);

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();

        private ShortInterval trim(ShortInterval r) {
            short first = r.first();
            short last = r.last();
            if (first >= this.beg && last <= this.end) return r;
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return first <= last ? ShortCollections.interval(first, last) : null;
        }
    }

    protected abstract static class AbstractComplementSubView extends AbstractShortSortedSet {
        protected final ShortSortedSet base;
        protected final short beg, end;
        protected AbstractComplementSubView(ShortSortedSet base, short beg, short end) {
            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 int intervalCount() {
            if (beg <= base.min() && end >= base.max()) {
                int count = base.intervalCount();
                if (count == 0) return isEmpty() ? 0 : 1;
                count--;
                if (base.first() > min()) count++;
                if (base.last() < max()) count++;
                return count;
            }
            return super.intervalCount();
        }
        public boolean add(short e) {
            if (e < beg || e > end) return false;
            return base.remove(e);
        }
        public boolean addInterval(short first, short last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.removeInterval(first, last);
        }
        public boolean remove(short e) {
            if (e < beg || e > end) return false;
            return base.add(e);
        }
        public boolean removeInterval(short first, short last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            if (first > last) return false;
            else return base.addInterval(first, last);
        }
        public boolean contains(short e) {
            return (e < beg || e > end) ? false : !base.contains(e);
        }
        public boolean containsInterval(short first, short last) {
            if (first > last) return true;
            if (first == last) return contains(first);
            if (first < this.beg || last > this.end) return false;
            return !base.containsInterval(first, last);
        }
        public ShortInterval enclosingInterval(short e) {
            if (e < beg || e > end) return null;
            if (base.contains(e)) return null;
            ShortInterval l = base.lowerInterval(e);
            ShortInterval h = base.higherInterval(e);
            short first = (l == null) ? Short.MIN_VALUE : (short)(l.last()+1);
            short last = (h == null) ? Short.MIN_VALUE : (short)(h.first()-1);
            return trim(first, last);
        }
        public ShortInterval lowerInterval(short n) {
            ShortInterval e = base.enclosingInterval(n);
            ShortInterval l = base.lowerInterval(n);
            if (e != null) {
                short efirst = e.first();
                if (efirst == Short.MIN_VALUE) return null;
                return trim(l == null ? Short.MIN_VALUE : (short)(l.last()+1), (short)(efirst-1));
            }
            else {
                if (l == null) return null;
                short lfirst = l.first();
                if (lfirst == Short.MIN_VALUE) return null;
                ShortInterval ll = base.lowerInterval((short)(lfirst-1));
                return trim(ll == null ? Short.MIN_VALUE : (short)(ll.last()+1), (short)(lfirst-1));
            }
        }
        public ShortInterval floorInterval(short n) {
            ShortInterval e = base.enclosingInterval(n);
            ShortInterval l = base.lowerInterval(n);
            if (e != null) {
                // same as lower
                short efirst = e.first();
                if (efirst == Short.MIN_VALUE) return null;
                return trim(l == null ? Short.MIN_VALUE : (short)(l.last()+1), (short)(efirst-1));
            }
            else {
                short first = (l == null ? Short.MIN_VALUE : (short)(l.last()+1));
                ShortInterval h = base.higherInterval(n);
                short last = (h == null ? Short.MAX_VALUE : (short)(h.first()-1));
                return trim(first, last);
            }
        }
        public ShortInterval higherInterval(short n) {
            ShortInterval e = base.enclosingInterval(n);
            ShortInterval h = base.higherInterval(n);
            if (e != null) {
                short elast = e.last();
                if (elast == Short.MAX_VALUE) return null;
                return trim((short)(elast+1), h == null ? Short.MAX_VALUE : (short)(h.first()-1));
            }
            else {
                if (h == null) return null;
                short hlast = h.last();
                if (hlast == Short.MAX_VALUE) return null;
                ShortInterval hh = base.higherInterval((short)(hlast+1));
                return trim((short)(hlast+1), hh == null ? Short.MAX_VALUE : (short)(hh.first()-1));
            }
        }
        public ShortInterval ceilingInterval(short n) {
            ShortInterval e = base.enclosingInterval(n);
            ShortInterval h = base.higherInterval(n);
            if (e != null) {
                // same as lower
                short elast = e.last();
                if (elast == Short.MAX_VALUE) return null;
                return trim((short)(elast+1), h == null ? Short.MIN_VALUE : (short)(h.first()-1));
            }
            else {
                short last = (h == null ? Short.MAX_VALUE : (short)(h.first()-1));
                ShortInterval l = base.lowerInterval(n);
                short first = (l == null ? Short.MIN_VALUE : (short)(l.last()+1));
                return trim(first, last);
            }
        }
        public void clear() {
            base.addInterval(beg, end);
        }

        private ShortInterval trim(short first, short last) {
            if (first < this.beg) first = this.beg;
            if (last > this.end) last = this.end;
            return first <= last ? ShortCollections.interval(first, last) : null;
        }

        public abstract Iterator intervalIterator();

        public abstract Iterator descendingIntervalIterator();
    }
}
