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 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 //#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 void qSort(int L, int R, GCompareProc* cmpFunc);
37 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
57 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 void setCount(int NewCount, OBJ& v); //same as setCount() but new objects are set to v
86 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
93 void Sort(GCompareProc* cmpFunc);
94 };
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 void qSort(int L, int R, GCompareProc* cmpFunc);
109 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 void setCount(int NewCount); //the same as setCapacity() but the new item range is filled with NULLs
144 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 int IndexOf(pointer item); //a linear search for pointer address!
154 void Sort(GCompareProc* cmpFunc);
155 };
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
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 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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 template <class OBJ> void GPVec<OBJ>::Pack() {
740 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 if (NewCount > fCount) //pad with NULL pointers
749 memset(fList[fCount], 0, (NewCount - fCount) * sizeof(OBJ*));
750 fCount = NewCount;
751 }
752
753 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 //---------------------------------------------------------------------------
785 #endif