Random IRC quote :      <Dreg> katypersky pero si se calcifican es mejor para la esteoporosis no?

My C++ sparse BitSet

Hace unas semanas me pidieron que implementase un mapa de bits en C++. La especificacion no tenia limitaciones mas alla de la eleccion del lenguaje de programacion… Asi que era un buen momento para hacer alguna implementacion «creativa».

Hace algunos años implemente una sparse matrix para almacenar sistemas de ecuaciones. Estos sistemas de ecuaciones solian tener muchos coeficientes nulos, por lo que las sparse matrix eran la opcion ideal. Esta representacion siempre me ha gustado, asi que cuando me propusieron implementar un mapa de bits, no me lo pense dos veces. Un Sparse BitSet, al que he llamado BitField.

Es evidente que la unica ventaja que tiene esta clase es el ahorro de espacio en mapas de bits que tengan muchos 0’s. Por contra, no tiene ninguna de las ventajas que se le presuponen a estructuras de datos de acceso secuancial, como el tiempo de acceso constante a los elementos. Por otro lado, la STL, Boost, etc. ya tienen su propia implementacion de mapas de bits.

Bueno, para no liarme mas, este es el resultado :o)

#define INT_BIT   (sizeof(int) * CHAR_BIT)

class BitField
{
public:

  class BitFieldReference
  {
  public:
               
    BitFieldReference(BitField & _BitField, size_t _Position)
    : m_BitField(_BitField), m_Position(_Position)
    {
    }

    BitFieldReference& operator = (bool _Value)
    {
      if(_Value)
      {
        m_BitField.set(m_Position);
      }
      else
      {
        m_BitField.clear(m_Position);
      }
      return *this;
    }

    BitFieldReference& operator = (const BitFieldReference& _BitFieldReference)
    {
      *this = _BitFieldReference.test();
      return *this;
    }

    bool test() const
    {
      return m_BitField.test(m_Position);
    }

    void set()
    {
      m_BitField.set(m_Position);
    }

    void clear()
    {
      m_BitField.clear(m_Position);
    }

    void flip()
    {
      m_BitField.flip(m_Position);
    }

  private:

    BitField &m_BitField;
    size_t m_Position;
  };

  BitField()
  {
    clear();
  }

  BitField(size_t _Size)
  {
    clear();
    m_Size = _Size;
  }

  BitField(const string & _str)
  {
    load_from_string(_str);
  }

  bool operator[](size_t _Position) const
  {
    return test(_Position);
  }

  BitFieldReference operator[](size_t _Position)
  {
    return (BitFieldReference(*this, _Position));
  }

  BitField& operator &= (const BitField & _Right)
  {
    unsigned int Length = min(_Right.length(), length());

    if(Length > 0)
    {
      map<int, int>::const_iterator citr = _Right.m_BitField.begin();
      int LastPos = (Length-1) / INT_BIT;
      int Pos = 0;

      for(citr = _Right.m_BitField.begin(); citr != _Right.m_BitField.end() && citr->first <= LastPos; citr++)
      {
        int bits = min(Length – citr->first * INT_BIT, INT_BIT);
        int newValue;

        while(Pos < citr->first)
        {
          remove_key(Pos++);
        }
        ++Pos;

        newValue = (bits == INT_BIT) ? citr->second : (citr->second & (1 << bits) -1);
        m_BitField[citr->first] &= newValue;
        if(m_BitField[citr->first] == 0)
        {
          remove_key(citr->first);
        }
      }
    }
    return *this;
  }

  BitField& operator |= (const BitField & _Right)
  {
    unsigned int Length = min(_Right.length(), length());

    if(Length > 0)
    {
      map<int, int>::const_iterator citr = _Right.m_BitField.begin();
      int LastPos = (Length-1) / INT_BIT;

      for(citr = _Right.m_BitField.begin(); citr != _Right.m_BitField.end() && citr->first <= LastPos; citr++)
      {
        int bits = min(Length – citr->first * INT_BIT, INT_BIT);
        int newValue;

        newValue = (bits == INT_BIT) ? citr->second : (citr->second & (1 << bits) -1);
        if(newValue != 0)
        {
          m_BitField[citr->first] |= newValue;
        }
      }
    }
    return *this;
  }

  BitField& operator ^= (const BitField & _Right)
  {
   
    unsigned int Length = min(_Right.length(), length());

    if(Length > 0)
    {
      map<int, int>::const_iterator citr = _Right.m_BitField.begin();
      int LastPos = (Length-1) / INT_BIT;

      for(citr = _Right.m_BitField.begin(); citr != _Right.m_BitField.end() && citr->first <= LastPos; citr++)
      {
        int bits = min(Length – citr->first * INT_BIT, INT_BIT);
        int NewValue;

        NewValue = (bits == INT_BIT) ? citr->second : (citr->second & (1 << bits) -1);
        m_BitField[citr->first] ^= NewValue;
        if(m_BitField[citr->first] == 0)
        {
          remove_key(citr->first);
        }
      }
    }
    return *this;
  }

