myBitString_generic.H

Go to the documentation of this file.

#ifndef MYBITSTRING_HEADER_
#define MYBITSTRING_HEADER_

#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

---