Main Page   Class Hierarchy   Compound List   File List   Compound Members  

skValist.h

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

Generated at Mon Mar 5 16:00:30 2001 for Simkin by doxygen1.2.0 written by Dimitri van Heesch, © 1997-2000