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

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