Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: orxonox.OLD/branches/2d-recalc/src/lib/util/list.h @ 5815

Last change on this file since 5815 was 5285, checked in by bensch, 19 years ago

orxonox/trunk: nicer quit-modi
TextEngine is now deleted by GraphicsEngine
trying to fix errors in the Element2D deletion

File size: 12.4 KB
Line 
1/*!
2 * @file list.h
3 * 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
14template<class T> class tIterator;
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 *  the list template class
26
27   you will use this as a generic list for all type of objects
28 */
29template<class T> class tList
30{
31  friend class tIterator<T>;
32
33  public:
34    tList ();
35    ~tList ();
36
37    void add(T* entity);
38    void addAtBeginning(T* entity); //!< @todo This should be made with an ENUM
39    void remove(const T* entity);
40    void removeLast();
41    void flush();
42    T* firstElement() const;
43    T* lastElement() const;
44    bool isEmpty() const;
45    unsigned int getSize() const;
46    bool inList(T* entity) const;
47    tIterator<T>* getIterator() const;
48    T* nextElement(T* toEntity);
49    T* toArray();
50
51  private:
52    unsigned int       size;             //!< the size (lenght) of the list
53    listElement<T>*    first;            //!< pointer to the first element
54    listElement<T>*    last;             //!< pointer to the last element
55    listElement<T>*    currentEl;        //!< pointer to the current element
56};
57
58
59/**
60 *  the constructor
61 */
62template<class T>
63    inline tList<T>::tList ()
64{
65  this->currentEl = NULL;
66  this->first = NULL;
67  this->last = NULL;
68  this->size = 0;
69}
70
71
72/**
73 *  the deconstructor
74
75   this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will remain
76 */
77template<class T>
78    inline tList<T>::~tList ()
79{
80  this->currentEl = this->first;
81  listElement<T>* le;
82  while(this->currentEl != NULL)
83  {
84    le = this->currentEl->next;
85    delete this->currentEl;
86    this->currentEl = le;
87  }
88  this->first = NULL;
89  this->last = NULL;
90  this->currentEl = NULL;
91  this->size = 0;
92}
93
94
95/**
96 *  add an entity to the list
97 * @param entity: the entity to add
98 */
99template<class T>
100    inline void tList<T>::add(T* entity)
101{
102  if( unlikely(entity == NULL)) return;
103  listElement<T>* el = new listElement<T>;
104  el->prev = this->last;
105  el->curr = entity;
106  el->next = NULL;
107
108  this->last = el;
109
110  if( unlikely(el->prev == NULL)) this->first = el; /* if first element */
111  else el->prev->next = el;
112  this->size++;
113}
114
115/**
116 *  add an entity to the list
117 * @param entity: the entity to add
118 */
119template<class T>
120    inline void tList<T>::addAtBeginning(T* entity)
121{
122  if( unlikely(entity == NULL)) return;
123  listElement<T>* el = new listElement<T>;
124  el->next = this->first;
125  el->curr = entity;
126  el->prev = NULL;
127
128  this->first = el;
129
130  if( unlikely(el->next == NULL)) this->last = el; /* if first element */
131  else el->next->prev = el;
132  this->size++;
133}
134
135
136/**
137 * remove an entity from the list
138 * @param entity: the entity to be removed
139 */
140template<class T>
141    inline void tList<T>::remove(const T* entity)
142{
143  this->currentEl = this->first;
144  while( this->currentEl != NULL)
145  {
146    if( unlikely(this->currentEl->curr == entity))
147    {
148      // erstes element?
149      if( unlikely(this->currentEl->prev == NULL)) this->first = this->currentEl->next;
150      else this->currentEl->prev->next = this->currentEl->next;
151
152      // letztes element?
153      if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
154      else this->currentEl->next->prev = this->currentEl->prev;
155
156      delete this->currentEl;
157      this->size--;
158      return;
159    }
160    this->currentEl = this->currentEl->next;
161  }
162}
163
164
165/**
166 * removes the Last Element of the List
167 */
168 template<class T>
169     inline void tList<T>::removeLast()
170{
171  if( unlikely(this->last == NULL))
172    return;
173
174  // only one element in the list (and its not NULL :D )
175  if( unlikely(this->last == this->first))
176  {
177    delete this->first;
178    this->first = NULL;
179    this->last = NULL;
180    this->size--;
181  }
182  else
183  {
184    listElement<T>* delLast = this->last;
185    this->last->prev->next = NULL;
186    this->last = this->last->prev;
187    delete delLast;
188  }
189}
190
191
192/**
193 *  this will delete all objects from the list, this can be very dangerous if there are ghost objects in the list.
194 */
195template<class T>
196    inline void tList<T>::flush()
197{
198  this->currentEl = this->first;
199
200  listElement<T>* le;
201  while( this->currentEl != NULL)
202  {
203    le = this->currentEl->next;
204    delete this->currentEl->curr;
205    delete this->currentEl;
206    this->currentEl = le;
207  }
208  this->first = NULL;
209  this->last = NULL;
210  this->currentEl = NULL;
211  this->size = 0;
212}
213
214
215/**
216 *  returns the first element of the list
217 * @returns first element
218 */
219template<class T>
220    inline T* tList<T>::firstElement() const
221{
222  return this->first->curr;
223}
224
225
226/**
227 *  function returns the last element of the list
228 * @returns the last element
229 */
230template<class T>
231    inline T* tList<T>::lastElement() const
232{
233  return this->last->curr;
234}
235
236
237/**
238 *  returns true if the list is empty
239 * @returns true if the list is empty
240 */
241template<class T>
242    inline bool tList<T>::isEmpty() const
243{
244  return (this->size == 0)?true:false;
245}
246
247
248/**
249 *  checks if an entity is in the List.
250 * @param entity The entity to check for in the entire List.
251 * @returns true if it is, false otherwise
252 */
253template<class T>
254    inline bool tList<T>::inList(T* entity) const
255{
256  // pre checks
257  if( unlikely(entity == NULL)) return false;
258
259  // search in the List
260  listElement<T>* el = this->first;
261  while( this->currentEl != NULL)
262  {
263    if( this->currentEl->curr == entity)
264      return true;
265
266    el = this->currentEl->next;
267  }
268}
269
270
271/**
272 *  this returns the number of elements in the list
273 * @returns number of elements
274 */
275template<class T>
276    inline unsigned int tList<T>::getSize() const
277{
278  return this->size;
279}
280
281
282/**
283 *  creates an itereator object and returns it
284 * @returns the iterator object to this list
285
286   You will use this, if you want to iterate through the list
287 */
288template<class T>
289    inline tIterator<T>* tList<T>::getIterator() const
290{
291  return new tIterator<T>(this);
292}
293
294
295
296/**
297 *  this returns the next element after toEntity or the first if toEntity is last
298 * @param toEntity: the entity after which is an entity, that has to be returned, sorry, terrible phrase
299 * @returns the element after toEntity
300 */
301template<class T>
302    inline T* tList<T>::nextElement(T* toEntity)
303{
304  //if( this->last == this->first == NULL) return NULL;
305  if(this->size == 0) return NULL;
306  if( toEntity == NULL) return this->first->curr;
307  if( toEntity == this->last->curr ) return this->first->curr;
308  this->currentEl = this->first;
309  while(this->currentEl->curr != toEntity && this->currentEl->next != NULL)
310  {
311    this->currentEl = this->currentEl->next;
312  }
313  if(this->currentEl == NULL) return NULL;
314  return this->currentEl->next->curr;
315}
316
317
318/**
319 *  creates an array out of the list (ATTENTION: not implemented)
320 * @returns pointer to the array beginning
321
322   ATTENTION: function is not implemented and wont do anything
323 */
324template<class T>
325    T* tList<T>::toArray()
326{
327  return NULL;
328}
329
330
331
332
333/**
334    *  an iterator class
335
336   this enables the user to iterate through a list very easely
337 */
338template<class T> class tIterator
339{
340  public:
341    tIterator(const tList<T>* list);
342    ~tIterator();
343
344    T* firstElement();
345    T* lastElement();
346    T* nextElement();
347    T* prevElement();
348    T* seekElement(const T* element);
349    T* iteratorElement(const tIterator<T>* iterator);
350    bool compareListPointer(const tList<T>* list);
351
352    /** another way to iterate through the list
353     * !! THIS IS NOT MEANT FOR DELETION
354     */
355    T* prevStep();
356    T* nextStep();
357    T* getCurrent();
358
359  private:
360    listElement<T>*    currentEl;                      //!< pointer to the current list element in the iterator
361    listElement<T>*    tmpEl;                          //!< temp listElemnt pointer
362    const tList<T>*    list;                           //!< The List, that we want to iterate through
363};
364
365
366/**
367 *  iterator constructor
368 * @param startElement:  the first list element from the tList
369 *
370 * normaly you will use it like this:
371 **********************************************************
372 * tIterator<char>* nameIterator = nameList->getIterator();
373 * char name* = nameIterator->firstElement();
374 * while( name != NULL)
375 *  {
376 *   PRINTF(3)("found name: %s in list\n", name);
377 *   name = nameIterator->nextElement();
378 *  }
379 * delete nameIterator;
380 * ********************************************************
381 */
382template<class T>
383  inline tIterator<T>::tIterator (const tList<T>* list)
384{
385  this->currentEl = NULL;
386  this->tmpEl = NULL;
387  this->list = list;
388}
389
390
391/**
392 *  the destructor
393 */
394template<class T>
395    inline tIterator<T>::~tIterator ()
396{
397  this->currentEl = NULL;
398  this->tmpEl = NULL;
399  this->list = NULL;
400}
401
402/**
403 * this returns the first element of the iterator list
404 * @returns first element
405 */
406template<class T>
407    inline T* tIterator<T>::firstElement ()
408{
409  this->tmpEl = this->list->first;
410  if( likely(this->tmpEl != NULL))
411  {
412    this->currentEl = this->tmpEl->next;
413    return this->tmpEl->curr;
414  }
415  else
416    return NULL;
417}
418
419/**
420 * this returns the last element of the iterator list
421 * @returns last element
422 */
423template<class T>
424    inline T* tIterator<T>::lastElement ()
425{
426  this->tmpEl = this->list->last;
427  if( likely(this->tmpEl != NULL))
428  {
429    this->currentEl = tmpEl->prev;
430    return this->tmpEl->curr;
431  }
432  else
433    return NULL;
434}
435
436
437/**
438 *  use it to iterate through the list
439 * @returns next list element
440 */
441template<class T>
442    inline T* tIterator<T>::nextElement ()
443{
444  if( unlikely(this->currentEl == NULL))
445    return NULL;
446
447  this->tmpEl = this->currentEl;
448  this->currentEl = this->currentEl->next;
449
450  return this->tmpEl->curr;
451}
452
453
454/**
455 *  use it to iterate backwards through the list
456 * @returns next list element
457 */
458template<class T>
459    inline T* tIterator<T>::prevElement ()
460{
461  if( unlikely(this->currentEl == NULL))
462    return NULL;
463
464  this->tmpEl = this->currentEl;
465  this->currentEl = this->currentEl->prev;
466
467  return this->tmpEl->curr;
468}
469
470
471/**
472 *  gets the element after the selected one, sets the iterator to this point in the list
473 * @param element the element to seek
474 * @returns current list element
475 */
476template<class T>
477    inline T* tIterator<T>::seekElement (const T* element)
478{
479  if( unlikely(element == NULL))
480  {
481    this->currentEl = NULL;
482    return NULL;
483  }
484  this->tmpEl = this->list->first;
485  while( this->tmpEl != NULL)
486  {
487    if( unlikely(this->tmpEl->curr == element))
488    {
489      this->currentEl = this->tmpEl;
490      return this->currentEl->curr;
491    }
492    this->tmpEl = this->tmpEl->next;
493  }
494  this->currentEl = NULL;
495  return NULL;
496}
497
498/**
499 * grabs the iterator entity from another iterator
500 * @param iterator the iterator to grab the local currentEl from
501 * @returns the grabbed element (current). NULL if not found, or not defined
502 *
503 * Both iterators must be from the same List!
504 */
505template<class T>
506    T* tIterator<T>::iteratorElement(const tIterator<T>* iterator)
507{
508  if( unlikely(iterator != NULL && iterator->list == this->list))
509  {
510    this->currentEl = iterator->currentEl;
511    if (this->currentEl != NULL)
512      return this->currentEl->curr;
513    else
514      return NULL;
515  }
516  else
517  {
518    this->currentEl = NULL;
519    return NULL;
520  }
521}
522
523template<class T>
524    bool tIterator<T>::compareListPointer(const tList<T>* list)
525{
526  return (this->list == list)?true:false;
527}
528
529
530/**
531 *  use it to move through the list without interfering with the iteration
532 * @returns previous list element
533 *
534 * this stepping mode will !not! step beyond the boundraries of the List!
535 */
536template<class T>
537    inline T* tIterator<T>::nextStep ()
538{
539  if( unlikely(this->tmpEl == NULL || this->tmpEl->next == NULL))
540    return NULL;
541  else
542  {
543    this->tmpEl = this->tmpEl->next;
544    return tmpEl->curr;
545  }
546}
547
548/**
549 *  use it to move backwards through the list without interfering with the itereation
550 * @returns next list element
551 *
552 * this stepping mode will !not! step beyond the boundraries of the List!
553 */
554template<class T>
555    inline T* tIterator<T>::prevStep ()
556{
557  if( unlikely(this->tmpEl == NULL || this->tmpEl->prev == NULL))
558    return NULL;
559  else
560  {
561    this->tmpEl = this->tmpEl->prev;
562    return tmpEl->curr;
563  }
564}
565
566/**
567 * @returns the current Element
568 */
569template<class T>
570    inline T* tIterator<T>::getCurrent()
571{
572  if (likely(this->tmpEl != NULL))
573    return this->tmpEl->curr;
574  else
575    return NULL;
576}
577
578#endif /* _LIST_H */
Note: See TracBrowser for help on using the repository browser.