bitArray.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef BITARRAY_H
# define BITARRAY_H
 
# include <bit>
# include <cstdint>
# include <iostream>
# include <fstream>
# include <algorithm>
# include <type_traits>
# include <aleph.H>
# include <tpl_dynArray.H>
# include <ah-errors.H>
# include <ahDry.H>
# include <ah-dry-mixin.H>
 
namespace Aleph
{
  class Byte
  {
    std::uint8_t value = 0;
 
  public:
    [[nodiscard]] unsigned int read_bit(const unsigned int i) const noexcept
    {
      assert(i < 8);
      return (value >> i) & 0x1;
    }
 
    void write_bit(const unsigned int i, const unsigned int val) noexcept
    {
      assert(i < 8);
      assert(val <= 1);
      const std::uint8_t mask = static_cast<std::uint8_t>(1) << i;
      const auto bit = static_cast<std::uint8_t>(val & 0x1u);
      this->value = (this->value & ~mask) | (bit << i);
    }
 
    Byte() noexcept = default;
 
    [[nodiscard]] int get_int() const noexcept
    {
      return static_cast<int>(value);
    }
 
    void set_int(int i) noexcept
    {
      value = static_cast<std::uint8_t>(i);
    }
 
    Byte &operator|=(const Byte & rhs) noexcept
    {
      value |= rhs.value;
      return *this;
    }
 
    Byte &operator&=(const Byte & rhs) noexcept
    {
      value &= rhs.value;
      return *this;
    }
 
    [[nodiscard]] int count_ones() const noexcept
    {
      return std::popcount(value);
    }
 
    [[nodiscard]] int count_zeros() const noexcept
    {
      return 8 - count_ones();
    }
  };
 
  class BitArray : public FunctionalMixin<BitArray, unsigned int>
  {
    size_t current_size;
    DynArray<Byte> array_of_bytes;
 
    void clear_unused_bits_in_last_byte() noexcept
    {
      if (current_size == 0)
        return;
 
      const size_t used_bits_in_last_byte = current_size % 8;
      if (used_bits_in_last_byte == 0)
        return;
 
      const size_t last_byte_index = current_size / 8;
      Byte *last_byte = array_of_bytes.test(last_byte_index);
      if (last_byte == nullptr)
        return;
 
      const int mask = (1u << used_bits_in_last_byte) - 1u;
      last_byte->set_int(last_byte->get_int() & mask);
    }
 
    void ensure_num_bytes(const size_t num_bytes)
    {
      if (num_bytes == 0)
        {
          array_of_bytes.cut();
          return;
        }
 
      if (array_of_bytes.size() < num_bytes)
        array_of_bytes.touch(num_bytes - 1);
    }
 
    size_t get_num_bytes() const noexcept
    {
      const size_t div = current_size / 8;
 
      return (current_size % 8) != 0 ? div + 1 : div;
    }
 
    class BitProxy
    {
      const size_t index;
      const size_t bit_index;
      const size_t byte_index;
      BitArray *array;
      Byte *byte_ptr;
 
    public:
      BitProxy(BitArray & a, const size_t i) noexcept
        : index(i), bit_index(i % 8), byte_index(i / 8), array(&a)
      {
        if (array->array_of_bytes.exist(byte_index))
          byte_ptr = &array->array_of_bytes.access(byte_index);
        else
          byte_ptr = nullptr;
      }
 
      operator int() const
      {
        ah_out_of_range_error_if(index >= array->current_size) << "Index out of range";
 
        return byte_ptr != nullptr ? byte_ptr->read_bit(bit_index) : 0;
      }
 
      BitProxy &operator=(const size_t value)
      {
        assert(value <= 1);
 
        if (byte_ptr == nullptr)
          byte_ptr = &array->array_of_bytes.touch(byte_index);
 
        const bool grew = index >= array->current_size;
        if (grew)
          array->current_size = index + 1;
 
        byte_ptr->write_bit(bit_index, value);
 
        if (grew)
          array->clear_unused_bits_in_last_byte();
 
        return *this;
      }
 
