bitsetvector.hh

Go to the documentation of this file.

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
#ifndef DUNE_BLOCK_BITFIELD_HH
#define DUNE_BLOCK_BITFIELD_HH
 
#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>
 
#include <dune/common/boundschecking.hh>
#include <dune/common/genericiterator.hh>
#include <dune/common/exceptions.hh>
 
namespace Dune {
 
  template <int block_size, class Alloc> class BitSetVector;
  template <int block_size, class Alloc> class BitSetVectorReference;
 
  template <int block_size, class Alloc>
  class BitSetVectorConstReference
  {
  protected:
 
    typedef Dune::BitSetVector<block_size, Alloc> BitSetVector;
    friend class Dune::BitSetVector<block_size, Alloc>;
 
    BitSetVectorConstReference(const BitSetVector& blockBitField_, int block_number_) :
      blockBitField(blockBitField_),
      block_number(block_number_)
    {
      DUNE_ASSERT_BOUNDS(blockBitField_.size() > static_cast<size_t>(block_number_));
    }
 
    BitSetVectorConstReference& operator=(const BitSetVectorConstReference & b);
 
  public:
 
    typedef std::bitset<block_size> bitset;
 
    // bitset interface typedefs
    typedef typename std::vector<bool, Alloc>::const_reference reference;
    typedef typename std::vector<bool, Alloc>::const_reference const_reference;
    typedef size_t size_type;
 
    bitset operator<<(size_type n) const
    {
      bitset b = *this;
      b <<= n;
      return b;
    }
 
    bitset operator>>(size_type n) const
    {
      bitset b = *this;
      b >>= n;
      return b;
    }
 
    bitset operator~() const
    {
      bitset b = *this;
      b.flip();
      return b;
    }
 
    size_type size() const
    {
      return block_size;
    }
 
    size_type count() const
    {
      size_type n = 0;
      for(size_type i=0; i<block_size; ++i)
        n += getBit(i);
      return n;
    }
 
    bool any() const
    {
      return count();
    }
 
    bool none() const
    {
      return ! any();
    }
 
    bool all() const
    {
      for(size_type i=0; i<block_size; ++i)
        if(not test(i))
          return false;
      return true;
    }
 
    bool test(size_type n) const
    {
      return getBit(n);
    }
 
    const_reference operator[](size_type i) const
    {
      return getBit(i);
    }
 
    operator bitset() const
    {
      return blockBitField.getRepr(block_number);
    }
 
    bool operator== (const bitset& bs) const
    {
      return equals(bs);
    }
 
    bool operator== (const BitSetVectorConstReference& bs) const
    {
      return equals(bs);
    }
 
    bool operator!= (const bitset& bs) const
    {
      return ! equals(bs);
    }
 
    bool operator!= (const BitSetVectorConstReference& bs) const
    {
      return ! equals(bs);
    }
 
    friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
    {
      s << "(";
      for(int i=0; i<block_size; ++i)
        s << v[i];
      s << ")";
      return s;
    }
 
  protected:
    const BitSetVector& blockBitField;
    int block_number;
 
    const_reference getBit(size_type i) const
    {
      return blockBitField.getBit(block_number,i);
    }
 
    template<class BS>
    bool equals(const BS & bs) const
    {
      bool eq = true;
      for(int i=0; i<block_size; ++i)
        eq &= (getBit(i) == bs[i]);
      return eq;
    }
 
  private:
    void operator & () = delete;
 
    friend class BitSetVectorReference<block_size, Alloc>;
  };
 
  template <int block_size, class Alloc>
  class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
  {
  protected:
 
    typedef Dune::BitSetVector<block_size, Alloc> BitSetVector;
    friend class Dune::BitSetVector<block_size, Alloc>;
 
    typedef Dune::BitSetVectorConstReference<block_size,Alloc> BitSetVectorConstReference;
 
    BitSetVectorReference(BitSetVector& blockBitField_, int block_number_) :
      BitSetVectorConstReference(blockBitField_, block_number_),
      blockBitField(blockBitField_)
    {}
 
  public:
    typedef std::bitset<block_size> bitset;
 
    typedef typename std::vector<bool, Alloc>::reference reference;
    typedef typename std::vector<bool, Alloc>::const_reference const_reference;
 
    typedef size_t size_type;
 
    BitSetVectorReference& operator=(bool b)
    {
      for(int i=0; i<block_size; ++i)
        getBit(i) = b;
      return (*this);
    }
 
