core/library/tests_nodes/test_list.cpp

   1 /*****************************************************************************\
   2 *                                                                             *
   3 *  Name   : test_list                                                         *
   4 *  Author : Chris Koeritz                                                     *
   5 *                                                                             *
   6 *******************************************************************************
   7 * Copyright (c) 1993-$now By Author.  This program is free software; you can  *
   8 * redistribute it and/or modify it under the terms of the GNU General Public  *
   9 * License as published by the Free Software Foundation; either version 2 of   *
  10 * the License or (at your option) any later version.  This is online at:      *
  11 *     http://www.fsf.org/copyleft/gpl.html                                    *
  12 * Please send any updates to: fred@gruntose.com                               *
  13 \*****************************************************************************/
  14
  15 #include <application/hoople_main.h>
  16 #include <basis/astring.h>
  17 #include <basis/guards.h>
  18 #include <configuration/application_configuration.h>
  19 #include <loggers/program_wide_logger.h>
  20 #include <mathematics/chaos.h>
  21 #include <nodes/list.h>
  22 #include <nodes/node.h>
  23 #include <structures/static_memory_gremlin.h>
  24 #include <unit_test/unit_base.h>
  25
  26 using namespace application;
  27 using namespace basis;
  28 using namespace configuration;
  29 using namespace loggers;
  30 using namespace mathematics;
  31 using namespace nodes;
  32 using namespace structures;
  33 using namespace unit_test;
  34
  35 //#define DEBUG_LIST
  36   // uncomment this line to get more debugging output.
  37
  38 const int DEFAULT_ITERATIONS = 50;
  39   // the default number of times we run through our phase loop.
  40
  41 typedef basket<int> t_node;
  42   // the object we store in the list, a templated integer.
  43
  44 #define CASTER(bare_node) static_cast<const t_node *>(bare_node)
  45   // turns a node pointer into our special t_node.
  46
  47 #define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print)
  48
  49 //////////////
  50
  51 class test_list : virtual public unit_base, virtual public application_shell
  52 {
  53 public:
  54   test_list() : unit_base() {}
  55   DEFINE_CLASS_NAME("test_list");
  56   virtual int execute();
  57 };
  58
  59 HOOPLE_MAIN(test_list, );
  60
  61 //////////////
  62
  63 int test_list::execute()
  64 {
  65   FUNCDEF("execute");
  66
  67   list the_list;
  68   chaos randomizer;
  69
  70   int iterations_left = DEFAULT_ITERATIONS;
  71   while (iterations_left-- > 0) {
  72
  73     // run through the phases below as many times as we are told.
  74
  75     {
  76       // phase for adding a random number into the list.
  77       int to_add = randomizer.inclusive(0, 100000);
  78
  79       // seek the correct insertion place to keep the list ordered.
  80       list::iterator iter = the_list.head();
  81       while (!iter.is_tail() && iter.observe()
  82           && (CASTER(iter.observe())->stored() <= to_add) )
  83         iter++;
  84       the_list.insert(iter, new t_node(2, to_add));
  85     }
  86
  87     {
  88       // test the list invariant (which is that all elements should be sorted
  89       // in non-decreasing order).
  90       list::iterator iter = the_list.tail();
  91       // initialize our comparator.
  92       int bigger = CASTER(iter.observe())->stored();
  93       // loop backwards until we hit the head.
  94       while (!iter.is_head()) {
  95         // check that the last value is not less than the current value.
  96         ASSERT_FALSE(bigger < CASTER(iter.observe())->stored(),
  97             "invariant check should not find a mal-ordering in the list");
  98         bigger = CASTER(iter.observe())->stored();
  99         iter--;
 100       }
 101     }
 102
 103     {
 104       // if the conditions are favorable, we whack at least one element out of
 105       // the list.
 106       if (randomizer.inclusive(1, 100) < 20) {
 107         int elem = the_list.elements();
 108         int to_whack = randomizer.inclusive(0, elem - 1);
 109
 110         // start at the head of the list...
 111         list::iterator iter = the_list.head();
 112         // and jump to the element we chose.
 113         the_list.forward(iter, to_whack);
 114         ASSERT_EQUAL(the_list.index(iter), to_whack,
 115             "forward should not see logic error where index of element to zap is incorrect");
 116         ASSERT_FALSE(iter.is_tail(),
 117             "forward should not see logic error where we get to the tail somehow");
 118         the_list.zap(iter);
 119       }
 120     }
 121
 122   }
 123
 124 #ifdef DEBUG_LIST
 125   list::iterator iter = the_list.head();
 126   log(astring(""));
 127   log(astring("list contents:"));
 128   int indy = 0;
 129   while (!iter.is_tail()) {
 130     int item = CASTER(iter.observe())->stored();
 131     log(a_sprintf("item #%d: %d", indy, item));
 132     indy++;
 133     iter++;
 134   }
 135 #endif
 136
 137   return final_report();
 138 }
 139
 140