#include "boost/signals2.hpp"
#include <iostream> 
#include <vector> 
#include "boost/function.hpp" 
#include <cstdlib> 
#include <algorithm>
#include "boost/shared_ptr.hpp"
#include "boost/make_shared.hpp"
#include "boost/signals.hpp"
#include <map>
#include "boost/timer.hpp"
#include "boost/preprocessor.hpp"

namespace test
{
	struct connection
	{
		void disconnect() { if( m_Con ) m_Con->disconnect(); }
		connection( const connection& a_Other ) : m_Con( a_Other.m_Con ) {}
		connection& operator=( const connection& a_RHS ) { m_Con = a_RHS.m_Con; return *this; }
		connection() {}
	private:
		template< typename Signature, typename PriorityType >
		friend class signals;
		struct connectionBase { virtual void disconnect() = 0; virtual ~connectionBase(){} };
		connection( connectionBase* a_Con ) : m_Con( a_Con ) {}
		boost::shared_ptr< connectionBase > m_Con;
	};
	template< typename Signature, typename PriorityType = unsigned int >
	class signals
	{
	public:
		signals( unsigned int a_Reserve = 0 )
		{
			m_Storage.reserve( a_Reserve );
		}
		typedef boost::function< Signature > FunctionType;
		typedef std::vector< std::pair< FunctionType, boost::shared_ptr< unsigned int > > > StorageType;
		// Priority -> Begin, End, Shift
		struct region
		{
			region( unsigned int a_Offset = 0u, unsigned int a_Length = 0u, int a_Shift = 0 ) : Offset( a_Offset ), Length( a_Length ), Shift( a_Shift ) {}
			unsigned int Offset, Length;
			int Shift;
		};
		typedef std::map< PriorityType, region > RegionMap;
		void operator()( )
		{
			for( unsigned int i = 0;i < m_Storage.size(); ++i )
				m_Storage[i].first();
		}
#define BOOST_PP_LOCAL_MACRO(n) \
	template < BOOST_PP_ENUM_PARAMS(n, typename T) > \
	void operator()( BOOST_PP_ENUM_BINARY_PARAMS(n, T, arg) ) \
		{ \
			for( unsigned int i = 0; i < m_Storage.size(); ++i )\
				m_Storage[i].first( BOOST_PP_ENUM_PARAMS(n, arg) ); \
		} \

#define BOOST_PP_LOCAL_LIMITS (1, 5)
#include BOOST_PP_LOCAL_ITERATE()
#undef BOOST_PP_LOCAL_MACRO

		connection connect( const FunctionType& a_Func, const PriorityType& a_Priority = PriorityType() )
		{
			typename RegionMap::iterator itrFnd = m_PriorityRegions.find( a_Priority );
			if( itrFnd == m_PriorityRegions.end() )
			{
				itrFnd = m_PriorityRegions.insert( std::make_pair( a_Priority, region() ) ).first;
				if( itrFnd != m_PriorityRegions.begin() )
				{
					typename RegionMap::iterator beforeUs = itrFnd;
					--beforeUs;
					itrFnd->second.Offset = beforeUs->second.Offset + beforeUs->second.Length;
				}
			}
			boost::shared_ptr< unsigned int > offset( boost::make_shared< unsigned int >( itrFnd->second.Length + itrFnd->second.Shift ) );
			m_Storage.push_back( std::make_pair( a_Func, offset ) );
			typename StorageType::value_type* current = &m_Storage.back();
			typename RegionMap::iterator itrCur( itrFnd );
			++itrCur;
			for( ; itrCur != m_PriorityRegions.end(); ++itrCur )
			{
				typename StorageType::value_type& swapee = m_Storage[ itrCur->second.Offset ];
				++itrCur->second.Offset;
				++itrCur->second.Shift;
				(*swapee.second.get()) = itrCur->second.Length + itrCur->second.Shift - 1;
				std::swap( *current, swapee );
			}
			++itrFnd->second.Length;
			return connection( new connectionImpl< ThisType >( this, itrFnd, offset ) );
		}
	private:
		typedef signals< Signature, PriorityType > ThisType;

		template< typename ParentType >
		friend struct connectionImpl;