    BitSetVectorReference& operator=(const bitset & b)
    {
      for(int i=0; i<block_size; ++i)
        getBit(i) = b.test(i);
      return (*this);
    }
 
    BitSetVectorReference& operator=(const BitSetVectorConstReference & b)
    {
      for(int i=0; i<block_size; ++i)
        getBit(i) = b.test(i);
      return (*this);
    }
 
    BitSetVectorReference& operator=(const BitSetVectorReference & b)
    {
      for(int i=0; i<block_size; ++i)
        getBit(i) = b.test(i);
      return (*this);
    }
 
    BitSetVectorReference& operator&=(const bitset& x)
    {
      for (size_type i=0; i<block_size; i++)
        getBit(i) = (test(i) & x.test(i));
      return *this;
    }
 
    BitSetVectorReference& operator&=(const BitSetVectorConstReference& x)
    {
      for (size_type i=0; i<block_size; i++)
        getBit(i) = (test(i) & x.test(i));
      return *this;
    }
 
    BitSetVectorReference& operator|=(const bitset& x)
    {
      for (size_type i=0; i<block_size; i++)
        getBit(i) = (test(i) | x.test(i));
      return *this;
    }
 
    BitSetVectorReference& operator|=(const BitSetVectorConstReference& x)
    {
      for (size_type i=0; i<block_size; i++)
        getBit(i) = (test(i) | x.test(i));
      return *this;
    }
 
    BitSetVectorReference& operator^=(const bitset& x)
    {
      for (size_type i=0; i<block_size; i++)
        getBit(i) = (test(i) ^ x.test(i));
      return *this;
    }
 
  private:
 
    // For some reason, the following variant of operator^= triggers an ICE or a hanging
    // compiler on Debian 9 with GCC 6.3 and full optimizations enabled (-O3).
    // The only way to reliably avoid the issue is by making sure that the compiler does not
    // see the XOR in the context of the function, so here is a little helper that will normally
    // be inlined, but not on the broken compiler. This incurs a substantial overhead (a function
    // call), but until someone else has a better idea, it's the only way to make it work reliably.
 
    static bool xor_helper(bool a, bool b)
#if defined(__GNUC__) && ! defined(__clang__) && __GNUC__ == 6 && __GNUC_MINOR__ == 3 && __cplusplus \
  == 201402L
      __attribute__((noinline))
#endif
      ;
 
  public:
 
    BitSetVectorReference& operator^=(const BitSetVectorConstReference& x)
    {
      // This uses the helper from above to hoist the actual XOR computation out of the function for
      // the buggy version of GCC.
      for (size_type i=0; i<block_size; i++)
        getBit(i) = xor_helper(test(i),x.test(i));
      return *this;
    }
 
    BitSetVectorReference& operator<<=(size_type n)
    {
      for (size_type i=0; i<block_size-n; i++)
        getBit(i) = test(i+n);
      return *this;
    }
 
    BitSetVectorReference& operator>>=(size_type n)
    {
      for (size_type i=0; i<block_size-n; i++)
        getBit(i+n) = test(i);
      return *this;
    }
 
    BitSetVectorReference& set()
    {
      for (size_type i=0; i<block_size; i++)
        set(i);
      return *this;
    }
 
    BitSetVectorReference& flip()
    {
      for (size_type i=0; i<block_size; i++)
        flip(i);
      return *this;
    }
 
    BitSetVectorReference& reset()
    {
      *this = false;
      return *this;
    }
 
    BitSetVectorReference& set(size_type n, int val = 1)
    {
      getBit(n) = val;
      return *this;
    }
 
    BitSetVectorReference& reset(size_type n)
    {
      set(n, false);
      return *this;
    }
 
    BitSetVectorReference& flip(size_type n)
    {
      getBit(n).flip();
      return *this;
    }
 
    using BitSetVectorConstReference::test;
    using BitSetVectorConstReference::operator[];
 
    reference operator[](size_type i)
    {
      return getBit(i);
    }
 
  protected:
    BitSetVector& blockBitField;
 
    using BitSetVectorConstReference::getBit;
 
    reference getBit(size_type i)
    {
      return blockBitField.getBit(this->block_number,i);
    }
  };
 
  // implementation of helper - I put it into the template to avoid having
  // to compile it in a dedicated compilation unit
  template<int block_size, class Alloc>
  bool BitSetVectorReference<block_size,Alloc>::xor_helper(bool a, bool b)
  {
    return a ^ b;
  }
 
