import java.util.AbstractSet;
import java.util.Iterator;
import java.util.ArrayList;


public class SparseSet<T extends Hintable> extends AbstractSet<T> {
    private ArrayList<T> dense;
    private int n;
    public SparseSet() {
        dense = new ArrayList<T>();
        n = 0;
    }


    public boolean add(T x){
        try{
            if(dense.get(((T)x).hint()) != (T)x)
            {
                dense.add(n, x);
                x.setHint(n);
                n++;
                return true;
            }
            else
                return false;
        }
        catch(IndexOutOfBoundsException e) {
            dense.add(n, x);
            x.setHint(n);
            n++;
            return true;
        }
    }

    public void clear(){
        n = 0;
    }

    public boolean contains(Object x){
        try {
            if (dense.get(((T) x).hint()) == (T) x)
                return true;
            else
                return false;
        }
        catch(IndexOutOfBoundsException e) {
            return false;
        }
    }

    public boolean remove(Object x){
        try {
            if (dense.get(((T)x).hint()) == (T)x)
            {
                n--;
                dense.set(((T)x).hint(), dense.get(n));
                dense.get(n).setHint(((T)x).hint());
                return true;
            }
            else
                return false;
        }
        catch(IndexOutOfBoundsException e) {
            return false;
        }
    }

    public int size(){
        return n;
    }


    private class Iterator1 implements Iterator<T>{
        int i = 0;

        public T next(){
            i++;
            return dense.get(i-1);
        }
        public void remove(){
            SparseSet.this.remove(dense.get(i-1));
        }
        public boolean hasNext(){
            return i < n;
        }
    }
    public Iterator<T> iterator(){
        return new Iterator1();
    }
}