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

vigra/bit_array.hxx VIGRA

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)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.9.0 (Tue Nov 6 2012)