MVAComputer/interface/BitSet.h

0001 #ifndef PhysicsTools_MVAComputer_BitSet_h
0002 #define PhysicsTools_MVAComputer_BitSet_h
0003 // -*- C++ -*-
0004 //
0005 // Package:     MVAComputer
0006 // Class  :     BitSet
0007 //
0008
0009 //
0010 // Author:  Christophe Saout <christophe.saout@cern.ch>
0011 // Created:     Sat Apr 24 15:18 CEST 2007
0012 //
0013
0014 #include <cstring>
0015 #include <cstddef>
0016 #include <cstring>
0017
0018 namespace PhysicsTools {
0019
0020   /** \class BitSet
0021  *
0022  * \short A compact container for storing single bits.
0023  *
0024  * BitSet provides a container of boolean values, similar to
0025  * a std::vector<bool> which only consumes one actual bit for each value.
0026  * Also an iterator is provided that can iterate over all set bits.
0027  *
0028  ************************************************************/
0029   class BitSet {
0030   public:
0031     typedef std::size_t size_t;
0032
0033   protected:
0034     typedef unsigned int Word_t;
0035
0036   public:
0037     /** \class Manipulator
0038      *
0039      * \short Opaque structure for transparent write access to individual bits.
0040      *
0041      * This structure is used transparently on the left side of an
0042      * assigment operator when writing a boolean value to an
0043      * individual bit, i.e. represents some sort of bit reference type.
0044      *
0045      ************************************************************/
0046     struct Manipulator {
0047     public:
0048       inline Manipulator(const Manipulator &orig) : word(orig.word), mask(orig.mask) {}
0049       inline ~Manipulator() {}
0050
0051       /// implicit cast to pointed-at boolean bit value
0052       inline operator bool() const { return *word & mask; }
0053
0054       /// bit assignment operator
0055       inline bool operator=(bool bit) {
0056         *word = (*word & ~mask) | (bit ? mask : 0);
0057         return bit;
0058       }
0059
0060     protected:
0061       friend class BitSet;
0062
0063       inline Manipulator(Word_t *word, unsigned int bit) : word(word), mask((Word_t)1 << bit) {}
0064
0065     private:
0066       Word_t *word;
0067       Word_t mask;
0068     };
0069
0070     /** \class Iterator
0071      *
0072      * \short Iterates over all set bits of a BitSet.
0073      *
0074      * This structure is used to iterate over all set bits in a BitSet.
0075      *
0076      ************************************************************/
0077     struct Iterator {
0078     public:
0079       /// boolean test for the end of the BitSet
0080       inline operator bool() const { return store < end; }
0081
0082       /// returns the index of the currently pointed-at bit
0083       inline size_t operator()() const { return (store - begin) * wordSize + pos; }
0084
0085       /// increment iterator to point at the next set bit
0086       Iterator &operator++() {
0087         if (++pos < wordSize) {
0088           //Only look at bits at and beyond pos
0089           Word_t word = *store & ((~(1U << pos)) + 1);
0090           if (word) {
0091             pos = ffs(word) - 1;
0092             return *this;
0093           }
0094         }
0095
0096         pos = 0;
0097         for (;;) {
0098           if (++store >= end)
0099             break;
0100           else if (*store) {
0101             pos = ffs(*store) - 1;
0102             break;
0103           }
0104         }
0105
0106         return *this;
0107       }
0108
0109       /// increment iterator to point at the next set bit
0110       inline Iterator operator++(int dummy) {
0111         Iterator orig = *this;
0112         ++*this;
0113         return orig;
0114       }
0115
0116     protected:
0117       friend class BitSet;
0118
0119       Iterator(Word_t *begin, Word_t *end) : begin(begin), store(begin), end(end), pos(0) {
0120         if (store < end && !(*store & 1))
0121           ++*this;
0122       }
0123
0124     private:
0125       Word_t *begin, *store, *end;
0126       unsigned int pos;
0127     };
0128
0129     BitSet() : store(nullptr), bits_(0) {}
0130
0131     BitSet(const BitSet &orig) : bits_(orig.bits_) {
0132       std::size_t words = bitsToWords(bits_);
0133       if (words) {
0134         store = new Word_t[words];
0135         std::memcpy(store, orig.store, words * sizeof(Word_t));
0136       } else
0137         store = nullptr;
0138     }
0139
0140     /// construct BitSet with a fixed size of \a bits bits
0141     BitSet(size_t bits) : bits_(bits) {
0142       std::size_t words = bitsToWords(bits);
0143       if (words) {
0144         store = new Word_t[words];
0145         std::memset(store, 0, sizeof(Word_t) * words);
0146       } else
0147         store = nullptr;
0148     }
0149
0150     inline ~BitSet() { delete[] store; }
0151
0152     BitSet &operator=(const BitSet &orig) {
0153       delete[] store;
0154       bits_ = orig.bits_;
0155       std::size_t words = bitsToWords(bits_);
0156       if (words) {
0157         store = new Word_t[words];
0158         std::memcpy(store, orig.store, words * sizeof(Word_t));
0159       } else
0160         store = nullptr;
0161       return *this;
0162     }
0163
0164     /// provide read/write access to bit with index \a bit via reference
0165     inline Manipulator operator[](size_t bit) { return Manipulator(&store[bit / wordSize], bit % wordSize); }
0166
0167     /// provide read access to bit with index \a bit via reference
0168     inline const Manipulator operator[](size_t bit) const {
0169       return Manipulator(&store[bit / wordSize], bit % wordSize);
0170     }
0171
0172     /// returns the number of all bits in the container
0173     inline size_t size() const { return bits_; }
0174
0175     /// returns the number of set bits in the container
0176     size_t bits() const;
0177
0178     /// create iterator over all set bits
0179     inline Iterator iter() const { return Iterator(store, store + bitsToWords(bits_)); }
0180
0181   private:
0182     static inline size_t bitsToWords(std::size_t bits) { return (bits + wordSize - 1) / wordSize; }
0183
0184     static const unsigned int wordSize = sizeof(Word_t) * 8;
0185
0186     Word_t *store;
0187     size_t bits_;
0188   };
0189
0190   namespace Calibration {
0191     class BitSet;
0192
0193     /// constructs BitSet container from persistent representation
0194     PhysicsTools::BitSet convert(const BitSet &bitSet);
0195     /// convert BitSet container into persistent representation
0196     BitSet convert(const PhysicsTools::BitSet &bitSet);
0197   }  // namespace Calibration
0198
0199 }  // namespace PhysicsTools
0200
0201 #endif  // PhysicsTools_MVAComputer_BitSet_h