Nebula
Loading...
Searching...
No Matches
bitarray.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
18#include "core/types.h"
19#include "util/array.h"
20
21namespace Util
22{
23//------------------------------------------------------------------------------
27{
28public:
30 BitArray();
32 ~BitArray();
33
35 void Resize(uint64_t numBits);
37 void EnsureBit(uint64_t bitIndex);
38
40 void SetBit(const uint64_t bitIndex);
42 void ClearBit(const uint64_t bitIndex);
44 bool IsSet(const uint64_t bitIndex) const;
46 void MoveBit(const uint64_t from, const uint64_t to);
47
49 bool IsNull() const;
51 bool SectionIsNull(const uint64_t section) const;
53 SizeT NumSections() const;
55 IndexT FirstSetBitInSection(const uint64_t section) const;
56
58 void Clear();
60 void Reset();
61
62private:
64};
65
66//------------------------------------------------------------------------------
69inline
73
74//------------------------------------------------------------------------------
77inline
81
82//------------------------------------------------------------------------------
85inline void
86BitArray::Resize(uint64_t numBits)
87{
88 SizeT const numWords = (SizeT)((numBits + 63) / 64);
89 if (numWords > this->words.Size())
90 {
91 this->words.Resize(numWords, 0);
92 }
93}
94
95//------------------------------------------------------------------------------
98inline void
99BitArray::EnsureBit(const uint64_t bitIndex)
100{
101 this->Resize(bitIndex + 1);
102}
103
104//------------------------------------------------------------------------------
107inline void
108BitArray::SetBit(const uint64_t bitIndex)
109{
110 this->Resize(bitIndex + 1);
111 this->words[bitIndex / 64] |= (1ULL << (bitIndex % 64));
112}
113
114//------------------------------------------------------------------------------
117inline void
118BitArray::ClearBit(const uint64_t bitIndex)
119{
120 if (bitIndex / 64 >= (uint64_t)this->words.Size())
121 {
122 return;
123 }
124 this->words[bitIndex / 64] &= ~(1ULL << (bitIndex % 64));
125}
126
127//------------------------------------------------------------------------------
130inline bool
131BitArray::IsSet(const uint64_t bitIndex) const
132{
133 if (bitIndex / 64 >= (uint64_t)this->words.Size())
134 {
135 return false;
136 }
137 return (this->words[bitIndex / 64] >> (bitIndex % 64)) & 1ULL;
138}
139
140//------------------------------------------------------------------------------
143inline void
144BitArray::MoveBit(const uint64_t from, const uint64_t to)
145{
146 bool const set = this->IsSet(from);
147 this->ClearBit(from);
148 if (set)
149 {
150 this->SetBit(to);
151 }
152}
153
154//------------------------------------------------------------------------------
157inline bool
159{
160 for (IndexT i = 0; i < this->words.Size(); i++)
161 {
162 if (this->words[i] != 0)
163 {
164 return false;
165 }
166 }
167 return true;
168}
169
170//------------------------------------------------------------------------------
173inline bool
174BitArray::SectionIsNull(const uint64_t section) const
175{
176 if (section >= (uint64_t)this->words.Size())
177 {
178 return true;
179 }
180 return this->words[section] == 0;
181}
182
183//------------------------------------------------------------------------------
186inline SizeT
188{
189 return this->words.Size();
190}
191
192//------------------------------------------------------------------------------
195inline IndexT
196BitArray::FirstSetBitInSection(const uint64_t section) const
197{
198 if (section >= (uint64_t)this->words.Size())
199 {
200 return InvalidIndex;
201 }
202 uint64_t const word = this->words[section];
203 if (word == 0)
204 {
205 return InvalidIndex;
206 }
207 IndexT bit = 0;
208 uint64_t remaining = word;
209 while ((remaining & 1ULL) == 0)
210 {
211 remaining >>= 1;
212 bit++;
213 }
214 return (IndexT)(section * 64 + (uint64_t)bit);
215}
216
217//------------------------------------------------------------------------------
220inline void
222{
223 for (IndexT i = 0; i < this->words.Size(); i++)
224 {
225 this->words[i] = 0;
226 }
227}
228
229//------------------------------------------------------------------------------
232inline void
234{
235 this->words.Clear();
236}
237
238} // namespace Util
239//------------------------------------------------------------------------------
Nebula's dynamic array class.
Definition array.h:61
void Clear()
clear array (calls destructors)
Definition array.h:1288
void Resize(SizeT num)
Set size. Grows array if num is greater than capacity. Calls destroy on all objects at index > num!
Definition array.h:1711
const SizeT Size() const
get number of elements in array
Definition array.h:934
~BitArray()
destructor
Definition bitarray.h:78
bool SectionIsNull(const uint64_t section) const
true when a whole 64 bit section is empty
Definition bitarray.h:174
void MoveBit(const uint64_t from, const uint64_t to)
move a bit from one index to another. The source is cleared and the target gets the value
Definition bitarray.h:144
void EnsureBit(uint64_t bitIndex)
make a bit addressable, growing the array when it is outside
Definition bitarray.h:99
BitArray()
constructor
Definition bitarray.h:70
Util::Array< uint64_t > words
Definition bitarray.h:63
bool IsNull() const
true when no bit is set
Definition bitarray.h:158
void Resize(uint64_t numBits)
resize to a number of bits. Growing keeps the bits which are already set, shrinking is not supported
Definition bitarray.h:86
SizeT NumSections() const
number of 64 bit sections which are allocated
Definition bitarray.h:187
void Reset()
clear all bits and release the storage
Definition bitarray.h:233
void ClearBit(const uint64_t bitIndex)
clear a bit by index. Does nothing when the index is outside the array
Definition bitarray.h:118
bool IsSet(const uint64_t bitIndex) const
check a bit by index. False when the index is outside the array
Definition bitarray.h:131
IndexT FirstSetBitInSection(const uint64_t section) const
the index of the first set bit in a section, or InvalidIndex when the section is empty
Definition bitarray.h:196
void Clear()
clear all bits. The allocated words are kept
Definition bitarray.h:221
void SetBit(const uint64_t bitIndex)
set a bit by index, growing the array when the index is outside it
Definition bitarray.h:108
A quad tree designed to return regions of free 2D space.
Definition Random.cs:4
int SizeT
Definition types.h:42
int IndexT
Definition types.h:41