Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

Last change on this file since 9757 was 5836, checked in by bensch, 19 years ago

orxonox/trunk: new list #define _T_LIST_H

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