/*! \file SparseSetTest.h
	\brief Declaration and implementation of the sps::SparseSetTest class. 

	Include this file if you want to use the sps::SparseSetTest class. 
	
	Note: This file is platform dependent. Full functionality is only available on win32 
		  systems with psapi.h and psapi.lib (from the the MS Platform SDK) placed in a 
		  subfolder called psapi. In all other cases define NO_PSAPI before including this 
		  file.	
*/

#ifndef _SparseSetTest_h_included_
#define _SparseSetTest_h_included_

#include <windows.h>

#include "Helpers.h"
#include "Iterator.h"
#include <map>
#include <iostream>

#ifndef NO_PSAPI
#include "psapi/psapi.h"
#endif

namespace sps
{
	/*! \brief A class for running sparse set tests.

		\c TSet is the concrete BitSet implementation to test and \c TIterator its iterator
		(you usually don't need to overwrite its default value). To run the tests only a 
		call to Test() is needed.

		Example:
		\code
		SparseSetTest< sps::BitList > spstest;
		spstest.Test("logfile.txt", 3); // this will run the tests of logfile.txt 3 times
		\endcode
	*/
	template< class TSet, class TIterator = TSet::Iterator >
	class SparseSetTest
	{
	public:
		SparseSetTest()
		: m_pLastActiveSparseSet( NULL )
		{
		}

		/*! \brief Executes all operations of \c psLogFile \c nLoops times.

		Each line of \c psLogFile must match the \c Line production (see below).
		The \c Id at the beginning of each line identifies the object. Commands 
		of an object are only allowed if the \c Id of the object is valid. An 
		\c Id starts to be valid on a constructor call (\c 'SparseSet()'
		and \c 'Iterator()') and ends to be valid on a destructor call
		(\c '~SparseSet()' and \c '~Iterator()'). An \c Id
		constructed with the \c 'SparseSet()' constructor is only valid for 
		\c SPSCommands and an \c Id constructed with the \c 'Iterator()' constructor only
		for \c ItCommands. 
		
		An \c 'Iterator()' constructor must directly follow each \c 'GetIterator()' command.
		This iterator is the result of the \c 'GetIterator()' call. Each command represents
		a call to the equal-named method in one of the SparseSet implementations or
		their Iterator implementation, respectivly. The iterator \c 'End()' command
		represents sps::Iterator::HasMoreElements() and \c 'Dereference()' 
		sps::Iterator::operator*().

		\code
		Line        := Id ':' Command
		Id          := [0-9a-fA-F]+
		Command     := SPSCommand | ItCommand
		SPSCommand  := 'SparseSet::' ( SPSNoArgCmd | SPSValueCmd | SPSIdCmd )
		SPSNoArgCmd := ( 'SparseSet()' | '~SparseSet()' | 'GetIterator()' | 'IsEmpty()' )
		SPSValueCmd := ( 'Add(' | 'Contains(' | 'Remove(' ) Value ')'
		Value       := [0-9]+
		SPSIdCmd    := ( 'Union(' | 'Intersect(' | 'Difference(' | 'Copy(' | 'IsEqual(' ) Id ')'
		ItCommand   := 'Iterator::' ( 'Iterator()'  | 
		                              '~Iterator()' | 
		                              'Begin()'     |
		                              'Next()'      |
		                              'End()'       | 
		                              'Dereference()' )
		\endcode
		*/
		int Test( const char* psLogFile, size_t nLoops )
		{
	#ifndef NO_PSAPI
			unsigned int nStartTime = GetTickCount();
	#endif

			cout << "Running " << ( unsigned int )nLoops << " iterations of '" << psLogFile << "'." << endl;

			for ( size_t i = 0; i != nLoops; ++i )
			{
				FILE* pLogFile = fopen( psLogFile, "r" );
				if ( !pLogFile )
				{
					cout << "File " << psLogFile << " not found!" << endl;
					return 2;
				}

				char psLine[1024];
				int nLine = 1;

				while ( fgets( psLine, sizeof( psLine ) / sizeof( psLine[ 0 ] ), pLogFile ) != NULL )
				{
					if ( !DoLine( psLine ) )
					{
						cout << "Error in line " << nLine << endl;
						break;
					}
					++nLine;
				}
				fclose( pLogFile );
			}

	#ifndef NO_PSAPI
			unsigned int nEndTime = GetTickCount();
			cout << "time                : " << nEndTime - nStartTime << " ms" << endl;
			PrintMemoryInfo();
	#endif

			return 0;
		}

	protected:
		typedef std::map< size_t, TSet* > TSparseSetMap;
		typedef std::map< size_t, TIterator > TIteratorMap;

	#ifndef NO_PSAPI
		void PrintMemoryInfo()
		{
			HANDLE hProcess = GetCurrentProcess();
			PROCESS_MEMORY_COUNTERS pmc;

			if ( GetProcessMemoryInfo( hProcess, &pmc, sizeof(pmc)) )
			{
				cout << "page faults         : " << ( unsigned int ) pmc.PageFaultCount << endl;
				cout << "peak workingset size: " << ( unsigned int ) pmc.PeakWorkingSetSize / 1024 << " kb" << endl;
				cout << "workingset wize     : " << ( unsigned int ) pmc.WorkingSetSize / 1024 << " kb" << endl;
			}

			CloseHandle( hProcess );
		}
	#endif

		void Clear()
		{
			m_pLastActiveSparseSet = NULL;
			m_mapSparseSets.clear();
			m_mapIterators.clear();
		}

