CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

bitarray.h

00001 // A one-dimensional array of bits, similar to STL bitset.
00002 //
00003 // Copyright 2000 Andrew Kirmse.  All rights reserved.
00004 //
00005 // Permission is granted to use this code for any purpose, as long as this
00006 // copyright message remains intact.
00007 
00008 #ifndef __CS_BITARRAY_H__
00009 #define __CS_BITARRAY_H__
00010 
00011 #include <memory.h>
00012 #include <assert.h>
00013 
00015 class csBitArray
00016 {
00017 private:
00018    
00019    typedef unsigned long store_type;
00020    enum
00021    {
00022       bits_per_byte = 8,
00023       cell_size     = sizeof(store_type) * bits_per_byte
00024    };
00025 
00026    store_type        *mpStore;  
00027    store_type         mSingleWord; // Use this buffer when mLength is 1
00028    unsigned           mLength;     // Length of mpStore in units of store_type
00029    unsigned           mNumBits;
00030 
00032    static unsigned GetIndex(unsigned bit_num)
00033    {
00034       return bit_num / cell_size;
00035    }
00036 
00037    static unsigned GetOffset(unsigned bit_num)
00038    {
00039       return bit_num % cell_size;
00040    }
00041 
00042    void Init(unsigned size)
00043    {
00044       mNumBits = size;
00045       
00046       if (size == 0)
00047          mLength = 0;
00048       else
00049          mLength = 1 + GetIndex(size - 1);
00050 
00051       // Avoid allocation if length is 1 (common case)
00052       if (mLength <= 1)
00053          mpStore = &mSingleWord;      
00054       else
00055          mpStore = new store_type[mLength];
00056    }
00057    
00059    inline void Trim()
00060    {
00061       unsigned extra_bits = mNumBits % cell_size;
00062       if (mLength > 0 && extra_bits != 0)
00063          mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00064    }
00065 
00066 public:
00067 
00071    class BitProxy
00072    {
00073    private:
00074       csBitArray &mArray;
00075       unsigned  mPos;
00076    public:
00077       BitProxy(csBitArray &array, unsigned pos):
00078             mArray(array), mPos(pos)
00079       {}
00080 
00081       BitProxy &operator=(bool value)
00082       {
00083          mArray.Set(mPos, value);
00084          return *this;
00085       }
00086 
00087       BitProxy &operator=(const BitProxy &that)
00088       {
00089          mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
00090          return *this;
00091       }
00092 
00093       operator bool() const
00094       {
00095          return mArray.IsBitSet(mPos);
00096       }
00097 
00098       bool Flip()
00099       {
00100          mArray.FlipBit(mPos);
00101          return mArray.IsBitSet(mPos);
00102       }
00103    };
00104 
00105    
00106    friend class BitProxy;
00107    
00108    //
00109    // Constructors and destructor
00110    //
00111    
00113    explicit csBitArray(unsigned size)
00114    {
00115       Init(size);
00116       // Clear last bits
00117       Trim();
00118    }
00119    
00121    csBitArray(const csBitArray &that)
00122    {
00123       mpStore = 0;
00124       *this = that;
00125    }
00126    
00128    virtual ~csBitArray()
00129    {
00130       if (mLength > 1)
00131          delete mpStore;
00132    }
00133 
00134    //
00135    // Operators
00136    //
00137 
00139    csBitArray &operator=(const csBitArray &that)
00140    {
00141       if (this != &that)
00142       {
00143          if (mLength > 1)
00144             delete mpStore;
00145 
00146          Init(that.mNumBits);
00147          
00148          memcpy(mpStore, that.mpStore, mLength * sizeof(store_type));
00149       }
00150       return *this;
00151    }
00152 
00154    BitProxy operator[](unsigned pos)
00155    {
00156       assert(pos < mNumBits);
00157       return BitProxy(*this, pos);
00158    }
00159 
00161    const BitProxy operator[](unsigned pos) const
00162    {
00163       assert(pos < mNumBits);
00164       return BitProxy(CONST_CAST(csBitArray&,*this), pos);
00165    }
00166    
00168    bool operator==(const csBitArray &that) const
00169    {
00170       if (mNumBits != that.mNumBits)
00171          return false;
00172       
00173       for (unsigned i = 0; i < mLength; i++)
00174          if (mpStore[i] != that.mpStore[i])
00175             return false;
00176       return true;
00177    }
00178 
00180    bool operator!=(const csBitArray &that) const
00181    {
00182       return !(*this == that);
00183    }
00184 
00186    csBitArray &operator&=(const csBitArray &that)
00187    {
00188       assert(mNumBits == that.mNumBits);
00189       for (unsigned i = 0; i < mLength; i++)
00190          mpStore[i] &= that.mpStore[i];
00191       return *this;
00192    }
00193 
00195    csBitArray operator|=(const csBitArray &that)
00196    {
00197       assert(mNumBits == that.mNumBits);
00198       for (unsigned i = 0; i < mLength; i++)
00199          mpStore[i] |= that.mpStore[i];
00200       return *this;
00201    }
00202 
00204    csBitArray operator^=(const csBitArray &that)
00205    {
00206       assert(mNumBits == that.mNumBits);
00207       for (unsigned i = 0; i < mLength; i++)
00208          mpStore[i] ^= that.mpStore[i];
00209       return *this;
00210    }
00211 
00213    csBitArray operator~() const
00214    {
00215       return csBitArray(*this).FlipAllBits();
00216    }
00217 
00219    friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2)
00220    {
00221       return csBitArray(a1) &= a2;
00222    }
00223 
00225    friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2)
00226    {
00227       return csBitArray(a1) |= a2;
00228    }
00229 
00231    friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2)
00232    {
00233       return csBitArray(a1) ^= a2;
00234    }
00235 
00236    //
00237    // Plain English interface
00238    //
00239    
00241    void Clear()
00242    {
00243       memset(mpStore, 0, mLength * sizeof(store_type));
00244    }
00245    
00247    void SetBit(unsigned pos)
00248    {
00249       assert(pos < mNumBits);
00250       mpStore[GetIndex(pos)] |= 1 << GetOffset(pos); 
00251    }
00252 
00254    void ClearBit(unsigned pos)
00255    { 
00256       assert(pos < mNumBits);
00257       mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos)); 
00258    }
00259 
00261    void FlipBit(unsigned pos) 
00262    { 
00263       assert(pos < mNumBits);
00264       mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos); 
00265    }
00266 
00268    void Set(unsigned pos, bool val)
00269    { 
00270       val ? SetBit(pos) : ClearBit(pos);
00271    }
00272 
00274    bool IsBitSet(unsigned pos) const
00275    {
00276       assert(pos < mNumBits);
00277       return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00278    }
00279 
00281    bool AllBitsFalse() const
00282    {
00283       for (unsigned i=0; i < mLength; i++)
00284          if (mpStore[i] != 0)
00285             return false;
00286       return true;
00287    }
00288 
00290    csBitArray &FlipAllBits()
00291    {
00292       for (unsigned i=0; i < mLength; i++)
00293          mpStore[i] = ~mpStore[i];
00294 
00295       Trim();
00296       return *this;
00297    }
00298    
00300    store_type* GetArrayBits()
00301    {
00302      return mpStore;
00303    }
00304 
00306    unsigned GetSingleWord()
00307    {
00308      return mSingleWord;
00309    }
00310 
00312    void SetSingleWord(unsigned w)
00313    {
00314      mSingleWord=w;
00315    }
00316 };
00317 
00318 #endif // __CS_BITARRAY_H__

Generated for Crystal Space by doxygen 1.2.14