Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: orxonox.OLD/branches/collision_detection/src/lib/util/list.h @ 5875

Last change on this file since 5875 was 5403, checked in by bensch, 19 years ago

orxonox/trunk:
implemented List-addAtIteratorPosition, to add any entity in the Sorted list at a designated position (for include-sorting)
include-sort the list of added Element2D's after their layer-depth

File size: 14.5 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 addAtIteratorPosition(T* entity, tIterator<T>* itereator);
40    void remove(const T* entity);
41    void removeFromLast(const T* entity);
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();
52
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
58};
59
60
61/**
62 *  the constructor
63 */
64template<class T>
65    inline tList<T>::tList ()
66{
67  this->currentEl = NULL;
68  this->first = NULL;
69  this->last = NULL;
70  this->size = 0;
71}
72
73
74/**
75 *  the deconstructor
76
77   this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will remain
78 */
79template<class T>
80    inline tList<T>::~tList ()
81{
82  this->currentEl = this->first;
83  listElement<T>* le;
84  while(this->currentEl != NULL)
85  {
86    le = this->currentEl->next;
87    delete this->currentEl;
88    this->currentEl = le;
89  }
90  this->first = NULL;
91  this->last = NULL;
92  this->currentEl = NULL;
93  this->size = 0;
94}
95
96
97/**
98 *  add an entity to the list
99 * @param entity: the entity to add
100 */
101template<class T>
102    inline void tList<T>::add(T* entity)
103{
104  if( unlikely(entity == NULL)) return;
105  listElement<T>* el = new listElement<T>;
106  el->prev = this->last;
107  el->curr = entity;
108  el->next = NULL;
109
110  this->last = el;
111
112  if( unlikely(el->prev == NULL)) this->first = el; /* if first element */
113  else el->prev->next = el;
114  this->size++;
115}
116
117/**
118 *  add an entity to the list
119 * @param entity: the entity to add
120 */
121template<class T>
122    inline void tList<T>::addAtBeginning(T* entity)
123{
124  if( unlikely(entity == NULL)) return;
125
126  listElement<T>* el = new listElement<T>;
127  el->next = this->first;
128  el->curr = entity;
129  el->prev = NULL;
130
131  this->first = el;
132
133  if( unlikely(el->next == NULL)) this->last = el; /* if first element */
134  else el->next->prev = el;
135  this->size++;
136}
137
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;
167
168    el->next->prev = el;
169    el->prev->next = el;
170  }
171}
172
173/**
174 * remove an entity from the list
175 * @param entity: the entity to be removed
176 */
177template<class T>
178    inline void tList<T>::remove(const T* entity)
179{
180  this->currentEl = this->first;
181  while( this->currentEl != NULL)
182  {
183    if( unlikely(this->currentEl->curr == entity))
184    {
185      // erstes element?
186      if( unlikely(this->currentEl->prev == NULL)) this->first = this->currentEl->next;
187      else this->currentEl->prev->next = this->currentEl->next;
188
189      // letztes element?
190      if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
191      else this->currentEl->next->prev = this->currentEl->prev;
192
193      delete this->currentEl;
194      this->size--;
195      return;
196    }
197    this->currentEl = this->currentEl->next;
198  }
199}
200
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;
219
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
233/**
234 * removes the Last Element of the List
235 */
236 template<class T>
237     inline void tList<T>::removeLast()
238{
239  if( unlikely(this->last == NULL))
240    return;
241
242  // only one element in the list (and its not NULL :D )
243  if( unlikely(this->last == this->first))
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}
258
259
260/**
261 *  this will delete all objects from the list, this can be very dangerous if there are ghost objects in the list.
262 */
263template<class T>
264    inline void tList<T>::flush()
265{
266  this->currentEl = this->first;
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  }
276  this->first = NULL;
277  this->last = NULL;
278  this->currentEl = NULL;
279  this->size = 0;
280}
281
282
283/**
284 *  returns the first element of the list
285 * @returns first element
286 */
287template<class T>
288    inline T* tList<T>::firstElement() const
289{
290  return this->first->curr;
291}
292
293
294/**
295 *  function returns the last element of the list
296 * @returns the last element
297 */
298template<class T>
299    inline T* tList<T>::lastElement() const
300{
301  return this->last->curr;
302}
303
304
305/**
306 *  returns true if the list is empty
307 * @returns true if the list is empty
308 */
309template<class T>
310    inline bool tList<T>::isEmpty() const
311{
312  return (this->size == 0)?true:false;
313}
314
315
316/**
317 *  checks if an entity is in the List.
318 * @param entity The entity to check for in the entire List.
319 * @returns true if it is, false otherwise
320 */
321template<class T>
322    inline bool tList<T>::inList(T* entity) const
323{
324  // pre checks
325  if( unlikely(entity == NULL)) return false;
326
327  // search in the List
328  listElement<T>* el = this->first;
329  while( this->currentEl != NULL)
330  {
331    if( this->currentEl->curr == entity)
332      return true;
333
334    el = this->currentEl->next;
335  }
336}
337
338
339/**
340 *  this returns the number of elements in the list
341 * @returns number of elements
342 */
343template<class T>
344    inline unsigned int tList<T>::getSize() const
345{
346  return this->size;
347}
348
349
350/**
351 *  creates an itereator object and returns it
352 * @returns the iterator object to this list
353
354   You will use this, if you want to iterate through the list
355 */
356template<class T>
357    inline tIterator<T>* tList<T>::getIterator() const
358{
359  return new tIterator<T>(this);
360}
361
362
363
364/**
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
368 */
369template<class T>
370    inline T* tList<T>::nextElement(T* toEntity)
371{
372  //if( this->last == this->first == NULL) return NULL;
373  if(this->size == 0) return NULL;
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)
378  {
379    this->currentEl = this->currentEl->next;
380  }
381  if(this->currentEl == NULL) return NULL;
382  return this->currentEl->next->curr;
383}
384
385
386/**
387 *  creates an array out of the list (ATTENTION: not implemented)
388 * @returns pointer to the array beginning
389
390   ATTENTION: function is not implemented and wont do anything
391 */
392template<class T>
393    T* tList<T>::toArray()
394{
395  return NULL;
396}
397
398
399
400
401/**
402    *  an iterator class
403
404   this enables the user to iterate through a list very easely
405 */
406template<class T> class tIterator
407{
408  friend class tList<T>;
409  public:
410    tIterator(const tList<T>* list);
411    ~tIterator();
412
413    T* firstElement();
414    T* lastElement();
415    T* nextElement();
416    T* prevElement();
417    T* seekElement(const T* element);
418    T* iteratorElement(const tIterator<T>* iterator);
419    bool compareListPointer(const tList<T>* list) const;
420    inline const tList<T>* getList() const { return this->list; };
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
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{
454  this->currentEl = NULL;
455  this->tmpEl = NULL;
456  this->list = list;
457}
458
459
460/**
461 *  the destructor
462 */
463template<class T>
464    inline tIterator<T>::~tIterator ()
465{
466  this->currentEl = NULL;
467  this->tmpEl = NULL;
468  this->list = NULL;
469}
470
471/**
472 * this returns the first element of the iterator list
473 * @returns first element
474 */
475template<class T>
476    inline T* tIterator<T>::firstElement ()
477{
478  this->tmpEl = this->list->first;
479  if( likely(this->tmpEl != NULL))
480  {
481    this->currentEl = this->tmpEl->next;
482    return this->tmpEl->curr;
483  }
484  else
485    return NULL;
486}
487
488/**
489 * this returns the last element of the iterator list
490 * @returns last element
491 */
492template<class T>
493    inline T* tIterator<T>::lastElement ()
494{
495  this->tmpEl = this->list->last;
496  if( likely(this->tmpEl != NULL))
497  {
498    this->currentEl = tmpEl->prev;
499    return this->tmpEl->curr;
500  }
501  else
502    return NULL;
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{
513  if( unlikely(this->currentEl == NULL))
514    return NULL;
515
516  this->tmpEl = this->currentEl;
517  this->currentEl = this->currentEl->next;
518
519  return this->tmpEl->curr;
520}
521
522
523/**
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{
530  if( unlikely(this->currentEl == NULL))
531    return NULL;
532
533  this->tmpEl = this->currentEl;
534  this->currentEl = this->currentEl->prev;
535
536  return this->tmpEl->curr;
537}
538
539
540/**
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>
546    inline T* tIterator<T>::seekElement (const T* element)
547{
548  if( unlikely(element == NULL))
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
570 * @returns the grabbed element (current). NULL if not found, or not defined
571 *
572 * Both iterators must be from the same List!
573 */
574template<class T>
575    T* tIterator<T>::iteratorElement(const tIterator<T>* iterator)
576{
577  if( unlikely(iterator != NULL && iterator->list == this->list))
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
592template<class T>
593    bool tIterator<T>::compareListPointer(const tList<T>* list) const
594{
595  return (this->list == list)?true:false;
596}
597
598
599/**
600 *  use it to move through the list without interfering with the iteration
601 * @returns previous list element
602 *
603 * this stepping mode will !not! step beyond the boundraries of the List!
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
620 *
621 * this stepping mode will !not! step beyond the boundraries of the List!
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
635/**
636 * @returns the current Element
637 */
638template<class T>
639    inline T* tIterator<T>::getCurrent()
640{
641  if (likely(this->tmpEl != NULL))
642    return this->tmpEl->curr;
643  else
644    return NULL;
645}
646
647#endif /* _LIST_H */
Note: See TracBrowser for help on using the repository browser.