Shamusworld >> Repos - ttedit/blob - src/list.h

   1 //\r
   2 // A generic list class using a circular singly linked list\r
   3 // by James L. Hammons\r
   4 // (C) 2004 Underground Software\r
   5 //\r
   6 // Based upon work I did for CS240 Project 5 at Cal Poly Pomona for Dr. Bruce Hillam.\r
   7 // Hello Dr. Hillam! :-)\r
   8 //\r
   9 // JLH = James L. Hammons <jlhamm@acm.org>\r
  10 //\r
  11 // Who  When        What\r
  12 // ---  ----------  -------------------------------------------------------------\r
  13 // JLH  08/30/1999  Created this file\r
  14 // JLH  05/11/2004  Cleaned up a few things in the implementation\r
  15 //\r
  16 \r
  17 \r
  18 // Some exception constants\r
  19 \r
  20 #define LIST_EMPTY              1\r
  21 #define OUT_OF_RANGE    2\r
  22 \r
  23 template <class T> class List;                                  // Forward declaration...\r
  24 template <class T> class Node\r
  25 {\r
  26         friend class List<T>;\r
  27 \r
  28         public:\r
  29 //              Node(void)                         { next = NULL; }\r
  30                 Node(void): next(NULL) {}\r
  31 //              Node(const T d, Node * ptr = NULL) { data = d;  next = ptr; }\r
  32                 Node(const T d, Node * ptr = NULL): data(d), next(ptr) {}\r
  33 \r
  34         private:\r
  35                 T data;\r
  36                 Node * next;\r
  37 };\r
  38 \r
  39 template <class T> class List      \r
  40 {\r
  41         // This class implements the following exceptions:\r
  42         // LIST_EMPTY is thrown if you attempt to remove an object from an empty list.\r
  43         // OUT_OF_RANGE is thrown if you attempt to Add or Get from a position that\r
  44         // does not exist for the list.\r
  45 \r
  46         private:\r
  47                 Node<T> * last;\r
  48                 int length;\r
  49 \r
  50         public:\r
  51                 List(void);\r
  52                 ~List();\r
  53                 bool operator==(List &l);\r
  54                 void AddAtFront(T data);\r
  55                 void AddAtRear(T data);\r
  56                 void AddAtPosition(int pos, T data);\r
  57                 T GetFront(void);\r
  58                 T GetRear(void);\r
  59                 T GetPosition(int pos);\r
  60                 T PeekFront(void);\r
  61                 T PeekRear(void);\r
  62                 T PeekPosition(int pos);\r
  63                 bool IsEmpty(void);\r
  64                 int Length(void);\r
  65 };\r
  66 \r
  67 //\r
  68 // List class implementation\r
  69 //\r
  70 template <class T> List<T>::List(void)\r
  71 {\r
  72         last = NULL;\r
  73         length = 0;\r
  74 }\r
  75 \r
  76 template <class T> List<T>::~List()\r
  77 {\r
  78         while (length)                                                          // Destroy all nodes that were created...\r
  79         {\r
  80                 Node<T> * tmp = last;\r
  81                 last = last->next;\r
  82                 delete tmp;\r
  83                 length--;\r
  84         }\r
  85 }\r
  86 \r
  87 template <class T> bool List<T>::operator==(List &l)\r
  88 {\r
  89         if (Length() != l.Length())\r
  90                 return false;\r
  91 \r
  92         Node<T> * ptr1 = last->next, * ptr2 = l.last->next;\r
  93 \r
  94         do\r
  95         {\r
  96                 if (ptr1->data != ptr2->data)\r
  97                         return false;\r
  98 \r
  99                 ptr1 = ptr1->next, ptr2 = ptr2->next;\r
 100         }\r
 101         while (ptr1 != last);\r
 102 \r
 103         return true;\r
 104 }\r
 105 \r
 106 template <class T> void List<T>::AddAtFront(T data)\r
 107 {\r
 108         Node<T> * newNode = new Node<T>(data);\r
 109 \r
 110         if (last == NULL)                                                       // i.e., the list is empty...\r
 111                 last = newNode->next = newNode;\r
 112         else\r
 113         {\r
 114                 newNode->next = last->next;\r
 115                 last->next = newNode;\r
 116         }\r
 117 \r
 118         length++;\r
 119 }\r
 120 \r
 121 template <class T> void List<T>::AddAtRear(T data)\r
 122 {\r
 123         Node<T> * newNode = new Node<T>(data);\r
 124 \r
 125         if (last == NULL)                                                       // i.e., the list is empty...\r
 126                 last = newNode->next = newNode;\r
 127         else\r
 128         {\r
 129                 newNode->next = last->next;\r
 130                 last->next = newNode;\r
 131                 last = newNode;\r
 132         }\r
 133 \r
 134         length++;\r
 135 }\r
 136 \r
 137 template <class T> void List<T>::AddAtPosition(int pos, T data)\r
 138 {\r
 139         if ((pos < 1) || (pos > length))\r
 140                 throw OUT_OF_RANGE;\r
 141 \r
 142         if (pos == 1)\r
 143                 AddAtFront(data);                                               // Why reinvent the wheel?\r
 144 \r
 145         if (pos == length)\r
 146                 AddAtRear(data);\r
 147 \r
 148         Node<T> * newNode = new Node<T>(data), * tmp = last;\r
 149 \r
 150         for(int i=1; i!=pos; i++)                                       // Make tmp point to node ahead of add position\r
 151                 tmp = tmp->next;\r
 152 \r
 153         newNode->next = tmp->next;\r
 154         tmp->next = newNode;\r
 155 \r
 156         length++;\r
 157 }\r
 158 \r
 159 template <class T> T List<T>::GetFront(void)\r
 160 {\r
 161         if (IsEmpty())\r
 162                 throw LIST_EMPTY;\r
 163 \r
 164         T retVal = last->next->data;\r
 165         Node<T> * ptr = last->next;\r
 166 \r
 167         if (length == 1)\r
 168                 last = NULL;\r
 169         else\r
 170                 last->next = last->next->next;\r
 171 \r
 172         delete ptr;\r
 173         length--;\r
 174 \r
 175         return retVal;\r
 176 }\r
 177 \r
 178 template <class T> T List<T>::GetRear(void)\r
 179 {\r
 180         if (IsEmpty())\r
 181                 throw LIST_EMPTY;\r
 182 \r
 183         T retVal = last->data;\r
 184         Node<T> * ptr = last;\r
 185 \r
 186         if (length == 1)\r
 187         {\r
 188                 delete last;\r
 189                 last = NULL;\r
 190         }\r
 191         else\r
 192         {\r
 193                 while (ptr->next != last)\r
 194                         ptr = ptr->next;\r
 195 \r
 196                 ptr->next = ptr->next->next;\r
 197                 delete last;\r
 198                 last = ptr;  \r
 199         }\r
 200 \r
 201         length--;\r
 202 \r
 203         return retVal;\r
 204 }\r
 205 \r
 206 template <class T> T List<T>::GetPosition(int pos)\r
 207 {\r
 208         if (IsEmpty())\r
 209                 throw LIST_EMPTY;\r
 210 \r
 211         if ((pos < 1) || (pos > length))\r
 212                 throw OUT_OF_RANGE;\r
 213 \r
 214         if (pos == 1)\r
 215                 return GetFront();                                              // Why reinvent the wheel?\r
 216 \r
 217         if (pos == length)\r
 218                 return GetRear();\r
 219 \r
 220         Node<T> * tmp = last;\r
 221 \r
 222         for(int i=1; i!=pos; i++)                                       // Make tmp point to node ahead of del position\r
 223                 tmp = tmp->next;\r
 224 \r
 225         Node<T> * nodeToDelete = tmp->next;\r
 226                 T retVal = nodeToDelete->data;\r
 227 \r
 228         tmp->next = tmp->next->next;\r
 229         delete nodeToDelete;\r
 230 \r
 231         length--;\r
 232         return retVal;\r
 233 }\r
 234 \r
 235 template <class T> T List<T>::PeekFront(void)\r
 236 {\r
 237         if (IsEmpty())\r
 238                 throw LIST_EMPTY;\r
 239 \r
 240         return last->next->data;\r
 241 }\r
 242 \r
 243 template <class T> T List<T>::PeekRear(void)\r
 244 {\r
 245         if (IsEmpty())\r
 246                 throw LIST_EMPTY;\r
 247 \r
 248         return last->data;\r
 249 }\r
 250 \r
 251 template <class T> T List<T>::PeekPosition(int pos)\r
 252 {\r
 253         if (IsEmpty())\r
 254                 throw LIST_EMPTY;\r
 255 \r
 256         if ((pos < 1) || (pos > length))\r
 257                 throw OUT_OF_RANGE;\r
 258 \r
 259         if (pos == 1)\r
 260                 return PeekFront();                                             // Why reinvent the wheel?\r
 261 \r
 262         if (pos == length)\r
 263                 return PeekRear();\r
 264 \r
 265         Node<T> * tmp = last;\r
 266 \r
 267         for(int i=1; i!=pos; i++)\r
 268                 tmp = tmp->next;\r
 269 \r
 270         return tmp->next->data;\r
 271 }\r
 272 \r
 273 template <class T> inline bool List<T>::IsEmpty(void)\r
 274 {\r
 275         return (bool)(length == 0);\r
 276 }\r
 277 \r
 278 template <class T> inline int List<T>::Length(void)\r
 279 {\r
 280         return length;\r
 281 }\r