t_list.cpp

Go to the documentation of this file.

/*****************************************************************************\
*                                                                             *
*  Name   : test_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 <basis/chaos.h>
#include <basis/guards.h>
#include <basis/istring.h>
#include <nodes/list.h>
#include <nodes/node.h>
#include <loggers/file_logger.h>
#include <opsystem/path_configuration.h>
#include <data_struct/static_memory_gremlin.h>

HOOPLE_STARTUP_CODE;

using namespace nodes;

#define DEBUG_LIST
  // uncomment this line to get more debugging output (into a file called
  // LOGFILE_NAME).

const istring LOGFILE_NAME =  path_configuration::make_logfile_name
    ("t_list.log");
  // the name of our logging file.

const int DEFAULT_ITERATIONS = 5000;
  // the default number of times we run through our phase loop.

typedef basket<int> t_node;
  // the object we store in the list, a templated integer.

#define CASTER(bare_node) static_cast<const t_node *>(bare_node)
  // turns a node pointer into our special t_node.

int main(int formal(argc), char *formal(argv)[])
{
  list the_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.
      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).
      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.
        if (bigger < CASTER(iter.observe())->stored())
          deadly_error("t_list", "invariant check",
              "found 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...
        list::iterator iter = the_list.head();
        // and jump to the element we chose.
        the_list.forward(iter, to_whack);
        if (the_list.index(iter) != to_whack)
          deadly_error("t_list", "forward check",
              "logic error: index of element to zap is incorrect");
        if (iter.is_tail())
          deadly_error("t_list", "forward check",
              "logic error: got to the tail somehow");
        the_list.zap(iter);
      }
    }

  }

#ifdef DEBUG_LIST
  list::iterator iter = the_list.head();
  file_logger log(LOGFILE_NAME);
  log.log("");
  log.log("list contents:");
  int indy = 0;
  while (!iter.is_tail()) {
    int item = CASTER(iter.observe())->stored();
    log.log(istring(istring::SPRINTF, "item #%d: %d", indy, item));
    indy++;
    iter++;
  }
#endif

  guards::alert_message("list:: works for those functions tested.");
  return 0;
}

---