import java.util.*; public class SparseSet { private int[] data; private int[] location; private int last; private int capacity; private Stack history; public SparseSet (int n){ data = new int[n]; location = new int[n]; last = -1; capacity = n; Arrays.fill(data,-1); Arrays.fill(location,-1); history = new Stack(); for (int i=0;i= capacity || i < 0) throw new SparseSetException("item "+ i +" out of range"); if (contains(i)) throw new SparseSetException("item "+ i +" already present"); last = last + 1; data[last] = i; location[i] = last; } // // add item for the 1st time. Used in initialisation // public void add(int i){ if (i >= capacity || i < 0) throw new SparseSetException("item "+ i +" out of range"); if (contains(i)) throw new SparseSetException("item "+ i +" already present"); swap(i,data[last+1]); last++; } // // add element i back into the set // public void add(int i,Stack change){ add(i); change.push(i); } public void remove(int i){ if (i >= capacity || i < 0) throw new SparseSetException("item "+ i +" out of range"); if (!contains(i)) throw new SparseSetException("item "+ i +" not present"); swap(i,data[last]); last--; } public void remove(int i,Stack change){ remove(i); change.push(i); } private void swap(int i,int j){ int loc_i = location[i]; int loc_j = location[j]; location[i] = loc_j; location[j] = loc_i; data[location[i]] = i; data[location[j]] = j; } public int get(int i){ if (i < 0 || i > last) throw new SparseSetException("item "+ i +" out of range"); return data[i]; } public void intersection(ArrayList N,Stack change){ int i=0; while (i <= last){ if (!N.contains(data[i])) remove(data[i],change); else i++; } } public void intersection(ArrayList N){ int i=0; while (i <= last){ if (!N.contains(data[i])) remove(data[i]); else i++; } } public int first(){return data[0];} public int card(){return last + 1;} public int capacity(){return capacity;} public boolean isEmpty(){return last == -1;} public boolean contains(int i){return 0 <= location[i] && location[i] <= last && data[location[i]] == i;} public void pushWorld(){history.push(last);} public void popWorld(){last = history.pop();} public String toString(){ String s = "["; if (last >= 0) s = s + data[0]; for (int i=1;i<=last;i++) s = s +","+ data[i]; s = s + "]"; return s; } }