import java util AbstractSet import java util Iterator import java uti

 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
77
78
79
80
81
82
83
84
85
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){
if(((T)x).hint() >= 0 && ((T)x).hint() < n && dense.get(((T)x).hint()) == (T)x)
return true;
else
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();
}
}