-
Notifications
You must be signed in to change notification settings - Fork 0
/
endless-bitset.js
112 lines (88 loc) · 2.26 KB
/
endless-bitset.js
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
109
110
111
112
const BitSet = require('fast-bitset');
const bigInt = require('big-integer');
const MAX = bigInt(2).pow(32);
const log = (a, b) => {
let count = 0;
while (a.gt(b)) {
a = a.divide(b);
count++;
}
return count;
};
const normalize = n => typeof n === 'number' ? bigInt(n) : n;
const EndlessBitSet = class {
constructor(length) {
this.length = normalize(length);
this.depth = log(this.length, MAX);
this.buckets = [];
}
max() {
return MAX.pow(this.depth + 1);
}
getBucket(iParam) {
const i = iParam.valueOf();
if (!this.buckets[i]) {
this.buckets[i] = this.depth === 0 ? new BitSet(MAX.valueOf()) : new EndlessBitSet(this.length.divide(MAX));
}
return this.buckets[i];
}
set(idxParam) {
return this._findOp('set', idxParam);
}
unset(idxParam) {
return this._findOp('unset', idxParam);
}
get(idxParam) {
return this._findOp('get', idxParam);
}
_findOp(op, idxParam) {
const idx = normalize(idxParam);
const i = idx.divide(this.max());
const r = idx.mod(this.max());
return this.getBucket(i)[op](r);
}
setRange(startParam, endParam) {
const startIdx = normalize(startParam);
const endIdx = normalize(endParam);
const start = startIdx.divide(this.max());
const end = endIdx.divide(this.max());
const startR = startIdx.mod(this.max());
const endR = endIdx.mod(this.max());
if (start.eq(end)) {
this.getBucket(start).setRange(startR, endR);
} else {
this.getBucket(start).setRange(startR, this.max());
for (let i = start.add(1); i.lt(end); i = i.next()) {
this.getBucket(i).setRange(0, this.max());
}
this.getBucket(end).setRange(0, endR);
}
}
nextUnsetBit(idxParam) {
const idx = normalize(idxParam);
const i = idx.divide(this.max());
const r = idx.mod(this.max());
let bucket = this.getBucket(i);
let bit = bucket.nextUnsetBit(r);
if (bit !== -1) {
return bit;
}
while (i < this.max()) {
bucket = this.getBucket(++i);
bit = bucket.nextUnsetBit(0);
if (bit !== -1) {
return bit;
}
}
return -1;
}
// WARNING : for testing porpuses only! this will explode your machine if the bitset is too big
toArray() {
const array = [];
for (let i = 0; i < this.length.valueOf(); i++) {
array.push(this.get(i));
}
return array;
}
};
module.exports = EndlessBitSet;