00001
00002
00003 #ifndef DUNE_BLOCK_BITFIELD_HH
00004 #define DUNE_BLOCK_BITFIELD_HH
00005
00010 #include <vector>
00011 #include <bitset>
00012 #include <iostream>
00013 #include <algorithm>
00014
00015 #include <dune/common/boundschecking.hh>
00016 #include <dune/common/genericiterator.hh>
00017 #include <dune/common/exceptions.hh>
00018
00019 namespace Dune {
00020
00021 template <int block_size, class Alloc> class BitSetVector;
00022 template <int block_size, class Alloc> class BitSetVectorReference;
00023
00034 template <int block_size, class Alloc>
00035 class BitSetVectorConstReference
00036 {
00037 protected:
00038
00039 typedef Dune::BitSetVector<block_size, Alloc> BitSetVector;
00040 friend class Dune::BitSetVector<block_size, Alloc>;
00041
00042 BitSetVectorConstReference(const BitSetVector& blockBitField_, int block_number_) :
00043 blockBitField(blockBitField_),
00044 block_number(block_number_)
00045 {
00046 DUNE_ASSERT_BOUNDS(blockBitField_.size() > block_number_);
00047 }
00048
00050 BitSetVectorConstReference& operator=(const BitSetVectorConstReference & b);
00051
00052 public:
00053
00054 typedef std::bitset<block_size> bitset;
00055
00056
00057 typedef typename std::vector<bool, Alloc>::const_reference reference;
00058 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
00059 typedef size_t size_type;
00060
00062 bitset operator<<(size_type n) const
00063 {
00064 bitset b = *this;
00065 b <<= n;
00066 return b;
00067 }
00068
00070 bitset operator>>(size_type n) const
00071 {
00072 bitset b = *this;
00073 b >>= n;
00074 return b;
00075 }
00076
00078 bitset operator~() const
00079 {
00080 bitset b = *this;
00081 b.flip();
00082 return b;
00083 }
00084
00086 size_type size() const
00087 {
00088 return block_size;
00089 }
00090
00092 size_type count() const
00093 {
00094 size_type n = 0;
00095 for(size_type i=0; i<block_size; ++i)
00096 n += getBit(i);
00097 return n;
00098 }
00099
00101 bool any() const
00102 {
00103 return count();
00104 }
00105
00107 bool none() const
00108 {
00109 return ! any();
00110 }
00111
00113 bool all() const
00114 {
00115 for(size_type i=0; i<block_size; ++i)
00116 if(not test(i))
00117 return false;
00118 return true;
00119 }
00120
00122 bool test(size_type n) const
00123 {
00124 return getBit(n);
00125 }
00126
00127 const_reference operator[](size_type i) const
00128 {
00129 return getBit(i);
00130 }
00131
00133 operator bitset() const
00134 {
00135 return blockBitField.getRepr(block_number);
00136 }
00137
00139 bool operator== (const bitset& bs) const
00140 {
00141 return equals(bs);
00142 }
00143
00145 bool operator== (const BitSetVectorConstReference& bs) const
00146 {
00147 return equals(bs);
00148 }
00149
00151 bool operator!= (const bitset& bs) const
00152 {
00153 return ! equals(bs);
00154 }
00155
00157 bool operator!= (const BitSetVectorConstReference& bs) const
00158 {
00159 return ! equals(bs);
00160 }
00161
00168 friend std::ostream& operator<< (std::ostream& s, const BitSetVectorConstReference& v)
00169 {
00170 s << "(";
00171 for(int i=0; i<block_size; ++i)
00172 s << v[i];
00173 s << ")";
00174 return s;
00175 }
00176
00177 protected:
00178 const BitSetVector& blockBitField;
00179 int block_number;
00180
00181 const_reference getBit(size_type i) const
00182 {
00183 return blockBitField.getBit(block_number,i);
00184 }
00185
00186 template<class BS>
00187 bool equals(const BS & bs) const
00188 {
00189 bool eq = true;
00190 for(int i=0; i<block_size; ++i)
00191 eq &= (getBit(i) == bs[i]);
00192 return eq;
00193 }
00194
00195 private:
00200 void operator & ();
00201
00202 friend class BitSetVectorReference<block_size, Alloc>;
00203 };
00204
00217 template <int block_size, class Alloc>
00218 class BitSetVectorReference : public BitSetVectorConstReference<block_size,Alloc>
00219 {
00220 protected:
00221
00222 typedef Dune::BitSetVector<block_size, Alloc> BitSetVector;
00223 friend class Dune::BitSetVector<block_size, Alloc>;
00224
00225 typedef Dune::BitSetVectorConstReference<block_size,Alloc> BitSetVectorConstReference;
00226
00227 BitSetVectorReference(BitSetVector& blockBitField_, int block_number_) :
00228 BitSetVectorConstReference(blockBitField_, block_number_),
00229 blockBitField(blockBitField_)
00230 {}
00231
00232 public:
00233 typedef std::bitset<block_size> bitset;
00234
00238 typedef typename std::vector<bool, Alloc>::reference reference;
00240 typedef typename std::vector<bool, Alloc>::const_reference const_reference;
00242
00244 typedef size_t size_type;
00245
00247 BitSetVectorReference& operator=(bool b)
00248 {
00249 for(int i=0; i<block_size; ++i)
00250 getBit(i) = b;
00251 return (*this);
00252 }
00253
00255 BitSetVectorReference& operator=(const bitset & b)
00256 {
00257 for(int i=0; i<block_size; ++i)
00258 getBit(i) = b.test(i);
00259 return (*this);
00260 }
00261
00263 BitSetVectorReference& operator=(const BitSetVectorConstReference & b)
00264 {
00265 for(int i=0; i<block_size; ++i)
00266 getBit(i) = b.test(i);
00267 return (*this);
00268 }
00269
00271 BitSetVectorReference& operator=(const BitSetVectorReference & b)
00272 {
00273 for(int i=0; i<block_size; ++i)
00274 getBit(i) = b.test(i);
00275 return (*this);
00276 }
00277
00279 BitSetVectorReference& operator&=(const bitset& x)
00280 {
00281 for (size_type i=0; i<block_size; i++)
00282 getBit(i) = (test(i) & x.test(i));
00283 return *this;
00284 }
00285
00287 BitSetVectorReference& operator&=(const BitSetVectorConstReference& x)
00288 {
00289 for (size_type i=0; i<block_size; i++)
00290 getBit(i) = (test(i) & x.test(i));
00291 return *this;
00292 }
00293
00295 BitSetVectorReference& operator|=(const bitset& x)
00296 {
00297 for (size_type i=0; i<block_size; i++)
00298 getBit(i) = (test(i) | x.test(i));
00299 return *this;
00300 }
00301
00303 BitSetVectorReference& operator|=(const BitSetVectorConstReference& x)
00304 {
00305 for (size_type i=0; i<block_size; i++)
00306 getBit(i) = (test(i) | x.test(i));
00307 return *this;
00308 }
00309
00311 BitSetVectorReference& operator^=(const bitset& x)
00312 {
00313 for (size_type i=0; i<block_size; i++)
00314 getBit(i) = (test(i) ^ x.test(i));
00315 return *this;
00316 }
00317
00319 BitSetVectorReference& operator^=(const BitSetVectorConstReference& x)
00320 {
00321 for (size_type i=0; i<block_size; i++)
00322 getBit(i) = (test(i) ^ x.test(i));
00323 return *this;
00324 }
00325
00327 BitSetVectorReference& operator<<=(size_type n)
00328 {
00329 for (size_type i=0; i<block_size-n; i++)
00330 getBit(i) = test(i+n);
00331 return *this;
00332 }
00333
00335 BitSetVectorReference& operator>>=(size_type n)
00336 {
00337 for (size_type i=0; i<block_size-n; i++)
00338 getBit(i+n) = test(i);
00339 return *this;
00340 }
00341
00342
00343 BitSetVectorReference& set()
00344 {
00345 for (size_type i=0; i<block_size; i++)
00346 set(i);
00347 return *this;
00348 }
00349
00351 BitSetVectorReference& flip()
00352 {
00353 for (size_type i=0; i<block_size; i++)
00354 flip(i);
00355 return *this;
00356 }
00357
00359 BitSetVectorReference& reset()
00360 {}
00361
00363 BitSetVectorReference& set(size_type n, int val = 1)
00364 {
00365 getBit(n) = val;
00366 return *this;
00367 }
00368
00370 BitSetVectorReference& reset(size_type n)
00371 {
00372 set(n, false);
00373 return *this;
00374 }
00375
00377 BitSetVectorReference& flip(size_type n)
00378 {
00379 getBit(n).flip();
00380 return *this;
00381 }
00382
00383 using BitSetVectorConstReference::test;
00384 using BitSetVectorConstReference::operator[];
00385
00386 reference operator[](size_type i)
00387 {
00388 return getBit(i);
00389 }
00390
00391 protected:
00392 BitSetVector& blockBitField;
00393
00394 using BitSetVectorConstReference::getBit;
00395
00396 reference getBit(size_type i)
00397 {
00398 return blockBitField.getBit(this->block_number,i);
00399 }
00400 };
00401
00405 template<int block_size, class Alloc>
00406 struct const_reference< BitSetVectorReference<block_size,Alloc> >
00407 {
00408 typedef BitSetVectorConstReference<block_size,Alloc> type;
00409 };
00410
00411 template<int block_size, class Alloc>
00412 struct const_reference< BitSetVectorConstReference<block_size,Alloc> >
00413 {
00414 typedef BitSetVectorConstReference<block_size,Alloc> type;
00415 };
00416
00417 template<int block_size, class Alloc>
00418 struct mutable_reference< BitSetVectorReference<block_size,Alloc> >
00419 {
00420 typedef BitSetVectorReference<block_size,Alloc> type;
00421 };
00422
00423 template<int block_size, class Alloc>
00424 struct mutable_reference< BitSetVectorConstReference<block_size,Alloc> >
00425 {
00426 typedef BitSetVectorReference<block_size,Alloc> type;
00427 };
00428
00432 template <int block_size, class Allocator=std::allocator<bool> >
00433 class BitSetVector : private std::vector<bool, Allocator>
00434 {
00436 typedef std::vector<bool, Allocator> BlocklessBaseClass;
00437
00438 public:
00441
00443 typedef std::bitset<block_size> value_type;
00444
00446 typedef BitSetVectorReference<block_size,Allocator> reference;
00447
00449 typedef BitSetVectorConstReference<block_size,Allocator> const_reference;
00450
00452 typedef BitSetVectorReference<block_size,Allocator>* pointer;
00453
00455 typedef BitSetVectorConstReference<block_size,Allocator>* const_pointer;
00456
00458 typedef typename std::vector<bool, Allocator>::size_type size_type;
00459
00461 typedef Allocator allocator_type;
00463
00466 typedef Dune::GenericIterator<BitSetVector<block_size,Allocator>, value_type, reference, std::ptrdiff_t, ForwardIteratorFacade> iterator;
00467 typedef Dune::GenericIterator<const BitSetVector<block_size,Allocator>, const value_type, const_reference, std::ptrdiff_t, ForwardIteratorFacade> const_iterator;
00469
00471 iterator begin(){
00472 return iterator(*this, 0);
00473 }
00474
00476 const_iterator begin() const {
00477 return const_iterator(*this, 0);
00478 }
00479
00481 iterator end(){
00482 return iterator(*this, size());
00483 }
00484
00486 const_iterator end() const {
00487 return const_iterator(*this, size());
00488 }
00489
00491 BitSetVector() :
00492 BlocklessBaseClass()
00493 {}
00494
00496 BitSetVector(const BlocklessBaseClass& blocklessBitField) :
00497 BlocklessBaseClass(blocklessBitField)
00498 {
00499 if (blocklessBitField.size()%block_size != 0)
00500 DUNE_THROW(RangeError, "Vector size is not a multiple of the block size!");
00501 }
00502
00506 explicit BitSetVector(int n) :
00507 BlocklessBaseClass(n*block_size)
00508 {}
00509
00511 BitSetVector(int n, bool v) :
00512 BlocklessBaseClass(n*block_size,v)
00513 {}
00514
00516 void clear()
00517 {
00518 BlocklessBaseClass::clear();
00519 }
00520
00522 void resize(int n, bool v = bool())
00523 {
00524 BlocklessBaseClass::resize(n*block_size, v);
00525 }
00526
00528 size_type size() const
00529 {
00530 return BlocklessBaseClass::size()/block_size;
00531 }
00532
00534 void setAll() {
00535 this->assign(BlocklessBaseClass::size(), true);
00536 }
00537
00539 void unsetAll() {
00540 this->assign(BlocklessBaseClass::size(), false);
00541 }
00542
00544 reference operator[](int i)
00545 {
00546 return reference(*this, i);
00547 }
00548
00550 const_reference operator[](int i) const
00551 {
00552 return const_reference(*this, i);
00553 }
00554
00556 reference back()
00557 {
00558 return reference(*this, size()-1);
00559 }
00560
00562 const_reference back() const
00563 {
00564 return const_reference(*this, size()-1);
00565 }
00566
00568 size_type count() const
00569 {
00570 return std::count(BlocklessBaseClass::begin(), BlocklessBaseClass::end(), true);
00571 }
00572
00574 size_type countmasked(int j) const
00575 {
00576 size_type n = 0;
00577 size_type blocks = size();
00578 for(size_type i=0; i<blocks; ++i)
00579 n += getBit(i,j);
00580 return n;
00581 }
00582
00584 friend std::ostream& operator<< (std::ostream& s, const BitSetVector& v)
00585 {
00586 for (size_t i=0; i<v.size(); i++)
00587 s << v[i] << " ";
00588 return s;
00589 }
00590
00591 private:
00592
00594 value_type getRepr(int i) const
00595 {
00596 value_type bits;
00597 for(int j=0; j<block_size; ++j)
00598 bits.set(j, getBit(i,j));
00599 return bits;
00600 }
00601
00602 typename std::vector<bool>::reference getBit(size_type i, size_type j) {
00603 DUNE_ASSERT_BOUNDS(j < block_size);
00604 DUNE_ASSERT_BOUNDS(i < size());
00605 return BlocklessBaseClass::operator[](i*block_size+j);
00606 }
00607
00608 typename std::vector<bool>::const_reference getBit(size_type i, size_type j) const {
00609 DUNE_ASSERT_BOUNDS(j < block_size);
00610 DUNE_ASSERT_BOUNDS(i < size());
00611 return BlocklessBaseClass::operator[](i*block_size+j);
00612 }
00613
00614 friend class BitSetVectorReference<block_size,Allocator>;
00615 friend class BitSetVectorConstReference<block_size,Allocator>;
00616 };
00617
00618 }
00619
00620 #endif