nucleus/library/tests_nodes/test_doubly_linked_list.cpp

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