ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GVec.hh
Revision: 310
Committed: Fri Mar 22 20:06:27 2013 UTC (5 years, 11 months ago) by gpertea
File size: 26290 byte(s)
Log Message:
sync with igm repo

Line File contents
1 //---------------------------------------------------------------------------
2 /*
3 Sortable collection of pointers to objects
4 */
5
6 #ifndef _GVec_HH
7 #define _GVec_HH
8
9 #include "GBase.h"
10
11 #define GVEC_INDEX_ERR "GVec error: invalid index: %d\n"
12 #if defined(NDEBUG) || defined(NODEBUG) || defined(_NDEBUG) || defined(NO_DEBUG)
13 #define TEST_INDEX(x)
14 #else
15 #define TEST_INDEX(x) \
16 if (x<0 || x>=fCount) GError(GVEC_INDEX_ERR, x)
17 #endif
18
19 #define GVEC_CAPACITY_ERR "GVec error: invalid capacity: %d\n"
20 #define GVEC_COUNT_ERR "GVec error: invalid count: %d\n"
21
22 #define MAXLISTSIZE INT_MAX-1
23
24 #define FREEDATA (fFreeProc!=NULL)
25
26 template<class T> struct IsPrimitiveType {
27 enum { VAL = 0 };
28 };
29
30 template<> struct IsPrimitiveType<bool> { enum { VAL = 1 }; };
31 template<> struct IsPrimitiveType<void*> { enum { VAL = 1 }; };
32 template<> struct IsPrimitiveType<float> { enum { VAL = 1 }; };
33 template<> struct IsPrimitiveType<double> { enum { VAL = 1 }; };
34
35 template<> struct IsPrimitiveType<int> { enum { VAL = 1 }; };
36 template<> struct IsPrimitiveType<unsigned int> { enum { VAL = 1 }; };
37 template<> struct IsPrimitiveType<char> { enum { VAL = 1 }; };
38 template<> struct IsPrimitiveType<unsigned char> { enum { VAL = 1 }; };
39 template<> struct IsPrimitiveType<short> { enum { VAL = 1 }; };
40 template<> struct IsPrimitiveType<unsigned short> { enum { VAL = 1 }; };
41 template<> struct IsPrimitiveType<long> { enum { VAL = 1 }; };
42 template<> struct IsPrimitiveType<unsigned long> { enum { VAL = 1 }; };
43 template<> struct IsPrimitiveType<long long> { enum { VAL = 1 }; };
44 template<> struct IsPrimitiveType<unsigned long long> { enum { VAL = 1 }; };
45
46 /*
47 template<> struct IsPrimitiveType<int64_t> { enum { VAL = 1 }; };
48 template<> struct IsPrimitiveType<uint64_t> { enum { VAL = 1 }; };
49 template<> struct IsPrimitiveType<int32_t> { enum { VAL = 1 }; };
50 template<> struct IsPrimitiveType<uint32_t> { enum { VAL = 1 }; };
51 template<> struct IsPrimitiveType<int16_t> { enum { VAL = 1 }; };
52 template<> struct IsPrimitiveType<uint16_t> { enum { VAL = 1 }; };
53 template<> struct IsPrimitiveType<int8_t> { enum { VAL = 1 }; };
54 template<> struct IsPrimitiveType<uint8_t> { enum { VAL = 1 }; };
55 */
56
57
58 template <class OBJ> int DefLTCompareProc(const pointer p1, const pointer p2) {
59 const OBJ& o1 = *((OBJ*) p1);
60 const OBJ& o2 = *((OBJ*) p2);
61 if (o1 < o2) return -1;
62 else return ((o2 < o1) ? 1 : 0 );
63 }
64
65 //basic template for array of objects;
66 //so it doesn't require comparison operators to be defined
67 template <class OBJ> class GVec {
68 protected:
69 OBJ* fArray;
70 int fCount;
71 int fCapacity;
72 void qSort(int L, int R, GCompareProc* cmpFunc);
73 public:
74 GVec(int init_capacity=2);
75 GVec(int init_count, const OBJ init_val);
76 GVec(GVec<OBJ>& array); //copy constructor
77 const GVec<OBJ>& operator=(GVec<OBJ>& array); //copy operator
78 virtual ~GVec();
79 void Insert(int idx, OBJ item) { Insert(idx, &item); }
80 void Insert(int idx, OBJ* item);
81 void idxInsert(int idx, OBJ& item) { Insert(idx, &item); }
82 void Grow();
83 void Grow(int idx, OBJ& item); //grow and add/insert item copy
84 void Reverse(); //WARNING: will break the sort order if SORTED!
85 int Add(OBJ* item); // simply append to the end of fArray, reallocating as needed
86 int Add(OBJ& item) { return Add(&item); }
87 int cAdd(OBJ item) { return Add(&item); } //all these will CREATE a new OBJ and COPY to it
88 // // using OBJ copy operator=
89 // -- stack/queue usage:
90 //int Push(OBJ& item) { return Add(&item); }
91 int Push(OBJ& item) { return Add(&item); }
92 int cPush(OBJ item) { return Add(&item); }
93 OBJ Pop();// Stack use; removes and returns a copy of the last item
94 OBJ Shift(); //Queue use: removes and returns a copy of the first item
95
96 void Add(GVec<OBJ>& list); //append copies of all items from another list
97
98 OBJ& Get(int idx) {
99 TEST_INDEX(idx);
100 return fArray[idx];
101 }
102 inline OBJ& operator[](int i) {
103 TEST_INDEX(i);
104 return fArray[i];
105 }
106 OBJ& Last() {
107 TEST_INDEX(fCount-1);
108 return fArray[fCount-1];
109 }
110 OBJ& First() {
111 TEST_INDEX(0);
112 return fArray[0];
113 }
114 void Clear();
115 void Delete(int index);
116 void Replace(int idx, OBJ& item); //Put, use operator= to copy
117 void Exchange(int idx1, int idx2);
118 void Swap(int idx1, int idx2) { Exchange(idx1, idx2); }
119 int Capacity() { return fCapacity; }
120 //this will reject identical items in sorted lists only!
121 void setCapacity(int NewCapacity);
122 int Count() { return fCount; }
123
124 void setCount(int NewCount); // will trim or expand the array as needed
125 void setCount(int NewCount, OBJ* v); //same as setCount() but new objects are set to v
126 void setCount(int NewCount, OBJ v);
127 void Resize(int NewCount) { setCount(NewCount); }
128 //void Resize(int NewCount, OBJ* v) { setCount(NewCount, v); }
129 void Resize(int NewCount, OBJ v) { setCount(NewCount, &v); }
130
131 //void Move(int curidx, int newidx);
132 bool isEmpty() { return fCount==0; }
133 bool notEmpty() { return fCount>0; }
134
135 void Sort(GCompareProc* cmpFunc);
136 void Sort();
137 };
138
139 //---- template for dynamic array of object pointers
140 //---- it's faster than GVec<OBJ*> and has item deallocation awareness
141 template <class OBJ> class GPVec {
142 protected:
143 OBJ** fList; //pointer to an array of pointers to objects
144 int fCount; //total number of entries in list
145 int fCapacity; //current allocated size
146 GFreeProc* fFreeProc; //useful for deleting objects
147 //---
148 void Expand();
149 void Grow();
150 void Grow(int idx, OBJ* newitem);
151 void qSort(int L, int R, GCompareProc* cmpFunc);
152 public:
153 static void DefaultFreeProc(pointer item) {
154 delete (OBJ*)item;
155 }
156 virtual ~GPVec();
157 GPVec(int init_capacity=2, bool free_elements=true); //also the default constructor
158 GPVec(bool free_elements);
159 GPVec(GPVec<OBJ>& list); //copy constructor?
160 GPVec(GPVec<OBJ>* list); //kind of a copy constructor
161 const GPVec<OBJ>& operator=(GPVec<OBJ>& list);
162 OBJ* Get(int i);
163 OBJ* operator[](int i) { return this->Get(i); }
164 void Reverse(); //reverse pointer array; WARNING: will break the sort order if sorted!
165 void freeItem(int idx); //calls fFreeProc (or DefaultFreeProc) on fList[idx] and sets NULL there, doesn't pack!
166 //it will free even if fFreeProc is NULL!
167 void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
168 void setFreeItem(bool doFree) {
169 if (doFree) fFreeProc=DefaultFreeProc;
170 else fFreeProc=NULL;
171 }
172 // -- stack usage:
173 int Push(OBJ* item) { return Add(item); }
174 OBJ* Pop();// Stack use; removes and returns last item,but does NOT FREE it
175 OBJ* Shift(); //Queue use: removes and returns first item, but does NOT FREE it
176 void deallocate_item(OBJ*& item); //forcefully call fFreeProc or delete on item
177 void Clear();
178 void Exchange(int idx1, int idx2);
179 void Swap(int idx1, int idx2) { Exchange(idx1, idx2); }
180 OBJ* First() { return (fCount>0)?fList[0]:NULL; }
181 OBJ* Last() { return (fCount>0)?fList[fCount-1]:NULL;}
182 bool isEmpty() { return fCount==0; }
183 bool notEmpty() { return fCount>0; }
184 int Capacity() { return fCapacity; }
185 int Count() { return fCount; }
186 void setCapacity(int NewCapacity);
187 void setCount(int NewCount); //the same as setCapacity() but the new item range is filled with NULLs
188 int Add(OBJ* item); //simply append the pointer copy
189 void Add(GPVec<OBJ>& list); //add all pointers from another list
190 void Insert(int idx, OBJ* item);
191 void Move(int curidx, int newidx);
192 void Put(int idx, OBJ* item);
193 void Pack();
194 void Delete(int index); //also frees the item if fFreeProc!=NULL, and shifts the successor items
195 void Forget(int idx); //simply places a NULL at fList[idx], nothing else
196 int RemovePtr(pointer item); //always use linear search to find the pointer! calls Delete() if found
197 int IndexOf(pointer item); //a linear search for pointer address!
198 void Sort(GCompareProc* cmpFunc);
199 void Sort();
200 };
201
202 //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
203
204 template <class OBJ> GVec<OBJ>::GVec(int init_capacity) {
205 fCount=0;
206 fCapacity=0;
207 fArray=NULL;
208 setCapacity(init_capacity);
209 }
210
211
212 template <class OBJ> GVec<OBJ>::GVec(int init_count, const OBJ init_val) {
213 fCount=0;
214 fCapacity=0;
215 fArray=NULL;
216 setCapacity(init_count);
217 fCount = init_count;
218 for (int i=0;i<fCount;i++)
219 fArray[i]=init_val;
220 }
221
222
223 template <class OBJ> GVec<OBJ>::GVec(GVec<OBJ>& array) { //copy constructor
224 this->fCount=array.fCount;
225 this->fCapacity=array.fCapacity;
226 this->fArray=NULL;
227 if (this->fCapacity>0) {
228 if (IsPrimitiveType<OBJ>::VAL) {
229 GMALLOC(fArray, fCapacity*sizeof(OBJ));
230 memcpy(fArray, array.fArray, fCount*sizeof(OBJ));
231 }
232 else {
233 fArray=new OBJ[this->fCapacity]; //]()
234 // uses OBJ operator=
235 for (int i=0;i<this->fCount;i++) fArray[i]=array[i];
236 }
237 }
238 this->fCount=array.fCount;
239 }
240
241 template <class OBJ> const GVec<OBJ>& GVec<OBJ>::operator=(GVec<OBJ>& array) {
242 if (&array==this) return *this;
243 Clear();
244 fCapacity=array.fCapacity;
245 fCount=array.fCount;
246 if (fCapacity>0) {
247 if (IsPrimitiveType<OBJ>::VAL) {
248 GMALLOC(fArray, fCapacity*sizeof(OBJ));
249 memcpy(fArray, array.fArray, fCount*sizeof(OBJ));
250 }
251 else {
252 fArray=new OBJ[this->fCapacity]; // ]()
253 // uses OBJ operator=
254 for (int i=0;i<fCount;i++) {
255 fArray[i]=array.fArray[i];
256 }
257 }
258 }
259 return *this;
260 }
261
262 template <class OBJ> GVec<OBJ>::~GVec() {
263 this->Clear();
264 }
265
266
267 template <class OBJ> void GVec<OBJ>::setCapacity(int NewCapacity) {
268 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
269 GError(GVEC_CAPACITY_ERR, NewCapacity);
270 //error: NewCapacity MUST be > fCount
271 //if you want to shrink it use Resize() or setCount()
272 if (NewCapacity!=fCapacity) {
273 if (NewCapacity==0) {
274 if (IsPrimitiveType<OBJ>::VAL) {
275 GFREE(fArray);
276 } else {
277 delete[] fArray;
278 fArray=NULL;
279 }
280 }
281 else {
282 if (IsPrimitiveType<OBJ>::VAL) {
283 GREALLOC(fArray, NewCapacity*sizeof(OBJ));
284 } else {
285 OBJ* oldArray=fArray;
286 //fArray=new OBJ[NewCapacity]();
287 fArray=new OBJ[NewCapacity];
288 for (int i=0;i<this->fCount;i++) {
289 fArray[i] = oldArray[i];
290 }// we need operator= here
291 //wouldn't be faster to use memcpy instead?
292 //memcpy(fArray, oldArray, fCount*sizeof(OBJ));
293 if (oldArray) delete[] oldArray;
294 }
295 }
296 fCapacity=NewCapacity;
297 }
298 }
299
300 template <class OBJ> void GVec<OBJ>::Clear() {
301 fCount=0;
302 if (IsPrimitiveType<OBJ>::VAL) {
303 GFREE(fArray);
304 }
305 else {
306 delete[] fArray;
307 fArray=NULL;
308 }
309 fCapacity=0;
310 }
311
312 template <class OBJ> void GVec<OBJ>::Grow() {
313 int delta = (fCapacity>8) ? (fCapacity>>2) : 1 ;
314 setCapacity(fCapacity + delta);
315 }
316
317 template <class OBJ> void GVec<OBJ>::Reverse() {
318 int l=0;
319 int r=fCount-1;
320 OBJ c;
321 while (l<r) {
322 c=fArray[l];fArray[l]=fArray[r];
323 fArray[r]=c;
324 l++;r--;
325 }
326 }
327
328 template <class OBJ> void GVec<OBJ>::Grow(int idx, OBJ& item) {
329 int delta = (fCapacity>8) ? (fCapacity>>2) : 1 ;
330 int NewCapacity=fCapacity+delta;
331 if (NewCapacity <= fCount || NewCapacity >= MAXLISTSIZE)
332 GError(GVEC_CAPACITY_ERR, NewCapacity);
333 //error: capacity not within range
334 //if (NewCapacity!=fCapacity) {
335 if (idx==fCount) { //append item
336 //GREALLOC(fArray, NewCapacity*sizeof(OBJ));
337 setCapacity(NewCapacity);
338 fArray[idx]=item;
339 }
340 else { //insert item at idx
341 OBJ* newList;
342 if (IsPrimitiveType<OBJ>::VAL) {
343 GMALLOC(newList, NewCapacity*sizeof(OBJ));
344 //copy data before idx
345 memcpy(&newList[0],&fArray[0], idx*sizeof(OBJ));
346 newList[idx]=item;
347 //copy data after idx
348 memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
349 //..shouldn't do this:
350 memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ));
351 //data copied:
352 GFREE(fArray);
353 } else {
354 newList=new OBJ[NewCapacity]; //]()
355 // operator= required!
356 for (int i=0;i<idx;i++) {
357 newList[i]=fArray[i];
358 }
359 newList[idx]=item;
360 //copy data after idx
361 //memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
362 for (int i=idx+1;i<=fCount;i++) {
363 newList[i]=fArray[i-1];
364 }
365 delete[] fArray;
366 }
367 fArray=newList;
368 fCapacity=NewCapacity;
369 }
370 fCount++;
371 }
372 template <class OBJ> int GVec<OBJ>::Add(OBJ* item) {
373 if (item==NULL) return -1;
374 if (fCount==fCapacity) Grow();
375 fArray[fCount] = *item; //OBJ::operator= must copy OBJ properly!
376 fCount++;
377 return fCount-1;
378 }
379
380
381 template <class OBJ> void GVec<OBJ>::Add(GVec<OBJ>& list) {
382 if (list.Count()==0) return;
383 //simply copy
384 setCapacity(fCapacity+list.fCount);
385 if (IsPrimitiveType<OBJ>::VAL) {
386 memcpy( &fArray[fCount], list.fArray, list.fCount*sizeof(OBJ));
387 }
388 else {
389 for (int i=0;i<list.fCount;i++)
390 fArray[fCount+i]=list.fArray[i];
391 }
392 fCount+=list.fCount;
393 }
394
395 //Stack usage:
396 template <class OBJ> OBJ GVec<OBJ>::Pop() {
397 if (fCount<=0) GError("Error: invalid GVec::Pop() operation!\n");
398 fCount--;
399 //OBJ o(fArray[fCount]); //copy constructor
400 //o=fList[fCount];
401 //fArray[fCount]=NULL;
402 return fArray[fCount]; //copy of the last element (copy constructor called)
403 }
404
405 //Queue usage:
406 template <class OBJ> OBJ GVec<OBJ>::Shift() {
407 if (fCount<=0) GError("Error: invalid GVec::Shift() operation!\n");
408 fCount--;
409 OBJ o(fArray[0]); //copy constructor
410 if (fCount>0)
411 memmove(&fArray[0], &fArray[1], (fCount)*sizeof(OBJ));
412 //fList[fCount]=NULL; //not that it matters..
413 return o;
414 }
415
416 template <class OBJ> void GVec<OBJ>::Insert(int idx, OBJ* item) {
417 //idx must be the new position this new item must have
418 //so the allowed range is [0..fCount]
419 //the old idx item all the above will be shifted to idx+1
420 if (idx<0 || idx>fCount) GError(GVEC_INDEX_ERR, idx);
421 if (fCount==fCapacity) { //need to resize the array
422 Grow(idx, *item); //expand and also copy/move data and insert the new item
423 return;
424 }
425 //move data around to make room for the new item
426 if (idx<fCount) {
427 //copy after-idx items (shift up)
428 if (IsPrimitiveType<OBJ>::VAL) {
429 memmove(&fArray[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
430 }
431 else {
432 for (int i=fCount; i>idx; i--) {
433 fArray[i]=fArray[i-1];
434 }
435 }
436 }
437 fArray[idx]=*item;
438 fCount++;
439 }
440
441
442 /*template <class OBJ> void GVec<OBJ>::Move(int curidx, int newidx) { //swap
443 if (curidx!=newidx || newidx>=fCount)
444 GError(GVEC_INDEX_ERR, newidx);
445 OBJ tmp=fArray[curidx]; //copy constructor here
446 fArray[curidx]=fArray[newidx];
447 fArray[newidx]=tmp;
448 }*/
449
450
451 template <class OBJ> void GVec<OBJ>::Replace(int idx, OBJ& item) {
452 TEST_INDEX(idx);
453 fArray[idx]=item;
454 }
455
456 template <class OBJ> void GVec<OBJ>::Exchange(int idx1, int idx2) {
457 TEST_INDEX(idx1);
458 TEST_INDEX(idx2);
459 OBJ item=fArray[idx1];
460 fArray[idx1]=fArray[idx2];
461 fArray[idx2]=item;
462 }
463
464
465 template <class OBJ> void GVec<OBJ>::Delete(int index) {
466 TEST_INDEX(index);
467 fCount--;
468 if (IsPrimitiveType<OBJ>::VAL) {
469 if (index<fCount)
470 //move higher elements if any (shift down)
471 memmove(&fArray[index], &fArray[index+1], (fCount-index)*sizeof(OBJ));
472 }
473 else {
474 while (index<fCount) {
475 fArray[index]=fArray[index+1];
476 index++;
477 }
478 }
479 }
480
481 template <class OBJ> void GVec<OBJ>::setCount(int NewCount) {
482 if (NewCount<0 || NewCount > MAXLISTSIZE)
483 GError(GVEC_COUNT_ERR, NewCount);
484 //if (NewCount > fCapacity) setCapacity(NewCount);
485 while(NewCount > fCapacity) Grow();
486 fCount = NewCount; //new items will be populated by the default object constructor(!)
487 }
488
489 template <class OBJ> void GVec<OBJ>::setCount(int NewCount, OBJ* v) {
490 if (NewCount<0 || NewCount > MAXLISTSIZE)
491 GError(GVEC_COUNT_ERR, NewCount);
492 while (NewCount > fCapacity) Grow();
493 if (NewCount>fCount) {
494 for (int i=fCount;i<NewCount;i++)
495 fArray[i]=*v;
496 }
497 fCount = NewCount;
498 }
499
500 template <class OBJ> void GVec<OBJ>::setCount(int NewCount, OBJ v) {
501 if (NewCount<0 || NewCount > MAXLISTSIZE)
502 GError(GVEC_COUNT_ERR, NewCount);
503 while (NewCount > fCapacity) Grow();
504 if (NewCount>fCount) {
505 for (int i=fCount;i<NewCount;i++)
506 fArray[i]=v;
507 }
508 fCount = NewCount;
509 }
510
511
512 template <class OBJ> void GVec<OBJ>::qSort(int l, int r, GCompareProc* cmpFunc) {
513 int i, j;
514 OBJ p,t;
515 do {
516 i = l; j = r;
517 p = this->fArray[(l + r) >> 1];
518 do {
519 while (cmpFunc(&(this->fArray[i]), &p) < 0) i++;
520 while (cmpFunc(&(this->fArray[j]), &p) > 0) j--;
521 if (i <= j) {
522 t = this->fArray[i];
523 this->fArray[i] = this->fArray[j];
524 this->fArray[j] = t;
525 i++; j--;
526 }
527 } while (i <= j);
528 if (l < j) qSort(l, j, cmpFunc);
529 l = i;
530 } while (i < r);
531 }
532
533 template <class OBJ> void GVec<OBJ>::Sort(GCompareProc* cmpFunc) {
534 if (cmpFunc==NULL) {
535 GMessage("Warning: NULL compare function given, useless Sort() call.\n");
536 return;
537 }
538 if (this->fArray!=NULL && this->fCount>0)
539 qSort(0, this->fCount-1, cmpFunc);
540 }
541
542 template <class OBJ> void GVec<OBJ>::Sort() {
543 GCompareProc* cmpFunc = DefLTCompareProc<OBJ>;
544 Sort(cmpFunc);
545 }
546
547
548 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
549 //*=> GPVec implementation
550
551 template <class OBJ> GPVec<OBJ>::GPVec(GPVec& list) { //copy constructor
552 fCount=list.fCount;
553 fCapacity=list.fCapacity;
554 fList=NULL;
555 if (fCapacity>0) {
556 GMALLOC(fList, fCapacity*sizeof(OBJ*));
557 }
558 fFreeProc=list.fFreeProc;
559 fCount=list.fCount;
560 memcpy(fList, list.fList, fCount*sizeof(OBJ*));
561 //for (int i=0;i<list.Count();i++) Add(list[i]);
562 }
563
564 template <class OBJ> GPVec<OBJ>::GPVec(GPVec* plist) { //another copy constructor
565 fCount=0;
566 fCapacity=plist->fCapacity;
567 fList=NULL;
568 if (fCapacity>0) {
569 GMALLOC(fList, fCapacity*sizeof(OBJ*));
570 }
571 fFreeProc=plist->fFreeProc;
572 fCount=plist->fCount;
573 memcpy(fList, plist->fList, fCount*sizeof(OBJ*));
574 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
575 }
576
577 template <class OBJ> const GPVec<OBJ>& GPVec<OBJ>::operator=(GPVec& list) {
578 if (&list!=this) {
579 Clear();
580 fFreeProc=list.fFreeProc;
581 //Attention: the object *POINTERS* are copied,
582 // but the actual object content is NOT duplicated
583 //for (int i=0;i<list.Count();i++) Add(list[i]);
584 fCount=list.fCount;
585 GMALLOC(fList, fCapacity*sizeof(OBJ*));
586 memcpy(fList, list.fList, fCount*sizeof(OBJ*));
587 }
588 return *this;
589 }
590
591
592 template <class OBJ> void GPVec<OBJ>::Add(GPVec<OBJ>& list) {
593 if (list.Count()==0) return;
594 //simply copy the pointers! -- the objects will be shared
595 setCapacity(fCapacity+list.fCount);
596 memcpy( & (fList[fCount]), list.fList, list.fCount*sizeof(OBJ*));
597 fCount+=list.fCount;
598 }
599
600 template <class OBJ> void GPVec<OBJ>::Reverse() {
601 int l=0;
602 int r=fCount-1;
603 OBJ* c;
604 while (l<r) {
605 c=fList[l];fList[l]=fList[r];
606 fList[r]=c;
607 l++;r--;
608 }
609 }
610
611 template <class OBJ> GPVec<OBJ>::GPVec(int init_capacity, bool free_elements) {
612 fCount=0;
613 fCapacity=0;
614 fList=NULL;
615 fFreeProc=(free_elements) ? DefaultFreeProc : NULL;
616 if (init_capacity>0)
617 setCapacity(init_capacity);
618 }
619
620 template <class OBJ> GPVec<OBJ>::GPVec(bool free_elements) {
621 fCount=0;
622 fCapacity=0;
623 fList=NULL;
624 fFreeProc=(free_elements) ? DefaultFreeProc : NULL;
625 }
626
627 template <class OBJ> GPVec<OBJ>::~GPVec() {
628 this->Clear();//this will free the items if fFreeProc is defined
629 }
630
631 template <class OBJ> void GPVec<OBJ>::setCapacity(int NewCapacity) {
632 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
633 GError(GVEC_CAPACITY_ERR, NewCapacity);
634 //error: capacity not within range
635 if (NewCapacity!=fCapacity) {
636 if (NewCapacity==0) {
637 GFREE(fList);
638 }
639 else {
640 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
641 }
642 fCapacity=NewCapacity;
643 }
644 }
645
646 template <class OBJ> void GPVec<OBJ>::deallocate_item(OBJ* &item) {
647 if (item==NULL) return;
648 if (FREEDATA) {
649 (*fFreeProc)(item);
650 item=NULL;
651 }
652 else {
653 delete item;
654 item=NULL;
655 }
656 }
657
658 template <class OBJ> void GPVec<OBJ>::Clear() {
659 if (FREEDATA) {
660 for (int i=0; i<fCount; i++) {
661 (*fFreeProc)(fList[i]);
662 }
663 }
664 GFREE(fList);
665 fCount=0;
666 fCapacity=0;
667 }
668
669 template <class OBJ> void GPVec<OBJ>::Exchange(int idx1, int idx2) {
670 TEST_INDEX(idx1);
671 TEST_INDEX(idx2);
672 OBJ* item=fList[idx1];
673 fList[idx1]=fList[idx2];
674 fList[idx2]=item;
675 }
676
677 template <class OBJ> void GPVec<OBJ>::Expand() {
678 if (fCount==fCapacity) Grow();
679 //return this;
680 }
681
682 template <class OBJ> OBJ* GPVec<OBJ>::Get(int idx) {
683 TEST_INDEX(idx);
684 return fList[idx];
685 }
686
687 template <class OBJ> void GPVec<OBJ>::Grow() {
688 /*
689 int delta;
690 if (fCapacity > 64 ) {
691 delta = (fCapacity > 0xFFF) ? 0x100 : (fCapacity>>4);
692 }
693 else {
694 delta = (fCapacity>8) ? (fCapacity>>2) : 1 ;
695 }
696 */
697 int delta = (fCapacity>8) ? (fCapacity>>2) : 1;
698 setCapacity(fCapacity + delta);
699 }
700
701 template <class OBJ> void GPVec<OBJ>::Grow(int idx, OBJ* newitem) {
702 /*
703 int delta;
704 if (fCapacity > 64 ) {
705 delta = (fCapacity > 0xFFF) ? 0x100 : (fCapacity>>4);
706 }
707 else {
708 delta = (fCapacity>8) ? (fCapacity>>2) : 1 ;
709 }
710 */
711 int delta = (fCapacity>8) ? (fCapacity>>2) : 1 ;
712 int NewCapacity=fCapacity+delta;
713 if (NewCapacity <= fCount || NewCapacity > MAXLISTSIZE)
714 GError(GVEC_CAPACITY_ERR, NewCapacity);
715 //error: capacity not within range
716 //if (NewCapacity!=fCapacity) {
717 /*if (NewCapacity==0) {
718 GFREE(fList);
719 }
720 else {//add the new item
721 */
722 if (idx==fCount) {
723 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
724 fList[idx]=newitem;
725 }
726 else {
727 OBJ** newList;
728 GMALLOC(newList, NewCapacity*sizeof(OBJ*));
729 //copy data before idx
730 memcpy(&newList[0],&fList[0], idx*sizeof(OBJ*));
731 newList[idx]=newitem;
732 //copy data after idx
733 memmove(&newList[idx+1],&fList[idx], (fCount-idx)*sizeof(OBJ*));
734 memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ*));
735 //data copied:
736 GFREE(fList);
737 fList=newList;
738 }
739 fCount++;
740 fCapacity=NewCapacity;
741 }
742
743 template <class OBJ> int GPVec<OBJ>::IndexOf(pointer item) {
744 int result=-1;
745 for (int i=0;i<fCount;i++) {
746 if (item==(pointer)fList[i]) return i;
747 }
748 return -1;
749 }
750
751 template <class OBJ> int GPVec<OBJ>::Add(OBJ* item) {
752 int result;
753 if (item==NULL) return -1;
754 result = fCount;
755 if (result==fCapacity) this->Grow();
756 fList[result]=item;
757 fCount++;
758 return fCount-1;
759 }
760
761 template <class OBJ> void GPVec<OBJ>::Insert(int idx, OBJ* item) {
762 //idx can be [0..fCount] so an item can be actually added
763 if (idx<0 || idx>fCount) GError(GVEC_INDEX_ERR, idx);
764 if (fCount==fCapacity) {
765 Grow(idx, item);
766 return;
767 }
768 if (idx<fCount)
769 memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
770 fList[idx]=item;
771 fCount++;
772 }
773
774 template <class OBJ> void GPVec<OBJ>::Move(int curidx, int newidx) { //s
775 //BE_UNSORTED; //cannot do that in a sorted list!
776 if (curidx!=newidx || newidx>=fCount)
777 GError(GVEC_INDEX_ERR, newidx);
778 OBJ* p;
779 p=Get(curidx);
780 //this is a delete:
781 fCount--;
782 if (curidx<fCount)
783 memmove(&fList[curidx], &fList[curidx+1], (fCount-curidx)*sizeof(OBJ*));
784 //-this was instead of delete
785 Insert(newidx, p);
786 }
787
788 template <class OBJ> void GPVec<OBJ>::Put(int idx, OBJ* item) {
789 //WARNING: this will never free the replaced item!
790 TEST_INDEX(idx);
791 fList[idx]=item;
792 }
793
794 template <class OBJ> void GPVec<OBJ>::Forget(int idx) {
795 TEST_INDEX(idx);
796 fList[idx]=NULL; //user should free that somewhere else
797 }
798
799 template <class OBJ> void GPVec<OBJ>::freeItem(int idx) {
800 TEST_INDEX(idx);
801 if (fFreeProc!=NULL) {
802 (*fFreeProc)(fList[idx]);
803 }
804 else this->DefaultFreeProc(fList[idx]);
805 fList[idx]=NULL;
806 }
807
808 template <class OBJ> void GPVec<OBJ>::Delete(int index) {
809 TEST_INDEX(index);
810 if (fFreeProc!=NULL && fList[index]!=NULL) {
811 (*fFreeProc)(fList[index]); //freeItem
812 }
813 fList[index]=NULL;
814 fCount--;
815 if (index<fCount) //move higher elements if any
816 memmove(&fList[index], &fList[index+1], (fCount-index)*sizeof(OBJ*));
817 }
818
819 //Stack usage:
820 template <class OBJ> OBJ* GPVec<OBJ>::Pop() {
821 if (fCount<=0) return NULL;
822 fCount--;
823 OBJ* o=fList[fCount];
824 fList[fCount]=NULL;
825 return o;
826 }
827
828 //Queue usage:
829 template <class OBJ> OBJ* GPVec<OBJ>::Shift() {
830 if (fCount<=0) return NULL;
831 fCount--;
832 OBJ* o=fList[0];
833 if (fCount>0)
834 memmove(&fList[0], &fList[1], (fCount)*sizeof(OBJ*));
835 fList[fCount]=NULL; //not that it matters..
836 return o;
837 }
838
839 //linear search for the pointer address
840 template <class OBJ> int GPVec<OBJ>::RemovePtr(pointer item) {
841 if (item==NULL) return -1;
842 for (int i=0;i<fCount;i++)
843 if ((pointer)fList[i] == item) {
844 Delete(i);
845 return i;
846 }
847 return -1; //not found
848 }
849
850 template <class OBJ> void GPVec<OBJ>::Pack() {
851 for (int i=fCount-1; i>=0; i--)
852 if (fList[i]==NULL) Delete(i); //shift rest of fList content accordingly
853 }
854
855 template <class OBJ> void GPVec<OBJ>::setCount(int NewCount) {
856 if (NewCount<0 || NewCount > MAXLISTSIZE)
857 GError(GVEC_COUNT_ERR, NewCount);
858 if (NewCount > fCapacity) setCapacity(NewCount);
859 if (NewCount > fCount) //pad with NULL pointers
860 memset(& fList[fCount], 0, (NewCount - fCount) * sizeof(OBJ*));
861 fCount = NewCount;
862 }
863
864 template <class OBJ> void GPVec<OBJ>::qSort(int L, int R, GCompareProc* cmpFunc) {
865 int I, J;
866 OBJ* P;
867 OBJ* T;
868 do {
869 I = L;
870 J = R;
871 P = this->fList[(L + R) >> 1];
872 do {
873 while (cmpFunc(this->fList[I], P) < 0) I++;
874 while (cmpFunc(this->fList[J], P) > 0) J--;
875 if (I <= J) {
876 T = this->fList[I];
877 this->fList[I] = this->fList[J];
878 this->fList[J] = T;
879 I++;
880 J--;
881 }
882 }
883 while (I <= J);
884 if (L < J) qSort(L, J, cmpFunc);
885 L = I;
886 }
887 while (I < R);
888 }
889
890 template <class OBJ> void GPVec<OBJ>::Sort(GCompareProc* cmpFunc) {
891 if (cmpFunc==NULL) {
892 GMessage("Warning: NULL compare function given, useless Sort() call.\n");
893 return;
894 }
895 if (this->fList!=NULL && this->fCount>0)
896 qSort(0, this->fCount-1, cmpFunc);
897 }
898
899
900 template <class OBJ> void GPVec<OBJ>::Sort() {
901 GCompareProc* cmpFunc = DefLTCompareProc<OBJ>;
902 Sort(cmpFunc);
903 }
904
905
906 //---------------------------------------------------------------------------
907 #endif