BitVector.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.
 
 
 
 
#ifndef Sawyer_BitVector_H
#define Sawyer_BitVector_H
 
#include <Sawyer/Assert.h>
#include <Sawyer/BitVectorSupport.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>
 
#include <boost/algorithm/string/predicate.hpp>
#include <boost/cstdint.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/vector.hpp>
 
namespace Sawyer {
namespace Container {
 
#ifdef BOOST_WINDOWS
 
inline double log2(double n) {
    return log(n) / log(2.0);
}
#endif
 
class BitVector {
public:
    typedef unsigned Word;                              
    typedef BitVectorSupport::BitRange BitRange;        
private:
    std::vector<Word> words_;
    size_t size_;
 
private:
    friend class boost::serialization::access;
    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(size_);
        s & BOOST_SERIALIZATION_NVP(words_);
    }
 
public:
    BitVector(): size_(0) {}
 
    BitVector(const BitVector &other): words_(other.words_), size_(other.size_) {}
 
    explicit BitVector(size_t nbits, bool newBits = false): size_(0) {
        resize(nbits, newBits);
    }
 
    static BitVector parse(std::string str) {
        // Radix information
        size_t bitsPerDigit = 0;
        const char *digits = NULL;
        if (boost::starts_with(str, "0x")) {
            bitsPerDigit = 4;
            digits = "0123456789abcdefABCDEF";
            str = str.substr(2);
        } else if (boost::starts_with(str, "0b")) {
            bitsPerDigit = 1;
            digits = "01";
            str = str.substr(2);
        } else if (boost::ends_with(str, "h")) {
            bitsPerDigit = 4;
            digits = "0123456789abcdefABCDEF";
            str = str.substr(0, str.size()-1);
        } else if (boost::starts_with(str, "0")) {
            bitsPerDigit = 2;
            digits = "01234567";
            str = str.substr(1);
        } else {
            bitsPerDigit = 0;                           // special case
            digits = "0123456789";
        }
 
        // Count digits
        size_t nDigits = 0;
        for (const char *t=str.c_str(); *t; ++t) {
            if (strchr(digits, *t))
                ++nDigits;
        }
        if (0==nDigits)
            throw std::runtime_error("BitVector::parse: no valid digits");
 
        // Number of bits
        size_t nBits = 0;
        if (bitsPerDigit) {
            nBits = bitsPerDigit * nDigits;
        } else {
            nBits = ceil(log2(pow(10.0, (double)nDigits)));
        }
 
        // Parse the string
        BitVector result(nBits);
        switch (bitsPerDigit) {
            case 0:
                result.fromDecimal(str);
                break;
            case 2:
                result.fromBinary(str);
                break;
            case 3:
                result.fromOctal(str);
                break;
            case 4:
                result.fromHex(str);
                break;
            default:
                assert(!"invalid radix");
                break;
        }
        return result;
    }
 
    BitVector& operator=(const BitVector &other) {
        words_ = other.words_;
        size_ = other.size_;
        return *this;
    }
 
    bool isEmpty() const { return 0 == size_; }
 
    size_t size() const { return size_; }
 
    BitVector& resize(size_t newSize, bool newBits=false) {
        if (0==newSize) {
            words_.clear();
            size_ = 0;
        } else if (newSize > size_) {
            size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
            words_.resize(nwords, Word(0));
            BitVectorSupport::setValue(data(), BitRange::hull(size_, newSize-1), newBits);
            size_ = newSize;
        } else {
            size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
            words_.resize(nwords);
            size_ = newSize;
        }
        return *this;
    }
 
    size_t capacity() const {
        return BitVectorSupport::bitsPerWord<Word>::value * words_.capacity();
    }
 
    BitRange hull() const {
        return 0==size_ ? BitRange() : BitRange::hull(0, size_-1);
    }
 
    static BitRange baseSize(size_t base, size_t size) {
        return BitRange::baseSize(base, size);
    }
 
    static BitRange hull(size_t minOffset, size_t maxOffset) {
        return BitRange::hull(minOffset, maxOffset);
    }
 
    //                                  Value access
 
    bool get(size_t idx) const {
        checkRange(idx);
        return BitVectorSupport::get(data(), idx);
    }
 
    BitVector& clear(const BitRange &range) {
        checkRange(range);
        BitVectorSupport::clear(data(), range);
        return *this;
    }
 
    BitVector& clear() {
        BitVectorSupport::clear(data(), hull());
        return *this;
    }
 
    BitVector& set(const BitRange &range) {
        checkRange(range);
        BitVectorSupport::set(data(), range);
        return *this;
    }
 
    BitVector& set() {
        BitVectorSupport::set(data(), hull());
        return *this;
    }
 
