00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef _BITVECTOR_H_
00020 #define _BITVECTOR_H_
00021
00022 #include "vec.h"
00023
00024 namespace LA {
00025
00026
00027
00028
00029 typedef unsigned long bitvector_block;
00030
00031 #define blockbits (8*sizeof(bitvector_block))
00032
00033 inline unsigned int bitvector_rounded(unsigned int n)
00034 {
00035 return ((n+blockbits-1)/blockbits)*blockbits;
00036 }
00037
00038 class bitvector : public NRVec<bitvector_block>
00039 {
00040 private:
00041 unsigned int modulo;
00042 public:
00043 bitvector() : NRVec<bitvector_block>() {};
00044 explicit bitvector (const unsigned int n):NRVec<bitvector_block>((n+blockbits-1)/blockbits) {modulo=n%blockbits;};
00045 bitvector (const bitvector_block a, const unsigned int n):NRVec<bitvector_block>(a,(n+blockbits-1)/blockbits) {modulo=n%blockbits;};
00046 bitvector(const bitvector &rhs) : NRVec<bitvector_block>(rhs) {modulo=rhs.modulo;};
00047
00048
00049
00050 void resize(const unsigned int n) {NRVec<bitvector_block>::resize((n+blockbits-1)/blockbits); modulo=n%blockbits;};
00051 unsigned int size() const {return (nn*blockbits)-blockbits+(modulo?modulo:blockbits);};
00052
00053 const bool operator[](const unsigned int i) const {return (v[i/blockbits] >>(i%blockbits))&1;};
00054 void set(const unsigned int i) {v[i/blockbits] |= (1<<(i%blockbits));};
00055 void reset(const unsigned int i) {v[i/blockbits] &= ~(1<<(i%blockbits));};
00056 const bool get(const unsigned int i) {return (v[i/blockbits] >>(i%blockbits))&1;};
00057 const bool assign(const unsigned int i, const bool r) {if(r) set(i); else reset(i); return r;};
00058 void clear() {copyonwrite(); memset(v,0,nn*sizeof(bitvector_block));};
00059 void fill() {memset(v,0xff,nn*sizeof(bitvector_block));};
00060 bool operator!=(const bitvector &rhs) const;
00061 bool operator==(const bitvector &rhs) const {return !(*this != rhs);};
00062 bool operator>(const bitvector &rhs) const;
00063 bool operator<(const bitvector &rhs) const;
00064 bool operator>=(const bitvector &rhs) const {return !(*this < rhs);};
00065 bool operator<=(const bitvector &rhs) const {return !(*this > rhs);};
00066 bitvector operator~() const;
00067 bitvector& operator&=(const bitvector &rhs);
00068 bitvector& operator|=(const bitvector &rhs);
00069 bitvector& operator^=(const bitvector &rhs);
00070 bitvector operator&(const bitvector &rhs) const {return bitvector(*this) &= rhs;};
00071 bitvector operator|(const bitvector &rhs) const {return bitvector(*this) |= rhs;};
00072 bitvector operator^(const bitvector &rhs) const {return bitvector(*this) ^= rhs;};
00073 unsigned int population(const unsigned int before=0) const;
00074
00075
00076
00077 };
00078
00079
00080 extern std::ostream & operator<<(std::ostream &s, const bitvector &x);
00081 extern std::istream & operator>>(std::istream &s, bitvector &x);
00082
00083 }
00084 #endif