bitstring.h

Go to the documentation of this file.

 
#ifndef BITSRING_H
#define BITSRING_H
 
#include <bitset>
#include <assert.h> //for CHAR_BIT
#include <limits.h>
#include <string.h>
#include <iostream>
 
#ifdef _GLIBCPP_BITSET_BITS_PER_WORD
#define BITS_PER_WORD _GLIBCPP_BITSET_BITS_PER_WORD
#else
#define BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long))
#endif
 
#ifndef _GLIBCPP_BITSET_WORDS
#define BITSET_WORDS(__n) \
((__n) < 1 ? 1 : ((__n) + BITS_PER_WORD - 1)/BITS_PER_WORD)
#else
#define BITSET_WORDS(__n) _GLIBCPP_BITSET_WORDS(__n)
#endif
 
 
#define MASK ULLONG_MAX
 
class bitstring {
  
public:
  
  typedef unsigned long _ul;
  
  class reference
  {
    friend class bitstring;
    
    _ul *_word;
    size_t _bitpos;
    
    // left undefined
    reference();
    
  public:
    reference(bitstring& bs, size_t pos)
    {
      _word = bs.getword_atPos( pos );
      _bitpos = pos % BITS_PER_WORD;
    }
    
    ~reference()
    { }
    
    // For b[i] = x;
    reference& operator=(bool x)
    {
      if (x)
        *_word |= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
      else
        *_word &= ~( 1UL << ( _bitpos % BITS_PER_WORD ) );
      return *this;
    }
    
    // For b[i] = b[j];
    reference& operator=(const reference& j)
    {
      if ((*(j._word) & ( 1UL << ( j._bitpos % BITS_PER_WORD ) ) ))
        *_word |= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
      else
        *_word &= ~( 1UL << ( _bitpos % BITS_PER_WORD ) );
      return *this;
    }
    
    // Flips the bit
    bool operator~() const
    { return (*(_word) & ( 1UL << ( _bitpos % BITS_PER_WORD ) ) ) == 0; }
    
    // For __x = b[i];
    operator bool() const
    { return (*(_word) & ( 1UL << ( _bitpos % BITS_PER_WORD ) ) ) != 0; }
    
    // For b[i].flip();
    reference& flip()
    {
      *_word ^= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
      return *this;
    }
  };
  
  friend class reference;
  
  bitstring () : _size(0), _words(0), _data(0) {}
 
  bitstring (size_t length) 
  : _size(length), _words( BITSET_WORDS(length) ), _data(0)
  {
    _data = new _ul [_words];
    memset(_data, 0, _words * sizeof(_ul));
  }
  
  bitstring (const bitstring& b) 
  : _size(b._size), _words(b._words), _data(0)
  {
    _data = new _ul [_words];
    memcpy(_data, b._data, _words * sizeof(_ul));
  }
  
  ~bitstring () {if(_data != NULL) delete [] _data;}
  
 
  void reset(size_t length)
  {
    _size = length;
 
    _words = BITSET_WORDS(length);
 
    if(_data) delete [] _data;
 
    _data = new _ul [_words];
    memset(_data, 0UL, _words * sizeof(_ul));
  }
 
  void reset ( )
  { for(unsigned int i = 0; i < _words; i++) _data[i] = 0UL; }
 
  _ul* getword_atPos (size_t pos) const
  { return &_data[ pos / BITS_PER_WORD ]; }
  
  _ul* getword_atIdx (size_t index) const
  { return &_data[ index ]; }
  
  size_t size     ( ) const {return _size;}
  
  size_t nb_words ( ) const {return _words;}
  
  bool at (size_t word, unsigned long bitmask) const
  {
    return bool( _data[ word ] & bitmask );
  }
 
  reference operator[] (size_t pos)
  { return reference(*this, pos); }
  
  bool operator[] (size_t n) const
  { return bool( _data[ n / BITS_PER_WORD ] & ( 1UL << ( n % BITS_PER_WORD ) ) ); }
  