      BitProxy &operator=(const BitProxy & proxy)
      {
        if (byte_ptr == nullptr)
          byte_ptr = &array->array_of_bytes.touch(byte_index);
 
        const bool grew = index >= array->current_size;
        if (grew)
          array->current_size = index + 1;
 
        const int rhs_value = proxy;
        byte_ptr->write_bit(bit_index, rhs_value);
 
        if (grew)
          array->clear_unused_bits_in_last_byte();
 
        return *this;
      }
    };
 
  public:
    using Item_Type = unsigned int;
 
    BitArray(const size_t dim = 0)
      : current_size(dim), array_of_bytes(get_num_bytes())
    {
      array_of_bytes.set_default_initial_value(Byte());
    }
 
    BitArray(const size_t dim, const unsigned int value)
      : BitArray(dim)
    {
      assert(value <= 1);
      for (size_t i = 0; i < dim; ++i)
        write_bit(i, value);
    }
 
    void reserve(const size_t dim)
    {
      set_size(dim);
    }
 
    [[nodiscard]] constexpr size_t size() const noexcept { return current_size; }
 
    void set_size(const size_t sz)
    {
      const size_t old_size = current_size;
      const size_t array_size = (sz + 7) / 8;
 
      array_of_bytes.adjust(array_size); // allocate for fast read()/write()
      current_size = sz;
 
      if (sz > old_size && old_size != 0)
        if (const size_t rem = old_size % 8; rem != 0)
          {
            const size_t clear_end = std::min(sz, old_size + (8 - rem));
            for (size_t i = old_size; i < clear_end; ++i)
              write_bit(i, 0);
          }
 
      clear_unused_bits_in_last_byte();
    }
 
    int operator[](const size_t i) const { return read_bit(i); }
 
    BitProxy operator[](const size_t i) noexcept { return BitProxy(*this, i); }
 
    int read_bit_ne(const size_t i) const noexcept
    {
      const unsigned int bit_index = static_cast<unsigned int>(i % 8);
      if (const auto ptr = array_of_bytes.test(i / 8))
        {
          const Byte & byte = *ptr;
          return byte.read_bit(bit_index);
        }
      return 0;
    }
 
    int read_bit(const size_t i) const
    {
      ah_out_of_range_error_if(i >= current_size) << "index out of range";
      return read_bit_ne(i);
    }
 
    int operator()(const size_t i) const { return read_bit(i); }
 
    void write_bit(const size_t i, const unsigned int value)
    {
      ah_out_of_range_error_if(value > 1) << "BitArray::write_bit: value must be 0 or 1";
      array_of_bytes.touch(i / 8).write_bit(i % 8, value);
      if (i >= current_size)
        {
          current_size = i + 1;
          clear_unused_bits_in_last_byte();
        }
    }
 
    int read(const size_t i) const
    {
      ah_out_of_range_error_if(i >= current_size) << "index out of range";
 
      const int bit_index = i % 8;
      return array_of_bytes.access(i / 8).read_bit(bit_index);
    }
 
    void write(const size_t i, const unsigned int value)
    {
      ah_out_of_range_error_if(value > 1) << "BitArray::write: value must be 0 or 1";
 
      array_of_bytes.access(i / 8).write_bit(i % 8, value);
      if (i >= current_size)
        {
          current_size = i + 1;
          clear_unused_bits_in_last_byte();
        }
    }
 
    int fast_read(const size_t i) const noexcept
    {
      return array_of_bytes.access(i / 8).read_bit(i % 8);
    }
 
    void fast_write(const size_t i, const unsigned int value)
    {
      ah_out_of_range_error_if(value > 1) << "BitArray::fast_write: value must be 0 or 1";
      array_of_bytes.access(i / 8).write_bit(i % 8, value);
    }
 
