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

/**
 * Convenience subclass for int sets.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public abstract class AbstractIntSet extends AbstractIntCollection
                                      implements IntSet {

    protected AbstractIntSet() {}

    public int min() {
        return Integer.MIN_VALUE;
    }

    public int max() {
        return Integer.MAX_VALUE;
    }

    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof IntSet)) return false;
        IntSet that = (IntSet)obj;
        if (this.size64() != that.size64()) return false; 
//        if (this.size() != that.size()) return false;   // PREPROC: except Int,Int
        try {
            return containsAll(that);
        }
        catch (Exception ignore) {
            return false;
        }
    }

    public int hashCode() {
        int h = 0;
        for (IntIterator itr = iterator(); itr.hasNext();) {
            h += hash(itr.next());
        }
        return h;
    }

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

    public boolean addAll(IntCollection c) {
        if (c instanceof IntInterval) {
            IntInterval r = (IntInterval)c;
            return addInterval(r.first(), r.last());
        }

        if (c instanceof IntSortedSet) {
            boolean modified = false;
            for (Iterator itr = ((IntSortedSet)c).intervalIterator(); itr.hasNext();) {
                IntInterval r = (IntInterval)itr.next();
                modified |= addInterval(r.first(), r.last());
            }
            return modified;
        }

        return super.addAll(c);
    }

    public boolean removeAll(IntCollection c) {
        if (c instanceof IntInterval) {
            IntInterval r = (IntInterval)c;
            return removeInterval(r.first(), r.last());
        }

        if (c instanceof IntSortedSet) {
            boolean modified = false;
            for (Iterator itr = ((IntSortedSet)c).intervalIterator(); itr.hasNext();) {
                IntInterval r = (IntInterval)itr.next();
                modified |= removeInterval(r.first(), r.last());
            }
            return modified;
        }

        if (size() <= c.size()) {
            return super.removeAll(c);
        }

        boolean modified = false;
        for (IntIterator itr = c.iterator(); itr.hasNext();) {
            modified |= remove(itr.next());
        }
        return modified;
    }

    public boolean retainAll(IntCollection c) {
        if (c instanceof IntInterval) {
            IntInterval r = (IntInterval)c;
            return retainInterval(r.first(), r.last());
        }
        return super.retainAll(c);
    }

    public boolean containsInterval(int first, int last) {
        if (first > last) return true;
        if (first == last) return contains(first);
        int min = min(), max = max();
        if (first < min || last > max) return false;
        int len = (int)(last-first+1);
        if (len > size()) return false;
        for (int e=first; e<=last; e++) {
            if (!contains(e)) return false;
        }
        return true;
    }

    public boolean addInterval(int first, int last) {
        int min = min(), max = max();
        if (first < min) first = min;
        if (last > max) last = max;
        boolean modified = false;
        for (int e = first; e<=last; e++) {
            modified |= add(e);
        }
        return modified;
    }

    public boolean removeInterval(int first, int last) {
        int min = min(), max = max();
        if (first < min) first = min;
        if (last > max) last = max;
        boolean modified = false;
        for (int e = first; e<=last; e++) {
            modified |= remove(e);
        }
        return modified;
    }

    public boolean retainInterval(int first, int last) {
        boolean modified = false;
        for (IntIterator itr = iterator(); itr.hasNext();) {
            int e = itr.next();
            if (e >= first && e <= last) {
                itr.remove();
                modified = true;
            }
        }
        return modified;
    }

    public IntSet complementSet() {
        return new ComplementView(this);
    }

    private final static int hash(int e) {
        return e;                                  
    }

    private static class ComplementView extends AbstractIntSet {
        final IntSet base;
        ComplementView(IntSet base) {
            this.base = base;
        }
        public int min() {
            return base.min();
        }
        public int max() {
            return base.max();
        }
        public int size64() {                         
            return max() - min() + 1 - base.size64();  
        }                                              
        public boolean contains(int e) {
            return !base.contains(e);
        }
        public boolean add(int e) {
            return base.remove(e);
        }
        public boolean remove(int e) {
            return base.add(e);
        }
        public boolean addAll(IntCollection c) {
            return base.removeAll(c);
        }
        public boolean removeAll(IntCollection c) {
            return base.addAll(c);
        }
        public boolean addInterval(int first, int last) {
            return base.removeInterval(first, last);
        }
        public boolean removeInterval(int first, int last) {
            return base.addInterval(first, last);
        }
        public void clear() {
            base.addInterval(min(), max());
        }
        public IntSet complementSet() {
            return base;
        }
        public IntIterator iterator() {
            return new ComplementIterator(base, min(), max());
        }
    }

    private static class ComplementIterator implements IntIterator {
        final IntSet base;
        final int min, max;
        int next;
        int curr;
        ComplementIterator(IntSet base, int min, int max) {
            this.base = base;
            this.min = min;
            this.max = max;
            this.next = min;
            fetchNext();
        }
        public boolean hasNext() {
            return next <= max;
        }
        public int next() {
            if (!hasNext()) throw new NoSuchElementException();
            curr = next++;
            fetchNext();
            return curr;
        }
        void fetchNext() {
            while (next <= max && base.contains(next)) next++;
        }
        public void remove() {
            base.add(curr);
        }
    }
}
