nucleus/library/nodes/singly_linked_list.h

   1 #ifndef SINGLY_LINKED_LIST_CLASS
   2 #define SINGLY_LINKED_LIST_CLASS
   3
   4 /*
   5 *  Name   : singly_linked_list
   6 *  Author : Chris Koeritz
   7 **
   8 * Copyright (c) 1998-$now By Author.  This program is free software; you can
   9 * redistribute it and/or modify it under the terms of the GNU General Public
  10 * License as published by the Free Software Foundation; either version 2 of
  11 * the License or (at your option) any later version.  This is online at:
  12 *     http://www.fsf.org/copyleft/gpl.html
  13 * Please send any updates to: fred@gruntose.com
  14 */
  15 #include "node.h"
  16
  17 namespace nodes {
  18
  19 //class node;  // forward.
  20
  21 //! Implements a singly-linked list structure.
  22
  23 class singly_linked_list : public node
  24 {
  25 public:
  26   singly_linked_list() : node(1) {}
  27
  28   //hmmm: clean up all children?
  29   ~singly_linked_list() {}
  30
  31   // symbol for the rest of the list linked here.
  32   static const int NEXT_NODE = 0;
  33
  34   int elements() const;
  35     //!< returns the number of items currently in the list, including this node.
  36     /*!< this is a costly operation. */
  37
  38   singly_linked_list *next() { return (singly_linked_list *)get_link(NEXT_NODE); }
  39
  40   void set_next(singly_linked_list *new_next) { set_link(NEXT_NODE, new_next); }
  41
  42   //! returns true if this list has a cycle in it.
  43   static bool has_cycle(singly_linked_list *check) {
  44         singly_linked_list *a = check;
  45         singly_linked_list *b = check;
  46         while ((a != NULL_POINTER) && (b!= NULL_POINTER) ) {
  47                 a = a->next();  // move position of a forward once.
  48           // move position of b forward twice.
  49                 b = b->next();
  50                 if (b != NULL_POINTER) b = b->next();
  51
  52                 if (a == b) {
  53                         // argh, our single skipper and double skipper have arrived at the same node.
  54                         // the only way that can happen is if there's a cycle in the list.
  55                         return true;
  56                 }
  57         }
  58         // if we fell out of the list iteration with a null for either pointer,
  59         // then there was no cycle in the list.
  60         return false;
  61   }
  62
  63 private:
  64   // not permitted.
  65   singly_linked_list(const singly_linked_list &);
  66   singly_linked_list &operator =(const singly_linked_list &);
  67 };
  68
  69 } // namespace.
  70
  71 #endif
  72