linklist.h Source File

00001 /*
00002     Dynamics/Kinematics modeling and simulation library.
00003     Copyright (C) 1999 by Michael Alexander Ewert
00004 
00005     This library is free software; you can redistribute it and/or
00006     modify it under the terms of the GNU Library General Public
00007     License as published by the Free Software Foundation; either
00008     version 2 of the License, or (at your option) any later version.
00009 
00010     This library is distributed in the hope that it will be useful,
00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013     Library General Public License for more details.
00014 
00015     You should have received a copy of the GNU Library General Public
00016     License along with this library; if not, write to the Free
00017     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 
00019 */
00020 
00021 #ifndef __CT_LINKLIST_H__
00022 #define __CT_LINKLIST_H__
00023 
00024 #include <stdlib.h>
00025 
00026 template <class T>
00027 class llLink
00028 {
00029 public:
00030   T* contents;
00031   llLink<T>* next;
00032 
00033   llLink ()
00034   { contents = 0; next = 0; }
00035 
00036   llLink ( T* c )
00037   { contents = c; next = 0; }
00038 
00039   llLink ( T* c, llLink<T>* n )
00040   { contents = c; next = n; }
00041 
00042   ~llLink(){}
00043 
00044   void delete_contents ()
00045   { delete contents; }
00046 };
00047 
00053 template <class T>
00054 class ctLinkList
00055 {
00056 protected:
00057   llLink<T>* head;
00058   llLink<T>* prev;  // cached the last link accessed
00059   llLink<T>* current;  // cached the last link accessed
00060   long size;
00061 
00062 public:
00064   void reset()
00065   { prev = 0; current = head; }
00066 
00068   T* get_first()
00069   {  if ( head->next != 0 )
00070      {
00071        prev = head;
00072        current = head->next;
00073        return head->next->contents;
00074      }
00075      else return 0;
00076   }
00077 
00079   T* get_next()
00080   {
00081     if ( current->next )
00082     {
00083       prev = current;
00084       current = current->next;
00085       return current->contents;
00086     }
00087     else return 0;
00088   }
00089 
00091   T* peek_first()
00092   {  return head->next->contents; }
00093 
00095   void add_link ( T* c )
00096   {
00097     head->next = new llLink<T>( c, head->next );
00098     current = head->next;
00099     prev = head;
00100     size++;
00101   }
00102 
00104   void push( T* c )
00105   {
00106     head->next = new llLink<T>( c, head->next );
00107     current = head->next;
00108     prev = head;
00109     size++;
00110   }
00111 
00113   T* pop ()
00114   {
00115     T* ret = head->next->contents;
00116     prev = head;
00117     current = head->next;
00118     head->next = current->next;
00119     delete current;
00120     current = head->next;
00121     size--;
00122     return ret;
00123   }
00124 
00126   void delete_link ( T* c )
00127   {
00128     if ( c == 0 ) return;
00129     if ( prev && prev->next && c == prev->next->contents )
00130     {
00131       current = prev->next->next;
00132       delete prev->next;
00133       size--;
00134       prev->next = current;
00135     }
00136     else
00137     {
00138       llLink<T>* ll = head;
00139       while ( ll->next )
00140       {
00141         if ( ll->next->contents == c )
00142         {
00143           prev = ll;
00144           current = ll->next->next;
00145           ll->next->delete_contents();
00146           delete ll->next;
00147           size--;
00148           prev->next = current;
00149           return;
00150         }
00151         ll = ll->next;
00152       }
00153     }
00154   }
00155 
00157   void remove_link ( T* c )
00158   {
00159     if ( c == 0 ) return;
00160     if ( prev && prev->next && c == prev->next->contents )
00161     {
00162       current = prev->next->next;
00163       delete prev->next;
00164       size--;
00165       prev->next = current;
00166     }
00167     else
00168     {
00169       llLink<T> *ll = head;
00170       while ( ll->next )
00171       {
00172         if( ll->next->contents == c ){
00173           prev = ll;
00174           current = ll->next->next;
00175           delete ll->next;
00176           size--;
00177           prev->next = current;
00178           return;
00179         }
00180         ll = ll->next;
00181       }
00182     }
00183   }
00184 
00186   void remove_all ()
00187   {
00188     if ( head == 0 )
00189       return;
00190     prev = head->next;
00191     while ( prev )
00192     {
00193       current = prev->next;
00194       delete prev;
00195       prev = current;
00196     }
00197     size = 0;
00198     head->next = prev = 0;
00199     current = head;
00200   }
00201 
00203   void delete_all ()
00204   {
00205     if ( head == 0 )
00206       return;
00207     prev = head->next;
00208     while ( prev )
00209     {
00210       current = prev->next;
00211       prev->delete_contents ();
00212       delete prev;
00213       prev = current;
00214     }
00215     size = 0;
00216     head->next = prev = 0;
00217     current = head;
00218   }
00219 
00221   long get_size ()
00222   { return size; }
00223 
00225   ctLinkList ()
00226   { size = 0; head = new llLink<T>(); prev = 0; current = head; }
00227 
00229   ~ctLinkList()
00230   {  remove_all(); delete head; }
00231 };
00232 
00233 #endif // __CT_LINKLIST_H__