NCBI C++ ToolKit
ct_bitset_cxx17.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef __CT_BITSET_CXX17_HPP_INCLUDED__
2 #define __CT_BITSET_CXX17_HPP_INCLUDED__
3 
4 /* $Id: ct_bitset_cxx17.hpp 98815 2023-01-10 13:42:44Z gotvyans $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Sergiy Gotvyanskyy
30  *
31  * File Description:
32  * partially backported std::bitset using c++17 constexpr
33  *
34  *
35  */
36 
37 
38 namespace compile_time_bits
39 {
40  template<typename _Ty, typename u_type = uint64_t> //typename real_underlying_type<_Ty>::type >
41  class range: private std::pair<u_type, u_type>
42  {
43  public:
44  using _MyBase = std::pair<u_type, u_type>;
46  {
47  public:
48  friend class range;
49  constexpr const_iterator() = default;
50 
51  constexpr _Ty operator*() noexcept { return static_cast<_Ty>(m_value); }
52  constexpr _Ty operator->() noexcept { return static_cast<_Ty>(m_value); }
53 
54  constexpr bool operator==(const const_iterator& o) const
55  {
56  return m_value == o.m_value;
57  }
58  constexpr bool operator!=(const const_iterator& o) const
59  {
60  return m_value != o.m_value;
61  }
63  {
64  ++m_value;
65  return *this;
66  }
67  constexpr const_iterator operator++(int)
68  {
69  const_iterator _this(*this);
70  operator++();
71  return _this;
72  }
73  private:
74  constexpr const_iterator(u_type v) : m_value{v} {}
75 
76  private:
77  u_type m_value{};
78  };
79 
80  constexpr range() = default;
81  constexpr range(_Ty _first, _Ty _last) : _MyBase{static_cast<u_type>(_first), static_cast<u_type>(_last)}
82  {
83 
84  }
85 
87 
88  constexpr const_iterator cbegin() const noexcept { return const_iterator(_MyBase::first); }
89  constexpr const_iterator cend() const noexcept { return const_iterator(_MyBase::second + 1); }
90  constexpr const_iterator begin() const noexcept { return cbegin(); }
91  constexpr const_iterator end() const noexcept { return cend(); }
92  };
93 
94  // template deduction rules by constructor
95  template<typename _Ty>
96  range(_Ty, _Ty) -> range<_Ty>;
97 
98  // this helper packs set of bits into an array usefull for initialisation of bitset
99  // using C++17
100 
101  template<class _Ty, size_t _Size, class u_type>
102  struct bitset_traits
103  {
105 
106  static constexpr size_t width = 8 * sizeof(_Ty);
107  static constexpr size_t max_width = 8 * sizeof(_Ty) * _Size;
108 
109  static constexpr bool IsYes(char c) { return c == '1'; }
110  static constexpr bool IsYes(bool c) { return c; }
111 
112  template<typename _Other>
113  static constexpr void ct_set(array_t& arr, _Other _v)
114  { // compile time version of set, doesn't throw an exception
115  size_t _Pos = static_cast<size_t>(_v);
116  if (_Pos < max_width) {
117  // _Pos off end
118  auto& val = arr[_Pos / width];
119  _Ty mask = _Ty(1) << (_Pos % width);
120  val |= mask;
121  }
122  }
123 
124  template<typename _Other>
125  static constexpr array_t set_bits(std::initializer_list<_Other> args)
126  {
127  array_t arr{};
128  for (auto value: args) {
129  ct_set(arr, value);
130  }
131  return arr;
132  }
133 
134  template<typename _Iterator>
135  static constexpr array_t set_bits(_Iterator begin, _Iterator end)
136  {
137  array_t arr{};
138  for (auto it = begin; it != end; ++it) {
139  if (IsYes(*it)) {
140  auto offset = std::distance(begin, it);
141  ct_set(arr, offset);
142  }
143  }
144  return arr;
145  }
146 
147  template<size_t N>
148  static constexpr array_t set_bits(const const_array<char, N>& in)
149  {
150  return set_bits(in.begin(), in.end());
151  }
152 
153  template<size_t N>
154  static constexpr array_t set_bits(const const_array<bool, N>& in)
155  {
156  return set_bits(in.begin(), in.end());
157  }
158 
159  template<typename T>
160  static constexpr array_t set_range(T from, T to)
161  {
162  array_t arr{};
163 
164  for (auto it: range(from, to))
165  {
166  ct_set(arr, it);
167  }
168  return arr;
169  }
170 
171  };
172 
173  // C++20 has constexpr std::popcount
174  // See Hamming Weight: https://en.wikipedia.org/wiki/Hamming_weight
175  constexpr int popcount64c(uint64_t x)
176  {
177  //This uses fewer arithmetic operations than any other known
178  //implementation on machines with fast multiplication.
179  //This algorithm uses 12 arithmetic operations, one of which is a multiply.
180 
181  //types and constants used in the functions below
182  //uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
183  constexpr uint64_t m1 = 0x5555555555555555; //binary: 0101...
184  constexpr uint64_t m2 = 0x3333333333333333; //binary: 00110011..
185  constexpr uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
186  //constexpr uint64_t m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
187  //constexpr uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
188  //constexpr uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
189  constexpr uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
190 
191  x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
192  x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
193  x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
194  return int((x * h01) >> 56); //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
195  }
196 
197  constexpr int popcount64d(uint64_t x)
198  {
199  int retval = 0;
200  while (x) {
201  x &= x - 1;
202  ++retval;
203  }
204  return retval;
205  }
206 
207  constexpr size_t find_first_bit(uint64_t x)
208  { // returns 64 for all zeros 'x'
209  //if (current == 0) return 0;
210 
211  // for any number in the form bXXXX100000
212  // only_low_bits will look like b0000111111
213  // so, counting those one's would give a product
214  auto only_low_bits = x ^ (x - 1);
215  auto count = popcount64c(only_low_bits);
216  return count;
217  }
218 
219 }
220 
221 namespace compile_time_bits
222 {
223  // partially backported std::bitset until it's constexpr version becomes available
224  template<size_t _Bits, class T>
225  class const_bitset
226  {
227  public:
229 
230  using _Ty = uint64_t;
231 
232  static constexpr size_t _Bitsperword = 8 * sizeof(_Ty);
233  static constexpr size_t _Words = (_Bits + _Bitsperword - 1) / _Bitsperword;
236 
237  constexpr const_bitset() = default;
238 
239  constexpr const_bitset(std::initializer_list<T> _init)
240  :const_bitset(traits::set_bits(_init))
241  {}
242 
243  constexpr const_bitset(T _init)
244  :const_bitset(traits::set_bits({_init}))
245  {}
246 
247  template<size_t N>
248  explicit constexpr const_bitset(char const (&_init)[N])
249  :const_bitset(make_array(_init))
250  {}
251 
252  template<size_t N>
253  explicit constexpr const_bitset(const const_array<char, N> &_init)
254  :const_bitset(traits::set_bits(_init))
255  {}
256 
257  struct range: std::pair<T, T>
258  {
259  using std::pair<T, T>::pair;
260  };
261 
262  explicit constexpr const_bitset(const range& _range)
263  :const_bitset(traits::set_range(_range.first, _range.second))
264  {}
265 
266  static constexpr const_bitset set_range(T _from, T _to)
267  {
268  return const_bitset(range{ _from, _to });
269  }
270 
271  static constexpr size_t capacity() { return _Bits; }
272  constexpr size_t size() const
273  {
274  size_t retval{0};
275  for (auto value: _Array)
276  {
277  retval += popcount64c(value);
278  }
279  return retval;
280  }
281  constexpr bool empty() const
282  {
283  for (auto value: _Array)
284  {
285  if (value != 0)
286  return false;
287  }
288  return true;
289  }
290 
291  constexpr bool test(T _Pos) const
292  {
293  return _Subscript(static_cast<size_t>(_Pos));
294  }
295 
297  {
298  set(value);
299  return *this;
300  }
301 
303  {
304  reset(value);
305  return *this;
306  }
307 
309  {
310  for (size_t i=0; i<_Array.size(); i++)
311  _Array[i] |= _Other._Array[i];
312  return *this;
313  }
314 
316  {
317  for (size_t i=0; i<_Array.size(); i++)
318  _Array[i] &= (~_Other._Array[i]);
319  return *this;
320  }
321 
322  bool reset(T _v)
323  {
324  size_t _Pos = static_cast<size_t>(_v);
325  if (_Bits <= _Pos)
326  _Xran(); // _Pos off end
327  auto& val = _Array[_Pos / _Bitsperword];
328  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
329  bool previous = (val & mask) != 0;
330  if (previous) {
331  val ^= mask;
332  }
333  return previous;
334  }
335  bool set(T _v)
336  {
337  size_t _Pos = static_cast<size_t>(_v);
338  if (_Bits <= _Pos)
339  _Xran(); // _Pos off end
340  auto& val = _Array[_Pos / _Bitsperword];
341  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
342  bool previous = (val & mask) != 0;
343  if (!previous) {
344  val |= mask;
345  }
346  return previous;
347  }
348 
349  constexpr bool ct_set(T _v)
350  { // compile time version of set, doesn't throw an exception
351  size_t _Pos = static_cast<size_t>(_v);
352  if (_Bits <= _Pos)
353  return false; // _Pos off end
354  auto& val = _Array[_Pos / _Bitsperword];
355  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
356  bool previous = (val & mask) != 0;
357  if (!previous) {
358  val |= mask;
359  }
360  return previous;
361  }
362 
363  constexpr bool ct_test(T _Pos) const
364  {
365  return _Subscript(static_cast<size_t>(_Pos));
366  }
367 
368  class const_iterator
369  {
370  public:
371  using difference_type = size_t;
372  using value_type = T;
373  using pointer = const T*;
374  using reference = const T&;
375  using iterator_category = std::forward_iterator_tag;
376 
377  constexpr const_iterator() = default;
378  friend class const_bitset;
379 
380  constexpr bool operator==(const const_iterator& o) const
381  {
382  return m_bitset == o.m_bitset && m_index == o.m_index;
383  }
384  constexpr bool operator!=(const const_iterator& o) const
385  {
386  return m_bitset != o.m_bitset || m_index != o.m_index;
387  }
389  {
390  if (m_index < _Bits) {
391  x_find_next_bit();
392  }
393  return *this;
394  }
395  constexpr const_iterator operator++(int)
396  {
397  const_iterator _this(*this);
398  operator++();
399  return _this;
400  }
401  constexpr T operator*() const
402  {
403  return static_cast<T>(m_index);
404  }
405  constexpr T operator->() const
406  {
407  return static_cast<T>(m_index);
408  }
409 
410  private:
411  constexpr void x_find_next_bit()
412  {
413  // See Hamming Weight: https://en.wikipedia.org/wiki/Hamming_weight
414 
415  _Ty current = m_current;
416 
417  if (current & _Ty(1)) {
418  m_current = current >> 1;
419  m_index++;
420  return;
421  }
422 
423  size_t index = m_index;
424  if constexpr (_Words > 1) {
425  if (current == 0) {
426  size_t offset = (index / _Bitsperword) + 1;
427  while (offset<_Words && (current = m_bitset->_Array[offset]) == 0)
428  ++offset;
429 
430  index = offset*_Bitsperword - 1;
431  }
432  }
433  if (current == 0) {
434  m_index = _Bits;
435  return;
436  }
437 
438  auto delta = find_first_bit(current);
439  m_index = index + delta;
440  // shift overflow is not well supported by all CPUs
441  current = delta == _Bitsperword ? 0 : current >> delta;
442  m_current = current;
443  }
444 
445  // begin operator
446  constexpr const_iterator(const const_bitset* _this, std::true_type) : m_bitset{ _this }
447  {
448  _Ty current = _this->_Array[0];
449  m_current = current >> 1;
450 
451  if (current & _Ty(1)) {
452  } else {
453  x_find_next_bit();
454  }
455  }
456 
457  // end operator
458  constexpr const_iterator(const const_bitset* _this, std::false_type) : m_index{ _Bits }, m_bitset{ _this }
459  {}
460 
461  size_t m_index{0};
462  const const_bitset* m_bitset{nullptr};
464  };
465 
466  using iterator = const_iterator;
467 
468  constexpr const_iterator cbegin() const noexcept { return const_iterator(this, std::true_type{}); }
469  constexpr const_iterator cend() const noexcept { return const_iterator(this, std::false_type{}); }
470  constexpr const_iterator begin() const noexcept { return cbegin(); }
471  constexpr const_iterator end() const noexcept { return cend(); }
472 
473  template<class _Ty, class _Alloc>
474  operator std::vector<_Ty, _Alloc>() const
475  {
476  std::vector<_Ty, _Alloc> vec;
477  vec.reserve(size());
478  vec.assign(begin(), end());
479  return vec;
480  }
481 
482  private:
483  explicit constexpr const_bitset(const _Array_t& args) : _Array(args) {}
484 
485  _Array_t _Array{}; // the set of bits
486 
487  constexpr bool x_test(size_t _Pos) const
488  {
489  return _Pos<_Bits ? _Subscript(_Pos) : false;
490  }
491 
492  constexpr bool _Subscript(size_t _Pos) const
493  { // subscript nonmutable sequence
494  return ((_Array[_Pos / _Bitsperword]
495  & ((_Ty)1 << _Pos % _Bitsperword)) != 0);
496  }
497  [[noreturn]] void _Xran() const
498  {
499  throw std::out_of_range("invalid const_bitset<_Bits, T> position");
500  }
501 
502  };
503 }
504 
505 
506 #endif
ncbi::TMaskedQueryRegions mask
constexpr const_iterator(const const_bitset *_this, std::false_type)
constexpr bool operator!=(const const_iterator &o) const
constexpr bool operator==(const const_iterator &o) const
constexpr const_iterator(const const_bitset *_this, std::true_type)
constexpr const_iterator cend() const noexcept
constexpr const_bitset(char const (&_init)[N])
constexpr const_iterator end() const noexcept
constexpr const_iterator begin() const noexcept
static constexpr size_t _Bitsperword
constexpr const_bitset()=default
static constexpr size_t capacity()
constexpr bool test(T _Pos) const
constexpr const_iterator cbegin() const noexcept
constexpr const_iterator begin() const
static constexpr const_bitset set_range(T _from, T _to)
constexpr bool x_test(size_t _Pos) const
constexpr size_t size() const
constexpr bool _Subscript(size_t _Pos) const
static constexpr size_t _Words
constexpr const_iterator cend() const
const_bitset & operator-=(T value)
constexpr const_iterator end() const
constexpr const_bitset(const _Array_t &args)
const_array< _Ty, _Words > _Array_t
constexpr const_iterator cbegin() const
constexpr const_bitset(std::initializer_list< T > _init)
const_bitset & operator+=(T value)
constexpr const_bitset(const range &_range)
constexpr const_bitset(const const_array< char, N > &_init)
constexpr bool ct_test(T _Pos) const
constexpr bool operator!=(const const_iterator &o) const
constexpr const_iterator operator++(int)
constexpr const_iterator & operator++()
constexpr bool operator==(const const_iterator &o) const
constexpr range()=default
constexpr const_iterator begin() const noexcept
constexpr const_iterator end() const noexcept
constexpr const_iterator cend() const noexcept
constexpr const_iterator cbegin() const noexcept
constexpr range(_Ty _first, _Ty _last)
std::pair< u_type, u_type > _MyBase
#define T(s)
Definition: common.h:230
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
int offset
Definition: replacements.h:160
Uint8 uint64_t
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
int i
constexpr int popcount64c(uint64_t x)
range(_Ty, _Ty) -> range< _Ty >
constexpr size_t find_first_bit(uint64_t x)
constexpr auto make_array(T &&a)
constexpr int popcount64d(uint64_t x)
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1227
std::istream & in(std::istream &in_, double &x_)
Int4 delta(size_t dimension_, const Int4 *score_)
#define uint64_t
Definition: config.h:48
static constexpr bool IsYes(bool c)
static constexpr array_t set_bits(const const_array< char, N > &in)
static constexpr array_t set_bits(std::initializer_list< _Other > args)
static constexpr void ct_set(array_t &arr, _Other _v)
static constexpr bool IsYes(char c)
static constexpr array_t set_bits(const const_array< bool, N > &in)
static constexpr size_t width
static constexpr array_t set_range(T from, T to)
static constexpr size_t max_width
static constexpr array_t set_bits(_Iterator begin, _Iterator end)
static constexpr size_t size() noexcept
#define const
Definition: zconf.h:232
#define N
Definition: crc32.c:57
Modified on Tue May 21 11:00:41 2024 by modify_doxy.py rev. 669887