IntegerRange.java

/**
 * Copyright (C) 2008 Logan Johnson
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


import java.util.*;
import java.lang.reflect.Array;

/**
 * Efficiently stores an inclusive range of <code>Integer</code>s, and represents the range as a <code>Set</code>.
 *
 * TODO: implement <code>NavigableSet</code>
 * TODO: optionally exclude one or both boundaries
 *
 * @author Logan Johnson &lt;logan.johnson@gmail.com&gt;
 */
public class IntegerRange extends AbstractSet<Integer> implements SortedSet<Integer>, Comparable<IntegerRange> {
	
	private Integer min = null;
	private Integer max = null;

    public IntegerRange() {}

    public IntegerRange(Integer only) {
        add(only);
    }
    public IntegerRange(Integer min, Integer max) {
        add(min);
        add(max);
    }

    @Override
    public boolean add(Integer e) {
		boolean changed = false;
		if ( min == null || e < min ) {
			min = e;
			changed = true;
		}
		if ( max == null || e > max ) {
			max = e;
			changed = true;
		}
		return changed;
	}


	@Override
	public void clear() {
		this.min = null;
		this.max = null;
	}

	@Override
	public boolean contains(Object o) {
		if ( ! (o instanceof Integer)) {
			return false;
		}
		Integer i = (Integer)o;
		return ( i >= min && i <= max);
	}

	@Override
	public boolean isEmpty() {
		return ( min == null && max == null );
	}

	@Override
	public Iterator<Integer> iterator() {
		return new IntegerRangeIterator(this);
	}

    /**
     * @throws IllegalArgumentException if removal would not result in a contiguous range.
     */
    @Override
	public boolean remove(Object o) {
        if ( o == null ) {
            return false;
        }
        if ( (o instanceof Integer) ) {
            Integer i = (Integer)o;
            if ( i < min || i > max ) {
                return false;
            }
            if ( i.equals(min) ) {
                min++;
                return true;
            }
            if ( i.equals(max) ) {
                max--;
                return true;
            }
            throw new IllegalArgumentException("cannot remove an Integer from the interior of a range");
        }
        return false;
    }


    private SortedSet<IntegerRange> minimalRangeSet(Collection<?> c) {
        SortedSet<IntegerRange> rangeSet = new TreeSet<IntegerRange>();
        for ( Object o : c ) {
            if ( o == null ) {
                continue;
            }
            if ( !(o instanceof Integer) ) {
                continue;
            }
            Integer i = (Integer)o;

            // see if this integer can be appended or prepended to an existing range
            IntegerRange subRange = null;
            for ( IntegerRange r : rangeSet ) {
                if ( i == r.first()-1 || i == r.last()+1) {
                    subRange = r;
                    break;
                }
            }
            // if an existing range was found, use it.  otherwise create a new range
            // which will only contain the current integer.
            if ( subRange != null ) {
                rangeSet.remove(subRange);
            } else {
                subRange = new IntegerRange();
            }
            subRange.add(i);

            // if the updated range now abuts another range, they should be merged.
            IntegerRange mergeWith = null;
            for ( IntegerRange r : rangeSet ) {
                if ( subRange.first().equals(r.last()+1) || subRange.last().equals(r.first()-1) ) {
                    mergeWith = r;
                    break;
                }
            }
            if ( mergeWith != null ) {
                rangeSet.remove(mergeWith);
                subRange.add(mergeWith.first());
                subRange.add(mergeWith.last());
            }
            rangeSet.add(subRange);
        }
        return Collections.unmodifiableSortedSet(rangeSet);
    }

     /**
     * @throws IllegalArgumentException if removal would not result in a contiguous range.
     */
    @Override
	public boolean removeAll(Collection<?> c) {

        IntegerRange newRange = new IntegerRange(first(), last());

        SortedSet<IntegerRange> toRemove = new TreeSet<IntegerRange>(minimalRangeSet(c));
        boolean reduced = false;
        do {
            reduced = false;
            for ( IntegerRange r : toRemove ) {
                // if r is disjoint from newRange, do nothing
                if ( (r.last() < newRange.first()) || (r.first() > newRange.last()) ) {
                    continue;
                }
                // if r is entirely interior to newRange, do nothing
                if ( r.first() > newRange.first() && r.last() < newRange.last() ) {
                    continue;
                }

                // if r intersects the lower bound of newRange, subtract r from newRange
                if ( r.last() >= newRange.first() ) {
                    if ( r.last() < newRange.last() ) {
                        newRange = new IntegerRange(r.last()+1, newRange.last());
                    } else {
                        newRange = new IntegerRange();
                    }
                    reduced = true;
                }

                // if r intersects the upper bound of newRange, subtract r from newRange
                if ( r.first() <= newRange.last() ) {
                    if ( r.first() > newRange.first() ) {
                        newRange = new IntegerRange(newRange.first(), r.first()-1);
                    } else {
                        newRange = new IntegerRange();
                    }
                    reduced = true;
                }
            }
        } while ( reduced && !toRemove.isEmpty() );

        if ( !toRemove.isEmpty() ) {
            throw new IllegalArgumentException("Cannot remove interior subrange " + toRemove.first());
        }

        if ( !reduced ) {
            return false;
        }
        min = newRange.first();
        max = newRange.last();
        return true;
    }

