Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Changeset 2860 in orxonox.OLD for orxonox/branches/dave/src/list.h


Ignore:
Timestamp:
Nov 15, 2004, 11:13:21 PM (20 years ago)
Author:
dave
Message:

orxonox/branches/dave: das level hat jetzt form angenommen, stand:nach der Convention vom Samstag….

File:
1 edited

Legend:

Unmodified
Added
Removed

  • orxonox/branches/dave/src/list.h

    r2636 r2860  
    1 /*
    2    orxonox - the future of 3D-vertical-scrollers
    3 
    4    Copyright (C) 2004 orx
    5 
    6    This program is free software; you can redistribute it and/or modify
    7    it under the terms of the GNU General Public License as published by
    8    the Free Software Foundation; either version 2, or (at your option)
    9    any later version.
    10 
    11    ### File Specific:
    12    main-programmer: Christian Meyer
    13 
    14    ADDONS/FIXES:
    15  
    16    Patrick Boenzli     :          Implemented getSize() function
    17 */
    18 
    19 
    20 /*!
    21   \file list.h
    22   \brief Contains a template for a doubly linked list
    23 */
    241
    252#ifndef LIST_H
    263#define LIST_H
    274
    28 #include "stdlib.h"
     5#include "stdincl.h"
    296
    307//! An enum to list all the modes available when adding an object to a List
    31 enum ADDMODE {LIST_ADD_NEXT, LIST_ADD_PREV, LIST_ADD_FIRST, LIST_ADD_LAST};
     8//enum ADDMODE {LIST_ADD_FIRST, LIST_ADD_LAST};
    329//! An enum to list the two searching directions available when removing an object from a List
    33 enum FINDMODE {LIST_FIND_BW, LIST_FIND_FW};
    34 
    35 //! A generic doubly linked list
    36 template<class T> class List
    37 {
    38   T* object;
    39   List<T>* next;
    40   List<T>* prev;
    41   bool bReference;
    42   int size;
     10//enum FINDMODE {LIST_FIND_BW, LIST_FIND_FW};
     11
     12
     13
     14class WorldEntity;
     15
     16class List {
     17
     18 public:
     19  List ();
     20  ~List ();
     21
     22  void add(WorldEntity* entity);
     23  void remove(WorldEntity* entity);
     24  void clear();
     25  WorldEntity* firstElement();
     26  bool isEmpty();
     27  int getSize();
     28  WorldEntity* enumerate();
     29  WorldEntity* nextElement();
     30  WorldEntity* toArray();
     31  void debug();
     32
     33 private:
     34  struct listElement
     35  {
     36    listElement* prev;
     37    WorldEntity* curr;
     38    listElement* next;
     39  };
     40  Uint32 size;
     41  listElement* first;
     42  listElement* last;
     43  listElement* currentEl;
     44
     45
     46};
     47
     48class Iterator
     49{
     50
     51 public:
     52  bool hasNext();
     53  WorldEntity* next();
     54
     55 private:
     56
     57};
     58
     59
     60template<class T> class tList
     61{
     62 private:
     63  struct listElement
     64  {
     65    listElement* prev;
     66    T* curr;
     67    listElement* next;
     68  };
     69
     70  Uint32 size;
     71  listElement* first;
     72  listElement* last;
     73  listElement* currentEl;
    4374 
    4475 public:
    45   List (T* obj, List<T>* n, List<T>* p, bool bRef);
    46   ~List ();
     76  tList ();
     77  ~tList ();
    4778 
    48   int add (T* obj, ADDMODE mode, bool bRef);
    49   T* get_object();
    50   List<T>* get_next ();
    51   List<T>* get_previous ();
    52   List<T>* get_last ();
    53   List<T>* get_first ();
    54   void set_next (List<T>* ptr);
    55   void set_prev (List<T>* ptr);
    56   int remove (T* obj, FINDMODE mode);
     79
     80  void add(WorldEntity* entity);
     81  void remove(WorldEntity* entity);
     82  void clear();
     83  T* firstElement();
     84  bool isEmpty();
    5785  int getSize();
     86  T* enumerate();
     87  T* nextElement();
     88  T* toArray();
     89  void debug();
    5890};
    5991
    6092
    61 /**
    62   \brief Standard constructor
    63  
    64   Call this without any parameters to generate a new List which can be filled with content.
    65   DO NOT create a List element that contains an object on your own, you'll lose the data
    66   contained in that object and will have trouble removing the list from your memory.
    67 */
    68 template<class T>
    69 List<T>::List (T* obj = NULL, List<T>* n = NULL, List<T>* p = NULL, bool bRef = false)
    70 {
    71   object = obj;
    72   next = n;
    73   prev = p;
    74   bReference = bRef;
    75   if(obj != NULL)
    76     ++size;
    77 }
    78 
    79 /**
    80   \brief Standard destructor
    81  
    82   Call this on the initially generated base List element to remove the whole List from the memory.
    83   You can safely do this to any List element you want without messing up the rest of the List, but keep in mind
    84   that the contained object will be deleted as well when bRef had been set to false.
    85 */
    86 template<class T>
    87 List<T>::~List ()
    88 {
    89   if (object == NULL) // deleted foot node => disband the list
    90   {
    91     while( next != NULL)
     93template<class T>
     94tList<T>::tList ()
     95{
     96  this->first = NULL;
     97  this->last = NULL;
     98  this->size = 0;
     99}
     100
     101template<class T>
     102tList<T>::~tList ()
     103{}
     104
     105template<class T>
     106void tList<T>::add(WorldEntity* entity)
     107{
     108  printf("tList<T>::add() \n");
     109  listElement* el = new listElement;
     110  el->prev = this->last;
     111  el->curr = entity;
     112  el->next = NULL;
     113
     114  this->last = el;
     115
     116  if(this->size == 0) this->first = el;
     117  else el->prev->next = el;
     118  this->size++;
     119}
     120
     121
     122template<class T>
     123void tList<T>::remove(WorldEntity* entity)
     124{
     125  this->currentEl = this->first;
     126  listElement* te;
     127  while( this->currentEl != NULL)
    92128    {
    93       delete next;
     129      if( this->currentEl->curr == entity)
     130        {
     131          printf("tList<T>::remove() - object found\n");
     132         
     133          if( this->currentEl->prev  == NULL ) this->first = this->currentEl->next;
     134          else this->currentEl->prev->next = this->currentEl->next;
     135
     136          if( this->currentEl->next == NULL) this->last = this->currentEl->prev;
     137          else this->currentEl->next->prev = this->currentEl->prev;
     138
     139          te = this->currentEl->next;
     140          delete this->currentEl;
     141          this->currentEl = te;
     142          return;
     143        }
     144      this->currentEl = this->currentEl->next;
    94145    }
    95     while( prev != NULL)
     146}
     147
     148
     149template<class T>
     150void tList<T>::clear()
     151{
     152  printf("tList<T>::clear() - clearing all world objects, releasing mem\n");
     153  this->currentEl = this->first;
     154  while(this->currentEl != NULL)
    96155    {
    97       delete prev;
     156      listElement* le = this->currentEl->next;
     157      delete this->currentEl->curr;
     158      delete this->currentEl;
     159      this->currentEl = le;
    98160    }
    99   }
    100   else
    101   {
    102     if (prev != NULL) prev->set_next (next);
    103     if (next != NULL) next->set_prev (prev);
    104     if (!bReference) delete object;
    105   }
    106 }
    107  
    108 /**
    109   \brief Add an object to the List
    110   \param obj: A pointer to an allocated object
    111   \param mode: A Value of ADDMODE (default: LIST_ADD_NEXT)
    112   \param bRef: Sets whether the element is serving as a storage point or a simple listing (default: false)
    113   \return 0 if the operation succeded, -1 if the element could not be added
    114  
    115   This adds a new List element to the chain. The mode parameter can be used to specify
    116   the location where the element should be added. LIST_ADD_NEXT will add the new element directly
    117   after the base element. LIST_ADD_PREV will add the new element directly before the base element.
    118   LIST_ADD_FIRST will add the element at the beginning of the List whereas LIST_ADD_LAST will add
    119   it to the end of the chain. If the bRef parameter is set to true, the object pointer will not be deleted
    120   when the element containing that object is deleted, thus the List can be used for temporary listings as
    121   well as permanent data storage.
    122 */
    123 template<class T>
    124 int List<T>::add (T* obj, ADDMODE mode = LIST_ADD_NEXT, bool bRef = false)
    125 {
    126   List<T>* p;
    127   if( obj == NULL) return -1;
    128   switch (mode)
    129   {
    130     case LIST_ADD_NEXT:
    131       p = new List<T>( obj, next, this, bRef);
    132       if( next != NULL) next->set_prev (p);
    133       next = p;
    134       break;
    135     case LIST_ADD_PREV:
    136       p = new List<T>( obj, this, prev, bRef);
    137       if( prev != NULL) prev->set_next (p);
    138       prev = p;
    139       break;
    140     case LIST_ADD_FIRST:
    141       if (prev == NULL) prev = new List<T> (obj, this, NULL, bRef);
    142       else return prev->add (obj, mode, bRef);
    143       break;
    144     case LIST_ADD_LAST:
    145       if (next == NULL) next = new List<T> (obj, NULL, this, bRef);
    146       else return next->add (obj, mode, bRef);
    147       break;
    148     default:
    149         return -1;
    150       break;
    151   }
    152   ++size;
    153   return 0;
    154 }
    155 
    156 /**
    157   \brief Get the next element of the List
    158   \return The List element after the current List element
    159 */
    160 template<class T>
    161 List<T>* List<T>::get_next ()
    162 {
    163   return next;
    164 }
    165  
    166 /**
    167   \brief Get the previous element of the List
    168   \return The List element before the current List element
    169 */
    170 template<class T>
    171 List<T>* List<T>::get_previous ()
    172 {
    173   return prev;
    174 }
    175 
    176 /**
    177   \brief Get the last element of the List
    178   \return The last List element
    179 */
    180 template<class T>
    181 List<T>* List<T>::get_last ()
    182 {
    183   if (next == NULL) return this;
    184   else return next->get_last();
    185 }
    186 
    187 /**
    188   \brief Get the first element of the List
    189   \return The first List element
    190 */
    191 template<class T>
    192 List<T>* List<T>::get_first ()
    193 {
    194   if (prev == NULL) return this;
    195   else return prev->get_first();
    196 }
    197 
    198 /**
    199   \brief Removes a certain element from the List
    200   \param obj: A pointer to the object that should be removed
    201   \param mode: A value of FINDMODE
    202   \return 0 if the element was found and removed, -1 if the element was not found
    203  
    204   This searches the part of the List specified with mode for the object in question.
    205   When the object is found it is deleted and the List element is removed from the chain.
    206   If mode is LIST_FIND_FW all elements AFTER the base element are searched, if mode is
    207   LIST_FIND_BW all elements BEFORE the base element are searched. Note that the object
    208   contained within the List element is NOT deleted when bRef was set to true.
    209 */
    210 template<class T>
    211 int List<T>::remove (T* obj, FINDMODE mode = LIST_FIND_FW)
    212 {
    213   if (obj == NULL) return -1;
    214   else
    215   {
    216     switch (mode)
    217     {
    218       case LIST_FIND_BW:
    219         if (prev == NULL) return -1;
    220         else
    221         {
    222           if( prev->get_object() == obj)
    223           {
    224             delete prev;
    225           }
    226           else
    227           {
    228             return prev->remove( obj, mode);
    229           }
    230         }
    231         break;
    232       case LIST_FIND_FW:
    233         if (next == NULL) return -1;
    234         else
    235         {
    236           if( next->get_object() == obj)
    237           {
    238             delete next;
    239           }
    240           else
    241           {
    242             return next->remove( obj, mode);
    243           }
    244         }
    245         break;
    246       default:
    247         return -1;
    248     }
    249   }
    250   --size;
    251   return 0;
    252 }
    253 
    254 /**
    255   \brief Set the next element of a List element
    256   \param ptr: A pointer to the new next element
    257    
    258   Sets the next element of a List element... Better not touch this, it can really mess up a List.
    259 */
    260 template<class T>
    261 void List<T>::set_next (List<T>* ptr)
    262 {
    263   next = ptr;
    264 }
    265 
    266 /**
    267   \brief Set the prev element of a List element
    268   \param ptr: A pointer to the new previous element
    269    
    270   Sets the previous element of a List element... Better not touch this, it can really mess up a List.
    271 */
    272 template<class T>
    273 void List<T>::set_prev (List<T>* ptr)
    274 {
    275   prev = ptr;
    276 }
    277 
    278 /**
    279   \brief Get the pointer to the object the element is containing
    280   \return The contained object (will be NULL if called on the base element).
    281 */
    282 template<class T>
    283 T* List<T>::get_object()
    284 {
    285   return object;
    286 }
    287 
    288 
    289 /**
    290   \brief Returns the current size of the List
    291   \return Size of List
    292 */
    293 template<class T>
    294 int List<T>::getSize()
     161  this->first = NULL;
     162  this->last = NULL;
     163  this->size = 0;
     164}
     165
     166
     167template<class T>
     168T* tList<T>::firstElement()
     169{
     170  return this->first->curr;
     171}
     172
     173
     174template<class T>
     175bool tList<T>::isEmpty()
     176{
     177  return (this->size==0)?true:false;
     178}
     179
     180
     181template<class T>
     182int tList<T>::getSize()
    295183{
    296184  return this->size;
    297185}
    298186
     187
     188template<class T>
     189T* tList<T>::enumerate()
     190{
     191  if(this->size == 0) return NULL;
     192  this->currentEl = this->first;
     193  return this->currentEl->curr;
     194}
     195
     196
     197template<class T>
     198T* tList<T>::nextElement()
     199{
     200  if(this->size == 0) return NULL;
     201  this->currentEl = this->currentEl->next;
     202  if(this->currentEl == NULL) return NULL;
     203  return this->currentEl->curr;
     204}
     205
     206
     207template<class T>
     208T* tList<T>::toArray()
     209{}
     210
    299211#endif
    300 
Note: See TracChangeset for help on using the changeset viewer.