bitvector.h

#ifndef BF_BITVECTOR_H
#define BF_BITVECTOR_H

#include <iterator>
#include <limits>
#include <string>
#include <vector>

namespace bf {

class bitvector
{
  friend std::string to_string(bitvector const&, bool, size_t);

public:
  typedef size_t block_type;
  typedef size_t size_type;
  static size_type constexpr npos = static_cast<size_type>(-1);
  static block_type constexpr bits_per_block = 
    std::numeric_limits<block_type>::digits;

public:
  class reference
  {
    friend class bitvector;
    void operator&() = delete;

    reference(block_type& block, block_type i);

  public:
    reference& flip();
    operator bool() const;
    bool operator~() const;
    reference& operator=(bool x);
    reference& operator=(reference const& other);
    reference& operator|=(bool x);
    reference& operator&=(bool x);
    reference& operator^=(bool x);
    reference& operator-=(bool x);

  private:
    block_type& block_;
    block_type const mask_;
  };

  typedef bool const_reference;

  bitvector();

  explicit bitvector(size_type size, bool value = false);

  template <typename InputIterator>
  bitvector(InputIterator first, InputIterator last)
  {
    bits_.insert(bits_.end(), first, last);
    num_bits_ = bits_.size() * bits_per_block;
  }

  bitvector(bitvector const& other);

  bitvector(bitvector&& other);

  bitvector& operator=(bitvector other);

  friend void swap(bitvector x, bitvector y);

  //
  // Bitwise operations
  //
  bitvector operator~() const;
  bitvector operator<<(size_type n) const;
  bitvector operator>>(size_type n) const;
  bitvector& operator<<=(size_type n);
  bitvector& operator>>=(size_type n);
  bitvector& operator&=(bitvector const& other);
  bitvector& operator|=(bitvector const& other);
  bitvector& operator^=(bitvector const& other);
  bitvector& operator-=(bitvector const& other);
  friend bitvector operator&(bitvector const& x, bitvector const& y);
  friend bitvector operator|(bitvector const& x, bitvector const& y);
  friend bitvector operator^(bitvector const& x, bitvector const& y);
  friend bitvector operator-(bitvector const& x, bitvector const& y);

  //
  // Relational operators
  //
  friend bool operator==(bitvector const& x, bitvector const& y);
  friend bool operator!=(bitvector const& x, bitvector const& y);
  friend bool operator<(bitvector const& x, bitvector const& y);

  //
  // Basic operations
  //
  template <
    typename Iterator,
    typename std::enable_if<
      std::is_same<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::forward_iterator_tag
      >::value
    >::type = 0
  >
  void append(Iterator first, Iterator last)
  {
    if (first == last)
      return;

    auto excess = extra_bits();
    auto delta = std::distance(first, last);
    bits_.reserve(blocks() + delta);
    if (excess == 0)
    {
      bits_.back() |= (*first << excess);
      do
      {
        auto b = *first++ >> (bits_per_block - excess);
        bits_.push_back(b | (first == last ? 0 : *first << excess));
      } while (first != last);
    }
    else
    {
      bits_.insert(bits_.end(), first, last);
    }

    num_bits_ += bits_per_block * delta;
  }

  void append(block_type block);

  void push_back(bool bit);

  void clear() noexcept;

  void resize(size_type n, bool value = false);

  bitvector& set(size_type i, bool bit = true);

  bitvector& set();

  bitvector& reset(size_type i);

  bitvector& reset();

  bitvector& flip(size_type i);

  bitvector& flip();

  reference operator[](size_type i);

  const_reference operator[](size_type i) const;

  size_type count() const;

  size_type blocks() const;

  size_type size() const;

  bool empty() const;

  size_type find_first() const;

  size_type find_next(size_type i) const;

private:
  static size_type constexpr block_index(size_type i)
  {
    return i / bits_per_block;
  }

  static block_type constexpr bit_index(size_type i)
  {
    return i % bits_per_block;
  }

  static block_type constexpr bit_mask(size_type i)
  {
    return block_type(1) << bit_index(i);
  }

  static size_type constexpr bits_to_blocks(size_type bits)
  {
    return bits / bits_per_block 
      + static_cast<size_type>(bits % bits_per_block != 0);
  }

  static size_type lowest_bit(block_type block);

  block_type extra_bits() const;

  // If the number of bits in the vector are not not a multiple of
  // bitvector::bits_per_block, then the last block exhibits unused bits which
  // this function resets.
  void zero_unused_bits();

  size_type find_from(size_type i) const;

  std::vector<block_type> bits_;
  size_type num_bits_;
};

std::string to_string(bitvector const& b,
                      bool msb_to_lsb = true,
                      bool all = false,
                      size_t cut_off = 0);

} // namespace bf

#endif