bitArray.H

# ifndef BITARRAY_H
# define BITARRAY_H

# include <iostream>
# include <fstream>
# include <aleph.H>
# include <tpl_dynArray.H>

namespace Aleph {

class Byte
{
  unsigned int b0 : 1;
  unsigned int b1 : 1;
  unsigned int b2 : 1;
  unsigned int b3 : 1;
  unsigned int b4 : 1;
  unsigned int b5 : 1;
  unsigned int b6 : 1;
  unsigned int b7 : 1;

public:

  unsigned int read_bit(const unsigned int i) const
  {
    I(i < 8);

    switch (i)
      {
      case 0 : return b0;
      case 1 : return b1;
      case 2 : return b2;
      case 3 : return b3;
      case 4 : return b4;
      case 5 : return b5;
      case 6 : return b6;
      case 7 : return b7;
      default: throw std::out_of_range ("bit index greater than 7"); 
      }
  } 

  void write_bit(const unsigned int i, const unsigned int value)
  {
    I(i < 8);
    I(value <= 1);

    switch (i)
      {
      case 0 : b0 = value; break;
      case 1 : b1 = value; break;
      case 2 : b2 = value; break;
      case 3 : b3 = value; break;
      case 4 : b4 = value; break;
      case 5 : b5 = value; break;
      case 6 : b6 = value; break;
      case 7 : b7 = value; break;
      default: throw std::out_of_range ("bit index greater than 7"); 
      }
  } 

  Byte() : b0(0), b1(0), b2(0), b3(0), b4(0), b5(0), b6(0), b7(0) {}

  int get_int() const
  {
    const unsigned char * const ptr = (unsigned char*) this;
    return *ptr;
  }

  void set_int(int i)
  {
    unsigned char * ptr = (unsigned char*) this;
    *ptr = i;
  }
};

class BitArray
{
  size_t         current_size;
  DynArray<Byte> array_of_bytes; 

  size_t get_num_bytes() 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) :
      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 = NULL;
    }
    
    operator int () const 
    {
      if (index >= array->current_size)
        throw std::out_of_range("Index out of range");

      return byte_ptr != NULL ? byte_ptr->read_bit(bit_index) : 0; 
    }

    BitProxy & operator = (const size_t value)
    {
      I(value <= 1);

      if (byte_ptr == NULL)
        byte_ptr = &array->array_of_bytes.touch(byte_index);

      if (index >= array->current_size)
        array->current_size = index;

      byte_ptr->write_bit(bit_index, value);

      return *this;
    }

    BitProxy & operator = (const BitProxy & proxy)
    {
      if (byte_ptr == NULL)
        byte_ptr = &array->array_of_bytes.touch(byte_index);

      if (index >= array->current_size)
        array->current_size = index;

      byte_ptr->write_bit(bit_index, proxy.byte_ptr->read_bit(proxy.bit_index));

      return *this;
    }
  };