    void push(const unsigned int value)
    {
      write_bit(current_size, value);
    }
 
    void pop()
    {
      ah_underflow_error_if(current_size == 0) << "BitArray::pop on empty array";
      current_size--;
      array_of_bytes.cut(get_num_bytes());
      clear_unused_bits_in_last_byte();
    }
 
    void empty() noexcept
    {
      current_size = 0;
      array_of_bytes.cut();
    }
 
    BitArray(const BitArray & array)
      : current_size(array.current_size), array_of_bytes(array.array_of_bytes)
    {
      // empty
    }
 
    void swap(BitArray & array) noexcept
    {
      std::swap(current_size, array.current_size);
      array_of_bytes.swap(array.array_of_bytes);
    }
 
    BitArray(BitArray && array) noexcept
      : BitArray()
    {
      swap(array);
    }
 
    BitArray &operator=(BitArray && array) noexcept
    {
      current_size = 0;
      array_of_bytes.cut();
      swap(array);
      return *this;
    }
 
    DynList<char> bits_list() const
    {
      DynList<char> ret_val;
      for (size_t i = 0; i < current_size; ++i)
        ret_val.append(static_cast<char>(read_bit(i)));
      return ret_val;
    }
 
    BitArray &operator=(const BitArray & array)
    {
      if (this == &array)
        return *this;
 
      current_size = array.current_size;
      array_of_bytes = array.array_of_bytes;
 
      return *this;
    }
 
    void save(std::ostream & output) const
    {
      const size_t num_bytes = get_num_bytes();
 
      // Header
      output << num_bytes << " " << current_size << '\n';
      ah_runtime_error_if(not output) << "BitArray::save: write failed (header)";
 
      // Payload
      for (size_t i = 0; i < num_bytes; ++i)
        {
          int byte = 0;
          if (const Byte *p = array_of_bytes.test(i); p != nullptr)
            byte = p->get_int();
 
          // defend export invariant last masked byte
          if (num_bytes != 0 && i + 1 == num_bytes)
            if (const size_t used = current_size % 8; used != 0)
              {
                const int mask = (1u << used) - 1u;
                byte &= mask;
              }
 
          output << byte << " ";
          ah_runtime_error_if(not output)
            << "BitArray::save: write payload failed (byte " << i << ")";
        }
 
      output << '\n';
      ah_runtime_error_if(not output) << "BitArray::save: write failed (newline)";
    }
 
    void load(std::istream & input)
    {
      // Read header first (without touching the current state until validated)
      size_t num_bytes = 0;
      size_t num_bits = 0;
 
      ah_runtime_error_if(not (input >> num_bytes >> num_bits)) << "BitArray::load: read failed (header)";
 
      const size_t expected = (num_bits + 7) / 8;
      ah_runtime_error_if(num_bytes != expected)
        << "BitArray::load: inconsistent header (num_bytes vs num_bits)";
 
      // Heavy Load: build temporary and then swap
      BitArray tmp;
      tmp.current_size = num_bits;
      tmp.array_of_bytes.cut();
      tmp.ensure_num_bytes(num_bytes);
 
      for (size_t i = 0; i < num_bytes; ++i)
        {
          long v = 0;
          ah_runtime_error_if(not (input >> v)) << "BitArray::load: read failed (payload)";
          ah_runtime_error_if(v < 0 or v > 255) << "BitArray::load: byte value out of range";
 
          tmp.array_of_bytes.touch(i).set_int(static_cast<int>(v));
        }
 
      tmp.clear_unused_bits_in_last_byte();
      swap(tmp);
    }
 
    BitArray(std::ifstream & input)
    {
      load(input);
    }
 
