Untitled

/***********************************************************************
2:  Author: Matt Klein
3:
4:  Filename: List.h
5:
6:  Desc: Linked List Template and implementations
7:
8:  Date Created: 11/17/2014
9:  **********************************************************************/
10:
11: #ifndef LinkedList_List_h
12: #define LinkedList_List_h
13:
14: class BADINDEX {};
15: template <class T>
16: class ContainerIfc
17: {
18: public:
19:     virtual ContainerIfc <T>& pushFront(T) =0;
20:     virtual ContainerIfc <T>& pushBack(T)  =0;
21:     virtual ContainerIfc <T>& popFront(T&) throw (BADINDEX) =0;
22:     virtual ContainerIfc <T>& popBack(T&)  throw (BADINDEX) =0;
23:     virtual int  getSize()                                  =0;
24:     virtual bool isEmpty()                                  =0;
25:     virtual T    front()                   throw (BADINDEX) =0;
26:     virtual T    back()                    throw (BADINDEX) =0;
27:     virtual T&   operator [](int)          throw (BADINDEX) =0;
28: };
29: template <class T>
30: class node
31: {
32: public:
33:     T data;
34:     node<T> *next;
35:     node(T e)
36:     {
37:         data = e;
38:         next = NULL;
39:     }
40: };
41: template <class T>
42: class List : public ContainerIfc <T>
43: {
44: public:
45:     List();
46:     ~List();
47:     List(const List&);
48:     List <T>& operator = (List&);
49:     List <T>& pushFront(T);
50:     List <T>& pushBack(T);
51:     List <T>& popFront(T&) throw(BADINDEX);
52:     List <T>& popBack(T&) throw(BADINDEX);
53:     int getSize();
54:     bool isEmpty();
55:     T  front() throw(BADINDEX);
56:     T  back() throw(BADINDEX);
57:     T& operator [](int) throw(BADINDEX);
58: private:
59:     node<T> *head;
60: };
61:
62: /**************************
63:
64:  name:List()
65:  description: class constructor
66:  pre-condition: none
67:  post-condition:  class object created with currentSize = 0
68:  , head points to NULL
69:  return: nothing
70:
71:  *************************/
72: template <class T>
73: List<T>::List()
74: {
75:     head = NULL;
76: }
77:
78:
79:
80:
81:
82: /**************************
83:
84:   name:~List()
85:  description: class destructor
86:  pre-condition: a List object exists
87:  post-condition:  all memory allocated to the List is
88:  deleted
89:  return: nothing
90:
91:
92:  *************************/
93: template <class T>
94: List<T>::~List()
95: {
96:     node<T> *curr = head;
97:     while(head != NULL)
98:     {
99:         curr = head;
100:         head = head->next;
101:         delete curr;
102:     }
103:     curr = NULL;
104: }
105:
106:
107:
108:
109:
110: /**************************
111:
112:   name: List(const List&)
113:  description: class copy constructor
114:  pre-condition: a List object exists
115:  post-condition:  a copy of the class object n is made
116:  return: nothing
117:
118:  *************************/
119: template <class T>
120: List<T>::List( const List& obj )
121: {
122:
123:         head = NULL;
124:         node<T> *temp = obj.head, *ptr = head;
125:         if(temp != NULL)
126:         {
127:         while(temp != NULL)
128:         {
129:             pushBack( temp->data );
130:             temp = temp->next;
131:         }
132:         }
133:     delete temp;
134: }
135:
136:
137:
138:
139:
140: /**************************
141:
142:  name: operator =
143:  description:    overloaded assignment operator
144:  pre-condition:  a object exists
145:  post-condition: the object n is unchanged
146:  and *this is an exact copy of n
147:
148:
149:
150:  *************************/
151: template <class T>
152: List<T>& List<T>::operator = (List& obj)
153: {
154:     if(this != &obj)
155:     {
156:         node<T> *curr = head;
157:         while(head != NULL)
158:         {
159:             curr = head;
160:             head = head->next;
161:             delete curr;
162:         }
163:         curr = NULL;
164:     }
165:     head = NULL;
166:     node<T> *temp = obj.head, *ptr = head;
167:     if(temp != NULL)
168:     {
169:         while(temp != NULL)
170:         {
171:             pushBack( temp->data );
172:             temp = temp->next;
173:         }
174:     }
175:     delete temp;
176:     return *this;
177: }
178:
179:
180:
181:
182:
183: /**************************
184:
185:   name:pushFront(T)
186:  description:    store data element n in a New node
187:  and adds the Node to the front
188:  of a data structure (List)
189:  pre-condition:  a List object exists
190:  post-condition: a new Node has been added
191:  to the front of the List,
192:  increment currentSize
193:  return:           a reference to self
194:
195:  *************************/
196: template <class T>
197: List <T>& List<T>::pushFront(T val)
198: {
199:     node<T> *temp = new node<T>(val);
200:     temp->next = head;
201:     head = temp;
202:
203:     return *this;
204:
205: }
206:
207:
208:
209:
210:
211: /**************************
212:
213:  name:pushBack(T)
214:  description:    store data element n in a New node
215:  and adds the Node to the rear (end)
216:  of a data structure (List)
217:  pre-condition:  a List object exists
218:  post-condition: a new data element has been added
219:  to the rear (end) of the List,
220:  increment currentSize
221:  return:         a reference to self
222:
223:  *************************/
224: template <class T>
225: List <T>& List<T>::pushBack(T val)
226: {
227:     node<T> *temp = new node<T>(val);
228:     if(head == NULL)
229:     {
230:         head = temp;
231:     }
232:     else
233:     {
234:         node<T> *ptr = head;
235:         while(ptr->next != NULL)
236:         {
237:             ptr = ptr->next;
238:         }
239:         ptr->next = temp;
240:     }
241:     return *this;
242: }
243:
244:
245:
246:
247:
248: /**************************
249:
250:  name:popFront(T)
251:  description:    removes a data element from the front
252:  of the data structure (List)
253:  pre-condition:  a object exists
254:  post-condition: a Node has been removed
255:  from the front of the linked List
256:  pointed to by head, decrement currentSize
257:  error: if the List is empty
258:  throw a BADINDEX exception
259:  return:         a reference to self
260:
261:  *************************/
262: template <class T>
263: List <T>& List<T>::popFront(T& val) throw (BADINDEX)
264: {
265:     if(isEmpty())
266:     {
267:         throw BADINDEX();
268:     }
269:     else if(head->next == NULL)
270:     {
271:         val = head->data;
272:         head = NULL;
273:     }
274:     else
275:     {
276:         val = head->data;
277:         node<T> *temp = head;
278:         head = head->next;
279:         temp->next = NULL;
280:         delete temp;
281:     }
282:
283:
284:
285:     return *this;
286:
287: }
288:
289:
290:
291:
292:
293: /**************************
294:
295:  name:popBack(T)
296:  description:    removes a data element from the rear (end)
297:  of the data structure (List)
298:  pre-condition:  a object exists
299:  post-condition: a Node has been removed
300:  from the rear of the linked List
301:  pointed to by head, decrement currentSize
302:  error: if the List is empty
303:  throw a BADINDEX exception
304:  return:         a reference to self
305:
306:  *************************/
307: template <class T>
308: List <T>& List<T>::popBack(T& val) throw (BADINDEX)
309: {
310:     if(isEmpty())
311:     {
312:         throw BADINDEX();
313:     }
314:     else if(head->next == NULL)
315:     {
316:         node<T> *ptr = head;
317:         head = NULL;
318:         val = ptr->data;
319:         delete ptr;
320:     }
321:     else
322:     {
323:         node<T> *temp = head, *prev = head;
324:
325:         while(temp->next != NULL)
326:         {
327:             prev = temp;
328:             temp = temp->next;
329:         }
330:
331:         val = temp->data;
332:         prev->next = NULL;
333:         delete temp;
334:     }
335:
336:     return *this;
337:
338: }
339:
340:
341:
342:
343:
344: /**************************
345:
346:  name:getSize()
347:  description:    returns the number of Nodes
348:  currently in the linked List
349:  pre-condition:  a object exists
350:  post-condition: the linked List is unchanged
351:  return:         an integer value representing
352:  the number of elements in the List
353:
354:
355:  *************************/
356: template <class T>
357: int List<T>::getSize()
358: {
359:     int size = 0;
360:     node<T> *a = head;
361:
362:     while(a != NULL)
363:     {
364:         size++;
365:         a = a->next;
366:     }
367:
368:     return size;
369: }
370:
371:
372:
373:
374:
375: /**************************
376:
377:  name:isEmpty()
378:  description: checks to see if head is empty
379:  pre-condition: head
380:  post-condition:head
381:  return: whether its empty or not
382:
383:  *************************/
384: template <class T>
385: bool List <T>::isEmpty()
386: {
387:     bool check = false;
388:
389:     if(getSize() == 0)
390:     {
391:         check = true;
392:     }
393:
394:     return check;
395: }
396:
397:
398:
399:
400:
401: /**************************
402:
403:  name:front()
404:  description:    returns a copy of the first data item
405:  in the linked List
406:  pre-condition:  a object exists
407:  post-condition: the object is unchanged
408:  error: throw BADINDEX if the
409:  linked List is empty
410:
411:  *************************/
412: template <class T>
413: T List<T>::front() throw (BADINDEX)
414: {
415:     if(isEmpty())
416:     {
417:         throw BADINDEX();
418:     }
419:
420:     return head->data;
421: }
422:
423:
424:
425:
426:
427: /**************************
428:
429:  name:back()
430:  description:    returns a copy of the last data item
431:  in the linked List
432:  pre-condition:  a object exists
433:  post-condition: the object is unchanged
434:  error: throw BADINDEX if the
435:  linked List is empty
436:
437:  *************************/
438: template <class T>
439: T List<T>::back() throw (BADINDEX)
440: {
441:     if(isEmpty())
442:     {
443:         throw BADINDEX();
444:     }
445:
446:     T back = NULL;
447:
448:     if(head->next == NULL)
449:     {
450:         back = head->data;
451:     }
452:     else
453:     {
454:         node<T> *b = head;
455:
456:         for(int i = 0; i < getSize() - 1; i++)
457:         {
458:             b = b->next;
459:         }
460:
461:         back = b->data;
462:     }
463:
464:     return back;
465:
466: }
467:
468:
469:
470:
471:
472: /**************************
473:
474:  name:operator []
475:  description:    returns a reference to data element n
476:  in the linked List
477:  pre-condition:  a object exists
478:  post-condition: the object is unchanged
479:  error: throw BADINDEX if n >= currentSize
480:  or n < 0
481:
482:  *************************/
483: template <class T>
484: T& List<T>::operator [](int val) throw (BADINDEX)
485: {
486:     if(val < 0 || val >= getSize())
487:     {
488:         throw BADINDEX();
489:     }
490:
491:     node<T> *temp = head;
492:
493:     for(int i = 0; i < val; i++)
494:     {
495:         temp = temp->next;
496:     }
497:
498:     return temp->data;
499: }
500:
501:
502: #endif