import java lang import java util class SparseSet extends Hintable ext

 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
import java.lang.*;
import java.util.*;
class SparseSet<T extends Hintable> extends AbstractSet<T>
{
private int n;
private ArrayList<T> dense;
public int size(){
return n;
}
//clear (очистка множества)
@Override
public void clear() {
n = 0;
}
SparseSet()
{
n = 0;
dense = new ArrayList<T>(Collections.EMPTY_LIST);
}
/*поле hint, в котором бы хранилось предполагаемое место ссылки на этот объект в массиве dense.*/
/////////////////////////////////////////////////////////////
//contains (проверку принадлежности объекта множеству)
@Override
public boolean contains(Object x){
return (T)x != null && ( (T)x ).hint()<n && ( (T)x ).hint() > -1 && dense.get( ( (T)x ).hint() ) == (T)x;
}
//add (добавление объекта)
@Override
public boolean add(T x)
{
if (!contains(x))
{
dense.add(x);
x.setHint(n++);
return true;
}
return false;
}
public Iterator<T> iterator()
{
return new Iterator<T>()
{
private int iter = 0;
@Override
public boolean hasNext() {
//return iter <= n;
return iter < n;
}
public void remove()
{
SparseSet.this.remove(dense.get(iter-1));
}
@Override
public T next() {
return dense.get(iter++);
}
};
}
// remove (удаление объекта)
@Override
public boolean remove(Object x)
{
if(contains( (T)x) )
{
dense.set( ( (T)x ) .hint(), dense.get(--n));
dense.get(n).setHint( ( (T)x ).hint() );
return true;
}
return false;
}
}