nevrax.org : docs

00001 
+00007 /* Copyright, 2000 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "stdmisc.h"
+00027 
+00028 #include "nel/misc/bit_set.h"
+00029 
+00030 using namespace std;
+00031 
+00032 
+00033 namespace       NLMISC
+00034 {
+00035 
+00036 // must be defined elsewhere
+00037 #ifndef min
+00038 #define min(a,b)            (((a) < (b)) ? (a) : (b))
+00039 #endif
+00040 
+00041 
+00042 
+00043 // ***************************************************************************
+00044 CBitSet::CBitSet()
+00045 {
+00046         NumBits= 0;
+00047         MaskLast= 0;
+00048 }
+00049 CBitSet::CBitSet(uint numBits)
+00050 {
+00051         NumBits= 0;
+00052         MaskLast= 0;
+00053         resize(numBits);
+00054 }
+00055 CBitSet::CBitSet(const CBitSet &bs)
+00056 {
+00057         NumBits= bs.NumBits;
+00058         MaskLast= bs.MaskLast;
+00059         Array= bs.Array;
+00060 }
+00061 CBitSet::~CBitSet()
+00062 {
+00063 }
+00064 CBitSet &CBitSet::operator=(const CBitSet &bs)
+00065 {
+00066         NumBits= bs.NumBits;
+00067         MaskLast= bs.MaskLast;
+00068         Array= bs.Array;
+00069 
+00070         return *this;
+00071 }
+00072 
+00073 
+00074 // ***************************************************************************
+00075 void    CBitSet::clear()
+00076 {
+00077         Array.clear();
+00078         NumBits= 0;
+00079         MaskLast=0;
+00080 }
+00081 void    CBitSet::resize(uint numBits)
+00082 {
+00083         if(numBits==0)
+00084                 clear();
+00085 
+00086         NumBits= numBits;
+00087         Array.resize( (NumBits+NL_BITLEN-1) / NL_BITLEN );
+00088         uint    nLastBits= NumBits & (NL_BITLEN-1) ;
+00089         // Generate the mask for the last word.
+00090         if(nLastBits==0)
+00091                 MaskLast= ~((uint)0);
+00092         else
+00093                 MaskLast= (1<< nLastBits) -1;
+00094 
+00095         // reset to 0.
+00096         clearAll();
+00097 }
+00098 void    CBitSet::resizeNoReset(uint numBits, bool value)
+00099 {
+00100         if(numBits==0)
+00101                 clear();
+00102 
+00103         uint oldNum=NumBits;
+00104         NumBits= numBits;
+00105         Array.resize( (NumBits+NL_BITLEN-1) / NL_BITLEN );
+00106         uint    nLastBits= NumBits & (NL_BITLEN-1) ;
+00107         // Generate the mask for the last word.
+00108         if(nLastBits==0)
+00109                 MaskLast= ~((uint)0);
+00110         else
+00111                 MaskLast= (1<< nLastBits) -1;
+00112 
+00113         // Set new bit to value
+00114         for (uint i=oldNum; i<(uint)NumBits; i++)
+00115                 set(i, value);
+00116 }
+00117 uint    CBitSet::size() const
+00118 {
+00119         return NumBits;
+00120 }
+00121 void    CBitSet::setAll()
+00122 {
+00123         fill_n(Array.begin(), Array.size(), ~((uint)0));
+00124 
+00125         Array[Array.size()-1]&= MaskLast;
+00126 }
+00127 void    CBitSet::clearAll()
+00128 {
+00129         fill_n(Array.begin(), Array.size(), 0);
+00130 }
+00131 
+00132 
+00133 // ***************************************************************************
+00134 CBitSet CBitSet::operator~() const
+00135 {
+00136         CBitSet ret;
+00137 
+00138         ret= *this;
+00139         ret.flip();
+00140         return ret;
+00141 }
+00142 CBitSet CBitSet::operator&(const CBitSet &bs) const
+00143 {
+00144         CBitSet ret;
+00145 
+00146         ret= *this;
+00147         ret&=bs;
+00148         return ret;
+00149 }
+00150 CBitSet CBitSet::operator|(const CBitSet &bs) const
+00151 {
+00152         CBitSet ret;
+00153 
+00154         ret= *this;
+00155         ret|=bs;
+00156         return ret;
+00157 }
+00158 CBitSet CBitSet::operator^(const CBitSet &bs) const
+00159 {
+00160         CBitSet ret;
+00161 
+00162         ret= *this;
+00163         ret^=bs;
+00164         return ret;
+00165 }
+00166 
+00167 
+00168 // ***************************************************************************
+00169 void    CBitSet::flip()
+00170 {
+00171         if(NumBits==0)
+00172                 return;
+00173 
+00174         for(sint i=0;i<(sint)Array.size();i++)
+00175                 Array[i]= ~Array[i];
+00176 
+00177         Array[Array.size()-1]&= MaskLast;
+00178 }
+00179 CBitSet &CBitSet::operator&=(const CBitSet &bs)
+00180 {
+00181         if(NumBits==0)
+00182                 return *this;
+00183 
+00184         sint    minSize= min(Array.size(), bs.Array.size());
+00185         sint    i;
+00186         for(i=0;i<minSize;i++)
+00187                 Array[i]= Array[i] & bs.Array[i];
+00188         for(i=minSize;i<(sint)Array.size();i++)
+00189                 Array[i]=0;
+00190 
+00191         Array[Array.size()-1]&= MaskLast;
+00192 
+00193         return *this;
+00194 }
+00195 CBitSet &CBitSet::operator|=(const CBitSet &bs)
+00196 {
+00197         if(NumBits==0)
+00198                 return *this;
+00199 
+00200         sint    minSize= min(Array.size(), bs.Array.size());
+00201         for(sint i=0;i<minSize;i++)
+00202                 Array[i]= Array[i] | bs.Array[i];
+00203         // Do nothing for bits word from minSize to Array.size().
+00204 
+00205         Array[Array.size()-1]&= MaskLast;
+00206 
+00207         return *this;
+00208 }
+00209 CBitSet &CBitSet::operator^=(const CBitSet &bs)
+00210 {
+00211         if(NumBits==0)
+00212                 return *this;
+00213 
+00214         sint    minSize= min(Array.size(), bs.Array.size());
+00215         for(sint i=0;i<minSize;i++)
+00216                 Array[i]= Array[i] ^ bs.Array[i];
+00217         // Do nothing for bits word from minSize to Array.size().
+00218 
+00219         Array[Array.size()-1]&= MaskLast;
+00220 
+00221         return *this;
+00222 }
+00223 
+00224 
+00225 // ***************************************************************************
+00226 bool    CBitSet::operator==(const CBitSet &bs) const
+00227 {
+00228         if(NumBits!=bs.NumBits)
+00229                 return false;
+00230 
+00231         for(sint i=0;i<(sint)Array.size();i++)
+00232         {
+00233                 if(Array[i]!=bs.Array[i])
+00234                         return false;
+00235         }
+00236         return true;
+00237 }
+00238 bool    CBitSet::operator!=(const CBitSet &bs) const
+00239 {
+00240         return (!operator==(bs));
+00241 }
+00242 bool    CBitSet::compareRestrict(const CBitSet &bs) const
+00243 {
+00244         sint    n=min(NumBits, bs.NumBits);
+00245         if(n==0) return true;
+00246 
+00247         sint    nA= (n+NL_BITLEN-1) / NL_BITLEN;
+00248         uint    mask;
+00249 
+00250         uint    nLastBits= n & (NL_BITLEN-1) ;
+00251         // Generate the mask for the last common word.
+00252         if(nLastBits==0)
+00253                 mask= ~((uint)0);
+00254         else
+00255                 mask= (1<< nLastBits) -1;
+00256 
+00257 
+00258         for(sint i=0;i<nA-1;i++)
+00259         {
+00260                 if(Array[i]!=bs.Array[i])
+00261                         return false;
+00262         }
+00263         if( (Array[nA-1]&mask) != (bs.Array[nA-1]&mask) )
+00264                 return false;
+00265 
+00266 
+00267         return true;
+00268 }
+00269 bool    CBitSet::allSet()
+00270 {
+00271         if(NumBits==0)
+00272                 return false;
+00273         for(sint i=0;i<(sint)Array.size()-1;i++)
+00274         {
+00275                 if( Array[i]!= (~((uint)0)) )
+00276                         return false;
+00277         }
+00278         if( Array[Array.size()-1]!= MaskLast )
+00279                 return false;
+00280         return true;
+00281 }
+00282 bool    CBitSet::allCleared()
+00283 {
+00284         if(NumBits==0)
+00285                 return false;
+00286         for(sint i=0;i<(sint)Array.size();i++)
+00287         {
+00288                 if( Array[i]!= 0 )
+00289                         return false;
+00290         }
+00291         return true;
+00292 }
+00293 
+00294 
+00295 
+00296 void    CBitSet::serial(IStream &f)
+00297 {
+00298         (void)f.serialVersion(0);
+00299         uint32  sz=0;
+00300         vector<uint32>  array32;
+00301 
+00302         // Must support any size of uint.
+00303         if(f.isReading())
+00304         {
+00305                 f.serial(sz);
+00306                 resize(sz);
+00307 
+00308                 f.serialCont(array32);
+00309                 for(sint i=0;i<(sint)sz;i++)
+00310                 {
+00311                         uint32  a=array32[i/32];
+00312                         a&= 1<<(i&31);
+00313                         set(i, a!=0);
+00314                 }
+00315         }
+00316         else
+00317         {
+00318                 sz= size();
+00319                 f.serial(sz);
+00320 
+00321                 array32.resize(sz/32);
+00322                 fill_n(array32.begin(), array32.size(), 0);
+00323                 for(sint i=0;i<(sint)sz;i++)
+00324                 {
+00325                         if(get(i))
+00326                                 array32[i/32]|= 1<<(i&31);
+00327                 }
+00328                 f.serialCont(array32);
+00329         }
+00330 }
+00331 
+00332 
+00333 }
+00334 
+
bit_set.cpp
