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:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
#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) = delete;

  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)
    {
      return (*this) = bitset(*this) & x;
    }

    BitSetVectorReference& operator&=(const BitSetVectorConstReference& x)
    {
      return (*this) &= bitset(x);
    }

    BitSetVectorReference& operator|=(const bitset& x)
    {
      return (*this) = bitset(*this) | x;
    }

    BitSetVectorReference& operator|=(const BitSetVectorConstReference& x)
    {
      return (*this) |= bitset(x);
    }

    BitSetVectorReference& operator^=(const bitset& x)
    {
      return (*this) = bitset(*this) ^ x;
    }

    BitSetVectorReference& operator^=(const BitSetVectorConstReference& x)
    {
      return (*this) ^= bitset(x);
    }

    BitSetVectorReference& operator<<=(size_type n)
    {
      return (*this) = bitset(*this) << n;
    }

    BitSetVectorReference& operator>>=(size_type n)
    {
      return (*this) = bitset(*this) >> n;
    }

    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);
    }
  };

  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