Empirical
BitVector.h
Go to the documentation of this file.
1 
18 #ifndef EMP_BIT_VECTOR_H
19 #define EMP_BIT_VECTOR_H
20 
21 #include <iostream>
22 
23 #include "../base/assert.h"
24 #include "../base/Ptr.h"
25 #include "../base/vector.h"
26 
27 #include "bitset_utils.h"
28 #include "functions.h"
29 #include "math.h"
30 
31 namespace emp {
32 
38 
39  class BitVector {
40  private:
41 #ifdef EMSCRIPTEN
42  using field_t = uint32_t;
43 #else
44  using field_t = uint64_t;
45 #endif
46 
47  static constexpr size_t FIELD_BITS = sizeof(field_t)*8;
48  size_t num_bits;
49  Ptr<field_t> bit_set;
50 
52  size_t LastBitID() const { return num_bits & (FIELD_BITS - 1); }
53 
55  size_t NumFields() const { return num_bits ? (1 + ((num_bits - 1) / FIELD_BITS)) : 0; }
56 
58  size_t NumBytes() const { return num_bits ? (1 + ((num_bits - 1) >> 3)) : 0; }
59 
61  size_t NumSizeFields() const { return NumFields() * sizeof(field_t) / sizeof(std::size_t); }
62 
64  struct BitProxy {
65  BitVector & bit_vector;
66  size_t index;
67 
69  BitProxy(BitVector & _v, size_t _idx) : bit_vector(_v), index(_idx) {;}
70 
72  BitProxy & operator=(bool b) {
73  bit_vector.Set(index, b);
74  return *this;
75  }
76 
78  operator bool() const {
79  return bit_vector.Get(index);
80  }
81 
84  BitProxy & operator &=(bool b) {
85  const bool v = bit_vector.Get(index);
86  bit_vector.Set(index, v & b);
87  return *this;
88  }
89 
92  BitProxy & operator |=(bool b) {
93  const bool v = bit_vector.Get(index);
94  bit_vector.Set(index, v | b);
95  return *this;
96  }
97 
100  BitProxy & operator ^=(bool b) {
101  const bool v = bit_vector.Get(index);
102  bit_vector.Set(index, v ^ b);
103  return *this;
104  }
105 
108  BitProxy & operator +=(bool b) {
109  const bool v = bit_vector.Get(index);
110  bit_vector.Set(index, v || b);
111  return *this;
112  }
113 
116  BitProxy & operator -=(bool b) {
117  const bool v = bit_vector.Get(index);
118  bit_vector.Set(index, v - b);
119  return *this;
120  }
121 
124  BitProxy & operator *=(bool b) {
125  const bool v = bit_vector.Get(index);
126  bit_vector.Set(index, v && b);
127  return *this;
128  }
129 
133  BitProxy & operator /=(bool b) {
134  emp_assert(b == true);
135  return *this;
136  }
137  };
138 
140  static constexpr size_t FieldID(const size_t index) { return index / FIELD_BITS; }
141 
143  static constexpr size_t FieldPos(const size_t index) { return index & (FIELD_BITS-1); }
144 
146  static constexpr size_t Byte2Field(const size_t index) { return index/sizeof(field_t); }
147 
149  static constexpr size_t Byte2FieldPos(const size_t index) {
150  return (index & (sizeof(field_t)-1)) << 3;
151  }
152 
155  void RawCopy(const Ptr<field_t> in_set) {
156  #ifdef EMP_TRACK_MEM
157  emp_assert(in_set.IsNull() == false);
158  emp_assert(bit_set.DebugIsArray() && in_set.DebugIsArray());
159  emp_assert(bit_set.DebugGetArrayBytes() == in_set.DebugGetArrayBytes(),
160  bit_set.DebugGetArrayBytes(), in_set.DebugGetArrayBytes());
161  #endif
162 
163  const size_t NUM_FIELDS = NumFields();
164  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = in_set[i];
165  }
166 
168  void ShiftLeft(const size_t shift_size) {
169  const size_t field_shift = shift_size / FIELD_BITS;
170  const size_t bit_shift = shift_size % FIELD_BITS;
171  const size_t bit_overflow = FIELD_BITS - bit_shift;
172  const size_t NUM_FIELDS = NumFields();
173 
174  // Loop through each field, from L to R, and update it.
175  if (field_shift) {
176  for (size_t i = NUM_FIELDS; i > field_shift; --i) {
177  bit_set[i-1] = bit_set[i - field_shift - 1];
178  }
179  for (size_t i = field_shift; i > 0; --i) bit_set[i-1] = 0;
180  }
181 
182  // account for bit_shift
183  if (bit_shift) {
184  for (size_t i = NUM_FIELDS - 1; i > field_shift; --i) {
185  bit_set[i] <<= bit_shift;
186  bit_set[i] |= (bit_set[i-1] >> bit_overflow);
187  }
188  // Handle final field (field_shift position)
189  bit_set[field_shift] <<= bit_shift;
190  }
191 
192  // Mask out any bits that have left-shifted away
193  const size_t last_bit_id = LastBitID();
194  constexpr field_t val_one = 1;
195  if (last_bit_id) { bit_set[NUM_FIELDS - 1] &= (val_one << last_bit_id) - val_one; }
196  }
197 
198 
200  void ShiftRight(const size_t shift_size) {
201  const size_t field_shift = shift_size / FIELD_BITS;
202  const size_t bit_shift = shift_size % FIELD_BITS;
203  const size_t bit_overflow = FIELD_BITS - bit_shift;
204  const size_t NUM_FIELDS = NumFields();
205  const size_t field_shift2 = NUM_FIELDS - field_shift;
206 
207  // account for field_shift
208  if (field_shift) {
209  for (size_t i = 0; i < field_shift2; ++i) {
210  bit_set[i] = bit_set[i + field_shift];
211  }
212  for (size_t i = field_shift2; i < NUM_FIELDS; i++) bit_set[i] = 0U;
213  }
214 
215  // account for bit_shift
216  if (bit_shift) {
217  for (size_t i = 0; i < (field_shift2 - 1); ++i) {
218  bit_set[i] >>= bit_shift;
219  bit_set[i] |= (bit_set[i+1] << bit_overflow);
220  }
221  bit_set[field_shift2 - 1] >>= bit_shift;
222  }
223  }
224 
225  public:
227  BitVector(size_t in_num_bits=0, bool init_val=false) : num_bits(in_num_bits), bit_set(nullptr) {
228  if (num_bits) bit_set = NewArrayPtr<field_t>(NumFields());
229  if (init_val) SetAll(); else Clear();
230  }
231 
233  BitVector(const BitVector & in_set) : num_bits(in_set.num_bits), bit_set(nullptr) {
234  #ifdef EMP_TRACK_MEM
235  emp_assert(in_set.bit_set.IsNull() || in_set.bit_set.DebugIsArray(), in_set.bit_set.IsNull(), in_set.bit_set.DebugIsArray());
236  emp_assert(in_set.bit_set.OK());
237  #endif
238 
239  if (num_bits) bit_set = NewArrayPtr<field_t>(NumFields());
240  RawCopy(in_set.bit_set);
241  }
242 
244  BitVector(BitVector && in_set) : num_bits(in_set.num_bits), bit_set(in_set.bit_set) {
245  #ifdef EMP_TRACK_MEM
246  emp_assert(bit_set == nullptr || bit_set.DebugIsArray());
247  emp_assert(bit_set.OK());
248  #endif
249 
250  in_set.bit_set = nullptr;
251  }
252 
255  if (bit_set) { // A move constructor can make bit_set == nullptr
256  bit_set.DeleteArray();
257  bit_set = nullptr;
258  }
259  }
260 
262  BitVector & operator=(const BitVector & in_set) {
263  #ifdef EMP_TRACK_MEM
264  emp_assert(in_set.bit_set == nullptr || in_set.bit_set.DebugIsArray());
265  emp_assert(in_set.bit_set != nullptr || in_set.num_bits == 0);
266  emp_assert(in_set.bit_set.OK());
267  #endif
268 
269  if (&in_set == this) return *this;
270  const size_t in_num_fields = in_set.NumFields();
271  const size_t prev_num_fields = NumFields();
272  num_bits = in_set.num_bits;
273 
274  if (in_num_fields != prev_num_fields) {
275  if (bit_set) bit_set.DeleteArray();
276  if (num_bits) bit_set = NewArrayPtr<field_t>(in_num_fields);
277  else bit_set = nullptr;
278  }
279 
280  if (num_bits) RawCopy(in_set.bit_set);
281 
282  return *this;
283  }
284 
287  emp_assert(&in_set != this); // in_set is an r-value, so this shouldn't be possible...
288  if (bit_set) bit_set.DeleteArray(); // If we already had a bitset, get rid of it.
289  num_bits = in_set.num_bits; // Update the number of bits...
290  bit_set = in_set.bit_set; // And steal the old memory for what those bits are.
291  in_set.bit_set = nullptr; // Prepare in_set for deletion without deallocating.
292 
293  return *this;
294  }
295 
297  BitVector & Resize(size_t new_bits) {
298  const size_t old_num_fields = NumFields();
299  num_bits = new_bits;
300  const size_t NUM_FIELDS = NumFields();
301 
302  if (NUM_FIELDS == old_num_fields) { // We can use our existing bit field
303  num_bits = new_bits;
304  // If there are extra bits, zero them out.
305  if (LastBitID() > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
306  }
307 
308  else { // We have to change the number of bitfields. Resize & copy old info.
309  Ptr<field_t> old_bit_set = bit_set;
310  if (num_bits > 0) bit_set = NewArrayPtr<field_t>(NUM_FIELDS);
311  else bit_set = nullptr;
312  const size_t min_fields = std::min(old_num_fields, NUM_FIELDS);
313  for (size_t i = 0; i < min_fields; i++) bit_set[i] = old_bit_set[i];
314  for (size_t i = min_fields; i < NUM_FIELDS; i++) bit_set[i] = 0U;
315  if (old_bit_set) old_bit_set.DeleteArray();
316  }
317 
318  return *this;
319  }
320 
322  bool operator==(const BitVector & in_set) const {
323  if (num_bits != in_set.num_bits) return false;
324 
325  const size_t NUM_FIELDS = NumFields();
326  for (size_t i = 0; i < NUM_FIELDS; ++i) {
327  if (bit_set[i] != in_set.bit_set[i]) return false;
328  }
329  return true;
330  }
331 
333  bool operator<(const BitVector & in_set) const {
334  if (num_bits != in_set.num_bits) return num_bits < in_set.num_bits;
335 
336  const size_t NUM_FIELDS = NumFields();
337  for (size_t i = NUM_FIELDS; i > 0; --i) { // Start loop at the largest field.
338  const size_t pos = i-1;
339  if (bit_set[pos] == in_set.bit_set[pos]) continue; // If same, keep looking!
340  return (bit_set[pos] < in_set.bit_set[pos]); // Otherwise, do comparison
341  }
342  return false;
343  }
344 
346  bool operator<=(const BitVector & in_set) const {
347  if (num_bits != in_set.num_bits) return num_bits <= in_set.num_bits;
348 
349  const size_t NUM_FIELDS = NumFields();
350  for (size_t i = NUM_FIELDS; i > 0; --i) { // Start loop at the largest field.
351  const size_t pos = i-1;
352  if (bit_set[pos] == in_set.bit_set[pos]) continue; // If same, keep looking!
353  return (bit_set[pos] < in_set.bit_set[pos]); // Otherwise, do comparison
354  }
355  return true;
356  }
357 
359  bool operator!=(const BitVector & in_set) const { return !operator==(in_set); }
360 
362  bool operator>(const BitVector & in_set) const { return !operator<=(in_set); }
363 
365  bool operator>=(const BitVector & in_set) const { return !operator<(in_set); }
366 
368  size_t GetSize() const { return num_bits; }
369 
371  bool Get(size_t index) const {
372  emp_assert(index < num_bits, index, num_bits);
373  const size_t field_id = FieldID(index);
374  const size_t pos_id = FieldPos(index);
375  return (bit_set[field_id] & (static_cast<field_t>(1) << pos_id)) != 0;
376  }
377 
379  void Set(size_t index, bool value=true) {
380  emp_assert(index < num_bits, index, num_bits);
381  const size_t field_id = FieldID(index);
382  const size_t pos_id = FieldPos(index);
383  constexpr field_t val_one = 1;
384  const field_t pos_mask = val_one << pos_id;
385 
386  if (value) bit_set[field_id] |= pos_mask;
387  else bit_set[field_id] &= ~pos_mask;
388  }
389 
391  std::size_t Hash() const {
392  const size_t num_sfields = NumSizeFields();
393  std::size_t hash_val = 0;
394  for (size_t i = 0; i < num_sfields; i++) {
395  hash_val ^= (bit_set.Cast<std::size_t>())[i];
396  }
397  return hash_val ^ ((97*num_bits) << 8);
398  }
399 
401  uint8_t GetByte(size_t index) const {
402  emp_assert(index < NumBytes(), index, NumBytes());
403  const size_t field_id = Byte2Field(index);
404  const size_t pos_id = Byte2FieldPos(index);
405  return (bit_set[field_id] >> pos_id) & 255U;
406  }
407 
409  void SetByte(size_t index, uint8_t value) {
410  emp_assert(index < NumBytes(), index, NumBytes());
411  const size_t field_id = Byte2Field(index);
412  const size_t pos_id = Byte2FieldPos(index);
413  const field_t val_uint = value;
414  bit_set[field_id] = (bit_set[field_id] & ~(static_cast<field_t>(255) << pos_id)) | (val_uint << pos_id);
415  }
416 
418  uint32_t GetUInt(size_t index) const {
419  // @CAO Need proper assert for variable bit fields!
420  // emp_assert(index < NumFields());
421  return bit_set.Cast<uint32_t>()[index];
422  }
423 
425  void SetUInt(size_t index, uint32_t value) {
426  // @CAO Need proper assert for variable bit fields!
427  // emp_assert(index < NumFields());
428  bit_set.Cast<uint32_t>()[index] = value;
429  }
430 
432  uint32_t GetUIntAtBit(size_t index) {
433  // @CAO Need proper assert for non-32-size bit fields!
434  // emp_assert(index < num_bits);
435  const size_t field_id = FieldID(index);
436  const size_t pos_id = FieldPos(index);
437  if (pos_id == 0) return (uint32_t) bit_set[field_id];
438  const size_t NUM_FIELDS = NumFields();
439  const uint32_t part1 = (uint32_t) (bit_set[field_id] >> pos_id);
440  const uint32_t part2 =
441  (uint32_t)((field_id+1 < NUM_FIELDS) ? bit_set[field_id+1] << (FIELD_BITS-pos_id) : 0);
442  return part1 | part2;
443  }
444 
446  template <size_t OUT_BITS>
447  field_t GetValueAtBit(size_t index) {
448  // @CAO This function needs to be generalized to return more then sizeof(field_t)*8 bits.
449  static_assert(OUT_BITS <= sizeof(field_t)*8, "Requesting too many bits to fit in a UInt");
450  return GetUIntAtBit(index) & MaskLow<field_t>(OUT_BITS);
451  }
452 
454  bool Any() const {
455  const size_t NUM_FIELDS = NumFields();
456  for (size_t i = 0; i < NUM_FIELDS; i++) {
457  if (bit_set[i]) return true;
458  }
459  return false;
460  }
461 
463  bool None() const { return !Any(); }
464 
466  bool All() const { return (~(*this)).None(); }
467 
469  explicit operator bool() const { return Any(); }
470 
472  bool operator[](size_t index) const { return Get(index); }
473 
475  BitProxy operator[](size_t index) { return BitProxy(*this, index); }
476 
478  void Clear() {
479  const size_t NUM_FIELDS = NumFields();
480  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = 0U;
481  }
482 
484  void SetAll() {
485  const size_t NUM_FIELDS = NumFields();
486  constexpr field_t all0 = 0;
487  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~all0;
488  if (LastBitID() > 0) { bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID()); }
489  }
490 
492  void Print(std::ostream & out=std::cout) const {
493  for (size_t i = num_bits; i > 0; --i) out << Get(i-1);
494  }
495 
497  void PrintFields(std::ostream & out=std::cout, const std::string spacer=" ") const {
498  for (size_t i = num_bits; i > 0; i--) {
499  out << Get(i-1);
500  if (i % FIELD_BITS == 0) out << spacer;
501  }
502  }
503 
505  void PrintArray(std::ostream & out=std::cout) const {
506  for (size_t i = 0; i < num_bits; i++) out << Get(i);
507  }
508 
510  void PrintOneIDs(std::ostream & out=std::cout, std::string spacer=" ") const {
511  for (size_t i = 0; i < num_bits; i++) { if (Get(i)) out << i << spacer; }
512  }
513 
514 
516  size_t CountOnes_Sparse() const {
517  const size_t NUM_FIELDS = NumFields();
518  size_t bit_count = 0;
519  for (size_t i = 0; i < NUM_FIELDS; i++) {
520  field_t cur_field = bit_set[i];
521  while (cur_field) {
522  cur_field &= (cur_field-1); // Peel off a single 1.
523  bit_count++; // And increment the counter
524  }
525  }
526  return bit_count;
527  }
528 
530  size_t CountOnes_Mixed() const {
531  const size_t NUM_FIELDS = NumFields() * sizeof(field_t)/4;
532  Ptr<const uint32_t> uint_bit_set = bit_set.Cast<const uint32_t>();
533  size_t bit_count = 0;
534  for (size_t i = 0; i < NUM_FIELDS; i++) {
535  const uint32_t v = uint_bit_set[i];
536  const uint32_t t1 = v - ((v >> 1) & 0x55555555);
537  const uint32_t t2 = (t1 & 0x33333333) + ((t1 >> 2) & 0x33333333);
538  bit_count += (((t2 + (t2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
539  }
540  return bit_count;
541  }
542 
544  size_t CountOnes() const { return CountOnes_Mixed(); }
545 
547  int FindBit() const {
548  const size_t NUM_FIELDS = NumFields();
549  size_t field_id = 0;
550  while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
551  return (field_id < NUM_FIELDS) ?
552  (int) (find_bit(bit_set[field_id]) + (field_id * FIELD_BITS)) : -1;
553  }
554 
556  int PopBit() {
557  const size_t NUM_FIELDS = NumFields();
558  size_t field_id = 0;
559  while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
560  if (field_id == NUM_FIELDS) return -1; // Failed to find bit!
561 
562  const size_t pos_found = find_bit(bit_set[field_id]);
563  constexpr field_t val_one = 1;
564  bit_set[field_id] &= ~(val_one << pos_found);
565  return (int) (pos_found + (field_id * FIELD_BITS));
566  }
567 
572 
573  int FindBit(const size_t start_pos) const {
574  if (start_pos >= num_bits) return -1;
575  size_t field_id = FieldID(start_pos); // What field do we start in?
576  const size_t field_pos = FieldPos(start_pos); // What position in that field?
577  if (field_pos && (bit_set[field_id] & ~(MaskLow<field_t>(field_pos)))) { // First field hit!
578  return (int) (find_bit(bit_set[field_id] & ~(MaskLow<field_t>(field_pos))) +
579  field_id * FIELD_BITS);
580  }
581 
582  // Search other fields...
583  const size_t NUM_FIELDS = NumFields();
584  if (field_pos) field_id++;
585  while (field_id < NUM_FIELDS && bit_set[field_id]==0) field_id++;
586  return (field_id < NUM_FIELDS) ?
587  (int) (find_bit(bit_set[field_id]) + (field_id * FIELD_BITS)) : -1;
588  }
589 
592  // @CAO -- There are probably better ways to do this with bit tricks.
593  emp::vector<size_t> out_set(CountOnes());
594  size_t cur_pos = 0;
595  for (size_t i = 0; i < num_bits; i++) {
596  if (Get(i)) out_set[cur_pos++] = i;
597  }
598  return out_set;
599  }
600 
602  BitVector NOT() const {
603  const size_t NUM_FIELDS = NumFields();
604  BitVector out_set(*this);
605  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~bit_set[i];
606  if (LastBitID() > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
607  return out_set;
608  }
609 
611  BitVector AND(const BitVector & set2) const {
612  const size_t NUM_FIELDS = NumFields();
613  BitVector out_set(*this);
614  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] & set2.bit_set[i];
615  return out_set;
616  }
617 
619  BitVector OR(const BitVector & set2) const {
620  const size_t NUM_FIELDS = NumFields();
621  BitVector out_set(*this);
622  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] | set2.bit_set[i];
623  return out_set;
624  }
625 
627  BitVector NAND(const BitVector & set2) const {
628  const size_t NUM_FIELDS = NumFields();
629  BitVector out_set(*this);
630  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] & set2.bit_set[i]);
631  if (LastBitID() > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
632  return out_set;
633  }
634 
636  BitVector NOR(const BitVector & set2) const {
637  const size_t NUM_FIELDS = NumFields();
638  BitVector out_set(*this);
639  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] | set2.bit_set[i]);
640  if (LastBitID() > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
641  return out_set;
642  }
643 
645  BitVector XOR(const BitVector & set2) const {
646  const size_t NUM_FIELDS = NumFields();
647  BitVector out_set(*this);
648  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = bit_set[i] ^ set2.bit_set[i];
649  return out_set;
650  }
651 
653  BitVector EQU(const BitVector & set2) const {
654  const size_t NUM_FIELDS = NumFields();
655  BitVector out_set(*this);
656  for (size_t i = 0; i < NUM_FIELDS; i++) out_set.bit_set[i] = ~(bit_set[i] ^ set2.bit_set[i]);
657  if (LastBitID() > 0) out_set.bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
658  return out_set;
659  }
660 
661 
664  const size_t NUM_FIELDS = NumFields();
665  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~bit_set[i];
666  if (LastBitID() > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
667  return *this;
668  }
669 
671  BitVector & AND_SELF(const BitVector & set2) {
672  const size_t NUM_FIELDS = NumFields();
673  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] & set2.bit_set[i];
674  return *this;
675  }
676 
678  BitVector & OR_SELF(const BitVector & set2) {
679  const size_t NUM_FIELDS = NumFields();
680  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] | set2.bit_set[i];
681  return *this;
682  }
683 
685  BitVector & NAND_SELF(const BitVector & set2) {
686  const size_t NUM_FIELDS = NumFields();
687  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] & set2.bit_set[i]);
688  if (LastBitID() > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
689  return *this;
690  }
691 
693  BitVector & NOR_SELF(const BitVector & set2) {
694  const size_t NUM_FIELDS = NumFields();
695  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] | set2.bit_set[i]);
696  if (LastBitID() > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
697  return *this;
698  }
699 
701  BitVector & XOR_SELF(const BitVector & set2) {
702  const size_t NUM_FIELDS = NumFields();
703  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = bit_set[i] ^ set2.bit_set[i];
704  return *this;
705  }
706 
708  BitVector & EQU_SELF(const BitVector & set2) {
709  const size_t NUM_FIELDS = NumFields();
710  for (size_t i = 0; i < NUM_FIELDS; i++) bit_set[i] = ~(bit_set[i] ^ set2.bit_set[i]);
711  if (LastBitID() > 0) bit_set[NUM_FIELDS - 1] &= MaskLow<field_t>(LastBitID());
712  return *this;
713  }
714 
716  BitVector SHIFT(const int shift_size) const {
717  BitVector out_set(*this);
718  if (shift_size > 0) out_set.ShiftRight((size_t) shift_size);
719  else if (shift_size < 0) out_set.ShiftLeft((size_t) -shift_size);
720  return out_set;
721  }
722 
724  BitVector & SHIFT_SELF(const int shift_size) {
725  if (shift_size > 0) ShiftRight((size_t) shift_size);
726  else if (shift_size < 0) ShiftLeft((size_t) -shift_size);
727  return *this;
728  }
729 
730 
732  BitVector operator~() const { return NOT(); }
733 
735  BitVector operator&(const BitVector & ar2) const { return AND(ar2); }
736 
738  BitVector operator|(const BitVector & ar2) const { return OR(ar2); }
739 
741  BitVector operator^(const BitVector & ar2) const { return XOR(ar2); }
742 
744  inline BitVector operator<<(const size_t shift_size) const { return SHIFT(-(int)shift_size); }
745 
747  inline BitVector operator>>(const size_t shift_size) const { return SHIFT((int)shift_size); }
748 
750  const BitVector & operator&=(const BitVector & ar2) { return AND_SELF(ar2); }
751 
753  const BitVector & operator|=(const BitVector & ar2) { return OR_SELF(ar2); }
754 
756  const BitVector & operator^=(const BitVector & ar2) { return XOR_SELF(ar2); }
757 
759  const BitVector & operator<<=(const size_t shift_size) { return SHIFT_SELF(-(int)shift_size); }
760 
762  const BitVector & operator>>=(const size_t shift_size) { return SHIFT_SELF((int)shift_size); }
763 
765  size_t size() const { return num_bits; }
766 
768  void resize(std::size_t new_size) { Resize(new_size); }
769 
771  bool all() const { return All(); }
772 
774  bool any() const { return Any(); }
775 
777  bool none() const { return !Any(); }
778 
780  size_t count() const { return CountOnes_Mixed(); }
781  };
782 
783 }
784 
785 namespace std {
787  template <>
788  struct hash<emp::BitVector> {
789  std::size_t operator()(const emp::BitVector & b) const {
790  return b.Hash();
791  }
792  };
793 
795  inline std::ostream & operator<<(std::ostream & out, const emp::BitVector & bit_v) {
796  bit_v.Print(out);
797  return out;
798  }
799 }
800 
801 #endif
Useful mathematical functions (that are constexpr when possible.)
bool any() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:774
void SetAll()
Set all bits to 1.
Definition: BitVector.h:484
BitVector EQU(const BitVector &set2) const
Perform a Boolean EQU on this BitVector and return the result.
Definition: BitVector.h:653
void Print(std::ostream &out=std::cout) const
Regular print function (from most significant bit to least)
Definition: BitVector.h:492
~BitVector()
Destructor.
Definition: BitVector.h:254
BitVector operator>>(const size_t shift_size) const
Operator shift right...
Definition: BitVector.h:747
size_t size() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:765
size_t CountOnes() const
Count the number of ones in the BitVector.
Definition: BitVector.h:544
BitVector & NOT_SELF()
Perform a Boolean NOT with this BitVector, store result here, and return this object.
Definition: BitVector.h:663
bool Any() const
Return true if ANY bits are set to 1, otherwise return false.
Definition: BitVector.h:454
void Clear()
Set all bits to 0.
Definition: BitVector.h:478
size_t CountOnes_Mixed() const
Count 1&#39;s in semi-parallel; fastest for even 0&#39;s & 1&#39;s.
Definition: BitVector.h:530
size_t DebugGetArrayBytes() const
Definition: Ptr.h:791
uint32_t GetUIntAtBit(size_t index)
Retrive the 32-bit uint at the specified BIT index.
Definition: BitVector.h:432
bool DebugIsArray() const
Definition: Ptr.h:790
uint32_t GetUInt(size_t index) const
Retrive the 32-bit uint from the specifeid uint index.
Definition: BitVector.h:418
void PrintFields(std::ostream &out=std::cout, const std::string spacer=" ") const
Print a space between each field (or other provided spacer)
Definition: BitVector.h:497
bool operator>=(const BitVector &in_set) const
Compare the would-be numerical values of two bit vectors.
Definition: BitVector.h:365
bool All() const
Return true if ALL bits are set to 1, otherwise return false.
Definition: BitVector.h:466
BitVector & Resize(size_t new_bits)
Resize this BitVector to have the specified number of bits.
Definition: BitVector.h:297
BitVector operator|(const BitVector &ar2) const
Operator bitwise OR...
Definition: BitVector.h:738
BitVector NOT() const
Perform a Boolean NOT on this BitVector and return the result.
Definition: BitVector.h:602
const BitVector & operator&=(const BitVector &ar2)
Compound operator bitwise AND...
Definition: BitVector.h:750
Definition: BitVector.h:785
A drop-in replacement for std::vector<bool>, but with extra bitwise logic features.
Definition: BitVector.h:39
A set of simple functions to manipulate bitsets.
emp::vector< size_t > GetOnes() const
Return positions of all ones.
Definition: BitVector.h:591
bool operator==(const BitVector &in_set) const
Test if two bit vectors are identical.
Definition: BitVector.h:322
BitVector(size_t in_num_bits=0, bool init_val=false)
Build a new BitVector with specified bit count (default 0) and initialization (default 0) ...
Definition: BitVector.h:227
BitProxy operator[](size_t index)
Index operator – return a proxy to the bit at the specified position so it can be an lvalue...
Definition: BitVector.h:475
bool None() const
Return true if NO bits are set to 1, otherwise return false.
Definition: BitVector.h:463
const BitVector & operator^=(const BitVector &ar2)
Compound operator bitwise XOR...
Definition: BitVector.h:756
const BitVector & operator|=(const BitVector &ar2)
Compound operator bitwise OR...
Definition: BitVector.h:753
int FindBit() const
Return the position of the first one; return -1 if no ones in vector.
Definition: BitVector.h:547
bool operator!=(const BitVector &in_set) const
Determine if two bit vectors are different.
Definition: BitVector.h:359
bool all() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:771
bool OK() const
Definition: Ptr.h:793
field_t GetValueAtBit(size_t index)
Retrieve the specified number of bits (stored in the field type) at the target bit index...
Definition: BitVector.h:447
BitVector & XOR_SELF(const BitVector &set2)
Perform a Boolean XOR with this BitVector, store result here, and return this object.
Definition: BitVector.h:701
BitVector NAND(const BitVector &set2) const
Perform a Boolean NAND on this BitVector and return the result.
Definition: BitVector.h:627
BitVector & operator=(BitVector &&in_set)
Move operator.
Definition: BitVector.h:286
bool Get(size_t index) const
Retrive the bit value from the specified index.
Definition: BitVector.h:371
BitVector & SHIFT_SELF(const int shift_size)
Positive shifts go left and negative go right; store result here, and return this object...
Definition: BitVector.h:724
BitVector OR(const BitVector &set2) const
Perform a Boolean OR on this BitVector and return the result.
Definition: BitVector.h:619
void DeleteArray()
Definition: Ptr.h:738
void PrintOneIDs(std::ostream &out=std::cout, std::string spacer=" ") const
Print the positions of all one bits, spaces are the default separator.
Definition: BitVector.h:510
bool operator>(const BitVector &in_set) const
Compare the would-be numerical values of two bit vectors.
Definition: BitVector.h:362
BitVector XOR(const BitVector &set2) const
Perform a Boolean XOR on this BitVector and return the result.
Definition: BitVector.h:645
void SetUInt(size_t index, uint32_t value)
Update the 32-bit uint at the specified uint index.
Definition: BitVector.h:425
std::size_t operator()(const emp::BitVector &b) const
Definition: BitVector.h:789
Ptr< T2 > Cast()
Definition: Ptr.h:730
BitVector SHIFT(const int shift_size) const
Positive shifts go left and negative go right (0 does nothing); return result.
Definition: BitVector.h:716
int PopBit()
Return the position of the first one and change it to a zero. Return -1 if no ones.
Definition: BitVector.h:556
void PrintArray(std::ostream &out=std::cout) const
Print from smallest bit position to largest.
Definition: BitVector.h:505
bool none() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:777
BitVector(BitVector &&in_set)
Move constructor of existing bit field.
Definition: BitVector.h:244
BitVector & NAND_SELF(const BitVector &set2)
Perform a Boolean NAND with this BitVector, store result here, and return this object.
Definition: BitVector.h:685
size_t CountOnes_Sparse() const
Count 1&#39;s by looping through once for each bit equal to 1.
Definition: BitVector.h:516
uint8_t GetByte(size_t index) const
Retrive the byte at the specified byte index.
Definition: BitVector.h:401
const BitVector & operator<<=(const size_t shift_size)
Compound operator for shift left...
Definition: BitVector.h:759
If we are in emscripten, make sure to include the header.
Definition: array.h:37
BitVector & operator=(const BitVector &in_set)
Assignment operator.
Definition: BitVector.h:262
std::size_t Hash() const
A simple hash function for bit vectors.
Definition: BitVector.h:391
BitVector operator~() const
Operator bitwise NOT...
Definition: BitVector.h:732
void resize(std::size_t new_size)
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:768
bool operator[](size_t index) const
Const index operator – return the bit at the specified position.
Definition: BitVector.h:472
#define emp_assert(...)
Definition: assert.h:199
constexpr size_t find_bit(const uint64_t &val)
Return the position of the first one bit (in a 64-bit unsigned int)
Definition: bitset_utils.h:61
BitVector & NOR_SELF(const BitVector &set2)
Perform a Boolean NOR with this BitVector, store result here, and return this object.
Definition: BitVector.h:693
const BitVector & operator>>=(const size_t shift_size)
Compound operator for shift right...
Definition: BitVector.h:762
BitVector & AND_SELF(const BitVector &set2)
Perform a Boolean AND with this BitVector, store result here, and return this object.
Definition: BitVector.h:671
BitVector operator^(const BitVector &ar2) const
Operator bitwise XOR...
Definition: BitVector.h:741
void SetByte(size_t index, uint8_t value)
Update the byte at the specified byte index.
Definition: BitVector.h:409
bool operator<(const BitVector &in_set) const
Compare the would-be numerical values of two bit vectors.
Definition: BitVector.h:333
bool IsNull() const
Definition: Ptr.h:727
BitVector AND(const BitVector &set2) const
Perform a Boolean AND on this BitVector and return the result.
Definition: BitVector.h:611
int FindBit(const size_t start_pos) const
Definition: BitVector.h:573
BitVector operator&(const BitVector &ar2) const
Operator bitwise AND...
Definition: BitVector.h:735
void Set(size_t index, bool value=true)
Update the bit value at the specified index.
Definition: BitVector.h:379
BitVector operator<<(const size_t shift_size) const
Operator shift left...
Definition: BitVector.h:744
BitVector(const BitVector &in_set)
Copy constructor of existing bit field.
Definition: BitVector.h:233
BitVector & EQU_SELF(const BitVector &set2)
Perform a Boolean EQU with this BitVector, store result here, and return this object.
Definition: BitVector.h:708
BitVector & OR_SELF(const BitVector &set2)
Perform a Boolean OR with this BitVector, store result here, and return this object.
Definition: BitVector.h:678
size_t GetSize() const
How many bits do we currently have?
Definition: BitVector.h:368
size_t count() const
Function to allow drop-in replacement with std::vector<bool>.
Definition: BitVector.h:780
bool operator<=(const BitVector &in_set) const
Compare the would-be numerical values of two bit vectors.
Definition: BitVector.h:346
BitVector NOR(const BitVector &set2) const
Perform a Boolean NOR on this BitVector and return the result.
Definition: BitVector.h:636