SparseBoolVector.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <alib/list>
#include <alib/tuple>
#include <alib/vector>
 
/* Canonical representation kept by all operations is in form of blocks of pairs run and word, where each word must contain at least one set bit, with exception of the last word.
 * Empty sequence of bits is represented by empty list of elements and size equal to zero.
 * If the size of the representation is divisible by sizeof ( unsigned ) * BITS_IN_BYTE then the last block must either be of nonzero run or its word must contain at least one set bit. This is not with contradiction with the first line.
 *
 * Examples:
 *                  least significant bit
 *                  v
 *   size = 32 [(0, 00000000000000000000000000000000)] is representing 32 times zero
 *   size = 32 [(0, 00000000000000000000000000000001)] is representing 31 times zero and one
 *   size = 33 [(1, 00000000000000000000000000000000)] is representing 31 times zero
 *   size = 64 [(0, 00000000000000000000000000000001), (0, 00000000000000000000000000000000)] is representing 31 times zero, one and 32 times zero
 * */
 
namespace common {
 
class SparseBoolVector {
    static const size_t BITS_IN_BYTE = 8;
public:
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    struct element {
        unsigned run;
        unsigned word;
 
        bool operator == ( const element & other ) const {
            return run == other.run && word == other.word;
        }
 
        std::strong_ordering operator <=> ( const element & other ) const {
            return std::tie ( run, word ) <=> std::tie ( other.run, other.word );
        }
    };
 