public:

  BitArray(const size_t dim = 0) throw(std::exception, std::bad_alloc) 
    : current_size(dim), array_of_bytes(get_num_bytes())
  {
    array_of_bytes.set_default_initial_value(Byte());
  }
  
  void reserve(size_t dim)
  {
    current_size = dim;

    int num_bytes = dim/8;
    if (dim % 8)
      ++num_bytes;
    
    array_of_bytes.reserve(num_bytes);
  }

  size_t size() const { return current_size; }

  void set_size(const size_t sz)
  {
    size_t array_size = sz / 8;
    if (array_size % 8)
      ++array_size;
    array_of_bytes.cut(array_size);
    current_size = sz;
  }

  BitProxy operator [] (const size_t i) const
  { 
    return BitProxy(const_cast<BitArray&>(*this), i);
  }

  BitProxy operator [] (const size_t i) { return BitProxy(*this, i); }

  int read_bit(const size_t i) const
  {
    if (i >= current_size)
      throw std::out_of_range("index out of range");

    const int bit_index = i % 8;
    const Byte byte = array_of_bytes[i/8];
    return byte.read_bit(bit_index);
  }

  void write_bit(const size_t i, const unsigned int value) 
  {
    array_of_bytes.touch(i/8).write_bit(i%8, value);
    if (i >= current_size)
      current_size = i + 1;
  }

  int read(const size_t i) const
  {
    if (i >= current_size)
      throw std::out_of_range("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) 
  {
    array_of_bytes.access(i/8).write_bit(i%8, value);
    if (i >= current_size)
      current_size = i + 1;
  }

  void push(const unsigned int value)
  {
    write_bit(current_size, value);
  }

  void pop()
  {
    current_size--;
    array_of_bytes.cut(get_num_bytes());
  }

  void empty()
  {
    current_size = 0;
    array_of_bytes.cut();
  }

  BitArray(const BitArray & array) throw(std::exception, std::bad_alloc)
    : current_size(array.current_size), array_of_bytes (array.array_of_bytes)
  { 
    // empty
  }

  void swap(BitArray & array)
  {
    std::swap(current_size, array.current_size);
    array_of_bytes.swap(array.array_of_bytes);
  }

  BitArray(BitArray && array) 
    : BitArray()
  {
    swap(array);
  }
                
  BitArray & operator = (BitArray && array)
  {
    current_size = 0;
    array_of_bytes.cut();
    swap(array);
    return *this;
  }

  DynList<char> bits_list() 
  {
    DynList<char> ret_val;
    for (size_t i = 0; i < current_size; ++i)
      ret_val.append((char) read_bit(i));
    return ret_val;
  }

  BitArray & operator = (const BitArray & array) 
    throw(std::exception, std::bad_alloc)
  {
    if (this == &array) 
      return *this;

    current_size = array.current_size;
    array_of_bytes = array.array_of_bytes;

    return *this;
  }

  void save(ofstream & output)
  {
    const size_t & num_bytes = array_of_bytes.size();

    output << num_bytes << " " << current_size << endl;

    for (size_t i = 0; i < num_bytes; i++)
      if (array_of_bytes.exist(i))
        {
          int byte = array_of_bytes.access(i).get_int();
          output << byte << " ";
        }
      else
        output << "0 ";

    output << endl;
  }

  void load(ifstream & input)
  {
    array_of_bytes.cut();

    size_t num_bytes = 0;
    input >> num_bytes >> current_size;
    for (size_t i = 0; i < num_bytes; i++)
      {
        int c;
        input >> c;
        array_of_bytes.touch(i).set_int(c);;
      }
  }

  BitArray(ifstream & input)
  {
    load(input);
  }

  void save_in_array_of_chars(const string & name, ofstream & output)
  {
    const size_t & num_bytes = array_of_bytes.size();

    output << "// " << current_size << " bits declaration" << endl
           << "const unsigned char " << name << " [" << num_bytes << "] = {" 
           << endl << "  ";
    for (size_t i = 0; i < num_bytes; i++)
      {
        if (array_of_bytes.exist(i))
          {
            int byte = array_of_bytes.access(i).get_int();
            output << byte;
          }
        else
          output << "0";

        if (i != num_bytes - 1)
          output << ", ";

        if ((i+1) % 15 == 0)
          output << endl << "  ";
      }
    output << endl << "};" << endl << endl;
  }

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

  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 (n >= current_size)
      {
        set_size(1);
        array_of_bytes.set_default_initial_value(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)
  {
    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)
  {
    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 - 1; i >= real_n; --i)
      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) // Paso copia porque es modificado adentro
  {                                                    
    empty();
    const size_t num_bits = sizeof(T) * 8;
    reserve(num_bits);
    for (int i = 0; i < num_bits; ++i)
      {
        write_bit(current_size - i - 1, n & 1);
        n >>= 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);
  }

  long get_num()
  {
    long ret_val = 0;
    for (int i = 0; i < current_size; ++i)
      ret_val += read_bit(current_size - i - 1) << i;
    return ret_val;                                   
  }

  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];
        I(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;
  }

  friend ostream & operator << (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);
  }
};

} // end namespace Aleph
# endif /* BITARRAY_H */