Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: orxonox.OLD/orxonox/trunk/src/lib/util/list.h @ 5037

Last change on this file since 5037 was 4836, checked in by bensch, 19 years ago

orxonox/trunk: renamed all the \param → @param and so on in Doxygen tags.
Thanks a lot to the kDevelop team. this took since the last commit :)

File size: 8.1 KB
Line 
1/*!
2  \file list.h
3  \brief a File that includes a List-template
4*/
5
6#ifndef _LIST_H
7#define _LIST_H
8
9#include "compiler.h"
10#ifndef NULL
11#define NULL 0                                       //!< this will define NULL
12#endif
13
14
15
16//! a list element of the tList,
17template<class T> struct listElement
18{
19  listElement*        prev;                          //!< pointer to the previous listElement in the list
20  T*                  curr;                          //!< pointer to the list payload/container
21  listElement*        next;                          //!< pointer to the next listElement
22};
23
24/**
25 *  an iterator class
26
27   this enables the user to iterate through a list very easely
28*/
29template<class T> class tIterator
30{
31 public:
32  tIterator(listElement<T>* startElement);
33  ~tIterator();
34
35  T* nextElement();
36  T* seekElement(T* element);
37
38 private:
39  listElement<T>*    currentEl;                      //!< pointer to the current list element in the iterator
40  listElement<T>*    tmpEl;                          //!< temp listElemnt pointer
41  listElement<T>*    startElement;                   //!< pointer to the start of the list
42};
43
44
45/**
46 *  iterator constructor
47 * @param startElement:  the first list element from the tList
48
49   normaly you will use it like this:
50
51   tIterator<char>* nameIterator = nameList->getIterator();
52   char name* = nameIterator->nextElement();
53   while( name != NULL)
54   {
55     PRINTF(3)("found name: %s in list\n", name);
56     name = nameIterator->nextElement();
57   }
58   delete nameIterator;
59*/
60template<class T>
61inline tIterator<T>::tIterator (listElement<T>* startElement)
62{
63  this->currentEl = startElement;
64  this->tmpEl = NULL;
65  this->startElement = startElement;
66}
67
68
69/**
70 *  the destructor
71*/
72template<class T>
73inline tIterator<T>::~tIterator ()
74{
75  this->currentEl = NULL;
76}
77
78
79/**
80 *  use it to iterate through the list
81 * @returns next list element
82*/
83template<class T>
84inline T* tIterator<T>::nextElement ()
85{
86  if( this->currentEl == NULL)
87    return NULL;
88
89  this->tmpEl = this->currentEl;
90  this->currentEl = this->currentEl->next;
91  return this->tmpEl->curr;
92}
93
94/**
95 *  gets the element after the selected one, sets the iterator to this point in the list
96 * @param element the element to seek
97 * @returns next list element
98
99  Attention: if you seek an element, the iterator pointer will point to the NEXT listelement after the argument!
100 */
101template<class T>
102inline T* tIterator<T>::seekElement (T* element)
103{
104  for(this->tmpEl = this->startElement; this->tmpEl != NULL; this->tmpEl = this->tmpEl->next)
105  {
106    if( unlikely(this->tmpEl->curr == element))
107    {
108      if( this->tmpEl->next != NULL)
109      {
110        this->currentEl = this->tmpEl->next->next;
111        return this->tmpEl->next->curr;
112      }
113      return NULL;
114    }
115  }
116  return NULL;
117}
118
119
120
121/**
122 *  the list template class
123
124   you will use this as a generic list for all type of objects
125*/
126template<class T> class tList
127{
128 public:
129  tList ();
130  ~tList ();
131
132  void add(T* entity);
133  void remove(T* entity);
134  void flush();
135  T* firstElement();
136  T* lastElement();
137  bool isEmpty();
138  int getSize();
139  bool inList(T* entity);
140  tIterator<T>* getIterator();
141  T* nextElement(T* toEntity);
142  T* toArray();
143
144 private:
145  unsigned int       size;             //!< the size (lenght) of the list
146  listElement<T>*    first;            //!< pointer to the first element
147  listElement<T>*    last;             //!< pointer to the last element
148  listElement<T>*    currentEl;        //!< pointer to the current element
149};
150
151
152/**
153 *  the constructor
154*/
155template<class T>
156inline tList<T>::tList ()
157{
158  this->first = NULL;
159  this->last = NULL;
160  this->size = 0;
161}
162
163
164/**
165 *  the deconstructor
166
167   this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will
168   not be deleted
169*/
170template<class T>
171inline tList<T>::~tList ()
172{
173  this->currentEl = this->first;
174  while(this->currentEl != NULL)
175    {
176      listElement<T>* le = this->currentEl->next;
177      //delete this->currentEl->curr;
178      delete this->currentEl;
179      this->currentEl = le;
180    }
181  this->first = NULL;
182  this->last = NULL;
183  this->size = 0;
184}
185
186
187/**
188 *  add an entity to the list
189 * @param entity: the entity to add
190*/
191template<class T>
192inline void tList<T>::add(T* entity)
193{
194  if( unlikely(entity == NULL)) return;
195  listElement<T>* el = new listElement<T>;
196  el->prev = this->last;
197  el->curr = entity;
198  el->next = NULL;
199
200  this->last = el;
201
202  if( unlikely(el->prev == NULL)) this->first = el; /* if first element */
203  else el->prev->next = el;
204  this->size++;
205}
206
207
208/**
209 *  remove an entity from the list
210 * @param entity: the entity to be removed
211*/
212template<class T>
213inline void tList<T>::remove(T* entity)
214{
215  this->currentEl = this->first;
216  listElement<T>* te;
217  while( this->currentEl != NULL)
218    {
219      if( unlikely(this->currentEl->curr == entity))
220        {
221          if( unlikely(this->currentEl->prev  == NULL)) this->first = this->currentEl->next;
222          else this->currentEl->prev->next = this->currentEl->next;
223
224          if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
225          else this->currentEl->next->prev = this->currentEl->prev;
226
227          delete this->currentEl;
228          this->size--;
229          return;
230        }
231      this->currentEl = this->currentEl->next;
232    }
233}
234
235
236/**
237 *  this will deletes the objects from the list
238*/
239template<class T>
240inline void tList<T>::flush()
241{
242  this->currentEl = this->first;
243  while(this->currentEl != NULL)
244    {
245      listElement<T>* le = this->currentEl->next;
246      delete this->currentEl->curr;
247      delete this->currentEl;
248      this->currentEl = le;
249    }
250  this->first = NULL;
251  this->last = NULL;
252  this->size = 0;
253}
254
255
256/**
257 *  returns the first element of the list
258 * @returns first element
259*/
260template<class T>
261inline T* tList<T>::firstElement()
262{
263  return this->first->curr;
264}
265
266
267/**
268 *  function returns the last element of the list
269 * @returns the last element
270*/
271template<class T>
272inline T* tList<T>::lastElement()
273{
274  return this->last->curr;
275}
276
277
278/**
279 *  returns true if the list is empty
280 * @returns true if the list is empty
281*/
282template<class T>
283inline bool tList<T>::isEmpty()
284{
285  return (this->size==0)?true:false;
286}
287
288/**
289 *  checks if an entity is in the List
290 * @param entity The entity to check for in the entire List.
291 * @returns true if it is, false otherwise
292*/
293template<class T>
294inline bool tList<T>::inList(T* entity)
295{
296  // pre checks
297  if(this->size == 0) return false;
298  if( entity == NULL) return false;
299
300  // search in the List
301  this->currentEl = this->first;
302  while(this->currentEl->curr != entity && this->currentEl != NULL)
303    this->currentEl = this->currentEl->next;
304
305  // post checks
306  if(this->currentEl == NULL)
307    return false;
308  else
309    return true;
310}
311
312/**
313 *  this returns the number of elements in the list
314 * @returns number of elements
315*/
316template<class T>
317inline int tList<T>::getSize()
318{
319  return this->size;
320}
321
322
323/**
324 *  creates an itereator object and returns it
325 * @returns the iterator object to this list
326
327   You will use this, if you want to iterate through the list
328*/
329template<class T>
330inline tIterator<T>* tList<T>::getIterator()
331{
332  tIterator<T>* iterator = new tIterator<T>(this->first);
333  return iterator;
334}
335
336
337
338/**
339 *  this returns the next element after toEntity or the first if toEntity is last
340 * @param toEntity: the entity after which is an entity, that has to be returned, sorry, terrible phrase
341 * @returns the element after toEntity
342*/
343template<class T>
344inline T* tList<T>::nextElement(T* toEntity)
345{
346  //if( this->last == this->first == NULL) return NULL;
347  if(this->size == 0) return NULL;
348  if( toEntity == NULL) return this->first->curr;
349  if( toEntity == this->last->curr ) return this->first->curr;
350  this->currentEl = this->first;
351  while(this->currentEl->curr != toEntity && this->currentEl->next != NULL)
352    {
353      this->currentEl = this->currentEl->next;
354    }
355  if(this->currentEl == NULL) return NULL;
356  return this->currentEl->next->curr;
357}
358
359
360/**
361 *  creates an array out of the list (ATTENTION: not implemented)
362 * @returns pointer to the array beginning
363
364   ATTENTION: function is not implemented and wont do anything
365*/
366template<class T>
367T* tList<T>::toArray()
368{
369  return NULL;
370}
371
372#endif /* _LIST_H */
Note: See TracBrowser for help on using the repository browser.