#ifndef MYBITSTRING_HEADER_
#define MYBITSTRING_HEADER_
/*! @file
* @brief
* generic implementation of an array class of bits (in dense representation)
*/
#include <new>
using std::nothrow;
#include "utils.H"
class myBitString
{
private:
template <class Tuint> class CmyBitMask
{
public:
inline const Tuint operator[] (const unsigned int i) const
{
return static_cast<Tuint>(1)<<i;
}
};
static const CmyBitMask<unsigned int> bitmask;
protected:
int size;
unsigned int *data;
inline void resize(int newsize)
{
if (newsize < size) return;
//cerr << "Resize " << size << " to " << newsize << endl;
unsigned int *olddata = data;
data = new(nothrow) unsigned int[newsize];
if (!data)
{
cerr << "myBitString.resize(" << newsize << ") out of memory" << endl;
exit(1);
}
for (int i=0; i<size; i++) data[i] = olddata[i];
for (int i=size; i< newsize; i++) data[i]=0;
size=newsize;
if (olddata) delete [] olddata;
}
public:
inline void optisize(void)
{
int i=size-1;
while (i>=0 && data[i]==0) i--;
if (i==size-1) return; // nothing to do...
if (size<128)
{
// to avoid heap pollution for small sizes, simply decrease
// the size without reallocating any heap memory
#ifdef VERBOSE
cout << "MyBitString::Optisize, no reallocate " << size << " to " << i+1 << endl;
#endif
size=i+1; return;
}
#ifdef VERBOSE
cout << "MyBitString::Optisize, reallocate" << size << " to " << i+1 << endl;
#endif
if (i<0) { delete [] data; data=NULL; size=0; return; } // now empty
size=i+1; // new size
unsigned int *olddata = data;
data = new(nothrow) unsigned int[size];
if (!data)
{
cerr << "myBitString.optisize(" << size << ") out of memory" << endl;
exit(1);
}
for (; i>=0; --i) data[i] = olddata[i];
if (olddata) delete [] olddata;
}
inline myBitString(void) : size(0), data(NULL) { }
inline ~myBitString(void)
{
if (data) delete [] data;
data=NULL;
size=0;
}
inline myBitString(const myBitString &rhs) : size(rhs.size), data(NULL)
{
data = new(nothrow) unsigned int[size];
if (!data)
{
cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
exit(1);
}
for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
}
inline myBitString& operator= (const myBitString &rhs)
{
if (data) delete [] data;
size=rhs.size;
data = new(nothrow) unsigned int[size];
if (!data)
{
cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
exit(1);
}
for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
return *this;
}
inline int count(const bool b = true) const
{
int i;
int z=0;
if (!b) return -1;
for (i=0; i<size; i++)
{
register unsigned int h = data[i];
while (h)
{
if (h&1) z++;
h>>=1;
}
}
return z;
}
inline int first(const bool b = true) const
{
if (b)
{
int j=0;
for (int i=0; i<size; i++)
{
register unsigned int h = data[i];
while (h)
{
if (h&1)
{
//cerr << "first(1)=" << 8*sizeof(unsigned int)*i+j << endl;
return 8*sizeof(unsigned int)*i+j;
}
h>>=1;
j++;
}
}
//cerr << "first(1)=-1" << endl;
return -1;
}
else
{
cerr << "myBitString.first(0) not implemented" << endl;
exit(1);
}
}
inline int next(int pos, const bool b = true) const
{
int i,j;
if (pos<0) return first(b);
pos++;
if (b)
{
i=pos/(8*sizeof(unsigned int));
j=pos%(8*sizeof(unsigned int));
if (i>=size) return -1;
register unsigned int h = data[i];
h>>=j;
if (h)
{
while (!(h&1))
{
h>>=1;
pos++;
}
return pos;
}
else
{
j = 0;
for (i++;i<size; i++)
{
h = data[i];
while (h)
{
if (h&1) return 8*sizeof(unsigned int)*i+j;
h>>=1;
j++;
}
}
}
return -1;
}
else
{
cerr << "myBitString.next(0) not implemented" << endl;
exit(1);
}
}
inline int last(const bool b = true) const
{
int i;
if (b)
{
int j = 8*sizeof(unsigned int)-1;
for (i=size-1; i>=0; i--)
{
//cerr << "i=" << i << endl;
register unsigned int h = data[i];
while (h)
{
if (h& bitmask[8*sizeof(unsigned int)-1])
{
//cerr << "last(1)=" << 8*sizeof(unsigned int)*i+j << endl;
return 8*sizeof(unsigned int)*i+j;
}
h<<=1;
j--;
}
}
//cerr << "last(1)=-1"<<endl;
return -1;
}
else
{
cerr << "myBitString.last(0) not implemented" << endl;
exit(1);
}
}
inline int prev(int pos, const bool b = true) const
{
int i,j;
if (pos>size*8*static_cast<int>(sizeof(unsigned int))) return last(b);
if (pos<=0) return -1;
pos--;
if (b)
{
i=pos/(8*sizeof(unsigned int));
j=pos%(8*sizeof(unsigned int));
register unsigned int h = data[i];
h<<=8*sizeof(unsigned int)-j-1;
if (h)
{
while (!(h&bitmask[8*sizeof(unsigned int)-1]))
{
h<<=1;
pos--;
}
return pos;
}
else
{
j = 8*sizeof(unsigned int)-1;
for (i--;i>=0; i--)
{
h = data[i];
while (h)
{
if (h&bitmask[8*sizeof(unsigned int)-1])
return 8*sizeof(unsigned int)*i+j;
h<<=1;
j--;
}
}
}
return -1;
}
else
{
cerr << "myBitString.prev(0) not implemented" << endl;
exit(1);
}
}
inline void invert(const int pos)
{
//cerr << "invert("<<pos<<")"<<endl;
int i=pos/(8*sizeof(unsigned int));
int j=pos%(8*sizeof(unsigned int));
if (i>=size) resize(i+1);
data[i] ^= bitmask[j];
}
inline bool test_and_invert(const int pos)
{
//cerr << "test_and_invert("<<pos<<")"<<endl;
int i=pos/(8*sizeof(unsigned int));
int j=pos%(8*sizeof(unsigned int));
if (i>=size) resize(i+1);
const bool ret = (data[i] & bitmask[j]);
data[i] ^= bitmask[j];
return ret;
}
inline bool test(const int pos) const
{
int i=pos/(8*sizeof(unsigned int));
int j=pos%(8*sizeof(unsigned int));
if (i>=size) return false;
//cerr << "test("<<pos<<")=" << (data[i] & bitmask[j]) << endl;
return (data[i] & bitmask[j]);
}
inline void set(const int pos, const bool b = true)
{
//cerr << "set("<<pos<< "," << b << ")" << endl;
int i=pos/(8*sizeof(unsigned int));
int j=pos%(8*sizeof(unsigned int));
if (i>=size)
{
if (b)
resize(i+1);
else
return;
}
if (b)
data[i] |= bitmask[j];
else
data[i] &= ~bitmask[j];
}
inline void _xor(const myBitString &s)
{
if (s.size>size)
{
//cerr << "myBitString.xor calls resize" << endl;
resize (s.size);
}
for (int i=0; i<s.size; i++)
data[i] ^= s.data[i];
}
inline const myBitString& operator ^= (const myBitString &s)
{
_xor(s); return *this;
}
inline void _and(const myBitString &s1, const myBitString &s2)
// der eigene Bitstring wird durch s1&s2 (komponentenweise) überschrieben
{
int i = MIN(s1.size,s2.size)-1;
if (i>=size) // <-> i+1>size
{
// CAUTION: (this == &s1 || this == &s2) -> BOOM!!
// But since (this == &s1 || this == &s2) also
// implies MIN(s1.size,s2.size)-1 < size, we can safely
// destroy the array...
if (data) delete [] data; // alten Vektor löschen
size=i+1;
data = new unsigned int[size];
// Initialisieren der Bits des neuen Vektors nicht notwendig (geschieht ja gleich durch das and)
}
else
{
register int j=size-1;
while (j>i) data[j--]=0; // überschüssige Bits im Resultat löschen
}
for (; i>=0; --i)
data[i] = s1.data[i] & s2.data[i];
}
template<typename T> void test_and_add_carry(const myBitString &s2, T &CarryVec) const
// temporäre (komponentenweise) AND-Verknüpfung den eigenen Bitstrings
// mit s2; den Vektor CarryVector an den korrespondierenden gesetzten
// Positionen inkrementieren.
{
const int s = MIN(size,s2.size);
const int Bits = 8*sizeof(unsigned int);
for (int i=0; i<s; ++i)
{
register unsigned int h = data[i] & s2.data[i];
register int j=0;
while (h)
{
if (h&0xff)
{
CarryVec[Bits*i+j ]+=h&1;
CarryVec[Bits*i+j+1]+=(h>>1)&1;
CarryVec[Bits*i+j+2]+=(h>>2)&1;
CarryVec[Bits*i+j+3]+=(h>>3)&1;
CarryVec[Bits*i+j+4]+=(h>>4)&1;
CarryVec[Bits*i+j+5]+=(h>>5)&1;
CarryVec[Bits*i+j+6]+=(h>>6)&1;
CarryVec[Bits*i+j+7]+=(h>>7)&1;
}
h>>=8;
j+=8;
}
}
}
};
#endif