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 = 30;
  33 //1200
  34
  35 const int MAX_VALUE = 28000;
  36
  37 #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger().get(), to_print)
  38
  39 class test_sorts : virtual public unit_base, virtual public application_shell
  40 {
  41 public:
  42         test_sorts()
  43                         : application_shell()
  44         {
  45         }
  46         DEFINE_CLASS_NAME("test_sorts")
  47         ;
  48
  49         int *populate_random_c_array(int size);
  50         basis::array<int> populate_random_array(int size);
  51
  52         void test_shell_sort(int *list, int size);
  53         void test_heap_sort(int *list, int size);
  54         void test_merge_sort(basis::array<int> &list);
  55
  56         virtual int execute();
  57 };
  58
  59 int *test_sorts::populate_random_c_array(int size)
  60 {
  61         int *list = new int[size];
  62         for (int i = 0; i < size; i++)
  63                 list[i] = randomizer().inclusive(0, MAX_VALUE);
  64         return list;
  65 }
  66
  67 basis::array<int> test_sorts::populate_random_array(int size)
  68 {
  69         basis::array<int> to_return(size);
  70         for (int i = 0; i < size; i++)
  71                 to_return[i] = randomizer().inclusive(0, MAX_VALUE);
  72         return to_return;
  73 }
  74
  75 //hmmm: this pattern is very silly.  it's nearly cookie cutter, so why not implement a templated version?
  76 // one diff is the C array versus basis array usage.
  77
  78 void test_sorts::test_shell_sort(int *list, int size)
  79 {
  80         FUNCDEF("test_shell_sort");
  81
  82         // check a normal sort.
  83         shell_sort(list, size);
  84         int last = -1;
  85         for (int j = 0; j < size; j++) {
  86                 ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check");
  87                 last = list[j];
  88         }
  89
  90         // re-randomize the list.
  91         for (int i = 0; i < size; i++)
  92                 list[i] = randomizer().inclusive(0, MAX_VALUE);
  93
  94         // check a reversed sort.
  95         shell_sort(list, size, true);
  96         last = MAX_VALUE + 100;  // past the maximum we'll include in the list.
  97         for (int j = 0; j < size; j++) {
  98                 ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check");
  99                 last = list[j];
 100         }
 101
 102         // clean up now.
 103         delete[] list;
 104 }
 105
 106 void test_sorts::test_heap_sort(int *list, int size)
 107 {
 108         FUNCDEF("test_heap_sort");
 109
 110         // check a normal sort.
 111         heap_sort(list, size);
 112
 113         int last = -1;
 114         for (int j = 0; j < size; j++) {
 115                 ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check");
 116                 last = list[j];
 117         }
 118
 119         // re-randomize the list.
 120         for (int i = 0; i < size; i++)
 121                 list[i] = randomizer().inclusive(0, MAX_VALUE);
 122
 123         // check a reversed sort.
 124         heap_sort(list, size, true);
 125
 126         last = MAX_VALUE + 100;  // past the maximum we'll include in the list.
 127         for (int j = 0; j < size; j++) {
 128                 ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check");
 129                 last = list[j];
 130         }
 131
 132         // clean up now.
 133         delete[] list;
 134 }
 135
 136 void test_sorts::test_merge_sort(basis::array<int> &list)
 137 {
 138         FUNCDEF("test_merge_sort");
 139
 140         // check a normal sort.
 141         basis::array<int> ret = merge_sort(list);
 142
 143 //      LOG(a_sprintf("list has %d elems", ret.length()));
 144 //      LOG(astring("list has ") + dump_list(ret.observe(), ret.length()));
 145
 146         int last = -1;
 147         for (int j = 0; j < list.length(); j++) {
 148                 ASSERT_FALSE(ret[j] < last, "ordering check - list should be ordered at first check");
 149                 last = ret[j];
 150         }
 151
 152         // re-randomize the list.
 153         for (int i = 0; i < list.length(); i++)
 154                 list[i] = randomizer().inclusive(0, MAX_VALUE);
 155
 156         // check a reversed sort.
 157         ret = merge_sort(list, true);
 158
 159         last = MAX_VALUE + 100;  // past the maximum we'll include in the list.
 160         for (int j = 0; j < list.length(); j++) {
 161                 ASSERT_FALSE(ret[j] > last, "ordering check - list should be ordered at second check");
 162                 last = ret[j];
 163         }
 164 }
 165
 166 int test_sorts::execute()
 167 {
 168         FUNCDEF("execute");
 169
 170         int size = MAX_ELEMENTS;
 171
 172         test_shell_sort(populate_random_c_array(size), size);
 173
 174         test_heap_sort(populate_random_c_array(size), size);
 175
 176         basis::array<int> testarray = populate_random_array(size);
 177         test_merge_sort(testarray);
 178
 179         //  test_quick_sort(populate_random_array(size), size);
 180
 181
 182         return final_report();
 183 }
 184
 185 HOOPLE_MAIN(test_sorts,)
 186