nucleus/library/tests_algorithms/test_sorts.cpp

   1 /*
   2 *  Name   : test_sorts
   3 *  Author : Chris Koeritz
   4 **
   5 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
   6 * redistribute it and/or modify it under the terms of the GNU General Public  *
   7 * License as published by the Free Software Foundation; either version 2 of   *
   8 * the License or (at your option) any later version.  This is online at:      *
   9 *     http://www.fsf.org/copyleft/gpl.html                                    *
  10 * Please send any updates to: fred@gruntose.com                               *
  11 */
  12
  13 #include <application/hoople_main.h>
  14 #include <basis/functions.h>
  15 #include <basis/guards.h>
  16 #include <loggers/console_logger.h>
  17 #include <mathematics/chaos.h>
  18 #include <structures/static_memory_gremlin.h>
  19 #include <unit_test/unit_base.h>
  20 #include <algorithms/sorts.h>
  21
  22 using namespace algorithms;
  23 using namespace application;
  24 using namespace basis;
  25 using namespace loggers;
  26 using namespace mathematics;
  27 using namespace structures;
  28 using namespace textual;
  29 using namespace timely;
  30 using namespace unit_test;
  31
  32 const int MAX_ELEMENTS = 1200;
  33
  34 const int MAX_VALUE = 28000;
  35
  36 #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger().get(), to_print)
  37
  38 class test_sorts : virtual public unit_base, virtual public application_shell
  39 {
  40 public:
  41   test_sorts() : application_shell() {}
  42   DEFINE_CLASS_NAME("test_sorts");
  43
  44   int *populate_random_c_array(int size);
  45   basis::array<int> populate_random_array(int size);
  46   int test_shell_sort(int *list, int size);
  47
  48   virtual int execute();
  49 };
  50
  51 int *test_sorts::populate_random_c_array(int size)
  52 {
  53         int *list = new int[size];
  54         for (int i = 0; i < size; i++)
  55                 list[i] = randomizer().inclusive(0, MAX_VALUE);
  56         return list;
  57 }
  58
  59 basis::array<int> test_sorts::populate_random_array(int size)
  60 {
  61         basis::array<int> to_return(size);
  62         for (int i = 0; i < size; i++)
  63                 to_return[i] = randomizer().inclusive(0, MAX_VALUE);
  64         return to_return;
  65 }
  66
  67 int test_sorts::test_shell_sort(int *list, int size)
  68 {
  69   FUNCDEF("test_shell_sort");
  70
  71   // check a normal sort.
  72   shell_sort(list, size);
  73   int last = -1;
  74   for (int j = 0; j < size; j++) {
  75     ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check");
  76     last = list[j];
  77   }
  78
  79   // re-randomize the list.
  80   for (int i = 0; i < size; i++)
  81     list[i] = randomizer().inclusive(0, MAX_VALUE);
  82
  83   // check a reversed sort.
  84   shell_sort(list, size, true);
  85   last = MAX_VALUE + 100;  // past the maximum we'll include in the list.
  86   for (int j = 0; j < size; j++) {
  87     ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check");
  88     last = list[j];
  89   }
  90
  91   // clean up now.
  92   delete [] list;
  93
  94   //hmmm: wait, what if it fails above?
  95   return true;
  96 }
  97
  98 int test_sorts::execute()
  99 {
 100   FUNCDEF("execute");
 101
 102   int size = MAX_ELEMENTS;
 103
 104 //astring ret;
 105 //for (int i = 0; i < size; i++) ret += a_sprintf("%d ", list[i]);
 106 //LOG(ret);
 107 //LOG("-------------");
 108
 109   test_shell_sort(populate_random_c_array(size), size);
 110
 111 //  test_quick_sort(populate_random_list(size), size);
 112
 113 //  test_merge_sort(populate_random_array(size));
 114
 115   return final_report();
 116 }
 117
 118 HOOPLE_MAIN(test_sorts, )
 119