A library for working with phylogenetic and population genetic data.
v0.32.0
bitvector.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_MATH_BITVECTOR_H_
2 #define GENESIS_UTILS_MATH_BITVECTOR_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2024 Lucas Czech
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lczech@carnegiescience.edu>
23  Department of Plant Biology, Carnegie Institution For Science
24  260 Panama Street, Stanford, CA 94305, USA
25 */
26 
34 #include <array>
35 #include <cassert>
36 #include <cstdint>
37 #include <iterator>
38 #include <limits>
39 #include <stdexcept>
40 #include <string>
41 #include <vector>
42 
43 namespace genesis {
44 namespace utils {
45 
46 // =================================================================================================
47 // Bitvector
48 // =================================================================================================
49 
50 class Bitvector
51 {
52 public:
53 
54  // ---------------------------------------------------------
55  // Typedefs, Enums, Constants
56  // ---------------------------------------------------------
57 
58  using IntType = uint64_t;
59  static const size_t IntSize = sizeof(IntType) * 8;
60 
64  static const size_t npos = std::numeric_limits<size_t>::max();
65 
66  // ---------------------------------------------------------
67  // Constructor and Rule of Five
68  // ---------------------------------------------------------
69 
73  Bitvector() = default;
74 
79  Bitvector( size_t size, bool initial_value = false)
80  : size_(size)
81  {
82  // Edge case.
83  if( size == 0 ) {
84  return;
85  }
86 
87  // reserve enough bits, and init them.
88  data_.resize( (size / IntSize) + (size % IntSize == 0 ? 0 : 1) );
89  set_all(initial_value);
90  }
91 
95  Bitvector( size_t size, std::initializer_list<size_t> list )
96  : Bitvector(size, false)
97  {
98  for( size_t e : list ) {
99  set(e);
100  }
101  }
102 
109  template<class It>
110  Bitvector( It first, It last )
111  : Bitvector( std::distance( first,last ), false )
112  {
113  size_t i = 0;
114  for( auto it = first; it != last; ++it ) {
115  set( i, *it );
116  ++i;
117  }
118  }
119 
126  Bitvector( size_t size, Bitvector const& other );
127 
134  Bitvector( std::string const& values );
135 
136  // /* *
137  // * @brief Create a Bitvector by copying the first @p max_size of another Bitvector.
138  // *
139  // * If `max_size > other.size()`, all max_size are used.
140  // */
141  // Bitvector( Bitvector const& other, size_t max_size );
142 
143  ~Bitvector() = default;
144 
145  Bitvector(Bitvector const&) = default;
146  Bitvector(Bitvector&&) = default;
147 
148  Bitvector& operator= (Bitvector const&) = default;
149  Bitvector& operator= (Bitvector&&) = default;
150 
151  // ---------------------------------------------------------
152  // Single Bit Functions
153  // ---------------------------------------------------------
154 
158  inline bool operator [] ( size_t index ) const {
159  assert( index / IntSize < data_.size() );
160  assert( index % IntSize < bit_mask_.size() );
161  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
162  }
163 
167  inline bool get( size_t index ) const
168  {
169  if( index >= size_ ) {
170  throw std::out_of_range(
171  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
173  );
174  }
175 
176  assert( index / IntSize < data_.size() );
177  assert( index % IntSize < bit_mask_.size() );
178  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
179  }
180 
184  inline void set( size_t index )
185  {
186  if (index >= size_) {
187  throw std::out_of_range(
188  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
190  );
191  }
192 
193  assert( index / IntSize < data_.size() );
194  assert( index % IntSize < bit_mask_.size() );
195  data_[index / IntSize] |= bit_mask_[index % IntSize];
196  }
197 
201  inline void unset( size_t index )
202  {
203  if( index >= size_ ) {
204  throw std::out_of_range(
205  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
207  );
208  }
209 
210  assert( index / IntSize < data_.size() );
211  assert( index % IntSize < bit_mask_.size() );
212  data_[index / IntSize] &= ~(bit_mask_[index % IntSize]);
213  }
214 
218  inline void set( size_t index, bool value )
219  {
220  if( value ) {
221  set( index );
222  } else {
223  unset( index );
224  }
225  }
226 
242  void set( size_t first, size_t last, bool value = true );
243 
247  inline void flip( size_t index )
248  {
249  if( index >= size_ ) {
250  throw std::out_of_range(
251  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
253  );
254  }
255 
256  assert( index / IntSize < data_.size() );
257  assert( index % IntSize < bit_mask_.size() );
258  data_[index / IntSize] ^= bit_mask_[index % IntSize];
259  }
260 
264  inline void toggle( size_t index )
265  {
266  return flip( index );
267  }
268 
269  // ---------------------------------------------------------
270  // Operators
271  // ---------------------------------------------------------
272 
273  Bitvector& operator &= (Bitvector const& rhs);
274  Bitvector& operator |= (Bitvector const& rhs);
275  Bitvector& operator ^= (Bitvector const& rhs);
276  Bitvector operator ~ () const;
277 
278  friend Bitvector operator & (Bitvector const& lhs, Bitvector const& rhs);
279  friend Bitvector operator | (Bitvector const& lhs, Bitvector const& rhs);
280  friend Bitvector operator ^ (Bitvector const& lhs, Bitvector const& rhs);
281 
282  bool operator == (const Bitvector &other) const;
283  bool operator != (const Bitvector &other) const;
284 
285  // ---------------------------------------------------------
286  // Other Functions
287  // ---------------------------------------------------------
288 
296  inline bool empty() const
297  {
298  return size_ == 0;
299  }
300 
304  inline size_t size() const
305  {
306  return size_;
307  }
308 
313  size_t count() const;
314 
331  size_t count( size_t first, size_t last ) const;
332 
336  bool any_set() const;
337 
345  size_t find_next_set( size_t start ) const;
346 
350  size_t hash() const;
351 
359  IntType x_hash() const;
360 
364  void negate();
365 
372  void normalize();
373 
377  void set_all(const bool value = false);
378 
379  std::string dump() const;
380  std::string dump_int(IntType x) const;
381 
382  std::vector<IntType> const& data() const
383  {
384  return data_;
385  }
386 
387  // ---------------------------------------------------------
388  // Internal Members
389  // ---------------------------------------------------------
390 
391 private:
392 
400  void unset_padding_();
401 
405  static size_t count_( IntType x );
406 
407  static const IntType all_0_;
408  static const IntType all_1_;
409 
413  static const std::array<IntType, IntSize> bit_mask_;
414 
429  static const std::array<IntType, IntSize> ones_mask_;
430 
437  static const std::array<IntType, 4> count_mask_;
438 
439  // ---------------------------------------------------------
440  // Data Members
441  // ---------------------------------------------------------
442 
443  size_t size_ = 0;
444  std::vector<IntType> data_;
445 };
446 
447 // =============================================================================
448 // Hashing
449 // =============================================================================
450 
465 {
466  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
467  {
468  return value.hash();
469  }
470 };
471 
488 {
489  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
490  {
491  return static_cast<std::size_t>( value.x_hash() );
492  }
493 };
494 
495 } // namespace utils
496 } // namespace genesis
497 
498 // =============================================================================
499 // Namespace std extension
500 // =============================================================================
501 
502 namespace std {
503 
511 template<>
512 struct hash<genesis::utils::Bitvector>
513 {
514  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
515  {
516  return value.hash();
517  }
518 };
519 
520 } // namespace std
521 
522 #endif // include guard
genesis::utils::Bitvector::operator~
Bitvector operator~() const
Definition: bitvector.cpp:264
genesis::utils::Bitvector::x_hash
IntType x_hash() const
Return a hash value of type IntType that is quicker to calculate than hash().
Definition: bitvector.cpp:492
genesis::utils::Bitvector::Bitvector
Bitvector(size_t size, bool initial_value=false)
Constructor that takes a size and an optional bool value to initialize the Bitvector,...
Definition: bitvector.hpp:79
genesis::utils::Bitvector::set
void set(size_t index)
Set the value of a single bit to true, with boundary check.
Definition: bitvector.hpp:184
genesis::utils::BitvectorHash
Helper structure that yields the hash of a given Bitvector.
Definition: bitvector.hpp:464
genesis::utils::Bitvector::get
bool get(size_t index) const
Return the value of a single bit, with boundary check.
Definition: bitvector.hpp:167
genesis::utils::Bitvector::operator|
friend Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:278
genesis::utils::Bitvector::find_next_set
size_t find_next_set(size_t start) const
Return the index of the next position in the Bitvector that is set.
Definition: bitvector.cpp:410
genesis::utils::Bitvector::operator[]
bool operator[](size_t index) const
Return the value of a single bit, without boundary check.
Definition: bitvector.hpp:158
genesis::utils::Bitvector::data
std::vector< IntType > const & data() const
Definition: bitvector.hpp:382
genesis::utils::Bitvector::flip
void flip(size_t index)
Flip (negate) the value of a single bit, with boundary check.
Definition: bitvector.hpp:247
genesis::utils::Bitvector::operator!=
bool operator!=(const Bitvector &other) const
Definition: bitvector.cpp:305
genesis::utils::Bitvector::set
void set(size_t index, bool value)
Set the value of a single bit to a given bool value, with boundary check.
Definition: bitvector.hpp:218
genesis::utils::Bitvector::Bitvector
Bitvector(size_t size, std::initializer_list< size_t > list)
Constructor that takes a size and a list of values (positions) to be set to true.
Definition: bitvector.hpp:95
genesis::utils::Bitvector::operator&=
Bitvector & operator&=(Bitvector const &rhs)
Definition: bitvector.cpp:219
genesis::population::to_string
std::string to_string(GenomeLocus const &locus)
Definition: function/genome_locus.hpp:52
genesis::utils::Bitvector::dump
std::string dump() const
Definition: bitvector.cpp:580
genesis::utils::Bitvector::Bitvector
Bitvector()=default
Default constructor. Creates an empty Bitvector of size 0.
genesis::utils::Bitvector::operator|=
Bitvector & operator|=(Bitvector const &rhs)
Definition: bitvector.cpp:234
genesis::utils::Bitvector::Bitvector
Bitvector(It first, It last)
Construct a Bitvector using a range of bools.
Definition: bitvector.hpp:110
genesis::utils::Bitvector::negate
void negate()
Flip all bits.
Definition: bitvector.cpp:501
genesis::utils::Bitvector::~Bitvector
~Bitvector()=default
genesis::utils::Bitvector::toggle
void toggle(size_t index)
Alias for flip(), see there for details.
Definition: bitvector.hpp:264
genesis::utils::Bitvector::hash
size_t hash() const
Return an std::hash value for the Bitvector.
Definition: bitvector.cpp:483
genesis::utils::Bitvector::operator&
friend Bitvector operator&(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:271
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::utils::Bitvector::IntSize
static const size_t IntSize
Definition: bitvector.hpp:59
genesis::utils::Bitvector::operator==
bool operator==(const Bitvector &other) const
Definition: bitvector.cpp:292
genesis::utils::Bitvector::empty
bool empty() const
Return whether the Bitvector is empty, that is, has size() == 0.
Definition: bitvector.hpp:296
genesis::utils::Bitvector::dump_int
std::string dump_int(IntType x) const
Definition: bitvector.cpp:594
genesis::utils::BitvectorHash::operator()
std::size_t operator()(genesis::utils::Bitvector const &value) const
Definition: bitvector.hpp:466
genesis::utils::BitvectorXhash
Helper structer that yields the x_hash of a given Bitvector.
Definition: bitvector.hpp:487
genesis::utils::BitvectorXhash::operator()
std::size_t operator()(genesis::utils::Bitvector const &value) const
Definition: bitvector.hpp:489
genesis::utils::Bitvector::normalize
void normalize()
Bring the Bitvector in a normalized form, where the first bit is always zero.
Definition: bitvector.cpp:512
genesis::utils::Bitvector::set_all
void set_all(const bool value=false)
Set all the bits to a specified value.
Definition: bitvector.cpp:519
genesis::utils::Bitvector::IntType
uint64_t IntType
Definition: bitvector.hpp:58
genesis::utils::Bitvector::count
size_t count() const
Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popc...
Definition: bitvector.cpp:314
genesis::utils::Bitvector::operator=
Bitvector & operator=(Bitvector const &)=default
genesis::utils::Bitvector::size
size_t size() const
Return the size (number of bits) of this Bitvector.
Definition: bitvector.hpp:304
genesis::utils::Bitvector::npos
static const size_t npos
Value to indicate that find_next_set() did not find any set bits.
Definition: bitvector.hpp:64
genesis::utils::Bitvector::any_set
bool any_set() const
Return if any bits are set at all.
Definition: bitvector.cpp:400
genesis::utils::Bitvector::operator^=
Bitvector & operator^=(Bitvector const &rhs)
Definition: bitvector.cpp:249
genesis::utils::Bitvector::operator^
friend Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:285
genesis::utils::Bitvector::unset
void unset(size_t index)
Set the value of a single bit to false, with boundary check.
Definition: bitvector.hpp:201
genesis::utils::Bitvector
Definition: bitvector.hpp:50