/*********************************************************
** Copyright (c) 2005
** University of Washington
** Licensed under the terms set forth by University of
** Washington. If you did not sign such a license, you
** are using this software/code illegally and you do not
** have permission to use, modify, or redistribute
** this or any files in this software package.
**
** File: SortTest.h
**
**********************************************************/
#ifndef __SORTTEST__
#define __SORTTEST__

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

/*
 * Class for testing/demonstrating
 * STL sort algorithms.
 */

typedef pair<double, int> PairType;
typedef vector<PairType*> VectorType;

struct less_PairType : public binary_function<PairType*, PairType*, bool> {
  bool operator()(PairType* x, PairType* y) 
  { 
    if(NULL == x || NULL == y) return false;

    return x->first < y->first;
  }
};

class CSortTest : public CUnitTestClass
{
 public:
  CSortTest() : CUnitTestClass("SortTest")
  {
  }

 protected:
  void RunTests()
  {
    TestSortPairs();
    TestCCostMap();
    //TestPerf();
    TestMemoryAllocation();
  }

 private:
  void TestSortPairs()
  {
    BeginTest("TestSortPairs");
    bool success = true;
    
    string expected = "[2, 3], [5, 4], [7, 1], [9, 0], [45, 2], ";
#undef DATALEN
#define DATALEN 5
    double pData[DATALEN] = {9, 7, 45, 2, 5};
    VectorType pairs;

    try
    {
      // Construct the data vector.
      for(int i = 0; i < DATALEN; i++)
	pairs.push_back(new PairType(pData[i], i));

      // Sort.
      sort(pairs.begin(), pairs.end(), less_PairType());
     
      // Construct output string
      stringstream sstr;
      for(VectorType::iterator i = pairs.begin(); i != pairs.end(); i++)
	sstr << "[" << (*i)->first << ", " << (*i)->second << "], ";
      
      // Compare results to expected results
      if(sstr.str() != expected)
	{
	  cout << "Actual sorted string         : " << sstr.str() << "\n";
	  cout << "Expected sorted string: " << expected << "\n";
	  __throw_message("sorted string was not as expected");
	}

    }
    catch(CTestException *pEx)
    {
      success = false;
      cout << pEx->Message() << "\n";
      delete pEx;
    }
    catch(...)
    {
      success = false;
      cout << "something's wrong\n";
    }
    
    for(VectorType::iterator i = pairs.begin(); i != pairs.end(); i++)
      {
	delete (*i);
      }

    EndTest(success);
  }

  void TestCCostMap()
  {
    BeginTest("TestCCostMap");
    bool success = true;
    
    string expected = "[2, 3], [5, 4], [7, 1], [9, 0], [45, 2], ";
#define DATALEN 5
    double pData[DATALEN] = {9, 7, 45, 2, 5};
    CCostMap pairs;

    try
    {
      // Construct the data vector.
      for(int i = 0; i < DATALEN; i++)
	pairs.insert(pair<double,int>(pData[i], i));

      // Sort.
      pairs.sort();
     
      // Construct output string
      stringstream sstr;
      for(CCostMap::iterator i = pairs.begin(); i != pairs.end(); i++)
	sstr << "[" << (*i).first << ", " << (*i).second << "], ";
      
      // Compare results to expected results
      if(sstr.str() != expected)
	{
	  cout << "Actual sorted string         : " << sstr.str() << "\n";
	  cout << "Expected sorted string: " << expected << "\n";
	  __throw_message("sorted string was not as expected");
	}

    }
    catch(CTestException *pEx)
    {
      success = false;
      cout << pEx->Message() << "\n";
      delete pEx;
    }
    catch(...)
    {
      success = false;
      cout << "something's wrong\n";
    }
    
    EndTest(success);
  }

  // Tests use of a map vs. use of CCostMap
  typedef map<double, int> TCostMap;
  void TestPerf()
  {
    BeginTest("TestPerf");
    bool success = true;
#undef DATALEN
#define DATALEN 10000
    double* pData;
    clock_t start1, end1, start2, end2;

    try
    {
      pData = new double[DATALEN];
      if (NULL == pData)
	__throw_message("Could not allocate pData");

      // Populate pData with numbers from 2000 down to 1000
      int val = DATALEN + DATALEN - 1;
      for(int i = 0; i < DATALEN; i++, val--)
	pData[i] = val;

      // Part 1. Construct and sort a CCostMap.
      start1 = clock();
      if((clock_t)-1 == start1)
	__throw_message("Could not get start1 time");

      CCostMap cMap;
      for(int i = 0; i < DATALEN; i++)
	cMap.insert(pair<double, int>(pData[i], i));
      
      cMap.sort();
		   
      end1 = clock();
      if((clock_t)-1 == end1)
	__throw_message("Could not get end1 time");


      // Part 2. Construct and sort a TCostMap.
      start2 = clock();
      if((clock_t)-1 == start2)
	__throw_message("Could not get start2 time");

      TCostMap tMap;
      for(int i = 0; i < DATALEN; i++)
	tMap.insert(pair<double, int>(pData[i], i));

      // No need to sort; data is sorted as it is inserted

      end2 = clock();
      if((clock_t)-1 == end2)
	__throw_message("Could not get end2 time");

      // Part 3. Compare their performance.
      clock_t time1 = end1-start1;
      clock_t time2 = end2-start2;

      // Compare results to expected results
      cout << "Time for CCostMap: " << time1 << "; ";
      cout << "Time for TCostMap: " << time2 << "; ";

      if(time1 > time2)
	{
	  __throw_message("CCostMap does not perform better for given number of items.");
	}

      // Make sure sorting worked correctly
      int j = 0;
      for(CCostMap::iterator i = cMap.begin(); i != cMap.end(); i++, j++)
	{
	  if((*i).first != j + DATALEN)
	    {
	      cout << "Element " << j << " was " << (*i).first << ", should be " << j + DATALEN << "\n";
	      __throw_message("CCostMap elements different");
	    }
	}
    }
    catch(CTestException *pEx)
    {
      success = false;
      cout << pEx->Message() << "\n";
      delete pEx;
    }
    catch(...)
    {
      success = false;
      cout << "something's wrong\n";
    }

    delete [] pData;

    EndTest(success);
    
  }

// 1/4 GB
#define QUARTERGIG 268435455L

  void TestMemoryAllocation()
  {
    BeginTest("TestPerf");
    // this test fails unless an exception is thrown
    bool success = false;

    // try to allocate a very large amount of memory... 4 GB
    double* bigArray[16];

    try
    {
      for(int i = 0; i < 10; i++)
	bigArray[i] = NULL;

      printf("\n");
      for(int i = 0; i < 10; i++)
	{
	  printf("allocating %d\n", i);
	  __catch_badalloc(bigArray[i] = new double[QUARTERGIG]);
	  if (NULL == bigArray[i])
	    __throw_message("Could not allocate huge array");
	}
      
      __throw_message("You have too much memory for this test (>4GB). The test needs to be rewritten.");
    }
    catch(CTestException *pEx)
    {
      success = false;
      cout << pEx->Message() << "\n";
      delete pEx;
    }
    catch(CClusterException *pEx)
    {
      if (pEx->Id() == CLUSTEX_OUTOFMEMORY) {
	success = true;
      }
      else {
	success = false;
	cout << pEx->Message() << "\n";
      }
      delete pEx;
    }
    catch(...)
    {
      success = false;
      cout << "something's wrong\n";
    }

    for(int i = 0; i < 10; i++)
      delete bigArray[i];

    EndTest(success);
  }

};

#endif
