/*****************************************************************************
 * $Id: InsertionSort.cc,v 1.1 2006/10/29 23:59:58 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Test of InsertionSort().
 *//*
 * LEGAL:	COPYRIGHT (C) 2006 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define TESTING 1
#include <vector>
#include "test.hh"
#include "gfx_sort.hh"
#include "gfx_random.hh"

/*****************************************************************************
 * Test.
 *****************************************************************************/
namespace gfx {

enum eHeapOrder { eHeapOrder_ORDER, eHeapOrder_REVERSE, eHeapOrder_RANDOM };

static bool
InsertionSortTest( const uint n, eHeapOrder order )
{
	std::vector<int> heap1( n );
	std::vector<int> heap2( n );
	if ( heap1.size () != n ) return false;
	if ( heap2.size () != n ) return false;
	for ( uint i = 0; i < n; ++i )
	{
		int val;
		if      ( order == eHeapOrder_ORDER )   val = i;
		else if ( order == eHeapOrder_REVERSE ) val = n - i;
		else if ( order == eHeapOrder_RANDOM )	val = random_ui();
		else		                            return false;
		heap1[i] = heap2[i] = val;
	}
	InsertionSort( heap1 );
	std::sort( heap2.begin(), heap2.end() );
	return heap1 == heap2;  // the power of the STL
}

static bool
InsertionSortTest( const uint n )
{
	return InsertionSortTest( n, eHeapOrder_ORDER )
        && InsertionSortTest( n, eHeapOrder_REVERSE )
        && InsertionSortTest( n, eHeapOrder_RANDOM );
}

bool
InsertionSortTest( void )
{
	if ( ! InsertionSortTest(0) ) { Fail(); }
	if ( ! InsertionSortTest(1) ) { Fail(); }
	if ( ! InsertionSortTest(2) ) { Fail(); }
	if ( ! InsertionSortTest(3) ) { Fail(); }
	if ( ! InsertionSortTest(4) ) { Fail(); }
	if ( ! InsertionSortTest(5) ) { Fail(); }
	if ( ! InsertionSortTest(100) ) { Fail(); }
	if ( ! InsertionSortTest(101) ) { Fail(); }
	if ( ! InsertionSortTest(102) ) { Fail(); }
	if ( ! InsertionSortTest(15000) ) { Fail(); }
	return true;
}
} // namespace gfx

/*****************************************************************************
 * main.
 *****************************************************************************/
int
main( int argc, char** argv )
{
	GFX_INIT( argv[0] );
	int res = 1;
	if ( InsertionSortTest() )
	{
		cerr << "Test PASSED. \n";
		res = 0;
	}
	else
	{
		cerr << "Test FAILED! \n";
		res = 1;
	}
	GFX_CLEANUP();
	exit( res );
}
