libdune-common-dev 2.2.1-2 / usr / include / dune / common / bitsetvector.hh

#ifndef DUNE_BLOCK_BITFIELD_HH
#define DUNE_BLOCK_BITFIELD_HH

/** \file
    \brief Efficient implementation of a dynamic array of static arrays of booleans
*/

#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>

#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;

    /**
       \brief A proxy class that acts as a const reference to a single
       bitset in a BitSetVector.

       It contains a conversion to std::bitset and most of the
       interface of const std::bitset.

       \warning As this is only a proxy class, you can not get the
       address of the bitset.
     */
    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)
        {};

        //! hide assignment operator
        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;
        
        //! Returns a copy of *this shifted left by n bits.
        bitset operator<<(size_type n) const
        {
            bitset b = *this;
            b <<= n;
            return b;
        }

        //! Returns a copy of *this shifted right by n bits.
        bitset operator>>(size_type n) const
        {
            bitset b = *this;
            b >>= n;
            return b;
        }

        //! Returns a copy of *this with all of its bits flipped.
        bitset operator~() const
        {
            bitset b = *this;
            b.flip();
            return b;
        }

        //! Returns block_size.
        size_type size() const
        {
            return block_size;
        }

        //! Returns the number of bits that are set.
        size_type count() const
        {
            size_type n = 0;
            for(size_type i=0; i<block_size; ++i)
                n += getBit(i);
            return n;
        }

        //! Returns true if any bits are set.
        bool any() const
        {
            return count();
        }

        //! Returns true if no bits are set.
        bool none() const
        {
            return ! any();
        }

        //! Returns true if bit n is set. 
        bool test(size_type n) const
        {
            return getBit(n);
        }
        
        const_reference operator[](size_type i) const
        {
            return getBit(i);
        }
        
        //! cast to bitset
        operator bitset() const
        {
            return blockBitField.getRepr(block_number);
        }

        //! Equality of reference and std::bitset
        bool operator== (const bitset& bs) const
        {
            return equals(bs);
        }

        //! Equality of reference and other reference
        bool operator== (const BitSetVectorConstReference& bs) const
        {
            return equals(bs);
        }

        //! Inequality of reference and std::bitset
        bool operator!= (const bitset& bs) const
        {
            return ! equals(bs);
        }

        //! Inequality of reference and other reference
        bool operator!= (const BitSetVectorConstReference& bs) const
        {
            return ! equals(bs);
        }

        /*!
          missing operators:

          - unsigned long to_ulong() const
         */
        
        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:
        /**
           This is only a Proxy class, you can't get the address of the
           object it references
         */
        void operator & ();

        friend class BitSetVectorReference<block_size, Alloc>;
    };

    /**
       \brief A proxy class that acts as a mutable reference to a
       single bitset in a BitSetVector.

       It contains an assignment operator from std::bitset.  It
       inherits the const std::bitset interface provided by
       BitSetVectorConstReference and adds most of the non-const
       methods of std::bitset.

       \warning As this is only a proxy class, you can not get the
       address of the bitset.
     */
    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;

        //! bitset interface typedefs
        //! \{
        //! A proxy class that acts as a reference to a single bit.
        typedef typename std::vector<bool, Alloc>::reference reference;
        //! A proxy class that acts as a const reference to a single bit.
        typedef typename std::vector<bool, Alloc>::const_reference const_reference;
        //! \}

        //! size_type typedef (an unsigned integral type)
        typedef size_t size_type;

        //! Assignment from bool, sets each bit in the bitset to b
        BitSetVectorReference& operator=(bool b)
        {
            for(int i=0; i<block_size; ++i)
                getBit(i) = b;
            return (*this);
        }
        
        //! Assignment from bitset
        BitSetVectorReference& operator=(const bitset & b)
        {
            for(int i=0; i<block_size; ++i)
                getBit(i) = b.test(i);
            return (*this);
        }

        //! Assignment from BitSetVectorConstReference
        BitSetVectorReference& operator=(const BitSetVectorConstReference & b)
        {
            for(int i=0; i<block_size; ++i)
                getBit(i) = b.test(i);
            return (*this);
        }

        //! Assignment from BitSetVectorReference
        BitSetVectorReference& operator=(const BitSetVectorReference & b)
        {
            for(int i=0; i<block_size; ++i)
                getBit(i) = b.test(i);
            return (*this);
        }

        //! Bitwise and (for bitset).
        BitSetVectorReference& operator&=(const bitset& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) & x.test(i));
            return *this;
        }

        //! Bitwise and (for BitSetVectorConstReference and BitSetVectorReference)
        BitSetVectorReference& operator&=(const BitSetVectorConstReference& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) & x.test(i));
            return *this;
        }

        //! Bitwise inclusive or (for bitset)
        BitSetVectorReference& operator|=(const bitset& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) | x.test(i));
            return *this;
        }

        //! Bitwise inclusive or (for BitSetVectorConstReference and BitSetVectorReference)
        BitSetVectorReference& operator|=(const BitSetVectorConstReference& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) | x.test(i));
            return *this;
        }

        //! Bitwise exclusive or (for bitset).
        BitSetVectorReference& operator^=(const bitset& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) ^ x.test(i));
            return *this;
        }

        //! Bitwise exclusive or (for BitSetVectorConstReference and BitSetVectorReference)
        BitSetVectorReference& operator^=(const BitSetVectorConstReference& x)
        {
            for (size_type i=0; i<block_size; i++)
                getBit(i) = (test(i) ^ x.test(i));
            return *this;
        }

        //! Left shift.
        BitSetVectorReference& operator<<=(size_type n)
        {
            for (size_type i=0; i<block_size-n; i++)
                getBit(i) = test(i+n);
            return *this;
        }

        //! Right shift.
        BitSetVectorReference& operator>>=(size_type n)
        {
            for (size_type i=0; i<block_size-n; i++)
                getBit(i+n) = test(i);
            return *this;
        }

        // Sets every bit.
        BitSetVectorReference& set()
        {
            for (size_type i=0; i<block_size; i++)
                set(i);
            return *this;
        }

        //! Flips the value of every bit.
        BitSetVectorReference& flip()
        {
            for (size_type i=0; i<block_size; i++)
                flip(i);
            return *this;
        }

        //! Clears every bit.
        BitSetVectorReference& reset()
        {
        }

        //! Sets bit n if val is nonzero, and clears bit n if val is zero.
        BitSetVectorReference& set(size_type n, int val = 1)
        {
            getBit(n) = val;
            return *this;
        }

        //! Clears bit n.
        BitSetVectorReference& reset(size_type n)
        {
            set(n, false);
            return *this;
        }

        //! Flips bit n.
        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);
        }
    };

    /**
       typetraits for BitSetVectorReference
     */
    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;
    };

    /**
       \brief A dynamic %array of blocks of booleans
    */
    template <int block_size, class Allocator=std::allocator<bool> >
    class BitSetVector : private std::vector<bool, Allocator>
    {
        /** \brief The implementation class: an unblocked bitfield */
        typedef std::vector<bool, Allocator> BlocklessBaseClass;
        
    public:
        //! container interface typedefs
        //! \{

        /** \brief Type of the values stored by the container */
        typedef std::bitset<block_size> value_type;

        /** \brief Reference to a small block of bits */
        typedef BitSetVectorReference<block_size,Allocator> reference;

        /** \brief Const reference to a small block of bits */
        typedef BitSetVectorConstReference<block_size,Allocator> const_reference;

        /** \brief Pointer to a small block of bits */
        typedef BitSetVectorReference<block_size,Allocator>* pointer;

        /** \brief Const pointer to a small block of bits */
        typedef BitSetVectorConstReference<block_size,Allocator>* const_pointer;

        /** \brief size type */
        typedef typename std::vector<bool, Allocator>::size_type size_type;

        /** \brief The type of the allocator */
        typedef Allocator allocator_type;
        //! \}

        //! iterators
        //! \{
        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;
        //! \}

        //! Returns a iterator pointing to the beginning of the vector.
        iterator begin(){
            return iterator(*this, 0);
        }

        //! Returns a const_iterator pointing to the beginning of the vector.
        const_iterator begin() const{    
            return const_iterator(*this, 0);
        }

        //! Returns an iterator pointing to the end of the vector.
        iterator end(){
            return iterator(*this, size());
        }

        //! Returns a const_iterator pointing to the end of the vector.
        const_iterator end() const{    
            return const_iterator(*this, size());
        }
  
        //! Default constructor
        BitSetVector() :
            BlocklessBaseClass()
        {}
        
        //! Construction from an unblocked bitfield
        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!");
        }
        
        /** Constructor with a given length
            \param n Number of blocks
        */
        explicit BitSetVector(int n) :
            BlocklessBaseClass(n*block_size)
        {}
        
        //! Constructor which initializes the field with true or false
        BitSetVector(int n, bool v) :
            BlocklessBaseClass(n*block_size,v)
        {}

        //! Erases all of the elements.
        void clear()
        {
            BlocklessBaseClass::clear();
        }
        
        //! Resize field
        void resize(int n, bool v = bool())
        {
            BlocklessBaseClass::resize(n*block_size, v);
        }
        
        /** \brief Return the number of blocks */
        size_type size() const
        {
            return BlocklessBaseClass::size()/block_size;
        }
        
        //! Sets all entries to <tt> true </tt>
        void setAll() {
            this->assign(BlocklessBaseClass::size(), true);
        }
        
        //! Sets all entries to <tt> false </tt>
        void unsetAll() {
            this->assign(BlocklessBaseClass::size(), false);
        }
        
        /** \brief Return reference to i-th block */
        reference operator[](int i)
        {
            return reference(*this, i);
        }
        
        /** \brief Return const reference to i-th block */
        const_reference operator[](int i) const
        {
            return const_reference(*this, i);
        }
        
        /** \brief Return reference to last block */
        reference back()
        {
            return reference(*this, size()-1);
        }
        
        /** \brief Return const reference to last block */
        const_reference back() const
        {
            return const_reference(*this, size()-1);
        }
        
        //! Returns the number of bits that are set.
        size_type count() const
        {
            return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
        }
        
        //! Returns the number of set bits, while each block is masked with 1<<i
        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;
        }
        
        //! Send bitfield to an output stream
        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:

        // get a prepresentation as value_type
        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) {
            return BlocklessBaseClass::operator[](i*block_size+j);
        }
        
        typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
            return BlocklessBaseClass::operator[](i*block_size+j);
        }
        
        friend class BitSetVectorReference<block_size,Allocator>;
        friend class BitSetVectorConstReference<block_size,Allocator>;
    };

}  // namespace Dune

#endif