bitVector.h

Classes:

class
Manage a vector of bits of arbitrary size.
Detailed Description

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _BITVECTOR_H_
 25#define _BITVECTOR_H_
 26
 27
 28/// Manage a vector of bits of arbitrary size.
 29class BitVector
 30{
 31   protected:
 32
 33      /// The array of bytes that stores our bits.
 34      U8* mBits;
 35
 36      /// The allocated size of the bit array.
 37      U32 mByteSize;
 38
 39      /// The size of the vector in bits. 
 40      U32 mSize;
 41
 42      /// Returns a size in bytes which is 32bit aligned
 43      /// and can hold all the requested bits.
 44      static U32 calcByteSize( const U32 numBits );
 45
 46      /// Internal function which resizes the bit array.
 47      void _resize( U32 sizeInBits, bool copyBits );
 48
 49      bool _test( const BitVector& vector, bool all ) const;
 50
 51   public:
 52
 53      /// Default constructor which creates an bit
 54      /// vector with a bit size of zero.
 55      BitVector();
 56      
 57      /// Constructs a bit vector with the desired size.
 58      /// @note The resulting vector is not cleared.
 59      BitVector( U32 sizeInBits );
 60
 61      /// Copy constructor
 62      BitVector( const BitVector &r);
 63      
 64      /// Destructor.
 65      ~BitVector();
 66
 67      /// @name Size Management
 68      /// @{
 69
 70      /// Return true if the bit vector is empty.
 71      bool empty() const { return ( mSize == 0 ); }
 72      
 73      /// Resizes the bit vector.
 74      /// @note The new bits in the vector are not cleared and 
 75      /// contain random garbage bits.
 76      void setSize( U32 sizeInBits );
 77
 78      /// Returns the size in bits.
 79      U32 getSize() const { return mSize; }
 80
 81      /// Returns the 32bit aligned size in bytes.
 82      U32 getByteSize() const { return mByteSize; }
 83
 84      /// Returns the bits.
 85      const U8* getBits() const { return mBits; }
 86      U8* getBits() { return mBits; }
 87
 88      /// @}
 89
 90      /// Copy the content of another bit vector.
 91      void copy( const BitVector &from );
 92
 93      /// Copy the contents of another bit vector
 94      BitVector& operator=( const BitVector &r);
 95
 96      /// @name Mutators
 97      /// Note that bits are specified by index, unlike BitSet32.
 98      /// @{
 99
100      /// Set the specified bit.
101      void set(U32 bit);
102
103      /// Set the specified bit on or off.
104      void set(U32 bit, bool on );
105
106      /// Set all the bits.
107      void set();
108
109      /// Clear the specified bit.
110      void clear(U32 bit);
111
112      /// Clear all the bits.
113      void clear();
114
115      /// Does an OR operation between BitVectors.
116      void combineOR( const BitVector &other );
117
118      /// Test that the specified bit is set.
119      bool test(U32 bit) const;
120
121      /// Test this vector's bits against all the corresponding bits
122      /// in @a vector and return true if any of the bits that are
123      /// set in @a vector are also set in this vector.
124      ///
125      /// @param vector Bit vector of the same size.
126      bool testAny( const BitVector& vector ) const { return _test( vector, false ); }
127
128      /// Test this vector's bits against all the corresponding bits
129      /// in @a vector and return true if all of the bits that are
130      /// set in @a vector are also set in this vector.
131      ///
132      /// @param vector Bit vector of the same size.
133      bool testAll( const BitVector& vector ) const { return _test( vector, true ); }
134
135      /// Return true if all bits are set.
136      bool testAll() const;
137      
138      /// Return true if all bits are clear.
139      bool testAllClear() const;
140
141      /// @}
142};
143
144inline BitVector::BitVector()
145{
146   mBits     = NULL;
147   mByteSize = 0;
148   mSize = 0;
149}
150
151
152inline BitVector::BitVector( U32 sizeInBits )
153{
154   mBits     = NULL;
155   mByteSize = 0;
156   mSize = 0;
157   setSize( sizeInBits );
158}
159
160inline BitVector::BitVector( const BitVector &r )
161{
162   mBits     = NULL;
163   mByteSize = 0;
164   mSize = 0;
165   copy(r);
166}
167
168inline BitVector::~BitVector()
169{
170   delete [] mBits;
171   mBits = NULL;
172   mByteSize = 0;
173   mSize = 0;
174}
175
176inline U32 BitVector::calcByteSize( U32 numBits )
177{
178   // Make sure that we are 32 bit aligned
179   return (((numBits + 0x7) >> 3) + 0x3) & ~0x3;
180}
181
182inline void BitVector::setSize( const U32 sizeInBits )
183{
184   _resize( sizeInBits, true );
185}
186
187inline void BitVector::clear()
188{
189   if (mSize != 0)
190      dMemset( mBits, 0x00, getByteSize() );
191}
192
193inline void BitVector::copy( const BitVector &from )
194{
195   _resize( from.getSize(), false );
196   if (mSize != 0)
197      dMemcpy( mBits, from.getBits(), getByteSize() );
198}
199
200inline BitVector& BitVector::operator=( const BitVector &r)
201{
202   copy(r);
203   return *this;
204}
205
206inline void BitVector::set()
207{
208   if (mSize != 0)
209      dMemset(mBits, 0xFF, getByteSize() );
210}
211
212inline void BitVector::set(U32 bit)
213{
214   AssertFatal(bit < mSize, "BitVector::set - Error, out of range bit!");
215
216   mBits[bit >> 3] |= U8(1 << (bit & 0x7));
217}
218
219inline void BitVector::set(U32 bit, bool on )
220{
221   AssertFatal(bit < mSize, "BitVector::set - Error, out of range bit!");
222
223   if ( on )
224      mBits[bit >> 3] |= U8(1 << (bit & 0x7));
225   else
226      mBits[bit >> 3] &= U8(~(1 << (bit & 0x7)));
227}
228
229inline void BitVector::clear(U32 bit)
230{
231   AssertFatal(bit < mSize, "BitVector::clear - Error, out of range bit!");
232   mBits[bit >> 3] &= U8(~(1 << (bit & 0x7)));
233}
234
235inline bool BitVector::test(U32 bit) const
236{
237   AssertFatal(bit < mSize, "BitVector::test - Error, out of range bit!");
238   return (mBits[bit >> 3] & U8(1 << (bit & 0x7))) != 0;
239}
240
241#endif //_BITVECTOR_H_
242