A toolkit for working with phylogenetic data.
v0.18.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-2017 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 <iostream>
35 #include <stdint.h>
36 #include <string>
37 #include <vector>
38 
39 namespace genesis {
40 namespace utils {
41 
42 // =================================================================================================
43 // Forward Declarations
44 // =================================================================================================
45 
46 class Bitvector;
47 
48 Bitvector operator & (Bitvector const& lhs, Bitvector const& rhs);
49 Bitvector operator | (Bitvector const& lhs, Bitvector const& rhs);
50 Bitvector operator ^ (Bitvector const& lhs, Bitvector const& rhs);
51 Bitvector operator - (Bitvector const& lhs, Bitvector const& rhs);
52 std::ostream& operator << (std::ostream& out, Bitvector const& rhs);
53 
54 // =================================================================================================
55 // Bitvector
56 // =================================================================================================
57 
58 class Bitvector
59 {
60 public:
61 
62  // ---------------------------------------------------------
63  // Declarations and Class Functions
64  // ---------------------------------------------------------
65 
66  typedef uint64_t IntType;
67  static const size_t IntSize = sizeof(IntType) * 8;
68 
69  friend Bitvector operator & (Bitvector const& lhs, Bitvector const& rhs);
70  friend Bitvector operator | (Bitvector const& lhs, Bitvector const& rhs);
71  friend Bitvector operator ^ (Bitvector const& lhs, Bitvector const& rhs);
72  friend Bitvector operator - (Bitvector const& lhs, Bitvector const& rhs);
73 
74  friend std::ostream& operator << (std::ostream& out, Bitvector const& rhs);
75 
79  Bitvector() = default;
80 
85  Bitvector (const size_t size, const bool init = false) : size_(size)
86  {
87  // reserve enough bits, and init them.
88  data_.resize( (size / IntSize) + (size % IntSize == 0 ? 0 : 1) );
89  reset(init);
90  }
91 
95  Bitvector (const size_t size, const std::initializer_list<int> list) : Bitvector(size, false)
96  {
97  for (int e : list) {
98  set(e);
99  }
100  }
101 
105  inline size_t size() const
106  {
107  return size_;
108  }
109 
110  // ---------------------------------------------------------
111  // Single Bit Functions
112  // ---------------------------------------------------------
113 
117  inline bool operator [] (size_t index) const {
118  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
119  }
120 
124  inline bool get (size_t index) const
125  {
126  if (index >= size_) {
127  return false;
128  }
129  return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
130  }
131 
135  inline void set (size_t index)
136  {
137  if (index >= size_) {
138  return;
139  }
140  data_[index / IntSize] |= bit_mask_[index % IntSize];
141  }
142 
146  inline void unset (size_t index)
147  {
148  if (index >= size_) {
149  return;
150  }
151  data_[index / IntSize] &= ~(bit_mask_[index % IntSize]);
152  }
153 
157  inline void set (size_t index, bool value)
158  {
159  if (value) {
160  set(index);
161  } else {
162  unset(index);
163  }
164  }
165 
169  inline void flip (size_t index)
170  {
171  if (index >= size_) {
172  return;
173  }
174  data_[index / IntSize] ^= bit_mask_[index % IntSize];
175  }
176 
177  // ---------------------------------------------------------
178  // Operators
179  // ---------------------------------------------------------
180 
181  Bitvector& operator &= (Bitvector const& rhs);
182  Bitvector& operator |= (Bitvector const& rhs);
183  Bitvector& operator ^= (Bitvector const& rhs);
184  Bitvector operator ~ () const;
185 
186  bool operator == (const Bitvector &other) const;
187  bool operator != (const Bitvector &other) const
188  {
189  return !(*this == other);
190  }
191 
195  inline bool operator < (Bitvector const& rhs) const
196  {
197  return ((*this & rhs) == *this) && (count() < rhs.count());
198  }
199 
203  inline bool operator > (Bitvector const& rhs) const
204  {
205  return rhs < *this;
206  }
207 
211  inline bool operator <= (Bitvector const& rhs) const
212  {
213  return (*this == rhs) || (*this < rhs);
214  }
215 
219  inline bool operator >= (Bitvector const& rhs) const
220  {
221  return (*this == rhs) || (*this > rhs);
222  }
223 
224  // ---------------------------------------------------------
225  // Other Functions
226  // ---------------------------------------------------------
227 
228  Bitvector symmetric_difference ( Bitvector const& rhs) const;
229  static Bitvector symmetric_difference (Bitvector const& lhs, Bitvector const& rhs);
230 
231  size_t count() const;
232  size_t hash() const;
233  IntType x_hash() const;
234 
235  void invert();
236  void normalize();
237  void reset(const bool value = false);
238 
239  std::string dump() const;
240  std::string dump_int(IntType x) const;
241 
242  // ---------------------------------------------------------
243  // Internal Members
244  // ---------------------------------------------------------
245 
246 protected:
247 
248  void unset_padding();
249 
250  static const IntType all_0_;
251  static const IntType all_1_;
252 
253  static const IntType bit_mask_[IntSize];
254  static const IntType ones_mask_[IntSize];
255 
256  static const IntType count_mask_[4];
257 
258  // ---------------------------------------------------------
259  // Data Members
260  // ---------------------------------------------------------
261 
262  size_t size_ = 0;
263  std::vector<IntType> data_;
264 };
265 
266 } // namespace utils
267 } // namespace genesis
268 
269 // =============================================================================
270 // Namespace std extension
271 // =============================================================================
272 
273 /*
274 namespace std {
275 
276 template<>
277 struct hash<genesis::utils::Bitvector>
278 {
279  size_t operator() (genesis::utils::Bitvector const &rhs) const
280  {
281  return rhs.hash();
282  }
283 };
284 
285 } // namespace std
286 */
287 
288 #endif // include guard
static const IntType all_0_
Definition: bitvector.hpp:250
Bitvector symmetric_difference(Bitvector const &rhs) const
Definition: bitvector.cpp:213
size_t size() const
Returns the size (number of total bits) of this Bitvector.
Definition: bitvector.hpp:105
void unset(size_t index)
Sets the value of a single bit to false, with boundary check.
Definition: bitvector.hpp:146
Bitvector & operator^=(Bitvector const &rhs)
Definition: bitvector.cpp:179
Bitvector(const size_t size, const bool init=false)
Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default.
Definition: bitvector.hpp:85
size_t count() const
Counts the number of set bits in the Bitvector.
Definition: bitvector.cpp:226
static const IntType all_1_
Definition: bitvector.hpp:251
IntType x_hash() const
Returns a hash value of type IntType, that is quicker to calculate than hash(), and thus can be used ...
Definition: bitvector.cpp:274
friend Bitvector operator-(Bitvector const &lhs, Bitvector const &rhs)
Set-minus of two Bitvectors.
Definition: bitvector.cpp:151
bool operator<=(Bitvector const &rhs) const
Subset or equal.
Definition: bitvector.hpp:211
bool operator>=(Bitvector const &rhs) const
Superset or equal.
Definition: bitvector.hpp:219
static const IntType count_mask_[4]
Mask used for quickly counting the number of set bits, see count().
Definition: bitvector.hpp:256
bool operator&(SkipWhitespace lhs, SkipWhitespace rhs)
And-operator to check whether a SkipWhitespace is set.
Definition: scanner.hpp:95
Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:120
size_t hash() const
Returns an std::hash value for the Bitvector.
Definition: bitvector.cpp:258
void reset(const bool value=false)
Reset all the bits to false. If provided with parameter true, sets all bits to true.
Definition: bitvector.cpp:313
void set(size_t index)
Sets the value of a single bit to true, with boundary check.
Definition: bitvector.hpp:135
static const size_t IntSize
Definition: bitvector.hpp:67
Bitvector()=default
Default constructor. Creates an empty Bitvector of size 0.
Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:135
bool operator==(const Bitvector &other) const
Definition: bitvector.cpp:196
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:95
void set(size_t index, bool value)
Sets the value of a single bit to a given bool value, with boundary check.
Definition: bitvector.hpp:157
void invert()
Flip all bits.
Definition: bitvector.cpp:286
Bitvector & operator&=(Bitvector const &rhs)
Definition: bitvector.cpp:160
void flip(size_t index)
Flips (inverts) the value of a single bit, with boundary check.
Definition: bitvector.hpp:169
static const IntType bit_mask_[IntSize]
Contains a single bit at each of the 64 positions.
Definition: bitvector.hpp:253
bool operator!=(const Bitvector &other) const
Definition: bitvector.hpp:187
friend Bitvector operator^(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:135
bool operator[](size_t index) const
Returns the value of a single bit, without boundary check.
Definition: bitvector.hpp:117
static const IntType ones_mask_[IntSize]
Contains as many ones as the position in the array tells.
Definition: bitvector.hpp:254
void normalize()
Brings the Bitvector in a normalized form, where the first bit is always zero.
Definition: bitvector.cpp:303
friend std::ostream & operator<<(std::ostream &out, Bitvector const &rhs)
Definition: bitvector.cpp:354
std::vector< IntType > data_
Definition: bitvector.hpp:263
Bitvector & operator|=(Bitvector const &rhs)
Definition: bitvector.cpp:169
void unset_padding()
Internal function that sets all bits to zero that are not actively used.
Definition: bitvector.cpp:334
Bitvector operator~() const
Definition: bitvector.cpp:189
std::ostream & operator<<(std::ostream &os, NexusBlock const &block)
Definition: block.hpp:80
bool operator>(Bitvector const &rhs) const
Strict superset.
Definition: bitvector.hpp:203
std::string dump_int(IntType x) const
Definition: bitvector.cpp:376
bool operator<(Bitvector const &rhs) const
Strict subset.
Definition: bitvector.hpp:195
friend Bitvector operator&(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:105
Bitvector operator-(Bitvector const &lhs, Bitvector const &rhs)
Set-minus of two Bitvectors.
Definition: bitvector.cpp:151
std::string dump() const
Definition: bitvector.cpp:362
friend Bitvector operator|(Bitvector const &lhs, Bitvector const &rhs)
Definition: bitvector.cpp:120