00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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;
00132 const int skTVALIST_DEFAULT_GROWTH_INCREMENT = 4;
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;
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;
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++)
00301 m_Array[x]=l.m_Array[x];
00302 }else{
00303 m_Array=0;
00304 m_ArraySize=0;
00305 }
00306 }
00307 return *this;
00308 }
00309
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;
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;
00326 else{
00327 if(m_ArraySize==0)
00328 m_ArraySize = 1;
00329 else
00330 m_ArraySize *= 2;
00331 }
00332
00333 T * new_array=new T[m_ArraySize];
00334 if(m_Array){
00335 for (USize x=0;x<m_Entries;x++)
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++)
00351 new_array[x]=m_Array[x];
00352 delete [] m_Array;
00353 }
00354 m_Array=new_array;
00355 }
00356 }
00357
00358 #endif