ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GVec.hh
Revision: 286
Committed: Mon Oct 15 17:31:47 2012 UTC (6 years, 9 months ago) by gpertea
File size: 22362 byte(s)
Log Message:
slight mods for rejoin use

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