1#pragma once
2
3#include <nn/util.h>
4
5#include <iterator>
6
7namespace nn::util {
8class BitArray {
9 NN_NO_COPY(BitArray);
10
11public:
12 class iterator;
13 class const_iterator;
14
15 typedef bool value_type;
16 typedef value_type* pointer;
17 typedef const value_type* const_pointer;
18 typedef const bool const_reference;
19 typedef std::reverse_iterator<iterator> reverse_iterator;
20 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
21 typedef int size_type;
22 typedef int difference_type;
23
24 class reference {
25 BitArray* m_pParent;
26 size_type m_Pos;
27
28 public:
29 reference& flip();
30 operator bool() const;
31 reference& operator=(bool);
32 reference& operator=(const reference&);
33 bool operator~() const;
34
35 private:
36 reference(BitArray*, size_type);
37 };
38
39 class iterator {
40 typedef difference_type difference_type;
41 typedef reference reference;
42 typedef pointer pointer;
43
44 BitArray* m_pParent;
45 difference_type m_Pos;
46
47 public:
48 operator const_iterator() const;
49 iterator& operator++();
50 iterator operator++(difference_type);
51 iterator& operator--();
52 iterator operator--(difference_type);
53 iterator& operator+=(difference_type);
54 iterator operator+(difference_type) const;
55 iterator& operator-=(difference_type);
56 iterator operator-(difference_type) const;
57 difference_type operator-(const iterator&) const;
58 bool operator==(const iterator&) const;
59 bool operator!=(const iterator&) const;
60 bool operator<(const iterator&) const;
61 bool operator>(const iterator&) const;
62 bool operator<=(const iterator&) const;
63 bool operator>=(const iterator&) const;
64 reference operator*() const;
65 reference operator[](difference_type) const;
66
67 private:
68 iterator(BitArray*, difference_type);
69 };
70
71 class const_iterator {
72 typedef difference_type difference_type;
73 typedef const_reference reference;
74 typedef const_pointer pointer;
75
76 const BitArray* m_pParent;
77 difference_type m_Pos;
78
79 public:
80 const_iterator& operator++();
81 const_iterator operator++(difference_type);
82 const_iterator& operator--();
83 const_iterator operator--(difference_type);
84 const_iterator& operator+=(difference_type);
85 const_iterator operator+(difference_type) const;
86 const_iterator& operator-=(difference_type);
87 const_iterator operator-(difference_type) const;
88 difference_type operator-(const const_iterator&) const;
89 reference operator==(const const_iterator&) const;
90 reference operator!=(const const_iterator&) const;
91 reference operator<(const const_iterator&) const;
92 reference operator>(const const_iterator&) const;
93 reference operator<=(const const_iterator&) const;
94 reference operator>=(const const_iterator&) const;
95 reference operator*() const;
96 reference operator[](difference_type) const;
97
98 private:
99 const_iterator(const BitArray*, difference_type);
100 };
101
102 BitArray();
103 BitArray(void* workMemory, [[maybe_unused]] size_t workMemorySize, size_type length)
104 : m_pBuf(static_cast<RawType*>(workMemory)), m_Len(length) {}
105
106 void* ResetWorkMemory();
107 void* ResetWorkMemory(void*, size_t, size_type);
108 size_type size() const;
109 size_type count() const;
110 bool all() const;
111 bool none() const;
112 bool any() const;
113
114 bool test(size_type pos) const { return Block(pos) & MakeBlockMask(pos); }
115
116 BitArray& flip();
117 BitArray& flip(size_type);
118 BitArray& set();
119
120 BitArray& set(size_type pos) {
121 Block(pos) |= MakeBlockMask(pos);
122 return *this;
123 }
124
125 BitArray& set(size_type pos, bool value) {
126 if (value) {
127 set(pos);
128 } else {
129 reset(pos);
130 }
131
132 return *this;
133 }
134
135 BitArray& reset();
136
137 BitArray& reset(size_type pos) {
138 Block(pos) &= ~MakeBlockMask(pos);
139 return *this;
140 }
141
142 iterator begin();
143 const_iterator begin() const;
144 iterator end();
145 const_iterator end() const;
146 reverse_iterator rbegin();
147 const_reverse_iterator rbegin() const;
148 reverse_iterator rend();
149 const_reverse_iterator rend() const;
150 const_iterator cbegin() const;
151 const_iterator cend() const;
152 const_reverse_iterator crbegin() const;
153 const_reverse_iterator crend() const;
154 bool operator==(const BitArray&) const;
155 bool operator!=(const BitArray&) const;
156 bool operator[](size_type) const;
157 reference operator[](size_type);
158 static void And(BitArray*, const BitArray&, const BitArray&);
159 static void Or(BitArray*, const BitArray&, const BitArray&);
160 static void Xor(BitArray*, const BitArray&, const BitArray&);
161 static void Not(BitArray*, const BitArray&);
162 static void RightShift(BitArray*, const BitArray&, size_type);
163 static void LeftShift(BitArray*, const BitArray&, size_type);
164 static size_t CalculateWorkMemorySize(size_type);
165
166private:
167 typedef uint64_t RawType;
168
169 static const size_type BitsPerBlock = 64;
170 static const size_type BlockShift = 6;
171 static const RawType BlockBitMask = BitsPerBlock - 1;
172
173 RawType& Block(size_type pos) { return m_pBuf[pos >> BlockShift]; }
174 const RawType& Block(size_type pos) const { return m_pBuf[pos >> BlockShift]; }
175
176 static RawType MakeBlockMask(size_type pos) { return RawType(1) << (pos & BlockBitMask); }
177 size_type GetBlockCount() const;
178 RawType MakeLastBlockBitMask() const;
179
180 RawType* m_pBuf;
181 size_type m_Len;
182};
183} // namespace nn::util