    BitVector& setValue(const BitRange &range, bool value) {
        checkRange(range);
        BitVectorSupport::setValue(data(), range, value);
        return *this;
    }
 
    BitVector& setValue(bool value) {
        BitVectorSupport::setValue(data(), hull(), value);
        return *this;
    }
 
    BitVector& copy(const BitRange &to, const BitVector &other, const BitRange &from) {
        checkRange(to);
        other.checkRange(from);
        BitVectorSupport::copy(other.data(), from, data(), to);
        return *this;
    }
 
    BitVector& copy(const BitRange &to, const BitRange &from) {
        checkRange(to);
        checkRange(from);
        BitVectorSupport::copy(data(), from, data(), to);
        return *this;
    }
 
    BitVector& swap(const BitRange &range1, BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        BitVectorSupport::swap(data(), range1, other.data(), range2);
        return *this;
    }
 
    BitVector& swap(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        BitVectorSupport::swap(data(), range1, data(), range2);
        return *this;
    }
 
    bool equalTo(const BitRange &range1, BitVector &other, const BitRange &range2) const {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::equalTo(data(), range1, other.data(), range2);
    }
 
    bool equalTo(const BitRange &range1, const BitRange &range2) const {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::equalTo(data(), range1, data(), range2);
    }
 
    bool equalTo(const BitVector &other) const {
        if (size() != other.size())
            return false;
        return BitVectorSupport::equalTo(data(), hull(), other.data(), other.hull());
    }
 
    //                                  Counting/searching
 
    Optional<size_t> leastSignificantSetBit(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::leastSignificantSetBit(data(), range);
    }
 
    Optional<size_t> leastSignificantSetBit() const {
        return BitVectorSupport::leastSignificantSetBit(data(), hull());
    }
 
    Optional<size_t> leastSignificantClearBit(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::leastSignificantClearBit(data(), range);
    }
 
    Optional<size_t> leastSignificantClearBit() const {
        return BitVectorSupport::leastSignificantClearBit(data(), hull());
    }
 
    Optional<size_t> mostSignificantSetBit(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::mostSignificantSetBit(data(), range);
    }
 
    Optional<size_t> mostSignificantSetBit() const {
        return BitVectorSupport::mostSignificantSetBit(data(), hull());
    }
 
    Optional<size_t> mostSignificantClearBit(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::mostSignificantClearBit(data(), range);
    }
 
    Optional<size_t> mostSignificantClearBit() const {
        return BitVectorSupport::mostSignificantClearBit(data(), hull());
    }
 
    bool isAllSet(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::isAllSet(data(), range);
    }
 
    bool isAllSet() const {
        return BitVectorSupport::isAllSet(data(), hull());
    }
 
    bool isAllClear(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::isAllClear(data(), range);
    }
 
    bool isAllClear() const {
        return BitVectorSupport::isAllClear(data(), hull());
    }
 
    size_t nSet(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::nSet(data(), range);
    }
 
    size_t nSet() const {
        return BitVectorSupport::nSet(data(), hull());
    }
 
    size_t nClear(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::nClear(data(), range);
    }
 
