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