A library for working with phylogenetic and population genetic data.
v0.27.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-2021 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 <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
34 #include <array>
35 #include <cassert>
36 #include <cstdint>
37 #include <stdexcept>
38 #include <string>
39 #include <vector>
40 
41 namespace genesis {
42 namespace utils {
43 
44 // =================================================================================================
45 // Bitvector
46 // =================================================================================================
47 
48 class Bitvector
49 {
50 public:
51 
52  // ---------------------------------------------------------
53  // Typedefs, Enums, Constants
54  // ---------------------------------------------------------
55 
56  using IntType = uint64_t;
57  static const size_t IntSize = sizeof(IntType) * 8;
58 
59  // ---------------------------------------------------------
60  // Constructor and Rule of Five
61  // ---------------------------------------------------------
62 
66  Bitvector() = default;
67 
72  Bitvector( size_t size, bool initial_value = false)
73  : size_(size)
74  {
75  // reserve enough bits, and init them.
76  data_.resize( (size / IntSize) + (size % IntSize == 0 ? 0 : 1) );
77  set_all(initial_value);
78  }
79 
83  Bitvector( size_t size, std::initializer_list<size_t> list)
84  : Bitvector(size, false)
85  {
86  for (size_t e : list) {
87  set(e);
88  }
89  }
90 
97  Bitvector( std::string const& values );
98 
104  Bitvector( Bitvector const& other, size_t max_size );
105 
106  ~Bitvector() = default;
107 
108  Bitvector(Bitvector const&) = default;
109  Bitvector(Bitvector&&) = default;
110 
111  Bitvector& operator= (Bitvector const&) = default;
112  Bitvector& operator= (Bitvector&&) = default;
113 
114  // ---------------------------------------------------------
115  // Single Bit Functions
116  // ---------------------------------------------------------
117 
121  inline bool operator [] (size_t index) const {
122  assert( index / IntSize < data_.size() );
123  assert( index % IntSize < bit_mask_.size() );
124  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
125  }
126 
130  inline bool get (size_t index) const
131  {
132  if (index >= size_) {
133  throw std::out_of_range(
134  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
136  );
137  }
138 
139  assert( index / IntSize < data_.size() );
140  assert( index % IntSize < bit_mask_.size() );
141  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
142  }
143 
147  inline void set (size_t index)
148  {
149  if (index >= size_) {
150  throw std::out_of_range(
151  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
153  );
154  }
155 
156  assert( index / IntSize < data_.size() );
157  assert( index % IntSize < bit_mask_.size() );
158  data_[index / IntSize] |= bit_mask_[index % IntSize];
159  }
160 
164  inline void unset (size_t index)
165  {
166  if (index >= size_) {
167  throw std::out_of_range(
168  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
170  );
171  }
172 
173  assert( index / IntSize < data_.size() );
174  assert( index % IntSize < bit_mask_.size() );
175  data_[index / IntSize] &= ~(bit_mask_[index % IntSize]);
176  }
177 
181  inline void set (size_t index, bool value)
182  {
183  if (value) {
184  set(index);
185  } else {
186  unset(index);
187  }
188  }
189 
193  inline void flip (size_t index)
194  {
195  if (index >= size_) {
196  throw std::out_of_range(
197  "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
199  );
200  }
201 
202  assert( index / IntSize < data_.size() );
203  assert( index % IntSize < bit_mask_.size() );
204  data_[index / IntSize] ^= bit_mask_[index % IntSize];
205  }
206 
207  // ---------------------------------------------------------
208  // Operators
209  // ---------------------------------------------------------
210 
211  Bitvector& operator &= (Bitvector const& rhs);
212  Bitvector& operator |= (Bitvector const& rhs);
213  Bitvector& operator ^= (Bitvector const& rhs);
214  Bitvector operator ~ () const;
215 
216  friend Bitvector operator & (Bitvector const& lhs, Bitvector const& rhs);
217  friend Bitvector operator | (Bitvector const& lhs, Bitvector const& rhs);
218  friend Bitvector operator ^ (Bitvector const& lhs, Bitvector const& rhs);
219 
220  bool operator == (const Bitvector &other) const;
221  bool operator != (const Bitvector &other) const;
222 
223  // ---------------------------------------------------------
224  // Other Functions
225  // ---------------------------------------------------------
226 
230  inline size_t size() const
231  {
232  return size_;
233  }
234 
239  size_t count() const;
240 
244  size_t hash() const;
245 
253  IntType x_hash() const;
254 
258  void negate();
259 
266  void normalize();
267 
271  void set_all(const bool value = false);
272 
273  std::string dump() const;
274  std::string dump_int(IntType x) const;
275 
276  std::vector<IntType> const& data() const
277  {
278  return data_;
279  }
280 
281  // ---------------------------------------------------------
282  // Internal Members
283  // ---------------------------------------------------------
284 
285 private:
286 
294  void unset_padding_();
295 
296  static const IntType all_0_;
297  static const IntType all_1_;
298 
302  static const std::array<IntType, IntSize> bit_mask_;
303 
321  static const std::array<IntType, IntSize> ones_mask_;
322 
326  static const std::array<IntType, 4> count_mask_;
327 
328  // ---------------------------------------------------------
329  // Data Members
330  // ---------------------------------------------------------
331 
332  size_t size_ = 0;
333  std::vector<IntType> data_;
334 };
335 
336 // =============================================================================
337 // Hashing
338 // =============================================================================
339 
354 {
355  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
356  {
357  return value.hash();
358  }
359 };
360 
377 {
378  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
379  {
380  return static_cast<std::size_t>( value.x_hash() );
381  }
382 };
383 
384 } // namespace utils
385 } // namespace genesis
386 
387 // =============================================================================
388 // Namespace std extension
389 // =============================================================================
390 
391 namespace std {
392 
400 template<>
401 struct hash<genesis::utils::Bitvector>
402 {
403  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
404  {
405  return value.hash();
406  }
407 };
408 
409 } // namespace std
410 
411 #endif // include guard
genesis::utils::Bitvector::operator~
Bitvector operator~() const
Definition: bitvector.cpp:173
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:261
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:72
genesis::utils::Bitvector::set
void set(size_t index)
Set the value of a single bit to true, with boundary check.
Definition: bitvector.hpp:147
genesis::utils::BitvectorHash
Helper structure that yields the hash of a given Bitvector.
Definition: bitvector.hpp:353
genesis::utils::Bitvector::get
bool get(size_t index) const
Return the value of a single bit, with boundary check.
Definition: bitvector.hpp:130
genesis::utils::Bitvector::operator|
friend Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:187
genesis::utils::Bitvector::operator[]
bool operator[](size_t index) const
Return the value of a single bit, without boundary check.
Definition: bitvector.hpp:121
genesis::utils::Bitvector::data
std::vector< IntType > const & data() const
Definition: bitvector.hpp:276
genesis::utils::Bitvector::flip
void flip(size_t index)
Flip (negate) the value of a single bit, with boundary check.
Definition: bitvector.hpp:193
genesis::utils::Bitvector::operator!=
bool operator!=(const Bitvector &other) const
Definition: bitvector.cpp:214
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:181
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:83
genesis::utils::Bitvector::operator&=
Bitvector & operator&=(Bitvector const &rhs)
Definition: bitvector.cpp:128
genesis::population::to_string
std::string to_string(GenomeLocus const &locus)
Definition: functions/genome_locus.hpp:48
genesis::utils::Bitvector::dump
std::string dump() const
Definition: bitvector.cpp:327
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:143
genesis::utils::Bitvector::negate
void negate()
Flip all bits.
Definition: bitvector.cpp:270
genesis::utils::Bitvector::~Bitvector
~Bitvector()=default
genesis::utils::Bitvector::hash
size_t hash() const
Return an std::hash value for the Bitvector.
Definition: bitvector.cpp:252
genesis::utils::Bitvector::operator&
friend Bitvector operator&(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:180
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:57
genesis::utils::Bitvector::operator==
bool operator==(const Bitvector &other) const
Definition: bitvector.cpp:201
genesis::utils::Bitvector::dump_int
std::string dump_int(IntType x) const
Definition: bitvector.cpp:341
genesis::utils::BitvectorHash::operator()
std::size_t operator()(genesis::utils::Bitvector const &value) const
Definition: bitvector.hpp:355
genesis::utils::BitvectorXhash
Helper structer that yields the x_hash of a given Bitvector.
Definition: bitvector.hpp:376
genesis::utils::BitvectorXhash::operator()
std::size_t operator()(genesis::utils::Bitvector const &value) const
Definition: bitvector.hpp:378
genesis::utils::Bitvector::normalize
void normalize()
Bring the Bitvector in a normalized form, where the first bit is always zero.
Definition: bitvector.cpp:281
genesis::utils::Bitvector::set_all
void set_all(const bool value=false)
Set all the bits to a specified value.
Definition: bitvector.cpp:288
genesis::utils::Bitvector::IntType
uint64_t IntType
Definition: bitvector.hpp:56
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:223
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:230
genesis::utils::Bitvector::operator^=
Bitvector & operator^=(Bitvector const &rhs)
Definition: bitvector.cpp:158
genesis::utils::Bitvector::operator^
friend Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:194
genesis::utils::Bitvector::unset
void unset(size_t index)
Set the value of a single bit to false, with boundary check.
Definition: bitvector.hpp:164
genesis::utils::Bitvector
Definition: bitvector.hpp:48