00001 #ifndef MYBITSTRING_HEADER_
00002 #define MYBITSTRING_HEADER_
00003
00010 #include <new>
00011 using std::nothrow;
00012
00013 #include "utils.H"
00014
00015
00016 class myBitString
00017 {
00018 private:
00019 template <class Tuint> class CmyBitMask
00020 {
00021 public:
00022 inline const Tuint operator[] (const unsigned int i) const
00023 {
00024 return static_cast<Tuint>(1)<<i;
00025 }
00026 };
00027 static const CmyBitMask<unsigned int> bitmask;
00028 protected:
00029 int size;
00030 unsigned int *data;
00031 inline void resize(int newsize)
00032 {
00033 if (newsize < size) return;
00034
00035 unsigned int *olddata = data;
00036 data = new(nothrow) unsigned int[newsize];
00037 if (!data)
00038 {
00039 cerr << "myBitString.resize(" << newsize << ") out of memory" << endl;
00040 exit(1);
00041 }
00042 for (int i=0; i<size; i++) data[i] = olddata[i];
00043 for (int i=size; i< newsize; i++) data[i]=0;
00044 size=newsize;
00045 if (olddata) delete [] olddata;
00046 }
00047 public:
00048 inline void optisize(void)
00049 {
00050 int i=size-1;
00051 while (i>=0 && data[i]==0) i--;
00052 if (i==size-1) return;
00053
00054 if (size<128)
00055 {
00056
00057
00058 #ifdef VERBOSE
00059 cout << "MyBitString::Optisize, no reallocate " << size << " to " << i+1 << endl;
00060 #endif
00061 size=i+1; return;
00062 }
00063
00064 #ifdef VERBOSE
00065 cout << "MyBitString::Optisize, reallocate" << size << " to " << i+1 << endl;
00066 #endif
00067 if (i<0) { delete [] data; data=NULL; size=0; return; }
00068
00069 size=i+1;
00070 unsigned int *olddata = data;
00071 data = new(nothrow) unsigned int[size];
00072 if (!data)
00073 {
00074 cerr << "myBitString.optisize(" << size << ") out of memory" << endl;
00075 exit(1);
00076 }
00077 for (; i>=0; --i) data[i] = olddata[i];
00078 if (olddata) delete [] olddata;
00079 }
00080
00081 inline myBitString(void) : size(0), data(NULL) { }
00082 inline ~myBitString(void)
00083 {
00084 if (data) delete [] data;
00085 data=NULL;
00086 size=0;
00087 }
00088 inline myBitString(const myBitString &rhs) : size(rhs.size), data(NULL)
00089 {
00090 data = new(nothrow) unsigned int[size];
00091 if (!data)
00092 {
00093 cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
00094 exit(1);
00095 }
00096 for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
00097 }
00098 inline myBitString& operator= (const myBitString &rhs)
00099 {
00100 if (data) delete [] data;
00101 size=rhs.size;
00102 data = new(nothrow) unsigned int[size];
00103 if (!data)
00104 {
00105 cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
00106 exit(1);
00107 }
00108 for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
00109 return *this;
00110 }
00111 inline int count(const bool b = true) const
00112 {
00113 int i;
00114 int z=0;
00115 if (!b) return -1;
00116 for (i=0; i<size; i++)
00117 {
00118 register unsigned int h = data[i];
00119 while (h)
00120 {
00121 if (h&1) z++;
00122 h>>=1;
00123 }
00124 }
00125 return z;
00126 }
00127 inline int first(const bool b = true) const
00128 {
00129 if (b)
00130 {
00131 int j=0;
00132 for (int i=0; i<size; i++)
00133 {
00134 register unsigned int h = data[i];
00135 while (h)
00136 {
00137 if (h&1)
00138 {
00139
00140 return 8*sizeof(unsigned int)*i+j;
00141 }
00142 h>>=1;
00143 j++;
00144 }
00145 }
00146
00147 return -1;
00148 }
00149 else
00150 {
00151 cerr << "myBitString.first(0) not implemented" << endl;
00152 exit(1);
00153 }
00154 }
00155 inline int next(int pos, const bool b = true) const
00156 {
00157 int i,j;
00158 if (pos<0) return first(b);
00159 pos++;
00160 if (b)
00161 {
00162 i=pos/(8*sizeof(unsigned int));
00163 j=pos%(8*sizeof(unsigned int));
00164 if (i>=size) return -1;
00165 register unsigned int h = data[i];
00166 h>>=j;
00167 if (h)
00168 {
00169 while (!(h&1))
00170 {
00171 h>>=1;
00172 pos++;
00173 }
00174 return pos;
00175 }
00176 else
00177 {
00178 j = 0;
00179 for (i++;i<size; i++)
00180 {
00181 h = data[i];
00182 while (h)
00183 {
00184 if (h&1) return 8*sizeof(unsigned int)*i+j;
00185 h>>=1;
00186 j++;
00187 }
00188 }
00189 }
00190 return -1;
00191 }
00192 else
00193 {
00194 cerr << "myBitString.next(0) not implemented" << endl;
00195 exit(1);
00196 }
00197 }
00198 inline int last(const bool b = true) const
00199 {
00200 int i;
00201
00202 if (b)
00203 {
00204 int j = 8*sizeof(unsigned int)-1;
00205 for (i=size-1; i>=0; i--)
00206 {
00207
00208 register unsigned int h = data[i];
00209 while (h)
00210 {
00211 if (h& bitmask[8*sizeof(unsigned int)-1])
00212 {
00213
00214 return 8*sizeof(unsigned int)*i+j;
00215 }
00216 h<<=1;
00217 j--;
00218 }
00219 }
00220
00221 return -1;
00222 }
00223 else
00224 {
00225 cerr << "myBitString.last(0) not implemented" << endl;
00226 exit(1);
00227 }
00228 }
00229 inline int prev(int pos, const bool b = true) const
00230 {
00231 int i,j;
00232
00233 if (pos>size*8*static_cast<int>(sizeof(unsigned int))) return last(b);
00234 if (pos<=0) return -1;
00235 pos--;
00236 if (b)
00237 {
00238 i=pos/(8*sizeof(unsigned int));
00239 j=pos%(8*sizeof(unsigned int));
00240 register unsigned int h = data[i];
00241 h<<=8*sizeof(unsigned int)-j-1;
00242 if (h)
00243 {
00244 while (!(h&bitmask[8*sizeof(unsigned int)-1]))
00245 {
00246 h<<=1;
00247 pos--;
00248 }
00249 return pos;
00250 }
00251 else
00252 {
00253 j = 8*sizeof(unsigned int)-1;
00254 for (i--;i>=0; i--)
00255 {
00256 h = data[i];
00257 while (h)
00258 {
00259 if (h&bitmask[8*sizeof(unsigned int)-1])
00260 return 8*sizeof(unsigned int)*i+j;
00261 h<<=1;
00262 j--;
00263 }
00264 }
00265 }
00266 return -1;
00267 }
00268 else
00269 {
00270 cerr << "myBitString.prev(0) not implemented" << endl;
00271 exit(1);
00272 }
00273 }
00274 inline void invert(const int pos)
00275 {
00276
00277 int i=pos/(8*sizeof(unsigned int));
00278 int j=pos%(8*sizeof(unsigned int));
00279
00280 if (i>=size) resize(i+1);
00281
00282 data[i] ^= bitmask[j];
00283 }
00284 inline bool test_and_invert(const int pos)
00285 {
00286
00287 int i=pos/(8*sizeof(unsigned int));
00288 int j=pos%(8*sizeof(unsigned int));
00289 if (i>=size) resize(i+1);
00290 const bool ret = (data[i] & bitmask[j]);
00291 data[i] ^= bitmask[j];
00292 return ret;
00293 }
00294 inline bool test(const int pos) const
00295 {
00296 int i=pos/(8*sizeof(unsigned int));
00297 int j=pos%(8*sizeof(unsigned int));
00298
00299 if (i>=size) return false;
00300
00301 return (data[i] & bitmask[j]);
00302 }
00303 inline void set(const int pos, const bool b = true)
00304 {
00305
00306 int i=pos/(8*sizeof(unsigned int));
00307 int j=pos%(8*sizeof(unsigned int));
00308
00309 if (i>=size)
00310 {
00311 if (b)
00312 resize(i+1);
00313 else
00314 return;
00315 }
00316 if (b)
00317 data[i] |= bitmask[j];
00318 else
00319 data[i] &= ~bitmask[j];
00320 }
00321 inline void _xor(const myBitString &s)
00322 {
00323 if (s.size>size)
00324 {
00325
00326 resize (s.size);
00327 }
00328 for (int i=0; i<s.size; i++)
00329 data[i] ^= s.data[i];
00330 }
00331 inline const myBitString& operator ^= (const myBitString &s)
00332 {
00333 _xor(s); return *this;
00334 }
00335
00336 inline void _and(const myBitString &s1, const myBitString &s2)
00337
00338 {
00339 int i = MIN(s1.size,s2.size)-1;
00340 if (i>=size)
00341 {
00342
00343
00344
00345
00346 if (data) delete [] data;
00347 size=i+1;
00348 data = new unsigned int[size];
00349
00350 }
00351 else
00352 {
00353 register int j=size-1;
00354 while (j>i) data[j--]=0;
00355 }
00356 for (; i>=0; --i)
00357 data[i] = s1.data[i] & s2.data[i];
00358 }
00359
00360 template<typename T> void test_and_add_carry(const myBitString &s2, T &CarryVec) const
00361
00362
00363
00364 {
00365 const int s = MIN(size,s2.size);
00366 const int Bits = 8*sizeof(unsigned int);
00367 for (int i=0; i<s; ++i)
00368 {
00369 register unsigned int h = data[i] & s2.data[i];
00370 register int j=0;
00371 while (h)
00372 {
00373 if (h&0xff)
00374 {
00375 CarryVec[Bits*i+j ]+=h&1;
00376 CarryVec[Bits*i+j+1]+=(h>>1)&1;
00377 CarryVec[Bits*i+j+2]+=(h>>2)&1;
00378 CarryVec[Bits*i+j+3]+=(h>>3)&1;
00379 CarryVec[Bits*i+j+4]+=(h>>4)&1;
00380 CarryVec[Bits*i+j+5]+=(h>>5)&1;
00381 CarryVec[Bits*i+j+6]+=(h>>6)&1;
00382 CarryVec[Bits*i+j+7]+=(h>>7)&1;
00383 }
00384 h>>=8;
00385 j+=8;
00386 }
00387 }
00388 }
00389
00390 };
00391
00392 #endif