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 
00018 namespace shogun
00019 {
00021 template <class T> class CListElement
00022 {
00023     public:
00025         CListElement* next;
00027         CListElement* prev;
00029         T data;
00030 
00031     public:
00038         CListElement(T p_data, CListElement* p_prev = NULL, CListElement* p_next = NULL)
00039         {
00040             this->data = p_data;
00041             this->next = p_next;
00042             this->prev = p_prev;
00043         };
00044 
00046         virtual ~CListElement() { data = NULL; }
00047 };
00048 
00054 template <class T> class CList : public CSGObject
00055 {
00056     public:
00061         CList(bool p_delete_data=false) : CSGObject()
00062         {
00063             first  = NULL;
00064             current = NULL;
00065             last   = NULL;
00066 
00067             num_elements = 0;
00068             this->delete_data=p_delete_data;
00069         }
00070 
00071         virtual ~CList()
00072         {
00073             SG_DEBUG("Destroying List %p\n", this);
00074 
00075             while (get_num_elements())
00076             {
00077                 T d=delete_element();
00078 
00079                 if (delete_data)
00080                 {
00081                     SG_DEBUG("Destroying List Element %p\n", d);
00082                     SG_UNREF(d);
00083                 }
00084             }
00085         }
00086 
00091         inline int32_t get_num_elements() { return num_elements; }
00092 
00097         inline T get_first_element()
00098         {
00099             if (first != NULL)
00100             {
00101                 current = first;
00102                 if (delete_data)
00103                     SG_REF(current->data);
00104                 return current->data;
00105             }
00106             else 
00107                 return NULL;
00108         }
00109 
00114         inline T get_last_element()
00115         {
00116             if (last != NULL)
00117             {
00118                 current = last;
00119                 if (delete_data)
00120                     SG_REF(current->data);
00121                 return current->data;
00122             }
00123             else 
00124                 return NULL;
00125         }
00126 
00131         inline T get_next_element()
00132         {
00133             if ((current != NULL) && (current->next != NULL))
00134             {
00135                 current = current->next;
00136                 if (delete_data)
00137                     SG_REF(current->data);
00138                 return current->data;
00139             }
00140             else
00141                 return NULL;
00142         }
00143 
00148         inline T get_previous_element()
00149         {
00150             if ((current != NULL) && (current->prev != NULL))
00151             {
00152                 current = current->prev;
00153                 if (delete_data)
00154                     SG_REF(current->data);
00155                 return current->data;
00156             }
00157             else
00158                 return NULL;
00159         }
00160 
00165         inline T get_current_element()
00166         {
00167             if (current != NULL)
00168             {
00169                 if (delete_data)
00170                     SG_REF(current->data);
00171                 return current->data;
00172             }
00173             else 
00174                 return NULL;
00175         }
00176 
00177 
00180 
00186         inline T get_first_element(CListElement<T> *&p_current)
00187         {
00188             if (first != NULL)
00189             {
00190                 p_current = first;
00191                 if (delete_data)
00192                     SG_REF(p_current->data);
00193                 return p_current->data;
00194             }
00195             else
00196                 return NULL;
00197         }
00198 
00204         inline T get_last_element(CListElement<T> *&p_current)
00205         {
00206             if (last != NULL)
00207             {
00208                 p_current = last;
00209                 if (delete_data)
00210                     SG_REF(p_current->data);
00211                 return p_current->data;
00212             }
00213             else
00214                 return NULL;
00215         }
00216 
00222         inline T get_next_element(CListElement<T> *& p_current)
00223         {
00224             if ((p_current != NULL) && (p_current->next != NULL))
00225             {
00226                 p_current = p_current->next;
00227                 if (delete_data)
00228                     SG_REF(p_current->data);
00229                 return p_current->data;
00230             }
00231             else
00232                 return NULL;
00233         }
00234 
00240         inline T get_previous_element(CListElement<T> *& p_current)
00241         {
00242             if ((p_current != NULL) && (p_current->prev != NULL))
00243             {
00244                 p_current = p_current->prev;
00245                 if (delete_data)
00246                     SG_REF(p_current->data);
00247                 return p_current->data;
00248             }
00249             else
00250                 return NULL;
00251         }
00252 
00258         inline T get_current_element(CListElement<T> *& p_current)
00259         {
00260             if (p_current != NULL)
00261             {
00262                 if (delete_data)
00263                     SG_REF(p_current->data);
00264                 return p_current->data;
00265             }
00266             else 
00267                 return NULL;
00268         }
00270 
00276         inline bool append_element(T data)
00277         {
00278             if (current != NULL)    // none available, case is shattered in insert_element()
00279             {
00280                 T e=get_next_element();
00281                 if (e)
00282                 {
00283                     if (delete_data)
00284                         SG_UNREF(e);
00285                     // if successor exists use insert_element()
00286                     return insert_element(data);
00287                 }
00288                 else
00289                 {
00290                     // case with no successor but nonempty
00291                     CListElement<T>* element;
00292 
00293                     if ((element = new CListElement<T>(data, current)) != NULL)
00294                     {
00295                         current->next = element;
00296                         current       = element;
00297                         last         = element;
00298 
00299                         num_elements++;
00300 
00301                         if (delete_data)
00302                             SG_REF(data);
00303 
00304                         return true;
00305                     }
00306                     else
00307                         return false;
00308                 }
00309             }
00310             else
00311                 return insert_element(data);
00312         }
00313 
00319         inline bool append_element_at_listend(T data)
00320         {
00321             T p = get_last_element();
00322             if (delete_data)
00323                 SG_UNREF(p);
00324 
00325             return append_element(data);
00326         }
00327 
00333         inline bool insert_element(T data)
00334         {
00335             CListElement<T>* element;
00336 
00337             if (delete_data)
00338                 SG_REF(data);
00339 
00340             if (current == NULL)
00341             {
00342                 if ((element = new CListElement<T> (data)) != NULL)
00343                 {
00344                     current = element;
00345                     first  = element;
00346                     last   = element;
00347 
00348                     num_elements++;
00349 
00350                     return true;
00351                 }
00352                 else
00353                     return false;
00354             }
00355             else
00356             {
00357                 if ((element = new CListElement<T>(data, current->prev, current)) != NULL)
00358                 {
00359                     if (current->prev != NULL)
00360                         current->prev->next = element;
00361                     else
00362                         first = element;
00363 
00364                     current->prev = element;
00365                     current       = element;
00366 
00367                     num_elements++;
00368 
00369                     return true;
00370                 }
00371                 else
00372                     return false;
00373             }
00374         }
00375 
00382         inline T delete_element(void)
00383         {
00384             T data = get_current_element();
00385 
00386             if (data)
00387             {
00388                 if (delete_data)
00389                     SG_UNREF(data);
00390 
00391                 CListElement<T> *element = current;
00392 
00393                 if (element->prev)
00394                     element->prev->next = element->next;
00395 
00396                 if (element->next)
00397                     element->next->prev = element->prev;
00398 
00399                 if (element->next)
00400                     current = element->next;
00401                 else
00402                     current = element->prev;
00403 
00404                 if (element == first)
00405                     first = element->next;
00406 
00407                 if (element == last)
00408                     last  = element->prev;
00409 
00410                 delete element;
00411 
00412                 num_elements--;
00413 
00414                 return data;
00415             } 
00416 
00417             return NULL;
00418         }
00419 
00421         inline virtual const char* get_name() const { return "List"; }
00422 
00423     private:
00425         bool delete_data;
00427         CListElement<T>* first;
00429         CListElement<T>* current;
00431         CListElement<T>* last;
00433         int32_t num_elements;
00434 };
00435 }
00436 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation