[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

bit_array.hxx |

1 #ifndef VIGRA_BIT_ARRAY_HXX
2 #define VIGRA_BIT_ARRAY_HXX
3
4 #include <functional>
5 #include <ostream>
6 #include "metaprogramming.hxx"
7
8 namespace vigra {
9
10 template <class> // undefined class to provoke usable error messages
11 class vigra_error_BitArray_accepts_only_unsigned_underlying_types_and_no_;
12
13 template <unsigned SIZE, class X> // bitwise operators do not necessarily work for bool
14 struct EnableBitArray
15 : public enable_if<(HasMetaLog2<X>::value && !IsSameType<X, bool>::value && SIZE > 0)> {};
16
17 // BitArray: a minimal subset of std::bitset with the extension of compile-time
18 // access functions set<unsigned>(), test<unsigned>(), reset<unsigned>(), and
19 // flip<unsigned>(), plus all relational operators;
20 // furthermore, there are no range checks.
21
22 template <unsigned SIZE, class WORD_TYPE = unsigned, class = void>
23 class BitArray
24 : public
25 vigra_error_BitArray_accepts_only_unsigned_underlying_types_and_no_
26 <WORD_TYPE>
27 {};
28
29 template <unsigned SIZE, class WORD_TYPE>
30 class BitArray<SIZE, WORD_TYPE, typename EnableBitArray<SIZE, WORD_TYPE>::type>
31 {
32 // 'unsigned' will be the most efficent word type for most CPUs,
33 // since very long immediates such as a possible 64 bit 'unsigned long'
34 // are slower for many typical uses of BitArray
35 protected:
36 static const unsigned bit_size = SIZE;
37 static const unsigned word_len = MetaLog2<WORD_TYPE>::value;
38 static const unsigned array_len = (bit_size + word_len - 1) / word_len;
39 static const unsigned last_pos = array_len - 1;
40 template <unsigned pos>
41 struct bit_index
42 {
43 static const unsigned word_pos = pos / word_len;
44 static const unsigned bit_pos = pos % word_len;
45 static const WORD_TYPE bit_mask = WORD_TYPE(1) << bit_pos;
46 };
47 typedef bit_index<bit_size> size_index;
48 static const WORD_TYPE ones_mask = ~(WORD_TYPE(0));
49 static const unsigned border_pos = size_index::bit_pos;
50 static const WORD_TYPE last_mask = !border_pos ? 0
51 : size_index::bit_mask - 1;
52 static const bool does_fit = border_pos == 0;
53 unsigned word_pos(unsigned pos) const
54 {
55 return pos / word_len;
56 };
57 WORD_TYPE bit_mask(unsigned pos) const
58 {
59 return WORD_TYPE(1) << (pos % word_len); // the compiler knows as well..
60 };
61
62 WORD_TYPE set_bits[array_len];
63
64 public:
65 unsigned size()
66 {
67 return bit_size;
68 }
69 void clear()
70 {
71 for (unsigned i = 0; i != array_len; ++i)
72 set_bits[i] = 0;
73 }
74 BitArray()
75 {
76 clear();
77 }
78 template <unsigned pos>
79 void set()
80 {
81 typedef bit_index<pos> index;
82 set_bits[index::word_pos] |= index::bit_mask;
83 }
84 template <unsigned pos>
85 void reset()
86 {
87 typedef bit_index<pos> index;
88 set_bits[index::word_pos] &= ~index::bit_mask;
89 }
90 template <unsigned pos>
91 void flip()
92 {
93 typedef bit_index<pos> index;
94 set_bits[index::word_pos] ^= index::bit_mask;
95 }
96 template <unsigned pos>
97 bool test() const
98 {
99 typedef bit_index<pos> index;
100 return (set_bits[index::word_pos] & index::bit_mask) != 0;
101 }
102
103 BitArray & set(unsigned pos, bool value = true)
104 {
105 (set_bits[word_pos(pos)] &= ~bit_mask(pos))
106 |= value ? bit_mask(pos) : 0;
107 return *this;
108 }
109 BitArray & reset(unsigned pos)
110 {
111 set_bits[word_pos(pos)] &= ~bit_mask(pos);
112 return *this;
113 }
114 BitArray & flip(unsigned pos)
115 {
116 set_bits[word_pos(pos)] ^= bit_mask(pos);
117 return *this;
118 }
119 bool test(unsigned pos) const
120 {
121 return set_bits[word_pos(pos)] & bit_mask(pos);
122 }
123 bool operator[](unsigned pos) const
124 {
125 return test(pos);
126 }
127
128 BitArray & set()
129 {
130 for (unsigned i = 0; i != last_pos + does_fit; ++i)
131 set_bits[i] = ones_mask;
132 if (!does_fit)
133 set_bits[last_pos] = last_mask;
134 return *this;
135 }
136 BitArray & reset()
137 {
138 for (unsigned i = 0; i != array_len; ++i)
139 set_bits[i] = 0;
140 return *this;
141 }
142 BitArray & flip()
143 {
144 for (unsigned i = 0; i != last_pos + does_fit; ++i)
145 set_bits[i] ^= ones_mask;
146 if (!does_fit)
147 set_bits[last_pos] ^= last_mask;
148 return *this;
149 }
150
151 operator bool() const
152 {
153 for (unsigned i = 0; i != array_len; ++i)
154 if (set_bits[i] != 0)
155 return true;
156 return false;
157 }
158 bool operator!() const
159 {
160 return !bool(*this);
161 }
162 bool any() const
163 {
164 return *this;
165 }
166 bool none() const
167 {
168 return !*this;
169 }
170 bool all() const
171 {
172 for (unsigned i = 0; i != last_pos + does_fit; ++i)
173 if (set_bits[i] != ones_mask)
174 return false;
175 if (!does_fit)
176 return set_bits[last_pos] == last_mask;
177 return true;
178 }
179
180 BitArray operator~() const
181 {
182 BitArray x(*this);
183 x.flip();
184 return x;
185 }
186
187 protected:
188 template <class F>
189 bool mutual_compare(const BitArray & t, F f, bool if_equal = false) const
190 {
191 for (int i = last_pos; i >= 0; i--)
192 {
193 WORD_TYPE x = set_bits[i];
194 WORD_TYPE y = t.set_bits[i];
195 if (f(x, y))
196 return true;
197 if (f(y, x))
198 return false;
199 }
200 return if_equal;
201 }
202 typedef std::less<WORD_TYPE> less;
203 typedef std::greater<WORD_TYPE> greater;
204
205 public:
206 bool operator<(const BitArray & t) const
207 {
208 return mutual_compare(t, less());
209 }
210 bool operator>(const BitArray & t) const
211 {
212 return mutual_compare(t, greater());
213 }
214
215 bool operator<=(const BitArray & t) const
216 {
217 return mutual_compare(t, less(), true);
218 }
219 bool operator>=(const BitArray & t) const
220 {
221 return mutual_compare(t, greater(), true);
222 }
223
224 bool operator!=(const BitArray & t) const
225 {
226 for (unsigned i = 0; i != array_len; ++i)
227 if (set_bits[i] != t.set_bits[i])
228 return true;
229 return false;
230 }
231 bool operator==(const BitArray & t) const
232 {
233 return !operator!=(t);
234 }
235
236 protected:
237 struct bit_and_assign
238 {
239 static void assign(WORD_TYPE & a, WORD_TYPE b) { a &= b; }
240 };
241 struct exclusive_or_assign
242 {
243 static void assign(WORD_TYPE & a, WORD_TYPE b) { a ^= b; }
244 };
245 struct bit_or_assign
246 {
247 static void assign(WORD_TYPE & a, WORD_TYPE b) { a |= b; }
248 };
249 template <class A>
250 BitArray & assign_operator(const BitArray & x)
251 {
252 for (unsigned i = 0; i != array_len; ++i)
253 A::assign(set_bits[i], x.set_bits[i]);
254 return *this;
255 }
256 public:
257 BitArray & operator&=(const BitArray & x)
258 {
259 return assign_operator<bit_and_assign>(x);
260 }
261 BitArray & operator^=(const BitArray & x)
262 {
263 return assign_operator<exclusive_or_assign>(x);
264 }
265 BitArray & operator|=(const BitArray & x)
266 {
267 return assign_operator<bit_or_assign>(x);
268 }
269
270 protected:
271 template <class A>
272 BitArray & bit_operator(const BitArray & y) const
273 {
274 BitArray x(*this);
275 return x.assign_operator<A>(y);
276 }
277 public:
278 BitArray operator&(const BitArray & y) const
279 {
280 return bit_operator<bit_and_assign>(y);
281 }
282 BitArray operator^(const BitArray & y) const
283 {
284 return bit_operator<exclusive_or_assign>(y);
285 }
286 BitArray operator|(const BitArray & y) const
287 {
288 return bit_operator<bit_or_assign>(y);
289 }
290
291 bool operator&&(const BitArray & y) const
292 {
293 return *this && y;
294 }
295 bool operator||(const BitArray & y) const
296 {
297 return *this || y;
298 }
299
300 friend std::ostream & operator<<(std::ostream & os, const BitArray & z)
301 {
302 for (int i = bit_size - 1; i >= 0; i--)
303 os << (z[i] ? "1" : "0");
304 return os;
305 }
306 };
307
308 // work around GCC's zero-sized array extension
309 template <class WORD_TYPE>
310 class BitArray<0, WORD_TYPE>
311 {
312 // bool error[-(long int)sizeof(WORD_TYPE)];
313 void clear() {}
314 };
315
316 } // namespace vigra
317
318 #endif // VIGRA_BIT_ARRAY_HXX
vigra
vigra::operator>
bool operator>(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
greater
Definition: fixedpoint.hxx:530
vigra::operator==
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition: fftw3.hxx:825
vigra::operator<=
bool operator<=(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less or equal
Definition: fixedpoint.hxx:521
vigra::operator<
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition: fixedpoint.hxx:512
vigra::operator>=
bool operator>=(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
greater or equal
Definition: fixedpoint.hxx:539
vigra::operator!=
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition: fftw3.hxx:841

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.1