bitset.h

// Copyright 2012-2023:
//   GobySoft, LLC (2013-)
//   Massachusetts Institute of Technology (2007-2014)
//   Community contributors (see AUTHORS file)
// File authors:
//   Toby Schneider <toby@gobysoft.org>
//   Nathan Knotts <nknotts@gmail.com>
//   philboske <philboske@gmail.com>
//
//
// This file is part of the Dynamic Compact Control Language Library
// ("DCCL").
//
// DCCL is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 2.1 of the License, or
// (at your option) any later version.
//
// DCCL is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with DCCL.  If not, see <http://www.gnu.org/licenses/>.
#ifndef DCCLBITSET20120424H
#define DCCLBITSET20120424H
 
#include <algorithm>
#include <cstring>
#include <deque>
#include <limits>
#include <string>
 
#include "exception.h"
 
namespace dccl
{
class Bitset : public std::deque<bool>
{
  public:
    explicit Bitset(Bitset* parent = nullptr) : parent_(parent) {}
 
    explicit Bitset(size_type num_bits, unsigned long value = 0, Bitset* parent = nullptr)
        : std::deque<bool>(num_bits, false), parent_(parent)
    {
        from(value, num_bits);
    }
 
    ~Bitset() = default;
 
    const Bitset* parent() const { return parent_; }
 
    void get_more_bits(size_type num_bits);
 
    Bitset& operator&=(const Bitset& rhs)
    {
        if (rhs.size() != size())
            throw(dccl::Exception("Bitset operator&= requires this->size() == rhs.size()"));
 
        for (size_type i = 0; i != this->size(); ++i) (*this)[i] &= rhs[i];
        return *this;
    }
 
    Bitset& operator|=(const Bitset& rhs)
    {
        if (rhs.size() != size())
            throw(dccl::Exception("Bitset operator|= requires this->size() == rhs.size()"));
 
        for (size_type i = 0; i != this->size(); ++i) (*this)[i] |= rhs[i];
        return *this;
    }
 
    Bitset& operator^=(const Bitset& rhs)
    {
        if (rhs.size() != size())
            throw(dccl::Exception("Bitset operator^= requires this->size() == rhs.size()"));
 
        for (size_type i = 0; i != this->size(); ++i) (*this)[i] ^= rhs[i];
        return *this;
    }
 
    //            Bitset& operator-=(const Bitset& rhs);
 
    Bitset& operator<<=(size_type n)
    {
        for (size_type i = 0; i < n; ++i)
        {
            push_front(false);
            pop_back();
        }
        return *this;
    }
 
    Bitset& operator>>=(size_type n)
    {
        for (size_type i = 0; i < n; ++i)
        {
            push_back(false);
            pop_front();
        }
        return *this;
    }
 
    Bitset operator<<(size_type n) const
    {
        Bitset copy(*this);
        copy <<= n;
        return copy;
    }
 
    Bitset operator>>(size_type n) const
    {
        Bitset copy(*this);
        copy >>= n;
        return copy;
    }
 
    Bitset& set(size_type n, bool val = true)
    {
        (*this)[n] = val;
        return *this;
    }
 
    Bitset& set()
    {
        for (bool& it : *this) it = true;
        return *this;
    }
 
    Bitset& reset(size_type n) { return set(n, false); }
 
    Bitset& reset()
    {
        for (bool& it : *this) it = false;
        return *this;
    }
 
    Bitset& flip(size_type n) { return set(n, !(*this)[n]); }
 
    Bitset& flip()
    {
        for (size_type i = 0, n = size(); i < n; ++i) flip(i);
        return *this;
    }
 
    bool test(size_type n) const { return (*this)[n]; }
 
    /* bool any() const; */
    /* bool none() const; */
    /* Bitset operator~() const; */
    /* size_type count() const; */
 
    template <typename IntType>
    void from(IntType value, size_type num_bits = std::numeric_limits<IntType>::digits)
    {
        this->resize(num_bits);
        for (int i = 0, n = std::min<size_type>(std::numeric_limits<IntType>::digits, size());
             i < n; ++i)
        {
            if (value & (static_cast<IntType>(1) << i))
                (*this)[i] = true;
        }
    }
 
