A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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-2018 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 <cassert>
35 #include <cstdint>
36 #include <string>
37 #include <vector>
38 
39 namespace genesis {
40 namespace utils {
41 
42 // =================================================================================================
43 // Bitvector
44 // =================================================================================================
45 
46 class Bitvector
47 {
48 public:
49 
50  // ---------------------------------------------------------
51  // Typedefs, Enums, Constants
52  // ---------------------------------------------------------
53 
54  typedef uint64_t IntType;
55  static const size_t IntSize = sizeof(IntType) * 8;
56 
57  // ---------------------------------------------------------
58  // Constructor and Rule of Five
59  // ---------------------------------------------------------
60 
64  Bitvector() = default;
65 
70  Bitvector (const size_t size, const bool initial_value = false)
71  : size_(size)
72  {
73  // reserve enough bits, and init them.
74  data_.resize( (size / IntSize) + (size % IntSize == 0 ? 0 : 1) );
75  set_all(initial_value);
76  }
77 
81  Bitvector (const size_t size, const std::initializer_list<int> list)
82  : Bitvector(size, false)
83  {
84  for (int e : list) {
85  set(e);
86  }
87  }
88 
94  Bitvector( Bitvector const& other, size_t bits )
95  {
96  if( bits > other.size() ) {
97  bits = other.size();
98  }
99  size_ = bits;
100  auto const ds = (size_ / IntSize) + (size_ % IntSize == 0 ? 0 : 1);
101  assert( ds <= other.data_.size() );
102  data_ = std::vector<IntType>( other.data_.begin(), other.data_.begin() + ds );
103  unset_padding_();
104  }
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  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
123  }
124 
128  inline bool get (size_t index) const
129  {
130  if (index >= size_) {
131  return false;
132  }
133  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
134  }
135 
139  inline void set (size_t index)
140  {
141  if (index >= size_) {
142  return;
143  }
144  data_[index / IntSize] |= bit_mask_[index % IntSize];
145  }
146 
150  inline void unset (size_t index)
151  {
152  if (index >= size_) {
153  return;
154  }
155  data_[index / IntSize] &= ~(bit_mask_[index % IntSize]);
156  }
157 
161  inline void set (size_t index, bool value)
162  {
163  if (value) {
164  set(index);
165  } else {
166  unset(index);
167  }
168  }
169 
173  inline void flip (size_t index)
174  {
175  if (index >= size_) {
176  return;
177  }
178  data_[index / IntSize] ^= bit_mask_[index % IntSize];
179  }
180 
181  // ---------------------------------------------------------
182  // Operators
183  // ---------------------------------------------------------
184 
185  Bitvector& operator &= (Bitvector const& rhs);
186  Bitvector& operator |= (Bitvector const& rhs);
187  Bitvector& operator ^= (Bitvector const& rhs);
188  Bitvector operator ~ () const;
189 
190  bool operator == (const Bitvector &other) const;
191  bool operator != (const Bitvector &other) const;
192 
193  // ---------------------------------------------------------
194  // Other Functions
195  // ---------------------------------------------------------
196 
200  inline size_t size() const
201  {
202  return size_;
203  }
204 
208  size_t count() const;
209 
213  size_t hash() const;
214 
222  IntType x_hash() const;
223 
227  void negate();
228 
235  void normalize();
236 
240  void set_all(const bool value = false);
241 
242  std::string dump() const;
243  std::string dump_int(IntType x) const;
244 
245  // ---------------------------------------------------------
246  // Internal Members
247  // ---------------------------------------------------------
248 
249 private:
250 
258  void unset_padding_();
259 
260  static const IntType all_0_;
261  static const IntType all_1_;
262 
263  static const IntType bit_mask_[IntSize];
264  static const IntType ones_mask_[IntSize];
265 
266  static const IntType count_mask_[4];
267 
268  // ---------------------------------------------------------
269  // Data Members
270  // ---------------------------------------------------------
271 
272  size_t size_ = 0;
273  std::vector<IntType> data_;
274 };
275 
276 } // namespace utils
277 } // namespace genesis
278 
279 // =============================================================================
280 // Namespace std extension
281 // =============================================================================
282 
283 /*
284 namespace std {
285 
286 template<>
287 struct hash<genesis::utils::Bitvector>
288 {
289  size_t operator() (genesis::utils::Bitvector const &rhs) const
290  {
291  return rhs.hash();
292  }
293 };
294 
295 } // namespace std
296 */
297 
298 #endif // include guard
size_t size() const
Return the size (number of bits) of this Bitvector.
Definition: bitvector.hpp:200
void unset(size_t index)
Set the value of a single bit to false, with boundary check.
Definition: bitvector.hpp:150
Bitvector & operator^=(Bitvector const &rhs)
Definition: bitvector.cpp:133
size_t count() const
Count the number of set bits in the Bitvector, that is, its Hamming weight.
Definition: bitvector.cpp:174
IntType x_hash() const
Return a hash value of type IntType that is quicker to calculate than hash().
Definition: bitvector.cpp:215
Bitvector(Bitvector const &other, size_t bits)
Create a Bitvector by copying the first bits of another Bitvector.
Definition: bitvector.hpp:94
size_t hash() const
Return an std::hash value for the Bitvector.
Definition: bitvector.cpp:203
void set(size_t index)
Set the value of a single bit to true, with boundary check.
Definition: bitvector.hpp:139
static const size_t IntSize
Definition: bitvector.hpp:55
Bitvector()=default
Default constructor. Creates an empty Bitvector of size 0.
bool operator==(const Bitvector &other) const
Definition: bitvector.cpp:152
Bitvector(const size_t size, const std::initializer_list< int > list)
Constructor that takes a size and a list of values (positions) to be set to true. ...
Definition: bitvector.hpp:81
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:161
void negate()
Flip all bits.
Definition: bitvector.cpp:224
Bitvector & operator&=(Bitvector const &rhs)
Definition: bitvector.cpp:109
void flip(size_t index)
Flip (negate) the value of a single bit, with boundary check.
Definition: bitvector.hpp:173
bool operator!=(const Bitvector &other) const
Definition: bitvector.cpp:165
bool operator[](size_t index) const
Return the value of a single bit, without boundary check.
Definition: bitvector.hpp:121
void normalize()
Bring the Bitvector in a normalized form, where the first bit is always zero.
Definition: bitvector.cpp:235
Bitvector & operator|=(Bitvector const &rhs)
Definition: bitvector.cpp:121
Bitvector operator~() const
Definition: bitvector.cpp:145
std::string dump_int(IntType x) const
Definition: bitvector.cpp:292
Bitvector & operator=(Bitvector const &)=default
void set_all(const bool value=false)
Set all the bits to a specified value.
Definition: bitvector.cpp:242
Bitvector(const size_t size, const bool initial_value=false)
Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default.
Definition: bitvector.hpp:70
std::string dump() const
Definition: bitvector.cpp:278