]> Shamusworld >> Repos - ttedit/blob - src/list.h
Move main repo to trunk.
[ttedit] / 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