nucleus/library/tests_nodes/test_singly_linked_list.cpp

   1 /*
   2 *  Name   : test_singly_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/singly_linked_list.h>
  20 #include <structures/static_memory_gremlin.h>
  21 #include <unit_test/unit_base.h>
  22
  23 using namespace application;
  24 using namespace basis;
  25 using namespace configuration;
  26 using namespace loggers;
  27 using namespace mathematics;
  28 using namespace nodes;
  29 using namespace structures;
  30 using namespace unit_test;
  31
  32 //#define DEBUG_LIST
  33   // uncomment this line to get more debugging output.
  34
  35 const int DEFAULT_ITERATIONS = 50;
  36   // the default number of times we run through our phase loop.
  37
  38 typedef basket<int> t_node;
  39   // the object we store in the list, a templated integer.
  40
  41 #define CASTER(bare_node) static_cast<const t_node *>(bare_node)
  42   // turns a node pointer into our special t_node.
  43
  44 #define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print)
  45
  46 //////////////
  47
  48 class test_singly_linked_list : virtual public unit_base, virtual public application_shell
  49 {
  50 public:
  51   test_singly_linked_list() : unit_base() {}
  52   DEFINE_CLASS_NAME("test_list");
  53   virtual int execute();
  54 };
  55
  56 HOOPLE_MAIN(test_singly_linked_list, );
  57
  58 //////////////
  59
  60 int test_singly_linked_list::execute()
  61 {
  62   FUNCDEF("execute");
  63
  64   // first some discrete tests, before we start looping around.
  65
  66   {
  67         // test that the cycle detector is working for finding a cycle.
  68         singly_linked_list *a = new singly_linked_list();
  69         singly_linked_list *b = new singly_linked_list();
  70         singly_linked_list *c = new singly_linked_list();
  71         singly_linked_list *d = new singly_linked_list();
  72         singly_linked_list *e = new singly_linked_list();
  73         a->set_next(b);
  74         b->set_next(c);
  75         c->set_next(d);
  76         d->set_next(e);
  77         e->set_next(c);
  78
  79         ASSERT_TRUE(singly_linked_list::has_cycle(a), "list should be found to have a cycle")
  80   }
  81
  82   {
  83         // test that the cycle detector is working to not find a cycle if one doesn't exist.
  84         singly_linked_list *a = new singly_linked_list();
  85         singly_linked_list *b = new singly_linked_list();
  86         singly_linked_list *c = new singly_linked_list();
  87         singly_linked_list *d = new singly_linked_list();
  88         singly_linked_list *e = new singly_linked_list();
  89         a->set_next(b);
  90         b->set_next(c);
  91         c->set_next(d);
  92         d->set_next(e);
  93         // it's not necessary to set e's next to null; this is the default.
  94
  95         ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles")
  96   }
  97
  98   singly_linked_list *the_list = new singly_linked_list();
  99
 100   chaos randomizer;
 101
 102   int iterations_left = DEFAULT_ITERATIONS;
 103   while (iterations_left-- > 0) {
 104
 105     // run through the phases below as many times as we are told.
 106
 107     {
 108       // phase for adding a random number into the list.
 109       int to_add = randomizer.inclusive(0, 100000);
 110
 111 //      // seek the correct insertion place to keep the list ordered.
 112 //      singly_linked_list::iterator iter = the_list.head();
 113 //      while (!iter.is_tail() && iter.observe()
 114 //          && (CASTER(iter.observe())->stored() <= to_add) )
 115 //        iter++;
 116 //      the_list.insert(iter, new t_node(2, to_add));
 117     }
 118
 119     {
 120 //      // test the list invariant (which is that all elements should be sorted
 121 //      // in non-decreasing order).
 122 //      singly_linked_list::iterator iter = the_list.tail();
 123 //      // initialize our comparator.
 124 //      int bigger = CASTER(iter.observe())->stored();
 125 //      // loop backwards until we hit the head.
 126 //      while (!iter.is_head()) {
 127 //        // check that the last value is not less than the current value.
 128 //        ASSERT_FALSE(bigger < CASTER(iter.observe())->stored(),
 129 //            "invariant check should not find a mal-ordering in the list");
 130 //        bigger = CASTER(iter.observe())->stored();
 131 //        iter--;
 132 //      }
 133     }
 134
 135     {
 136 //      // if the conditions are favorable, we whack at least one element out of
 137 //      // the list.
 138 //      if (randomizer.inclusive(1, 100) < 20) {
 139 //        int elem = the_list.elements();
 140 //        int to_whack = randomizer.inclusive(0, elem - 1);
 141 //
 142 //        // start at the head of the list...
 143 //        singly_linked_list::iterator iter = the_list.head();
 144 //        // and jump to the element we chose.
 145 //        the_list.forward(iter, to_whack);
 146 //        ASSERT_EQUAL(the_list.index(iter), to_whack,
 147 //            "forward should not see logic error where index of element to zap is incorrect");
 148 //        ASSERT_FALSE(iter.is_tail(),
 149 //            "forward should not see logic error where we get to the tail somehow");
 150 //        the_list.zap(iter);
 151 //      }
 152     }
 153
 154   }
 155
 156 //#ifdef DEBUG_LIST
 157 //  singly_linked_list::iterator iter = the_list.head();
 158 //  log(astring(""));
 159 //  log(astring("list contents:"));
 160 //  int indy = 0;
 161 //  while (!iter.is_tail()) {
 162 //    int item = CASTER(iter.observe())->stored();
 163 //    log(a_sprintf("item #%d: %d", indy, item));
 164 //    indy++;
 165 //    iter++;
 166 //  }
 167 //#endif
 168
 169   return final_report();
 170 }
 171
 172