[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
vigra/bit_array.hxx | ![]() |
00001 #ifndef VIGRA_BIT_ARRAY_HXX 00002 #define VIGRA_BIT_ARRAY_HXX 00003 00004 #include <functional> 00005 #include <ostream> 00006 #include "metaprogramming.hxx" 00007 00008 namespace vigra { 00009 00010 template <class> // undefined class to provoke usable error messages 00011 class vigra_error_BitArray_accepts_only_unsigned_underlying_types_and_no_; 00012 00013 template <unsigned SIZE, class X> // bitwise operators do not necessarily work for bool 00014 struct EnableBitArray 00015 : public enable_if<(HasMetaLog2<X>::value && !IsSameType<X, bool>::value && SIZE > 0)> {}; 00016 00017 // BitArray: a minimal subset of std::bitset with the extension of compile-time 00018 // access functions set<unsigned>(), test<unsigned>(), reset<unsigned>(), and 00019 // flip<unsigned>(), plus all relational operators; 00020 // furthermore, there are no range checks. 00021 00022 template <unsigned SIZE, class WORD_TYPE = unsigned, class = void> 00023 class BitArray 00024 : public 00025 vigra_error_BitArray_accepts_only_unsigned_underlying_types_and_no_ 00026 <WORD_TYPE> 00027 {}; 00028 00029 template <unsigned SIZE, class WORD_TYPE> 00030 class BitArray<SIZE, WORD_TYPE, typename EnableBitArray<SIZE, WORD_TYPE>::type> 00031 { 00032 // 'unsigned' will be the most efficent word type for most CPUs, 00033 // since very long immediates such as a possible 64 bit 'unsigned long' 00034 // are slower for many typical uses of BitArray 00035 protected: 00036 static const unsigned bit_size = SIZE; 00037 static const unsigned word_len = MetaLog2<WORD_TYPE>::value; 00038 static const unsigned array_len = (bit_size + word_len - 1) / word_len; 00039 static const unsigned last_pos = array_len - 1; 00040 template <unsigned pos> 00041 struct bit_index 00042 { 00043 static const unsigned word_pos = pos / word_len; 00044 static const unsigned bit_pos = pos % word_len; 00045 static const WORD_TYPE bit_mask = WORD_TYPE(1) << bit_pos; 00046 }; 00047 typedef bit_index<bit_size> size_index; 00048 static const WORD_TYPE ones_mask = ~(WORD_TYPE(0)); 00049 static const unsigned border_pos = size_index::bit_pos; 00050 static const WORD_TYPE last_mask = !border_pos ? 0 00051 : size_index::bit_mask - 1; 00052 static const bool does_fit = border_pos == 0; 00053 unsigned word_pos(unsigned pos) const 00054 { 00055 return pos / word_len; 00056 }; 00057 WORD_TYPE bit_mask(unsigned pos) const 00058 { 00059 return WORD_TYPE(1) << (pos % word_len); // the compiler knows as well.. 00060 }; 00061 00062 WORD_TYPE set_bits[array_len]; 00063 00064 public: 00065 unsigned size() 00066 { 00067 return bit_size; 00068 } 00069 void clear() 00070 { 00071 for (unsigned i = 0; i != array_len; ++i) 00072 set_bits[i] = 0; 00073 } 00074 BitArray() 00075 { 00076 clear(); 00077 } 00078 template <unsigned pos> 00079 void set() 00080 { 00081 typedef bit_index<pos> index; 00082 set_bits[index::word_pos] |= index::bit_mask; 00083 } 00084 template <unsigned pos> 00085 void reset() 00086 { 00087 typedef bit_index<pos> index; 00088 set_bits[index::word_pos] &= ~index::bit_mask; 00089 } 00090 template <unsigned pos> 00091 void flip() 00092 { 00093 typedef bit_index<pos> index; 00094 set_bits[index::word_pos] ^= index::bit_mask; 00095 } 00096 template <unsigned pos> 00097 bool test() const 00098 { 00099 typedef bit_index<pos> index; 00100 return (set_bits[index::word_pos] & index::bit_mask) != 0; 00101 } 00102 00103 BitArray & set(unsigned pos, bool value = true) 00104 { 00105 (set_bits[word_pos(pos)] &= ~bit_mask(pos)) 00106 |= value ? bit_mask(pos) : 0; 00107 return *this; 00108 } 00109 BitArray & reset(unsigned pos) 00110 { 00111 set_bits[word_pos(pos)] &= ~bit_mask(pos); 00112 return *this; 00113 } 00114 BitArray & flip(unsigned pos) 00115 { 00116 set_bits[word_pos(pos)] ^= bit_mask(pos); 00117 return *this; 00118 } 00119 bool test(unsigned pos) const 00120 { 00121 return set_bits[word_pos(pos)] & bit_mask(pos); 00122 } 00123 bool operator[](unsigned pos) const 00124 { 00125 return test(pos); 00126 } 00127 00128 BitArray & set() 00129 { 00130 for (unsigned i = 0; i != last_pos + does_fit; ++i) 00131 set_bits[i] = ones_mask; 00132 if (!does_fit) 00133 set_bits[last_pos] = last_mask; 00134 return *this; 00135 } 00136 BitArray & reset() 00137 { 00138 for (unsigned i = 0; i != array_len; ++i) 00139 set_bits[i] = 0; 00140 return *this; 00141 } 00142 BitArray & flip() 00143 { 00144 for (unsigned i = 0; i != last_pos + does_fit; ++i) 00145 set_bits[i] ^= ones_mask; 00146 if (!does_fit) 00147 set_bits[last_pos] ^= last_mask; 00148 return *this; 00149 } 00150 00151 operator bool() const 00152 { 00153 for (unsigned i = 0; i != array_len; ++i) 00154 if (set_bits[i] != 0) 00155 return true; 00156 return false; 00157 } 00158 bool operator!() const 00159 { 00160 return !bool(*this); 00161 } 00162 bool any() const 00163 { 00164 return *this; 00165 } 00166 bool none() const 00167 { 00168 return !*this; 00169 } 00170 bool all() const 00171 { 00172 for (unsigned i = 0; i != last_pos + does_fit; ++i) 00173 if (set_bits[i] != ones_mask) 00174 return false; 00175 if (!does_fit) 00176 return set_bits[last_pos] == last_mask; 00177 return true; 00178 } 00179 00180 BitArray operator~() const 00181 { 00182 BitArray x(*this); 00183 x.flip(); 00184 return x; 00185 } 00186 00187 protected: 00188 template <class F> 00189 bool mutual_compare(const BitArray & t, F f, bool if_equal = false) const 00190 { 00191 for (int i = last_pos; i >= 0; i--) 00192 { 00193 WORD_TYPE x = set_bits[i]; 00194 WORD_TYPE y = t.set_bits[i]; 00195 if (f(x, y)) 00196 return true; 00197 if (f(y, x)) 00198 return false; 00199 } 00200 return if_equal; 00201 } 00202 typedef std::less<WORD_TYPE> less; 00203 typedef std::greater<WORD_TYPE> greater; 00204 00205 public: 00206 bool operator<(const BitArray & t) const 00207 { 00208 return mutual_compare(t, less()); 00209 } 00210 bool operator>(const BitArray & t) const 00211 { 00212 return mutual_compare(t, greater()); 00213 } 00214 00215 bool operator<=(const BitArray & t) const 00216 { 00217 return mutual_compare(t, less(), true); 00218 } 00219 bool operator>=(const BitArray & t) const 00220 { 00221 return mutual_compare(t, greater(), true); 00222 } 00223 00224 bool operator!=(const BitArray & t) const 00225 { 00226 for (unsigned i = 0; i != array_len; ++i) 00227 if (set_bits[i] != t.set_bits[i]) 00228 return true; 00229 return false; 00230 } 00231 bool operator==(const BitArray & t) const 00232 { 00233 return !operator!=(t); 00234 } 00235 00236 protected: 00237 struct bit_and_assign 00238 { 00239 static void assign(WORD_TYPE & a, WORD_TYPE b) { a &= b; } 00240 }; 00241 struct exclusive_or_assign 00242 { 00243 static void assign(WORD_TYPE & a, WORD_TYPE b) { a ^= b; } 00244 }; 00245 struct bit_or_assign 00246 { 00247 static void assign(WORD_TYPE & a, WORD_TYPE b) { a |= b; } 00248 }; 00249 template <class A> 00250 BitArray & assign_operator(const BitArray & x) 00251 { 00252 for (unsigned i = 0; i != array_len; ++i) 00253 A::assign(set_bits[i], x.set_bits[i]); 00254 return *this; 00255 } 00256 public: 00257 BitArray & operator&=(const BitArray & x) 00258 { 00259 return assign_operator<bit_and_assign>(x); 00260 } 00261 BitArray & operator^=(const BitArray & x) 00262 { 00263 return assign_operator<exclusive_or_assign>(x); 00264 } 00265 BitArray & operator|=(const BitArray & x) 00266 { 00267 return assign_operator<bit_or_assign>(x); 00268 } 00269 00270 protected: 00271 template <class A> 00272 BitArray & bit_operator(const BitArray & y) const 00273 { 00274 BitArray x(*this); 00275 return x.assign_operator<A>(y); 00276 } 00277 public: 00278 BitArray operator&(const BitArray & y) const 00279 { 00280 return bit_operator<bit_and_assign>(y); 00281 } 00282 BitArray operator^(const BitArray & y) const 00283 { 00284 return bit_operator<exclusive_or_assign>(y); 00285 } 00286 BitArray operator|(const BitArray & y) const 00287 { 00288 return bit_operator<bit_or_assign>(y); 00289 } 00290 00291 bool operator&&(const BitArray & y) const 00292 { 00293 return *this && y; 00294 } 00295 bool operator||(const BitArray & y) const 00296 { 00297 return *this || y; 00298 } 00299 00300 friend std::ostream & operator<<(std::ostream & os, const BitArray & z) 00301 { 00302 for (int i = bit_size - 1; i >= 0; i--) 00303 os << (z[i] ? "1" : "0"); 00304 return os; 00305 } 00306 }; 00307 00308 // work around GCC's zero-sized array extension 00309 template <class WORD_TYPE> 00310 class BitArray<0, WORD_TYPE> 00311 { 00312 // bool error[-(long int)sizeof(WORD_TYPE)]; 00313 void clear() {} 00314 }; 00315 00316 } // namespace vigra 00317 00318 #endif // VIGRA_BIT_ARRAY_HXX
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|