-
-
Notifications
You must be signed in to change notification settings - Fork 44
/
IntSet.java
108 lines (91 loc) · 2.12 KB
/
IntSet.java
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package nallar.collections;
import java.util.*;
public class IntSet {
private static final int EMPTY_KEY = Integer.MIN_VALUE;
private static final int BUCKET_SIZE = 4096;
private final int[][] keys = new int[BUCKET_SIZE][];
private int size;
public int[][] getValues() {
return keys;
}
public int size() {
return size;
}
public boolean contains(int key) {
int index = keyIndex(key);
int[] inner = keys[index];
if (inner == null) {
return false;
}
for (int i = 0; i < inner.length; i++) {
int innerKey = inner[i];
if (innerKey == EMPTY_KEY) {
return false;
} else if (innerKey == key) {
return true;
}
}
return false;
}
public synchronized boolean add(int key) {
int index = keyIndex(key);
int[] innerKeys = keys[index];
if (innerKeys == null) {
// need to make a new chain
keys[index] = innerKeys = new int[8];
Arrays.fill(innerKeys, EMPTY_KEY);
innerKeys[0] = key;
size++;
} else {
int i;
for (i = 0; i < innerKeys.length; i++) {
int currentKey = innerKeys[i];
if (currentKey == EMPTY_KEY) {
innerKeys[i] = key;
size++;
return true;
}
if (currentKey == key) {
return false;
}
}
keys[index] = innerKeys = Arrays.copyOf(innerKeys, i << 1);
Arrays.fill(innerKeys, i, innerKeys.length, EMPTY_KEY);
innerKeys[i] = key;
size++;
}
return true;
}
public synchronized boolean remove(int key) {
int index = keyIndex(key);
int[] inner = keys[index];
if (inner == null) {
return false;
}
for (int i = 0; i < inner.length; i++) {
if (inner[i] == EMPTY_KEY) {
break;
}
if (inner[i] == key) {
for (i++; i < inner.length; i++) {
if (inner[i] == EMPTY_KEY) {
break;
}
inner[i - 1] = inner[i];
}
inner[i - 1] = EMPTY_KEY;
size--;
return true;
}
}
return false;
}
private static int keyIndex(int key) {
key ^= key >> 16;
key *= 0x85ebca6b;
key ^= key >> 13;
key *= 0xc2b2ae35;
key ^= key >> 16;
return key & (BUCKET_SIZE - 1);
}
}