-
Notifications
You must be signed in to change notification settings - Fork 38
Expand file tree
/
Copy pathBitSet.js
More file actions
123 lines (108 loc) · 3.23 KB
/
BitSet.js
File metadata and controls
123 lines (108 loc) · 3.23 KB
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
113
114
115
116
117
118
119
120
121
122
123
/* Copyright (c) 2012-2022 The ANTLR Project Contributors. All rights reserved.
* Use is of this file is governed by the BSD 3-clause license that
* can be found in the LICENSE.txt file in the project root.
*/
import HashCode from "./HashCode.js";
import equalArrays from "../utils/equalArrays.js";
export default class BitSet {
constructor() {
this.data = new Uint32Array(1);
}
set(index) {
BitSet._checkIndex(index)
this._resize(index);
this.data[index >>> 5] |= 1 << index % 32;
}
get(index) {
BitSet._checkIndex(index)
let slot = index >>> 5;
if (slot >= this.data.length) {
return false;
}
return (this.data[slot] & 1 << index % 32) !== 0;
}
clear(index) {
BitSet._checkIndex(index)
let slot = index >>> 5;
if (slot < this.data.length) {
this.data[slot] &= ~(1 << index);
}
}
or(set) {
let minCount = Math.min(this.data.length, set.data.length);
for (let k = 0; k < minCount; ++k) {
this.data[k] |= set.data[k];
}
if (this.data.length < set.data.length) {
this._resize((set.data.length << 5) - 1);
let c = set.data.length;
for (let k = minCount; k < c; ++k) {
this.data[k] = set.data[k];
}
}
}
values() {
let result = new Array(this.length);
let pos = 0;
let length = this.data.length;
for (let k = 0; k < length; ++k) {
let l = this.data[k];
while (l !== 0) {
let t = l & -l;
result[pos++] = (k << 5) + BitSet._bitCount(t - 1);
l ^= t;
}
}
return result;
}
minValue() {
for (let k = 0; k < this.data.length; ++k) {
let l = this.data[k];
if (l !== 0) {
let result = 0;
while ((l & 1) === 0) {
result++;
l >>= 1;
}
return result + (32 * k);
}
}
return 0;
}
hashCode() {
return HashCode.hashStuff(this.values());
}
equals(other) {
return other instanceof BitSet && equalArrays(this.data, other.data);
}
toString() {
return "{" + this.values().join(", ") + "}";
}
get length() {
return this.data.map(l => BitSet._bitCount(l)).reduce((s, v) => s + v, 0);
}
_resize(index) {
let count = index + 32 >>> 5;
if (count <= this.data.length) {
return;
}
let data = new Uint32Array(count);
data.set(this.data);
data.fill(0, this.data.length);
this.data = data;
}
static _checkIndex(index) {
if (index < 0)
throw new RangeError("index cannot be negative");
}
static _bitCount(l) {
// see https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
let count = 0;
l = l - ((l >> 1) & 0x55555555);
l = (l & 0x33333333) + ((l >> 2) & 0x33333333);
l = (l + (l >> 4)) & 0x0f0f0f0f;
l = l + (l >> 8);
l = l + (l >> 16);
return count + l & 0x3f;
}
}