	@Override
	public boolean retainAll(Collection<?> c) {
        SortedSet<IntegerRange> minRanges = minimalRangeSet(c);
        if ( minRanges.size() == 0 ) {
            clear();
            return true;
        }
        if ( minRanges.size() > 1 ) {
            throw new IllegalArgumentException("Retaining only disjoint sets would result in an invalid range");
        }
        boolean changed = false;
        IntegerRange r = minRanges.first();
        if ( r.first() != first() ) {
            min = r.first();
            changed = true;
        }
        if ( r.last() != last() ) {
            max = last();
            changed = true;
        }
        return changed;
    }

	@Override
	public int size() {
		if ( max == null || min == null ) {
			return 0;
		}
		return 1 + (max - min);
	}
	
	@Override
	public String toString() {
		return getClass().getSimpleName() + "[" + first() + "," + last() + "]";
	}

    @Override
    public Comparator<? super Integer> comparator() {
        return null;
    }

    @Override
    public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) {
        return new SubRange(fromElement, toElement-1);
    }

    @Override
    public SortedSet<Integer> headSet(Integer toElement) {
        return new SubRange(null, Math.min(last(),toElement-1));
    }

    @Override
    public SortedSet<Integer> tailSet(Integer integer) {
        return new SubRange(integer, null);
    }

    @Override
    public Integer first() {
        return min;
    }

    @Override
    public Integer last() {
        return max;
    }

    
    /**
     * IntegerRanges are compared based on their endpoints.
     * null ranges are less than non-null ranges.
     * empty ranges are less than non-empty ranges.
     * between two non-empty ranges, the range with the lower min is the lesser range.
     * between two non-empty ranges with equal minima, the range with the lower max is the lesser range.
     * two non-empty ranges with the samee minima and maxima are equal.
     */
    @Override
    public int compareTo(IntegerRange integerRange) {
        if ( integerRange == null ) {
            return 1;
        }
        if ( isEmpty() ) {
            if ( integerRange.isEmpty() ) {
                return 0;
            } else {
                return -1;
            }
        } 
        if ( integerRange.isEmpty() ) {
            return 1;
        }
        if ( first() < integerRange.first() ) {
            return -1;
        }
        if ( first().equals(integerRange.first()) ) {
            return last().compareTo(integerRange.last());
        }
        return 0;
    }

    private class SubRange extends IntegerRange implements SortedSet<Integer> {

        final private Integer initialMin;
        final private Integer initialMax;

        public SubRange(Integer min, Integer max) {
            this.initialMin = min;
            this.initialMax = max;
        }

        @Override
        public boolean add(Integer integer) {
            if ( contains(integer) ) {
                return false;
            } else {
                throw new IllegalArgumentException();
            }
        }

        @Override
        public boolean remove(Object o) {
            throw new UnsupportedOperationException("Cannot remove an element from a sub-range");
        }

        @Override
        public boolean addAll(Collection<? extends Integer> integers) {
            if ( containsAll(integers) ) {
                return false;
            } else {
                throw new IllegalArgumentException();
            }
        }

        @Override
        public void clear() {
            IntegerRange.this.removeAll(this);
        }
    }

    private static class IntegerRangeIterator implements Iterator<Integer> {
        final private IntegerRange range;
        final private Integer initialMin;
        final private Integer initialMax;
        private Integer currentValue;

        public IntegerRangeIterator(IntegerRange range) {
            this.range = range;
            this.initialMin = range.first();
            this.initialMax = range.last();
            currentValue = initialMin - 1;
        }
        @Override
        public boolean hasNext() {
            checkBounds();
            return ( currentValue < range.last() );
        }

        @Override
        public Integer next() {
            checkBounds();
            currentValue++;
            return currentValue;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Can't remove an object from a range");
        }

        private void checkBounds() {
            if ( ! (initialMin.equals(range.first()) && initialMax.equals(range.last())) ) {
                throw new ConcurrentModificationException();
            }
        }
    }
}