/*
 * vector.hpp
 *
 * Created on: Feb 28, 2014
 * Author: Jan Travnicek
 */

#ifndef __VECTOR_HPP_
#define __VECTOR_HPP_

#include <vector>
#include <ostream>
#include <string>
#include <sstream>

#include "compare.hpp"

namespace std {

template< class T , class ... Ts >
std::ostream& operator<<(std::ostream& out, const std::vector<T, Ts ...>& vector) {
	out << "[";

	bool first = true;
	for(const T& item : vector) {
		if(!first) out << ", ";
		first = false;
		out << item;
	}

	out << "]";
	return out;
}

} /* namespace std */

namespace ext {

template<class T, class ... Ts>
struct compare<std::vector<T, Ts ...>> {
	int operator()(const std::vector<T, Ts...>& first, const std::vector<T, Ts...>& second) const {
		if(first.size() < second.size()) return -1;
		if(first.size() > second.size()) return 1;

		static compare<typename std::decay < T >::type > comp;
		for(auto iterF = first.begin(), iterS = second.begin(); iterF != first.end(); ++iterF, ++iterS) {
			int res = comp(*iterF, *iterS);
			if(res != 0) return res;
		}
		return 0;
	}
};

template < class T, class ... Ts >
std::string to_string ( const std::vector < T, Ts ... > & value ) {
	std::stringstream ss;
	ss << value;
	return ss.str();
}

} /* namespace ext */

