00001 00002 00003 00004 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;
00117 const int TVALIST_DEFAULT_GROWTH_INCREMENT = 4;
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;
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;
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++)
00274 m_Array[x]=l.m_Array[x];
00275 }else{
00276 m_Array=0;
00277 m_ArraySize=0;
00278 }
00279 }
00280 return *this;
00281 }
00282
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;
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;
00299 else{
00300 if(m_ArraySize==0)
00301 m_ArraySize = 1;
00302 else
00303 m_ArraySize *= 2;
00304 }
00305
00306 T * new_array=new T[m_ArraySize];
00307 if(m_Array){
00308 for (USize x=0;x<m_Entries;x++)
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++)
00324 new_array[x]=m_Array[x];
00325 delete [] m_Array;
00326 }
00327 m_Array=new_array;
00328 }
00329 }
00330
00331 #endif