#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
#include <omp.h>
#include <mcstl.h>

template < class InputIterator, class OutputIterator>
OutputIterator unique_copy2(InputIterator first, InputIterator last,
					   OutputIterator result)
{
	typedef typename std::iterator_traits<InputIterator>::difference_type difference_type;
	typedef typename std::iterator_traits<InputIterator>::value_type value_type;
	
	if ( last == first )
		return result;
		
	std::vector< difference_type > Offset;
	difference_type temp = 0;
	
	#pragma omp parallel
	{
		
		difference_type size = last - first;
		difference_type chunk = size / omp_get_num_threads();
		difference_type rest = size % omp_get_num_threads();
		
		#pragma omp single
		Offset.resize( omp_get_num_threads() );
		
		const int tid = omp_get_thread_num();
		InputIterator begin = first + tid * chunk + std::min( difference_type( tid ), rest);
		InputIterator end = begin + ((tid < rest) ? 1 : 0) + chunk;
		InputIterator source = begin;
		
		difference_type Counter;
		value_type Value;
		
		if ( tid )
		{
			Counter = 0;
			Value = *(source-1);
		}
		else
		{
			// the very first value is always counted
			Counter = 1;
			Value = *(source++);
		}
		
		for ( ; source != end; ++source )
		{
			if ( Value != *source )
			{
				++Counter;
				Value = *source;
			}
		}
		Offset[ tid ] = Counter;
		
		#pragma omp barrier
		#pragma omp single
		{
			for ( typename std::vector< difference_type >::iterator i = Offset.begin();
						   i != Offset.end(); ++i )
			{
				const difference_type foo = temp;
				temp += *i;
				*i = foo;
			}
		}
		source = begin;
		
		if ( tid )
		{
			Value = *(source-1);
		}
		else
		{
			// the very first value is always counted
			Value = *(source++);
			*(result + Offset[ tid ]++) = Value;
			--Counter;
		}
		
		/*for ( ; source != end; ++source )
		{
			if ( Value != *source )
			{
				Value = *source;
				*(result + Offset[ tid ]++) = Value;
			}
		}	*/
		// alternativly
		while ( Counter )
		{
			while ( Value == *source )
				++source;
			
			Value = *source;
			*(result + Offset[ tid ]++) = Value;
			
			--Counter;
		}
	}
	
	return result + temp;
}


template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union2( 
	InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2,
	OutputIterator result)
{
	typedef typename std::iterator_traits<OutputIterator>::value_type value_type;

	std::vector< value_type > buffer ( (last1 - first1) + (last2 - first2) );
	
	OutputIterator end = std::merge(first1, last1, first2, last2, result );
	
	typename std::vector< value_type >::iterator unique_end = unique_copy2( result, end, buffer.begin() );
	
	return std::copy( buffer.begin(), unique_end, result);
	
}


class foo
{
	public:
	inline unsigned int operator()()
	{
		return std::rand() % (23*42);
	}
};

template < class Iterator > class range_printer_token
{
public:
	Iterator begin;
	Iterator end;
	
	range_printer_token( Iterator begin, Iterator end )
	: begin( begin ), end( end ) {}
private:	
};

template< class Iterator >
std::ostream& operator<<( std::ostream& out, range_printer_token< Iterator > p )
{
	out << "[" ;
	
	if ( p.begin != p.end ) 
	{
		while( true )
		{
			out << *p.begin;
			++p.begin;
			if (p.begin != p.end) 
			{
				out << ",";
			}
			else
				break;
		}
	}
	
	out << "]";
}

template< class T >
range_printer_token< T > print_range( T a, T b )
{
	return range_printer_token< T >( a, b );
}

int main() {
	unsigned int Groesse = 64;

	std::vector< unsigned int > Puffer( Groesse );
	std::vector< unsigned int > Puffer2( Groesse );
	std::vector< unsigned int > Senke( Groesse + Groesse, 0 );
	std::vector< unsigned int > Senke2( Groesse + Groesse, 0 );
	
	std::generate( Puffer.begin(), Puffer.end(), foo() );
	std::generate( Puffer2.begin(), Puffer2.end(), foo() );
	std::sort( Puffer.begin(), Puffer.end() );
	std::sort( Puffer2.begin(), Puffer2.end() );
	
	//std::vector< unsigned int > ::iterator Result = unique_copy2( Puffer.begin(), Puffer.end(), Senke.begin() );
	typedef std::vector< unsigned int >::iterator myit;
	myit Result = set_union2(
			Puffer.begin(), Puffer.end(),
			Puffer2.begin(), Puffer2.end(),
			Senke.begin() );
	
	
	myit Result2 = std::set_union(
			Puffer.begin(), Puffer.end(),
			Puffer2.begin(), Puffer2.end(),
			Senke2.begin() );
	
	
	std::pair< myit, myit > p = std::mismatch( Senke.begin(), Result, Senke2.begin() );
	
	std::cout << "The first mismatch is in position " << p.first - Senke.begin() << std::endl;
	std::cout << "Values are: " << *(p.first) << ", " << *(p.second) << std::endl;
	/*
	{
		std::cout << "Great success!" << std::endl;
	}
	else
	{
		std::cout << "You fail." << std::endl;
	}
 	std::cout << "[";
	
	for ( unsigned int i = 0; i < Groesse; ++i )
	{
		std::cout << Puffer[ i ] << ',';
	}
	std::cout << "]" << std::endl;*//*
	std::cout << "[";
	for ( unsigned int i = 0; i < (Result - Senke.begin()); ++i )
	{
		std::cout << Senke[ i ] << ',';
	}
	std::cout << "]" << std::endl;
	*/
	//print( std::cout, begin, end);
	
	std::cout << print_range( Senke.begin(), Result ) << std::endl;
	
	return 0;
}