    void save_in_array_of_chars(const std::string & name, std::ostream & output) const
    {
      const size_t num_bytes = get_num_bytes();
 
      output << "// " << current_size << " bits declaration" << '\n'
          << "const unsigned char " << name << " [" << num_bytes << "] = {"
          << '\n' << "  ";
 
      for (size_t i = 0; i < num_bytes; i++)
        {
          int byte = 0;
          if (const Byte *p = array_of_bytes.test(i); p != nullptr)
            byte = p->get_int();
 
          if (num_bytes != 0 && i + 1 == num_bytes)
            if (const size_t used = current_size % 8; used != 0)
              {
                const int mask = (1u << used) - 1u;
                byte &= mask;
              }
 
          output << byte;
 
          if (i != num_bytes - 1)
            output << ", ";
 
          if ((i + 1) % 15 == 0)
            output << '\n' << "  ";
        }
 
      output << '\n' << "};" << '\n' << '\n';
    }
 
    void load_from_array_of_chars(const unsigned char str[],
                                  const size_t num_bits)
    {
      array_of_bytes.cut();
 
      size_t num_bytes = num_bits / 8;
 
      if (num_bits % 8 != 0)
        num_bytes++;
 
      for (size_t i = 0; i < num_bytes; i++)
        array_of_bytes.touch(i).set_int(str[i]);
 
      current_size = num_bits;
      clear_unused_bits_in_last_byte();
    }
 
    void left_shift(const size_t n = 1)
    {
      const size_t real_n = std::min<size_t>(n, current_size);
 
      for (size_t i = 0; i < current_size - real_n; ++i)
        write_bit(i, read_bit(i + real_n));
 
      for (size_t i = current_size - real_n; i < current_size; ++i)
        write_bit(i, 0);
    }
 
    void right_shift(const size_t n = 1)
    {
      const size_t real_n = std::min<size_t>(n, current_size);
 
      for (size_t i = current_size; i > real_n; --i)
        write_bit(i - 1, read_bit(i - real_n - 1));
 
      for (size_t i = real_n; i > 0; --i)
        write_bit(i - 1, 0);
    }
 
    void dyn_left_shift(const size_t n = 1)
    {
      for (size_t i = 0; i < n; ++i)
        push(0);
    }
 
    void dyn_right_shift(const size_t n = 1)
    {
      if (current_size == 0)
        return;
 
      if (n >= current_size)
        {
          set_size(1);
          write_bit(0, 0);
          clear_unused_bits_in_last_byte();
          return;
        }
 
      BitArray array(current_size - n);
 
      for (size_t i = 0; i < current_size - n; ++i)
        array.write_bit(i, read_bit(i));
 
      *this = array;
    }
 
    void circular_left_shift(const size_t n = 1)
    {
      if (current_size < 2)
        return;
 
      const size_t real_n = n % current_size;
 
      if (real_n == 0)
        return;
 
      BitArray array(real_n);
 
      for (size_t i = 0; i < real_n; ++i)
        array.write_bit(i, read_bit(i));
 
      for (size_t i = 0; i < current_size - real_n; ++i)
        write_bit(i, read_bit(i + real_n));
 
      for (size_t i = 0; i < real_n; ++i)
        write_bit(current_size - real_n + i, array.read_bit(i));
    }
 
    void circular_right_shift(const size_t n = 1)
    {
      if (current_size < 2)
        return;
 
      const size_t real_n = n % current_size;
 
      if (real_n == 0)
        return;
 
      BitArray array(real_n);
 
      for (size_t i = current_size - real_n; i < current_size; ++i)
        array.write_bit(i - (current_size - real_n), read_bit(i));
 
      for (size_t i = current_size; i-- > real_n;)
        write_bit(i, read_bit(i - real_n));
 
      for (size_t i = 0; i < real_n; ++i)
        write_bit(i, array.read_bit(i));
    }
 
    template <typename T>
    void set_num(T n) // Copy step because it is modified inside
    {
      using U = std::make_unsigned_t<T>;
      U u = static_cast<U>(n);
      empty();
      const size_t num_bits = sizeof(T) * 8;
      reserve(num_bits);
      for (size_t i = 0; i < num_bits; ++i)
        {
          write_bit(current_size - i - 1, u & 1u);
          u >>= 1;
        }
    }
 
