store.h

#ifndef STORE_H
#define STORE_H

#include <cstdint>
#include <stdexcept>
#include <vector>
#include <boost/dynamic_bitset.hpp>

namespace bf {

template <typename Derived>
class store_policy
{
public:
    // TODO: decide on a reasonable interface.

private:
    //
    // CRTP interface
    //
    Derived& derived()
    {
        return *static_cast<Derived*>(this);
    }

    const Derived& derived() const
    {
        return *static_cast<const Derived*>(this);
    }
};

template <typename Block, typename Allocator>
class fixed_width : public store_policy<fixed_width<Block, Allocator>>
{
public:
    typedef Block block_type;
    typedef Allocator allocator_type;

    typedef boost::dynamic_bitset<Block, Allocator> bitset;
    typedef typename bitset::size_type size_type;
    typedef std::vector<size_type> pos_vector;
    typedef uint64_t count_type;

public:
    fixed_width(unsigned cells, unsigned width)
      : bits_(cells * width)
      , width_(width)
    {
        if (cells == 0)
            throw std::invalid_argument("zero cells");

        if (width == 0)
            throw std::invalid_argument("zero width");

        auto max = std::numeric_limits<count_type>::digits;
        if (width > static_cast<decltype(width)>(max))
            throw std::invalid_argument("width too large");
    }

    template <typename B, typename A>
    void swap(fixed_width<B, A>& store) // no throw
    {
        std::swap(bits_, store.bits_);
        std::swap(width_, store.width_);
    }

    bool increment(size_type cell)
    {
        assert(cell < size());

        size_type lsb = cell * width_;
        for (auto i = lsb; i < lsb + width_; ++i)
            if (! bits_[i])
            {
                bits_[i] = true;
                while (i && i > lsb)
                    bits_[--i] = false;

                return true;
            }

        return false;
    }

    bool increment(size_type cell, count_type value)
    {
        assert(cell < size());

        size_type lsb = cell * width_;

        if (value >= max())
        {
            bool r = false;
            for (auto i = lsb; i < lsb + width_; ++i)
                if (! bits_[i])
                {
                    bits_[i] = 1;
                    if (! r)
                        r = true;
                }

            return r;
        }

        bitset b(width_, value);
        bool carry = false;
        size_type i = lsb, j = 0;

        while (i < lsb + width_)
        {
            if (bits_[i])
            {
                if (b[j])
                {
                    bits_[i] = false;
                    if (! carry)
                        carry = true;
                }
                else if (carry)
                    bits_[i] = false;
            }
            else if (b[j])
            {
                bits_[i] = true;
            }
            else if (carry)
            {
                bits_[i] = true;
                carry = false;
            }

            ++i;
            ++j;
        }

        if (! carry)
            return true;

        for (i = lsb; i < lsb + width_; ++i)
            bits_[i] = 1;

        return false;
    }

    bool decrement(size_type cell)
    {
        assert(cell < size());

        size_type lsb = cell * width_;
        for (auto i = lsb; i < lsb + width_; ++i)
            if (bits_[i])
            {
                bits_[i] = false;

                while (i && i > lsb)
                    bits_[--i] = true;

                return true;
            }

        return false;
    }

    count_type count(size_type cell) const
    {
        assert(cell < size());

        count_type cnt = 0, order = 1;
        size_type lsb = cell * width_;
        for (auto i = lsb; i < lsb + width_; ++i, order <<= 1)
            if (bits_[i])
                cnt |= order;

        return cnt;
    }

    void set()
    {
        bits_.set();
    }

    void set(size_type cell)
    {
        assert(cell < size());

        auto lsb = cell * width_;
        for (auto i = lsb; i < lsb + width_; ++i)
            bits_[i] = true;
    }

    void set(size_type cell, count_type value)
    {
        assert(cell < size());
        assert(value <= max());

        bitset bits(width_, value);
        size_type i = cell * width_;
        for (auto bit : bits)
            bits_[i++] = bit;
    }

    void reset()
    {
        bits_.reset();
    }

    void reset(size_type cell)
    {
        assert(cell < size());

        auto lsb = cell * width_;
        for (auto i = lsb; i < lsb + width_; ++i)
            bits_[i] = false;
    }

    void halve()
    {
        assert(bits_.size() % 2 == 0);
        assert(bits_.size() > 0);

        size_type half = bits_.size() / 2;
        size_type i = 0;
        size_type j = half;

        while (i < half)
            set(i, count(i) + count(j));

        bits_.resize(half * width_);
    }

    size_type size() const
    {
        return bits_.size() / width_;
    }

    count_type max() const
    {
        return std::numeric_limits<count_type>::max() >>
            (std::numeric_limits<count_type>::digits - width());
    }

    bool none() const
    {
        return bits_.none();
    }

    unsigned width() const
    {
        return width_;
    }

    void width(unsigned w)
    {
        assert(! "not yet tested");

        if (w < width_)
        {
            size_type i = 0;
            for (auto cell = 0; cell < bits_.size(); cell += width_)
                if (bits_[cell + width_])
                    for (auto j = 0; j < w; ++j)
                        bits_[i++] = true;
                else
                    for (auto j = 0; j < w; ++j)
                        bits_[i++] = bits_[cell + j];

            bits_.resize(w * bits_.size());
        }
        else
        {
            auto old = bits_.size();
            bits_.resize(w * bits_.size());
            auto i = bits_.size() / w - 1;

            for (auto cell = old - width_ - 1; cell != 0; cell -= width_)
            {
                size_type j = 0;
                while (j++ < width_)
                    bits_[i++] = bits_[cell + j];
                while (j++ < w)
                    bits_[i++] = 0;

                i -= width_;
            }
        }

        width_ = w;
    }

    std::string to_string() const
    {
        std::string str(bits_.size(), '0');
        for (size_type i = 0; i < bits_.size(); ++i)
            if (bits_[i])
                str[i] = '1';

        return str;
    }

    template <typename F>
    void each(F f) const
    {
        for (size_type cell = 0; cell < bits_.size() / width_; ++cell)
            f(count(cell));
    }

private:
    bitset bits_;
    unsigned width_;
};

} // namespace bf

#endif