2 * Name : test_singly_linked_list
3 * Author : Chris Koeritz
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
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>
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;
33 // uncomment this line to get more debugging output.
35 const int DEFAULT_ITERATIONS = 50;
36 // the default number of times we run through our phase loop.
38 typedef basket<int> t_node;
39 // the object we store in the list, a templated integer.
41 #define CASTER(bare_node) static_cast<const t_node *>(bare_node)
42 // turns a node pointer into our special t_node.
44 #define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print)
48 class test_singly_linked_list : virtual public unit_base, virtual public application_shell
51 test_singly_linked_list() : unit_base() {}
52 DEFINE_CLASS_NAME("test_list");
53 virtual int execute();
56 HOOPLE_MAIN(test_singly_linked_list, );
60 int test_singly_linked_list::execute()
64 // first some discrete tests, before we start looping around.
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();
79 ASSERT_TRUE(singly_linked_list::has_cycle(a), "list should be found to have a cycle")
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();
93 // it's not necessary to set e's next to null; this is the default.
95 ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles")
98 singly_linked_list *the_list = new singly_linked_list();
102 int iterations_left = DEFAULT_ITERATIONS;
103 while (iterations_left-- > 0) {
105 // run through the phases below as many times as we are told.
108 // phase for adding a random number into the list.
109 int to_add = randomizer.inclusive(0, 100000);
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) )
116 // the_list.insert(iter, new t_node(2, to_add));
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();
136 // // if the conditions are favorable, we whack at least one element out of
138 // if (randomizer.inclusive(1, 100) < 20) {
139 // int elem = the_list.elements();
140 // int to_whack = randomizer.inclusive(0, elem - 1);
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);
157 // singly_linked_list::iterator iter = the_list.head();
159 // log(astring("list contents:"));
161 // while (!iter.is_tail()) {
162 // int item = CASTER(iter.observe())->stored();
163 // log(a_sprintf("item #%d: %d", indy, item));
169 return final_report();