-//\r
-// A generic list class using a circular singly linked list\r
-// by James L. Hammons\r
-// (C) 2004 Underground Software\r
-//\r
-// Based upon work I did for CS240 Project 5 at Cal Poly Pomona for Dr. Bruce Hillam.\r
-// Hello Dr. Hillam! :-)\r
-//\r
-// JLH = James L. Hammons <jlhamm@acm.org>\r
-//\r
-// Who When What\r
-// --- ---------- -------------------------------------------------------------\r
-// JLH 08/30/1999 Created this file\r
-// JLH 05/11/2004 Cleaned up a few things in the implementation\r
-//\r
-\r
-\r
-// Some exception constants\r
-\r
-#define LIST_EMPTY 1\r
-#define OUT_OF_RANGE 2\r
-\r
-template <class T> class List; // Forward declaration...\r
-template <class T> class Node\r
-{\r
- friend class List<T>;\r
-\r
- public:\r
-// Node(void) { next = NULL; }\r
- Node(void): next(NULL) {}\r
-// Node(const T d, Node * ptr = NULL) { data = d; next = ptr; }\r
- Node(const T d, Node * ptr = NULL): data(d), next(ptr) {}\r
-\r
- private:\r
- T data;\r
- Node * next;\r
-};\r
-\r
-template <class T> class List \r
-{\r
- // This class implements the following exceptions:\r
- // LIST_EMPTY is thrown if you attempt to remove an object from an empty list.\r
- // OUT_OF_RANGE is thrown if you attempt to Add or Get from a position that\r
- // does not exist for the list.\r
-\r
- private:\r
- Node<T> * last;\r
- int length;\r
-\r
- public:\r
- List(void);\r
- ~List();\r
- bool operator==(List &l);\r
- void AddAtFront(T data);\r
- void AddAtRear(T data);\r
- void AddAtPosition(int pos, T data);\r
- T GetFront(void);\r
- T GetRear(void);\r
- T GetPosition(int pos);\r
- T PeekFront(void);\r
- T PeekRear(void);\r
- T PeekPosition(int pos);\r
- bool IsEmpty(void);\r
- int Length(void);\r
-};\r
-\r
-//\r
-// List class implementation\r
-//\r
-template <class T> List<T>::List(void)\r
-{\r
- last = NULL;\r
- length = 0;\r
-}\r
-\r
-template <class T> List<T>::~List()\r
-{\r
- while (length) // Destroy all nodes that were created...\r
- {\r
- Node<T> * tmp = last;\r
- last = last->next;\r
- delete tmp;\r
- length--;\r
- }\r
-}\r
-\r
-template <class T> bool List<T>::operator==(List &l)\r
-{\r
- if (Length() != l.Length())\r
- return false;\r
-\r
- Node<T> * ptr1 = last->next, * ptr2 = l.last->next;\r
-\r
- do\r
- {\r
- if (ptr1->data != ptr2->data)\r
- return false;\r
-\r
- ptr1 = ptr1->next, ptr2 = ptr2->next;\r
- }\r
- while (ptr1 != last);\r
-\r
- return true;\r
-}\r
-\r
-template <class T> void List<T>::AddAtFront(T data)\r
-{\r
- Node<T> * newNode = new Node<T>(data);\r
-\r
- if (last == NULL) // i.e., the list is empty...\r
- last = newNode->next = newNode;\r
- else\r
- {\r
- newNode->next = last->next;\r
- last->next = newNode;\r
- }\r
-\r
- length++;\r
-}\r
-\r
-template <class T> void List<T>::AddAtRear(T data)\r
-{\r
- Node<T> * newNode = new Node<T>(data);\r
-\r
- if (last == NULL) // i.e., the list is empty...\r
- last = newNode->next = newNode;\r
- else\r
- {\r
- newNode->next = last->next;\r
- last->next = newNode;\r
- last = newNode;\r
- }\r
-\r
- length++;\r
-}\r
-\r
-template <class T> void List<T>::AddAtPosition(int pos, T data)\r
-{\r
- if ((pos < 1) || (pos > length))\r
- throw OUT_OF_RANGE;\r
-\r
- if (pos == 1)\r
- AddAtFront(data); // Why reinvent the wheel?\r
-\r
- if (pos == length)\r
- AddAtRear(data);\r
-\r
- Node<T> * newNode = new Node<T>(data), * tmp = last;\r
-\r
- for(int i=1; i!=pos; i++) // Make tmp point to node ahead of add position\r
- tmp = tmp->next;\r
-\r
- newNode->next = tmp->next;\r
- tmp->next = newNode;\r
-\r
- length++;\r
-}\r
-\r
-template <class T> T List<T>::GetFront(void)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- T retVal = last->next->data;\r
- Node<T> * ptr = last->next;\r
-\r
- if (length == 1)\r
- last = NULL;\r
- else\r
- last->next = last->next->next;\r
-\r
- delete ptr;\r
- length--;\r
-\r
- return retVal;\r
-}\r
-\r
-template <class T> T List<T>::GetRear(void)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- T retVal = last->data;\r
- Node<T> * ptr = last;\r
-\r
- if (length == 1)\r
- {\r
- delete last;\r
- last = NULL;\r
- }\r
- else\r
- {\r
- while (ptr->next != last)\r
- ptr = ptr->next;\r
-\r
- ptr->next = ptr->next->next;\r
- delete last;\r
- last = ptr; \r
- }\r
-\r
- length--;\r
-\r
- return retVal;\r
-}\r
-\r
-template <class T> T List<T>::GetPosition(int pos)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- if ((pos < 1) || (pos > length))\r
- throw OUT_OF_RANGE;\r
-\r
- if (pos == 1)\r
- return GetFront(); // Why reinvent the wheel?\r
-\r
- if (pos == length)\r
- return GetRear();\r
-\r
- Node<T> * tmp = last;\r
-\r
- for(int i=1; i!=pos; i++) // Make tmp point to node ahead of del position\r
- tmp = tmp->next;\r
-\r
- Node<T> * nodeToDelete = tmp->next;\r
- T retVal = nodeToDelete->data;\r
-\r
- tmp->next = tmp->next->next;\r
- delete nodeToDelete;\r
-\r
- length--;\r
- return retVal;\r
-}\r
-\r
-template <class T> T List<T>::PeekFront(void)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- return last->next->data;\r
-}\r
-\r
-template <class T> T List<T>::PeekRear(void)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- return last->data;\r
-}\r
-\r
-template <class T> T List<T>::PeekPosition(int pos)\r
-{\r
- if (IsEmpty())\r
- throw LIST_EMPTY;\r
-\r
- if ((pos < 1) || (pos > length))\r
- throw OUT_OF_RANGE;\r
-\r
- if (pos == 1)\r
- return PeekFront(); // Why reinvent the wheel?\r
-\r
- if (pos == length)\r
- return PeekRear();\r
-\r
- Node<T> * tmp = last;\r
-\r
- for(int i=1; i!=pos; i++)\r
- tmp = tmp->next;\r
-\r
- return tmp->next->data;\r
-}\r
-\r
-template <class T> inline bool List<T>::IsEmpty(void)\r
-{\r
- return (bool)(length == 0);\r
-}\r
-\r
-template <class T> inline int List<T>::Length(void)\r
-{\r
- return length;\r
-}\r
+//
+// A generic list class using a circular singly linked list
+// by James Hammons
+// (C) 2016 Underground Software
+//
+// Based upon work I did for CS240 Project 5 at Cal Poly Pomona for Dr. Bruce
+// Hillam. Hello Dr. Hillam! :-)
+//
+// JLH = James L. Hammons <jlhamm@acm.org>
+//
+// Who When What
+// --- ---------- -----------------------------------------------------------
+// JLH 08/30/1999 Created this file
+// JLH 05/11/2004 Cleaned up a few things in the implementation
+//
+
+
+// Some exception constants
+
+#define LIST_EMPTY 1
+#define OUT_OF_RANGE 2
+
+template <class T> class List; // Forward declaration...
+template <class T> class Node
+{
+ friend class List<T>;
+
+ public:
+ Node(void): next(NULL) {}
+ Node(const T d, Node * ptr = NULL): data(d), next(ptr) {}
+
+ private:
+ T data;
+ Node * next;
+};
+
+template <class T> class List
+{
+ // This class implements the following exceptions:
+ // LIST_EMPTY is thrown if you attempt to remove an object from an empty list.
+ // OUT_OF_RANGE is thrown if you attempt to Add or Get from a position that
+ // does not exist for the list.
+
+ private:
+ Node<T> * last;
+ int length;
+
+ public:
+ List(void);
+ ~List();
+ bool operator==(List &l);
+ void AddAtFront(T data);
+ void AddAtRear(T data);
+ void AddAtPosition(int pos, T data);
+ T GetFront(void);
+ T GetRear(void);
+ T GetPosition(int pos);
+ T PeekFront(void);
+ T PeekRear(void);
+ T PeekPosition(int pos);
+ bool IsEmpty(void);
+ int Length(void);
+};
+
+//
+// List class implementation
+//
+template <class T> List<T>::List(void)
+{
+ last = NULL;
+ length = 0;
+}
+
+template <class T> List<T>::~List()
+{
+ while (length) // Destroy all nodes that were created...
+ {
+ Node<T> * tmp = last;
+ last = last->next;
+ delete tmp;
+ length--;
+ }
+}
+
+template <class T> bool List<T>::operator==(List &l)
+{
+ if (Length() != l.Length())
+ return false;
+
+ Node<T> * ptr1 = last->next, * ptr2 = l.last->next;
+
+ do
+ {
+ if (ptr1->data != ptr2->data)
+ return false;
+
+ ptr1 = ptr1->next, ptr2 = ptr2->next;
+ }
+ while (ptr1 != last);
+
+ return true;
+}
+
+template <class T> void List<T>::AddAtFront(T data)
+{
+ Node<T> * newNode = new Node<T>(data);
+
+ if (last == NULL) // i.e., the list is empty...
+ last = newNode->next = newNode;
+ else
+ {
+ newNode->next = last->next;
+ last->next = newNode;
+ }
+
+ length++;
+}
+
+template <class T> void List<T>::AddAtRear(T data)
+{
+ Node<T> * newNode = new Node<T>(data);
+
+ if (last == NULL) // i.e., the list is empty...
+ last = newNode->next = newNode;
+ else
+ {
+ newNode->next = last->next;
+ last->next = newNode;
+ last = newNode;
+ }
+
+ length++;
+}
+
+template <class T> void List<T>::AddAtPosition(int pos, T data)
+{
+ if ((pos < 1) || (pos > length))
+ throw OUT_OF_RANGE;
+
+ if (pos == 1)
+ AddAtFront(data); // Why reinvent the wheel?
+
+ if (pos == length)
+ AddAtRear(data);
+
+ Node<T> * newNode = new Node<T>(data), * tmp = last;
+
+ for(int i=1; i!=pos; i++) // Make tmp point to node ahead of add position
+ tmp = tmp->next;
+
+ newNode->next = tmp->next;
+ tmp->next = newNode;
+
+ length++;
+}
+
+template <class T> T List<T>::GetFront(void)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ T retVal = last->next->data;
+ Node<T> * ptr = last->next;
+
+ if (length == 1)
+ last = NULL;
+ else
+ last->next = last->next->next;
+
+ delete ptr;
+ length--;
+
+ return retVal;
+}
+
+template <class T> T List<T>::GetRear(void)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ T retVal = last->data;
+ Node<T> * ptr = last;
+
+ if (length == 1)
+ {
+ delete last;
+ last = NULL;
+ }
+ else
+ {
+ while (ptr->next != last)
+ ptr = ptr->next;
+
+ ptr->next = ptr->next->next;
+ delete last;
+ last = ptr;
+ }
+
+ length--;
+
+ return retVal;
+}
+
+template <class T> T List<T>::GetPosition(int pos)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ if ((pos < 1) || (pos > length))
+ throw OUT_OF_RANGE;
+
+ if (pos == 1)
+ return GetFront(); // Why reinvent the wheel?
+
+ if (pos == length)
+ return GetRear();
+
+ Node<T> * tmp = last;
+
+ for(int i=1; i!=pos; i++) // Make tmp point to node ahead of del position
+ tmp = tmp->next;
+
+ Node<T> * nodeToDelete = tmp->next;
+ T retVal = nodeToDelete->data;
+
+ tmp->next = tmp->next->next;
+ delete nodeToDelete;
+
+ length--;
+ return retVal;
+}
+
+template <class T> T List<T>::PeekFront(void)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ return last->next->data;
+}
+
+template <class T> T List<T>::PeekRear(void)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ return last->data;
+}
+
+template <class T> T List<T>::PeekPosition(int pos)
+{
+ if (IsEmpty())
+ throw LIST_EMPTY;
+
+ if ((pos < 1) || (pos > length))
+ throw OUT_OF_RANGE;
+
+ if (pos == 1)
+ return PeekFront(); // Why reinvent the wheel?
+
+ if (pos == length)
+ return PeekRear();
+
+ Node<T> * tmp = last;
+
+ for(int i=1; i!=pos; i++)
+ tmp = tmp->next;
+
+ return tmp->next->data;
+}
+
+template <class T> inline bool List<T>::IsEmpty(void)
+{
+ return (bool)(length == 0);
+}
+
+template <class T> inline int List<T>::Length(void)
+{
+ return length;
+}
projects / ttedit / blobdiff