ZeroRunLengthEncoding.hpp

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

#ifndef ZERO_RUN_LENGTHPP_ENCODING_HPP_
#define ZERO_RUN_LENGTHPP_ENCODING_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 ZeroRunLengthEncoding {
	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:
	ZeroRunLengthEncoding ( ) : m_Size ( 0 ) { }

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

	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 ) {
		m_Size = size;

		packData ( );
	}

	size_t size ( ) const {
		return m_Size;
	}

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

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

	friend bool operator < ( const ZeroRunLengthEncoding & first, const ZeroRunLengthEncoding & 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 ZeroRunLengthEncoding & first, const ZeroRunLengthEncoding & second ) {
		return second < first;
	}

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

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

	friend ZeroRunLengthEncoding & operator <<= ( ZeroRunLengthEncoding & 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 ZeroRunLengthEncoding operator << ( ZeroRunLengthEncoding A, size_t dist ) {
		A <<= dist;
		return A;
	}

	friend std::ostream & operator << ( std::ostream & out, const common::ZeroRunLengthEncoding::element & elem ) {
		out << "(" << elem.run << ", ";
		for ( unsigned i = 0; i < sizeof ( elem.word ) * 8; ++ i )
			out << (bool) ( elem.word & 1 << i );
		out << ")";
		return out;
	}


};

} /* namespace common */

#endif /* ZERO_RUN_LENGTHPP_ENCODING_HPP_ */