1 #include "lib.h"
2 #include "bitset.h"
3
4 #define MEMSIZE(n) ((n + 31) >> 5)
5
bitcount(Word32 word)6 static inline Int bitcount(Word32 word) {
7 word = word - ((word >> 1) & 0x55555555);
8 word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
9 return (((word + (word >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
10 }
11
init(Int n)12 void BitSet::init(Int n) {
13 _bits = n;
14 _words = MEMSIZE(n);
15 _data = (Word32 *) GC_MALLOC_ATOMIC(sizeof(Word32) * _words);
16 memset(_data, 0, sizeof(Word32) * _words);
17 }
18
zero()19 void BitSet::zero() {
20 memset(_data, 0, sizeof(Word32) * _words);
21 }
22
resize(Int n)23 void BitSet::resize(Int n) {
24 Int words = _words;
25 Word32 *data = _data;
26 _bits = n;
27 _words = MEMSIZE(n);
28 _data = (Word32 *) GC_MALLOC_ATOMIC(sizeof(Word32) * _words);
29 memcpy(_data, data, sizeof(Word32) * Min(words, _words));
30 if (_words > words) {
31 memset(_data + words, 0, (_words - words) * sizeof(Word32));
32 }
33 }
expand(Int n)34 void BitSet::expand(Int n) {
35 if (n > _bits)
36 resize(n);
37 }
38
count()39 Int BitSet::count() {
40 Int result = 0;
41 for (Int i = 0; i < _words; i++) {
42 if (_data[i])
43 result += bitcount(_data[i]);
44 }
45 return result;
46 }
47
complement_in_place()48 BitSet *BitSet::complement_in_place() {
49 for (Int i = 0; i < _words; i++) {
50 _data[i] = ~_data[i];
51 }
52 Int n = _bits & 31;
53 if (n != 0) {
54 // zero top bits
55 _data[_words - 1] &= ((1 << n) - 1);
56 }
57 return this;
58 }
59
complement()60 BitSet *BitSet::complement() {
61 return clone()->complement_in_place();
62 }
63
union_in_place(BitSet * that)64 BitSet *BitSet::union_in_place(BitSet *that) {
65 expand(that->_bits);
66 for (Int i = 0; i < _words; i++)
67 _data[i] |= that->_data[i];
68 return this;
69 }
70
union_with(BitSet * that)71 BitSet *BitSet::union_with(BitSet *that) {
72 BitSet *result = clone();
73 result->union_in_place(that);
74 return result;
75 }
76
intersect_in_place(BitSet * that)77 BitSet *BitSet::intersect_in_place(BitSet *that) {
78 expand(that->_bits);
79 for (Int i = 0; i < _words; i++)
80 _data[i] &= that->_data[i];
81 return this;
82 }
83
intersect_with(BitSet * that)84 BitSet *BitSet::intersect_with(BitSet *that) {
85 return clone()->intersect_in_place(that);
86 }
87
diff_in_place(BitSet * that)88 BitSet *BitSet::diff_in_place(BitSet *that) {
89 expand(that->_bits);
90 for (Int i = 0; i < _words; i++)
91 _data[i] &= ~that->_data[i];
92 return this;
93 }
94
diff_with(BitSet * that)95 BitSet *BitSet::diff_with(BitSet *that) {
96 return clone()->diff_in_place(that);
97 }
98
MakeBitMatrix(Int rows,Int cols)99 BitMatrix *MakeBitMatrix(Int rows, Int cols) {
100 BitMatrix *result = new BitMatrix();
101 for (Int i = 0; i < rows; i++)
102 result->add(new BitSet(cols));
103 return result;
104 }
105
Clone(BitMatrix * mat)106 BitMatrix *Clone(BitMatrix *mat) {
107 BitMatrix *result = new BitMatrix(mat->len());
108 for (Int i = 0; i < mat->len(); i++)
109 result->add(mat->at(i)->clone());
110 return result;
111 }
112
IsMatrix(BitMatrix * mat)113 bool IsMatrix(BitMatrix *mat) {
114 if (mat->len() != 0 && mat->at(0)->len() == 0)
115 return false;
116 for (Int i = 1; i < mat->len(); i++) {
117 if (mat->at(i - 1)->len() != mat->at(i)->len()) {
118 return false;
119 }
120 }
121 return true;
122 }
123
Transpose(BitMatrix * mat)124 BitMatrix *Transpose(BitMatrix *mat) {
125 require(IsMatrix(mat), "not a proper matrix");
126 if (mat->len() == 0)
127 return MakeBitMatrix(0, 0);
128 Int rows = mat->len();
129 Int cols = mat->at(0)->len();
130 BitMatrix *result = MakeBitMatrix(cols, rows);
131 for (Int col = 0; col < cols; col++) {
132 BitSet *result_row = result->at(col);
133 for (Int row = 0; row < rows; row++) {
134 if (mat->at(row)->test(col)) {
135 result_row->set(row);
136 }
137 }
138 }
139 return result;
140 }
141
TransitiveClosure(BitMatrix * mat)142 BitMatrix *TransitiveClosure(BitMatrix *mat) {
143 // Floyd-Warshall algorithm
144 require(IsMatrix(mat), "not a proper matrix");
145 Int rows = mat->len();
146 if (rows == 0)
147 return MakeBitMatrix(0, 0);
148 Int cols = mat->at(0)->len();
149 require(mat->len() == mat->at(0)->len(), "not a square matrix");
150 mat = Clone(mat);
151 for (Int col = 0; col < cols; col++) {
152 for (Int row = 0; row < rows; row++) {
153 if (mat->at(row)->test(col)) {
154 mat->at(row)->union_in_place(mat->at(col));
155 }
156 }
157 }
158 return mat;
159 }
160