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()
  42                         : application_shell()
  43         {
  44         }
  45
  46         DEFINE_CLASS_NAME("test_sorts")
  47
  48         int *populate_random_c_array(int size);
  49         basis::array<int> populate_random_array(int size);
  50         void rerandomize(int list[], int size);
  51         bool verify_ascending(const int *list, int size);
  52         bool verify_descending(const int *list, int size);
  53
  54         void test_shell_sort(int size);
  55         void test_heap_sort(int size);
  56         void test_merge_sort(int size);
  57         void test_quick_sort(int size);
  58
  59         virtual int execute();
  60 };
  61
  62 int *test_sorts::populate_random_c_array(int size)
  63 {
  64         int *list = new int[size];
  65         for (int i = 0; i < size; i++)
  66                 list[i] = randomizer().inclusive(0, MAX_VALUE);
  67         return list;
  68 }
  69
  70 basis::array<int> test_sorts::populate_random_array(int size)
  71 {
  72         basis::array<int> to_return(size);
  73         for (int i = 0; i < size; i++)
  74                 to_return[i] = randomizer().inclusive(0, MAX_VALUE);
  75         return to_return;
  76 }
  77
  78 void test_sorts::rerandomize(int list[], int size)
  79 {
  80         for (int i = 0; i < size; i++)
  81                 list[i] = randomizer().inclusive(0, MAX_VALUE);
  82 }
  83
  84 bool test_sorts::verify_ascending(const int *list, int size)
  85 {
  86         FUNCDEF("verify_ascending")
  87         int last = list[0];
  88         for (int j = 1; j < size; j++) {
  89                 if (list[j] < last) return false;
  90                 last = list[j];
  91         }
  92         return true;
  93 }
  94
  95 bool test_sorts::verify_descending(const int *list, int size)
  96 {
  97         FUNCDEF("verify_descending")
  98         int last = list[0];
  99         for (int j = 1; j < size; j++) {
 100                 if (list[j] > last) return false;
 101                 last = list[j];
 102         }
 103         return true;
 104 }
 105
 106 void test_sorts::test_shell_sort(int size)
 107 {
 108         FUNCDEF("test_shell_sort");
 109
 110         int *list = populate_random_c_array(size);
 111
 112         // check a normal sort.
 113         shell_sort(list, size);
 114         ASSERT_TRUE(verify_ascending(list, size),
 115             "ordering check - list should be ordered at first check");
 116
 117         rerandomize(list, size);
 118
 119         // check a reversed sort.
 120         shell_sort(list, size, true);
 121         ASSERT_TRUE(verify_descending(list, size),
 122             "ordering check - list should be ordered at second check");
 123
 124         // clean up now.
 125         delete[] list;
 126 }
 127
 128 void test_sorts::test_heap_sort(int size)
 129 {
 130         FUNCDEF("test_heap_sort");
 131
 132         int *list = populate_random_c_array(size);
 133
 134         // check a normal sort.
 135         heap_sort(list, size);
 136         ASSERT_TRUE(verify_ascending(list, size),
 137             "ordering check - list should be ordered at first check");
 138
 139         rerandomize(list, size);
 140
 141         // check a reversed sort.
 142         heap_sort(list, size, true);
 143         ASSERT_TRUE(verify_descending(list, size),
 144             "ordering check - list should be ordered at second check");
 145
 146         // clean up now.
 147         delete[] list;
 148 }
 149
 150 void test_sorts::test_merge_sort(int size)
 151 {
 152         FUNCDEF("test_merge_sort");
 153
 154         basis::array<int> list = populate_random_array(size);
 155
 156         // check a normal sort.
 157         basis::array<int> ret = merge_sort(list);
 158
 159 //      LOG(astring("list has ") + dump_list(ret.observe(), ret.length()));
 160
 161         ASSERT_TRUE(verify_ascending(ret.access(), size),
 162             "ordering check - list should be ordered at first check");
 163
 164         rerandomize(list.access(), size);
 165
 166         // check a reversed sort.
 167         ret = merge_sort(list, true);
 168         ASSERT_TRUE(verify_descending(ret.access(), size),
 169             "ordering check - list should be ordered at second check");
 170 }
 171
 172 void test_sorts::test_quick_sort(int size)
 173 {
 174         FUNCDEF("test_quick_sort");
 175
 176         int *list = populate_random_c_array(size);
 177
 178         // check a normal sort.
 179         quick_sort(list, size);
 180         ASSERT_TRUE(verify_ascending(list, size),
 181             "ordering check - list should be ordered at first check");
 182
 183 //      LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s()));
 184
 185         rerandomize(list, size);
 186
 187         // check a reversed sort.
 188         quick_sort(list, size, true);
 189         ASSERT_TRUE(verify_descending(list, size),
 190             "ordering check - list should be ordered at second check");
 191
 192         // clean up now.
 193         delete[] list;
 194 }
 195
 196
 197 int test_sorts::execute()
 198 {
 199         FUNCDEF("execute");
 200
 201         int size = MAX_ELEMENTS;
 202
 203         test_shell_sort(size);
 204
 205         test_heap_sort(size);
 206
 207         test_merge_sort(size);
 208
 209         test_quick_sort(size);
 210
 211         return final_report();
 212 }
 213
 214 HOOPLE_MAIN(test_sorts,)
 215