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

skValist.h

00001 /*
00002   Copyright 1996-2003
00003   Simon Whiteside
00004 
00005     This library is free software; you can redistribute it and/or
00006     modify it under the terms of the GNU Lesser 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     Lesser General Public License for more details.
00014 
00015     You should have received a copy of the GNU Lesser General Public
00016     License along with this library; if not, write to the Free Software
00017     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00018 
00019 * $Id: skValist_8h-source.html,v 1.5 2003/01/23 15:31:03 simkin_cvs Exp $
00020 */
00021 
00022 #ifndef skVALIST_H
00023 #define skVALIST_H
00024 
00025 
00026 #include "skGeneral.h"
00027 #include "skBoundsException.h"
00028     
00032 template <class T> class skTVAList 
00033 {         
00034  public:
00038   skTVAList();
00042   skTVAList(const skTVAList<T>&);
00046   skTVAList(USize initial_size,USize growth_increment);
00050   virtual ~skTVAList();                                 
00054   skTVAList& operator=(const skTVAList<T>&);
00058   void  clear();                                        
00062   USize entries() const;
00067   void  deleteElt(USize  n);
00071   void  prepend(const T &t);
00076   void  insert(const T &t,USize index);
00080   void  append(const T &t);
00084   void  remove(const T &t);     
00090   T& operator[](USize  n) const;
00095   int index(const T &t) const;
00100   bool  contains(const T &t) const;
00104   void  growTo(USize new_size);
00105  protected:
00109   int   findElt(const T &t) const;
00113   void  grow();
00117   T*  m_Array;  
00121   USize m_ArraySize;
00125   USize m_Entries;
00129   USize m_GrowthIncrement;
00130 };        
00131 const int skTVALIST_DEFAULT_SIZE = 0;                                   // so array not allocated until needed
00132 const int skTVALIST_DEFAULT_GROWTH_INCREMENT = 4;       // value of 0 means 'double in size'
00133 
00134 #ifdef __gnuc__
00135 #define skTVALIST_PRE template <class T> 
00136 #else
00137 #define skTVALIST_PRE template <class T> 
00138 #endif
00139 
00140 
00141 //-----------------------------------------------------------------
00142 skTVALIST_PRE inline skTVAList<T>::skTVAList()
00143      //-----------------------------------------------------------------
00144   :m_ArraySize(skTVALIST_DEFAULT_SIZE),m_GrowthIncrement(skTVALIST_DEFAULT_GROWTH_INCREMENT),m_Entries(0)
00145 {
00146   if(skTVALIST_DEFAULT_SIZE != 0)
00147     m_Array=new T[skTVALIST_DEFAULT_SIZE];
00148   else
00149     m_Array = 0;                // don't allocate space until needed
00150 }
00151 //-----------------------------------------------------------------
00152 skTVALIST_PRE inline skTVAList<T>::skTVAList(USize initial_size,USize growth_increment)
00153      //-----------------------------------------------------------------
00154   :m_ArraySize(initial_size),m_GrowthIncrement(growth_increment),m_Entries(0)
00155 {
00156   if(m_ArraySize != 0)
00157     m_Array=new T[m_ArraySize];
00158   else
00159     m_Array = 0;                // don't allocate space until needed
00160 }
00161 //-----------------------------------------------------------------
00162 skTVALIST_PRE inline skTVAList<T>::skTVAList(const skTVAList& l)
00163      //-----------------------------------------------------------------
00164   : m_ArraySize(l.m_ArraySize),m_Entries(l.m_Entries),m_GrowthIncrement(l.m_GrowthIncrement)
00165 {
00166   if(m_ArraySize){
00167     m_Array=new T[m_ArraySize];
00168     for (USize x=0;x<m_Entries;x++)
00169       m_Array[x]=l.m_Array[x];
00170   }else
00171     m_Array = 0;
00172 }
00173 //-----------------------------------------------------------------
00174 skTVALIST_PRE inline skTVAList<T>::~skTVAList()
00175      //-----------------------------------------------------------------
00176 {
00177   if(m_Array)
00178     delete [] m_Array;
00179 }
00180 //-----------------------------------------------------------------
00181 skTVALIST_PRE inline void skTVAList<T>::clear()
00182      //-----------------------------------------------------------------
00183 {
00184   m_Entries=0;
00185   if(m_Array)
00186     delete [] m_Array;
00187   m_Array=0;
00188   m_ArraySize=0;
00189 }
00190 //-----------------------------------------------------------------
00191 skTVALIST_PRE inline USize skTVAList<T>::entries() const
00192      //-----------------------------------------------------------------
00193 {
00194   return m_Entries;
00195 }
00196 //-----------------------------------------------------------------
00197 skTVALIST_PRE void skTVAList<T>::deleteElt(USize  n)
00198      //-----------------------------------------------------------------
00199 {
00200   assert(n<m_Entries);
00201   if (n>=m_Entries)
00202 #ifdef EXCEPTIONS_DEFINED
00203     throw skBoundsException("Invalid index to DeleteElt",__FILE__,__LINE__);
00204 #else
00205     exit(EXIT_FAILURE);
00206 #endif
00207   for (USize x=n;x<m_Entries-1;x++)
00208     m_Array[x]=m_Array[x+1];
00209   m_Entries--;
00210 }
00211 //-----------------------------------------------------------------
00212 skTVALIST_PRE void skTVAList<T>::insert(const T &t,USize index)
00213      //-----------------------------------------------------------------
00214 {
00215   assert(index<=m_Entries);
00216   if (index>m_Entries)
00217 #ifdef EXCEPTIONS_DEFINED
00218     throw skBoundsException("Invalid index to Insert",__FILE__,__LINE__);
00219 #else
00220     exit(EXIT_FAILURE);
00221 #endif
00222   if (m_ArraySize==m_Entries)
00223     grow();
00224   if (index<m_Entries){
00225     for (USize x=m_Entries;x>index;x--)
00226       m_Array[x]=m_Array[x-1];
00227   }
00228   m_Array[index]=t;
00229   m_Entries++;
00230 }
00231 //-----------------------------------------------------------------
00232 skTVALIST_PRE void skTVAList<T>::prepend(const T &t)
00233      //-----------------------------------------------------------------
00234 {
00235   if (m_ArraySize==m_Entries)
00236     grow();
00237   m_Entries++;
00238   for (USize x=m_Entries-1;x>=1;x--)
00239     m_Array[x]=m_Array[x-1];
00240   m_Array[0]=t;
00241 }
00242 //-----------------------------------------------------------------
00243 skTVALIST_PRE inline void skTVAList<T>::append(const T &t)
00244      //-----------------------------------------------------------------
00245 {
00246   if (m_ArraySize==m_Entries)
00247     grow();
00248   m_Array[m_Entries]=t;
00249   m_Entries++;
00250 }
00251 //-----------------------------------------------------------------
00252 skTVALIST_PRE void skTVAList<T>::remove(const T &t)
00253      //-----------------------------------------------------------------
00254 {
00255   int index = findElt(t);
00256   assert(index>=0 && "VAList does not contain item"!=0);
00257   if (index>=0){
00258     for (USize x=(USize)index;x<m_Entries-1;x++)
00259       m_Array[x]=m_Array[x+1];
00260 
00261     m_Entries--;
00262   }
00263 }
00264 //-----------------------------------------------------------------
00265 skTVALIST_PRE inline T& skTVAList<T>::operator[](USize  n) const
00266      //-----------------------------------------------------------------
00267 {
00268   assert(n<m_Entries);
00269   if (n>=m_Entries)
00270 #ifdef EXCEPTIONS_DEFINED
00271     throw skBoundsException(skSTR("Invalid index to []"),__FILE__,__LINE__);
00272 #else
00273     exit(EXIT_FAILURE);
00274 #endif
00275   return m_Array[n];
00276 }
00277 //-----------------------------------------------------------------
00278 skTVALIST_PRE inline int skTVAList<T>::index(const T &t) const
00279      //-----------------------------------------------------------------
00280 {
00281   return (USize)findElt(t);
00282 }
00283 //-----------------------------------------------------------------
00284 skTVALIST_PRE inline bool skTVAList<T>::contains(const T &t) const
00285      //-----------------------------------------------------------------
00286 {
00287   return (bool)(findElt(t) >= 0);
00288 }
00289 //-----------------------------------------------------------------
00290 skTVALIST_PRE skTVAList<T>& skTVAList<T>::operator=(const skTVAList<T>& l)
00291      //-----------------------------------------------------------------
00292 {
00293   if (&l!=this){
00294     clear();
00295     m_ArraySize=l.m_ArraySize;
00296     m_Entries=l.m_Entries;
00297     m_GrowthIncrement=l.m_GrowthIncrement;
00298     if(m_Entries){
00299       m_Array=new T[m_ArraySize];
00300       for (USize x=0;x<m_Entries;x++)           //??use memcopy for speed
00301         m_Array[x]=l.m_Array[x];
00302     }else{
00303       m_Array=0;        // don't allocate until needed
00304       m_ArraySize=0;
00305     }
00306   }
00307   return *this;
00308 }
00309 // Returns -1 if not found.
00310 //-----------------------------------------------------------------
00311 skTVALIST_PRE inline int skTVAList<T>::findElt(const T &t) const
00312      //-----------------------------------------------------------------
00313 {
00314   for (USize index=0;index<m_Entries;index++){
00315     if (m_Array[index]==t)
00316       return (int)index;                // jump out
00317   }
00318   return -1;
00319 }
00320 //-----------------------------------------------------------------
00321 skTVALIST_PRE void skTVAList<T>::grow()
00322      //-----------------------------------------------------------------
00323 {
00324   if(m_GrowthIncrement != 0)
00325     m_ArraySize += m_GrowthIncrement;   // constant increase in size
00326   else{
00327     if(m_ArraySize==0)
00328       m_ArraySize = 1;
00329     else
00330       m_ArraySize *= 2;                 // double size
00331   }
00332 
00333   T *  new_array=new T[m_ArraySize];
00334   if(m_Array){
00335     for (USize x=0;x<m_Entries;x++)             //??use memcopy for speed
00336       new_array[x]=m_Array[x];
00337     delete [] m_Array;
00338   }
00339   m_Array=new_array;
00340 }
00341 //-----------------------------------------------------------------
00342 skTVALIST_PRE void skTVAList<T>::growTo(USize new_size)
00343      //-----------------------------------------------------------------
00344 {
00345   if (new_size>m_ArraySize){
00346     m_ArraySize=new_size;
00347 
00348     T *  new_array=new T[m_ArraySize];
00349     if(m_Array){
00350       for (USize x=0;x<m_Entries;x++)           //??use memcopy for speed
00351         new_array[x]=m_Array[x];
00352       delete [] m_Array;
00353     }
00354     m_Array=new_array;
00355   }
00356 }
00357 
00358 #endif

Generated on Thu Jan 23 15:25:39 2003 for Simkin by doxygen1.3-rc1