2 * Name : test_doubly_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/node.h>
20 #include <structures/static_memory_gremlin.h>
21 #include <unit_test/unit_base.h>
22 #include <nodes/doubly_linked_list.h>
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;
34 // uncomment this line to get more debugging output.
36 const int DEFAULT_ITERATIONS = 50;
37 // the default number of times we run through our phase loop.
39 typedef basket<int> t_node;
40 // the object we store in the list, a templated integer.
42 #define CASTER(bare_node) static_cast<const t_node *>(bare_node)
43 // turns a node pointer into our special t_node.
45 #define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print)
49 class test_doubly_linked_list : virtual public unit_base, virtual public application_shell
52 test_doubly_linked_list() : unit_base() {}
53 DEFINE_CLASS_NAME("test_list");
54 virtual int execute();
57 HOOPLE_MAIN(test_doubly_linked_list, );
61 int test_doubly_linked_list::execute()
65 doubly_linked_list the_list;
68 int iterations_left = DEFAULT_ITERATIONS;
69 while (iterations_left-- > 0) {
71 // run through the phases below as many times as we are told.
74 // phase for adding a random number into the list.
75 int to_add = randomizer.inclusive(0, 100000);
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) )
82 the_list.insert(iter, new t_node(2, to_add));
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();
102 // if the conditions are favorable, we whack at least one element out of
104 if (randomizer.inclusive(1, 100) < 20) {
105 int elem = the_list.elements();
106 int to_whack = randomizer.inclusive(0, elem - 1);
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");
123 doubly_linked_list::iterator iter = the_list.head();
125 log(astring("list contents:"));
127 while (!iter.is_tail()) {
128 int item = CASTER(iter.observe())->stored();
129 log(a_sprintf("item #%d: %d", indy, item));
135 return final_report();