#include <vector>

#include <algorithm>

#include <functional>

#if defined (STLPORT) && defined (_STLP_DEBUG) && defined (_STLP_DEBUG_MODE_THROWS)

#  define _STLP_DO_CHECK_BAD_PREDICATE

#  include <stdexcept>

#endif

#include "cppunit/cppunit_proxy.h"

#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)

using namespace std;

#endif

//

// TestCase class

//

class SortTest : public CPPUNIT_NS::TestCase

{

  CPPUNIT_TEST_SUITE(SortTest);

  CPPUNIT_TEST(sort1);

  CPPUNIT_TEST(sort2);

  CPPUNIT_TEST(sort3);

  CPPUNIT_TEST(sort4);

  CPPUNIT_TEST(stblsrt1);

  CPPUNIT_TEST(stblsrt2);

#if defined (_STLP_DO_CHECK_BAD_PREDICATE)

  CPPUNIT_TEST(bad_predicate_detected);

#endif

  CPPUNIT_TEST_SUITE_END();

protected:

  void sort1();

  void sort2();

  void sort3();

  void sort4();

  void stblsrt1();

  void stblsrt2();

  void bad_predicate_detected();

  static bool string_less(const char* a_, const char* b_)

  {

    return strcmp(a_, b_) < 0 ? 1 : 0;

  }

};

CPPUNIT_TEST_SUITE_REGISTRATION(SortTest);

//

// tests implementation

//

void SortTest::stblsrt1()

{

  //Check that stable_sort do sort

  int numbers[6] = { 1, 50, -10, 11, 42, 19 };

  stable_sort(numbers, numbers + 6);

  //-10 1 11 19 42 50

  CPPUNIT_ASSERT(numbers[0]==-10);

  CPPUNIT_ASSERT(numbers[1]==1);

  CPPUNIT_ASSERT(numbers[2]==11);

  CPPUNIT_ASSERT(numbers[3]==19);

  CPPUNIT_ASSERT(numbers[4]==42);

  CPPUNIT_ASSERT(numbers[5]==50);

  char const* letters[6] = {"bb", "aa", "ll", "dd", "qq", "cc" };

  stable_sort(letters, letters + 6, string_less);

  // aa bb cc dd ll qq

  CPPUNIT_ASSERT( strcmp(letters[0], "aa") == 0 );

  CPPUNIT_ASSERT( strcmp(letters[1], "bb") == 0 );

  CPPUNIT_ASSERT( strcmp(letters[2], "cc") == 0 );

  CPPUNIT_ASSERT( strcmp(letters[3], "dd") == 0 );

  CPPUNIT_ASSERT( strcmp(letters[4], "ll") == 0 );

  CPPUNIT_ASSERT( strcmp(letters[5], "qq") == 0 );

}

struct Data {

  Data(int index, int value)

    : m_index(index), m_value(value) {}

  bool operator == (const Data& other) const

  { return m_index == other.m_index && m_value == other.m_value; }

  bool operator < (const Data& other) const

  { return m_value < other.m_value; }

private:

  int m_index, m_value;

};

void SortTest::stblsrt2()

{

  //Check that stable_sort is stable:

  Data datas[] = {

    Data(0, 10),

    Data(1, 8),

    Data(2, 6),

    Data(3, 6),

    Data(4, 6),

    Data(5, 4),

    Data(6, 9)

  };

  stable_sort(datas, datas + 7);

  CPPUNIT_ASSERT( datas[0] == Data(5, 4) );

  CPPUNIT_ASSERT( datas[1] == Data(2, 6) );

  CPPUNIT_ASSERT( datas[2] == Data(3, 6) );

  CPPUNIT_ASSERT( datas[3] == Data(4, 6) );

  CPPUNIT_ASSERT( datas[4] == Data(1, 8) );

  CPPUNIT_ASSERT( datas[5] == Data(6, 9) );

  CPPUNIT_ASSERT( datas[6] == Data(0, 10) );

}

void SortTest::sort1()

{

  int numbers[6] = { 1, 50, -10, 11, 42, 19 };

  sort(numbers, numbers + 6);

  // -10 1 11 19 42 50

  CPPUNIT_ASSERT(numbers[0]==-10);

  CPPUNIT_ASSERT(numbers[1]==1);

  CPPUNIT_ASSERT(numbers[2]==11);

  CPPUNIT_ASSERT(numbers[3]==19);

  CPPUNIT_ASSERT(numbers[4]==42);

  CPPUNIT_ASSERT(numbers[5]==50);

}

void SortTest::sort2()

{

  int numbers[] = { 1, 50, -10, 11, 42, 19 };

  int count = sizeof(numbers) / sizeof(numbers[0]);

  sort(numbers, numbers + count, greater<int>());

  //  50 42 19 11 1 -10

  CPPUNIT_ASSERT(numbers[5]==-10);

  CPPUNIT_ASSERT(numbers[4]==1);

  CPPUNIT_ASSERT(numbers[3]==11);

  CPPUNIT_ASSERT(numbers[2]==19);

  CPPUNIT_ASSERT(numbers[1]==42);

  CPPUNIT_ASSERT(numbers[0]==50);

}

void SortTest::sort3()

{

  vector<bool> boolVector;

  boolVector.push_back( true );

  boolVector.push_back( false );

  sort( boolVector.begin(), boolVector.end() );

  CPPUNIT_ASSERT(boolVector[0]==false);

  CPPUNIT_ASSERT(boolVector[1]==true);

}

/*

 * A small utility class to check a potential compiler bug

 * that can result in a bad sort algorithm behavior. The type

 * _Tp of the SortTestFunc has to be SortTestAux without any

 * reference qualifier.

 */

struct SortTestAux {

  SortTestAux (bool &b) : _b(b)

  {}

  SortTestAux (SortTestAux const&other) : _b(other._b) {

    _b = true;

  }

  bool &_b;

private:

  //explicitely defined as private to avoid warnings:

  SortTestAux& operator = (SortTestAux const&);

};

template <class _Tp>

void SortTestFunc (_Tp) {

}

void SortTest::sort4()

{

  bool copy_constructor_called = false;

  SortTestAux instance(copy_constructor_called);

  SortTestAux &r_instance = instance;

  SortTestAux const& rc_instance = instance;

  SortTestFunc(r_instance);

  CPPUNIT_ASSERT(copy_constructor_called);

  copy_constructor_called = false;

  SortTestFunc(rc_instance);

  CPPUNIT_ASSERT(copy_constructor_called);

}

#if defined (_STLP_DO_CHECK_BAD_PREDICATE)

void SortTest::bad_predicate_detected()

{

  int numbers[] = { 0, 0, 1, 0, 0, 1, 0, 0 };

  try {

    sort(numbers, numbers + sizeof(numbers) / sizeof(numbers[0]), less_equal<int>());

    //Here is means that no exception has been raised

    CPPUNIT_ASSERT( false );

  }

  catch (runtime_error const&)

  { /*OK bad predicate has been detected.*/ }

  try {

    stable_sort(numbers, numbers + sizeof(numbers) / sizeof(numbers[0]), less_equal<int>());

    //Here is means that no exception has been raised

    CPPUNIT_ASSERT( false );

  }

  catch (runtime_error const&)

  { /*OK bad predicate has been detected.*/ }

}

#endif