    void set_num(const char & c)
    {
      set_num<char>(c);
    }
 
    void set_num(const short & c)
    {
      set_num<short>(c);
    }
 
    void set_num(const int & c)
    {
      set_num<int>(c);
    }
 
    void set_num(const long & c)
    {
      set_num<long>(c);
    }
 
    unsigned long get_unum() const noexcept
    {
      using UL = unsigned long;
      constexpr size_t max_bits = sizeof(UL) * 8;
      const size_t n = std::min(current_size, max_bits);
 
      UL ret_val = 0;
      for (size_t i = 0; i < n; ++i)
        ret_val |= static_cast<UL>(read_bit_ne(current_size - i - 1)) << i;
      return ret_val;
    }
 
    long get_num() const noexcept
    {
      return static_cast<long>(get_unum());
    }
 
    void set_bit_str(const std::string & str)
    {
      empty();
      const size_t & str_size = str.size();
 
      reserve(str_size);
 
      for (size_t i = 0; i < str_size; ++i)
        {
          char c = str[i];
          assert(c == '1' or c == '0');
          write_bit(i, (c == '0' ? 0 : 1));
        }
    }
 
    std::string get_bit_str() const
    {
      std::string ret_val;
      for (size_t i = 0; i < current_size; ++i)
        ret_val.append(read_bit(i) == 0 ? "0" : "1");
 
      return ret_val;
    }
 
    std::string to_string() const
    {
      return get_bit_str();
    }
 
    friend std::ostream &operator<<(std::ostream & out, const BitArray & array)
    {
      for (size_t i = 0; i < array.current_size; ++i)
        out << array.read_bit(i);
      return out;
    }
 
    BitArray(const unsigned char str[], const size_t num_bits)
    {
      load_from_array_of_chars(str, num_bits);
    }
 
    BitArray &operator|=(const BitArray & rhs)
    {
      if (rhs.size() > current_size)
        {
          current_size = rhs.size();
          ensure_num_bytes(get_num_bytes());
        }
 
      const size_t rhs_num_bytes = (rhs.size() + 7) / 8;
      const size_t rhs_used_bits_in_last_byte = rhs.size() % 8;
      for (size_t i = 0; i < rhs_num_bytes; ++i)
        {
          const Byte *rhs_byte = rhs.array_of_bytes.test(i);
          if (rhs_byte == nullptr)
            continue;
 
          Byte masked = *rhs_byte;
          if (rhs_used_bits_in_last_byte != 0 && i + 1 == rhs_num_bytes)
            {
              const int mask = (1u << rhs_used_bits_in_last_byte) - 1u;
              masked.set_int(masked.get_int() & mask);
            }
 
          if (masked.get_int() == 0)
            continue;
 
          array_of_bytes.touch(i) |= masked;
        }
 
      clear_unused_bits_in_last_byte();
      return *this;
    }
 
    BitArray &operator&=(const BitArray & rhs)
    {
      if (const size_t new_size = std::min(size(), rhs.size()); new_size != current_size)
        {
          current_size = new_size;
          array_of_bytes.cut(get_num_bytes());
        }
 
      const size_t num_bytes = get_num_bytes();
      for (size_t i = 0; i < num_bytes; ++i)
        {
          Byte *lhs_byte = array_of_bytes.test(i);
          if (lhs_byte == nullptr)
            continue;
 
          if (const Byte *rhs_byte = rhs.array_of_bytes.test(i); rhs_byte == nullptr)
            lhs_byte->set_int(0);
          else
            *lhs_byte &= *rhs_byte;
        }
 
      clear_unused_bits_in_last_byte();
      return *this;
    }
 
    friend BitArray operator|(const BitArray & op1, const BitArray & op2)
    {
      BitArray ret = op1;
      ret |= op2;
      return ret;
    }
 
