Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

skValist.h

00001 /*
00002   Copyright 1996-2001
00003   Simon Whiteside
00004 
00005 * $Id: skValist_h-source.html,v 1.19 2001/11/05 19:22:33 sdw Exp $
00006 */
00007 
00008 #ifndef skVALIST_H
00009 #define skVALIST_H
00010 
00011 
00012 #include "skGeneral.h"
00013 #include "skBoundsException.h"
00014     
00018 template <class T> class skTVAList 
00019 {         
00020  public:
00024   skTVAList();
00028   skTVAList(const skTVAList<T>&);
00032   skTVAList(USize initial_size,USize growth_increment);
00036   virtual ~skTVAList();                                 
00040   skTVAList& operator=(const skTVAList<T>&);
00044   void  clear();                                        
00048   USize entries() const;
00053   void  deleteElt(USize  n);
00057   void  prepend(const T &t);
00062   void  insert(const T &t,USize index);
00066   void  append(const T &t);
00070   void  remove(const T &t);     
00076   T& operator[](USize  n) const;
00081   int index(const T &t) const;
00086   bool  contains(const T &t) const;
00090   void  growTo(USize new_size);
00091  protected:
00095   int   findElt(const T &t) const;
00099   void  grow();
00103   T*  m_Array;  
00107   USize m_ArraySize;
00111   USize m_Entries;
00115   USize m_GrowthIncrement;
00116 };        
00117 const int skTVALIST_DEFAULT_SIZE = 0;                                   // so array not allocated until needed
00118 const int skTVALIST_DEFAULT_GROWTH_INCREMENT = 4;       // value of 0 means 'double in size'
00119 
00120 #ifdef __gnuc__
00121 #define skTVALIST_PRE template <class T> 
00122 #else
00123 #define skTVALIST_PRE template <class T> 
00124 #endif
00125 
00126 
00127 //-----------------------------------------------------------------
00128 skTVALIST_PRE inline skTVAList<T>::skTVAList()
00129      //-----------------------------------------------------------------
00130   :m_ArraySize(skTVALIST_DEFAULT_SIZE),m_GrowthIncrement(skTVALIST_DEFAULT_GROWTH_INCREMENT),m_Entries(0)
00131 {
00132   if(skTVALIST_DEFAULT_SIZE != 0)
00133     m_Array=new T[skTVALIST_DEFAULT_SIZE];
00134   else
00135     m_Array = 0;                // don't allocate space until needed
00136 }
00137 //-----------------------------------------------------------------
00138 skTVALIST_PRE inline skTVAList<T>::skTVAList(USize initial_size,USize growth_increment)
00139      //-----------------------------------------------------------------
00140   :m_ArraySize(initial_size),m_GrowthIncrement(growth_increment),m_Entries(0)
00141 {
00142   if(m_ArraySize != 0)
00143     m_Array=new T[m_ArraySize];
00144   else
00145     m_Array = 0;                // don't allocate space until needed
00146 }
00147 //-----------------------------------------------------------------
00148 skTVALIST_PRE inline skTVAList<T>::skTVAList(const skTVAList& l)
00149      //-----------------------------------------------------------------
00150   : m_ArraySize(l.m_ArraySize),m_Entries(l.m_Entries),m_GrowthIncrement(l.m_GrowthIncrement)
00151 {
00152   if(m_ArraySize){
00153     m_Array=new T[m_ArraySize];
00154     for (USize x=0;x<m_Entries;x++)
00155       m_Array[x]=l.m_Array[x];
00156   }else
00157     m_Array = 0;
00158 }
00159 //-----------------------------------------------------------------
00160 skTVALIST_PRE inline skTVAList<T>::~skTVAList()
00161      //-----------------------------------------------------------------
00162 {
00163   if(m_Array)
00164     delete [] m_Array;
00165 }
00166 //-----------------------------------------------------------------
00167 skTVALIST_PRE inline void skTVAList<T>::clear()
00168      //-----------------------------------------------------------------
00169 {
00170   m_Entries=0;
00171   if(m_Array)
00172     delete [] m_Array;
00173   m_Array=0;
00174   m_ArraySize=0;
00175 }
00176 //-----------------------------------------------------------------
00177 skTVALIST_PRE inline USize skTVAList<T>::entries() const
00178      //-----------------------------------------------------------------
00179 {
00180   return m_Entries;
00181 }
00182 //-----------------------------------------------------------------
00183 skTVALIST_PRE void skTVAList<T>::deleteElt(USize  n)
00184      //-----------------------------------------------------------------
00185 {
00186   assert(n<m_Entries);
00187   if (n>=m_Entries)
00188     THROW(skBoundsException("Invalid index to DeleteElt",__FILE__,__LINE__),skBoundsException_Code);
00189   for (USize x=n;x<m_Entries-1;x++)
00190     m_Array[x]=m_Array[x+1];
00191   m_Entries--;
00192 }
00193 //-----------------------------------------------------------------
00194 skTVALIST_PRE void skTVAList<T>::insert(const T &t,USize index)
00195      //-----------------------------------------------------------------
00196 {
00197   assert(index<=m_Entries);
00198   if (index>m_Entries)
00199     THROW(skBoundsException("Invalid index to Insert",__FILE__,__LINE__),skBoundsException_Code);
00200   if (m_ArraySize==m_Entries)
00201     grow();
00202   if (index<m_Entries){
00203     for (USize x=m_Entries;x>index;x--)
00204       m_Array[x]=m_Array[x-1];
00205   }
00206   m_Array[index]=t;
00207   m_Entries++;
00208 }
00209 //-----------------------------------------------------------------
00210 skTVALIST_PRE void skTVAList<T>::prepend(const T &t)
00211      //-----------------------------------------------------------------
00212 {
00213   if (m_ArraySize==m_Entries)
00214     grow();
00215   m_Entries++;
00216   for (USize x=m_Entries-1;x>=1;x--)
00217     m_Array[x]=m_Array[x-1];
00218   m_Array[0]=t;
00219 }
00220 //-----------------------------------------------------------------
00221 skTVALIST_PRE inline void skTVAList<T>::append(const T &t)
00222      //-----------------------------------------------------------------
00223 {
00224   if (m_ArraySize==m_Entries)
00225     grow();
00226   m_Array[m_Entries]=t;
00227   m_Entries++;
00228 }
00229 //-----------------------------------------------------------------
00230 skTVALIST_PRE void skTVAList<T>::remove(const T &t)
00231      //-----------------------------------------------------------------
00232 {
00233   int index = findElt(t);
00234   assert(index>=0 && "VAList does not contain item"!=0);
00235   if (index>=0){
00236     for (USize x=(USize)index;x<m_Entries-1;x++)
00237       m_Array[x]=m_Array[x+1];
00238 
00239     m_Entries--;
00240   }
00241 }
00242 //-----------------------------------------------------------------
00243 skTVALIST_PRE inline T& skTVAList<T>::operator[](USize  n) const
00244      //-----------------------------------------------------------------
00245 {
00246   assert(n<m_Entries);
00247   if (n>=m_Entries)
00248     THROW(skBoundsException(skSTR("Invalid index to []"),__FILE__,__LINE__),skBoundsException_Code);
00249   return m_Array[n];
00250 }
00251 //-----------------------------------------------------------------
00252 skTVALIST_PRE inline int skTVAList<T>::index(const T &t) const
00253      //-----------------------------------------------------------------
00254 {
00255   return (USize)findElt(t);
00256 }
00257 //-----------------------------------------------------------------
00258 skTVALIST_PRE inline bool skTVAList<T>::contains(const T &t) const
00259      //-----------------------------------------------------------------
00260 {
00261   return (bool)(findElt(t) >= 0);
00262 }
00263 //-----------------------------------------------------------------
00264 skTVALIST_PRE skTVAList<T>& skTVAList<T>::operator=(const skTVAList<T>& l)
00265      //-----------------------------------------------------------------
00266 {
00267   if (&l!=this){
00268     clear();
00269     m_ArraySize=l.m_ArraySize;
00270     m_Entries=l.m_Entries;
00271     m_GrowthIncrement=l.m_GrowthIncrement;
00272     if(m_Entries){
00273       m_Array=new T[m_ArraySize];
00274       for (USize x=0;x<m_Entries;x++)           //??use memcopy for speed
00275         m_Array[x]=l.m_Array[x];
00276     }else{
00277       m_Array=0;        // don't allocate until needed
00278       m_ArraySize=0;
00279     }
00280   }
00281   return *this;
00282 }
00283 // Returns -1 if not found.
00284 //-----------------------------------------------------------------
00285 skTVALIST_PRE inline int skTVAList<T>::findElt(const T &t) const
00286      //-----------------------------------------------------------------
00287 {
00288   for (USize index=0;index<m_Entries;index++){
00289     if (m_Array[index]==t)
00290       return (int)index;                // jump out
00291   }
00292   return -1;
00293 }
00294 //-----------------------------------------------------------------
00295 skTVALIST_PRE void skTVAList<T>::grow()
00296      //-----------------------------------------------------------------
00297 {
00298   if(m_GrowthIncrement != 0)
00299     m_ArraySize += m_GrowthIncrement;   // constant increase in size
00300   else{
00301     if(m_ArraySize==0)
00302       m_ArraySize = 1;
00303     else
00304       m_ArraySize *= 2;                 // double size
00305   }
00306 
00307   T *  new_array=new T[m_ArraySize];
00308   if(m_Array){
00309     for (USize x=0;x<m_Entries;x++)             //??use memcopy for speed
00310       new_array[x]=m_Array[x];
00311     delete [] m_Array;
00312   }
00313   m_Array=new_array;
00314 }
00315 //-----------------------------------------------------------------
00316 skTVALIST_PRE void skTVAList<T>::growTo(USize new_size)
00317      //-----------------------------------------------------------------
00318 {
00319   if (new_size>m_ArraySize){
00320     m_ArraySize=new_size;
00321 
00322     T *  new_array=new T[m_ArraySize];
00323     if(m_Array){
00324       for (USize x=0;x<m_Entries;x++)           //??use memcopy for speed
00325         new_array[x]=m_Array[x];
00326       delete [] m_Array;
00327     }
00328     m_Array=new_array;
00329   }
00330 }
00331 
00332 #endif

Generated at Mon Nov 5 19:22:25 2001 for Simkin by doxygen1.2.1 written by Dimitri van Heesch, © 1997-2000