libbf  0.1
 All Classes Functions Typedefs Friends Pages
bitvector.cc
1 #include <bf/bitvector.h>
2 
3 #include <cassert>
4 
5 namespace bf {
6 
7 typedef bitvector::size_type size_type;
8 typedef bitvector::block_type block_type;
9 
10 namespace {
11 
12 uint8_t count_table[] =
13 {
14  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
15  3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
16  3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
17  4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
18  3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
19  6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
20  4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
21  6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
22  3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
23  4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
24  6, 7, 6, 7, 7, 8
25 };
26 
27 } // namespace <anonymous>
28 
29 bitvector::reference::reference(block_type& block, block_type i)
30  : block_(block)
31  , mask_(block_type(1) << i)
32 {
33  assert(i < bits_per_block);
34 }
35 
36 bitvector::reference& bitvector::reference::flip()
37 {
38  block_ ^= mask_;
39  return *this;
40 }
41 
42 bitvector::reference::operator bool() const
43 {
44  return (block_ & mask_) != 0;
45 }
46 
47 bool bitvector::reference::operator~() const
48 {
49  return (block_ & mask_) == 0;
50 }
51 
52 bitvector::reference& bitvector::reference::operator=(bool x)
53 {
54  x ? block_ |= mask_ : block_ &= ~mask_;
55  return *this;
56 }
57 
58 bitvector::reference& bitvector::reference::operator=(reference const& other)
59 {
60  other ? block_ |= mask_ : block_ &= ~mask_;
61  return *this;
62 }
63 
64 bitvector::reference& bitvector::reference::operator|=(bool x)
65 {
66  if (x)
67  block_ |= mask_;
68  return *this;
69 }
70 
71 bitvector::reference& bitvector::reference::operator&=(bool x)
72 {
73  if (! x)
74  block_ &= ~mask_;
75  return *this;
76 }
77 
78 bitvector::reference& bitvector::reference::operator^=(bool x)
79 {
80  if (x)
81  block_ ^= mask_;
82  return *this;
83 }
84 
85 bitvector::reference& bitvector::reference::operator-=(bool x)
86 {
87  if (x)
88  block_ &= ~mask_;
89  return *this;
90 }
91 
92 
94  : num_bits_(0)
95 {
96 }
97 
98 bitvector::bitvector(size_type size, bool value)
99  : bits_(bits_to_blocks(size), value ? ~block_type(0) : 0)
100  , num_bits_(size)
101 {
102 }
103 
105  : bits_(other.bits_)
106  , num_bits_(other.num_bits_)
107 {
108 }
109 
111  : bits_(std::move(other.bits_))
112  , num_bits_(other.num_bits_)
113 {
114  other.num_bits_ = 0;
115 }
116 
117 bitvector bitvector::operator~() const
118 {
119  bitvector b(*this);
120  b.flip();
121  return b;
122 }
123 
125 {
126  swap(*this, other);
127  return *this;
128 }
129 
130 void swap(bitvector x, bitvector y)
131 {
132  using std::swap;
133  swap(x.bits_, y.bits_);
134  swap(x.num_bits_, y.num_bits_);
135 }
136 
137 bitvector bitvector::operator<<(size_type n) const
138 {
139  bitvector b(*this);
140  return b <<= n;
141 }
142 
143 bitvector bitvector::operator>>(size_type n) const
144 {
145  bitvector b(*this);
146  return b >>= n;
147 }
148 
149 bitvector& bitvector::operator<<=(size_type n)
150 {
151  if (n >= num_bits_)
152  return reset();
153 
154  if (n > 0)
155  {
156  auto last = blocks() - 1;
157  auto div = n / bits_per_block;
158  auto r = bit_index(n);
159  auto b = &bits_[0];
160  assert(blocks() >= 1);
161  assert(div <= last);
162 
163  if (r != 0)
164  {
165  for (size_type i = last - div; i > 0; --i)
166  b[i + div] = (b[i] << r) | (b[i - 1] >> (bits_per_block - r));
167  b[div] = b[0] << r;
168  }
169  else
170  {
171  for (size_type i = last-div; i > 0; --i)
172  b[i + div] = b[i];
173  b[div] = b[0];
174  }
175 
176  std::fill_n(b, div, block_type(0));
177  zero_unused_bits();
178  }
179 
180  return *this;
181 }
182 
183 bitvector& bitvector::operator>>=(size_type n)
184 {
185  if (n >= num_bits_)
186  return reset();
187 
188  if (n > 0)
189  {
190  auto last = blocks() - 1;
191  auto div = n / bits_per_block;
192  auto r = bit_index(n);
193  auto b = &bits_[0];
194  assert(blocks() >= 1);
195  assert(div <= last);
196 
197  if (r != 0)
198  {
199  for (size_type i = last - div; i > 0; --i)
200  b[i - div] = (b[i] >> r) | (b[i + 1] << (bits_per_block - r));
201  b[last - div] = b[last] >> r;
202  }
203  else
204  {
205  for (size_type i = div; i <= last; ++i)
206  b[i-div] = b[i];
207  }
208 
209  std::fill_n(b + (blocks() - div), div, block_type(0));
210  }
211 
212  return *this;
213 }
214 
215 bitvector& bitvector::operator&=(bitvector const& other)
216 {
217  assert(size() >= other.size());
218  for (size_type i = 0; i < blocks(); ++i)
219  bits_[i] &= other.bits_[i];
220  return *this;
221 }
222 
223 bitvector& bitvector::operator|=(bitvector const& other)
224 {
225  assert(size() >= other.size());
226  for (size_type i = 0; i < blocks(); ++i)
227  bits_[i] |= other.bits_[i];
228  return *this;
229 }
230 
231 bitvector& bitvector::operator^=(bitvector const& other)
232 {
233  assert(size() >= other.size());
234  for (size_type i = 0; i < blocks(); ++i)
235  bits_[i] ^= other.bits_[i];
236  return *this;
237 }
238 
239 bitvector& bitvector::operator-=(bitvector const& other)
240 {
241  assert(size() >= other.size());
242  for (size_type i = 0; i < blocks(); ++i)
243  bits_[i] &= ~other.bits_[i];
244  return *this;
245 }
246 
247 bitvector operator&(bitvector const& x, bitvector const& y)
248 {
249  bitvector b(x);
250  return b &= y;
251 }
252 
253 bitvector operator|(bitvector const& x, bitvector const& y)
254 {
255  bitvector b(x);
256  return b |= y;
257 }
258 
259 bitvector operator^(bitvector const& x, bitvector const& y)
260 {
261  bitvector b(x);
262  return b ^= y;
263 }
264 
265 bitvector operator-(bitvector const& x, bitvector const& y)
266 {
267  bitvector b(x);
268  return b -= y;
269 }
270 
271 bool operator==(bitvector const& x, bitvector const& y)
272 {
273  return x.num_bits_ == y.num_bits_ && x.bits_ == y.bits_;
274 }
275 
276 bool operator!=(bitvector const& x, bitvector const& y)
277 {
278  return ! (x == y);
279 }
280 
281 bool operator<(bitvector const& x, bitvector const& y)
282 {
283  assert(x.size() == y.size());
284  for (size_type r = x.blocks(); r > 0; --r)
285  {
286  auto i = r - 1;
287  if (x.bits_[i] < y.bits_[i])
288  return true;
289  else if (x.bits_[i] > y.bits_[i])
290  return false;
291  }
292  return false;
293 }
294 
295 void bitvector::resize(size_type n, bool value)
296 {
297  auto old = blocks();
298  auto required = bits_to_blocks(n);
299  auto block_value = value ? ~block_type(0) : block_type(0);
300 
301  if (required != old)
302  bits_.resize(required, block_value);
303 
304  if (value && (n > num_bits_) && extra_bits())
305  bits_[old - 1] |= (block_value << extra_bits());
306 
307  num_bits_ = n;
308  zero_unused_bits();
309 }
310 
311 void bitvector::clear() noexcept
312 {
313  bits_.clear();
314  num_bits_ = 0;
315 }
316 
317 void bitvector::push_back(bool bit)
318 {
319  auto s = size();
320  resize(s + 1);
321  set(s, bit);
322 }
323 
324 void bitvector::append(block_type block)
325 {
326  auto excess = extra_bits();
327  if (excess)
328  {
329  assert(! bits_.empty());
330  bits_.push_back(block >> (bits_per_block - excess));
331  bits_[bits_.size() - 2] |= (block << excess);
332  }
333  else
334  {
335  bits_.push_back(block);
336  }
337  num_bits_ += bits_per_block;
338 }
339 
340 bitvector& bitvector::set(size_type i, bool bit)
341 {
342  assert(i < num_bits_);
343 
344  if (bit)
345  bits_[block_index(i)] |= bit_mask(i);
346  else
347  reset(i);
348 
349  return *this;
350 }
351 
353 {
354  std::fill(bits_.begin(), bits_.end(), ~block_type(0));
355  zero_unused_bits();
356  return *this;
357 }
358 
360 {
361  assert(i < num_bits_);
362  bits_[block_index(i)] &= ~bit_mask(i);
363  return *this;
364 }
365 
367 {
368  std::fill(bits_.begin(), bits_.end(), block_type(0));
369  return *this;
370 }
371 
373 {
374  assert(i < num_bits_);
375  bits_[block_index(i)] ^= bit_mask(i);
376  return *this;
377 }
378 
380 {
381  for (size_type i = 0; i < blocks(); ++i)
382  bits_[i] = ~bits_[i];
383  zero_unused_bits();
384  return *this;
385 }
386 
387 bool bitvector::operator[](size_type i) const
388 {
389  assert(i < num_bits_);
390  return (bits_[block_index(i)] & bit_mask(i)) != 0;
391 }
392 
394 {
395  assert(i < num_bits_);
396  return {bits_[block_index(i)], bit_index(i)};
397 }
398 
399 size_type bitvector::count() const
400 {
401  auto first = bits_.begin();
402  size_t n = 0;
403  auto length = blocks();
404  while (length)
405  {
406  auto block = *first;
407  while (block)
408  {
409  // TODO: use __popcnt if available.
410  n += count_table[block & ((1u << 8) - 1)];
411  block >>= 8;
412  }
413  ++first;
414  --length;
415  }
416  return n;
417 }
418 
419 size_type bitvector::blocks() const
420 {
421  return bits_.size();
422 }
423 
424 size_type bitvector::size() const
425 {
426  return num_bits_;
427 }
428 
429 bool bitvector::empty() const
430 {
431  return bits_.empty();
432 }
433 
434 size_type bitvector::find_first() const
435 {
436  return find_from(0);
437 }
438 
439 size_type bitvector::find_next(size_type i) const
440 {
441  if (i >= (size() - 1) || size() == 0)
442  return npos;
443  ++i;
444  auto bi = block_index(i);
445  auto block = bits_[bi] & (~block_type(0) << bit_index(i));
446  return block ? bi * bits_per_block + lowest_bit(block) : find_from(bi + 1);
447 }
448 
449 size_type bitvector::lowest_bit(block_type block)
450 {
451  auto x = block - (block & (block - 1)); // Extract right-most 1-bit.
452  size_type log = 0;
453  while (x >>= 1)
454  ++log;
455  return log;
456 }
457 
458 block_type bitvector::extra_bits() const
459 {
460  return bit_index(size());
461 }
462 
463 void bitvector::zero_unused_bits()
464 {
465  if (extra_bits())
466  bits_.back() &= ~(~block_type(0) << extra_bits());
467 }
468 
469 size_type bitvector::find_from(size_type i) const
470 {
471  while (i < blocks() && bits_[i] == 0)
472  ++i;
473  if (i >= blocks())
474  return npos;
475  return i * bits_per_block + lowest_bit(bits_[i]);
476 }
477 
478 std::string to_string(bitvector const& b,
479  bool msb_to_lsb,
480  bool all,
481  size_t cut_off)
482 {
483  std::string str;
484  auto str_size = all ? bitvector::bits_per_block * b.blocks() : b.size();
485  if (cut_off == 0 || str_size <= cut_off)
486  {
487  str.assign(str_size, '0');
488  }
489  else
490  {
491  str.assign(cut_off + 2, '0');
492  str[cut_off + 0] = '.';
493  str[cut_off + 1] = '.';
494  str_size = cut_off;
495  }
496 
497  for (bitvector::size_type i = 0; i < std::min(str_size, b.size()); ++i)
498  if (b[i])
499  str[msb_to_lsb ? str_size - i - 1 : i] = '1';
500 
501  return str;
502 }
503 
504 } // namespace bf