renamings and add of singly linked list

[feisty_meow.git] / nucleus / library / nodes / singly_linked_list.h

diff --git a/nucleus/library/nodes/singly_linked_list.h b/nucleus/library/nodes/singly_linked_list.h
new file mode 100644 (file)
index 0000000..d58f20f
--- /dev/null
+++ b/nucleus/library/nodes/singly_linked_list.h
@@ -0,0 +1,71 @@
+#ifndef SINGLY_LINKED_LIST_CLASS
+#define SINGLY_LINKED_LIST_CLASS
+
+/*
+*  Name   : singly_linked_list
+*  Author : Chris Koeritz
+**
+* Copyright (c) 1998-$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 "node.h"
+
+namespace nodes {
+
+//class node;  // forward.
+
+//! Implements a singly-linked list structure.
+
+class singly_linked_list : public node
+{
+public:
+  singly_linked_list() : node(1) {}
+
+  //hmmm: clean up all children?
+  ~singly_linked_list() {}
+
+  const int NEXT_NODE = 0;  // symbol for the rest of the list linked here.
+
+  int elements() const;
+    //!< returns the number of items currently in the list, including this node.
+    /*!< this is a costly operation. */
+
+  singly_linked_list *next() { return (singly_linked_list *)get_link(NEXT_NODE); }
+
+  void set_next(singly_linked_list *new_next) { set_link(NEXT_NODE, new_next); }
+
+  //! returns true if this list has a cycle in it.
+  static bool has_cycle(singly_linked_list *check) {
+       singly_linked_list *a = check;
+       singly_linked_list *b = check;
+       while ((a != NULL_POINTER) && (b!= NULL_POINTER) ) {
+               a = a->next();  // move position of a forward once.
+         // move position of b forward twice.
+               b = b->next();
+               if (b != NULL_POINTER) b = b->next();
+
+               if (a == b) {
+                       // argh, our single skipper and double skipper have arrived at the same node.
+                       // the only way that can happen is if there's a cycle in the list.
+                       return true;
+               }
+       }
+       // if we fell out of the list iteration with a null for either pointer,
+       // then there was no cycle in the list.
+       return false;
+  }
+
+private:
+  // not permitted.
+  singly_linked_list(const singly_linked_list &);
+  singly_linked_list &operator =(const singly_linked_list &);
+};
+
+} // namespace.
+
+#endif
+