  void resize(size_t _Size)
  {
    if(_Size == 0)
    {
      clear();
    }
    else
    {
      if(_Size < m_Size && !m_BitField.empty())
      {
        map<int,int>::iterator itr = –m_BitField.end();
        int Position = (_Size – 1) / INT_BIT;

        while(!m_BitField.empty() && itr->first > Position)
        {
          m_BitField.erase(itr–);
        }

        if(itr->first == Position)
        {
          int bits = _Size % INT_BIT;

          itr->second &= (1 << bits) -1;

          if(itr->second == 0)
          {
            m_BitField.erase(itr);
          }
        }
      }
    }
    m_Size = _Size;
  }

  size_t length() const
  {
    return m_Size;
  }

  void clear()
  {
    m_BitField.clear();
    m_Size = 0;
  }

  bool test(size_t _Position) const
  {
    bool Result = false;

    if(_Position < m_Size)
    {
      map<int,int>::const_iterator itr;

      itr = m_BitField.find(_Position / INT_BIT);
      if(itr != m_BitField.end() && (itr->second & (1 << _Position % INT_BIT)) != 0)
      {
        Result = true;
      }
    }
    return Result;
  }

  void set(size_t _Position)
  {
    if(_Position < m_Size)
    {
      m_BitField[_Position / INT_BIT] |= 1 << _Position % INT_BIT;
    }
  }

  void clear(size_t _Position)
  {
    if(_Position < m_Size)
    {
      map<int,int>::iterator itr = m_BitField.find(_Position / INT_BIT);

      if(itr != m_BitField.end())
      {
        itr->second &= ~(1 << _Position % INT_BIT);

        if(itr->second == 0)
        {
          m_BitField.erase(itr);
        }
      }
    }
  }

  void flip(size_t _Position)
  {
    if(_Position < m_Size)
    {
      map<int,int>::iterator itr = m_BitField.find(_Position / INT_BIT);

      if(itr != m_BitField.end())
      {
        itr->second ^= 1 << _Position % INT_BIT;

        if(itr->second == 0)
        {
          m_BitField.erase(itr);
        }
      }
      else
      {
        set(_Position);
      }
    }
  }

  void load_from_string(const string & _str)
  {
    unsigned int strOffset = 0;

    clear();
    m_Size = _str.length();

    for(unsigned int Position = 0; Position <= m_Size / INT_BIT; Position++)
    {
      unsigned int Value = 0;
      unsigned int Offset;

      for(Offset = 0; Offset < INT_BIT && strOffset < m_Size; Offset++, strOffset++)
      {
        Value >>= 1;
        if(_str[strOffset] == ‘1’)
        {
          Value += (unsigned int) 1 << (INT_BIT – 1);
        }
      }

      Value >>= (INT_BIT – Offset);

      if(Value != 0)
      {
        m_BitField[Position] = Value;
      }
    }
  }

  void to_string(string & _str) const
  {
    int Position = 0;
    int Bits = m_Size;
    map<int,int>::const_iterator itr;

    _str.clear();

    for(itr = m_BitField.begin(); itr != m_BitField.end(); itr++)
    {
      int value = 1;

      while(itr->first > Position)
      {
        for(int i = 0 ; i < INT_BIT ; i++)
        {
          _str += ‘0’;
        }
        Bits -= INT_BIT;
        ++Position;
      }

      ++Position;
      value = 1;

      while(value != 0 && Bits > 0)
      {
        if((itr->second & value) != 0)
        {
          _str += ‘1’;
        }
        else
        {
          _str += ‘0’;
        }
        value <<= 1;
        –Bits;
      }
    }
    while(Bits–)
    {
      _str += ‘0’;
    }
  }

private:

  void remove_key(int _Key)
  {
    map<int, int>::iterator itr = m_BitField.find(_Key);
    if(itr != m_BitField.end())
    {
      m_BitField.erase(itr);
    }
  }

  map<int, int> m_BitField;
  size_t m_Size;
};
 

4 Comentarios para “My C++ sparse BitSet”

  1. Comment por Diego | 03/08/11 at 12:35 pm

    ¿Y la documentación de la clase? Porque sí, todos sabemos leer el código, pero la presentación en HTML en un navegador no es igual que en un editor.

    ¿Y tampoco nos vas a poner un ejemplo de su uso?

  2. Comment por Jesus Fernandez | 03/08/11 at 1:02 pm

    Buen trabajo, me ha resultado muy interesante.

  3. Comment por erg0t | 03/08/11 at 7:37 pm

    Quien lo pensaría Marconi tirando C++ en 48bits (donde quedaron esos dias donde escribias C++ solo en la intimidad? xDDD). Felicitaciones 🙂
    Luego mirare el codigo mas detalladamente (mi salud no me lo permite en este momento), mi unica recomendacion asi mirandolo por arriva sería utilizar ++interador en lugar de iterador++

  4. Comment por Nixon | 03/09/11 at 11:39 am

    Programar en C++ es de comunistas.

Se han cerrado los comentarios