#include "vecsorted.h"
#include "sarray.h"
#include "stl_vector.h"
#include "g_vector.h"

//=======================================================================================

/*********************************************

Why "vecsorted" is better than map :

1. It can be built on any vector type, including static vectors (like my sarray)
	which do zero allocations, which can make it much faster and cleaner.  Maps
	can also be made to use static memory, but it's very messy and difficult.

2. Memory use is much lower.  There is zero overhead; only the class data is stored.

3. Because memory use is lower, it can be much faster in real applications where
	memory bandwidth is the worst problem.  This doesn't show up in isolated profiles
	because you don't have competition for the cache.

4. Walking the map in sorted order is much more efficient and much better for cache
	coherency, and simpler.  The iterators are random-access which lets you use more
	algorithms.

5. The APIs are safer and more convenient.  Of coure, this could also be accomplished
	with a wrapping of std::map

6. The code is much simpler, hence easier to debug.  The template is much lighter,
	hence faster to compile.

7. It's easy to put in your own vector, which does range checking with assert, etc.

*********************************************/

//=======================================================================================

// @@ 
//	stp : std on pairs
//	-> good idea or bad?
//	kind of convenient, but would take a ton of work to make complete,
//		and creates an inconsistency
//	
namespace stp
{

	template <class iterator,class functor>
	void for_each( const std::pair<iterator,iterator> & itpair, functor f )
	{
		std::for_each(itpair.first,itpair.second,f);
	}

	template <class iterator,class _Tp>
	iterator find( const std::pair<iterator,iterator> & itpair, 
                       const _Tp& val)
	{
		return std::find(itpair.first,itpair.second,val);
	}
	
	template <class iterator,class _Predicate>
	iterator find_if( const std::pair<iterator,iterator> & itpair, 
                       _Predicate pred)
	{
		return std::find_if(itpair.first,itpair.second,pred);
	}

	template <class iterator, class _Tp>
	iterator remove(const std::pair<iterator,iterator> & itpair, 
				   const _Tp& val)
	{
		return std::remove(itpair.first,itpair.second,val);
	}

	template <class iterator, class _Predicate>
	iterator remove_if(const std::pair<iterator,iterator> & itpair, 
				  _Predicate pred)
	{
		return std::remove_if(itpair.first,itpair.second,pred);
	}

};

//=======================================================================================
// explicit template instantiation for testing :

template multivecsorted< std::vector<int> >;
template vecsorted< std::vector<int> >;

//=======================================================================================

void vecsorted_test()
{

	//-------------------------------------------------------------------------------------

	{
	typedef multivecsorted< std::vector<int> > vecs_t;
	vecs_t vecs;

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	struct Local
	{
	static void printint(const int & i)
	{
		printf("%d,",i);
	}
	};
	
	puts("X");

	std::for_each(vecs.begin(),vecs.end(),Local::printint);

	puts("X");

	vecs_t::const_iterator it = vecs.find(1);
	vecs.erase(it);
	
	vecs.erase( vecs.find(4) );
	vecs.erase( vecs.find(7) );
	vecs.erase( vecs.find(6) );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);

	puts("X");

	vecs.insert( 3 );
	vecs.insert( 3 );
	vecs.insert( 1 );
	vecs.insert( 3 );

	vecs_t::iterator_pair itpair = vecs.findrange(1);
	stp::for_each(itpair,Local::printint);

	itpair = vecs.findrange(3);
	stp::for_each(itpair,Local::printint);

	vecs.erase(3);

	puts("X");
	}

	//-------------------------------------------------------------------------------------

	{
	typedef multivecsorted< sarray<int,32> > vecs_t;
	vecs_t vecs;

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	struct Local
	{
	static void printint(const int & i)
	{
		printf("%d,",i);
	}
	};
	
	puts("X");

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");

	vecs_t::const_iterator it = vecs.find(1);
	vecs.erase(it);
	
	vecs.erase( vecs.find(4) );
	vecs.erase( vecs.find(7) );
	vecs.erase( vecs.find(6) );

	gAssert( vecs.is_valid() );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	gAssert( vecs.is_valid() );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	}
	
	//-------------------------------------------------------------------------------------

	{
	typedef vecsorted< sarray<int,32> , std::less<int> , vecsorted_type::unique > vecs_t;
	vecs_t vecs;

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	gAssert( vecs.is_valid() );

	struct Local
	{
	static void printint(const int & i)
	{
		printf("%d,",i);
	}
	};
	
	puts("X");

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");

	vecs_t::const_iterator it = vecs.find(1);
	vecs.erase(it);
	
	vecs.erase( vecs.find(4) );
	vecs.erase( vecs.find(7) );
	vecs.erase( vecs.find(6) );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	gAssert( vecs.is_valid() );

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	gAssert( vecs.is_valid() );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	}
	
	//-------------------------------------------------------------------------------------

	{
	gMem::LogAllocations();

	typedef vecsorted< g_vector<int> , std::less<int> , vecsorted_type::unique > vecs_t;
	vecs_t vecs;

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	struct Local
	{
	static void printint(const int & i)
	{
		printf("%d,",i);
	}
	};
	
	puts("X");

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");

	vecs_t::const_iterator it = vecs.find(1);
	vecs.erase(it);
	
	vecs.erase( vecs.find(4) );
	vecs.erase( vecs.find(7) );
	vecs.erase( vecs.find(6) );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	gAssert( vecs.is_valid() );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	gAssert( vecs.is_valid() );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);
	puts("X");
	
	gMem::LogAllocations();
	}
	
	//-------------------------------------------------------------------------------------

	{
	typedef multivecsorted< sarray<int,32> > vecs_t;
	vecs_t vecs;

	vecs.insert(1);
	vecs.insert(2);
	vecs.insert(0);
	vecs.insert(7);
	vecs.insert(4);
	vecs.insert(3);
	
	struct Local
	{
	static void printint(const int & i)
	{
		printf("%d,",i);
	}
	};
	
	puts("X");

	std::for_each(vecs.begin(),vecs.end(),Local::printint);

	puts("X");

	vecs_t::const_iterator it = vecs.find(1);
	vecs.erase(it);
	
	vecs.erase( vecs.find(4) );
	vecs.erase( vecs.find(7) );
	vecs.erase( vecs.find(6) );

	std::for_each(vecs.begin(),vecs.end(),Local::printint);

	puts("X");
	
	std::vector<int> v1;
	std::vector<int> v2(v1.begin(),v1.end());

	vecs_t vecs2(vecs);
	vecs_t vecs3(vecs.begin(),vecs.end(),vecsorted_construct::non_sorted);
	vecs_t vecs4(vecs.begin(),vecs.end(),vecsorted_construct::sorted);

	typedef vecsorted< sarray<int,32> > uvecs_t;

	vecs.insert(2);
	vecs.insert(2);
	uvecs_t vecs5(vecs.begin(),vecs.end(),vecsorted_construct::non_unique);
	int msize = vecs.size();
	int usize = vecs5.size();
	
	std::for_each(vecs.begin(),vecs.end(),Local::printint);

	puts("X");
	
	std::for_each(vecs5.begin(),vecs5.end(),Local::printint);

	puts("X");

	printf("multi size = %d, unique size = %d\n",msize,usize);
	}

	//-------------------------------------------------------------------------------------
}