  bitstring& operator= (const bitstring& b)
  {
    _size = b._size;
    if (_words != b._words) {
      _words = b._words;
      if(_data != NULL) delete [] _data;
      _data = new _ul [_words];
    }
    memcpy(_data, b._data, _words * sizeof(_ul));
    return *this;
  }
  
  bitstring& operator&= (const bitstring& x)
  {
    for (size_t i = 0; i < _words; i++)
      _data[i] &= x._data[i];
    return *this;
  }
  
  bitstring& operator|= (const bitstring& x)
  {
    for (size_t i = 0; i < _words; i++)
      _data[i] |= x._data[i];
    return *this;
  }
  
  bitstring& operator^= (const bitstring& x)
  {
    for (size_t i = 0; i < _words; i++)
      _data[i] ^= x._data[i];
    return *this;
  }
  
  bitstring operator~ (void)
  {
    for (size_t i = 0; i < _words; i++)
      _data[i] = ~(_data[i]);
    return *this;
  }
  
  bitstring operator& (const bitstring& x)
  {
    bitstring result(*this);
    result &= x;
    return result;
  }
  
  bitstring operator| (const bitstring& x)
  {
    bitstring result(*this);
    result |= x;
    return result;
  }
  
  bitstring operator^ (const bitstring& x)
  {
    bitstring result(*this);
    result ^= x;
    return result;
  }
  
#ifdef __POPCNT__
  unsigned int local_popcountl (_ul wd) const
  {
    return (unsigned int) __builtin_popcountl(wd);
  }
#else
  unsigned int local_popcountl (_ul wd) const
  {
    unsigned char* c = (unsigned char*)&wd;
    unsigned short cnt = 0;
 
    for(unsigned int i = 0; i < sizeof(_ul); i++)
      cnt += _bit_count[ (unsigned int)c[i] ];
 
    return (unsigned int) cnt;
  }
#endif
  
  unsigned int count ( ) 
  {
    unsigned int cnt = 0;
    
    for(size_t i = 0; i < _words; i++)
      cnt += local_popcountl(_data[i]);
    
    return cnt;
  }
  
  unsigned int count (size_t from, size_t to)
  {
      assert(from < to && to <= _size);
 
      unsigned int cnt = 0;
      size_t start_w = from / BITS_PER_WORD;
      size_t end_w   = to   / BITS_PER_WORD;
      size_t start_l = from % BITS_PER_WORD;
      size_t end_l   = to   % BITS_PER_WORD;
 
      if (start_w == end_w) {
          _ul mask = (MASK << start_l) & (MASK >> (BITS_PER_WORD - end_l));
          return local_popcountl( _ul(_data[start_w] & mask) );
      }
 
      // first partial word
      cnt += local_popcountl(_data[start_w] & (MASK << start_l));
 
      // full words in between
      for (size_t i = start_w + 1; i < end_w; ++i)
          cnt += local_popcountl(_data[i]);
 
      // last partial word
      if (end_l > 0)
          cnt += local_popcountl(_data[end_w] & (MASK >> (BITS_PER_WORD - end_l)));
 
      return cnt;
  }
 