		bool DoLine( const char* psLine )
		{
			if ( *psLine == '#' )
			{
				return true;
			}

			char* psEnd = 0;
			size_t nId = strtoul( psLine, &psEnd, 16 );

			if ( *psEnd != ':' )
			{
				return false;
			}

			const char* psClass = psEnd + 2;
			const char* psMethod = 0;

			if ( !strncmp( psClass, "SparseSet::", 11 ) )
			{
				psMethod = psClass + 11;

				if ( !strncmp( psMethod, "SparseSet()", 11 ) )
				{
					if ( m_mapSparseSets.find( nId ) != m_mapSparseSets.end() )
					{
						return false;
					}

					m_mapSparseSets[ nId ] = new TSet();
				}
				else 
				{
					TSparseSetMap::iterator it = m_mapSparseSets.find( nId );
					if ( it == m_mapSparseSets.end() )
					{
						return false;
					}

					TSet* pSparseSet = it->second;
					
					if ( !strncmp( psMethod, "~SparseSet()", 12 ) ) 
					{
						delete pSparseSet;
						m_mapSparseSets.erase( it );
					}
					else if ( !strncmp( psMethod, "Add(", 4 ) ) 
					{
						size_t nBit = strtoul( psMethod + 4, &psEnd, 10 );
						pSparseSet->Add( nBit );
					}
					else if ( !strncmp( psMethod, "Remove(", 7 ) ) 
					{
						size_t nBit = strtoul( psMethod + 7, &psEnd, 10 );
						pSparseSet->Remove( nBit );
					}
					else if ( !strncmp( psMethod, "Contains(", 9 ) ) 
					{
						size_t nBit = strtoul( psMethod + 9, &psEnd, 10 );
						pSparseSet->Contains( nBit );
					}
					else if ( !strncmp( psMethod, "Union(", 6 ) ) 
					{
						size_t nOtherId = strtoul( psMethod + 6, &psEnd, 16 );
						TSparseSetMap::iterator itOther = m_mapSparseSets.find( nOtherId );
						if ( itOther == m_mapSparseSets.end() )
						{
							return false;
						}

						pSparseSet->Union( *itOther->second );
					}
					else if ( !strncmp( psMethod, "Intersect(", 10 ) ) 
					{
						size_t nOtherId = strtoul( psMethod + 10, &psEnd, 16 );
						TSparseSetMap::iterator itOther = m_mapSparseSets.find( nOtherId );
						if ( itOther == m_mapSparseSets.end() )
						{
							return false;
						}

						pSparseSet->Intersect( *itOther->second );
					}
					else if ( !strncmp( psMethod, "Difference(", 11 ) ) 
					{
						size_t nOtherId = strtoul( psMethod + 11, &psEnd, 16 );
						TSparseSetMap::iterator itOther = m_mapSparseSets.find( nOtherId );
						if ( itOther == m_mapSparseSets.end() )
						{
							return false;
						}

						pSparseSet->Difference( *itOther->second );
					}
					else if ( !strncmp( psMethod, "Copy(", 5 ) )
					{
						size_t nOtherId = strtoul( psMethod + 5, &psEnd, 16 );
						TSparseSetMap::iterator itOther = m_mapSparseSets.find( nOtherId );
						if ( itOther == m_mapSparseSets.end() )
						{
							return false;
						}

						*pSparseSet = *itOther->second;
					}
					else if ( !strncmp( psMethod, "GetIterator()", 13 ) )
					{
						m_pLastActiveSparseSet = pSparseSet;
					}
					else if ( !strncmp( psMethod, "IsEmpty()", 9 ) )
					{
						pSparseSet->IsEmpty();
					}
					else if ( !strncmp( psMethod, "IsEqual(", 8 ) )
					{
						size_t nOtherId = strtoul( psMethod + 8, &psEnd, 16 );
						TSparseSetMap::iterator itOther = m_mapSparseSets.find( nOtherId );
						if ( itOther == m_mapSparseSets.end() )
						{
							return false;
						}

						pSparseSet->IsEqual( *itOther->second );
					}
					else
					{
						cout << psMethod << endl;
						return false;
					}

				}
			}
			else if ( !strncmp( psClass, "Iterator::", 10 ) )
			{
				psMethod = psClass + 10;

				if ( !strncmp( psMethod, "Iterator()", 10 ) )
				{
					if ( m_mapIterators.find( nId ) != m_mapIterators.end() )
					{
						return false;
					}

					m_mapIterators[ nId ] = m_pLastActiveSparseSet->GetIterator();
				}
				else
				{
					TIteratorMap::iterator it = m_mapIterators.find( nId );
					if ( it == m_mapIterators.end() )
					{
						return false;
					}

					TSet::Iterator& rIterator = it->second;
					
					if ( !strncmp( psMethod, "~Iterator()", 11 ) ) 
					{
						m_mapIterators.erase( it );
					}
					else if ( !strncmp( psMethod, "Begin()", 7 ) ) 
					{
						rIterator.Begin();
					}
					else if ( !strncmp( psMethod, "Next()", 6 ) ) 
					{
						rIterator.Next();
					}
					else if ( !strncmp( psMethod, "End()", 5 ) ) 
					{
						rIterator.HasMoreElements();
					}
					else if ( !strncmp( psMethod, "Dereference()", 13 ) ) 
					{
						rIterator.operator *();
					}
					else
					{
						cout << psMethod << endl;
						return false;
					}
				}
			}

			return true;
		}

		TSparseSetMap m_mapSparseSets;
		TIteratorMap m_mapIterators;
		TSet* m_pLastActiveSparseSet;
	};
}

#endif //_SparseSetTest_h_included_