    ext::list < element > m_Data;
    size_t m_Size { 0 };
 
private:
    static inline unsigned getMask ( size_t dist ) {
        return ( ( 1u ) << dist ) - 1;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    void packData ( ) {
        size_t sizeWithin = m_Size % ( sizeof ( unsigned ) * BITS_IN_BYTE );
        size_t sizeBlocks = m_Size / ( sizeof ( unsigned ) * BITS_IN_BYTE ) + static_cast < unsigned > ( sizeWithin != 0 );
        unsigned mask = getMask ( sizeWithin );
 
        // crop by size
        ext::list < element >::iterator elementIter = m_Data.begin ( );
        for ( ; elementIter != m_Data.end ( ); ++ elementIter ) {
            if ( sizeBlocks <= elementIter->run + 1 )
                break;
            sizeBlocks -= elementIter->run + 1;
        }
 
         // sizeBlocks is smaller or equal to elementIter->run + 1
        if ( sizeBlocks == elementIter->run + 1 ) {
            if ( mask != 0 )
                elementIter->word &= mask;
        } else {
            elementIter->run = sizeBlocks - 1;
            elementIter->word = 0;
        }
        ++ elementIter;
 
        for ( ; elementIter != m_Data.end ( ); ) {
            elementIter = m_Data.erase ( elementIter );
        }
 
        // erase not needed blocks
        unsigned runCarry = 0;
        for ( elementIter = m_Data.begin ( ); elementIter != m_Data.end ( ); ++ elementIter ) {
            while ( elementIter->word == 0 && std::next ( elementIter ) != m_Data.end ( ) ) {
                runCarry += elementIter->run + 1;
                elementIter = m_Data.erase ( elementIter );
            }
            elementIter->run += runCarry;
            runCarry = 0;
        }
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
public:
    SparseBoolVector ( ) = default;
 
    SparseBoolVector ( const ext::vector < bool > & raw ) {
        for ( bool boolean : raw ) {
            push_back ( boolean );
        }
    }
 
    SparseBoolVector ( ext::list < element > data, size_t size ) : m_Data ( std::move ( data ) ), m_Size ( size ) {
        packData ( );
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    void push_back ( bool boolean ) {
        size_t sizeWithin = m_Size % ( sizeof ( unsigned ) * BITS_IN_BYTE );
 
        if ( m_Data.empty ( ) ) {
            m_Data.push_back ( element { 0, 0 } );
        } else if ( sizeWithin == 0 && m_Data.back ( ).word == 0 ) {
            m_Data.back ( ).run += 1;
        } else if ( sizeWithin == 0 && m_Data.back ( ).word != 0 ) {
            m_Data.push_back ( element { 0, 0 } );
        }
 
        m_Data.back ( ).word |= static_cast < unsigned > ( boolean ) << sizeWithin;
        m_Size += 1;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool operator [] ( size_t index ) const {
        size_t sizeWithin = index % ( sizeof ( unsigned ) * BITS_IN_BYTE );
        size_t sizeBlocks = index / ( sizeof ( unsigned ) * BITS_IN_BYTE );
 
        ext::list < element >::const_iterator elementIter = m_Data.begin ( );
        for ( ; elementIter != m_Data.end ( ); ++ elementIter ) {
            if ( elementIter->run + 1 > sizeBlocks )
                break;
            sizeBlocks -= elementIter->run + 1;
        }
        if ( elementIter->run > sizeBlocks )
            return false;
        else
            return static_cast < bool > ( elementIter->word & 1u << sizeWithin );
    }
 
private:
    class BitReference {
        ext::list < element > & data;
        ext::list < element >::iterator elementIter;
        size_t sizeWithin;
        size_t sizeBlocks;
    public:
        BitReference ( ext::list < element > & d, ext::list < element >::iterator iter, size_t within, size_t blocks ) : data ( d ), elementIter ( iter ), sizeWithin ( within ), sizeBlocks ( blocks ) {
        }
 
        BitReference & operator = ( bool value ) {
            if ( elementIter->run > sizeBlocks ) {
                elementIter->run -= sizeBlocks + 1;
                elementIter = data.insert ( elementIter, element { static_cast < unsigned > ( sizeBlocks ), 0 } );
            }
            if ( value )
                elementIter->word |= 1u << sizeWithin;
            else
                elementIter->word &= ~ ( 1u << sizeWithin );
 
            return * this;
        }
 
        operator bool ( ) {
            if ( elementIter->run > sizeBlocks )
                return false;
            else
                return elementIter->word & 1u << sizeWithin;
        }
 
    };
 
public:
    BitReference operator [] ( size_t index ) {
        size_t sizeWithin = index % ( sizeof ( unsigned ) * BITS_IN_BYTE );
        size_t sizeBlocks = index / ( sizeof ( unsigned ) * BITS_IN_BYTE );
 
        ext::list < element >::iterator elementIter = m_Data.begin ( );
        for ( ; elementIter != m_Data.end ( ); ++ elementIter ) {
            if ( elementIter->run + 1 > sizeBlocks )
                break;
            sizeBlocks -= elementIter->run + 1;
        }
        return BitReference ( m_Data, elementIter, sizeWithin, sizeBlocks );
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    operator ext::vector < bool > ( ) const {
        ext::vector < bool > res;
 
        for ( const element & elem : m_Data ) {
            for ( unsigned i = 0; i < elem.run ; ++i )
                for ( size_t j = 0; j < sizeof ( unsigned ) * BITS_IN_BYTE; ++j )
                    res.push_back ( false );
 
            for ( size_t i = 0; i < sizeof ( unsigned ) * BITS_IN_BYTE; ++i ) {
                res.push_back ( elem.word & 1u << i );
            }
        }
 
        res.resize ( m_Size );
 
        return res;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    void resize ( size_t newSize ) {
        if ( newSize > m_Size ) {
            // could be better
            size_t added = ( newSize - m_Size ) / ( sizeof ( unsigned ) * BITS_IN_BYTE ) + 1;
            m_Data.push_back ( element { static_cast < unsigned > ( added ), 0 } );
        }
        m_Size = newSize;
 
        packData ( );
    }
 
    size_t size ( ) const {
        return m_Size;
    }
 
    const ext::list < element > & data ( ) const {
        return m_Data;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool operator == ( const SparseBoolVector & other ) const {
        return m_Size == other.m_Size && m_Data == other.m_Data;
    }
 
    std::strong_ordering operator <=> ( const SparseBoolVector & other ) const {
        return ext::tie ( m_Size, m_Data ) <=> ext::tie ( other.m_Size, other.m_Data );
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    friend SparseBoolVector & operator <<= ( SparseBoolVector & A, size_t dist ) {
        if ( A.m_Size == 0 || dist == 0 )
            return A;
 
        size_t distBlocks = dist / ( sizeof ( unsigned ) * BITS_IN_BYTE );
        size_t distWithin = dist % ( sizeof ( unsigned ) * BITS_IN_BYTE );
        size_t backDist = sizeof ( unsigned ) * BITS_IN_BYTE - distWithin;
 
        // shift by block
        A.m_Data.front ( ).run += distBlocks;
 
        if ( distWithin == 0 ) {
            A.packData ( );
            return A;
        }
 
        unsigned shiftedWord = 0;
 
        for ( auto elementIter = A.m_Data.begin ( ); elementIter != A.m_Data.end ( ); ++ elementIter ) {
            if ( shiftedWord != 0 && elementIter->run != 0 ) {
                // shift into new block borrow from this run
                elementIter->run -= 1;
 
                elementIter = A.m_Data.insert ( elementIter, element { 0, shiftedWord } );
 
                shiftedWord = 0;
            } else {
                unsigned tmp = elementIter->word >> backDist;
                elementIter->word = elementIter->word << distWithin | shiftedWord;
                shiftedWord = tmp;
            }
        }
 
        A.packData ( );
 
        return A;
    }
 
    friend SparseBoolVector operator << ( SparseBoolVector A, size_t dist ) {
        A <<= dist;
        return A;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    friend ext::ostream & operator << ( ext::ostream & out, const common::SparseBoolVector & elem ) {
        out << "(" << elem.m_Size << ", " << elem.m_Data << ")";
        return out;
    }
 
    friend ext::ostream & operator << ( ext::ostream & out, const common::SparseBoolVector::element & elem ) {
        out << "(" << elem.run << ", ";
        for ( size_t i = 0; i < sizeof ( elem.word ) * BITS_IN_BYTE; ++ i )
            out << static_cast < bool > ( elem.word & 1u << i );
        out << ")";
        return out;
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    class SparseBoolVectorOnesIterator {
        ext::list < element >::const_iterator underlying;
        ext::list < element >::const_iterator underlyingEnd;
        size_t index;
 
    public:
        SparseBoolVectorOnesIterator ( ext::list < element >::const_iterator iterBegin, ext::list < element >::const_iterator iterEnd, size_t ind ) : underlying ( iterBegin ), underlyingEnd ( iterEnd ), index ( ind ) {
            if ( underlying == underlyingEnd ) {
                return;
            }
 
            // if we have one at the exact place we are done
            index = sizeof ( unsigned ) * BITS_IN_BYTE * underlying->run;
            if ( underlying->word & 1u )
                return;
 
            // othervise increment to a closest one
            ++ * this;
        }
 
        SparseBoolVectorOnesIterator & operator ++ ( ) {
            if ( underlying == underlyingEnd )
                return *this;
 
            // get the index within word from global index and increment both
            size_t innerIndex = index % ( sizeof ( unsigned ) * BITS_IN_BYTE );
            ++ innerIndex;
            ++ index;
 
            // if we crossed the boundary of the word increment underlying iterator
            if ( innerIndex == sizeof ( unsigned ) * BITS_IN_BYTE )
                ++ underlying;
 
            // if we reached the end iterator there is no next one
            if ( underlying == underlyingEnd )
                return *this;
 
            // othervise skip sizeof word times the run size
            if ( innerIndex == sizeof ( unsigned ) * BITS_IN_BYTE )
                index += sizeof ( unsigned ) * BITS_IN_BYTE * underlying->run;
 
            while ( true ) {
                // from the current position try to find next one in the current word
                for ( innerIndex = index % ( sizeof ( unsigned ) * BITS_IN_BYTE ); innerIndex < sizeof ( unsigned ) * BITS_IN_BYTE; ++ innerIndex ) {
                    // if we have it we are done
                    if ( underlying->word & ( 1u << innerIndex ) )
                        return *this;
 
                    ++ index;
                }
 
                // if we got here there was no next one in the current word, try next one
                ++ underlying;
 
                // which however may not exist we could have got out of the container
                if ( underlying == underlyingEnd )
                    return *this;
 
                // if we didn't increase the index by sizeof word times the run size
                index += sizeof ( unsigned ) * BITS_IN_BYTE * underlying->run;
            }
        }
 
        SparseBoolVectorOnesIterator operator ++( int ) {
            SparseBoolVectorOnesIterator tmp ( * this );
 
            operator ++( );
            return tmp;
        }
 
        bool operator == ( const SparseBoolVectorOnesIterator & other ) const {
            return underlying == underlyingEnd && other.underlying == other.underlyingEnd && underlying == other.underlying;
        }
 
        bool operator != ( const SparseBoolVectorOnesIterator & other ) const {
            return ! ( *this == other );
        }
 
        size_t operator * ( ) const {
            return index;
        }
    };
 
    SparseBoolVectorOnesIterator begin ( ) const {
        return SparseBoolVectorOnesIterator ( m_Data.begin ( ), m_Data.end ( ), 0 );
    }
 
    SparseBoolVectorOnesIterator end ( ) const {
        return SparseBoolVectorOnesIterator ( m_Data.end ( ), m_Data.end ( ), m_Size );
    }
 
// --------------------------------------------------------------------------------------------------------------------------------------------------
 
    friend SparseBoolVector & operator &= ( SparseBoolVector & A, const SparseBoolVector & B ) {
        A.resize ( std::max ( A.size ( ), B.size ( ) ) );
 
        ext::list < element >::iterator iterA = A.m_Data.begin ( );
        ext::list < element >::const_iterator iterB = B.m_Data.begin ( );
 
        size_t blocksA = iterA->run;
        size_t blocksB = iterB->run;
 
        while ( iterA != A.m_Data.end ( ) && iterB != B.m_Data.end ( ) ) {
            if ( blocksA == blocksB ) {
                iterA->word &= iterB->word;
 
                ++ iterA;
                blocksA += 1 + iterA->run;
 
                ++ iterB;
                blocksB += 1 + iterB->run;
            } else if ( blocksA < blocksB ) {
                iterA->word = 0;
 
                ++ iterA;
                blocksA += 1 + iterA->run;
            } else { // blockA > blockB
                ++ iterB;
                blocksB += 1 + iterB->run;
            }
        }
 
        while ( iterA != A.m_Data.end ( ) ) {
            iterA->word = 0;
            ++ iterA;
        }
 
        A.packData();
 
        return A;
    }
 
    friend SparseBoolVector operator & ( SparseBoolVector A, const SparseBoolVector & B ) {
        A &= B;
        return A;
    }
 
};
 
} /* namespace common */