List.h

00001 /*
00002 File: List.h
00003 
00004 Function: Provides linked list primitives.
00005 
00006 Author(s): Andrew Willmott
00007 
00008 Copyright: (c) 1995-2000, Andrew Willmott
00009 */
00010 
00011 #ifndef __List__
00012 #define __List__
00013 
00014 #include "cl/Basics.h"
00015 
00016 
00017 // --- Simple Linked List ---------------------------------------------------
00018 
00019 
00020 // A node in the list.
00021 
00022  class Node
00023 {
00024 public:
00025  Node *next; // Next item in the list
00026 
00027  Node() : next(0) {};
00028 
00029  Void InsertAfter(Node *node) { node->next = next; next = node;};
00030 
00031 Void FreeAfter();
00032 
00033 virtual Node *Clone();
00034 Node *CloneList();
00035 };
00036 
00037 
00038 // A list : essentially a (Node *) with associated methods. Imitates 
00039 // Lisp/Prolog lists, in that it has head & tail methods. Has pointer
00040 // semantics: you must call Clone() to copy it, and Free() to delete it. 
00041 
00042  class List
00043 {
00044 public:
00045  Node *first; // Pointer to the first node in the list.
00046 
00047  List() : first(0) {};
00048 
00049  Bool IsEmpty() { return first == 0; };
00050  Node &Head() { return *first; };
00051  List &Tail() { return (List &) first->next; };
00052 
00053  Void Prepend(Node *node)
00054 { node->next = first; first = node; };
00055 Void Prepend(List list);
00056 Void Append(Node *node);
00057 Void Append(List list);
00058 
00059 Void Free();
00060 List Clone();
00061 
00062  Void DeleteFirst()
00063 { Node *t = first; first = first->next; delete t; }; 
00064  Node *DisconnectFirst()
00065 { Node *t = first; first = first->next; return(t); }; 
00066 
00067 Int NumItems();
00068 };
00069 
00070 template <class T> 
00071  class TypedList : public List
00072 {
00073 public:
00074  T &Head() { return (T &) *first; };
00075  TypedList<T> &Tail() { return (TypedList<T> &) first->next; };
00076 };
00077 
00078 template <class T> ostream &operator << (ostream &s, TypedList<T> list);
00079 
00080 // Associated iterator. 
00081 
00082  template <class T> class Iter
00083 {
00084 public:
00085  List *cursor;
00086 
00087  Void Begin(List &list)
00088 { cursor = &list; };
00089  Void Inc() 
00090 { Assert(!cursor->IsEmpty(), "Moved past end of list");
00091 cursor = (List *) cursor->first; };
00092 
00093  Bool AtEnd()
00094 { return cursor->first == 0; };
00095  T &Data()
00096 { return (T &) cursor->Head(); };
00097 
00098  Void Delete()
00099 { cursor->DeleteFirst();};
00100  Void InsertBefore(Node *node)
00101 { cursor->Prepend(node); cursor = (List *) cursor->first;};
00102  Void InsertAfter(Node *node)
00103 { cursor->Tail().Prepend(node);};
00104 };
00105 
00106 
00107 // --- Doubly-linked list -----------------------------------------------------
00108 
00109 
00110  class DblNode
00111 {
00112 public:
00113  DblNode *prev; // Previous item in the list
00114  DblNode *next; // Next item in the list
00115 
00116  DblNode() : prev(0), next(0) {};
00117 
00118  Void InsertAfter(DblNode *node)
00119 { 
00120 node->next = next; 
00121 node->prev = this; 
00122 if (next) next->prev = node; 
00123 next = node; 
00124 };
00125  Void InsertBefore(DblNode *node)
00126 { 
00127 node->next = this; 
00128 node->prev = prev;
00129 if (prev) prev->next = node; 
00130 prev = node;
00131 };
00132  Void Delete()
00133 { delete Disconnect(); };
00134  DblNode *Disconnect()
00135 { 
00136 if (prev) prev->next = next; 
00137 if (next) next->prev = prev; 
00138 return(this);
00139 };
00140 
00141  Bool AtStart() { return(prev == 0); };
00142  Bool AtEnd() { return(next == 0); };
00143 
00144 Void FreeAfter();
00145 Void FreeBefore();
00146  Void FreeList() { FreeAfter(); FreeBefore(); delete this; }
00147 
00148  virtual DblNode *Clone() { return new DblNode(SELF); };
00149 
00150 DblNode *CloneAfter();
00151 DblNode *CloneBefore();
00152 DblNode *CloneList();
00153 };
00154 
00155 // Associated iterator
00156 
00157  template <class T> class DblIter
00158 {
00159 public:
00160  DblNode *cursor;
00161 
00162  Void Begin(DblNode *list) { cursor = list; };
00163  Void Inc()
00164 { Assert(!cursor->AtEnd(), "Moved past end of list");
00165 cursor = cursor->next; };
00166  Void Dec()
00167 { Assert(!cursor->AtStart(), "Moved past end of list");
00168 cursor = cursor->prev; };
00169 
00170  Bool AtEnd() { return cursor == 0; };
00171 
00172  T &Data() { return (T &) *cursor; };
00173 
00174  Void Delete()
00175 { DblNode *t = cursor; cursor->Delete(); cursor = t;};
00176  Void InsertBefore(DblNode *node)
00177 { cursor->InsertBefore(node); };
00178  Void InsertAfter(DblNode *node)
00179 { cursor->InsertAfter(node); };
00180 };
00181 
00182 
00183 // --- Templated functions ----------------------------------------------------
00184 
00185 template <class T> 
00186  ostream &operator << (ostream &s, TypedList<T> list)
00187 {
00188 s << "(";
00189 
00190 if (!list.IsEmpty())
00191 {
00192 s << list.Head();
00193 list = list.Tail();
00194 
00195 while (!list.IsEmpty())
00196 {
00197 s << " " << list.Head();
00198 list = list.Tail();
00199 }
00200 }
00201 
00202 s << ")";
00203 return(s);
00204 };
00205 
00206 
00207 #endif