1// tBitArray.h 
2// 
3// A tBitArray is a holder for an arbitrary number of bits and allows individual access to each bit, the ability to 
4// clear or set all bits, and some simple binary bitwise operators such as 'and', 'xor', and 'or'. It currently does 
5// not support dynamic growing or shrinking. If the number of bits you need is known at compile time, consider using a 
6// tBitField instead as it is more feature-complete. 
7// 
8// Copyright (c) 2004-2006, 2015, 2017, 2019 Tristan Grimmer. 
9// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
10// granted, provided that the above copyright notice and this permission notice appear in all copies. 
11// 
12// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
13// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
14// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
15// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
16// PERFORMANCE OF THIS SOFTWARE. 
17 
18#pragma once 
19#include "Foundation/tPlatform.h" 
20#include "Foundation/tStandard.h" 
21 
22 
23class tBitArray 
24{ 
25public: 
26 tBitArray() /* Creates an invalid bit array. Call Set before using. */ : NumBits(0), BitFields(nullptr) { } 
27 tBitArray(int numBits) /* All bit values guaranteed to be 0 after this. */ : NumBits(0), BitFields(nullptr) { Set(numBits); } 
28 tBitArray(const uint32* data, int numBits) /* Copies numBits from data. */ : NumBits(0), BitFields(nullptr) { Set(data, numBits); } 
29 tBitArray(const tBitArray& src) : NumBits(0), BitFields(nullptr) { Set(src); } 
30 ~tBitArray() { delete[] BitFields; } 
31 
32 void Set(int numBits); // All bit values guaranteed to be 0 after this. 
33 void Set(const uint32* data, int numBits); // Copies numBits from data. 
34 void Set(const tBitArray& src); 
35 void Clear() /* Invalidates. Use ClearAll if you want all bits clear. */ { delete[] BitFields; BitFields = nullptr; NumBits = 0; } 
36 bool IsValid() const { return BitFields ? true : false; } 
37 
38 bool GetBit(int n) const; // n is the bit index with 0 being the least significant. 
39 void SetBit(int n, bool v); 
40 void SetAll(bool v = true); 
41 void ClearAll(); 
42 void InvertAll(); 
43 bool AreAll(bool v) const; 
44 int GetNumBits() const { return NumBits; } 
45 int CountBits(bool = true) const; // Counts how many bits are set to supplied value. 
46 
47 // Returns how many uint32 fields are used to store the bit array. 
48 int GetNumFields() const { return (NumBits>>5) + ((NumBits & 0x1F) ? 1 : 0); } 
49 uint32* GetFields() const { return BitFields; } 
50 
51 // Returns index of a bit that is clear. Which one is arbitrary. Returns -1 if none are available. 
52 int GetClearedBitPos() const; 
53 
54 // Binary operators must operate on arrays with the same number of bits. 
55 tBitArray& operator=(const tBitArray& src) { Set(src); return *this; } 
56 tBitArray& operator&=(const tBitArray&); 
57 tBitArray& operator|=(const tBitArray&); 
58 tBitArray& operator^=(const tBitArray&); 
59 
60 const tBitArray operator~() const { tBitArray r(*this); r.InvertAll(); return r; } 
61 bool operator[](int n) const { return GetBit(n); } 
62 bool operator==(const tBitArray&) const; 
63 bool operator!=(const tBitArray&) const; 
64 
65private: 
66 int GetClearedBit(int index) const; 
67 void ClearPadBits(); 
68 
69 int NumBits; // Number of bits. Not number of fields. 
70 uint32* BitFields; // If there are padding bits, they must be set to 0. 
71}; 
72 
73 
74// Implementation below this line. 
75 
76 
77inline bool tBitArray::GetBit(int index) const 
78{ 
79 tAssert(index < NumBits); 
80 int fieldIndex = index >> 5; 
81 int offset = index & 0x1F; 
82 uint32 mask = 1 << offset; 
83 
84 return (BitFields[fieldIndex] & mask) ? true : false; 
85} 
86 
87 
88inline void tBitArray::SetBit(int index, bool v) 
89{ 
90 tAssert(index < NumBits); 
91 int fieldIndex = index >> 5; 
92 int offset = index & 0x1F; 
93 uint32 mask = 1 << offset; 
94 if (v) 
95 BitFields[fieldIndex] |= mask; 
96 else 
97 BitFields[fieldIndex] &= ~mask; 
98} 
99 
100 
101inline void tBitArray::SetAll(bool v) 
102{ 
103 int n = GetNumFields(); 
104 tStd::tMemset(BitFields, v ? 0xFF : 0, n*sizeof(uint32)); 
105 if (v) 
106 ClearPadBits(); 
107} 
108 
109 
110inline void tBitArray::ClearAll() 
111{ 
112 tAssert(BitFields); 
113 int n = GetNumFields(); 
114 tStd::tMemset(BitFields, 0, n*sizeof(uint32)); 
115} 
116 
117 
118inline bool tBitArray::operator==(const tBitArray& s) const 
119{ 
120 tAssert(GetNumBits() == s.GetNumBits()); 
121 int n = GetNumFields(); 
122 for (int i = 0; i < n; i++) 
123 if (BitFields[i] != s.BitFields[i]) 
124 return false; 
125 
126 return true; 
127} 
128 
129 
130inline void tBitArray::ClearPadBits() 
131{ 
132 tAssert(BitFields); 
133 int numFields = GetNumFields(); 
134 int last = NumBits & 0x1F; 
135 uint32 maxFull = (last ? (1 << last) : 0) - 1; 
136 BitFields[numFields-1] &= maxFull; 
137} 
138