    size_t nClear() const {
        return BitVectorSupport::nClear(data(), hull());
    }
 
    Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitVector &other,
                                               const BitRange &range2) const {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::mostSignificantDifference(data(), range1, other.data(), range2);
    }
 
    Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitRange &range2) const {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::mostSignificantDifference(data(), range1, data(), range2);
    }
 
    Optional<size_t> mostSignificantDifference(const BitVector &other) const {
        return BitVectorSupport::mostSignificantDifference(data(), hull(), other.data(), other.hull());
    }
 
    Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitVector &other,
                                                const BitRange &range2) const {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::leastSignificantDifference(data(), range1, other.data(), range2);
    }
 
    Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitRange &range2) const {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::leastSignificantDifference(data(), range1, data(), range2);
    }
 
    Optional<size_t> leastSignificantDifference(const BitVector &other) const {
        return BitVectorSupport::leastSignificantDifference(data(), hull(), other.data(), other.hull());
    }
 
    //                                  Shift/rotate
 
    BitVector& shiftLeft(const BitRange &range, size_t nShift, bool newBits = 0) {
        checkRange(range);
        BitVectorSupport::shiftLeft(data(), range, nShift, newBits);
        return *this;
    }
 
    BitVector& shiftLeft(size_t nShift, bool newBits = 0) {
        BitVectorSupport::shiftLeft(data(), hull(), nShift, newBits);
        return *this;
    }
 
    BitVector& shiftRight(const BitRange &range, size_t nShift, bool newBits = 0) {
        checkRange(range);
        BitVectorSupport::shiftRight(data(), range, nShift, newBits);
        return *this;
    }
 
    BitVector& shiftRight(size_t nShift, bool newBits = 0) {
        BitVectorSupport::shiftRight(data(), hull(), nShift, newBits);
        return *this;
    }
 
    BitVector& shiftRightArithmetic(const BitRange &range, size_t nShift) {
        checkRange(range);
        BitVectorSupport::shiftRightArithmetic(data(), range, nShift);
        return *this;
    }
 
    BitVector& shiftRightArithmetic(size_t nShift) {
        BitVectorSupport::shiftRightArithmetic(data(), hull(), nShift);
        return *this;
    }
 
    BitVector& rotateRight(const BitRange &range, size_t nShift) {
        checkRange(range);
        BitVectorSupport::rotateRight(data(), range, nShift);
        return *this;
    }
 
    BitVector& rotateRight(size_t nShift) {
        BitVectorSupport::rotateRight(data(), hull(), nShift);
        return *this;
    }
 
    BitVector& rotateLeft(const BitRange &range, size_t nShift) {
        checkRange(range);
        BitVectorSupport::rotateLeft(data(), range, nShift);
        return *this;
    }
 
    BitVector& rotateLeft(size_t nShift) {
        BitVectorSupport::rotateLeft(data(), hull(), nShift);
        return *this;
    }
 
    //                                  Arithmetic
 
    BitVector& negate(const BitRange &range1) {
        checkRange(range1);
        BitVectorSupport::negate(data(), range1);
        return *this;
    }
 
    BitVector& negate() {
        BitVectorSupport::negate(data(), hull());
        return *this;
    }
 
    bool increment(const BitRange &range1) {
        checkRange(range1);
        return BitVectorSupport::increment(data(), range1);
    }
 
    bool increment() {
        return BitVectorSupport::increment(data(), hull());
    }
 
    bool decrement(const BitRange &range1) {
        checkRange(range1);
        return BitVectorSupport::decrement(data(), range1);
    }
 
    bool decrement() {
        return BitVectorSupport::decrement(data(), hull());
    }
 
    bool add(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::add(other.data(), range2, data(), range1, false);
    }
 
    bool add(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::add(data(), range2, data(), range1, false);
    }
 
    bool add(const BitVector &other) {
        return BitVectorSupport::add(other.data(), other.hull(), data(), hull(), false);
    }
 
    bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::subtract(other.data(), range2, data(), range1);
    }
 
    bool subtract(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::subtract(data(), range2, data(), range1);
    }
 
    bool subtract(const BitVector &other) {
        return BitVectorSupport::subtract(other.data(), other.hull(), data(), hull());
    }
 
    BitVector& signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        BitVectorSupport::signExtend(other.data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& signExtend(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        BitVectorSupport::signExtend(data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& signExtend(const BitVector &other) {
        BitVectorSupport::signExtend(other.data(), other.hull(), data(), hull());
        return *this;
    }
 
    BitVector& multiply10() {
        BitVectorSupport::multiply10(data(), hull());
        return *this;
    }
 
    BitVector& multiply10(const BitRange &range) {
        BitVectorSupport::multiply10(data(), range);
        return *this;
    }
 
    BitVector multiply(const BitVector &other) const {
        BitVector product(size() + other.size());
        BitVector addend = other;
        addend.resize(product.size());
        for (size_t i = 0; i < size(); ++i) {
            if (get(i))
                product.add(addend);
            addend.shiftLeft(1);
        }
        return product;
    }
 
    BitVector multiplySigned(const BitVector &other) const {
        // Unoptimized version using simple elementary school long multiply. The Wikipedia "Binary multiplier" article has a good
        // description of a more optimized approach.
        BitVector product(size() + other.size());
 
        // Absolute value of A
        BitVector a = *this;
        bool aIsNeg = false;
        if (a.size() > 1 && a.get(a.size()-1)) {
            aIsNeg = true;
            a.negate();
        }
 
        // Absolute value of B, and extended to result width
        BitVector b = other;
        bool bIsNeg = false;
        if (b.size() > 1 && b.get(b.size()-1)) {
            bIsNeg = true;
            b.negate();
        }
        b.resize(product.size());
 
        // Long multiplication
        for (size_t i = 0; i < a.size(); ++i) {
            if (a.get(i))
                product.add(b);
            b.shiftLeft(1);
        }
 
        // Correct the result sign
        if (aIsNeg != bIsNeg)
            product.negate();
 
        return product;
    }
 
    // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
    // to be different sizes.
 
    //                                  Bit-wise Boolean logic
 
    BitVector& invert(const BitRange &range) {
        checkRange(range);
        BitVectorSupport::invert(data(), range);
        return *this;
    }
 
    BitVector& invert() {
        BitVectorSupport::invert(data(), hull());
        return *this;
    }
 
    BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseAnd(const BitVector &other) {
        BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
        return *this;
    }
 
    BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseOr(const BitVector &other) {
        BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
        return *this;
    }
 
    BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
        checkRange(range1);
        other.checkRange(range2);
        BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
        checkRange(range1);
        checkRange(range2);
        BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
        return *this;
    }
 
    BitVector& bitwiseXor(const BitVector &other) {
        BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
        return *this;
    }
 
    //                                  Numeric comparisons
 
    bool isEqualToZero(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::isEqualToZero(data(), range);
    }
 
    bool isEqualToZero() const {
        return BitVectorSupport::isEqualToZero(data(), hull());
    }
 
    int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::compare(data(), range1, other.data(), range2);
    }
 
    int compare(const BitRange &range1, const BitRange &range2) const {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::compare(data(), range1, data(), range2);
    }
 
    int compare(const BitVector &other) const {
        return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
    }
 
    int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
        checkRange(range1);
        other.checkRange(range2);
        return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
    }
 
    int compareSigned(const BitRange &range1, const BitRange &range2) const {
        checkRange(range1);
        checkRange(range2);
        return BitVectorSupport::compareSigned(data(), range1, data(), range2);
    }
 
    int compareSigned(const BitVector &other) const {
        return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
    }
 
    //                                  Conversion
 
    boost::uint64_t toInteger(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::toInteger(data(), range);
    }
 
    boost::uint64_t toInteger() const {
        if (size() <= 64)
            return BitVectorSupport::toInteger(data(), size());
        return BitVectorSupport::toInteger(data(), hull());
    }
 
    boost::int64_t toSignedInteger(const BitRange &range) const {
        checkRange(range);
        return BitVectorSupport::toInteger(data(), range);
    }
 
    boost::int64_t toSignedInteger() const {
        if (size() <= 64)
            return BitVectorSupport::toSignedInteger(data(), size());
        return BitVectorSupport::toSignedInteger(data(), hull());
    }
 
    std::string toHex(const BitRange &range) const {
        return BitVectorSupport::toHex(data(), range);
    }
 
    std::string toHex() const {
        return BitVectorSupport::toHex(data(), hull());
    }
 
    std::string toOctal(const BitRange &range) const {
        return BitVectorSupport::toOctal(data(), range);
    }
 
    std::string toOctal() const {
        return BitVectorSupport::toOctal(data(), hull());
    }
 
    std::string toBinary(const BitRange &range) const {
        return BitVectorSupport::toBinary(data(), range);
    }
 
    std::string toBinary() const {
        return BitVectorSupport::toBinary(data(), hull());
    }
 
    BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
        checkRange(range);
        BitVectorSupport::fromInteger(data(), range, value);
        return *this;
    }
 
    BitVector& fromInteger(boost::uint64_t value) {
        BitVectorSupport::fromInteger(data(), hull(), value);
        return *this;
    }
 
    BitVector& fromDecimal(const BitRange &range, const std::string &input) {
        checkRange(range);
        BitVectorSupport::fromDecimal(data(), range, input);
        return *this;
    }
 
    BitVector& fromDecimal(const std::string &input) {
        BitVectorSupport::fromDecimal(data(), hull(), input);
        return *this;
    }
 
    BitVector& fromHex(const BitRange &range, const std::string &input) {
        checkRange(range);
        BitVectorSupport::fromHex(data(), range, input);
        return *this;
    }
 
    BitVector& fromHex(const std::string &input) {
        BitVectorSupport::fromHex(data(), hull(), input);
        return *this;
    }
 
    BitVector& fromOctal(const BitRange &range, const std::string &input) {
        checkRange(range);
        BitVectorSupport::fromOctal(data(), range, input);
        return *this;
    }
 
    BitVector& fromOctal(const std::string &input) {
        BitVectorSupport::fromOctal(data(), hull(), input);
        return *this;
    }
 
    BitVector& fromBinary(const BitRange &range, const std::string &input) {
        checkRange(range);
        BitVectorSupport::fromBinary(data(), range, input);
        return *this;
    }
 
    BitVector& fromBinary(const std::string &input) {
        BitVectorSupport::fromBinary(data(), hull(), input);
        return *this;
    }
 
    //                                  Utility
 
    void checkRange(const BitRange &range) const {
        ASSERT_always_require(hull().isContaining(range)); // so range is always used
    }
 
    Word* data() {
        return words_.empty() ? NULL : &words_[0];
    }
 
    const Word* data() const {
        return words_.empty() ? NULL : &words_[0];
    }
    size_t dataSize() const {
        return words_.size();
    }
};
 
} // namespace
} // namespace
#endif