cpp/core/src/common/BitArray.cpp

   1 /*
   2  *  BitArray.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 09/05/2008.
   6  *  Copyright 2008 Google UK. All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include "BitArray.h"
  22 #include <iostream>
  23
  24 using namespace std;
  25
  26 namespace common {
  27   static unsigned int logDigits(unsigned digits) {
  28     unsigned log = 0;
  29     unsigned val = 1;
  30     while (val < digits) {
  31       log++;
  32       val <<= 1;
  33     }
  34     return log;
  35   }
  36   const unsigned int BitArray::bitsPerWord_ =
  37     numeric_limits<unsigned int>::digits;
  38   const unsigned int BitArray::logBits_ = logDigits(bitsPerWord_);
  39   const unsigned int BitArray::bitsMask_ = (1 << logBits_) - 1;
  40   size_t BitArray::wordsForBits(size_t bits) {
  41     int arraySize = bits >> logBits_;
  42     if (bits - (arraySize << logBits_) != 0) {
  43       arraySize++;
  44     }
  45     return arraySize;
  46   }
  47   BitArray::BitArray() {
  48     cout << "hey! don't use this BitArrayConstructor!\n";
  49   }
  50
  51   BitArray::BitArray(size_t size) :
  52   size_(size), bits_((const unsigned int)0, wordsForBits(size)) {
  53   }
  54   BitArray::~BitArray() { }
  55   size_t BitArray::getSize() {
  56     return size_;
  57   }
  58   bool BitArray::get(size_t i) {
  59     return (bits_[i >> logBits_] & (1 << (i & bitsMask_))) != 0;
  60   }
  61   void BitArray::set(size_t i) {
  62     bits_[i >> logBits_] |= 1 << (i & bitsMask_);
  63   }
  64   void BitArray::setBulk(size_t i, unsigned int newBits) {
  65     bits_[i >> logBits_] = newBits;
  66   }
  67   void BitArray::clear() {
  68     size_t max = bits_.size();
  69     for (size_t i = 0; i < max; i++) {
  70       bits_[i] = 0;
  71     }
  72   }
  73   bool BitArray::isRange(size_t start, size_t end, bool value) {
  74     if (end < start) {
  75       throw new IllegalArgumentException("end must be after start");
  76     }
  77     if (end == start) {
  78       return true;
  79     }
  80     // treat the 'end' as inclusive, rather than exclusive
  81     end--;
  82     size_t firstWord = start >> logBits_;
  83     size_t lastWord = end >> logBits_;
  84     for (size_t i = firstWord; i <= lastWord; i++) {
  85       size_t firstBit = i > firstWord ? 0 : start & bitsMask_;
  86       size_t lastBit = i < lastWord ? logBits_ : end & bitsMask_;
  87       unsigned int mask;
  88       if (firstBit == 0 && lastBit == logBits_) {
  89         mask = numeric_limits<unsigned int>::max();
  90       } else {
  91         mask = 0;
  92         for (size_t j = firstBit; j <= lastBit; j++) {
  93           mask |= 1 << j;
  94         }
  95       }
  96       if (value) {
  97         if ((bits_[i] & mask) != mask) {
  98           return false;
  99         }
 100       } else {
 101         if ((bits_[i] & mask) != 0) {
 102           return false;
 103         }
 104       }
 105     }
 106     return true;
 107   }
 108   valarray<unsigned int>& BitArray::getBitArray() {
 109     return bits_;
 110   }
 111   void BitArray::reverse() {
 112     unsigned int allBits = numeric_limits<unsigned int>::max();
 113     size_t max = bits_.size();
 114     for (size_t i = 0; i < max; i++) {
 115       bits_[i] = bits_[i] ^ allBits;
 116     }
 117   }
 118 }