  template<int block_size, class Alloc>
  struct const_reference< BitSetVectorReference<block_size,Alloc> >
  {
    typedef BitSetVectorConstReference<block_size,Alloc> type;
  };
 
  template<int block_size, class Alloc>
  struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
  {
    typedef BitSetVectorConstReference<block_size,Alloc> type;
  };
 
  template<int block_size, class Alloc>
  struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
  {
    typedef BitSetVectorReference<block_size,Alloc> type;
  };
 
  template<int block_size, class Alloc>
  struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
  {
    typedef BitSetVectorReference<block_size,Alloc> type;
  };
 
  template <int block_size, class Allocator=std::allocator<bool> >
  class BitSetVector : private std::vector<bool, Allocator>
  {
    typedef std::vector<bool, Allocator> BlocklessBaseClass;
 
  public:
 
    typedef std::bitset<block_size> value_type;
 
    typedef BitSetVectorReference<block_size,Allocator> reference;
 
    typedef BitSetVectorConstReference<block_size,Allocator> const_reference;
 
    typedef BitSetVectorReference<block_size,Allocator>* pointer;
 
    typedef BitSetVectorConstReference<block_size,Allocator>* const_pointer;
 
    typedef typename std::vector<bool, Allocator>::size_type size_type;
 
    typedef Allocator allocator_type;
 
    typedef Dune::GenericIterator<BitSetVector<block_size,Allocator>, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade> iterator;
    typedef Dune::GenericIterator<const BitSetVector<block_size,Allocator>, const value_type, const_reference, std::ptrdiff_t, ForwardIteratorFacade> const_iterator;
 
    iterator begin(){
      return iterator(*this, 0);
    }
 
    const_iterator begin() const {
      return const_iterator(*this, 0);
    }
 
    iterator end(){
      return iterator(*this, size());
    }
 
    const_iterator end() const {
      return const_iterator(*this, size());
    }
 
    BitSetVector() :
      BlocklessBaseClass()
    {}
 
    BitSetVector(const BlocklessBaseClass& blocklessBitField) :
      BlocklessBaseClass(blocklessBitField)
    {
      if (blocklessBitField.size()%block_size != 0)
        DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
    }
 
    explicit BitSetVector(int n) :
      BlocklessBaseClass(n*block_size)
    {}
 
    BitSetVector(int n, bool v) :
      BlocklessBaseClass(n*block_size,v)
    {}
 
    void clear()
    {
      BlocklessBaseClass::clear();
    }
 
    void resize(int n, bool v = bool())
    {
      BlocklessBaseClass::resize(n*block_size, v);
    }
 
    size_type size() const
    {
      return BlocklessBaseClass::size()/block_size;
    }
 
    void setAll() {
      this->assign(BlocklessBaseClass::size(), true);
    }
 
    void unsetAll() {
      this->assign(BlocklessBaseClass::size(), false);
    }
 
    reference operator[](int i)
    {
      return reference(*this, i);
    }
 
    const_reference operator[](int i) const
    {
      return const_reference(*this, i);
    }
 
    reference back()
    {
      return reference(*this, size()-1);
    }
 
    const_reference back() const
    {
      return const_reference(*this, size()-1);
    }
 
    size_type count() const
    {
      return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
    }
 
    size_type countmasked(int j) const
    {
      size_type n = 0;
      size_type blocks = size();
      for(size_type i=0; i<blocks; ++i)
        n += getBit(i,j);
      return n;
    }
 
    friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
    {
      for (size_t i=0; i<v.size(); i++)
        s << v[i] << "  ";
      return s;
    }
 
  private:
 
    value_type getRepr(int i) const
    {
      value_type bits;
      for(int j=0; j<block_size; ++j)
        bits.set(j, getBit(i,j));
      return bits;
    }
 
    typename std::vector<bool>::reference getBit(size_type i, size_type j) {
      DUNE_ASSERT_BOUNDS(j < block_size);
      DUNE_ASSERT_BOUNDS(i < size());
      return BlocklessBaseClass::operator[](i*block_size+j);
    }
 
    typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
      DUNE_ASSERT_BOUNDS(j < block_size);
      DUNE_ASSERT_BOUNDS(i < size());
      return BlocklessBaseClass::operator[](i*block_size+j);
    }
 
    friend class BitSetVectorReference<block_size,Allocator>;
    friend class BitSetVectorConstReference<block_size,Allocator>;
  };
 
}  // namespace Dune
 
#endif