  unsigned int count_and (const bitstring& mask) const
  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl(_data[i] & mask._data[i]);
    return cnt;
  }
 
  unsigned int count_xor (const bitstring& other) const
  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl(_data[i] ^ other._data[i]);
    return cnt;
  }
 
  unsigned int count_xor_and (const bitstring& other, const bitstring& mask) const
  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl((_data[i] ^ other._data[i]) & mask._data[i]);
    return cnt;
  }
 
  unsigned int count_and_and (const bitstring& other, const bitstring& mask) const
  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl((_data[i] & other._data[i]) & mask._data[i]);
    return cnt;
  }
 
  void set (size_t n) {_data[n / BITS_PER_WORD] |= (1UL << (n % BITS_PER_WORD));}
  
  void set (size_t n, bool x) {
    if (x)
      _data[n / BITS_PER_WORD] |= ( 1UL << ( n % BITS_PER_WORD ) );
    else
      _data[n / BITS_PER_WORD]  &= ~( 1UL << ( n % BITS_PER_WORD ) );
  }
 
  void flip (size_t n) {_data[n / BITS_PER_WORD] ^= (1UL << (n % BITS_PER_WORD));}
  
  void set_data (_ul* srce, size_t nbwrd)
  { 
    //    if(nbwrd != _words) { 
    //      std::cerr<<"bitstring::set_data: different sizes in memcpy!!\n";
    //      exit(1);
    //      }
    assert(nbwrd == _words);
    memcpy(_data, srce, nbwrd * sizeof(_ul));
  }
  
  void copy (const bitstring& b) 
  { memcpy(_data, b._data, _words * sizeof(_ul)); }
  
  void copy (const bitstring& b, size_t word_pos)
  { _data[ word_pos ] = b._data[ word_pos ]; }
  
  void copy (const bitstring& b, size_t from, size_t to)
  {
    assert(to <= _size);
    
    if(to != from) { // only if we do have something to copy
 
      size_t start_w, end_w, start_l, end_l;
      _ul mask, tmpl;
 
      start_w = from / BITS_PER_WORD;
      end_w = to / BITS_PER_WORD;
 
      start_l = from % BITS_PER_WORD;
      end_l = to % BITS_PER_WORD;
 
      if(start_w != end_w) {
        //copy wihtin first word:
        mask =  (MASK << start_l);
 
        _data[ start_w ]   &= ~mask;
        tmpl = b._data[ start_w ] & mask;
 
        _data[ start_w ] |= tmpl;
 
        //copy words in-between:
        size_t k = start_w + 1;
 
        memcpy(&_data[k], &b._data[k], (end_w - k)*sizeof(_ul));
 
        //copy within last word; skip when 'to' is word-aligned (end_l == 0),
        //since end_w then sits one past the last valid word and there's
        //nothing left to copy beyond what the memcpy above already did.
        if (end_l != 0) {
          mask =  (MASK >> (BITS_PER_WORD - end_l) );
 
          _data[ end_w ]   &= ~mask;
          tmpl = b._data[ end_w ] & mask;
 
          _data[ end_w ] |= tmpl;
        }
 
      } else {
        //bits to copy are within a word:
        mask =  (MASK << start_l) & (MASK >> (BITS_PER_WORD - end_l) );
 
        _data[ start_w ] &= ~mask;
        tmpl = b._data[ start_w ] & mask;
 
        _data[ start_w ] |= tmpl;
 
      }
    }
  }
  
  std::string to_string() const
  {
    const char one = '1';
    std::string result;
 
    result.assign(_size, '0');
 
    for(size_t i = 0; i < _size; ++i) {
      if(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ))
        result[i] = one;
    }
 
    return result;
  }
 
  std::string to_string(size_t from, size_t to) const
  {
    assert(from < to && to < _size+1);
 
    const char one = '1';
 
    size_t len = to - from;
 
    std::string result;
 
    result.assign(len, '0');
 
    for(size_t i = from, s = 0; i < to && s < len; ++i, ++s) {
      if(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ))
        result[s] = one;
    }
    return result;
  }
 
  void print (size_t from, size_t to) const
  {
    assert(from < to && to < _size+1);
    for(unsigned int i = from; i < to; ++i)
      std::cout<< (bool)(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ));
    std::cout<<std::endl;
  }
 
  void print() const
  {
    for(unsigned int i = 0; i < _size; ++i)
      std::cout<< (bool)(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ));
    std::cout<<std::endl;
  }
 
private:
  size_t _size;
  
  size_t _words;
  
  _ul *_data;
  
  
#ifndef __POPCNT__
  static unsigned char _bit_count[256];
#endif
  
};
 
#endif