A toolkit for working with phylogenetic data.
v0.24.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-2020 Lucas Czech and HITS gGmbH
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  // ---------------------------------------------------------
277  // Internal Members
278  // ---------------------------------------------------------
279 
280 private:
281 
289  void unset_padding_();
290 
291  static const IntType all_0_;
292  static const IntType all_1_;
293 
297  static const std::array<IntType, IntSize> bit_mask_;
298 
316  static const std::array<IntType, IntSize> ones_mask_;
317 
321  static const std::array<IntType, 4> count_mask_;
322 
323  // ---------------------------------------------------------
324  // Data Members
325  // ---------------------------------------------------------
326 
327  size_t size_ = 0;
328  std::vector<IntType> data_;
329 };
330 
331 // =============================================================================
332 // Hashing
333 // =============================================================================
334 
349 {
350  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
351  {
352  return value.hash();
353  }
354 };
355 
372 {
373  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
374  {
375  return static_cast<std::size_t>( value.x_hash() );
376  }
377 };
378 
379 } // namespace utils
380 } // namespace genesis
381 
382 // =============================================================================
383 // Namespace std extension
384 // =============================================================================
385 
386 namespace std {
387 
395 template<>
396 struct hash<genesis::utils::Bitvector>
397 {
398  std::size_t operator() ( genesis::utils::Bitvector const& value ) const
399  {
400  return value.hash();
401  }
402 };
403 
404 } // namespace std
405 
406 #endif // include guard
void unset(size_t index)
Set the value of a single bit to false, with boundary check.
Definition: bitvector.hpp:164
Bitvector & operator^=(Bitvector const &rhs)
Definition: bitvector.cpp:158
Bitvector & operator&=(Bitvector const &rhs)
Bitvector(size_t size, bool initial_value=false)
Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default.
Definition: bitvector.hpp:72
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
std::string dump() const
Definition: bitvector.cpp:327
bool operator[](size_t index) const
Return the value of a single bit, without boundary check.
Definition: bitvector.hpp:121
STL namespace.
Helper structer that yields the x_hash of a given Bitvector.
Definition: bitvector.hpp:371
IntType x_hash() const
Return a hash value of type IntType that is quicker to calculate than hash().
Definition: bitvector.cpp:261
static const size_t IntSize
Definition: bitvector.hpp:57
Bitvector()=default
Default constructor. Creates an empty Bitvector of size 0.
Bitvector operator~() const
Definition: bitvector.cpp:173
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
void negate()
Flip all bits.
Definition: bitvector.cpp:270
friend Bitvector operator&(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:180
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
void flip(size_t index)
Flip (negate) the value of a single bit, with boundary check.
Definition: bitvector.hpp:193
bool operator==(const Bitvector &other) const
Definition: bitvector.cpp:201
bool operator!=(const Bitvector &other) const
Definition: bitvector.cpp:214
Helper structure that yields the hash of a given Bitvector.
Definition: bitvector.hpp:348
friend Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:194
void normalize()
Bring the Bitvector in a normalized form, where the first bit is always zero.
Definition: bitvector.cpp:281
Bitvector & operator|=(Bitvector const &rhs)
Definition: bitvector.cpp:143
std::string dump_int(IntType x) const
Definition: bitvector.cpp:341
std::shared_ptr< BaseOutputTarget > to_string(std::string &target_string)
Obtain an output target for writing to a string.
Bitvector & operator=(Bitvector const &)=default
void set_all(const bool value=false)
Set all the bits to a specified value.
Definition: bitvector.cpp:288
size_t hash() const
Return an std::hash value for the Bitvector.
Definition: bitvector.cpp:252
size_t size() const
Return the size (number of bits) of this Bitvector.
Definition: bitvector.hpp:230
friend Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:187