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