00001 00002 00003 00004 00005 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 TVALIST_DEFAULT_SIZE = 0;
00118 const int TVALIST_DEFAULT_GROWTH_INCREMENT = 4;
00119
00120 #ifdef __gnuc__
00121 #define TVALIST_PRE template <class T>
00122 #else
00123 #define TVALIST_PRE template <class T>
00124 #endif
00125
00126
00127
00128 TVALIST_PRE inline skTVAList<T>::skTVAList()
00129
00130 :m_ArraySize(TVALIST_DEFAULT_SIZE),m_GrowthIncrement(TVALIST_DEFAULT_GROWTH_INCREMENT),m_Entries(0)
00131 {
00132 if(TVALIST_DEFAULT_SIZE != 0)
00133 m_Array=new T[TVALIST_DEFAULT_SIZE];
00134 else
00135 m_Array = 0;
00136 }
00137
00138 TVALIST_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;
00146 }
00147
00148 TVALIST_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 TVALIST_PRE inline skTVAList<T>::~skTVAList()
00161
00162 {
00163 if(m_Array)
00164 delete [] m_Array;
00165 }
00166
00167 TVALIST_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 TVALIST_PRE inline USize skTVAList<T>::entries() const
00178
00179 {
00180 return m_Entries;
00181 }
00182
00183 TVALIST_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__);
00189 for (USize x=n;x<m_Entries-1;x++)
00190 m_Array[x]=m_Array[x+1];
00191 m_Entries--;
00192 }
00193
00194 TVALIST_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__);
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 TVALIST_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 TVALIST_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 TVALIST_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 TVALIST_PRE inline T& skTVAList<T>::operator[](USize n) const
00244
00245 {
00246 assert(n<m_Entries);
00247 if (n>=m_Entries)
00248 throw skBoundsException("Invalid index to []",__FILE__,__LINE__);
00249 return m_Array[n];
00250 }
00251
00252 TVALIST_PRE inline int skTVAList<T>::index(const T &t) const
00253
00254 {
00255 return (USize)findElt(t);
00256 }
00257
00258 TVALIST_PRE inline bool skTVAList<T>::contains(const T &t) const
00259
00260 {
00261 return (bool)(findElt(t) >= 0);
00262 }
00263
00264 TVALIST_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++)
00275 m_Array[x]=l.m_Array[x];
00276 }else{
00277 m_Array=0;
00278 m_ArraySize=0;
00279 }
00280 }
00281 return *this;
00282 }
00283
00284
00285 TVALIST_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;
00291 }
00292 return -1;
00293 }
00294
00295 TVALIST_PRE void skTVAList<T>::grow()
00296
00297 {
00298 if(m_GrowthIncrement != 0)
00299 m_ArraySize += m_GrowthIncrement;
00300 else{
00301 if(m_ArraySize==0)
00302 m_ArraySize = 1;
00303 else
00304 m_ArraySize *= 2;
00305 }
00306
00307 T * new_array=new T[m_ArraySize];
00308 if(m_Array){
00309 for (USize x=0;x<m_Entries;x++)
00310 new_array[x]=m_Array[x];
00311 delete [] m_Array;
00312 }
00313 m_Array=new_array;
00314 }
00315
00316 TVALIST_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++)
00325 new_array[x]=m_Array[x];
00326 delete [] m_Array;
00327 }
00328 m_Array=new_array;
00329 }
00330 }
00331
00332 #endif