00001
00002
00003 #include "IntArrayList.h"
00004
00005 DSS_NAMESPASE_BEGIN
00006
00007 IntArrayList::IntArrayList()
00008 {
00009 Items = new long[Capacity = 16];
00010 Count = 0;
00011 }
00012
00013
00014 IntArrayList::IntArrayList(long capacity)
00015 {
00016 Items = new long[Capacity = capacity];
00017 Count = 0;
00018 }
00019
00020 IntArrayList::IntArrayList(long n,long* data)
00021 {
00022 Items = new long[n];
00023 Array::Copy(data,Items,n);
00024 Capacity = Count = n;
00025 }
00026
00027
00028
00029
00030
00031
00032
00033 IntArrayList::IntArrayList(const IntArrayList& al)
00034 {
00035 Items = new long[al.Count];
00036 Array::Copy(al.Items,0,Items,0,al.Count);
00037 Capacity = Count = al.Count;
00038 }
00039
00040 IntArrayList::~IntArrayList()
00041 {
00042 if (Items) delete [] Items;
00043 Items = NULL;
00044 }
00045
00046 long IntArrayList::Add(long a)
00047 {
00048 long cn = Count;
00049 if (Capacity<=cn)
00050 {
00051 long* old_items = Items;
00052 Capacity *= 2;
00053 if (Capacity<4) Capacity = 4;
00054 Items = new long[Capacity];
00055 Array::Copy(old_items,Items,Count);
00056 if (old_items) delete [] old_items;
00057 }
00058 Items[Count++]=a;
00059 return cn;
00060 }
00061
00062 void IntArrayList::AddRange(long count,long val)
00063 {
00064 long cn = Count+count;
00065 if (Capacity<cn)
00066 {
00067 long* old_items = Items;
00068 Capacity = Count+count;
00069 Items = new long[Capacity];
00070 Array::Copy(old_items,Items,Count);
00071 if (old_items) delete [] old_items;
00072 }
00073 for (long i=Count; i<Count+count; i++)
00074 Items[i]=val;
00075
00076 Count+=count;
00077 }
00078
00079 void IntArrayList::Fill(const IntArrayList& al)
00080 {
00081 if (Items) delete [] Items;
00082 Items = new long[al.Count];
00083 Array::Copy(al.Items,0,Items,0,al.Count);
00084 Capacity = Count = al.Count;
00085 }
00086
00087
00088
00089
00090 long IntArrayList::AddIfNotLast(long item)
00091 {
00092 if (Count==0 || Items[Count-1]!=item)
00093 return Add(item);
00094 return -1;
00095 }
00096
00097 void IntArrayList::Clear()
00098 {
00099 Count = 0;
00100 }
00101
00102 void IntArrayList::TrimToSize()
00103 {
00104 if (Capacity>Count)
00105 {
00106 long* old_items = Items;
00107 Capacity = Count;
00108 Items = new long[Capacity];
00109 Array::Copy(old_items,Items,Count);
00110 if (old_items) delete [] old_items;
00111 }
00112 }
00113
00114 void IntArrayList::Alloc()
00115 {
00116 Count = Capacity;
00117 Initialize();
00118 }
00119
00120 void IntArrayList::InitIdentity()
00121 {
00122 Count = Capacity;
00123 for(int i=0; i<Count; i++)
00124 Items[i] = i;
00125 }
00126
00127 void IntArrayList::Alloc(long size)
00128 {
00129 if (Capacity<size)
00130 {
00131 Count = Capacity = size;
00132 if (Items) delete [] Items;
00133 Items = new long[Capacity];
00134 Initialize();
00135 }
00136 else
00137 {
00138 Count = size;
00139 Initialize();
00140 }
00141 }
00142
00143 void IntArrayList::Initialize()
00144 {
00145 memset(Items,0,Count*sizeof(long));
00146 }
00147
00148 void IntArrayList::Initialize(long val)
00149 {
00150 for(long* p = Items+Count-1; p>=Items; p--) *p = val;
00151 }
00152
00153 void IntArrayList::SortInsert(long item)
00154 {
00155 if (Capacity<=Count)
00156 {
00157 long* old_items = Items;
00158 Capacity *= 2;
00159 if (Capacity<4) Capacity = 4;
00160 Items = new long[Capacity];
00161 Array::Copy(old_items,Items,Count);
00162 if (old_items) delete [] old_items;
00163 }
00164
00165 long*pI = this->Items;
00166 {
00167 long* ptr = pI + Count;
00168 for(;ptr>pI && ptr[-1]>item; ptr--)
00169 *ptr = ptr[-1];
00170
00171 *ptr = item;
00172 }
00173 Count++;
00174 }
00175
00176 long IntArrayList::SortInsertIfNot(long item)
00177 {
00178 long myIndex = BinarySearch(item);
00179 if (myIndex<0)
00180 {
00181 Insert(~myIndex,item);
00182 return ~myIndex;
00183 }
00184 return -1;
00185 }
00186
00187 void IntArrayList::Insert(long pos,long item)
00188 {
00189 if (pos<0 || pos>Count)
00190 return;
00191
00192 if (Capacity<=Count)
00193 {
00194 long* old_items = Items;
00195 Capacity *= 2;
00196 if (Capacity<4) Capacity = 4;
00197 Items = new long[Capacity];
00198 Array::Copy(old_items,0,Items,0,pos);
00199 Array::Copy(old_items,pos,Items,pos+1,Count-pos);
00200 if (old_items) delete [] old_items;
00201 }
00202 else
00203 {
00204
00205 for (int i=Count; i>pos; i--)
00206 Items[i] =Items[i-1];
00207 }
00208 Count++;
00209 Items[pos] = item;
00210 }
00211
00212 void IntArrayList::RemoveAt(long pos)
00213 {
00214 Count--;
00215 Array::Copy(Items,pos+1,Items,pos,Count-pos);
00216 }
00217
00218 long IntArrayList::BinarySearch(long item)
00219 {
00220 return BinarySearch(Count,item);
00221 }
00222
00223
00224 long IntArrayList::BinarySearch(long count, long item)
00225 {
00226 if (count==0)
00227 return ~0;
00228 long h = 0;
00229 long e = count-1;
00230
00231 if (item<Items[h])
00232 return ~0;
00233 if (item==Items[h])
00234 return 0;
00235 if (item>Items[e])
00236 return ~count;
00237 if (item==Items[e])
00238 return e;
00239
00240 while ((h+1)<e)
00241 {
00242 long m = (h+e)/2;
00243
00244 if (item==Items[m])
00245 return m;
00246 else if (item<Items[m])
00247 e = m;
00248 else
00249 h = m;
00250 }
00251 return ~e;
00252
00253 }
00254
00255 long* IntArrayList::ToArray()
00256 {
00257 long* arr = new long[Count];
00258 memcpy(arr,Items,Count);
00259
00260 return arr;
00261 }
00262
00263
00264
00265 long IntArrayList::SumElements()
00266 {
00267 long sum = 0;
00268 long*pI = this->Items;
00269 if (pI)
00270 for(long* p = pI+Count-1; p>=pI; p--)
00271 sum+=*p;
00272 return sum;
00273 }
00274
00275
00276
00277
00278 void IntArrayList::SetIndexesTo(long* ptr,long val)
00279 {
00280 long*pI = this->Items;
00281 if (pI)
00282 for(long* p = pI+Count-1; p>=pI; p--)
00283 ptr[*p] = val;
00284 }
00285
00286
00287
00288 void IntArrayList::SetIndexesToMap(long* ptr)
00289 {
00290 if (Items)
00291 {
00292 long*pI = Items;
00293 long idx = Count-1;
00294 for(long* p = pI+idx; p>=pI; p--,idx--)
00295 ptr[*p] = ~idx;
00296 }
00297 }
00298
00299
00300 bool IntArrayList::TestSetIndexesTo(long* ptr,long valtest,long valset,bool& ind)
00301 {
00302 long*pI = this->Items;
00303 if (pI)
00304 for(long* p = pI+Count-1; p>=pI; p--)
00305 {
00306 if (ptr[*p] != valtest)
00307 ind = false;
00308 ptr[*p] = valset;
00309 }
00310 return ind;
00311 }
00312
00313
00314
00315 void IntArrayList::RemoveByBattern(long* ptr)
00316 {
00317 long*pI = this->Items;
00318 if (pI)
00319 {
00320 long* src = pI;
00321 long* des = pI;
00322 for(long k=Count; k>0; k--)
00323 {
00324 long e = *src++;
00325 if (ptr[e]==0)
00326 *des++ = e;
00327 else
00328 Count--;
00329 }
00330 }
00331 }
00332
00333
00334
00335
00336 void IntArrayList::RemoveMarkByBattern(long* ptr)
00337 {
00338 long* src = Items;
00339 long* des = Items;
00340 for(long k=Count; k>0; k--)
00341 {
00342 long e = *src++;
00343 if (ptr[e]==0)
00344 {
00345 *des++ = e;
00346 ptr[e] = 1;
00347 }
00348 else
00349 Count--;
00350 }
00351 }
00352
00353
00354
00355 long IntArrayList::CountWithoutMask(long* ptr)
00356 {
00357 long cnt = 0;
00358 if (Items)
00359 for(long* p = Items+Count-1; p>=Items; p--)
00360 if (ptr[*p]==0)
00361 cnt++;
00362 return cnt;
00363 }
00364
00365 DSS_NAMESPASE_END