DTTPGConfig/interface/BitArray.h

0001 //-------------------------------------------------
0002 //
0003 //   Class: BitArray
0004 //
0005 //   Description: Manipulates arrays of bits
0006 //
0007 //
0008 //   Author List:
0009 //   C. Grandi
0010 //   Modifications:
0011 //
0012 //
0013 //--------------------------------------------------
0014 #ifndef BIT_ARRAY_H_
0015 #define BIT_ARRAY_H_
0016
0017 //---------------
0018 // C++ Headers --
0019 //---------------
0020 #include <cassert>
0021 #include <iostream>
0022
0023 //              ---------------------
0024 //              -- Class Interface --
0025 //              ---------------------
0026
0027 template <int N>
0028 class BitArray {
0029 public:
0030   class refToBit;
0031   friend class refToBit;
0032
0033   // reference to bit class
0034   class refToBit {
0035     friend class BitArray;
0036
0037     //refToBit();
0038
0039   public:
0040     refToBit() {}
0041     refToBit(BitArray& b, int pos) {
0042       _word = &b.getWord(pos);
0043       _pos = getPosInWord(pos);
0044     }
0045     ~refToBit() {}
0046
0047     refToBit& operator=(const int val) {
0048       if (val) {
0049         *_word |= getPosMask(_pos);
0050       } else {
0051         *_word &= ~(getPosMask(_pos));
0052       }
0053       return *this;
0054     }
0055
0056     refToBit& operator=(const refToBit& rtb) {
0057       if ((*(rtb._word) & getPosMask(rtb._pos))) {
0058         *_word |= getPosMask(_pos);
0059       } else {
0060         *_word &= ~getPosMask(_pos);
0061       }
0062       return *this;
0063     }
0064
0065     int operator~() const { return ((*_word) & getPosMask(_pos)) == 0; }
0066
0067     operator int() const { return ((*_word) & getPosMask(_pos)) != 0; }
0068
0069     refToBit& flip() {
0070       *_word ^= getPosMask(_pos);
0071       return *this;
0072     }
0073
0074   private:
0075     unsigned* _word;
0076     int _pos;
0077   };
0078
0079   BitArray() { this->zero(); }
0080
0081   BitArray(const BitArray<N>& br) {
0082     for (int i = 0; i < this->nWords(); i++) {
0083       _data[i] = br._data[i];
0084     }
0085     this->cleanUnused();
0086   }
0087   BitArray(const char* str) {
0088     this->zero();
0089     this->assign(0, this->nBits(), str);
0090     this->cleanUnused();
0091   }
0092   BitArray(const char* str, const int p, const int n) {
0093     this->zero();
0094     this->assign(p, n, str);
0095   }
0096   BitArray(const unsigned i) {
0097     this->zero();
0098     _data[0] = i;  // the nBit least sign. bits are considered
0099     this->cleanUnused();
0100   }
0101   /*
0102   BitArray(const unsigned long i) {
0103     this->zero();
0104     unsigned j = i&static_cast<unsigned long>(0xffffffff);
0105     _data[0] = j;                 // the nBit least sign. bits are considered
0106     if(this->nBits()>32) {
0107       j=i>>32;
0108       _data[1] = j;
0109     }
0110     this->cleanUnused();
0111   }
0112 */
0113   //  Destructor
0114   // ~BitArray() {}
0115
0116   // Return number of bits
0117   inline int nBits() const { return N; }
0118   inline int size() const { return this->nBits(); }
0119
0120   // Return number of words
0121   inline int nWords() const { return N / 32 + 1; }
0122
0123   // Return a data word
0124   unsigned dataWord(const int i) const {
0125     assert(i >= 0 && i < this->nWords());
0126     return _data[i];
0127   }
0128   unsigned& dataWord(const int i) {
0129     assert(i >= 0 && i < this->nWords());
0130     return _data[i];
0131   }
0132
0133   // Return the dataword which contains bit in position
0134   unsigned& getWord(const int pos) {
0135     assert(pos >= 0 && pos < this->nBits());
0136     return _data[pos / 32];
0137   }
0138   unsigned getWord(const int pos) const {
0139     assert(pos >= 0 && pos < this->nBits());
0140     return _data[pos / 32];
0141   }
0142
0143   // Return the position inside a word given the position in bitArray
0144   static int getPosInWord(const int pos) {
0145     // assert(pos>=0&& pos<this->nBits());
0146     return pos % 32;
0147   }
0148
0149   // Return the word mask for a given bit
0150   static unsigned getPosMask(const int pos) { return static_cast<unsigned>(1) << getPosInWord(pos); }
0151
0152   // how many bits are not used (most significative bits of last word)
0153   int unusedBits() const {
0154     if (this->nBits() == 0)
0155       return 32;
0156     return 31 - ((this->nBits() - 1) % 32);
0157   }
0158
0159   // mask to get rid of last word unused bits
0160   unsigned lastWordMask() const { return static_cast<unsigned>(0xffffffff) >> (this->unusedBits()); }
0161
0162   // set unused bits to 0
0163   void cleanUnused() { _data[this->nWords() - 1] &= (this->lastWordMask()); }
0164
0165   // count non 0 bits
0166   int count() const {
0167     int n = 0;
0168     for (int i = 0; i < this->nBits(); i++) {
0169       if (this->element(i))
0170         n++;
0171     }
0172     return n;
0173   }
0174
0175   // true if any bit == 1
0176   int any() {
0177     int nw = this->nWords();
0178     int ub = unusedBits();
0179     if (this->dataWord(nw - 1) << ub != 0)
0180       return 1;
0181     if (nw > 1) {
0182       for (int iw = 0; iw < nw - 1; iw++) {
0183         if (this->dataWord(iw) != 0)
0184           return 1;
0185       }
0186     }
0187     return 0;
0188   }
0189
0190   // true if any bit == 0
0191   int none() {
0192     int nw = this->nWords();
0193     int ub = unusedBits();
0194     if (this->dataWord(nw - 1) << ub != 0xffffffff)
0195       return 1;
0196     if (nw > 1) {
0197       for (int iw = 0; iw < nw - 1; iw++) {
0198         if (this->dataWord(iw) != 0xffffffff)
0199           return 1;
0200       }
0201     }
0202     return 0;
0203   }
0204
0205   // Return i^th elemnet
0206   int element(const int pos) const { return (getWord(pos) & getPosMask(pos)) != static_cast<unsigned>(0); }
0207   inline int test(const int i) const { return element(i); }
0208
0209   // Set/unset all elements
0210   void zero() {
0211     for (int i = 0; i < this->nWords(); i++) {
0212       _data[i] = 0x0;  // set to 0
0213     }
0214   }
0215   inline void reset() { zero(); }
0216
0217   void one() {
0218     for (int i = 0; i < this->nWords(); i++) {
0219       _data[i] = 0xffffffff;  // set to 1
0220     }
0221   }
0222
0223   // Set/unset i^th element
0224   void set(const int i) { getWord(i) |= getPosMask(i); }
0225   void unset(const int i) { getWord(i) &= ~getPosMask(i); }
0226   inline void reset(const int i) { this->unset(i); }
0227
0228   // Set the i^th element to a given value
0229   inline void set(const int i, const int val) { this->assign(i, 1, val); }
0230   inline void set(const int i, const char* str) { this->assign(i, 1, str); }
0231
0232   // Set/unset many bits to a given integer/bitArray/string
0233   void assign(const int p, const int n, const int val) {
0234     assert(p >= 0 && p + n <= this->nBits());
0235     // only the n least significant bits of val are considered
0236     for (int i = 0; i < n; i++) {
0237       if (val >> i & 1) {
0238         this->set(p + i);
0239       } else {
0240         this->unset(p + i);
0241       }
0242     }
0243   }
0244   void assign(const int p, const int n, const BitArray<N>& val) {
0245     assert(p >= 0 && p + n <= this->nBits());
0246     // only the n least significant bits of val are considered
0247     for (int i = 0; i < n; i++) {
0248       if (val.element(i)) {
0249         this->set(p + i);
0250       } else {
0251         this->unset(p + i);
0252       }
0253     }
0254   }
0255   void assign(const int p, const int n, const char* str) {
0256     assert(p >= 0 && p + n <= this->nBits());
0257     // only the n least significant bits of val are considered
0258     for (int i = 0; i < n; i++) {
0259       assert(str[i] == '1' || str[i] == '0');
0260       if (str[i] == '1') {
0261         this->set(p + n - i - 1);    // reading a string from left to right
0262       } else {                       // --> most significative bit is the one
0263         this->unset(p + n - i - 1);  // with lower string index
0264       }
0265     }
0266   }
0267
0268   // Read a given range in an unsigned integer
0269   unsigned read(const int p, const int n) const {
0270     assert(p >= 0 && p + n <= this->nBits());
0271     assert(n <= 32);  // the output must fit in a 32 bit word
0272     // only the n least significant bits of val are considered
0273     unsigned out = 0x0;
0274     for (int i = 0; i < n; i++) {
0275       if (this->test(p + i))
0276         out |= 1 << i;
0277     }
0278     return out;
0279   }
0280
0281   // Read BitArray in bytes. Returns a BitArray<8>
0282   BitArray<8> byte(const int i) const {
0283     BitArray<8> out;
0284     if (i >= 0 && i < 4 * this->nWords()) {
0285       unsigned k = (_data[i / 4] >> 8 * (i % 4)) & 0xff;
0286       out = k;
0287     }
0288     return out;
0289   }
0290   // Assignment
0291   BitArray<N>& operator=(const BitArray<N>& a) {
0292     if (this != &a) {
0293       for (int i = 0; i < this->nWords(); i++) {
0294         _data[i] = a._data[i];
0295       }
0296     }
0297     this->cleanUnused();
0298     return *this;
0299   }
0300
0301   // Conversion from unsigned
0302   BitArray<N>& operator=(const unsigned i) {
0303     this->zero();
0304     _data[0] = i;  // the nBit least sign. bits are considered
0305     this->cleanUnused();
0306     return *this;
0307   }
0308   /*
0309   // Conversion from unsigned long
0310   BitArray<N>& operator=(const unsigned long i) {
0311     this->zero();
0312     unsigned j = i&0xffffffff;
0313     _data[0] = j;                 // the nBit least sign. bits are considered
0314     if(this->nBits()>32) {
0315       j=i>>32;
0316       _data[1] = j;
0317     }
0318     this->cleanUnused();
0319     return *this;
0320   }
0321 */
0322   // Conversion from char
0323   BitArray<N>& operator=(const char* str) {
0324     this->zero();
0325     for (int i = 0; i < this->nBits(); i++) {
0326       assert(str[i] == '1' || str[i] == '0');
0327       if (str[i] == '1') {
0328         this->set(this->nBits() - i - 1);    // reading a string from left to right
0329       } else if (str[i] == '0') {            // --> most significative bit is the one
0330         this->unset(this->nBits() - i - 1);  // with lower string index
0331       } else {
0332         break;  // exit when find a char which is not 0 or 1
0333       }
0334     }
0335     this->cleanUnused();
0336     return *this;
0337   }
0338
0339   // Print
0340   std::ostream& print(std::ostream& o = std::cout) const {
0341     for (int i = this->nBits() - 1; i >= 0; i--) {
0342       o << this->element(i);
0343     }
0344     return o;
0345   }
0346
0347   // direct access to set/read elements
0348   refToBit operator[](const int pos) { return refToBit(*this, pos); }
0349   int operator[](const int pos) const { return element(pos); }
0350
0351   // logical operators ==
0352   bool operator==(const BitArray<N>& a) const {
0353     int nw = this->nWords();
0354     int ub = this->unusedBits();
0355     if (this->dataWord(nw - 1) << ub !=  // check last word
0356         a.dataWord(nw - 1) << ub)
0357       return false;
0358     if (nw > 1) {
0359       for (int iw = 0; iw < nw - 1; iw++) {
0360         if (this->dataWord(iw) != a.dataWord(iw))
0361           return false;
0362       }
0363     }
0364     return true;
0365   }
0366
0367   // logical operators <
0368   bool operator<(const BitArray<N>& a) const {
0369     int nw = this->nWords();
0370     int ub = this->unusedBits();
0371     unsigned aaa = this->dataWord(nw - 1) << ub;  // ignore unused bits
0372     unsigned bbb = a.dataWord(nw - 1) << ub;      // in both operands
0373     if (aaa < bbb) {
0374       return true;
0375     } else if (aaa > bbb) {
0376       return false;
0377     }
0378     if (nw > 1) {
0379       for (int iw = nw - 2; iw >= 0; iw--) {
0380         if (this->dataWord(iw) < a.dataWord(iw)) {
0381           return true;
0382         } else if (this->dataWord(iw) > a.dataWord(iw)) {
0383           return false;
0384         }
0385       }
0386     }
0387     return false;
0388   }
0389
0390   // logical operators !=
0391   bool operator!=(const BitArray<N>& a) const { return !(a == *this); }
0392
0393   // logical operators >=
0394   bool operator>=(const BitArray<N>& a) const { return !(*this < a); }
0395
0396   // logical operators >
0397   bool operator>(const BitArray<N>& a) const { return !(*this < a || *this == a); }
0398
0399   // logical operators <=
0400   bool operator<=(const BitArray<N>& a) const { return !(*this > a); }
0401
0402   // non-const bit by bit negation
0403   BitArray<N>& flip() {
0404     for (int i = 0; i < this->nWords(); i++) {
0405       _data[i] = ~_data[i];
0406     }
0407     return *this;
0408   }
0409
0410   // const bit by bit negation
0411   BitArray<N> operator~() const { return BitArray<N>(*this).flip(); }
0412
0413   // bit by bit AND and assignment
0414   BitArray<N>& operator&=(const BitArray<N>& a) {
0415     for (int i = 0; i < this->nWords(); i++) {
0416       this->dataWord(i) &= a.dataWord(i);
0417     }
0418     return *this;
0419   }
0420
0421   // bit by bit AND
0422   BitArray<N> operator&(const BitArray<N>& a) { return BitArray<N>(*this) &= a; }
0423
0424   // bit by bit OR and assignment
0425   BitArray<N>& operator|=(const BitArray<N>& a) {
0426     for (int i = 0; i < this->nWords(); i++) {
0427       this->dataWord(i) |= a.dataWord(i);
0428     }
0429     return *this;
0430   }
0431
0432   // bit by bit AND
0433   BitArray<N> operator|(const BitArray<N>& a) { return BitArray<N>(*this) |= a; }
0434
0435   // bit by bit XOR and assignment
0436   BitArray<N>& operator^=(const BitArray<N>& a) {
0437     for (int i = 0; i < this->nWords(); i++) {
0438       this->dataWord(i) ^= a.dataWord(i);
0439     }
0440     return *this;
0441   }
0442
0443   // bit by bit XOR
0444   BitArray<N> operator^(const BitArray<N>& a) { return BitArray<N>(*this) ^= a; }
0445
0446   // left shift and assignment
0447   BitArray<N>& operator<<=(const int n) {
0448     assert(n >= 0 && n < this->nBits());
0449     if (n == 0)
0450       return *this;
0451     int i = 0;
0452     for (i = this->nBits() - 1; i >= n; i--)
0453       this->set(i, this->element(i - n));
0454     for (i = n - 1; i >= 0; i--)
0455       this->unset(i);
0456     return *this;
0457   }
0458
0459   // left shift
0460   BitArray<N> operator<<(const int n) { return BitArray<N>(*this) <<= n; }
0461
0462   // right shift and assignment
0463   BitArray<N>& operator>>=(const int n) {
0464     assert(n >= 0 && n < this->nBits());
0465     if (n == 0)
0466       return *this;
0467     int i = 0;
0468     for (i = 0; i < this->nBits() - n; i++)
0469       this->set(i, this->element(i + n));
0470     for (i = this->nBits() - n; i < this->nBits(); i++)
0471       this->unset(i);
0472     return *this;
0473   }
0474
0475   // right shift
0476   BitArray<N> operator>>(const int n) { return BitArray<N>(*this) >>= n; }
0477
0478   // sum and assignment
0479   BitArray<N>& operator+=(const BitArray<N>& a) {
0480     int rep = 0;
0481     int sum = 0;
0482     for (int i = 0; i < this->nBits(); i++) {
0483       sum = this->element(i) ^ rep;
0484       rep = this->element(i) & rep;
0485       this->set(i, sum ^ a.element(i));
0486       rep |= (sum & a.element(i));
0487     }
0488     return *this;
0489   }
0490
0491   // sum
0492   BitArray<N> operator+(const BitArray<N>& a) { return BitArray<N>(*this) += a; }
0493
0494   // postfix increment
0495   BitArray<N>& operator++(int) {
0496     int i = 0;
0497     while (i < this->nBits() && this->element(i) == 1) {
0498       this->unset(i);
0499       i++;
0500     }
0501     if (i < this->nBits())
0502       this->set(i);
0503     return *this;
0504   }
0505
0506   // const 2 complement
0507   BitArray<N> twoComplement() const { return BitArray<N>(~*this)++; }
0508
0509   // non-const 2 complement
0510   BitArray<N>& twoComplement() {
0511     (*this).flip();
0512     (*this)++;
0513     return *this;
0514   }
0515
0516   // subtract and assignment
0517   BitArray<N>& operator-=(const BitArray<N>& a) { return *this += a.twoComplement(); }
0518
0519   // subtract
0520   BitArray<N> operator-(const BitArray<N>& a) { return BitArray<N>(*this) -= a; }
0521
0522 private:
0523   unsigned _data[N / 32 + 1];
0524 };
0525
0526 /*
0527 template<int N>
0528 ostream & operator <<(ostream & o, const BitArray<N> &b) {
0529   b.print(o); return o;
0530 }
0531 */
0532
0533 #endif