[ 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) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.9.0 (Tue Nov 6 2012)