1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 | function BitSet(size) {
|
10 | if (size) {
|
11 | var numWords = Math.ceil(size / 32);
|
12 | this.words = new Array(numWords);
|
13 | }
|
14 | else {
|
15 | this.words = [];
|
16 | }
|
17 | this.wordsInUse = 0;
|
18 | }
|
19 |
|
20 | var P = BitSet.prototype;
|
21 |
|
22 | function wordIndex(bitIndex) {
|
23 | return Math.floor(bitIndex / 32);
|
24 | }
|
25 |
|
26 |
|
27 | P.ensureSize = function(numWords) {
|
28 | var wordsPresent = this.words.length;
|
29 | if (wordsPresent < numWords) {
|
30 | this.words = this.words.concat(new Array(numWords - wordsPresent));
|
31 | }
|
32 | }
|
33 |
|
34 | P.set = function(bitIndex) {
|
35 | var w = wordIndex(bitIndex);
|
36 | if (w >= this.wordsInUse) {
|
37 | this.ensureSize(w + 1);
|
38 | this.wordsInUse = w + 1;
|
39 | }
|
40 | var bit = 1 << bitIndex;
|
41 | this.words[w] |= bit;
|
42 | };
|
43 |
|
44 | P.clear = function(bitIndex) {
|
45 | var w = wordIndex(bitIndex);
|
46 | if (w >= this.wordsInUse) return;
|
47 | var mask = ~(1 << bitIndex);
|
48 | this.words[w] &= mask;
|
49 | };
|
50 |
|
51 | P.get = function(bitIndex) {
|
52 | var w = wordIndex(bitIndex);
|
53 | if (w >= this.wordsInUse) return false;
|
54 | var bit = 1 << bitIndex;
|
55 | return !!(this.words[w] & bit);
|
56 | }
|
57 |
|
58 | function trailingZeros(i) {
|
59 |
|
60 |
|
61 |
|
62 | if (i === 0) return 32;
|
63 | var y, n = 31;
|
64 | y = i << 16; if (y != 0) { n = n -16; i = y; }
|
65 | y = i << 8; if (y != 0) { n = n - 8; i = y; }
|
66 | y = i << 4; if (y != 0) { n = n - 4; i = y; }
|
67 | y = i << 2; if (y != 0) { n = n - 2; i = y; }
|
68 | return n - ((i << 1) >>> 31);
|
69 | }
|
70 |
|
71 |
|
72 |
|
73 | P.nextSetBit = function(fromIndex) {
|
74 | var w = wordIndex(fromIndex);
|
75 | if (w >= this.wordsInUse) return -1;
|
76 |
|
77 |
|
78 |
|
79 | var word = this.words[w] & (0xffffffff << fromIndex);
|
80 | while (true) {
|
81 | if (word) return (w * 32) + trailingZeros(word);
|
82 | w++;
|
83 | if (w === this.wordsInUse) return -1;
|
84 | word = this.words[w];
|
85 | }
|
86 | };
|
87 |
|
88 | P.nextClearBit = function(fromIndex) {
|
89 | var w = wordIndex(fromIndex);
|
90 | if (w >= this.wordsInUse) return fromIndex;
|
91 |
|
92 | var word = ~(this.words[w]) & (0xffffffff << fromIndex);
|
93 | while (true) {
|
94 | if (word) return (w * 32) + trailingZeros(word);
|
95 | w++;
|
96 | if (w == this.wordsInUse) return w * 32;
|
97 | word = ~(this.words[w]);
|
98 | }
|
99 | };
|
100 |
|
101 | module.exports.BitSet = BitSet;
|