		template< typename ParentType >
		struct connectionImpl : public connection::connectionBase
		{
			void disconnect()
			{
				// Makes sure our host as well as our slot is still alive
				if( boost::shared_ptr< unsigned int > offset = m_Offset.lock() )
				{
					m_Priority->second.Length;
					typename ParentType::StorageType::value_type* current = &m_Parent->m_Storage[ m_Priority->second.Offset + ( *offset ) - m_Priority->second.Shift ]; 
					typename ParentType::StorageType::value_type* lastInOur = &m_Parent->m_Storage[ m_Priority->second.Offset + m_Priority->second.Length - 1 ];
					*lastInOur->second = *current->second;
					std::swap( *current, *lastInOur );
					current = lastInOur;
					typename ParentType::RegionMap::iterator itrCur( m_Priority );
					++itrCur;
					for( ; itrCur != m_Parent->m_PriorityRegions.end(); ++itrCur )
					{
						typename ParentType::StorageType::value_type* tmp = &m_Parent->m_Storage[ itrCur->second.Offset + itrCur->second.Length - 1 ];
						std::swap( *tmp, *current );
						--itrCur->second.Offset;
						--itrCur->second.Shift;
						*current->second = itrCur->second.Shift;
						current = tmp;
					}
					m_Parent->m_Storage.pop_back();
					--m_Priority->second.Length;
				}
			}
			connectionImpl( ParentType* a_Parent, const typename ParentType::RegionMap::iterator& a_Priority, boost::shared_ptr< unsigned int > a_Offset ) : 
			m_Parent( a_Parent ), m_Priority( a_Priority ), m_Offset( a_Offset ) {}
			ParentType* m_Parent;
			typename ParentType::RegionMap::iterator m_Priority;
			boost::weak_ptr< unsigned int > m_Offset;
		};

		RegionMap m_PriorityRegions;
		StorageType m_Storage;
	};
}

