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

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

	public:
		ZeroRunLengthEncodingOnesIterator ( 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;
		}

		ZeroRunLengthEncodingOnesIterator & 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;
			}
		}

		ZeroRunLengthEncodingOnesIterator operator ++( int ) {
			ZeroRunLengthEncodingOnesIterator tmp ( * this );

			operator ++( );
			return tmp;
		}

		bool operator == ( const ZeroRunLengthEncodingOnesIterator & other ) const {
			return underlying == underlyingEnd && other.underlying == other.underlyingEnd && underlying == other.underlying;
		}

		bool operator != ( const ZeroRunLengthEncodingOnesIterator & other ) const {
			return ! ( *this == other );
		}

		size_t operator * ( ) {
			return index;
		}
	};

	ZeroRunLengthEncodingOnesIterator begin ( ) const {
		return ZeroRunLengthEncodingOnesIterator ( m_Data.begin ( ), m_Data.end ( ), 0 );
	}

	ZeroRunLengthEncodingOnesIterator end ( ) const {
		return ZeroRunLengthEncodingOnesIterator ( m_Data.end ( ), m_Data.end ( ), m_Size );
	}

};

} /* namespace common */

namespace std {

template < >
struct compare < common::ZeroRunLengthEncoding > {
	int operator()(const common::ZeroRunLengthEncoding & first, const common::ZeroRunLengthEncoding & 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 /* ZERO_RUN_LENGTHPP_ENCODING_HPP_ */