---

test-sort_algorithms.cc

/*
*  Name:      test-sort_algorithms.cc
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   Test for sort algorithms
*  Date:      $Date: 2003/04/14 00:18:36 $
*  Revision:  $Revision: 1.1 $
*
*  Copyright (C) 1994-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
*  MA 02111-1307, USA.
*/

#include <algorithm>
#include <cstdlib>
#include <mpcl/util/strategy/bubble_sort_algorithm.hh>
#include <mpcl/util/strategy/quick_sort_algorithm.hh>
#include <mpcl/test.h>
#include <vector>


using mpcl::util::strategy::TBubbleSortAlgorithm;
using mpcl::util::strategy::TQuickSortAlgorithm;


//
//  L O C A L   T Y P E S
//

typedef std::vector<int> TVectorInt;


//
//  L O C A L   V A R I A B L E S
//

static TVectorInt   _tVector1;
static TVectorInt   _tVector2;
static TVectorInt   _tVector3;
static TVectorInt   _tVector4;
static TVectorInt   _tSortedVector1;
static TVectorInt   _tSortedVector2;
static TVectorInt   _tSortedVector3;
static TVectorInt   _tSortedVector4;


//
//  L O C A L   F U N C T I O N S
//

static int _StlSortTest (void)
{

  using std::sort;

  TVectorInt   tVector;

  TEST_INIT ("test for STL sorting algorithms");

  tVector = _tVector1;
  TEST_START_WATCH;
  sort (tVector.begin(), tVector.end());
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector1.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector1 ));
  TEST_DISPLAY_WATCH ("STL sort benchmark");

  tVector = _tVector2;
  TEST_START_WATCH;
  sort (tVector.begin(), tVector.end());
  TEST_STOP_WATCH;
  
  TEST_NUMBERS (_tVector2.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector2 ));
  TEST_DISPLAY_WATCH ("STL sort benchmark");

  tVector = _tVector3;
  TEST_START_WATCH;
  sort (tVector.begin(), tVector.end());
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector3.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector3 ));
  TEST_DISPLAY_WATCH ("STL sort benchmark");

  tVector = _tVector4;
  TEST_START_WATCH;
  sort (tVector.begin(), tVector.end());
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector4.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector4 ));
  TEST_DISPLAY_WATCH ("STL sort benchmark");

  TEST_RETURN_CODE;

}  // _StlSortTest()


static int _QuickSortTest (void)
{

  TVectorInt                        tVector;
  TQuickSortAlgorithm<TVectorInt>   tQuickSort;

  TEST_INIT ("test for class 'TQuickSortAlgorithm'");

  tVector = _tVector1;
  TEST_START_WATCH;
  tQuickSort.execute (tVector);
  TEST_STOP_WATCH;
 
  TEST_NUMBERS (_tVector1.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector1 ));
  
  TEST_DISPLAY_WATCH ("'TQuickSortAlgorithm' sort benchmark");

  tVector = _tVector2;
  TEST_START_WATCH;
  tQuickSort.execute (tVector);
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector2.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector2 ));
  TEST_DISPLAY_WATCH ("'TQuickSortAlgorithm' sort benchmark");

  tVector = _tVector3;
  TEST_START_WATCH;
  tQuickSort.execute (tVector);
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector3.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector3 ));
  TEST_DISPLAY_WATCH ("'TQuickSortAlgorithm' sort benchmark");

  tVector = _tVector4;
  TEST_START_WATCH;
  tQuickSort.execute (tVector);
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector4.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector4 ));
  TEST_DISPLAY_WATCH ("'TQuickSortAlgorithm' sort benchmark");
  TEST_RETURN_CODE;

}  // _QuickSortTest()


