# import java util AbstractSet import java util Iterator public class In

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 import java.util.AbstractSet; import java.util.Iterator; public class IntSparseSet extends AbstractSet { private int low, high, n; int[] sparse, dense; public IntSparseSet(int l, int h) { low = l; high = h; sparse = new int[h-l]; dense = new int[h-l]; n = 0; for(int i=0;i= 0 && x < high-low){ if (sparse[x] >= n || dense[sparse[x]] != x) { dense[n] = x; sparse[x] = n; n++; return true; } } return false; } public void clear(){ n = 0; } public boolean contains(Object x){ x=(Integer)x-low; if((Integer)x >= 0 && (Integer)x < high-low) if(sparse[(Integer)x] < n) if(dense[sparse[(Integer)x]] == (Integer)x) return true; return false; } public boolean remove(Object x){ x=(Integer)x-low; try { if (sparse[(Integer) x] <= n - 1 && dense[sparse[(Integer) x]] == (Integer) x) { dense[sparse[(Integer) x]] = dense[n - 1]; sparse[dense[n - 1]] = sparse[(Integer) x]; n--; return true; } } catch(IndexOutOfBoundsException e) { return false; } return false; } public int size(){ return n; } private class Iterator1 implements Iterator{ int i = 0; public Integer next(){ i++; return dense[i-1]+low; } public void remove(){ IntSparseSet.this.remove(dense[i - 1] + low); } public boolean hasNext(){ return i < n; } } public Iterator iterator(){ return new Iterator1(); } }