void foo( ) {  }
#define FRAG_VERSIONS
int main() 
{

	const unsigned int numConnections = 100000, numCalls = 100, numGroups = 200, rndSeed = 0, fragSpread = 30;
	std::cout << "Using numConnections = " << numConnections << " numCalls = " << numCalls <<  " numGroups = " << numGroups << " rndSeed = " << rndSeed << " fragSpread = " << fragSpread << std::endl;
	test::signals< void( void ) > vectorSignalUnfrag( numConnections ); 
	std::vector< boost::function< void ( void ) > > manualSignal; 
	typedef std::list< boost::function< void ( void ) > >::iterator SigListIterator; 
	std::list< boost::function< void ( void ) > > manualSignalListUnfragmented, manualSignalListFragmented; 
	boost::signal< void ( void ) > boostSignalFragmented, boostSignalUnfragmented; 
	namespace bs2 = boost::signals2; 
	bs2::signal_type<void (void), bs2::keywords::mutex_type<bs2::dummy_mutex> >::type boostSignal2Fragmented, boostSignal2Unfragmented; 
	typedef std::vector< boost::signals::connection > ConnectionVectorSig1; 
	typedef std::vector< boost::signals2::connection > ConnectionVectorSig2; 
	typedef std::vector< test::connection > ConnectionVectorSigTest; 
	double rndRuntime = .0;
	{
		std::srand( rndSeed );
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			std::rand();

		rndRuntime = tm.elapsed();
		std::cout << "Generating random sequence takes: " << rndRuntime << " seconds" << std::endl;
	}
	{
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			manualSignalListUnfragmented.push_back( &foo );

		double elapsed = tm.elapsed();
		std::cout << "Connecting to unfrag list:< function<> >: " << elapsed << " seconds" << std::endl;
	}
	{
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			manualSignal.push_back( &foo );

		double elapsed = tm.elapsed();
		std::cout << "Connecting to vector< function<> >: " << elapsed << " seconds" << std::endl;
	}
	{
		std::srand( rndSeed );
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			boostSignal2Unfragmented.connect( std::rand() % numGroups, &foo );

		double elapsed = tm.elapsed() - rndRuntime;
		std::cout << "Connecting to unfrag signals2< function<> >: " << elapsed << " seconds" << std::endl;
	}
	{
		std::srand( rndSeed );
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			boostSignalUnfragmented.connect( std::rand() % numGroups, &foo );

		double elapsed = tm.elapsed() - rndRuntime;
		std::cout << "Connecting to unfrag signals1< function<> >: " << elapsed << " seconds" << std::endl;
	}
	{
		std::srand( rndSeed );
		boost::timer tm;
		for( unsigned int i = 0; i < numConnections; ++i )
			vectorSignalUnfrag.connect( &foo, std::rand() % numGroups );
		double elapsed = tm.elapsed() - rndRuntime;
		std::cout << "Connecting to test::signals< function<> >: " << elapsed << " seconds" << std::endl;
	}
#ifdef FRAG_VERSIONS
	{
		ConnectionVectorSig1 connectionsFragSig1( numConnections * fragSpread );
		std::srand( rndSeed );
		for( unsigned int i = 0; i < numConnections * fragSpread; ++i )
			connectionsFragSig1.push_back( boostSignalFragmented.connect( std::rand() % numGroups, &foo ) );

		std::random_shuffle( connectionsFragSig1.begin(), connectionsFragSig1.end() );
		for( unsigned int i = numConnections; i < numConnections * fragSpread; ++i )
			connectionsFragSig1[i].disconnect();

		connectionsFragSig1.erase( connectionsFragSig1.begin() + numConnections, connectionsFragSig1.end() );
	}
	std::cout << "..." << std::endl;
	{
		ConnectionVectorSig2 connectionsFragSig2( numConnections * fragSpread );
		std::srand( rndSeed );
		for( unsigned int i = 0; i < numConnections * fragSpread; ++i )
			connectionsFragSig2.push_back( boostSignal2Fragmented.connect( std::rand() % numGroups, &foo ) );

		std::random_shuffle( connectionsFragSig2.begin(), connectionsFragSig2.end() );
		for( unsigned int i = numConnections; i < numConnections * fragSpread; ++i )
			connectionsFragSig2[i].disconnect();

		connectionsFragSig2.erase( connectionsFragSig2.begin() + numConnections, connectionsFragSig2.end() );
	}
	std::cout << "..." << std::endl;
#ifdef LIST_VERSION
	{
		std::srand( rndSeed );
		for( unsigned int i = 0; i < numConnections * fragSpread; ++i )
			manualSignalListFragmented.push_back( &foo );
		for( unsigned int i = numConnections; i < numConnections * fragSpread; ++i )
		{
			SigListIterator itrErase = manualSignalListFragmented.begin();
			std::advance( itrErase, std::rand() % manualSignalListFragmented.size() );
			manualSignalListFragmented.erase( itrErase );
		}
	}
#endif
	std::cout << "..." << std::endl;
#endif
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
		{ 
			for( unsigned int j = 0; j < numConnections; ++j ) 
				manualSignal[ j ]( ); 
		} 
		double elapsed = tm.elapsed(); 
		std::cout << "vector< function<> > invocation: " << elapsed << " seconds" << std::endl; 
	} 
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
			boostSignalUnfragmented( );

		double elapsed = tm.elapsed(); 
		std::cout << "signals< function<> > unfragmented invocation: " << elapsed << " seconds" << std::endl; 
	} 
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
			boostSignal2Unfragmented( ); 

		double elapsed = tm.elapsed(); 
		std::cout << "signals2< function<> >unfragmented invocation: " << elapsed << " seconds" << std::endl; 
	} 

	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
		{ 
			for( SigListIterator itrCur = manualSignalListUnfragmented.begin(), itrEnd = manualSignalListUnfragmented.end(); itrCur != itrEnd; ++itrCur ) 
				(*itrCur)( ); 
		} 
		double elapsed = tm.elapsed(); 
		std::cout << "list< function<> > unfragmented invocation: " << elapsed << " seconds" << std::endl; 
	} 

	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i )
			vectorSignalUnfrag();

		double elapsed = tm.elapsed(); 
		std::cout << "test::signals< function<> > invocation: " << elapsed << " seconds" << std::endl; 

	}	
#ifdef FRAG_VERSIONS
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
			boostSignalFragmented( ); 

		double elapsed = tm.elapsed(); 
		std::cout << "signals< function<> > fragmented invocation: " << elapsed << " seconds" << std::endl; 
	} 	
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
			boostSignal2Fragmented( ); 

		double elapsed = tm.elapsed(); 
		std::cout << "signal2< function<> > fragmented invocation: " << elapsed << " seconds" << std::endl; 
	}
#ifdef LIST_VERSION
	{ 
		boost::timer tm; 
		for( unsigned int i = 0; i < numCalls; ++i ) 
		{ 
			for( SigListIterator itrCur = manualSignalListFragmented.begin(), itrEnd = manualSignalListFragmented.end(); itrCur != itrEnd; ++itrCur ) 
				(*itrCur)( ); 
		} 
		double elapsed = tm.elapsed(); 
		std::cout << "list< function<> > fragmented invocation: " << elapsed << " seconds" << std::endl; 
	} 
#endif
#endif
	std::cout << "Done!" << std::endl;
}