static int _BubbleSortTest (void)
{

  TVectorInt                         tVector;
  TBubbleSortAlgorithm<TVectorInt>   tBubbleSort;

  TEST_INIT ("test for class 'TBubbleSortAlgorithm'");

  tVector = _tVector1;
  TEST_START_WATCH;
  tBubbleSort.execute (tVector);
  TEST_STOP_WATCH;

  TEST_NUMBERS (_tVector1.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector1 ));
  TEST_DISPLAY_WATCH ("'TBubbleSortAlgorithm' sort benchmark");

  tVector = _tVector2;
  TEST_START_WATCH;
  tBubbleSort.execute (tVector);
  TEST_STOP_WATCH;
  
  TEST_NUMBERS (_tVector2.size(), tVector.size());
  TEST_NUMBERS (true, ( tVector == _tSortedVector2 ));
  TEST_DISPLAY_WATCH ("'TBubbleSortAlgorithm' sort benchmark");

  //
  //  Benchmarks over _tVector3 and _tVector4 is not feasible due to the
  //  excessive amount of time needed to finish.
  //
  
  TEST_RETURN_CODE;

}  // _BubbleSortTest()


int main (void)
{

  using std::sort;

  register size_t   zIndex;
  const size_t      kzSizeBigVector = 100000;
 
  TEST_INIT ("tests for Sort Algorithms");
  TEST_START_WATCH;

  //
  //  Generation of first array: 
  //
  //    [1, 1, 1, 2, 1, 1, 1]
  //
  _tVector1.push_back (1);
  _tVector1.push_back (1);
  _tVector1.push_back (1);
  _tVector1.push_back (2);
  _tVector1.push_back (1);
  _tVector1.push_back (1);
  _tVector1.push_back (1);

  //
  //  Generation of a sorted version of the first array: 
  //  
  //    [1, 1, 1, 1, 1, 1, 2]
  //
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (1);
  _tSortedVector1.push_back (2);

  //
  //  Generation of second array: 
  //
  //    [10, 9, 8, 7, 6, 5, 4]
  //
  _tVector2.push_back (10);
  _tVector2.push_back (9);
  _tVector2.push_back (8);
  _tVector2.push_back (7);
  _tVector2.push_back (6);
  _tVector2.push_back (5);
  _tVector2.push_back (4);

  //
  //  Generation of a sorted version of the second array: 
  //  
  //    [4, 5, 6, 7, 8, 9, 10]
  //
  _tSortedVector2.push_back (4);
  _tSortedVector2.push_back (5);
  _tSortedVector2.push_back (6);
  _tSortedVector2.push_back (7);
  _tSortedVector2.push_back (8);
  _tSortedVector2.push_back (9);
  _tSortedVector2.push_back (10);

  //
  //  Check time for entering kzSizeBigVector elements.
  //
  TEST_START_WATCH;

  //
  //  Generation of third array: 
  //
  //    [kzSizeBigVector, kzSizeBigVector - 1,... 1]
  //
  for (zIndex = 0; ( zIndex < kzSizeBigVector ) ;++zIndex)
  {
    _tVector3.push_back (kzSizeBigVector - zIndex);
  }

  //
  //  Generation of a sorted version of the third array: 
  //  
  //    [1, 2, 3,... kzSizeBigVector]
  //
  for (zIndex = 1; ( zIndex <= kzSizeBigVector ) ;++zIndex)
  {
    _tSortedVector3.push_back (zIndex);
  }

  //
  //  Generation of fourth array: 
  //
  //    [rand(), rand(),... rand()]
  //
  for (zIndex = 0; ( zIndex < kzSizeBigVector ) ;++zIndex)
  {
    _tVector4.push_back (rand());
  }

  //
  //  Generation of a sorted version of the fourth array: 
  //
  _tSortedVector4 = _tVector4;
  sort (_tSortedVector4.begin(), _tSortedVector4.end());

  TEST_STOP_WATCH;
  TEST_DISPLAY_WATCH ("STL sort benchmark");

  TEST_NUMBERS (kzSizeBigVector, _tVector3.size());
  TEST_NUMBERS (kzSizeBigVector, _tSortedVector3.size());
  TEST_NUMBERS (kzSizeBigVector, _tVector4.size());
  TEST_NUMBERS (kzSizeBigVector, _tSortedVector4.size());

  TEST_FUNCTION (_StlSortTest());
  TEST_FUNCTION (_QuickSortTest());
  TEST_FUNCTION (_BubbleSortTest());

  TEST_MEMORY_STATUS;
  TEST_RETURN_CODE;

}  // main()

---