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();
}
}