Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Changeset 2816 in orxonox.OLD for orxonox/trunk/src/list.h


Ignore:
Timestamp:
Nov 11, 2004, 10:32:34 PM (20 years ago)
Author:
patrick
Message:

orxonox/trunk/src: new list implemented

File:
1 edited

Legend:

Unmodified
Added
Removed

  • orxonox/trunk/src/list.h

    r2636 r2816  
    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};
     10//enum FINDMODE {LIST_FIND_BW, LIST_FIND_FW};
    3411
    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;
    43  
     12
     13
     14class WorldEntity;
     15
     16class List {
     17
    4418 public:
    45   List (T* obj, List<T>* n, List<T>* p, bool bRef);
     19  List ();
    4620  ~List ();
    47  
    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);
     21
     22  void add(WorldEntity* entity);
     23  void remove(WorldEntity* entity);
     24  void clear();
     25  WorldEntity* firstElement();
     26  bool isEmpty();
    5727  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
    5846};
    5947
     48class Iterator
     49{
    6050
    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 }
     51 public:
     52  bool hasNext();
     53  WorldEntity* next();
    7854
    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)
    92     {
    93       delete next;
    94     }
    95     while( prev != NULL)
    96     {
    97       delete prev;
    98     }
    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 }
     55 private:
    15556
    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()
    295 {
    296   return this->size;
    297 }
     57};
    29858
    29959#endif
    300 
Note: See TracChangeset for help on using the changeset viewer.