linked_list.h
Go to the documentation of this file.
1 // *****************************************************************************
2 //
3 // Copyright (c) 2014, Southwest Research Institute® (SwRI®)
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of Southwest Research Institute® (SwRI®) nor the
14 // names of its contributors may be used to endorse or promote products
15 // derived from this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
21 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28 // *****************************************************************************
29 
30 #ifndef MARTI_DATA_STRUCTURES_LINKED_LIST_H_
31 #define MARTI_DATA_STRUCTURES_LINKED_LIST_H_
32 
33 #ifndef NULL
34 #define NULL 0
35 #endif
36 
38 {
39  template<class T>
40  class LinkedList
41  {
42  public:
43  // Default constructor
45  {
46  NumElements = 0;
47  }
48 
49  // Copy Constructor
51  {
52  NumElements = 0;
53  this->CopyList(src, *this);
54  }
55 
57  {
58  ctr *tptr;
59  while (this->size() > 0)
60  {
61  tptr = HEAD;
62  HEAD = HEAD->next;
63  this->remove(tptr);
64  }
65  }
66 
67  // Copy Assignment
69  {
70  this->CopyList(src, *this);
71  return *this;
72  }
73 
74  void initialize()
75  {
76  ctr *tptr;
77  while (this->size() > 0)
78  {
79  tptr = HEAD;
80  HEAD = HEAD->next;
81  this->remove(tptr);
82  }
83  }
84 
85  int size()
86  {
87  return NumElements;
88  }
89 
90  void add(T &newElem)
91  {
92  if (this->size() == 0)
93  {
94  this->CreateNewLinkedList(&newElem);
95  }
96  else
97  {
98  this->addToTail(&newElem);
99  }
100  }
101 
102  void addCopy(const T &newElem)
103  {
104  T* copyElem = new T;
105  *copyElem = newElem;
106  this->add(*copyElem);
107  }
108 
109  // Adds a new element at location i, and moves previous i (and all above) to
110  // i+1 (and so on). If i >= Size the new element will be added to the end
111  // of the list
112  void insertAt(T &newElem, int i)
113  {
114  this->addInPosition(&newElem, i);
115  }
116 
117  void insertCopyAt(const T &newElem, int i)
118  {
119  T* copyElem = new T;
120  *copyElem = newElem;
121  this->addInPosition(copyElem, i);
122  }
123 
124  void remove(int i)
125  {
126  ctr *tptr;
127  tptr = this->get(i);
128  if (tptr) // if tptr!=NULL
129  {
130  this->remove(tptr);
131  }
132  }
133 
134  T* ReturnElement(int i)
135  {
136  // returns NULL if index out of bounds
137  ctr* temp = this->get(i);
138  if (NULL == temp)
139  {
140  return NULL;
141  }
142  else
143  {
144  return (temp->Data);
145  }
146  }
147 
148  // Crops list by removing all elements from i to the end (i inclusive)
149  void CropList(int i)
150  {
151  while (this->ReturnElement(i))
152  {
153  this->remove(i);
154  }
155  }
156 
157  private:
158  struct ctr
159  {
160  T *Data;
163  };
168 
169  // void UpdatePointers()
170  void CreateNewLinkedList(T *firstElement)
171  {
172  temp = this->alloc_elem(firstElement);
173  HEAD = temp;
174  TAIL = temp;
175  temp->next = NULL;
176  temp->prev = NULL;
177  NumElements++;
178  }
179 
180  void addToTail(T *newElem)
181  {
182  temp = this->alloc_elem(newElem);
183  temp->prev = TAIL;
184  TAIL = temp;
185  temp->next = NULL;
186  temp->prev->next = temp;
187  NumElements++;
188  }
189 
190  void addInPosition(T *elem, int i)
191  {
192  ctr *itemToMove = this->get(i);
193  if (itemToMove == NULL)
194  {
195  this->add(*elem); // KCK modified
196  }
197  else
198  {
199  temp = this->alloc_elem(elem);
200  temp->next = itemToMove;
201  temp->prev = itemToMove->prev;
202  if (temp->prev != NULL)
203  {
204  itemToMove->prev->next = temp;
205  }
206  else
207  {
208  this->HEAD = temp;
209  }
210  itemToMove->prev = temp;
211  NumElements++;
212  }
213  }
214 
215  ctr* alloc_elem(T *elem)
216  {
217  ctr *tptr = new ctr;
218  tptr->Data = elem;
219  return tptr;
220  }
221 
222  void release_elem(ctr *elem)
223  {
224  delete elem->Data;
225  delete elem;
226  }
227 
228  ctr* get(int i)
229  {
230  if (i >= this->size() || i < 0)
231  {
232  return NULL;
233  }
234  ctr* temp = HEAD;
235  for (int j = 0; j < i; j++)
236  {
237  temp = temp->next;
238  }
239  return temp;
240  }
241 
242  void remove(ctr *node)
243  {
244  if (node->prev != NULL)
245  {
246  node->prev->next = node->next;
247  }
248  else
249  {
250  HEAD = node->next;
251  if (HEAD != NULL)
252  {
253  HEAD->prev = NULL; // KCK -- added (2008/05/23)
254  }
255  }
256  if (node->next != NULL)
257  {
258  node->next->prev = node->prev;
259  }
260  else
261  {
262  TAIL = node->prev;
263  if (TAIL != NULL)
264  {
265  TAIL->next = NULL; // KCK -- added (2008/05/23)
266  }
267  }
268  this->release_elem(node);
269  NumElements--;
270  }
271 
272  // Copy function
273  void CopyList(const LinkedList<T> &src, LinkedList<T> &dest)
274  {
275  dest.initialize();
276  int N = src.size();
277  for (int i = 0; i < N; ++i)
278  {
279  dest.addCopy(*(src.ReturnElement(i)));
280  }
281  }
282  };
283 
284  template<class T>
286  {
287  public:
288  // Default constructor
290  {
291  NumElements = 0;
292  }
293 
294  // Copy Constructor
296  {
297  this->CopyList(src, *this);
298  }
299 
301  {
302  ctr *tptr;
303  while (this->size() > 0)
304  {
305  tptr = HEAD;
306  HEAD = HEAD->next;
307  this->remove(tptr);
308  }
309  }
310 
311  // Copy Assignment
313  {
314  this->CopyList(src, *this);
315  return *this;
316  }
317 
318  void initialize()
319  {
320  ctr *tptr;
321  while (this->size() > 0)
322  {
323  tptr = HEAD;
324  HEAD = HEAD->next;
325  this->remove(tptr);
326  }
327  }
328 
329  int size()
330  {
331  return NumElements;
332  }
333 
334  void add(T &newElem)
335  {
336  if (this->size() == 0)
337  {
338  this->CreateNewLinkedList(&newElem);
339  }
340  else
341  {
342  this->addToTail(&newElem);
343  }
344  }
345 
346  void addCopy(const T &newElem)
347  {
348  T* copyElem = new T;
349  *copyElem = newElem;
350  this->add(*copyElem);
351  }
352 
353  // Adds a new element at location i, and moves previous i (and all above) to
354  // i+1 (and so on). If i >= Size the new element will be added to the end
355  // of the list
356  void insertAt(T &newElem, int i)
357  {
358  this->addInPosition(&newElem, i);
359  }
360 
361  void insertCopyAt(const T &newElem, int i)
362  {
363  T* copyElem = new T;
364  *copyElem = newElem;
365  this->addInPosition(copyElem, i);
366  }
367 
368  void remove(int i)
369  {
370  ctr *tptr;
371  tptr = this->get(i);
372  if (tptr) // if tptr!=NULL
373  {
374  this->remove(tptr);
375  }
376  }
377 
378  T* ReturnElement(int i)
379  {
380  // returns NULL if index out of bounds
381  ctr* temp = this->get(i);
382  if (NULL == temp)
383  {
384  return NULL;
385  }
386  else
387  {
388  return (temp->Data);
389  }
390  }
391 
392  // Crops list by removing all elements from i to the end (i inclusive)
393  void CropList(int i)
394  {
395  while (this->ReturnElement(i))
396  {
397  this->remove(i);
398  }
399  }
400 
401  private:
402  struct ctr
403  {
404  T *Data;
407  };
412 
413  // void UpdatePointers()
414  void CreateNewLinkedList(T *firstElement)
415  {
416  temp = this->alloc_elem(firstElement);
417  HEAD = temp;
418  TAIL = temp;
419  temp->next = NULL;
420  temp->prev = NULL;
421  NumElements++;
422  }
423 
424  void addToTail(T *newElem)
425  {
426  temp = this->alloc_elem(newElem);
427  temp->prev = TAIL;
428  TAIL = temp;
429  temp->next = NULL;
430  temp->prev->next = temp;
431  NumElements++;
432  }
433 
434  void addInPosition(T *elem, int i)
435  {
436  ctr *itemToMove = this->get(i);
437  if (itemToMove == NULL)
438  {
439  this->add(*elem); // KCK modified
440  }
441  else
442  {
443  temp = this->alloc_elem(elem);
444  temp->next = itemToMove;
445  temp->prev = itemToMove->prev;
446  if (temp->prev != NULL)
447  {
448  itemToMove->prev->next = temp;
449  }
450  else
451  {
452  this->HEAD = temp;
453  }
454  itemToMove->prev = temp;
455  NumElements++;
456  }
457  }
458 
459  ctr* alloc_elem(T *elem)
460  {
461  ctr *tptr = new ctr;
462  tptr->Data = elem;
463  return tptr;
464  }
465 
466  void release_elem(ctr *elem)
467  {
468  delete elem;
469  }
470 
471  ctr* get(int i)
472  {
473  if (i >= this->size() || i < 0)
474  {
475  return NULL;
476  }
477  ctr* temp = HEAD;
478  for (int j = 0; j < i; j++)
479  {
480  temp = temp->next;
481  }
482  return temp;
483  }
484 
485  void remove(ctr *node)
486  {
487  if (node->prev != NULL)
488  {
489  node->prev->next = node->next;
490  }
491  else
492  {
493  HEAD = node->next;
494  if (HEAD != NULL)
495  {
496  HEAD->prev = NULL; // KCK -- added (2008/05/23)
497  }
498  }
499  if (node->next != NULL)
500  {
501  node->next->prev = node->prev;
502  }
503  else
504  {
505  TAIL = node->prev;
506  if (TAIL != NULL)
507  {
508  TAIL->next = NULL; // KCK -- added (2008/05/23)
509  }
510  }
511  this->release_elem(node);
512  NumElements--;
513  }
514 
515  // Copy function
516  void CopyList(
517  const LinkedList_NoDealloc<T> &src,
519  {
520  dest.initialize();
521  int N = src.size();
522  for (int i = 0; i < N; ++i)
523  {
524  dest.addCopy(*(src.ReturnElement(i)));
525  }
526  }
527  };
528 }
529 
530 #endif // MARTI_DATA_STRUCTURES_LINKED_LIST_H_
void CreateNewLinkedList(T *firstElement)
Definition: linked_list.h:170
void insertAt(T &newElem, int i)
Definition: linked_list.h:112
void insertCopyAt(const T &newElem, int i)
Definition: linked_list.h:361
void addCopy(const T &newElem)
Definition: linked_list.h:102
LinkedList(const LinkedList< T > &src)
Definition: linked_list.h:50
LinkedList_NoDealloc(const LinkedList_NoDealloc< T > &src)
Definition: linked_list.h:295
#define NULL
Definition: linked_list.h:34
void CopyList(const LinkedList< T > &src, LinkedList< T > &dest)
Definition: linked_list.h:273
void CopyList(const LinkedList_NoDealloc< T > &src, LinkedList_NoDealloc< T > &dest)
Definition: linked_list.h:516
void insertCopyAt(const T &newElem, int i)
Definition: linked_list.h:117
LinkedList_NoDealloc< T > & operator=(const LinkedList_NoDealloc< T > &src)
Definition: linked_list.h:312
LinkedList< T > & operator=(const LinkedList< T > &src)
Definition: linked_list.h:68
void addInPosition(T *elem, int i)
Definition: linked_list.h:190


marti_data_structures
Author(s): Kris Kozak
autogenerated on Fri Jun 7 2019 22:05:37