SparseBoolVector.hpp

/*
 * SparseBoolVector.hpp
 *
 *  Created on: 23. 2. 2017
 *	  Author: Jan Travnicek
 */

#ifndef SPARSE_BOOL_VECTOR_HPP_
#define SPARSE_BOOL_VECTOR_HPP_

#include <list>

/* 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 ) * 8 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 {

// --------------------------------------------------------------------------------------------------------------------------------------------------

	struct element {
		unsigned run;
		unsigned word;

		bool operator == ( const element & other ) const {
			return run == other.run && word == other.word;
		}

		bool operator < ( const element & other ) const {
			auto firstTie = std::tie ( run, word );
			auto secondTie = std::tie ( other.run, other.word );

			return firstTie < secondTie;
		}
	};

	std::list < element > m_Data;
	size_t m_Size;

	static inline unsigned getMask ( size_t dist ) {
		return ( ( 1u ) << dist ) - 1;
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	void packData ( ) {
		size_t sizeWithin = m_Size % ( sizeof ( unsigned ) * 8 );
		long long sizeBlocks = m_Size / ( sizeof ( unsigned ) * 8 ) + ( bool ) sizeWithin;
		unsigned mask = getMask ( sizeWithin );

		// crop by size
		std::list < element >::iterator elementIter;
		for ( elementIter = m_Data.begin ( ); elementIter != m_Data.end ( ); ++ elementIter ) {
			sizeBlocks -= elementIter->run + 1;
			if ( sizeBlocks <= 0 )
				break;
		}

		if ( sizeBlocks == 0 ) { // sizeBlocks is negative or 0
			if ( mask != 0 )
				elementIter->word &= mask;
			++ elementIter;
		} else {
			elementIter->run += sizeBlocks; //sizeBlocks is negative
			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 ( ) : m_Size ( 0 ) { }

	SparseBoolVector ( const std::vector < bool > & raw ) : m_Size ( 0 ) {
		for ( bool boolean : raw ) {
			push_back ( boolean );
		}
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	void push_back ( bool boolean ) {
		size_t sizeWithin = m_Size % ( sizeof ( unsigned ) * 8 );

		if ( m_Data.size ( ) == 0 ) {
			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 |= boolean << sizeWithin;
		m_Size += 1;
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	bool operator [] ( size_t index ) const {
		size_t sizeWithin = index % ( sizeof ( unsigned ) * 8 );
		size_t sizeBlocks = index / ( sizeof ( unsigned ) * 8 );

		std::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 elementIter->word & 1u << sizeWithin;
	}

private:
	class BitReference {
		std::list < element > & data;
		std::list < element >::iterator elementIter;
		size_t sizeWithin;
		size_t sizeBlocks;
	public:
		BitReference ( std::list < element > & d, std::list < element >::iterator iter, size_t within, size_t blocks ) : data ( d ), elementIter ( iter ), sizeWithin ( within ), sizeBlocks ( blocks ) {
		}

		bool operator = ( bool value ) {
			if ( elementIter->run > sizeBlocks ) {
				elementIter->run -= sizeBlocks + 1;
				elementIter = data.insert ( elementIter, element { ( unsigned ) sizeBlocks, 0 } );
			}
			if ( value )
				elementIter->word |= 1u << sizeWithin;
			else
				elementIter->word &= ~ ( 1u << sizeWithin );
			return value;
		}

		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 ) * 8 );
		size_t sizeBlocks = index / ( sizeof ( unsigned ) * 8 );

		std::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 std::vector < bool > ( ) const {
		std::vector < bool > res;

		for ( const element & elem : m_Data ) {
			for ( unsigned i = 0; i < elem.run ; ++i )
				for ( unsigned j = 0; j < sizeof ( unsigned ) * 8; ++j )
					res.push_back ( false );

			for ( unsigned i = 0; i < sizeof ( unsigned ) * 8; ++i ) {
				res.push_back ( elem.word & 1 << i );
			}
		}

		res.resize ( m_Size );

		return res;
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	const std::list < element > & data ( ) {
		return m_Data;
	}

	void resize ( size_t size ) {
		if ( size > m_Size ) {
			// could be better
			size_t added = ( size - m_Size ) / ( sizeof ( unsigned ) * 8 ) + 1;
			m_Data.push_back ( element { ( unsigned ) added, 0 } );
		}
		m_Size = size;

		packData ( );
	}

	size_t size ( ) const {
		return m_Size;
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	friend bool operator == ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		return first.m_Size == second.m_Size && first.m_Data == second.m_Data;
	}

	friend bool operator != ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		return ! ( first == second );
	}

	friend bool operator < ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		auto firstTie = std::tie ( first.m_Size, first.m_Data );
		auto secondTie = std::tie ( second.m_Size, second.m_Data );

		return firstTie < secondTie;
	}

	friend bool operator > ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		return second < first;
	}

	friend bool operator <= ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		return ! ( first > second );
	}

	friend bool operator >= ( const SparseBoolVector & first, const SparseBoolVector & second ) {
		return ! ( first < second );
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	friend SparseBoolVector & operator <<= ( SparseBoolVector & A, size_t dist ) {
		if ( A.m_Size == 0 || dist == 0 )
			return A;

		size_t distBlocks = dist / ( sizeof ( unsigned ) * 8 );
		size_t distWithin = dist % ( sizeof ( unsigned ) * 8 );
		size_t backDist = sizeof ( unsigned ) * 8 - 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 std::ostream & operator << ( std::ostream & out, const common::SparseBoolVector::element & elem ) {
		out << "(" << elem.run << ", ";
		for ( unsigned i = 0; i < sizeof ( elem.word ) * 8; ++ i )
			out << (bool) ( elem.word & 1 << i );
		out << ")";
		return out;
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

	class SparseBoolVectorOnesIterator {
		std::list < element >::const_iterator underlying;
		std::list < element >::const_iterator underlyingEnd;
		size_t index;

	public:
		SparseBoolVectorOnesIterator ( std::list < element >::const_iterator iterBegin, std::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 ) * 8 * 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 ) * 8 );
			++ innerIndex;
			++ index;

			// if we crossed the boundary of the word increment underlying iterator
			if ( innerIndex == sizeof ( unsigned ) * 8 )
				++ 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 ) * 8 )
				index += sizeof ( unsigned ) * 8 * underlying->run;

			while ( true ) {
				// from the current position try to find next one in the current word
				for ( innerIndex = index % ( sizeof ( unsigned ) * 8 ); innerIndex < sizeof ( unsigned ) * 8; ++ 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 ) * 8 * 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 * ( ) {
			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 );
	}

// --------------------------------------------------------------------------------------------------------------------------------------------------

};

} /* namespace common */

namespace std {

template < >
struct compare < common::SparseBoolVector > {
	int operator()(const common::SparseBoolVector & first, const common::SparseBoolVector & second) const {
		if(first.size() < second.size()) return -1;
		if(first.size() > second.size()) return 1;

		static compare < unsigned > comp;
		auto iterF = first.begin(), iterS = second.begin();

		for(; iterF != first.end() && iterS != second.end ( ); ++iterF, ++iterS) {
			int res = comp(*iterF, *iterS);
			if(res != 0) return - res;
		}

		if ( iterF == first.end ( ) && iterS == second.end ( ) )
			return 0;
		if ( iterF == first.end ( ) )
			return -1;
		return 1;
	}
};

}

#endif /* SPARSE_BOOL_VECTOR_HPP_ */