List.h

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 1999-2009 Soeren Sonnenburg
00008  * Written (W) 1999-2008 Gunnar Raetsch
00009  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
00010  */
00011 
00012 #ifndef _LIST_H_
00013 #define _LIST_H_
00014 
00015 #include "lib/common.h"
00016 #include "base/SGObject.h"
00017 
00019 template <class T> class CListElement
00020 {
00021     public:
00023         CListElement* next;
00025         CListElement* prev;
00027         T data;
00028 
00029     public:
00036         CListElement(T p_data, CListElement* p_prev = NULL, CListElement* p_next = NULL)
00037         {
00038             this->data = p_data;
00039             this->next = p_next;
00040             this->prev = p_prev;
00041         };
00042 
00044         virtual ~CListElement() { data = NULL; }
00045 };
00046 
00052 template <class T> class CList : public CSGObject
00053 {
00054     public:
00059         CList(bool p_delete_data=false) : CSGObject()
00060         {
00061             first  = NULL;
00062             current = NULL;
00063             last   = NULL;
00064 
00065             num_elements = 0;
00066             this->delete_data=p_delete_data;
00067         }
00068 
00069         virtual ~CList()
00070         {
00071             while (get_num_elements())
00072             {
00073                 T d=delete_element();
00074 
00075                 if (delete_data)
00076                     SG_UNREF(d);
00077             }
00078         }
00079 
00084         inline int32_t get_num_elements() { return num_elements; }
00085 
00090         inline T get_first_element()
00091         {
00092             if (first != NULL)
00093             {
00094                 current = first;
00095                 if (delete_data)
00096                     SG_REF(current->data);
00097                 return current->data;
00098             }
00099             else 
00100                 return NULL;
00101         }
00102 
00107         inline T get_last_element()
00108         {
00109             if (last != NULL)
00110             {
00111                 current = last;
00112                 if (delete_data)
00113                     SG_REF(current->data);
00114                 return current->data;
00115             }
00116             else 
00117                 return NULL;
00118         }
00119 
00124         inline T get_next_element()
00125         {
00126             if ((current != NULL) && (current->next != NULL))
00127             {
00128                 current = current->next;
00129                 if (delete_data)
00130                     SG_REF(current->data);
00131                 return current->data;
00132             }
00133             else
00134                 return NULL;
00135         }
00136 
00141         inline T get_previous_element()
00142         {
00143             if ((current != NULL) && (current->prev != NULL))
00144             {
00145                 current = current->prev;
00146                 if (delete_data)
00147                     SG_REF(current->data);
00148                 return current->data;
00149             }
00150             else
00151                 return NULL;
00152         }
00153 
00158         inline T get_current_element()
00159         {
00160             if (current != NULL)
00161             {
00162                 if (delete_data)
00163                     SG_REF(current->data);
00164                 return current->data;
00165             }
00166             else 
00167                 return NULL;
00168         }
00169 
00170 
00173 
00179         inline T get_first_element(CListElement<T> *&p_current)
00180         {
00181             if (first != NULL)
00182             {
00183                 p_current = first;
00184                 if (delete_data)
00185                     SG_REF(p_current->data);
00186                 return p_current->data;
00187             }
00188             else
00189                 return NULL;
00190         }
00191 
00197         inline T get_last_element(CListElement<T> *&p_current)
00198         {
00199             if (last != NULL)
00200             {
00201                 p_current = last;
00202                 if (delete_data)
00203                     SG_REF(p_current->data);
00204                 return p_current->data;
00205             }
00206             else
00207                 return NULL;
00208         }
00209 
00215         inline T get_next_element(CListElement<T> *& p_current)
00216         {
00217             if ((p_current != NULL) && (p_current->next != NULL))
00218             {
00219                 p_current = p_current->next;
00220                 if (delete_data)
00221                     SG_REF(p_current->data);
00222                 return p_current->data;
00223             }
00224             else
00225                 return NULL;
00226         }
00227 
00233         inline T get_previous_element(CListElement<T> *& p_current)
00234         {
00235             if ((p_current != NULL) && (p_current->prev != NULL))
00236             {
00237                 p_current = p_current->prev;
00238                 if (delete_data)
00239                     SG_REF(p_current->data);
00240                 return p_current->data;
00241             }
00242             else
00243                 return NULL;
00244         }
00245 
00251         inline T get_current_element(CListElement<T> *& p_current)
00252         {
00253             if (p_current != NULL)
00254             {
00255                 if (delete_data)
00256                     SG_REF(p_current->data);
00257                 return p_current->data;
00258             }
00259             else 
00260                 return NULL;
00261         }
00263 
00269         inline bool append_element(T data)
00270         {
00271             if (current != NULL)    // none available, case is shattered in insert_element()
00272             {
00273                 T e=get_next_element();
00274                 if (e)
00275                 {
00276                     if (delete_data)
00277                         SG_UNREF(e);
00278                     // if successor exists use insert_element()
00279                     return insert_element(data);
00280                 }
00281                 else
00282                 {
00283                     // case with no successor but nonempty
00284                     CListElement<T>* element;
00285 
00286                     if ((element = new CListElement<T>(data, current)) != NULL)
00287                     {
00288                         current->next = element;
00289                         current       = element;
00290                         last         = element;
00291 
00292                         num_elements++;
00293 
00294                         if (delete_data)
00295                             SG_REF(data);
00296 
00297                         return true;
00298                     }
00299                     else
00300                         return false;
00301                 }
00302             }
00303             else
00304                 return insert_element(data);
00305         }
00306 
00312         inline bool insert_element(T data)
00313         {
00314             CListElement<T>* element;
00315 
00316             if (delete_data)
00317                 SG_REF(data);
00318 
00319             if (current == NULL)
00320             {
00321                 if ((element = new CListElement<T> (data)) != NULL)
00322                 {
00323                     current = element;
00324                     first  = element;
00325                     last   = element;
00326 
00327                     num_elements++;
00328 
00329                     return true;
00330                 }
00331                 else
00332                     return false;
00333             }
00334             else
00335             {
00336                 if ((element = new CListElement<T>(data, current->prev, current)) != NULL)
00337                 {
00338                     if (current->prev != NULL)
00339                         current->prev->next = element;
00340                     else
00341                         first = element;
00342 
00343                     current->prev = element;
00344                     current       = element;
00345 
00346                     num_elements++;
00347 
00348                     return true;
00349                 }
00350                 else
00351                     return false;
00352             }
00353         }
00354 
00361         inline T delete_element(void)
00362         {
00363             T data = get_current_element();
00364 
00365             if (data)
00366             {
00367                 if (delete_data)
00368                     SG_UNREF(data);
00369 
00370                 CListElement<T> *element = current;
00371 
00372                 if (element->prev)
00373                     element->prev->next = element->next;
00374 
00375                 if (element->next)
00376                     element->next->prev = element->prev;
00377 
00378                 if (element->next)
00379                     current = element->next;
00380                 else
00381                     current = element->prev;
00382 
00383                 if (element == first)
00384                     first = element->next;
00385 
00386                 if (element == last)
00387                     last  = element->prev;
00388 
00389                 delete element;
00390 
00391                 num_elements--;
00392 
00393                 return data;
00394             } 
00395 
00396             return NULL;
00397         }
00398 
00400         inline virtual const char* get_name() const { return "List"; }
00401 
00402     private:
00404         bool delete_data;
00406         CListElement<T>* first;
00408         CListElement<T>* current;
00410         CListElement<T>* last;
00412         int32_t num_elements;
00413 };
00414 #endif

SHOGUN Machine Learning Toolbox - Documentation