bitset.h

// Copyright 2009-2017 Toby Schneider (http://gobysoft.org/index.wt/people/toby)
//                     GobySoft, LLC (for 2013-)
//                     Massachusetts Institute of Technology (for 2007-2014)
//                     Community contributors (see AUTHORS file)
//
//
// 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 <deque>
#include <algorithm>
#include <limits>
#include <string>
#include <cstring>

#include "exception.h"

namespace dccl
{
    class Bitset : public std::deque<bool>
    {
      public:
        explicit Bitset(Bitset* parent = 0)
            : parent_(parent)
        { }

        explicit Bitset(size_type num_bits, unsigned long value = 0, Bitset* parent = 0)
            : std::deque<bool>(num_bits, false),
            parent_(parent)
            { from(value, num_bits); }
        
        ~Bitset() { } 

        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] = (*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] = (*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] = (*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(iterator it = begin(), n = end(); it != n; ++it)
                *it = true;
            return *this;
        }
            
        Bitset& reset(size_type n)
        { return set(n, false);}

        Bitset& reset()
        {
            for(iterator it = begin(), n = end(); it != n; ++it)
                *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(Bitset::const_reverse_iterator 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(const_reverse_iterator it = bits.rbegin(),
                    n = bits.rend(); it != n; ++it)
                push_front(*it);

            return *this;
        }

        Bitset& append(const Bitset& bits)
        {
            for(const_iterator it = bits.begin(),
                    n = bits.end(); it != n; ++it)
                push_back(*it);                

            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());
    }

}

inline void dccl::Bitset::get_more_bits(size_type num_bits)
{
    relinquish_bits(num_bits, true);
}


#endif