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

   test_algo.cpp

  * Copyright (c) 1997

  * Mark of the Unicorn, Inc.

  *

  * Permission to use, copy, modify, distribute and sell this software

  * and its documentation for any purpose is hereby granted without fee,

  * provided that the above copyright notice appear in all copies and

  * that both that copyright notice and this permission notice appear

  * in supporting documentation.  Mark of the Unicorn makes no

  * representations about the suitability of this software for any

  * purpose.  It is provided "as is" without express or implied warranty.

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

 #include "Tests.h"

 #include "LeakCheck.h"

 #include "SortClass.h"

 #if defined (EH_NEW_HEADERS)

 # include <algorithm>

 # include <cassert>

 #else

 # include <algo.h>

 # include <assert.h>

 #endif

 #if defined (EH_NEW_IOSTREAMS)

 # include <iostream>

 #else

 # include <iostream.h>

 #endif

 //

 // SortBuffer -- a buffer of SortClass objects that can be used to test sorting.

 //

 struct SortBuffer

 {

     enum { kBufferSize = 100 };

     SortClass* begin() { return items; }

     const SortClass* begin() const { return items; }

     SortClass* end() { return items + kBufferSize; }

     const SortClass* end() const { return items + kBufferSize; }

   // Sort each half of the buffer and reset the address of each element

   // so that merge() can be tested for stability.

     void PrepareMerge()

     {

         EH_STD::sort( begin(), begin() + ( end() - begin() )/2 );

         EH_STD::sort( begin() + ( end() - begin() )/2, end() );

         for ( SortClass* p = begin(); p != end(); p++ )

             p->ResetAddress();

     }

   SortBuffer()

   {

     PrepareMerge();

   }

   SortBuffer( const SortBuffer& rhs )

   {

     SortClass* q = begin();

     for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ )

       *q = *p;

   }

 private:

     SortClass items[kBufferSize];

 };

 //

 // less_by_reference -- a functor for comparing objects against a

 //   constant value.

 //

 template <class T>

 struct less_by_reference

 {

     less_by_reference( const T& arg ) : fArg(arg) {}

     bool operator()( const T& x ) const { return x < fArg; }

 private:

     const T& fArg;

 };

 struct test_stable_partition

 {

     test_stable_partition( const SortBuffer& buf )

         : orig( buf ), partitionPoint(SortClass::kRange / 2) {

         gTestController.SetCurrentTestName("stable_partition()");

         }

     void operator()( SortBuffer& buf ) const

     {

         less_by_reference<SortClass> throw_cmp( partitionPoint );

         SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp );

     // If we get here no exception occurred during the operation.

     // Stop any potential failures that might occur during verification.

         gTestController.CancelFailureCountdown();

         // Prepare an array of counts of the occurrence of each value in

         // the legal range.

         unsigned counts[SortClass::kRange];

         EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );

         for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )

             counts[ q->value() ]++;

         less_by_reference<TestClass> cmp( partitionPoint );

         for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )

         {

           // Check that adjacent items with the same value haven't been

           // reordered. This could be a more thorough test.

             if ( p != buf.begin() && p->value() == p[-1].value() )

                 EH_ASSERT( p->GetAddress() > p[-1].GetAddress() );

             // Check that the partitioning worked.

             EH_ASSERT( (p < d) == cmp( *p ) );

             // Decrement the appropriate count for each value.

             counts[ p->value() ]--;

         }

         // Check that the values were only rearranged, and none were lost.

         for ( unsigned j = 0; j < SortClass::kRange; j++ )

             EH_ASSERT( counts[j] == 0 );

     }

 private:

     const SortBuffer& orig;

     SortClass partitionPoint;

 };

 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf );

 /*===================================================================================

   assert_sorted_version

   EFFECTS: Asserts that buf is a stable-sorted version of orig.

 ====================================================================================*/

 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )

 {

   // Stop any potential failures that might occur during verification.

     gTestController.CancelFailureCountdown();

     // Prepare an array of counts of the occurrence of each value in

     // the legal range.

     unsigned counts[SortClass::kRange];

     EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );

     for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )

         counts[ q->value() ]++;

   // Check that each element is greater than the previous one, or if they are

   // equal, that their order has been preserved.

     for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )

     {

         if ( p != buf.begin() )

             EH_ASSERT( p->value() > p[-1].value()

                     || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() );

     // Decrement the appropriate count for each value.

         counts[ p->value() ]--;

     }

   // Check that the values were only rearranged, and none were lost.

     for ( unsigned j = 0; j < SortClass::kRange; j++ )

         EH_ASSERT( counts[j] == 0 );

 }

 //

 // The test operators

 //

 struct test_stable_sort_1

 {

     test_stable_sort_1( const SortBuffer& buf )

         : orig( buf ) {

         gTestController.SetCurrentTestName("stable_sort() #1");

         }

     void operator()( SortBuffer& buf ) const

     {

         EH_STD::stable_sort( buf.begin(), buf.end() );

         assert_sorted_version( orig, buf );

     }

 private:

     const SortBuffer& orig;

 };

 struct test_stable_sort_2

 {

     test_stable_sort_2( const SortBuffer& buf )

         : orig( buf ) {

             gTestController.SetCurrentTestName("stable_sort() #2");

         }

     void operator()( SortBuffer& buf ) const

     {

       EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() );

       assert_sorted_version( orig, buf );

     }

 private:

     const SortBuffer& orig;

 };

 struct test_inplace_merge_1

 {

     test_inplace_merge_1( SortBuffer& buf )

         : orig( buf ) {

         gTestController.SetCurrentTestName("inplace_merge #1()");

         }

     void operator()( SortBuffer& buf ) const

     {

         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() );

         assert_sorted_version( orig, buf );

     }

 private:

     const SortBuffer& orig;

 };

 struct test_inplace_merge_2

 {

     test_inplace_merge_2( SortBuffer& buf )

         : orig( buf ) {

         gTestController.SetCurrentTestName("inplace_merge() #2");

         }

     void operator()( SortBuffer& buf ) const

     {

         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(),

                        EH_STD::less<SortClass>() );

         assert_sorted_version( orig, buf );

     }

 private:

     const SortBuffer& orig;

 };

 void test_algo()

 {

     SortBuffer mergeBuf;

     mergeBuf.PrepareMerge();

     EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl;

     WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) );

     WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) );

     SortBuffer buf;

     WeakCheck( buf, test_stable_sort_1( buf ) );

     WeakCheck( buf, test_stable_sort_2( buf ) );

     WeakCheck( buf, test_stable_partition( buf ) );

 }