[2816] | 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 | */ |
---|
| 24 | |
---|
[3224] | 25 | #ifndef _LIST_TEMPLATE_H |
---|
| 26 | #define _LIST_TEMPLATE_H |
---|
[2816] | 27 | |
---|
| 28 | #include "stdincl.h" |
---|
| 29 | |
---|
| 30 | //! 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}; |
---|
| 32 | //! 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 ListTemplate |
---|
| 37 | { |
---|
| 38 | T* object; |
---|
| 39 | ListTemplate<T>* next; |
---|
| 40 | ListTemplate<T>* prev; |
---|
| 41 | bool bReference; |
---|
| 42 | int size; |
---|
| 43 | |
---|
| 44 | public: |
---|
| 45 | ListTemplate (T* obj, ListTemplate<T>* n, ListTemplate<T>* p, bool bRef); |
---|
| 46 | ~ListTemplate (); |
---|
| 47 | |
---|
[3214] | 48 | int add(T* obj, ADDMODE mode, bool bRef); |
---|
[3230] | 49 | T* getObject(); |
---|
| 50 | ListTemplate<T>* getNext(); |
---|
| 51 | ListTemplate<T>* getPrevious(); |
---|
| 52 | ListTemplate<T>* getLast(); |
---|
| 53 | ListTemplate<T>* getFirst(); |
---|
| 54 | void setNext(ListTemplate<T>* ptr); |
---|
| 55 | void setPrev(ListTemplate<T>* ptr); |
---|
[2816] | 56 | int remove (T* obj, FINDMODE mode); |
---|
| 57 | int getSize(); |
---|
[3214] | 58 | void destroy(); |
---|
[2816] | 59 | }; |
---|
| 60 | |
---|
| 61 | |
---|
| 62 | /** |
---|
| 63 | \brief Standard constructor |
---|
| 64 | |
---|
| 65 | Call this without any parameters to generate a new ListTemplate which can be filled with content. |
---|
| 66 | DO NOT create a ListTemplate element that contains an object on your own, you'll lose the data |
---|
| 67 | contained in that object and will have trouble removing the list from your memory. |
---|
| 68 | */ |
---|
| 69 | template<class T> |
---|
| 70 | ListTemplate<T>::ListTemplate (T* obj = NULL, ListTemplate<T>* n = NULL, ListTemplate<T>* p = NULL, bool bRef = false) |
---|
| 71 | { |
---|
| 72 | object = obj; |
---|
| 73 | next = n; |
---|
| 74 | prev = p; |
---|
| 75 | bReference = bRef; |
---|
| 76 | if(obj != NULL) |
---|
| 77 | ++size; |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | /** |
---|
| 81 | \brief Standard destructor |
---|
| 82 | |
---|
| 83 | Call this on the initially generated base ListTemplate element to remove the whole ListTemplate from the memory. |
---|
| 84 | You can safely do this to any ListTemplate element you want without messing up the rest of the ListTemplate, but keep in mind |
---|
| 85 | that the contained object will be deleted as well when bRef had been set to false. |
---|
| 86 | */ |
---|
| 87 | template<class T> |
---|
| 88 | ListTemplate<T>::~ListTemplate () |
---|
| 89 | { |
---|
| 90 | if (object == NULL) // deleted foot node => disband the list |
---|
| 91 | { |
---|
| 92 | while( next != NULL) |
---|
| 93 | { |
---|
| 94 | delete next; |
---|
| 95 | } |
---|
| 96 | while( prev != NULL) |
---|
| 97 | { |
---|
| 98 | delete prev; |
---|
| 99 | } |
---|
| 100 | } |
---|
| 101 | else |
---|
| 102 | { |
---|
[3230] | 103 | if (prev != NULL) prev->setNext (next); |
---|
| 104 | if (next != NULL) next->setPrev (prev); |
---|
[2816] | 105 | if (!bReference) delete object; |
---|
| 106 | } |
---|
| 107 | } |
---|
| 108 | |
---|
| 109 | /** |
---|
| 110 | \brief Add an object to the ListTemplate |
---|
| 111 | \param obj: A pointer to an allocated object |
---|
| 112 | \param mode: A Value of ADDMODE (default: LIST_ADD_NEXT) |
---|
| 113 | \param bRef: Sets whether the element is serving as a storage point or a simple listing (default: false) |
---|
| 114 | \return 0 if the operation succeded, -1 if the element could not be added |
---|
| 115 | |
---|
| 116 | This adds a new ListTemplate element to the chain. The mode parameter can be used to specify |
---|
| 117 | the location where the element should be added. LIST_ADD_NEXT will add the new element directly |
---|
| 118 | after the base element. LIST_ADD_PREV will add the new element directly before the base element. |
---|
| 119 | LIST_ADD_FIRST will add the element at the beginning of the ListTemplate whereas LIST_ADD_LAST will add |
---|
| 120 | it to the end of the chain. If the bRef parameter is set to true, the object pointer will not be deleted |
---|
| 121 | when the element containing that object is deleted, thus the ListTemplate can be used for temporary listings as |
---|
| 122 | well as permanent data storage. |
---|
| 123 | */ |
---|
| 124 | template<class T> |
---|
| 125 | int ListTemplate<T>::add (T* obj, ADDMODE mode = LIST_ADD_NEXT, bool bRef = false) |
---|
| 126 | { |
---|
| 127 | ListTemplate<T>* p; |
---|
| 128 | if( obj == NULL) return -1; |
---|
| 129 | switch (mode) |
---|
| 130 | { |
---|
| 131 | case LIST_ADD_NEXT: |
---|
| 132 | p = new ListTemplate<T>( obj, next, this, bRef); |
---|
[3230] | 133 | if( next != NULL) next->setPrev (p); |
---|
[2816] | 134 | next = p; |
---|
| 135 | break; |
---|
| 136 | case LIST_ADD_PREV: |
---|
| 137 | p = new ListTemplate<T>( obj, this, prev, bRef); |
---|
[3230] | 138 | if( prev != NULL) prev->setNext (p); |
---|
[2816] | 139 | prev = p; |
---|
| 140 | break; |
---|
| 141 | case LIST_ADD_FIRST: |
---|
| 142 | if (prev == NULL) prev = new ListTemplate<T> (obj, this, NULL, bRef); |
---|
| 143 | else return prev->add (obj, mode, bRef); |
---|
| 144 | break; |
---|
| 145 | case LIST_ADD_LAST: |
---|
| 146 | if (next == NULL) next = new ListTemplate<T> (obj, NULL, this, bRef); |
---|
| 147 | else return next->add (obj, mode, bRef); |
---|
| 148 | break; |
---|
| 149 | default: |
---|
| 150 | return -1; |
---|
| 151 | break; |
---|
| 152 | } |
---|
| 153 | ++size; |
---|
| 154 | return 0; |
---|
| 155 | } |
---|
| 156 | |
---|
| 157 | /** |
---|
| 158 | \brief Get the next element of the ListTemplate |
---|
| 159 | \return The ListTemplate element after the current ListTemplate element |
---|
| 160 | */ |
---|
| 161 | template<class T> |
---|
[3230] | 162 | ListTemplate<T>* ListTemplate<T>::getNext () |
---|
[2816] | 163 | { |
---|
| 164 | return next; |
---|
| 165 | } |
---|
| 166 | |
---|
| 167 | /** |
---|
| 168 | \brief Get the previous element of the ListTemplate |
---|
| 169 | \return The ListTemplate element before the current ListTemplate element |
---|
| 170 | */ |
---|
| 171 | template<class T> |
---|
[3230] | 172 | ListTemplate<T>* ListTemplate<T>::getPrevious () |
---|
[2816] | 173 | { |
---|
| 174 | return prev; |
---|
| 175 | } |
---|
| 176 | |
---|
| 177 | /** |
---|
| 178 | \brief Get the last element of the ListTemplate |
---|
| 179 | \return The last ListTemplate element |
---|
| 180 | */ |
---|
| 181 | template<class T> |
---|
[3230] | 182 | ListTemplate<T>* ListTemplate<T>::getLast () |
---|
[2816] | 183 | { |
---|
| 184 | if (next == NULL) return this; |
---|
[3230] | 185 | else return next->getLast(); |
---|
[2816] | 186 | } |
---|
| 187 | |
---|
| 188 | /** |
---|
| 189 | \brief Get the first element of the ListTemplate |
---|
| 190 | \return The first ListTemplate element |
---|
| 191 | */ |
---|
| 192 | template<class T> |
---|
[3230] | 193 | ListTemplate<T>* ListTemplate<T>::getFirst () |
---|
[2816] | 194 | { |
---|
| 195 | if (prev == NULL) return this; |
---|
[3230] | 196 | else return prev->getFirst(); |
---|
[2816] | 197 | } |
---|
| 198 | |
---|
| 199 | /** |
---|
| 200 | \brief Removes a certain element from the ListTemplate |
---|
| 201 | \param obj: A pointer to the object that should be removed |
---|
| 202 | \param mode: A value of FINDMODE |
---|
| 203 | \return 0 if the element was found and removed, -1 if the element was not found |
---|
| 204 | |
---|
| 205 | This searches the part of the ListTemplate specified with mode for the object in question. |
---|
| 206 | When the object is found it is deleted and the ListTemplate element is removed from the chain. |
---|
| 207 | If mode is LIST_FIND_FW all elements AFTER the base element are searched, if mode is |
---|
| 208 | LIST_FIND_BW all elements BEFORE the base element are searched. Note that the object |
---|
| 209 | contained within the ListTemplate element is NOT deleted when bRef was set to true. |
---|
| 210 | */ |
---|
| 211 | template<class T> |
---|
| 212 | int ListTemplate<T>::remove (T* obj, FINDMODE mode = LIST_FIND_FW) |
---|
| 213 | { |
---|
| 214 | if (obj == NULL) return -1; |
---|
| 215 | else |
---|
| 216 | { |
---|
| 217 | switch (mode) |
---|
| 218 | { |
---|
| 219 | case LIST_FIND_BW: |
---|
| 220 | if (prev == NULL) return -1; |
---|
| 221 | else |
---|
| 222 | { |
---|
[3230] | 223 | if( prev->getObject() == obj) |
---|
[2816] | 224 | { |
---|
| 225 | delete prev; |
---|
| 226 | } |
---|
| 227 | else |
---|
| 228 | { |
---|
| 229 | return prev->remove( obj, mode); |
---|
| 230 | } |
---|
| 231 | } |
---|
| 232 | break; |
---|
| 233 | case LIST_FIND_FW: |
---|
| 234 | if (next == NULL) return -1; |
---|
| 235 | else |
---|
| 236 | { |
---|
[3230] | 237 | if( next->getObject() == obj) |
---|
[2816] | 238 | { |
---|
| 239 | delete next; |
---|
| 240 | } |
---|
| 241 | else |
---|
| 242 | { |
---|
| 243 | return next->remove( obj, mode); |
---|
| 244 | } |
---|
| 245 | } |
---|
| 246 | break; |
---|
| 247 | default: |
---|
| 248 | return -1; |
---|
| 249 | } |
---|
| 250 | } |
---|
| 251 | --size; |
---|
| 252 | return 0; |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | /** |
---|
| 256 | \brief Set the next element of a ListTemplate element |
---|
| 257 | \param ptr: A pointer to the new next element |
---|
| 258 | |
---|
| 259 | Sets the next element of a ListTemplate element... Better not touch this, it can really mess up a ListTemplate. |
---|
| 260 | */ |
---|
| 261 | template<class T> |
---|
[3230] | 262 | void ListTemplate<T>::setNext (ListTemplate<T>* ptr) |
---|
[2816] | 263 | { |
---|
| 264 | next = ptr; |
---|
| 265 | } |
---|
| 266 | |
---|
| 267 | /** |
---|
| 268 | \brief Set the prev element of a ListTemplate element |
---|
| 269 | \param ptr: A pointer to the new previous element |
---|
| 270 | |
---|
| 271 | Sets the previous element of a ListTemplate element... Better not touch this, it can really mess up a ListTemplate. |
---|
| 272 | */ |
---|
| 273 | template<class T> |
---|
[3230] | 274 | void ListTemplate<T>::setPrev (ListTemplate<T>* ptr) |
---|
[2816] | 275 | { |
---|
| 276 | prev = ptr; |
---|
| 277 | } |
---|
| 278 | |
---|
| 279 | /** |
---|
| 280 | \brief Get the pointer to the object the element is containing |
---|
| 281 | \return The contained object (will be NULL if called on the base element). |
---|
| 282 | */ |
---|
| 283 | template<class T> |
---|
[3230] | 284 | T* ListTemplate<T>::getObject() |
---|
[2816] | 285 | { |
---|
| 286 | return object; |
---|
| 287 | } |
---|
| 288 | |
---|
| 289 | |
---|
| 290 | /** |
---|
| 291 | \brief Returns the current size of the ListTemplate |
---|
| 292 | \return Size of ListTemplate |
---|
| 293 | */ |
---|
| 294 | template<class T> |
---|
| 295 | int ListTemplate<T>::getSize() |
---|
| 296 | { |
---|
| 297 | return this->size; |
---|
| 298 | } |
---|
| 299 | |
---|
[3214] | 300 | |
---|
| 301 | template<class T> |
---|
| 302 | void ListTemplate<T>::destroy() |
---|
| 303 | { |
---|
| 304 | /* \todo at the moment - doing nothing. should delete everything */ |
---|
| 305 | } |
---|
| 306 | |
---|
[3224] | 307 | #endif /* _LIST_TENMPLATE_H */ |
---|
[2816] | 308 | |
---|