namespace std {

template < class ... Ts >
std::vector < bool, Ts ... > & operator |= ( std::vector < bool, Ts ... > & A, const std::vector < bool, Ts ... > & B ) {
	A.resize ( std::max ( A.size ( ), B.size ( ) ) );

	typename std::vector < bool, Ts ... >::iterator itA = A.begin ( );
	typename std::vector < bool, Ts ... >::const_iterator itB = B.begin ( );

	// c++ implementation-specific
	while ( itB < B.end ( ) ) // A is longer or of the same size as B
		* ( itA._M_p ++ ) |= * ( itB._M_p ++ ); // word-at-a-time bitwise operation

	// The rest of A above the size of B can be left intact

	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator | ( std::vector < bool, Ts ... > A, const std::vector < bool, Ts ... > & B ) {
	A |= B;
	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > & operator &= ( std::vector < bool, Ts ... > & A, const std::vector < bool, Ts ... > & B ) {
	A.resize ( std::max ( A.size ( ), B.size ( ) ) );

	typename std::vector < bool, Ts ... >::iterator itA = A.begin ( );
	typename std::vector < bool, Ts ... >::const_iterator itB = B.begin ( );

	// c++ implementation-specific
	while ( itB < B.end ( ) ) // A is longer or of the same size as B
		* ( itA._M_p ++ ) &= * ( itB._M_p ++ ); // word-at-a-time bitwise operation

	while ( itA < A.end ( ) ) // The rest of A above the size of B shall be zeroed
		* ( itA._M_p ++ ) = 0;

	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator & ( std::vector < bool, Ts ... > A, const std::vector < bool, Ts ... > & B ) {
	A &= B;
	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > & operator ^= ( std::vector < bool, Ts ... > & A, const std::vector < bool, Ts ... > & B ) {
	A.resize ( std::max ( A.size ( ), B.size ( ) ) );

	typename std::vector < bool, Ts ... >::iterator itA = A.begin ( );
	typename std::vector < bool, Ts ... >::const_iterator itB = B.begin ( );

	// c++ implementation-specific
	while ( itB < B.end ( ) ) // A is longer or of the same size as B
		* ( itA._M_p ++ ) ^= * ( itB._M_p ++ ); // word-at-a-time bitwise operation

	while ( itA < A.end ( ) ) // The rest of A above the size of B shall be flipped
		* ( itA._M_p ++ ) = ~ * ( itA._M_p ++ );

	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator ^ ( std::vector < bool, Ts ... > A, const std::vector < bool, Ts ... > & B ) {
	A ^= B;
	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator ~ ( std::vector < bool, Ts ... > A ) {
	A.flip ( );
	return A;
}

// the same type as the std::vector bool's internal storage type
typedef typename std::decay < decltype ( * ( std::declval < std::vector < bool > > ( ).begin ( )._M_p ) ) >::type vectorBoolInternalType;
// the size of the std::vector bool's internal storage type
const unsigned vectorBoolInternalTypeInBits = sizeof ( vectorBoolInternalType ) * 8;

// private helper for mask computation
inline vectorBoolInternalType getMask ( size_t dist ) {
	return ( ( vectorBoolInternalType { } + 1 ) << dist ) - 1;
}

template < class ... Ts >
std::vector < bool, Ts ... > & operator <<= ( std::vector < bool, Ts ... > & A, size_t dist ) {
	if ( A.size ( ) == 0 )
		return A;

	size_t distBlocks = dist / vectorBoolInternalTypeInBits;
	size_t distWithin = dist % vectorBoolInternalTypeInBits;
	size_t backDist = vectorBoolInternalTypeInBits - distWithin;

	// shift blocks if needed
	if ( distBlocks ) {
		// simulate behavior of reverse iterator
		auto itAReverse = A.end ( ) - 1;
		auto itASource = itAReverse;
		itASource._M_p -= distBlocks;

		while ( itASource >= A.begin ( ) )
			* ( itAReverse._M_p -- ) = * ( itASource._M_p -- );

		while ( itAReverse >= A.begin ( ) )
			* ( itAReverse._M_p -- ) = 0;
	}

	if ( distWithin == 0 )
		return A;

	// shift by the rest dist
	{
		vectorBoolInternalType bits1 { };
		vectorBoolInternalType bits2 { };

		// it might be more clear to iterate from the begining. However this is working nicely
		auto itA = A.begin ( );

		while ( itA < A.end ( ) ) {
			bits2 = * ( itA._M_p );
			* ( itA._M_p ) = * ( itA._M_p ) << distWithin | bits1 >> backDist;
			bits1 = bits2;

			itA._M_p ++;
		}
	}

	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator << ( std::vector < bool, Ts ... > A, size_t dist ) {
	A <<= dist;
	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > & operator >>= ( std::vector < bool, Ts ... > & A, size_t dist ) {
	if ( A.size ( ) == 0 )
		return A;

	size_t distBlocks = dist / vectorBoolInternalTypeInBits;
	size_t distWithin = dist % vectorBoolInternalTypeInBits;
	size_t sizeWithin = A.size ( ) % vectorBoolInternalTypeInBits;
	size_t backDist = vectorBoolInternalTypeInBits - distWithin;

	// shift blocks if needed
	if ( distBlocks ) {
		auto itA = A.begin ( );
		auto itASource = itA;
		itASource._M_p += distBlocks;

		while ( itASource < A.end ( ) )
			* ( itA._M_p ++ ) = * ( itASource._M_p ++ );

		while ( itA < A.end ( ) )
			* ( itA._M_p ++ ) = 0;
	}

	if ( distWithin == 0 )
		return A;

	// shift by the rest dist
	{
		vectorBoolInternalType bits1 { };
		vectorBoolInternalType bits2 { };

		// it might be more clear to iterate from the begining. However this is working nicely
		auto itAReverse = A.end ( ) - 1;

		// upper part of the last word in the std::vector can contain some garbage so it needs to be cleared
		if ( sizeWithin != 0 )
			* ( itAReverse._M_p ) &= getMask ( sizeWithin );

		// simulate behavior of reverse iterator
		while ( itAReverse >= A.begin ( ) ) {
			bits2 = * ( itAReverse._M_p );
			* ( itAReverse._M_p ) = * ( itAReverse._M_p ) >> distWithin | bits1 << backDist;
			bits1 = bits2;

			itAReverse._M_p --;
		}
	}

	return A;
}

template < class ... Ts >
std::vector < bool, Ts ... > operator >> ( std::vector < bool, Ts ... > A, size_t dist ) {
	A >>= dist;
	return A;
}

template < class ... Ts >
bool any ( const std::vector < bool, Ts ... > & v ) {
	size_t sizeWithin = v.size ( ) % vectorBoolInternalTypeInBits;

	typename std::vector < bool, Ts ... >::const_iterator itV = v.begin ( );

	// c++ implementation-specific
	while ( itV + 1 < v.end ( ) )
		if ( * ( itV._M_p ++ ) != 0 )
			return true;

	if ( sizeWithin == 0 )
		return * itV._M_p != 0;
	else
		return ( * itV._M_p & getMask ( sizeWithin ) ) != 0;
}

template < class ... Ts >
void fill ( const std::vector < bool, Ts ... > & v ) {
	typename std::vector < bool, Ts ... >::const_iterator itV = v.begin ( );

	// c++ implementation-specific
	while ( itV < v.end ( ) )
		* ( itV._M_p ++ ) = ~ vectorBoolInternalType { };
}

template < class ... Ts >
void clear ( const std::vector < bool, Ts ... > & v ) {
	typename std::vector < bool, Ts ... >::const_iterator itV = v.begin ( );

	// c++ implementation-specific
	while ( itV < v.end ( ) )
		* ( itV._M_p ++ ) = 0;
}

} /* namespace std */

#endif /* __VECTOR_HPP_ */