Newer
Older
// -*- 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
/** \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;
}
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//! 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
{
}
//! 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)
return (*this);
}
//! Assignment from BitSetVectorConstReference
BitSetVectorReference& operator=(const BitSetVectorConstReference & b)
{
for(int i=0; i<block_size; ++i)
return (*this);
}
//! Assignment from BitSetVectorReference
BitSetVectorReference& operator=(const BitSetVectorReference & b)
{
for(int i=0; i<block_size; ++i)
//! 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++)
return *this;
}
//! Right shift.
BitSetVectorReference& operator>>=(size_type n)
{
for (size_type i=0; i<block_size-n; i++)
return *this;
}
// Sets every bit.
{
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)
return *this;
}
using BitSetVectorConstReference::test;
using BitSetVectorConstReference::operator[];
reference operator[](size_type i)
{
return getBit(i);
}
protected:
using BitSetVectorConstReference::getBit;
reference getBit(size_type i)
{
return blockBitField.getBit(this->block_number,i);
}
};
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
/**
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;
typedef typename std::vector<bool, Allocator>::size_type size_type;
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
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 */
{
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