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

Go to the SVN repository for this file.

1 #ifndef __CT_BITSET_CXX14_HPP_INCLUDED__
2 #define __CT_BITSET_CXX14_HPP_INCLUDED__
3 
4 /* $Id: ct_bitset_cxx14.hpp 98668 2022-12-19 14:25:48Z 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++14 constexpr
33  *
34  *
35  */
36 
37 namespace compile_time_bits
38 {
39  // this helper packs set of bits into an array usefull for initialisation of bitset
40  // using C++14
41 
42  template<class _Ty, size_t _Size, class u_type>
44  {
46 
47  static constexpr size_t width = 8 * sizeof(_Ty);
48 
49  struct range_t
50  {
51  size_t m_from;
52  size_t m_to;
53  };
54 
55  static constexpr bool check_range(const range_t& range, size_t i)
56  {
57  return (range.m_from <= i && i <= range.m_to);
58  };
59 
60  template <size_t I>
61  static constexpr _Ty assemble_mask(const range_t& _init)
62  {
63  constexpr auto _min = I * width;
64  constexpr auto _max = I * width + width - 1;
65  if (check_range(_init, _min) && check_range(_init, _max))
67 
68  _Ty ret = 0;
69  for (size_t j = 0; j < width; ++j)
70  {
71  bool is_set = check_range(_init, j + _min);
72  if (is_set)
73  ret |= (_Ty(1) << j);
74  }
75  return ret;
76  }
77  template <size_t I, typename _Other>
78  static constexpr _Ty assemble_mask(const std::initializer_list<_Other>& _init)
79  {
80  _Ty ret = 0;
81  constexpr auto _min = I * width;
82  constexpr auto _max = I * width + width - 1;
83  for (_Other _rec : _init)
84  {
85  size_t rec = static_cast<size_t>(static_cast<u_type>(_rec));
86  if (_min <= rec && rec <= _max)
87  {
88  ret |= _Ty(1) << (rec % width);
89  }
90  }
91  return ret;
92  }
93 
94  static constexpr bool IsYes(char c) { return c == '1'; }
95  static constexpr bool IsYes(bool c) { return c; }
96 
97  template <size_t I, size_t N, typename _Base>
98  static constexpr _Ty assemble_mask(const const_array<_Base, N>& _init)
99  {
100  _Ty ret = 0;
101  _Ty mask = 1;
102  constexpr auto _min = I * width;
103  constexpr auto _max = I * width + width;
104  for (size_t pos = _min; pos < _max && pos < N; ++pos)
105  {
106  if (IsYes(_init[pos])) ret |= mask;
107  mask = mask << 1;
108  }
109  return ret;
110  }
111  template <typename _Input, std::size_t... I>
112  static constexpr array_t assemble_bitset(const _Input& _init, std::index_sequence<I...>)
113  {
114  return {assemble_mask<I>(_init)...};
115  }
116 
117  template<typename _Other>
118  static constexpr array_t set_bits(std::initializer_list<_Other> args)
119  {
120  return assemble_bitset(args, std::make_index_sequence<_Size>{});
121  }
122  template<typename T>
123  static constexpr array_t set_range(T from, T to)
124  {
125  return assemble_bitset(range_t{ static_cast<size_t>(from), static_cast<size_t>(to) }, std::make_index_sequence<_Size>{});
126  }
127  template<size_t N>
128  static constexpr array_t set_bits(const const_array<char, N>& in)
129  {
130  return assemble_bitset(in, std::make_index_sequence<_Size>{});
131  }
132  template<size_t N>
133  static constexpr array_t set_bits(const const_array<bool, N>& in)
134  {
135  return assemble_bitset(in, std::make_index_sequence<_Size>{});
136  }
137  };
138 
139  // partially backported std::bitset until it's constexpr version becomes available
140  template<size_t _Bits, class T>
142  {
143  public:
145 
146  using _Ty = uint64_t;
147 
148  static constexpr size_t _Bitsperword = 8 * sizeof(_Ty);
149  static constexpr size_t _Words = (_Bits + _Bitsperword - 1) / _Bitsperword;
152 
153  constexpr const_bitset() = default;
154 
155  constexpr const_bitset(std::initializer_list<T> _init)
156  :const_bitset(traits::set_bits(_init))
157  {}
158 
159  constexpr const_bitset(T _init)
160  :const_bitset(traits::set_bits({_init}))
161  {}
162 
163  template<size_t N>
164  explicit constexpr const_bitset(char const (&_init)[N])
165  :const_bitset(make_array(_init))
166  {}
167 
168  template<size_t N>
169  explicit constexpr const_bitset(const const_array<char, N> &_init)
170  :const_bitset(traits::set_bits(_init))
171  {}
172 
173  struct range: std::pair<T, T>
174  {
175  using std::pair<T, T>::pair;
176  };
177 
178  explicit constexpr const_bitset(const range& _range)
179  :const_bitset(traits::set_range(_range.first, _range.second))
180  {}
181 
182  static constexpr const_bitset set_range(T _from, T _to)
183  {
184  return const_bitset(range{ _from, _to });
185  }
186 
187  static constexpr size_t capacity() { return _Bits; }
188  constexpr size_t size() const
189  { // See Hamming Weight: https://en.wikipedia.org/wiki/Hamming_weight
190  size_t retval{0};
191  for (auto value: _Array)
192  {
193  while (value) {
194  value &= value - 1;
195  ++retval;
196  }
197  }
198  return retval;
199  }
200  constexpr bool empty() const
201  {
202  for (auto value: _Array)
203  {
204  if (value != 0)
205  return false;
206  }
207  return true;
208  }
209 
210  constexpr bool test(T _Pos) const
211  {
212  return _Subscript(static_cast<size_t>(_Pos));
213  }
214 
216  {
217  set(value);
218  return *this;
219  }
220 
222  {
223  reset(value);
224  return *this;
225  }
226 
228  {
229  for (size_t i=0; i<_Array.size(); i++)
230  _Array[i] |= _Other._Array[i];
231  return *this;
232  }
233 
235  {
236  for (size_t i=0; i<_Array.size(); i++)
237  _Array[i] &= (~_Other._Array[i]);
238  return *this;
239  }
240 
241  bool reset(T _v)
242  {
243  size_t _Pos = static_cast<size_t>(_v);
244  if (_Bits <= _Pos)
245  _Xran(); // _Pos off end
246  auto& val = _Array[_Pos / _Bitsperword];
247  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
248  bool previous = (val & mask) != 0;
249  if (previous) {
250  val ^= mask;
251  }
252  return previous;
253  }
254  bool set(T _v)
255  {
256  size_t _Pos = static_cast<size_t>(_v);
257  if (_Bits <= _Pos)
258  _Xran(); // _Pos off end
259  auto& val = _Array[_Pos / _Bitsperword];
260  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
261  bool previous = (val & mask) != 0;
262  if (!previous) {
263  val |= mask;
264  }
265  return previous;
266  }
267 
268  constexpr bool ct_set(T _v)
269  { // compile time version of set, doesn't throw an exception
270  size_t _Pos = static_cast<size_t>(_v);
271  if (_Bits <= _Pos)
272  return false; // _Pos off end
273  auto& val = _Array[_Pos / _Bitsperword];
274  _Ty mask = (_Ty)1 << _Pos % _Bitsperword;
275  bool previous = (val & mask) != 0;
276  if (!previous) {
277  val |= mask;
278  }
279  return previous;
280  }
281 
283  {
284  public:
285  using difference_type = size_t;
286  using value_type = T;
287  using pointer = const T*;
288  using reference = const T&;
289  using iterator_category = std::forward_iterator_tag;
290 
291  constexpr const_iterator() = default;
292  friend class const_bitset;
293 
294  constexpr bool operator==(const const_iterator& o) const
295  {
296  return m_bitset == o.m_bitset && m_index == o.m_index;
297  }
298  constexpr bool operator!=(const const_iterator& o) const
299  {
300  return m_bitset != o.m_bitset || m_index != o.m_index;
301  }
303  {
304  while (m_index < m_bitset->capacity())
305  {
306  ++m_index;
308  break;
309  }
310  return *this;
311  }
312  constexpr const_iterator operator++(int)
313  {
314  const_iterator _this(*this);
315  operator++();
316  return _this;
317  }
318  constexpr T operator*() const
319  {
320  return static_cast<T>(m_index);
321  }
322  constexpr T operator->() const
323  {
324  return static_cast<T>(m_index);
325  }
326 
327  private:
328  constexpr const_iterator(const const_bitset* _this, size_t index) : m_index{ index }, m_bitset{ _this }
329  {
330  while (m_index < m_bitset->capacity() && !m_bitset->x_test(m_index))
331  {
332  ++m_index;
333  }
334  }
335  size_t m_index{0};
336  const const_bitset* m_bitset{nullptr};
337  };
338 
339  using iterator = const_iterator;
340 
341  constexpr const_iterator begin() const { return const_iterator(this, 0); }
342  constexpr const_iterator end() const { return const_iterator(this, capacity()); }
343  constexpr const_iterator cbegin() const { return const_iterator(this, 0); }
344  constexpr const_iterator cend() const { return const_iterator(this, capacity()); }
345 
346  template<class _Ty, class _Alloc>
347  operator std::vector<_Ty, _Alloc>() const
348  {
349  std::vector<_Ty, _Alloc> vec;
350  vec.reserve(size());
351  vec.assign(begin(), end());
352  return vec;
353  }
354 
355  private:
356  explicit constexpr const_bitset(const _Array_t& args) : _Array(args) {}
357 
358  _Array_t _Array{}; // the set of bits
359 
360  constexpr bool x_test(size_t _Pos) const
361  {
362  return _Subscript(_Pos);
363  }
364 
365  constexpr bool _Subscript(size_t _Pos) const
366  { // subscript nonmutable sequence
367  return ((_Array[_Pos / _Bitsperword]
368  & ((_Ty)1 << _Pos % _Bitsperword)) != 0);
369  }
370  [[noreturn]] void _Xran() const
371  {
372  throw std::out_of_range("invalid const_bitset<_Bits, T> position");
373  }
374 
375  };
376 }
377 
378 
379 #endif
ncbi::TMaskedQueryRegions mask
constexpr const_iterator(const const_bitset *_this, size_t index)
constexpr bool operator!=(const const_iterator &o) const
constexpr bool operator==(const const_iterator &o) const
constexpr const_bitset(char const (&_init)[N])
static constexpr size_t _Bitsperword
constexpr const_bitset()=default
static constexpr size_t capacity()
constexpr bool test(T _Pos) const
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)
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)
#define T(s)
Definition: common.h:230
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
int i
constexpr auto make_array(T &&a)
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1227
T max(T x_, T y_)
std::istream & in(std::istream &in_, double &x_)
#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 array_t assemble_bitset(const _Input &_init, std::index_sequence< I... >)
static constexpr _Ty assemble_mask(const std::initializer_list< _Other > &_init)
static constexpr bool IsYes(char c)
static constexpr bool check_range(const range_t &range, size_t i)
static constexpr array_t set_bits(const const_array< bool, N > &in)
static constexpr size_t width
static constexpr _Ty assemble_mask(const const_array< _Base, N > &_init)
static constexpr array_t set_range(T from, T to)
static constexpr _Ty assemble_mask(const range_t &_init)
static constexpr size_t size() noexcept
#define N
Definition: crc32.c:57
Modified on Thu Apr 11 15:10:47 2024 by modify_doxy.py rev. 669887