X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Ftests_nodes%2Ftest_singly_linked_list.cpp;fp=nucleus%2Flibrary%2Ftests_nodes%2Ftest_singly_linked_list.cpp;h=e5e88c5884a5ccd0406d379a31ee85805ecd4a43;hb=1b2df1d72f942ac68040bd5d44879729e7306bbb;hp=0000000000000000000000000000000000000000;hpb=244e0eeaf916718d7bcd7beba44f9c0de29c504d;p=feisty_meow.git diff --git a/nucleus/library/tests_nodes/test_singly_linked_list.cpp b/nucleus/library/tests_nodes/test_singly_linked_list.cpp new file mode 100644 index 00000000..e5e88c58 --- /dev/null +++ b/nucleus/library/tests_nodes/test_singly_linked_list.cpp @@ -0,0 +1,172 @@ +/* +* Name : test_singly_linked_list +* Author : Chris Koeritz +** +* Copyright (c) 1993-$now By Author. This program is free software; you can +* redistribute it and/or modify it under the terms of the GNU General Public +* License as published by the Free Software Foundation; either version 2 of +* the License or (at your option) any later version. This is online at: +* http://www.fsf.org/copyleft/gpl.html +* Please send any updates to: fred@gruntose.com +*/ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace application; +using namespace basis; +using namespace configuration; +using namespace loggers; +using namespace mathematics; +using namespace nodes; +using namespace structures; +using namespace unit_test; + +//#define DEBUG_LIST + // uncomment this line to get more debugging output. + +const int DEFAULT_ITERATIONS = 50; + // the default number of times we run through our phase loop. + +typedef basket t_node; + // the object we store in the list, a templated integer. + +#define CASTER(bare_node) static_cast(bare_node) + // turns a node pointer into our special t_node. + +#define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print) + +////////////// + +class test_singly_linked_list : virtual public unit_base, virtual public application_shell +{ +public: + test_singly_linked_list() : unit_base() {} + DEFINE_CLASS_NAME("test_list"); + virtual int execute(); +}; + +HOOPLE_MAIN(test_singly_linked_list, ); + +////////////// + +int test_singly_linked_list::execute() +{ + FUNCDEF("execute"); + + // first some discrete tests, before we start looping around. + + { + // test that the cycle detector is working for finding a cycle. + singly_linked_list *a = new singly_linked_list(); + singly_linked_list *b = new singly_linked_list(); + singly_linked_list *c = new singly_linked_list(); + singly_linked_list *d = new singly_linked_list(); + singly_linked_list *e = new singly_linked_list(); + a->set_next(b); + b->set_next(c); + c->set_next(d); + d->set_next(e); + e->set_next(c); + + ASSERT_TRUE(singly_linked_list::has_cycle(a), "list should be found to have a cycle") + } + + { + // test that the cycle detector is working to not find a cycle if one doesn't exist. + singly_linked_list *a = new singly_linked_list(); + singly_linked_list *b = new singly_linked_list(); + singly_linked_list *c = new singly_linked_list(); + singly_linked_list *d = new singly_linked_list(); + singly_linked_list *e = new singly_linked_list(); + a->set_next(b); + b->set_next(c); + c->set_next(d); + d->set_next(e); +// e->set_next(NULL_POINTER); // not actually necessary, right? + + ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles") + } + + singly_linked_list *the_list = new singly_linked_list(); + + chaos randomizer; + + int iterations_left = DEFAULT_ITERATIONS; + while (iterations_left-- > 0) { + + // run through the phases below as many times as we are told. + + { + // phase for adding a random number into the list. + int to_add = randomizer.inclusive(0, 100000); + +// // seek the correct insertion place to keep the list ordered. +// singly_linked_list::iterator iter = the_list.head(); +// while (!iter.is_tail() && iter.observe() +// && (CASTER(iter.observe())->stored() <= to_add) ) +// iter++; +// the_list.insert(iter, new t_node(2, to_add)); + } + + { +// // test the list invariant (which is that all elements should be sorted +// // in non-decreasing order). +// singly_linked_list::iterator iter = the_list.tail(); +// // initialize our comparator. +// int bigger = CASTER(iter.observe())->stored(); +// // loop backwards until we hit the head. +// while (!iter.is_head()) { +// // check that the last value is not less than the current value. +// ASSERT_FALSE(bigger < CASTER(iter.observe())->stored(), +// "invariant check should not find a mal-ordering in the list"); +// bigger = CASTER(iter.observe())->stored(); +// iter--; +// } + } + + { +// // if the conditions are favorable, we whack at least one element out of +// // the list. +// if (randomizer.inclusive(1, 100) < 20) { +// int elem = the_list.elements(); +// int to_whack = randomizer.inclusive(0, elem - 1); +// +// // start at the head of the list... +// singly_linked_list::iterator iter = the_list.head(); +// // and jump to the element we chose. +// the_list.forward(iter, to_whack); +// ASSERT_EQUAL(the_list.index(iter), to_whack, +// "forward should not see logic error where index of element to zap is incorrect"); +// ASSERT_FALSE(iter.is_tail(), +// "forward should not see logic error where we get to the tail somehow"); +// the_list.zap(iter); +// } + } + + } + +//#ifdef DEBUG_LIST +// singly_linked_list::iterator iter = the_list.head(); +// log(astring("")); +// log(astring("list contents:")); +// int indy = 0; +// while (!iter.is_tail()) { +// int item = CASTER(iter.observe())->stored(); +// log(a_sprintf("item #%d: %d", indy, item)); +// indy++; +// iter++; +// } +//#endif + + return final_report(); +} + +