    void from_ulong(unsigned long value,
                    size_type num_bits = std::numeric_limits<unsigned long>::digits)
    {
        from<unsigned long>(value, num_bits);
    }
 
    template <typename IntType> IntType to() const
    {
        if (size() > static_cast<size_type>(std::numeric_limits<IntType>::digits))
            throw(Exception("Type IntType cannot represent current bitset (this->size() > "
                            "std::numeric_limits<IntType>::digits)"));
 
        IntType out = 0;
        for (int i = 0, n = size(); i < n; ++i)
        {
            if ((*this)[i])
                out |= (static_cast<IntType>(1) << i);
        }
 
        return out;
    }
 
    unsigned long to_ulong() const { return to<unsigned long>(); }
 
    std::string to_string() const
    {
        std::string s(size(), 0);
        int i = 0;
        for (auto it = rbegin(), n = rend(); it != n; ++it)
        {
            s[i] = (*it) ? '1' : '0';
            ++i;
        }
        return s;
    }
 
    // little-endian
    // LSB = string[0]
    // MSB = string[N]
 
    std::string to_byte_string()
    {
        // number of bytes needed is ceil(size() / 8)
        std::string s(this->size() / 8 + (this->size() % 8 ? 1 : 0), 0);
 
        for (size_type i = 0, n = this->size(); i < n; ++i)
            s[i / 8] |= static_cast<char>((*this)[i] << (i % 8));
 
        return s;
    }
 
    size_t to_byte_string(char* buf, size_t max_len)
    {
        // number of bytes needed is ceil(size() / 8)
        size_t len = this->size() / 8 + (this->size() % 8 ? 1 : 0);
 
        if (max_len < len)
        {
            throw std::length_error("max_len must be >= len");
        }
 
        // initialize buffer to all zeroes
        std::fill_n(buf, len, 0);
 
        for (size_type i = 0, n = this->size(); i < n; ++i)
            buf[i / 8] |= static_cast<char>((*this)[i] << (i % 8));
 
        return len;
    }
 
    void from_byte_string(const std::string& s) { from_byte_stream(s.begin(), s.end()); }
 
    template <typename CharIterator> void from_byte_stream(CharIterator begin, CharIterator end)
    {
        this->resize(std::distance(begin, end) * 8);
        int i = 0;
        for (CharIterator it = begin; it != end; ++it)
        {
            for (size_type j = 0; j < 8; ++j) (*this)[i * 8 + j] = (*it) & (1 << j);
            ++i;
        }
    }
 
    Bitset& prepend(const Bitset& bits)
    {
        for (auto it = bits.rbegin(), n = bits.rend(); it != n; ++it) push_front(*it);
 
        return *this;
    }
 
    Bitset& append(const Bitset& bits)
    {
        for (bool bit : bits) push_back(bit);
 
        return *this;
    }
 
  private:
    Bitset relinquish_bits(size_type num_bits, bool final_child);
 
  private:
    Bitset* parent_;
};
 
inline bool operator==(const Bitset& a, const Bitset& b)
{
    return (a.size() == b.size()) && std::equal(a.begin(), a.end(), b.begin());
}
 
inline bool operator<(const Bitset& a, const Bitset& b)
{
    for (int i = (std::max(a.size(), b.size()) - 1); i >= 0; --i)
    {
        bool a_bit = (i < static_cast<int>(a.size())) ? a[i] : 0;
        bool b_bit = (i < static_cast<int>(b.size())) ? b[i] : 0;
 
        if (a_bit > b_bit)
            return false;
        else if (a_bit < b_bit)
            return true;
    }
    return false;
}
 
inline Bitset operator&(const Bitset& b1, const Bitset& b2)
{
    Bitset out(b1);
    out &= b2;
    return out;
}
 
inline Bitset operator|(const Bitset& b1, const Bitset& b2)
{
    Bitset out(b1);
    out |= b2;
    return out;
}
 
inline Bitset operator^(const Bitset& b1, const Bitset& b2)
{
    Bitset out(b1);
    out ^= b2;
    return out;
}
 
inline std::ostream& operator<<(std::ostream& os, const Bitset& b) { return (os << b.to_string()); }
 
} // namespace dccl
 
inline void dccl::Bitset::get_more_bits(size_type num_bits) { relinquish_bits(num_bits, true); }
 
#endif