blob: d02cd2feb4f923e95b56c3a3692e2d38d0c13417 (
plain)
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
|
// A set of non-negative integers, represented one bit per value.
struct bitset {
i64[] !_bits;
new bitset = { ->
_bits = new i64[1];
};
// Return 0 for missing, non-zero for true
val get = { int bit ->
if( (bit >> 6) >= _bits# ) return false;
i64 mask = 1 << (bit & 63);
return (_bits[bit >> 6] & mask);
};
val _grow = { int bit ->
int x = bit >> 6;
int len = _bits#;
if( x < len ) return self;
while( x >= len ) len *= 2;
var bits = new i64[len];
for( int i=0; i<_bits#; i++ )
bits[i] = _bits[i];
_bits = bits;
return self;
};
// Set
val set = { int bit ->
i64 mask = 1 << (bit & 63);
_grow(bit)._bits[bit >> 6] |= mask;
return self;
};
// Test and set
val tset = { int bit ->
int idx = bit >> 6;
i64 mask = 1 << (bit & 63);
if( _grow(bit)._bits[idx] & mask )
return true; // Already set
_bits[idx] |= mask;
return false; // Was false (and now set)
};
val clr = { int bit ->
if( (bit >> 6) >= _bits# ) return self;
i64 mask = 1 << (bit & 63);
_bits[bit >> 6] &= (mask ^ -1);
return self;
};
val clear = { ->
for( int i=0; i<_bits#; i++ ) _bits[i] = 0;
return self;
};
};
|