    friend BitArray operator&(const BitArray & op1, const BitArray & op2)
    {
      BitArray ret = op1;
      ret &= op2;
      return ret;
    }
 
    bool operator==(const BitArray & rhs) const
    {
      if (size() != rhs.size())
        return false;
 
      for (size_t i = 0; i < size(); ++i)
        if (read_bit(i) != rhs.read_bit(i))
          return false;
 
      return true;
    }
 
  private:
    template <class Operation>
    bool __traverse(Operation & operation)
    {
      for (size_t i = 0; i < current_size; ++i)
        if (not operation(read_bit(i)))
          return false;
      return true;
    }
 
  public:
    class Iterator
    {
      BitArray *array_ptr = nullptr;
      long curr_idx = 0;
 
    public:
      Iterator() = default;
 
      Iterator(const BitArray & array) noexcept
        : array_ptr(const_cast<BitArray *>(&array)), curr_idx(0)
      {
        // empty
      }
 
      [[nodiscard]] bool has_curr() const noexcept
      {
        return array_ptr != nullptr and curr_idx >= 0 and
               static_cast<size_t>(curr_idx) < array_ptr->size();
      }
 
      [[nodiscard]] unsigned int get_curr_ne() const noexcept
      {
        return has_curr() ? array_ptr->read_bit_ne(static_cast<size_t>(curr_idx)) : 0;
      }
 
      [[nodiscard]] unsigned int get_curr() const
      {
        ah_overflow_error_if(not has_curr())
          << "Iterator is at the end of the list";
        return array_ptr->read_bit(static_cast<size_t>(curr_idx));
      }
 
      [[nodiscard]] long get_pos() const noexcept { return curr_idx; }
 
      void next_ne() noexcept { ++curr_idx; }
 
      void next()
      {
        ah_overflow_error_if(array_ptr == nullptr) << "Iterator is not bound to any BitArray";
        ah_overflow_error_if(curr_idx == static_cast<long>(array_ptr->size()))
          << "not current item in iterator";
        next_ne();
      }
 
      void prev_ne() noexcept { --curr_idx; }
 
      void prev()
      {
        ah_underflow_error_if(array_ptr == nullptr) << "Iterator is not bound to any BitArray";
        ah_underflow_error_if(curr_idx == -1) << "not current item in iterator";
        prev_ne();
      }
 
      void reset_last() noexcept
      {
        if (array_ptr == nullptr or array_ptr->size() == 0)
          curr_idx = -1;
        else
          curr_idx = static_cast<long>(array_ptr->size()) - 1;
      }
 
      void end() noexcept
      {
        if (array_ptr == nullptr)
          {
            curr_idx = 0;
            return;
          }
        curr_idx = static_cast<long>(array_ptr->size());
      }
 
      void reset_first() noexcept { curr_idx = 0; }
 
      void reset() noexcept { reset_first(); }
    };
 
    auto get_it() const noexcept { return Iterator(*this); }
 
    template <class Operation>
    bool traverse(Operation & operation) const
    {
      return const_cast<BitArray &>(*this).__traverse(operation);
    }
 
    template <class Operation>
    bool traverse(Operation & operation)
    {
      return __traverse(operation);
    }
 
    template <class Operation>
    bool traverse(Operation && operation = Operation()) const
    {
      return traverse<Operation>(operation);
    }
 
    template <class Operation>
    bool traverse(Operation && operation = Operation())
    {
      return traverse<Operation>(operation);
    }
 
    // Functional methods provided by FunctionalMixin<BitArray, unsigned int>
 
    Generic_Items(unsigned int);
 
    STL_ALEPH_ITERATOR(BitArray);
 
    int count_ones() const noexcept
    {
      return foldl<int>(0, [](int acc, int x) { return acc + x; });
    }
 
    int count_zeros() const noexcept
    {
      return foldl<int>(0, [](int acc, int x) { return acc + (x == 0); });
    }
  };
} // end namespace Aleph
# endif /* BITARRAY_H */