import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * An implementation of IntSet using an array of booleans, one per possible value in
 * the set, so that the array contains a true for exactly those values that are in the set.
 */
public class ArrayIntSet extends AbstractIntSet
{
    private boolean[] elements;
    private int min;
    private int max;
    
    public ArrayIntSet(int min, int max)
    {
	this.min = min;
	this.max = max;

	elements = new boolean[max - min + 1];
    }

    public int getRangeMin()
    {
	return min;
    }

    public int getRangeMax()
    {
	return max;
    }

    public void add(int n)
    {
	if (n >= min && n <= max)
	    {
		elements[n - min] = true;
	    }
    }

    public void remove(int n)
    {
	if (n >= min && n <= max)
	    {
		elements[n - min] = false;
	    }
    }

    public boolean contains(int n)
    {
	return n >= min && n <= max && elements[n - min];
    }

    /**
     * An iterator through this set.
     */
    public Iterator implements java.util.Iterator<Integer>
    {
	/**
	 * The current value (the one returned by the next call to next).
	 */
	private int curr;

	public Iterator()
	    {
		curr = getRangeMin();
		findNext(); // find next T in array of flags
	    }

	private void findNext()
	{
	    // sequential search for the next item in the set
	    // note that an instance of the inner class is associated with the
	    // instance of the outer class that created it and has access to its members,
	    // so getRangeMax and contains are invoked on the outer object here
	    while (curr <= getRangeMax() && !contains(curr))
		{
		    curr++;
		}
	}

	public Integer next()
	{
	    if (hasNext())
		{
		    int n = curr;
		    
		    curr++;
		    findNext();
		    
		    return n;
		}
	    else
		{
		    throw new NoSuchElementException();
		}
	}

	public boolean hasNext()
	{
	    return curr <= getRangeMax();
	}

	public void remove()
	{
	    // explicit reference to the outer object to use method with same name as
	    // method in the inner class
	    ArrayIntSet.this.remove(curr);
	}
    }
}