CrystalSpace

Public API Reference

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

bitarray.h

00001 /*
00002     Copyright (C) 2000 by Andrew Kirmse
00003 
00004     This library is free software; you can redistribute it and/or
00005     modify it under the terms of the GNU Library General Public
00006     License as published by the Free Software Foundation; either
00007     version 2 of the License, or (at your option) any later version.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Library General Public License for more details.
00013 
00014     You should have received a copy of the GNU Library General Public
00015     License along with this library; if not, write to the Free
00016     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00017 */
00018 
00019 // A one-dimensional array of bits, similar to STL bitset.
00020 //
00021 // Copyright 2000 Andrew Kirmse.  All rights reserved.
00022 //
00023 // Permission is granted to use this code for any purpose, as long as this
00024 // copyright message remains intact.
00025 
00026 #ifndef __CS_BITARRAY_H__
00027 #define __CS_BITARRAY_H__
00028 
00029 #include <memory.h>
00030 
00032 class csBitArray
00033 {
00034 private:
00035   typedef unsigned long store_type;
00036   enum
00037   {
00038     bits_per_byte = 8,
00039     cell_size     = sizeof(store_type) * bits_per_byte
00040   };
00041 
00042   store_type *mpStore;
00043   store_type mSingleWord; // Use this buffer when mLength is 1
00044   unsigned mLength;       // Length of mpStore in units of store_type
00045   unsigned mNumBits;
00046 
00048   static unsigned GetIndex(unsigned bit_num)
00049   {
00050     return bit_num / cell_size;
00051   }
00052 
00053   static unsigned GetOffset(unsigned bit_num)
00054   {
00055     return bit_num % cell_size;
00056   }
00057 
00058   void Init(unsigned size)
00059   {
00060     mNumBits = size;
00061 
00062     if (size == 0)
00063       mLength = 0;
00064     else
00065       mLength = 1 + GetIndex(size - 1);
00066 
00067     // Avoid allocation if length is 1 (common case)
00068     if (mLength <= 1)
00069       mpStore = &mSingleWord;
00070     else
00071       mpStore = new store_type[mLength];
00072   }
00073 
00075   inline void Trim()
00076   {
00077     unsigned extra_bits = mNumBits % cell_size;
00078     if (mLength > 0 && extra_bits != 0)
00079       mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00080   }
00081 
00082 public:
00086   class BitProxy
00087   {
00088   private:
00089     csBitArray &mArray;
00090     unsigned  mPos;
00091   public:
00092     BitProxy(csBitArray &array, unsigned pos): mArray(array), mPos(pos)
00093     {}
00094 
00095     BitProxy &operator= (bool value)
00096     {
00097       mArray.Set(mPos, value);
00098       return *this;
00099     }
00100 
00101     BitProxy &operator= (const BitProxy &that)
00102     {
00103       mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
00104       return *this;
00105     }
00106 
00107     operator bool() const
00108     {
00109       return mArray.IsBitSet(mPos);
00110     }
00111 
00112     bool Flip()
00113     {
00114       mArray.FlipBit(mPos);
00115       return mArray.IsBitSet(mPos);
00116     }
00117   };
00118 
00119 
00120   friend class BitProxy;
00121 
00122   //
00123   // Constructors and destructor
00124   //
00125 
00127   explicit csBitArray(unsigned size)
00128   {
00129     Init(size);
00130     // Clear last bits
00131     Trim();
00132   }
00133 
00135   csBitArray(const csBitArray &that)
00136   {
00137     mpStore = 0;
00138     *this = that;
00139   }
00140 
00142   virtual ~csBitArray()
00143   {
00144     if (mLength > 1)
00145       delete mpStore;
00146   }
00147 
00148   //
00149   // Operators
00150   //
00151 
00153   csBitArray &operator=(const csBitArray &that)
00154   {
00155     if (this != &that)
00156     {
00157       if (mLength > 1)
00158         delete mpStore;
00159 
00160       Init(that.mNumBits);
00161 
00162       memcpy (mpStore, that.mpStore, mLength * sizeof(store_type));
00163     }
00164     return *this;
00165   }
00166 
00168   BitProxy operator[](unsigned pos)
00169   {
00170     CS_ASSERT (pos < mNumBits);
00171     return BitProxy(*this, pos);
00172   }
00173 
00175   const BitProxy operator[](unsigned pos) const
00176   {
00177     CS_ASSERT (pos < mNumBits);
00178     return BitProxy(CONST_CAST(csBitArray&,*this), pos);
00179   }
00180 
00182   bool operator==(const csBitArray &that) const
00183   {
00184     if (mNumBits != that.mNumBits)
00185       return false;
00186 
00187     for (unsigned i = 0; i < mLength; i++)
00188       if (mpStore[i] != that.mpStore[i])
00189         return false;
00190     return true;
00191   }
00192 
00194   bool operator!=(const csBitArray &that) const
00195   {
00196     return !(*this == that);
00197   }
00198 
00200   csBitArray &operator&=(const csBitArray &that)
00201   {
00202     CS_ASSERT (mNumBits == that.mNumBits);
00203     for (unsigned i = 0; i < mLength; i++)
00204       mpStore[i] &= that.mpStore[i];
00205     return *this;
00206   }
00207 
00209   csBitArray operator|=(const csBitArray &that)
00210   {
00211     CS_ASSERT (mNumBits == that.mNumBits);
00212     for (unsigned i = 0; i < mLength; i++)
00213       mpStore[i] |= that.mpStore[i];
00214     return *this;
00215   }
00216 
00218   csBitArray operator^=(const csBitArray &that)
00219   {
00220     CS_ASSERT (mNumBits == that.mNumBits);
00221     for (unsigned i = 0; i < mLength; i++)
00222       mpStore[i] ^= that.mpStore[i];
00223     return *this;
00224   }
00225 
00227   csBitArray operator~() const
00228   {
00229     return csBitArray(*this).FlipAllBits();
00230   }
00231 
00233   friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2)
00234   {
00235     return csBitArray(a1) &= a2;
00236   }
00237 
00239   friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2)
00240   {
00241     return csBitArray(a1) |= a2;
00242   }
00243 
00245   friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2)
00246   {
00247     return csBitArray(a1) ^= a2;
00248   }
00249 
00250   //
00251   // Plain English interface
00252   //
00253 
00255   void Clear()
00256   {
00257     memset (mpStore, 0, mLength * sizeof(store_type));
00258   }
00259 
00261   void SetBit(unsigned pos)
00262   {
00263     CS_ASSERT (pos < mNumBits);
00264     mpStore[GetIndex(pos)] |= 1 << GetOffset(pos);
00265   }
00266 
00268   void ClearBit(unsigned pos)
00269   {
00270     CS_ASSERT (pos < mNumBits);
00271     mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos));
00272   }
00273 
00275   void FlipBit(unsigned pos)
00276   {
00277     CS_ASSERT (pos < mNumBits);
00278     mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos);
00279   }
00280 
00282   void Set(unsigned pos, bool val)
00283   {
00284     val ? SetBit(pos) : ClearBit(pos);
00285   }
00286 
00288   bool IsBitSet(unsigned pos) const
00289   {
00290     CS_ASSERT (pos < mNumBits);
00291     return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00292   }
00293 
00295   bool AllBitsFalse() const
00296   {
00297     for (unsigned i=0; i < mLength; i++)
00298       if (mpStore[i] != 0)
00299         return false;
00300     return true;
00301   }
00302 
00304   csBitArray &FlipAllBits()
00305   {
00306     for (unsigned i=0; i < mLength; i++)
00307       mpStore[i] = ~mpStore[i];
00308 
00309     Trim();
00310     return *this;
00311   }
00312 
00314   store_type* GetArrayBits()
00315   {
00316     return mpStore;
00317   }
00318 
00323   unsigned GetSingleWord()
00324   {
00325     return mSingleWord;
00326   }
00327 
00332   void SetSingleWord(unsigned w)
00333   {
00334     mSingleWord=w;
00335   }
00336 };
00337 
00338 #endif // __CS_BITARRAY_H__

Generated for Crystal Space by doxygen 1.2.14