dynamic_bitset 1.3.0
Simple Useful Libraries: C++17/20 header-only dynamic bitset
Loading...
Searching...
No Matches
dynamic_bitset.hpp
Go to the documentation of this file.
1//
2// Copyright (c) 2019 Maxime Pinard
3//
4// Distributed under the MIT license
5// See accompanying file LICENSE or copy at
6// https://opensource.org/licenses/MIT
7//
8#ifndef SUL_DYNAMIC_BITSET_HPP
9#define SUL_DYNAMIC_BITSET_HPP
10
16#define SUL_DYNAMIC_BITSET_VERSION_MAJOR 1
17
23#define SUL_DYNAMIC_BITSET_VERSION_MINOR 3
24
30#define SUL_DYNAMIC_BITSET_VERSION_PATCH 0
31
46#include <memory>
47#include <vector>
48#include <algorithm>
49#include <string>
50#include <string_view>
51#include <functional>
52#include <type_traits>
53#include <limits>
54#include <stdexcept>
55#include <cmath>
56#include <cassert>
57
58// define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT
59#if !defined(DYNAMIC_BITSET_NO_LIBPOPCNT)
60// https://github.com/kimwalisch/libpopcnt
61# if __has_include(<libpopcnt.h>)
62# include <libpopcnt.h>
63# define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT true
64# endif
65#endif
66#if !defined(DYNAMIC_BITSET_CAN_USE_LIBPOPCNT)
67# define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT false
68#endif
69
70// define DYNAMIC_BITSET_CAN_USE_STD_BITOPS
71#if !defined(DYNAMIC_BITSET_NO_STD_BITOPS)
72// https://en.cppreference.com/w/cpp/header/bit
73# if __has_include(<bit>)
74# include <bit>
75# ifdef __cpp_lib_bitops
76# define DYNAMIC_BITSET_CAN_USE_STD_BITOPS true
77# endif
78# endif
79#endif
80#if !defined(DYNAMIC_BITSET_CAN_USE_STD_BITOPS)
81# define DYNAMIC_BITSET_CAN_USE_STD_BITOPS false
82#endif
83
84// define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
85// define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ
86// define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN
87// define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD
88// define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64
89#if !DYNAMIC_BITSET_CAN_USE_STD_BITOPS && !defined(DYNAMIC_BITSET_NO_COMPILER_BUILTIN)
90# if defined(__clang__)
91// https://clang.llvm.org/docs/LanguageExtensions.html#feature-checking-macros
92// https://clang.llvm.org/docs/LanguageExtensions.html#intrinsics-support-within-constant-expressions
93# ifdef __has_builtin
94# if __has_builtin(__builtin_popcount) && __has_builtin(__builtin_popcountl) \
95 && __has_builtin(__builtin_popcountll)
96# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT true
97# endif
98# if __has_builtin(__builtin_ctz) && __has_builtin(__builtin_ctzl) \
99 && __has_builtin(__builtin_ctzll)
100# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ true
101# endif
102# endif
103# elif defined(__GNUC__) // also defined by clang
104// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
105# define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN true
106# elif defined(_MSC_VER)
107// https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64
108// __popcnt16, __popcnt, __popcnt64 not used because it require to check the hardware support at runtime
109// (https://docs.microsoft.com/fr-fr/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160#remarks)
110# if defined(_M_IX86) || defined(_M_ARM) || defined(_M_X64) || defined(_M_ARM64)
111# include <intrin.h>
112# pragma intrinsic(_BitScanForward)
113# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD true
114# endif
115# if(defined(_M_X64) || defined(_M_ARM64)) \
116 && !defined(DYNAMIC_BITSET_NO_MSVC_BUILTIN_BITSCANFORWARD64) // for testing purposes
117# pragma intrinsic(_BitScanForward64)
118# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64 true
119# endif
120# endif
121#endif
122#if !defined(DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT)
123# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT false
124#endif
125#if !defined(DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ)
126# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ false
127#endif
128#if !defined(DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN)
129# define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN false
130#endif
131#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD)
132# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD false
133#endif
134#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64)
135# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64 false
136#endif
137#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN)
138# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN false
139#endif
140
141#ifndef DYNAMIC_BITSET_NO_NAMESPACE
147namespace sul
148{
149#endif
150
170template<typename Block = unsigned long long, typename Allocator = std::allocator<Block>>
171class dynamic_bitset
172{
173 static_assert(std::is_unsigned<Block>::value, "Block is not an unsigned integral type");
174
175public:
181 typedef size_t size_type;
182
188 typedef Block block_type;
189
195 typedef Allocator allocator_type;
196
202 static constexpr size_type bits_per_block = std::numeric_limits<block_type>::digits;
203
209 static constexpr size_type npos = std::numeric_limits<size_type>::max();
210
221 class reference
222 {
223 public:
235 constexpr reference(dynamic_bitset<Block, Allocator>& bitset, size_type bit_pos);
236
242 constexpr reference(const reference&) noexcept = default;
243
249 constexpr reference(reference&&) noexcept = default;
250
256 ~reference() noexcept = default;
257
269 constexpr reference& operator=(bool v);
270
282 constexpr reference& operator=(const reference& rhs);
283
295 constexpr reference& operator=(reference&& rhs) noexcept;
296
309 constexpr reference& operator&=(bool v);
310
323 constexpr reference& operator|=(bool v);
324
337 constexpr reference& operator^=(bool v);
338
356 constexpr reference& operator-=(bool v);
357
367 [[nodiscard]] constexpr bool operator~() const;
368
376 [[nodiscard]] constexpr operator bool() const;
377
383 constexpr void operator&() = delete;
384
394 constexpr reference& set();
395
405 constexpr reference& reset();
406
416 constexpr reference& flip();
417
429 constexpr reference& assign(bool v);
430
431 private:
432 block_type& m_block;
433 block_type m_mask;
434 };
435
441 typedef bool const_reference;
442
448 constexpr dynamic_bitset(const dynamic_bitset<Block, Allocator>& other) = default;
449
455 constexpr dynamic_bitset(dynamic_bitset<Block, Allocator>&& other) noexcept = default;
456
462 constexpr dynamic_bitset<Block, Allocator>& operator=(
463 const dynamic_bitset<Block, Allocator>& other) = default;
464
470 constexpr dynamic_bitset<Block, Allocator>& operator=(
471 dynamic_bitset<Block, Allocator>&& other) noexcept = default;
472
484 constexpr explicit dynamic_bitset(const allocator_type& allocator = allocator_type());
485
502 constexpr explicit dynamic_bitset(size_type nbits,
503 unsigned long long init_val = 0,
504 const allocator_type& allocator = allocator_type());
505
520 constexpr dynamic_bitset(std::initializer_list<block_type> init_vals,
521 const allocator_type& allocator = allocator_type());
522
548 template<typename _CharT, typename _Traits>
549 constexpr explicit dynamic_bitset(
550 std::basic_string_view<_CharT, _Traits> str,
551 typename std::basic_string_view<_CharT, _Traits>::size_type pos = 0,
552 typename std::basic_string_view<_CharT, _Traits>::size_type n =
553 std::basic_string_view<_CharT, _Traits>::npos,
554 _CharT zero = _CharT('0'),
555 _CharT one = _CharT('1'),
556 const allocator_type& allocator = allocator_type());
557
584 template<typename _CharT, typename _Traits, typename _Alloc>
585 constexpr explicit dynamic_bitset(
586 const std::basic_string<_CharT, _Traits, _Alloc>& str,
587 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type pos = 0,
588 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type n =
589 std::basic_string<_CharT, _Traits, _Alloc>::npos,
590 _CharT zero = _CharT('0'),
591 _CharT one = _CharT('1'),
592 const allocator_type& allocator = allocator_type());
593
619 template<typename _CharT, typename _Traits = std::char_traits<_CharT>>
620 constexpr explicit dynamic_bitset(
621 const _CharT* str,
622 typename std::basic_string<_CharT>::size_type pos = 0,
623 typename std::basic_string<_CharT>::size_type n = std::basic_string<_CharT>::npos,
624 _CharT zero = _CharT('0'),
625 _CharT one = _CharT('1'),
626 const allocator_type& allocator = allocator_type());
627
633 ~dynamic_bitset() noexcept = default;
634
650 constexpr void resize(size_type nbits, bool value = false);
651
664 constexpr void clear();
665
678 constexpr void push_back(bool value);
679
690 constexpr void pop_back();
691
703 constexpr void append(block_type block);
704
716 constexpr void append(std::initializer_list<block_type> blocks);
717
733 template<typename BlockInputIterator>
734 constexpr void append(BlockInputIterator first, BlockInputIterator last);
735
752 constexpr dynamic_bitset<Block, Allocator>& operator&=(
753 const dynamic_bitset<Block, Allocator>& rhs);
754
771 constexpr dynamic_bitset<Block, Allocator>& operator|=(
772 const dynamic_bitset<Block, Allocator>& rhs);
773
790 constexpr dynamic_bitset<Block, Allocator>& operator^=(
791 const dynamic_bitset<Block, Allocator>& rhs);
792
814 constexpr dynamic_bitset<Block, Allocator>& operator-=(
815 const dynamic_bitset<Block, Allocator>& rhs);
816
830 constexpr dynamic_bitset<Block, Allocator>& operator<<=(size_type shift);
831
845 constexpr dynamic_bitset<Block, Allocator>& operator>>=(size_type shift);
846
865 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator<<(size_type shift) const;
866
885 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator>>(size_type shift) const;
886
902 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator~() const;
903
923 constexpr dynamic_bitset<Block, Allocator>& set(size_type pos, size_type len, bool value);
924
941 constexpr dynamic_bitset<Block, Allocator>& set(size_type pos, bool value = true);
942
952 constexpr dynamic_bitset<Block, Allocator>& set();
953
970 constexpr dynamic_bitset<Block, Allocator>& reset(size_type pos, size_type len);
971
987 constexpr dynamic_bitset<Block, Allocator>& reset(size_type pos);
988
998 constexpr dynamic_bitset<Block, Allocator>& reset();
999
1016 constexpr dynamic_bitset<Block, Allocator>& flip(size_type pos, size_type len);
1017
1033 constexpr dynamic_bitset<Block, Allocator>& flip(size_type pos);
1034
1044 constexpr dynamic_bitset<Block, Allocator>& flip();
1045
1061 [[nodiscard]] constexpr bool test(size_type pos) const;
1062
1080 [[nodiscard]] constexpr bool test_set(size_type pos, bool value = true);
1081
1095 [[nodiscard]] constexpr bool all() const;
1096
1110 [[nodiscard]] constexpr bool any() const;
1111
1125 [[nodiscard]] constexpr bool none() const;
1126
1138 [[nodiscard]] constexpr size_type count() const noexcept;
1139
1155 [[nodiscard]] constexpr reference operator[](size_type pos);
1156
1172 [[nodiscard]] constexpr const_reference operator[](size_type pos) const;
1173
1183 [[nodiscard]] constexpr size_type size() const noexcept;
1184
1194 [[nodiscard]] constexpr size_type num_blocks() const noexcept;
1195
1210 [[nodiscard]] constexpr bool empty() const noexcept;
1211
1222 [[nodiscard]] constexpr size_type capacity() const noexcept;
1223
1238 constexpr void reserve(size_type num_bits);
1239
1252 constexpr void shrink_to_fit();
1253
1282 [[nodiscard]] constexpr bool is_subset_of(const dynamic_bitset<Block, Allocator>& bitset) const;
1283
1312 [[nodiscard]] constexpr bool is_proper_subset_of(
1313 const dynamic_bitset<Block, Allocator>& bitset) const;
1314
1340 [[nodiscard]] constexpr bool intersects(const dynamic_bitset<Block, Allocator>& bitset) const;
1341
1355 [[nodiscard]] constexpr size_type find_first() const;
1356
1374 [[nodiscard]] constexpr size_type find_next(size_type prev) const;
1375
1387 constexpr void swap(dynamic_bitset<Block, Allocator>& other);
1388
1398 [[nodiscard]] constexpr allocator_type get_allocator() const;
1399
1422 template<typename _CharT = char,
1423 typename _Traits = std::char_traits<_CharT>,
1424 typename _Alloc = std::allocator<_CharT>>
1425 [[nodiscard]] constexpr std::basic_string<_CharT, _Traits, _Alloc> to_string(
1426 _CharT zero = _CharT('0'),
1427 _CharT one = _CharT('1')) const;
1428
1444 [[nodiscard]] constexpr unsigned long to_ulong() const;
1445
1461 [[nodiscard]] constexpr unsigned long long to_ullong() const;
1462
1490 template<typename Function, typename... Parameters>
1491 constexpr void iterate_bits_on(Function&& function, Parameters&&... parameters) const;
1492
1527 [[nodiscard]] constexpr block_type* data() noexcept;
1528
1563 [[nodiscard]] constexpr const block_type* data() const noexcept;
1564
1580 template<typename Block_, typename Allocator_>
1581 friend constexpr bool operator==(const dynamic_bitset<Block_, Allocator_>& lhs,
1582 const dynamic_bitset<Block_, Allocator_>& rhs);
1583
1630 template<typename Block_, typename Allocator_>
1631 friend constexpr bool operator<(const dynamic_bitset<Block_, Allocator_>& lhs,
1632 const dynamic_bitset<Block_, Allocator_>& rhs);
1633
1634private:
1635 template<typename T>
1636 struct dependent_false : public std::false_type
1637 {
1638 };
1639
1640 std::vector<Block, Allocator> m_blocks;
1641 size_type m_bits_number;
1642
1643 static constexpr block_type zero_block = block_type(0);
1644 static constexpr block_type one_block = block_type(~zero_block);
1645 static constexpr size_type block_last_bit_index = bits_per_block - 1;
1646
1647 static constexpr size_type blocks_required(size_type nbits) noexcept;
1648
1649 static constexpr size_type block_index(size_type pos) noexcept;
1650 static constexpr size_type bit_index(size_type pos) noexcept;
1651
1652 static constexpr block_type bit_mask(size_type pos) noexcept;
1653 static constexpr block_type bit_mask(size_type first, size_type last) noexcept;
1654
1655 static constexpr void set_block_bits(block_type& block,
1656 size_type first,
1657 size_type last,
1658 bool val = true) noexcept;
1659 static constexpr void flip_block_bits(block_type& block,
1660 size_type first,
1661 size_type last) noexcept;
1662
1663 static constexpr size_type block_count(const block_type& block) noexcept;
1664 static constexpr size_type block_count(const block_type& block, size_type nbits) noexcept;
1665
1666 static constexpr size_type count_block_trailing_zero(const block_type& block) noexcept;
1667
1668 template<typename _CharT, typename _Traits>
1669 constexpr void init_from_string(std::basic_string_view<_CharT, _Traits> str,
1670 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
1671 typename std::basic_string_view<_CharT, _Traits>::size_type n,
1672 _CharT zero,
1673 _CharT one);
1674
1675 constexpr block_type& get_block(size_type pos);
1676 constexpr const block_type& get_block(size_type pos) const;
1677 constexpr block_type& last_block();
1678 constexpr block_type last_block() const;
1679
1680 // used bits in the last block
1681 constexpr size_type extra_bits_number() const noexcept;
1682 // unused bits in the last block
1683 constexpr size_type unused_bits_number() const noexcept;
1684
1685 template<typename BinaryOperation>
1686 constexpr void apply(const dynamic_bitset<Block, Allocator>& other, BinaryOperation binary_op);
1687 template<typename UnaryOperation>
1688 constexpr void apply(UnaryOperation unary_op);
1689 constexpr void apply_left_shift(size_type shift);
1690 constexpr void apply_right_shift(size_type shift);
1691
1692 // reset unused bits to 0
1693 constexpr void sanitize();
1694
1695 // check functions used in asserts
1696 constexpr bool check_unused_bits() const noexcept;
1697 constexpr bool check_size() const noexcept;
1698 constexpr bool check_consistency() const noexcept;
1699};
1700
1701// Deduction guideline for expressions like "dynamic_bitset a(32);" with an integral type as parameter
1702// to use the constructor with the initial size instead of the constructor with the allocator.
1703template<typename integral_type, typename = std::enable_if_t<std::is_integral_v<integral_type>>>
1704dynamic_bitset(integral_type) -> dynamic_bitset<>;
1705
1706//=================================================================================================
1707// dynamic_bitset external functions declarations
1708//=================================================================================================
1709
1733template<typename Block, typename Allocator>
1734constexpr bool operator!=(const dynamic_bitset<Block, Allocator>& lhs,
1735 const dynamic_bitset<Block, Allocator>& rhs);
1736
1761template<typename Block, typename Allocator>
1762constexpr bool operator<=(const dynamic_bitset<Block, Allocator>& lhs,
1763 const dynamic_bitset<Block, Allocator>& rhs);
1764
1790template<typename Block, typename Allocator>
1791constexpr bool operator>(const dynamic_bitset<Block, Allocator>& lhs,
1792 const dynamic_bitset<Block, Allocator>& rhs);
1793
1819template<typename Block, typename Allocator>
1820constexpr bool operator>=(const dynamic_bitset<Block, Allocator>& lhs,
1821 const dynamic_bitset<Block, Allocator>& rhs);
1822
1852template<typename Block, typename Allocator>
1853constexpr dynamic_bitset<Block, Allocator> operator&(const dynamic_bitset<Block, Allocator>& lhs,
1854 const dynamic_bitset<Block, Allocator>& rhs);
1855
1885template<typename Block, typename Allocator>
1886constexpr dynamic_bitset<Block, Allocator> operator|(const dynamic_bitset<Block, Allocator>& lhs,
1887 const dynamic_bitset<Block, Allocator>& rhs);
1888
1918template<typename Block, typename Allocator>
1919constexpr dynamic_bitset<Block, Allocator> operator^(const dynamic_bitset<Block, Allocator>& lhs,
1920 const dynamic_bitset<Block, Allocator>& rhs);
1921
1951template<typename Block, typename Allocator>
1952constexpr dynamic_bitset<Block, Allocator> operator-(const dynamic_bitset<Block, Allocator>& lhs,
1953 const dynamic_bitset<Block, Allocator>& rhs);
1954
1980template<typename _CharT, typename _Traits, typename Block, typename Allocator>
1981constexpr std::basic_ostream<_CharT, _Traits>& operator<<(
1982 std::basic_ostream<_CharT, _Traits>& os,
1983 const dynamic_bitset<Block, Allocator>& bitset);
1984
2013template<typename _CharT, typename _Traits, typename Block, typename Allocator>
2014constexpr std::basic_istream<_CharT, _Traits>& operator>>(std::basic_istream<_CharT, _Traits>& is,
2015 dynamic_bitset<Block, Allocator>& bitset);
2016
2038template<typename Block, typename Allocator>
2039constexpr void swap(dynamic_bitset<Block, Allocator>& bitset1,
2040 dynamic_bitset<Block, Allocator>& bitset2);
2041
2042//=================================================================================================
2043// dynamic_bitset::reference functions implementations
2044//=================================================================================================
2045
2046template<typename Block, typename Allocator>
2047constexpr dynamic_bitset<Block, Allocator>::reference::reference(
2048 dynamic_bitset<Block, Allocator>& bitset,
2049 size_type bit_pos)
2050 : m_block(bitset.get_block(bit_pos)), m_mask(dynamic_bitset<Block, Allocator>::bit_mask(bit_pos))
2051{
2052}
2053
2054template<typename Block, typename Allocator>
2055constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2056 reference::operator=(bool v)
2057{
2058 assign(v);
2059 return *this;
2060}
2061
2062template<typename Block, typename Allocator>
2063constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2064 reference::operator=(const dynamic_bitset<Block, Allocator>::reference& rhs)
2065{
2066 assign(rhs);
2067 return *this;
2068}
2069
2070template<typename Block, typename Allocator>
2077
2078template<typename Block, typename Allocator>
2079constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2080 reference::operator&=(bool v)
2081{
2082 if(!v)
2083 {
2084 reset();
2085 }
2086 return *this;
2087}
2088
2089template<typename Block, typename Allocator>
2090constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2091 reference::operator|=(bool v)
2092{
2093 if(v)
2094 {
2095 set();
2096 }
2097 return *this;
2098}
2099
2100template<typename Block, typename Allocator>
2101constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2102 reference::operator^=(bool v)
2103{
2104 if(v)
2105 {
2106 flip();
2107 }
2108 return *this;
2109}
2110
2111template<typename Block, typename Allocator>
2112constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2113 reference::operator-=(bool v)
2114{
2115 if(v)
2116 {
2117 reset();
2118 }
2119 return *this;
2120}
2121
2122template<typename Block, typename Allocator>
2123constexpr bool dynamic_bitset<Block, Allocator>::reference::operator~() const
2124{
2125 return (m_block & m_mask) == zero_block;
2126}
2127
2128template<typename Block, typename Allocator>
2129constexpr dynamic_bitset<Block, Allocator>::reference::operator bool() const
2130{
2131 return (m_block & m_mask) != zero_block;
2132}
2133
2134template<typename Block, typename Allocator>
2135constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2136 reference::set()
2137{
2138 m_block |= m_mask;
2139 return *this;
2140}
2141
2142template<typename Block, typename Allocator>
2143constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2144 reference::reset()
2145{
2146 m_block &= static_cast<block_type>(~m_mask);
2147 return *this;
2148}
2149
2150template<typename Block, typename Allocator>
2151constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2152 reference::flip()
2153{
2154 m_block ^= m_mask;
2155 return *this;
2156}
2157
2158template<typename Block, typename Allocator>
2159constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::
2160 reference::assign(bool v)
2161{
2162 if(v)
2163 {
2164 set();
2165 }
2166 else
2167 {
2168 reset();
2169 }
2170 return *this;
2171}
2172
2173//=================================================================================================
2174// dynamic_bitset public functions implementations
2175//=================================================================================================
2176
2177template<typename Block, typename Allocator>
2178constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(const allocator_type& allocator)
2179 : m_blocks(allocator), m_bits_number(0)
2180{
2181}
2182
2183template<typename Block, typename Allocator>
2184constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(size_type nbits,
2185 unsigned long long init_val,
2186 const allocator_type& allocator)
2187 : m_blocks(blocks_required(nbits), allocator), m_bits_number(nbits)
2188{
2189 if(nbits == 0 || init_val == 0)
2190 {
2191 return;
2192 }
2193
2194 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
2195 constexpr size_t init_val_required_blocks = ull_bits_number / bits_per_block;
2196 if constexpr(init_val_required_blocks == 1)
2197 {
2198 m_blocks[0] = init_val;
2199 }
2200 else
2201 {
2202 const unsigned long long block_mask = static_cast<unsigned long long>(one_block);
2203 const size_t blocks_to_init = std::min(m_blocks.size(), init_val_required_blocks);
2204 for(size_t i = 0; i < blocks_to_init; ++i)
2205 {
2206 m_blocks[i] = block_type((init_val >> (i * bits_per_block) & block_mask));
2207 }
2208 }
2209 sanitize();
2210}
2211
2212template<typename Block, typename Allocator>
2213constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2214 std::initializer_list<block_type> init_vals,
2215 const allocator_type& allocator)
2216 : m_blocks(allocator), m_bits_number(0)
2217{
2218 append(init_vals);
2219}
2220
2221template<typename Block, typename Allocator>
2222template<typename _CharT, typename _Traits>
2223constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2224 std::basic_string_view<_CharT, _Traits> str,
2225 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
2226 typename std::basic_string_view<_CharT, _Traits>::size_type n,
2227 _CharT zero,
2228 _CharT one,
2229 const allocator_type& allocator)
2230 : m_blocks(allocator), m_bits_number(0)
2231{
2232 assert(pos < str.size());
2233 init_from_string(str, pos, n, zero, one);
2234}
2235
2236template<typename Block, typename Allocator>
2237template<typename _CharT, typename _Traits, typename _Alloc>
2238constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2239 const std::basic_string<_CharT, _Traits, _Alloc>& str,
2240 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type pos,
2241 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type n,
2242 _CharT zero,
2243 _CharT one,
2244 const allocator_type& allocator)
2245 : m_blocks(allocator), m_bits_number(0)
2246{
2247 assert(pos < str.size());
2248 init_from_string(std::basic_string_view<_CharT, _Traits>(str), pos, n, zero, one);
2249}
2250
2251template<typename Block, typename Allocator>
2252template<typename _CharT, typename _Traits>
2253constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2254 const _CharT* str,
2255 typename std::basic_string<_CharT>::size_type pos,
2256 typename std::basic_string<_CharT>::size_type n,
2257 _CharT zero,
2258 _CharT one,
2259 const allocator_type& allocator)
2260 : m_blocks(allocator), m_bits_number(0)
2261{
2262 init_from_string(std::basic_string_view<_CharT, _Traits>(str), pos, n, zero, one);
2263}
2264
2265template<typename Block, typename Allocator>
2266constexpr void dynamic_bitset<Block, Allocator>::resize(size_type nbits, bool value)
2267{
2268 if(nbits == m_bits_number)
2269 {
2270 return;
2271 }
2272
2273 const size_type old_num_blocks = num_blocks();
2274 const size_type new_num_blocks = blocks_required(nbits);
2275
2276 const block_type init_value = value ? one_block : zero_block;
2277 if(new_num_blocks != old_num_blocks)
2278 {
2279 m_blocks.resize(new_num_blocks, init_value);
2280 }
2281
2282 if(value && nbits > m_bits_number && old_num_blocks > 0)
2283 {
2284 // set value of the new bits in the old last block
2285 const size_type extra_bits = extra_bits_number();
2286 if(extra_bits > 0)
2287 {
2288 m_blocks[old_num_blocks - 1] |= static_cast<block_type>(init_value << extra_bits);
2289 }
2290 }
2291
2292 m_bits_number = nbits;
2293 sanitize();
2294 assert(check_consistency());
2295}
2296
2297template<typename Block, typename Allocator>
2298constexpr void dynamic_bitset<Block, Allocator>::clear()
2299{
2300 m_blocks.clear();
2301 m_bits_number = 0;
2302}
2303
2304template<typename Block, typename Allocator>
2305constexpr void dynamic_bitset<Block, Allocator>::push_back(bool value)
2306{
2307 const size_type new_last_bit = m_bits_number++;
2308 if(m_bits_number <= m_blocks.size() * bits_per_block)
2309 {
2310 if(value)
2311 {
2312 set(new_last_bit, value);
2313 }
2314 }
2315 else
2316 {
2317 m_blocks.push_back(block_type(value));
2318 }
2319 assert(operator[](new_last_bit) == value);
2320 assert(check_consistency());
2321}
2322
2323template<typename Block, typename Allocator>
2324constexpr void dynamic_bitset<Block, Allocator>::pop_back()
2325{
2326 if(empty())
2327 {
2328 return;
2329 }
2330
2331 --m_bits_number;
2332 if(m_blocks.size() > blocks_required(m_bits_number))
2333 {
2334 m_blocks.pop_back();
2335 // no extra bits: sanitize not required
2336 assert(extra_bits_number() == 0);
2337 }
2338 else
2339 {
2340 sanitize();
2341 }
2342 assert(check_consistency());
2343}
2344
2345template<typename Block, typename Allocator>
2346constexpr void dynamic_bitset<Block, Allocator>::append(block_type block)
2347{
2348 const size_type extra_bits = extra_bits_number();
2349 if(extra_bits == 0)
2350 {
2351 m_blocks.push_back(block);
2352 }
2353 else
2354 {
2355 last_block() |= static_cast<block_type>(block << extra_bits);
2356 m_blocks.push_back(block_type(block >> (bits_per_block - extra_bits)));
2357 }
2358
2359 m_bits_number += bits_per_block;
2360 assert(check_consistency());
2361}
2362
2363template<typename Block, typename Allocator>
2364constexpr void dynamic_bitset<Block, Allocator>::append(std::initializer_list<block_type> blocks)
2365{
2366 if(blocks.size() == 0)
2367 {
2368 return;
2369 }
2370
2371 append(std::cbegin(blocks), std::cend(blocks));
2372}
2373
2374template<typename Block, typename Allocator>
2375template<typename BlockInputIterator>
2376constexpr void dynamic_bitset<Block, Allocator>::append(BlockInputIterator first,
2377 BlockInputIterator last)
2378{
2379 if(first == last)
2380 {
2381 return;
2382 }
2383
2384 // if random access iterators, std::distance complexity is constant
2385 if constexpr(std::is_same_v<
2386 typename std::iterator_traits<BlockInputIterator>::iterator_category,
2387 std::random_access_iterator_tag>)
2388 {
2389 assert(std::distance(first, last) > 0);
2390 m_blocks.reserve(m_blocks.size() + static_cast<size_type>(std::distance(first, last)));
2391 }
2392
2393 const size_type extra_bits = extra_bits_number();
2394 const size_type unused_bits = unused_bits_number();
2395 if(extra_bits == 0)
2396 {
2397 auto pos = m_blocks.insert(std::end(m_blocks), first, last);
2398 assert(std::distance(pos, std::end(m_blocks)) > 0);
2399 m_bits_number +=
2400 static_cast<size_type>(std::distance(pos, std::end(m_blocks))) * bits_per_block;
2401 }
2402 else
2403 {
2404 last_block() |= static_cast<block_type>(*first << extra_bits);
2405 block_type block = block_type(*first >> unused_bits);
2406 ++first;
2407 while(first != last)
2408 {
2409 block |= static_cast<block_type>(*first << extra_bits);
2410 m_blocks.push_back(block);
2411 m_bits_number += bits_per_block;
2412 block = block_type(*first >> unused_bits);
2413 ++first;
2414 }
2415 m_blocks.push_back(block);
2416 m_bits_number += bits_per_block;
2417 }
2418
2419 assert(check_consistency());
2420}
2421template<typename Block, typename Allocator>
2422constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator&=(
2423 const dynamic_bitset<Block, Allocator>& rhs)
2424{
2425 assert(size() == rhs.size());
2426 //apply(rhs, std::bit_and());
2427 for(size_type i = 0; i < m_blocks.size(); ++i)
2428 {
2429 m_blocks[i] &= rhs.m_blocks[i];
2430 }
2431 return *this;
2432}
2433
2434template<typename Block, typename Allocator>
2435constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator|=(
2436 const dynamic_bitset<Block, Allocator>& rhs)
2437{
2438 assert(size() == rhs.size());
2439 //apply(rhs, std::bit_or());
2440 for(size_type i = 0; i < m_blocks.size(); ++i)
2441 {
2442 m_blocks[i] |= rhs.m_blocks[i];
2443 }
2444 return *this;
2445}
2446
2447template<typename Block, typename Allocator>
2448constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator^=(
2449 const dynamic_bitset<Block, Allocator>& rhs)
2450{
2451 assert(size() == rhs.size());
2452 //apply(rhs, std::bit_xor());
2453 for(size_type i = 0; i < m_blocks.size(); ++i)
2454 {
2455 m_blocks[i] ^= rhs.m_blocks[i];
2456 }
2457 return *this;
2458}
2459
2460template<typename Block, typename Allocator>
2461constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator-=(
2462 const dynamic_bitset<Block, Allocator>& rhs)
2463{
2464 assert(size() == rhs.size());
2465 //apply(rhs, [](const block_type& x, const block_type& y) { return (x & ~y); });
2466 for(size_type i = 0; i < m_blocks.size(); ++i)
2467 {
2468 m_blocks[i] &= static_cast<block_type>(~rhs.m_blocks[i]);
2469 }
2470 return *this;
2471}
2472
2473template<typename Block, typename Allocator>
2474constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator<<=(
2475 size_type shift)
2476{
2477 if(shift != 0)
2478 {
2479 if(shift >= m_bits_number)
2480 {
2481 reset();
2482 }
2483 else
2484 {
2485 apply_left_shift(shift);
2486 sanitize(); // unused bits can have changed, reset them to 0
2487 }
2488 }
2489 return *this;
2490}
2491
2492template<typename Block, typename Allocator>
2493constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator>>=(
2494 size_type shift)
2495{
2496 if(shift != 0)
2497 {
2498 if(shift >= m_bits_number)
2499 {
2500 reset();
2501 }
2502 else
2503 {
2504 apply_right_shift(shift);
2505 }
2506 }
2507 return *this;
2508}
2509
2510template<typename Block, typename Allocator>
2516
2517template<typename Block, typename Allocator>
2523
2524template<typename Block, typename Allocator>
2531
2532template<typename Block, typename Allocator>
2533constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::set(size_type pos,
2534 size_type len,
2535 bool value)
2536{
2537 assert(pos < size());
2538 if(len == 0)
2539 {
2540 return *this;
2541 }
2542 assert(pos + len - 1 < size());
2543
2544 const size_type first_block = block_index(pos);
2545 const size_type last_block = block_index(pos + len - 1);
2546 const size_type first_bit_index = bit_index(pos);
2547 const size_type last_bit_index = bit_index(pos + len - 1);
2548
2549 if(first_block == last_block)
2550 {
2551 set_block_bits(m_blocks[first_block], first_bit_index, last_bit_index, value);
2552 }
2553 else
2554 {
2555 size_type first_full_block = first_block;
2556 size_type last_full_block = last_block;
2557
2558 if(first_bit_index != 0)
2559 {
2560 ++first_full_block; // first block is not full
2561 set_block_bits(m_blocks[first_block], first_bit_index, block_last_bit_index, value);
2562 }
2563
2564 if(last_bit_index != block_last_bit_index)
2565 {
2566 --last_full_block; // last block is not full
2567 set_block_bits(m_blocks[last_block], 0, last_bit_index, value);
2568 }
2569
2570 const block_type full_block = value ? one_block : zero_block;
2571 for(size_type i = first_full_block; i <= last_full_block; ++i)
2572 {
2573 m_blocks[i] = full_block;
2574 }
2575 }
2576
2577 return *this;
2578}
2579
2580template<typename Block, typename Allocator>
2581constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::set(size_type pos,
2582 bool value)
2583{
2584 assert(pos < size());
2585
2586 if(value)
2587 {
2588 m_blocks[block_index(pos)] |= bit_mask(pos);
2589 }
2590 else
2591 {
2592 m_blocks[block_index(pos)] &= static_cast<block_type>(~bit_mask(pos));
2593 }
2594
2595 return *this;
2596}
2597
2598template<typename Block, typename Allocator>
2599constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::set()
2600{
2601 std::fill(std::begin(m_blocks), std::end(m_blocks), one_block);
2602 sanitize();
2603 return *this;
2604}
2605
2606template<typename Block, typename Allocator>
2612
2613template<typename Block, typename Allocator>
2618
2619template<typename Block, typename Allocator>
2620constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::reset()
2621{
2622 std::fill(std::begin(m_blocks), std::end(m_blocks), zero_block);
2623 return *this;
2624}
2625
2626template<typename Block, typename Allocator>
2627constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip(size_type pos,
2628 size_type len)
2629{
2630 assert(pos < size());
2631 if(len == 0)
2632 {
2633 return *this;
2634 }
2635 assert(pos + len - 1 < size());
2636
2637 const size_type first_block = block_index(pos);
2638 const size_type last_block = block_index(pos + len - 1);
2639 const size_type first_bit_index = bit_index(pos);
2640 const size_type last_bit_index = bit_index(pos + len - 1);
2641
2642 if(first_block == last_block)
2643 {
2644 flip_block_bits(m_blocks[first_block], first_bit_index, last_bit_index);
2645 }
2646 else
2647 {
2648 size_type first_full_block = first_block;
2649 size_type last_full_block = last_block;
2650
2651 if(first_bit_index != 0)
2652 {
2653 ++first_full_block; // first block is not full
2654 flip_block_bits(m_blocks[first_block], first_bit_index, block_last_bit_index);
2655 }
2656
2657 if(last_bit_index != block_last_bit_index)
2658 {
2659 --last_full_block; // last block is not full
2660 flip_block_bits(m_blocks[last_block], 0, last_bit_index);
2661 }
2662
2663 for(size_type i = first_full_block; i <= last_full_block; ++i)
2664 {
2665 m_blocks[i] = block_type(~m_blocks[i]);
2666 }
2667 }
2668
2669 return *this;
2670}
2671
2672template<typename Block, typename Allocator>
2673constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip(size_type pos)
2674{
2675 assert(pos < size());
2676 m_blocks[block_index(pos)] ^= bit_mask(pos);
2677 return *this;
2678}
2679
2680template<typename Block, typename Allocator>
2681constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip()
2682{
2683 std::transform(
2684 std::cbegin(m_blocks), std::cend(m_blocks), std::begin(m_blocks), std::bit_not<block_type>());
2685 sanitize();
2686 return *this;
2687}
2688
2689template<typename Block, typename Allocator>
2690constexpr bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
2691{
2692 assert(pos < size());
2693 return (m_blocks[block_index(pos)] & bit_mask(pos)) != zero_block;
2694}
2695
2696template<typename Block, typename Allocator>
2697constexpr bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool value)
2698{
2699 bool const result = test(pos);
2700 if(result != value)
2701 {
2702 set(pos, value);
2703 }
2704 return result;
2705}
2706
2707template<typename Block, typename Allocator>
2708constexpr bool dynamic_bitset<Block, Allocator>::all() const
2709{
2710 if(empty())
2711 {
2712 return true;
2713 }
2714
2715 const block_type full_block = one_block;
2716 if(extra_bits_number() == 0)
2717 {
2718 for(const block_type& block: m_blocks)
2719 {
2720 if(block != full_block)
2721 {
2722 return false;
2723 }
2724 }
2725 }
2726 else
2727 {
2728 for(size_type i = 0; i < m_blocks.size() - 1; ++i)
2729 {
2730 if(m_blocks[i] != full_block)
2731 {
2732 return false;
2733 }
2734 }
2735 if(last_block() != (full_block >> unused_bits_number()))
2736 {
2737 return false;
2738 }
2739 }
2740 return true;
2741}
2742
2743template<typename Block, typename Allocator>
2744constexpr bool dynamic_bitset<Block, Allocator>::any() const
2745{
2746 for(const block_type& block: m_blocks)
2747 {
2748 if(block != zero_block)
2749 {
2750 return true;
2751 }
2752 }
2753 return false;
2754}
2755
2756template<typename Block, typename Allocator>
2757constexpr bool dynamic_bitset<Block, Allocator>::none() const
2758{
2759 return !any();
2760}
2761
2762template<typename Block, typename Allocator>
2763constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block,
2764 Allocator>::count()
2765 const noexcept
2766{
2767 if(empty())
2768 {
2769 return 0;
2770 }
2771
2772#if DYNAMIC_BITSET_CAN_USE_LIBPOPCNT
2773 const size_type count =
2774 static_cast<size_type>(popcnt(m_blocks.data(), m_blocks.size() * sizeof(block_type)));
2775#else
2776 size_type count = 0;
2777
2778 // full blocks
2779 for(size_type i = 0; i < m_blocks.size() - 1; ++i)
2780 {
2781 count += block_count(m_blocks[i]);
2782 }
2783
2784 // last block
2785 const block_type& block = last_block();
2786 const size_type extra_bits = extra_bits_number();
2787 if(extra_bits == 0)
2788 {
2789 count += block_count(block);
2790 }
2791 else
2792 {
2793 count += block_count(block, extra_bits);
2794 }
2795#endif
2796 return count;
2797}
2798
2799template<typename Block, typename Allocator>
2806
2807template<typename Block, typename Allocator>
2808constexpr typename dynamic_bitset<Block, Allocator>::const_reference dynamic_bitset<
2809 Block,
2810 Allocator>::operator[](size_type pos) const
2811{
2812 return test(pos);
2813}
2814
2815template<typename Block, typename Allocator>
2816constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block,
2817 Allocator>::size()
2818 const noexcept
2819{
2820 return m_bits_number;
2821}
2822
2823template<typename Block, typename Allocator>
2829
2830template<typename Block, typename Allocator>
2831constexpr bool dynamic_bitset<Block, Allocator>::empty() const noexcept
2832{
2833 return size() == 0;
2834}
2835
2836template<typename Block, typename Allocator>
2837constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block,
2838 Allocator>::capacity()
2839 const noexcept
2840{
2841 return m_blocks.capacity() * bits_per_block;
2842}
2843
2844template<typename Block, typename Allocator>
2845constexpr void dynamic_bitset<Block, Allocator>::reserve(size_type num_bits)
2846{
2847 m_blocks.reserve(blocks_required(num_bits));
2848}
2849
2850template<typename Block, typename Allocator>
2851constexpr void dynamic_bitset<Block, Allocator>::shrink_to_fit()
2852{
2853 m_blocks.shrink_to_fit();
2854}
2855
2856template<typename Block, typename Allocator>
2857constexpr bool dynamic_bitset<Block, Allocator>::is_subset_of(
2858 const dynamic_bitset<Block, Allocator>& bitset) const
2859{
2860 assert(size() == bitset.size());
2861 for(size_type i = 0; i < m_blocks.size(); ++i)
2862 {
2863 if((m_blocks[i] & ~bitset.m_blocks[i]) != zero_block)
2864 {
2865 return false;
2866 }
2867 }
2868 return true;
2869}
2870
2871template<typename Block, typename Allocator>
2872constexpr bool dynamic_bitset<Block, Allocator>::is_proper_subset_of(
2873 const dynamic_bitset<Block, Allocator>& bitset) const
2874{
2875 assert(size() == bitset.size());
2876 bool is_proper = false;
2877 for(size_type i = 0; i < m_blocks.size(); ++i)
2878 {
2879 const block_type& self_block = m_blocks[i];
2880 const block_type& other_block = bitset.m_blocks[i];
2881
2882 if((self_block & ~other_block) != zero_block)
2883 {
2884 return false;
2885 }
2886 if((~self_block & other_block) != zero_block)
2887 {
2888 is_proper = true;
2889 }
2890 }
2891 return is_proper;
2892}
2893
2894template<typename Block, typename Allocator>
2895constexpr bool dynamic_bitset<Block, Allocator>::intersects(
2896 const dynamic_bitset<Block, Allocator>& bitset) const
2897{
2898 const size_type min_blocks_number = std::min(m_blocks.size(), bitset.m_blocks.size());
2899 for(size_type i = 0; i < min_blocks_number; ++i)
2900 {
2901 if((m_blocks[i] & bitset.m_blocks[i]) != zero_block)
2902 {
2903 return true;
2904 }
2905 }
2906 return false;
2907}
2908
2909template<typename Block, typename Allocator>
2910constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
2911 find_first() const
2912{
2913 for(size_type i = 0; i < m_blocks.size(); ++i)
2914 {
2915 if(m_blocks[i] != zero_block)
2916 {
2917 return i * bits_per_block + count_block_trailing_zero(m_blocks[i]);
2918 }
2919 }
2920 return npos;
2921}
2922
2923template<typename Block, typename Allocator>
2924constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
2925 find_next(size_type prev) const
2926{
2927 if(empty() || prev >= (size() - 1))
2928 {
2929 return npos;
2930 }
2931
2932 const size_type first_bit = prev + 1;
2933 const size_type first_block = block_index(first_bit);
2934 const size_type first_bit_index = bit_index(first_bit);
2935 const block_type first_block_shifted = block_type(m_blocks[first_block] >> first_bit_index);
2936
2937 if(first_block_shifted != zero_block)
2938 {
2939 return first_bit + count_block_trailing_zero(first_block_shifted);
2940 }
2941 else
2942 {
2943 for(size_type i = first_block + 1; i < m_blocks.size(); ++i)
2944 {
2945 if(m_blocks[i] != zero_block)
2946 {
2947 return i * bits_per_block + count_block_trailing_zero(m_blocks[i]);
2948 }
2949 }
2950 }
2951 return npos;
2952}
2953
2954template<typename Block, typename Allocator>
2955constexpr void dynamic_bitset<Block, Allocator>::swap(dynamic_bitset<Block, Allocator>& other)
2956{
2957 std::swap(m_blocks, other.m_blocks);
2958 std::swap(m_bits_number, other.m_bits_number);
2959}
2960
2961template<typename Block, typename Allocator>
2962constexpr typename dynamic_bitset<Block, Allocator>::allocator_type dynamic_bitset<
2963 Block,
2964 Allocator>::get_allocator() const
2965{
2966 return m_blocks.get_allocator();
2967}
2968
2969template<typename Block, typename Allocator>
2970template<typename _CharT, typename _Traits, typename _Alloc>
2971constexpr std::basic_string<_CharT, _Traits, _Alloc> dynamic_bitset<Block, Allocator>::to_string(
2972 _CharT zero,
2973 _CharT one) const
2974{
2975 const size_type len = size();
2976 std::basic_string<_CharT, _Traits, _Alloc> str(len, zero);
2977 for(size_type i_block = 0; i_block < m_blocks.size(); ++i_block)
2978 {
2979 if(m_blocks[i_block] == zero_block)
2980 {
2981 continue;
2982 }
2983 block_type mask = block_type(1);
2984 const size_type limit =
2985 i_block * bits_per_block < len ? len - i_block * bits_per_block : bits_per_block;
2986 for(size_type i_bit = 0; i_bit < limit; ++i_bit)
2987 {
2988 if((m_blocks[i_block] & mask) != zero_block)
2989 {
2990 _Traits::assign(str[len - (i_block * bits_per_block + i_bit + 1)], one);
2991 }
2992 // mask <<= 1; not used because it trigger -Wconversion because of integral promotion for block_type smaller than int
2993 mask = static_cast<block_type>(mask << 1);
2994 }
2995 }
2996 return str;
2997}
2998
2999template<typename Block, typename Allocator>
3000constexpr unsigned long dynamic_bitset<Block, Allocator>::to_ulong() const
3001{
3002 if(m_bits_number == 0)
3003 {
3004 return 0;
3005 }
3006
3007 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3008 if(find_next(ul_bits_number - 1) != npos)
3009 {
3010 throw std::overflow_error("sul::dynamic_bitset::to_ulong");
3011 }
3012
3013 unsigned long result = 0;
3014 const size_type result_bits_number = std::min(ul_bits_number, m_bits_number);
3015 for(size_type i_block = 0; i_block <= block_index(result_bits_number - 1); ++i_block)
3016 {
3017 result |= (static_cast<unsigned long>(m_blocks[i_block]) << (i_block * bits_per_block));
3018 }
3019
3020 return result;
3021}
3022
3023template<typename Block, typename Allocator>
3024constexpr unsigned long long dynamic_bitset<Block, Allocator>::to_ullong() const
3025{
3026 if(m_bits_number == 0)
3027 {
3028 return 0;
3029 }
3030
3031 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3032 if(find_next(ull_bits_number - 1) != npos)
3033 {
3034 throw std::overflow_error("sul::dynamic_bitset::to_ullong");
3035 }
3036
3037 unsigned long long result = 0;
3038 const size_type result_bits_number = std::min(ull_bits_number, m_bits_number);
3039 for(size_type i_block = 0; i_block <= block_index(result_bits_number - 1); ++i_block)
3040 {
3041 result |=
3042 (static_cast<unsigned long long>(m_blocks[i_block]) << (i_block * bits_per_block));
3043 }
3044
3045 return result;
3046}
3047
3048template<typename Block, typename Allocator>
3049template<typename Function, typename... Parameters>
3050constexpr void dynamic_bitset<Block, Allocator>::iterate_bits_on(Function&& function,
3051 Parameters&&... parameters) const
3052{
3053 if constexpr(!std::is_invocable_v<Function, size_t, Parameters...>)
3054 {
3055 static_assert(dependent_false<Function>::value, "Function take invalid arguments");
3056 // function should take (size_t, parameters...) as arguments
3057 }
3058
3059 if constexpr(std::is_same_v<std::invoke_result_t<Function, size_t, Parameters...>, void>)
3060 {
3061 size_type i_bit = find_first();
3062 while(i_bit != npos)
3063 {
3064 std::invoke(
3065 std::forward<Function>(function), i_bit, std::forward<Parameters>(parameters)...);
3066 i_bit = find_next(i_bit);
3067 }
3068 }
3069 else if constexpr(std::is_convertible_v<std::invoke_result_t<Function, size_t, Parameters...>,
3070 bool>)
3071 {
3072 size_type i_bit = find_first();
3073 while(i_bit != npos)
3074 {
3075 if(!std::invoke(
3076 std::forward<Function>(function), i_bit, std::forward<Parameters>(parameters)...))
3077 {
3078 break;
3079 }
3080 i_bit = find_next(i_bit);
3081 }
3082 }
3083 else
3084 {
3085 static_assert(dependent_false<Function>::value, "Function have invalid return type");
3086 // return type should be void, or convertible to bool
3087 }
3088}
3089
3090template<typename Block, typename Allocator>
3091constexpr typename dynamic_bitset<Block, Allocator>::block_type* dynamic_bitset<Block, Allocator>::
3092 data() noexcept
3093{
3094 return m_blocks.data();
3095}
3096
3097template<typename Block, typename Allocator>
3098constexpr const typename dynamic_bitset<Block, Allocator>::block_type* dynamic_bitset<
3099 Block,
3100 Allocator>::data() const noexcept
3101{
3102 return m_blocks.data();
3103}
3104
3105template<typename Block_, typename Allocator_>
3106[[nodiscard]] constexpr bool operator==(const dynamic_bitset<Block_, Allocator_>& lhs,
3107 const dynamic_bitset<Block_, Allocator_>& rhs)
3108{
3109 return (lhs.m_bits_number == rhs.m_bits_number) && (lhs.m_blocks == rhs.m_blocks);
3110}
3111
3112template<typename Block_, typename Allocator_>
3113[[nodiscard]] constexpr bool operator<(const dynamic_bitset<Block_, Allocator_>& lhs,
3114 const dynamic_bitset<Block_, Allocator_>& rhs)
3115{
3116 using size_type = typename dynamic_bitset<Block_, Allocator_>::size_type;
3117 using block_type = typename dynamic_bitset<Block_, Allocator_>::block_type;
3118 const size_type lhs_size = lhs.size();
3119 const size_type rhs_size = rhs.size();
3120 const size_type lhs_blocks_size = lhs.m_blocks.size();
3121 const size_type rhs_blocks_size = rhs.m_blocks.size();
3122
3123 if(lhs_size == rhs_size)
3124 {
3125 // if comparison of two empty bitsets
3126 if(lhs_size == 0)
3127 {
3128 return false;
3129 }
3130
3131 for(size_type i = lhs_blocks_size - 1; i > 0; --i)
3132 {
3133 if(lhs.m_blocks[i] != rhs.m_blocks[i])
3134 {
3135 return lhs.m_blocks[i] < rhs.m_blocks[i];
3136 }
3137 }
3138 return lhs.m_blocks[0] < rhs.m_blocks[0];
3139 }
3140
3141 // empty bitset inferior to 0-only bitset
3142 if(lhs_size == 0)
3143 {
3144 return true;
3145 }
3146 if(rhs_size == 0)
3147 {
3148 return false;
3149 }
3150
3151 const bool rhs_longer = rhs_size > lhs_size;
3152 const dynamic_bitset<Block_, Allocator_>& longest_bitset = rhs_longer ? rhs : lhs;
3153 const size_type longest_blocks_size = std::max(lhs_blocks_size, rhs_blocks_size);
3154 const size_type shortest_blocks_size = std::min(lhs_blocks_size, rhs_blocks_size);
3155 for(size_type i = longest_blocks_size - 1; i >= shortest_blocks_size; --i)
3156 {
3157 if(longest_bitset.m_blocks[i] != block_type(0))
3158 {
3159 return rhs_longer;
3160 }
3161 }
3162
3163 for(size_type i = shortest_blocks_size - 1; i > 0; --i)
3164 {
3165 if(lhs.m_blocks[i] != rhs.m_blocks[i])
3166 {
3167 return lhs.m_blocks[i] < rhs.m_blocks[i];
3168 }
3169 }
3170 if(lhs.m_blocks[0] != rhs.m_blocks[0])
3171 {
3172 return lhs.m_blocks[0] < rhs.m_blocks[0];
3173 }
3174 return lhs_size < rhs_size;
3175}
3176
3177//=================================================================================================
3178// dynamic_bitset private functions implementations
3179//=================================================================================================
3180
3181template<typename Block, typename Allocator>
3182constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3183 blocks_required(size_type nbits) noexcept
3184{
3185 return nbits / bits_per_block + static_cast<size_type>(nbits % bits_per_block > 0);
3186}
3187
3188template<typename Block, typename Allocator>
3189constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3190 block_index(size_type pos) noexcept
3191{
3192 return pos / bits_per_block;
3193}
3194
3195template<typename Block, typename Allocator>
3196constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3197 bit_index(size_type pos) noexcept
3198{
3199 return pos % bits_per_block;
3200}
3201
3202template<typename Block, typename Allocator>
3203constexpr typename dynamic_bitset<Block, Allocator>::block_type dynamic_bitset<Block, Allocator>::
3204 bit_mask(size_type pos) noexcept
3205{
3206 return block_type(block_type(1) << bit_index(pos));
3207}
3208
3209template<typename Block, typename Allocator>
3210constexpr typename dynamic_bitset<Block, Allocator>::block_type dynamic_bitset<Block, Allocator>::
3211 bit_mask(size_type first, size_type last) noexcept
3212{
3213 first = bit_index(first);
3214 last = bit_index(last);
3215 if(last == (block_last_bit_index))
3216 {
3217 return block_type(one_block << first);
3218 }
3219 else
3220 {
3221 return block_type(((block_type(1) << (last + 1)) - 1) ^ ((block_type(1) << first) - 1));
3222 }
3223}
3224
3225template<typename Block, typename Allocator>
3226constexpr void dynamic_bitset<Block, Allocator>::set_block_bits(block_type& block,
3227 size_type first,
3228 size_type last,
3229 bool val) noexcept
3230{
3231 if(val)
3232 {
3233 block |= bit_mask(first, last);
3234 }
3235 else
3236 {
3237 block &= static_cast<block_type>(~bit_mask(first, last));
3238 }
3239}
3240
3241template<typename Block, typename Allocator>
3242constexpr void dynamic_bitset<Block, Allocator>::flip_block_bits(block_type& block,
3243 size_type first,
3244 size_type last) noexcept
3245{
3246 block ^= bit_mask(first, last);
3247}
3248
3249template<typename Block, typename Allocator>
3250constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3251 block_count(const block_type& block) noexcept
3252{
3253#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3254 return static_cast<size_type>(std::popcount(block));
3255#else
3256 if(block == zero_block)
3257 {
3258 return 0;
3259 }
3260
3261# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
3262 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3263 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3264 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3265 if constexpr(bits_per_block <= u_bits_number)
3266 {
3267 return static_cast<size_type>(__builtin_popcount(static_cast<unsigned int>(block)));
3268 }
3269 else if constexpr(bits_per_block <= ul_bits_number)
3270 {
3271 return static_cast<size_type>(__builtin_popcountl(static_cast<unsigned long>(block)));
3272 }
3273 else if constexpr(bits_per_block <= ull_bits_number)
3274 {
3275 return static_cast<size_type>(__builtin_popcountll(static_cast<unsigned long long>(block)));
3276 }
3277# endif
3278
3279 size_type count = 0;
3280 block_type mask = 1;
3281 for(size_type bit_index = 0; bit_index < bits_per_block; ++bit_index)
3282 {
3283 count += static_cast<size_type>((block & mask) != zero_block);
3284 // mask <<= 1; not used because it trigger -Wconversion because of integral promotion for block_type smaller than int
3285 mask = static_cast<block_type>(mask << 1);
3286 }
3287 return count;
3288#endif
3289}
3290
3291template<typename Block, typename Allocator>
3292constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3293 block_count(const block_type& block, size_type nbits) noexcept
3294{
3295 assert(nbits <= bits_per_block);
3296#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3297 const block_type shifted_block = block_type(block << (bits_per_block - nbits));
3298 return static_cast<size_type>(std::popcount(shifted_block));
3299#else
3300 const block_type shifted_block = block_type(block << (bits_per_block - nbits));
3301 if(shifted_block == zero_block)
3302 {
3303 return 0;
3304 }
3305
3306# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
3307 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3308 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3309 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3310 if constexpr(bits_per_block <= u_bits_number)
3311 {
3312 return static_cast<size_type>(__builtin_popcount(static_cast<unsigned int>(shifted_block)));
3313 }
3314 else if constexpr(bits_per_block <= ul_bits_number)
3315 {
3316 return static_cast<size_type>(
3317 __builtin_popcountl(static_cast<unsigned long>(shifted_block)));
3318 }
3319 else if constexpr(bits_per_block <= ull_bits_number)
3320 {
3321 return static_cast<size_type>(
3322 __builtin_popcountll(static_cast<unsigned long long>(shifted_block)));
3323 }
3324# endif
3325
3326 size_type count = 0;
3327 block_type mask = 1;
3328 for(size_type bit_index = 0; bit_index < nbits; ++bit_index)
3329 {
3330 count += static_cast<size_type>((block & mask) != zero_block);
3331 // mask <<= 1; not used because it trigger -Wconversion because of integral promotion for block_type smaller than int
3332 mask = static_cast<block_type>(mask << 1);
3333 }
3334
3335 return count;
3336#endif
3337}
3338
3339template<typename Block, typename Allocator>
3340constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3341 count_block_trailing_zero(const block_type& block) noexcept
3342{
3343 assert(block != zero_block);
3344#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3345 return static_cast<size_type>(std::countr_zero(block));
3346#else
3347# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ
3348 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3349 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3350 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3351 if constexpr(bits_per_block <= u_bits_number)
3352 {
3353 return static_cast<size_type>(__builtin_ctz(static_cast<unsigned int>(block)));
3354 }
3355 else if constexpr(bits_per_block <= ul_bits_number)
3356 {
3357 return static_cast<size_type>(__builtin_ctzl(static_cast<unsigned long>(block)));
3358 }
3359 else if constexpr(bits_per_block <= ull_bits_number)
3360 {
3361 return static_cast<size_type>(__builtin_ctzll(static_cast<unsigned long long>(block)));
3362 }
3363
3364# elif DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD
3365 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3366 constexpr size_t ui64_bits_number = std::numeric_limits<unsigned __int64>::digits;
3367 if constexpr(bits_per_block <= ul_bits_number)
3368 {
3369 unsigned long index = std::numeric_limits<unsigned long>::max();
3370 _BitScanForward(&index, static_cast<unsigned long>(block));
3371 return static_cast<size_type>(index);
3372 }
3373 else if constexpr(bits_per_block <= ui64_bits_number)
3374 {
3375# if DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64
3376 unsigned long index = std::numeric_limits<unsigned long>::max();
3377 _BitScanForward64(&index, static_cast<unsigned __int64>(block));
3378 return static_cast<size_type>(index);
3379# else
3380 constexpr unsigned long max_ul = std::numeric_limits<unsigned long>::max();
3381 unsigned long low = block & max_ul;
3382 if(low != 0)
3383 {
3384 unsigned long index = std::numeric_limits<unsigned long>::max();
3385 _BitScanForward(&index, low);
3386 return static_cast<size_type>(index);
3387 }
3388 unsigned long high = block >> ul_bits_number;
3389 unsigned long index = std::numeric_limits<unsigned long>::max();
3390 _BitScanForward(&index, high);
3391 return static_cast<size_type>(ul_bits_number + index);
3392# endif
3393 }
3394# endif
3395
3396 block_type mask = block_type(1);
3397 for(size_type i = 0; i < bits_per_block; ++i)
3398 {
3399 if((block & mask) != zero_block)
3400 {
3401 return i;
3402 }
3403 // mask <<= 1; not used because it trigger -Wconversion because of integral promotion for block_type smaller than int
3404 mask = static_cast<block_type>(mask << 1);
3405 }
3406 assert(false); // LCOV_EXCL_LINE: unreachable
3407 return npos; // LCOV_EXCL_LINE: unreachable
3408#endif
3409}
3410
3411template<typename Block, typename Allocator>
3412template<typename _CharT, typename _Traits>
3413constexpr void dynamic_bitset<Block, Allocator>::init_from_string(
3414 std::basic_string_view<_CharT, _Traits> str,
3415 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
3416 typename std::basic_string_view<_CharT, _Traits>::size_type n,
3417 [[maybe_unused]] _CharT zero,
3418 _CharT one)
3419{
3420 assert(pos < str.size());
3421
3422 const size_type size = std::min(n, str.size() - pos);
3423 m_bits_number = size;
3424
3425 m_blocks.clear();
3426 m_blocks.resize(blocks_required(size));
3427 for(size_t i = 0; i < size; ++i)
3428 {
3429 const _CharT c = str[(pos + size - 1) - i];
3430 assert(c == zero || c == one);
3431 if(c == one)
3432 {
3433 set(i);
3434 }
3435 }
3436}
3437
3438template<typename Block, typename Allocator>
3439constexpr typename dynamic_bitset<Block, Allocator>::block_type& dynamic_bitset<Block, Allocator>::
3440 get_block(size_type pos)
3441{
3442 return m_blocks[block_index(pos)];
3443}
3444
3445template<typename Block, typename Allocator>
3446constexpr const typename dynamic_bitset<Block, Allocator>::block_type& dynamic_bitset<
3447 Block,
3448 Allocator>::get_block(size_type pos) const
3449{
3450 return m_blocks[block_index(pos)];
3451}
3452
3453template<typename Block, typename Allocator>
3454constexpr typename dynamic_bitset<Block, Allocator>::block_type& dynamic_bitset<Block, Allocator>::
3455 last_block()
3456{
3457 return m_blocks[m_blocks.size() - 1];
3458}
3459
3460template<typename Block, typename Allocator>
3461constexpr typename dynamic_bitset<Block, Allocator>::block_type dynamic_bitset<Block, Allocator>::
3462 last_block() const
3463{
3464 return m_blocks[m_blocks.size() - 1];
3465}
3466
3467template<typename Block, typename Allocator>
3468constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3469 extra_bits_number() const noexcept
3470{
3471 return bit_index(m_bits_number);
3472}
3473
3474template<typename Block, typename Allocator>
3475constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::
3476 unused_bits_number() const noexcept
3477{
3478 return bits_per_block - extra_bits_number();
3479}
3480
3481template<typename Block, typename Allocator>
3482template<typename BinaryOperation>
3483constexpr void dynamic_bitset<Block, Allocator>::apply(
3484 const dynamic_bitset<Block, Allocator>& other,
3485 BinaryOperation binary_op)
3486{
3487 assert(num_blocks() == other.num_blocks());
3488 std::transform(std::cbegin(m_blocks),
3489 std::cend(m_blocks),
3490 std::cbegin(other.m_blocks),
3491 std::begin(m_blocks),
3492 binary_op);
3493}
3494
3495template<typename Block, typename Allocator>
3496template<typename UnaryOperation>
3497constexpr void dynamic_bitset<Block, Allocator>::apply(UnaryOperation unary_op)
3498{
3499 std::transform(std::cbegin(m_blocks), std::cend(m_blocks), std::begin(m_blocks), unary_op);
3500}
3501
3502template<typename Block, typename Allocator>
3503constexpr void dynamic_bitset<Block, Allocator>::apply_left_shift(size_type shift)
3504{
3505 assert(shift > 0);
3506 assert(shift < capacity());
3507
3508 const size_type blocks_shift = shift / bits_per_block;
3509 const size_type bits_offset = shift % bits_per_block;
3510
3511 if(bits_offset == 0)
3512 {
3513 for(size_type i = m_blocks.size() - 1; i >= blocks_shift; --i)
3514 {
3515 m_blocks[i] = m_blocks[i - blocks_shift];
3516 }
3517 }
3518 else
3519 {
3520 const size_type reverse_bits_offset = bits_per_block - bits_offset;
3521 for(size_type i = m_blocks.size() - 1; i > blocks_shift; --i)
3522 {
3523 m_blocks[i] =
3524 block_type((m_blocks[i - blocks_shift] << bits_offset)
3525 | block_type(m_blocks[i - blocks_shift - 1] >> reverse_bits_offset));
3526 }
3527 m_blocks[blocks_shift] = block_type(m_blocks[0] << bits_offset);
3528 }
3529
3530 // set bit that came at the right to 0 in unmodified blocks
3531 std::fill(std::begin(m_blocks),
3532 std::begin(m_blocks)
3533 + static_cast<typename decltype(m_blocks)::difference_type>(blocks_shift),
3534 zero_block);
3535}
3536
3537template<typename Block, typename Allocator>
3538constexpr void dynamic_bitset<Block, Allocator>::apply_right_shift(size_type shift)
3539{
3540 assert(shift > 0);
3541 assert(shift < capacity());
3542
3543 const size_type blocks_shift = shift / bits_per_block;
3544 const size_type bits_offset = shift % bits_per_block;
3545 const size_type last_block_to_shift = m_blocks.size() - blocks_shift - 1;
3546
3547 if(bits_offset == 0)
3548 {
3549 for(size_type i = 0; i <= last_block_to_shift; ++i)
3550 {
3551 m_blocks[i] = m_blocks[i + blocks_shift];
3552 }
3553 }
3554 else
3555 {
3556 const size_type reverse_bits_offset = bits_per_block - bits_offset;
3557 for(size_type i = 0; i < last_block_to_shift; ++i)
3558 {
3559 m_blocks[i] =
3560 block_type((m_blocks[i + blocks_shift] >> bits_offset)
3561 | block_type(m_blocks[i + blocks_shift + 1] << reverse_bits_offset));
3562 }
3563 m_blocks[last_block_to_shift] = block_type(m_blocks[m_blocks.size() - 1] >> bits_offset);
3564 }
3565
3566 // set bit that came at the left to 0 in unmodified blocks
3567 std::fill(
3568 std::begin(m_blocks)
3569 + static_cast<typename decltype(m_blocks)::difference_type>(last_block_to_shift + 1),
3570 std::end(m_blocks),
3571 zero_block);
3572}
3573
3574template<typename Block, typename Allocator>
3575constexpr void dynamic_bitset<Block, Allocator>::sanitize()
3576{
3577 size_type shift = m_bits_number % bits_per_block;
3578 if(shift > 0)
3579 {
3580 last_block() &= static_cast<block_type>(~(one_block << shift));
3581 }
3582}
3583
3584template<typename Block, typename Allocator>
3585constexpr bool dynamic_bitset<Block, Allocator>::check_unused_bits() const noexcept
3586{
3587 const size_type extra_bits = extra_bits_number();
3588 if(extra_bits > 0)
3589 {
3590 return (last_block() & (one_block << extra_bits)) == zero_block;
3591 }
3592 return true;
3593}
3594
3595template<typename Block, typename Allocator>
3596constexpr bool dynamic_bitset<Block, Allocator>::check_size() const noexcept
3597{
3598 return blocks_required(size()) == m_blocks.size();
3599}
3600
3601template<typename Block, typename Allocator>
3602constexpr bool dynamic_bitset<Block, Allocator>::check_consistency() const noexcept
3603{
3604 return check_unused_bits() && check_size();
3605}
3606
3607//=================================================================================================
3608// dynamic_bitset external functions implementations
3609//=================================================================================================
3610
3611template<typename Block, typename Allocator>
3612constexpr bool operator!=(const dynamic_bitset<Block, Allocator>& lhs,
3613 const dynamic_bitset<Block, Allocator>& rhs)
3614{
3615 return !(lhs == rhs);
3616}
3617
3618template<typename Block, typename Allocator>
3619constexpr bool operator<=(const dynamic_bitset<Block, Allocator>& lhs,
3620 const dynamic_bitset<Block, Allocator>& rhs)
3621{
3622 return !(rhs < lhs);
3623}
3624
3625template<typename Block, typename Allocator>
3626constexpr bool operator>(const dynamic_bitset<Block, Allocator>& lhs,
3627 const dynamic_bitset<Block, Allocator>& rhs)
3628{
3629 return rhs < lhs;
3630}
3631
3632template<typename Block, typename Allocator>
3633constexpr bool operator>=(const dynamic_bitset<Block, Allocator>& lhs,
3634 const dynamic_bitset<Block, Allocator>& rhs)
3635{
3636 return !(lhs < rhs);
3637}
3638
3639template<typename Block, typename Allocator>
3646
3647template<typename Block, typename Allocator>
3654
3655template<typename Block, typename Allocator>
3662
3663template<typename Block, typename Allocator>
3670
3671template<typename _CharT, typename _Traits, typename Block, typename Allocator>
3672constexpr std::basic_ostream<_CharT, _Traits>& operator<<(
3673 std::basic_ostream<_CharT, _Traits>& os,
3674 const dynamic_bitset<Block, Allocator>& bitset)
3675{
3676 // A better implementation is possible
3677 return os << bitset.template to_string<_CharT, _Traits>();
3678}
3679
3680template<typename _CharT, typename _Traits, typename Block, typename Allocator>
3681constexpr std::basic_istream<_CharT, _Traits>& operator>>(std::basic_istream<_CharT, _Traits>& is,
3682 dynamic_bitset<Block, Allocator>& bitset)
3683{
3684 // A better implementation is possible
3685 constexpr _CharT zero = _CharT('0');
3686 constexpr _CharT one = _CharT('1');
3687 typename std::basic_istream<_CharT, _Traits>::sentry s(is);
3688 if(!s)
3689 {
3690 return is;
3691 }
3692
3693 dynamic_bitset<Block, Allocator> reverse_bitset;
3694 _CharT val;
3695 is.get(val);
3696 while(is.good())
3697 {
3698 if(val == one)
3699 {
3700 reverse_bitset.push_back(true);
3701 }
3702 else if(val == zero)
3703 {
3704 reverse_bitset.push_back(false);
3705 }
3706 else
3707 {
3708 is.unget();
3709 break;
3710 }
3711 is.get(val);
3712 }
3713
3714 bitset.clear();
3715 if(!reverse_bitset.empty())
3716 {
3717 for(typename dynamic_bitset<Block, Allocator>::size_type i = reverse_bitset.size() - 1;
3718 i > 0;
3719 --i)
3720 {
3721 bitset.push_back(reverse_bitset.test(i));
3722 }
3723 bitset.push_back(reverse_bitset.test(0));
3724 }
3725
3726 return is;
3727}
3728
3729template<typename Block, typename Allocator>
3735
3736#ifndef DYNAMIC_BITSET_NO_NAMESPACE
3737} // namespace sul
3738#endif
3739
3740#endif //SUL_DYNAMIC_BITSET_HPP
sul::dynamic_bitset::reference
Reference to a sul::dynamic_bitset bit.
Definition dynamic_bitset.hpp:222
sul::dynamic_bitset::reference::reset
constexpr reference & reset()
Reset the referenced bit to false.
Definition dynamic_bitset.hpp:2144
sul::dynamic_bitset::reference::operator-=
constexpr reference & operator-=(bool v)
Apply binary difference to the referenced bit and a value, and assign the result to the referenced bi...
Definition dynamic_bitset.hpp:2113
sul::dynamic_bitset::reference::assign
constexpr reference & assign(bool v)
Assign the value v to the referenced bit.
Definition dynamic_bitset.hpp:2160
sul::dynamic_bitset::reference::reference
constexpr reference(dynamic_bitset< Block, Allocator > &bitset, size_type bit_pos)
Constructs a reference to a bit from a sul::dynamic_bitset and a bit position.
Definition dynamic_bitset.hpp:2047
sul::dynamic_bitset::reference::operator|=
constexpr reference & operator|=(bool v)
Apply binary operator OR to the referenced bit and a value, and assign the result to the referenced b...
Definition dynamic_bitset.hpp:2091
sul::dynamic_bitset::reference::reference
constexpr reference(const reference &) noexcept=default
Copy constructor.
sul::dynamic_bitset::reference::reference
constexpr reference(reference &&) noexcept=default
Move constructor.
sul::dynamic_bitset::reference::operator&=
constexpr reference & operator&=(bool v)
Apply binary operator AND to the referenced bit and a value, and assign the result to the referenced ...
Definition dynamic_bitset.hpp:2080
sul::dynamic_bitset::reference::operator~
constexpr bool operator~() const
Return the result of applying unary NOT operator.
Definition dynamic_bitset.hpp:2123
sul::dynamic_bitset::reference::operator=
constexpr reference & operator=(bool v)
Assign a value to the referenced bit.
Definition dynamic_bitset.hpp:2056
sul::dynamic_bitset::reference::flip
constexpr reference & flip()
Flip the referenced bit.
Definition dynamic_bitset.hpp:2152
sul::dynamic_bitset::reference::set
constexpr reference & set()
Set the referenced bit to true.
Definition dynamic_bitset.hpp:2136
sul::dynamic_bitset::reference::operator^=
constexpr reference & operator^=(bool v)
Apply binary operator XOR to the referenced bit and a value, and assign the result to the referenced ...
Definition dynamic_bitset.hpp:2102
sul::dynamic_bitset
Dynamic bitset.
Definition dynamic_bitset.hpp:172
sul::dynamic_bitset::operator<<=
constexpr dynamic_bitset< Block, Allocator > & operator<<=(size_type shift)
Performs binary shift left of shift bits.
Definition dynamic_bitset.hpp:2474
sul::dynamic_bitset::size
constexpr size_type size() const noexcept
Give the number of bits of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2817
sul::dynamic_bitset::operator^=
constexpr dynamic_bitset< Block, Allocator > & operator^=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary XOR on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2448
sul::dynamic_bitset::push_back
constexpr void push_back(bool value)
Add a new bit with the value value at the end of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2305
sul::dynamic_bitset::test_set
constexpr bool test_set(size_type pos, bool value=true)
Test the value of the bit at position pos and set it to true or value value.
Definition dynamic_bitset.hpp:2697
sul::dynamic_bitset::set
constexpr dynamic_bitset< Block, Allocator > & set()
Set all the bits of the sul::dynamic_bitset to true.
Definition dynamic_bitset.hpp:2599
sul::dynamic_bitset::iterate_bits_on
constexpr void iterate_bits_on(Function &&function, Parameters &&... parameters) const
Iterate on the sul::dynamic_bitset and call function with the position of the bits on.
Definition dynamic_bitset.hpp:3050
sul::dynamic_bitset::empty
constexpr bool empty() const noexcept
Checks if the sul::dynamic_bitset is empty.
Definition dynamic_bitset.hpp:2831
sul::dynamic_bitset::block_type
Block block_type
Same type as Block.
Definition dynamic_bitset.hpp:188
sul::dynamic_bitset::any
constexpr bool any() const
Checks if any bits are set to true.
Definition dynamic_bitset.hpp:2744
sul::dynamic_bitset::operator<<
constexpr dynamic_bitset< Block, Allocator > operator<<(size_type shift) const
Performs binary shift right of shift bits.
Definition dynamic_bitset.hpp:2511
sul::dynamic_bitset::clear
constexpr void clear()
Clears the sul::dynamic_bitset, resize it to 0.
Definition dynamic_bitset.hpp:2298
sul::dynamic_bitset::num_blocks
constexpr size_type num_blocks() const noexcept
Give the number of blocks used by the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2825
sul::dynamic_bitset::is_subset_of
constexpr bool is_subset_of(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset is a subset of bitset.
Definition dynamic_bitset.hpp:2857
sul::dynamic_bitset::size_type
size_t size_type
Type used to represent the size of a sul::dynamic_bitset.
Definition dynamic_bitset.hpp:181
sul::dynamic_bitset::to_string
constexpr std::basic_string< _CharT, _Traits, _Alloc > to_string(_CharT zero=_CharT('0'), _CharT one=_CharT('1')) const
Generate a string representation of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2971
sul::dynamic_bitset::all
constexpr bool all() const
Checks if all bits are set to true.
Definition dynamic_bitset.hpp:2708
sul::dynamic_bitset::reset
constexpr dynamic_bitset< Block, Allocator > & reset()
Reset all the bits of the sul::dynamic_bitset to false.
Definition dynamic_bitset.hpp:2620
sul::dynamic_bitset::operator&=
constexpr dynamic_bitset< Block, Allocator > & operator&=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary AND on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2422
sul::dynamic_bitset::allocator_type
Allocator allocator_type
Same type as Allocator.
Definition dynamic_bitset.hpp:195
sul::dynamic_bitset::is_proper_subset_of
constexpr bool is_proper_subset_of(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset is a proper subset of bitset.
Definition dynamic_bitset.hpp:2872
sul::dynamic_bitset::operator-=
constexpr dynamic_bitset< Block, Allocator > & operator-=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of the binary difference between the bits of *this and rhs.
Definition dynamic_bitset.hpp:2461
sul::dynamic_bitset::swap
constexpr void swap(dynamic_bitset< Block, Allocator > &other)
Exchanges the bits of this sul::dynamic_bitset with those of other.
Definition dynamic_bitset.hpp:2955
sul::dynamic_bitset::count
constexpr size_type count() const noexcept
Count the number of bits set to true.
Definition dynamic_bitset.hpp:2764
sul::dynamic_bitset::dynamic_bitset
constexpr dynamic_bitset(const dynamic_bitset< Block, Allocator > &other)=default
Copy constructor.
sul::dynamic_bitset::capacity
constexpr size_type capacity() const noexcept
Give the number of bits that the sul::dynamic_bitset has currently allocated space for.
Definition dynamic_bitset.hpp:2838
sul::dynamic_bitset::operator|=
constexpr dynamic_bitset< Block, Allocator > & operator|=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary OR on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2435
sul::dynamic_bitset::to_ulong
constexpr unsigned long to_ulong() const
Converts the contents of the bitset to an unsigned long integer.
Definition dynamic_bitset.hpp:3000
sul::dynamic_bitset::flip
constexpr dynamic_bitset< Block, Allocator > & flip()
Flip all the bits of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2681
sul::dynamic_bitset::find_next
constexpr size_type find_next(size_type prev) const
Find the position of the first bit set in the range [prev + 1, size()[ of the sul::dynamic_bitset sta...
Definition dynamic_bitset.hpp:2925
sul::dynamic_bitset::test
constexpr bool test(size_type pos) const
Test the value of the bit at position pos.
Definition dynamic_bitset.hpp:2690
sul::dynamic_bitset::reserve
constexpr void reserve(size_type num_bits)
Increase the capacity of the sul::dynamic_bitset to a value that's greater or equal to num_bits.
Definition dynamic_bitset.hpp:2845
sul::dynamic_bitset::shrink_to_fit
constexpr void shrink_to_fit()
Requests the removal of unused capacity.
Definition dynamic_bitset.hpp:2851
sul::dynamic_bitset::none
constexpr bool none() const
Checks if none of the bits are set to true.
Definition dynamic_bitset.hpp:2757
sul::dynamic_bitset::find_first
constexpr size_type find_first() const
Find the position of the first bit set in the sul::dynamic_bitset starting from the least-significant...
Definition dynamic_bitset.hpp:2911
sul::dynamic_bitset::bits_per_block
static constexpr size_type bits_per_block
Number of bits that can be stored in a block.
Definition dynamic_bitset.hpp:202
sul::dynamic_bitset::intersects
constexpr bool intersects(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset and bitset intersect.
Definition dynamic_bitset.hpp:2895
sul::dynamic_bitset::append
constexpr void append(block_type block)
Append a block of bits block at the end of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2346
sul::dynamic_bitset::const_reference
bool const_reference
Const reference to a sul::dynamic_bitset bit, type bool.
Definition dynamic_bitset.hpp:441
sul::dynamic_bitset::get_allocator
constexpr allocator_type get_allocator() const
Gets the associated allocator.
Definition dynamic_bitset.hpp:2964
sul::dynamic_bitset::data
constexpr block_type * data() noexcept
Return a pointer to the underlying array serving as blocks storage.
Definition dynamic_bitset.hpp:3092
sul::dynamic_bitset::operator[]
constexpr reference operator[](size_type pos)
Accesses the bit at position pos.
Definition dynamic_bitset.hpp:2801
sul::dynamic_bitset::flip
constexpr dynamic_bitset< Block, Allocator > & flip(size_type pos, size_type len)
Flip the bits of the range [pos, pos + len[.
Definition dynamic_bitset.hpp:2627
sul::dynamic_bitset::npos
static constexpr size_type npos
Maximum value of size_type, returned for invalid positions.
Definition dynamic_bitset.hpp:209
sul::dynamic_bitset::pop_back
constexpr void pop_back()
Remove the last bit of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2324
sul::dynamic_bitset::resize
constexpr void resize(size_type nbits, bool value=false)
Resize the sul::dynamic_bitset to contain nbits bits.
Definition dynamic_bitset.hpp:2266
sul::dynamic_bitset::operator~
constexpr dynamic_bitset< Block, Allocator > operator~() const
Performs a unary NOT on all bits.
Definition dynamic_bitset.hpp:2525
sul::dynamic_bitset::to_ullong
constexpr unsigned long long to_ullong() const
Converts the contents of the bitset to an unsigned long long integer.
Definition dynamic_bitset.hpp:3024
sul::dynamic_bitset::operator>>
constexpr dynamic_bitset< Block, Allocator > operator>>(size_type shift) const
Performs binary shift left of shift bits.
Definition dynamic_bitset.hpp:2518
sul::dynamic_bitset::operator>>=
constexpr dynamic_bitset< Block, Allocator > & operator>>=(size_type shift)
Performs binary shift right of shift bits.
Definition dynamic_bitset.hpp:2493
sul
Simple Useful Libraries.
Definition dynamic_bitset.hpp:148
sul::operator>=
constexpr bool operator>=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "greater than or equal to" rhs. The comparison of the two sul::dynamic_bitset is first...
Definition dynamic_bitset.hpp:3633
sul::operator<=
constexpr bool operator<=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "less than or equal to" rhs. The comparison of the two sul::dynamic_bitset is first on...
Definition dynamic_bitset.hpp:3619
sul::operator<
constexpr bool operator<(const dynamic_bitset< Block_, Allocator_ > &lhs, const dynamic_bitset< Block_, Allocator_ > &rhs)
Definition dynamic_bitset.hpp:3113
sul::operator>
constexpr bool operator>(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "greater than" rhs. The comparison of the two sul::dynamic_bitset is first on numbers ...
Definition dynamic_bitset.hpp:3626
sul::operator>>
constexpr std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &is, dynamic_bitset< Block, Allocator > &bitset)
Extract a sul::dynamic_bitset from a character stream using its string representation.
Definition dynamic_bitset.hpp:3681
sul::operator|
constexpr dynamic_bitset< Block, Allocator > operator|(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary OR on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3648
sul::operator&
constexpr dynamic_bitset< Block, Allocator > operator&(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary AND on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3640
sul::operator-
constexpr dynamic_bitset< Block, Allocator > operator-(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary difference between bits of lhs and rhs.
Definition dynamic_bitset.hpp:3664
sul::operator^
constexpr dynamic_bitset< Block, Allocator > operator^(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary XOR on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3656
sul::operator<<
constexpr std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &os, const dynamic_bitset< Block, Allocator > &bitset)
Insert a string representation of this sul::dynamic_bitset to a character stream.
Definition dynamic_bitset.hpp:3672
sul::swap
constexpr void swap(dynamic_bitset< Block, Allocator > &bitset1, dynamic_bitset< Block, Allocator > &bitset2)
Exchange the content of bitset1 and bitset2.
Definition dynamic_bitset.hpp:3730
sul::operator==
constexpr bool operator==(const dynamic_bitset< Block_, Allocator_ > &lhs, const dynamic_bitset< Block_, Allocator_ > &rhs)
Definition dynamic_bitset.hpp:3106
sul::operator!=
constexpr bool operator!=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if two sul::dynamic_bitset content are different.
Definition dynamic_bitset.hpp:3612