00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052 #include <w.h>
00053
00054
00055
00056
00057 template<int BIT_COUNT>
00058 class w_bitvector_t
00059 {
00060 public:
00061 enum { BITS = BIT_COUNT };
00062 typedef unsigned long Word;
00063 private:
00064 enum { BITS_PER_WORD=8*sizeof(Word) };
00065 enum { WORDS = (BITS+BITS_PER_WORD-1)/BITS_PER_WORD };
00066 unsigned long data[WORDS];
00067
00068 public:
00069
00070 w_bitvector_t() { clear(); }
00071
00072
00073 int num_bits() const {
00074 return BIT_COUNT;
00075 }
00076
00077
00078 int num_words() const {
00079 int n= sizeof(data)/sizeof(data[0]);
00080 w_assert1(n==WORDS);
00081 return n;
00082 }
00083
00084
00085
00086
00087
00088
00089
00090 bool overlap(w_bitvector_t &merged, const w_bitvector_t &other) const
00091 {
00092 return words_overlap(merged, other) == num_words();
00093 }
00094
00095
00096
00097
00098
00099
00100
00101
00102 int words_overlap(w_bitvector_t &merged, const w_bitvector_t &other) const
00103 {
00104 const unsigned long *mine=&data[0];
00105 const unsigned long *theirs=&other.data[0];
00106 unsigned long *newvec=&merged.data[0];
00107
00108 int matches=0;
00109 for(int i=0; i < num_words(); i++)
00110 {
00111 if (*mine == (*mine & *theirs)) matches++;
00112 *newvec = (*mine | *theirs);
00113 newvec++;
00114 mine++;
00115 theirs++;
00116 }
00117 return matches;
00118 }
00119
00120 ostream &print(ostream &o) const
00121 {
00122 {
00123 const char *sep="";
00124 o << "{";
00125 for(int i=0; i < BITS; i++)
00126 {
00127 if(is_set(i)) { o << sep << i; sep="."; }
00128 }
00129 o << "}";
00130 }
00131 {
00132
00133 const char *sep="";
00134 o << "(~{";
00135 for(int i=0; i < BITS; i++)
00136 {
00137 if( !is_set(i)) { o << sep << i; sep="."; }
00138 }
00139 o << "})";
00140 return o;
00141 }
00142 }
00143
00144
00145 void clear() {
00146 for(long i=0; i < WORDS; i++)
00147 data[i] = 0;
00148 }
00149
00150
00151 bool is_empty() const {
00152 Word hash = 0;
00153 for(long i=0; i < WORDS; i++)
00154 hash |= data[i];
00155 return hash == 0;
00156 }
00157
00158 int num_bits_set() const {
00159 int j=0;
00160 for(int i=0; i < BITS; i++)
00161 {
00162 if(is_set(i)) j++;
00163 }
00164 return j;
00165 }
00166
00167
00168 bool is_full() const {
00169 return num_bits_set() == BIT_COUNT;
00170 }
00171
00172
00173 void copy(const w_bitvector_t &other) {
00174 for(long i=0; i < WORDS; i++)
00175 data[i] = other.data[i];
00176 }
00177
00178 #define BIT_VECTOR_PROLOGUE(idx) \
00179 w_assert1(idx < BITS); \
00180 Word wdex = idx / BITS_PER_WORD; \
00181 Word bdex = idx % BITS_PER_WORD
00182
00183
00184 Word get_bit(Word idx) const {
00185 BIT_VECTOR_PROLOGUE(idx);
00186 return (data[wdex] >> bdex) & 0x1;
00187 }
00188
00189 bool is_set(Word idx) const {
00190 return (get_bit(idx) == 0x1);
00191 }
00192
00193 void set_bit(Word idx) {
00194 BIT_VECTOR_PROLOGUE(idx);
00195 data[wdex] |= (1ul << bdex);
00196 }
00197
00198 void clear_bit(Word idx) {
00199 BIT_VECTOR_PROLOGUE(idx);
00200 data[wdex] &= ~(1ul << bdex);
00201 }
00202 #undef BIT_VECTOR_PROLOGUE
00203 };