ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 132
Committed: Thu Dec 8 02:53:32 2011 UTC (7 years, 10 months ago) by gpertea
File size: 41340 byte(s)
Log Message:
GBam working; fixed serious memory leak in GVec::setCapacity()

Line File contents
1 //---------------------------------------------------------------------------
2 /*
3 Sortable collection of pointers to objects
4 */
5
6 #ifndef GListHH
7 #define GListHH
8
9 #include "GBase.h"
10 //#include "assert.h"
11
12 #ifdef __LINE__
13 #define SLISTINDEX_ERR "GList error (%s:%d):Invalid list index: %d\n"
14 #define TEST_INDEX(x) \
15 if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, __FILE__,__LINE__, x)
16 #else
17 #define SLISTINDEX_ERR "GList error:Invalid list index: %d\n"
18 #define TEST_INDEX(x) \
19 if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x, __FILE__,__LINE__)
20 #endif
21
22 #define SLISTCAPACITY_ERR "GList error: invalid capacity: %d\n"
23 #define SLISTCOUNT_ERR "GList error: invalid count: %d\n"
24 #define SLISTSORTED_ERR "Operation not allowed on a sorted list!\n"
25 #define SLISTUNSORTED_ERR "Operation not allowed on an unsorted list!\n"
26
27 // ------ macros:
28 #define BE_UNSORTED if (fCompareProc!=NULL) { GError(SLISTSORTED_ERR); return; }
29 #define BE_SORTED if (fCompareProc==NULL) { GError(SLISTUNSORTED_ERR); return; }
30
31 #define MAXLISTSIZE INT_MAX-1
32
33 #define SORTED (fCompareProc!=NULL)
34 #define UNSORTED (fCompareProc==NULL)
35 #define FREEDATA (fFreeProc!=NULL)
36 /* #define TEST_INDEX(x) assert(x>=0 && x<fCount); \
37 if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x) */
38
39
40 //template for array of objects; GVec is not sortable,
41 // so it doesn't require comparison operators defined
42 template <class OBJ> class GVec {
43 protected:
44 OBJ* fArray;
45 int fCount;
46 int fCapacity;
47 public:
48 GVec(int init_capacity=20);
49 GVec(GVec<OBJ>& array); //copy constructor
50 const GVec<OBJ>& operator=(GVec& array); //copy operator
51 virtual ~GVec();
52 void idxInsert(int idx, OBJ& item);
53 void Grow();
54 void Grow(int idx, OBJ& item);
55 void Reverse(); //WARNING: will break the sort order if SORTED!
56 int Add(OBJ* item); // simply append to the end of fArray, reallocating as needed
57 int Add(OBJ& item) { return Add(&item); } //both will CREATE a new OBJ and COPY to it
58 // using OBJ new operator=
59 void Add(GVec<OBJ>& list); //append copies of all items from another list
60 OBJ& Get(int idx) {
61 TEST_INDEX(idx);
62 return fArray[idx];
63 }
64 OBJ& operator[](int i) {
65 TEST_INDEX(i);
66 return fArray[i];
67 }
68 void Clear();
69 void Insert(int idx, OBJ* item);
70 void Delete(int index);
71 void Replace(int idx, OBJ& item); //Put, use operator= to copy
72 void Exchange(int idx1, int idx2);
73 void Swap(int idx1, int idx2) { Exchange(idx1, idx2); }
74 int Capacity() { return fCapacity; }
75 //this will reject identical items in sorted lists only!
76 void setCapacity(int NewCapacity);
77 int Count() { return fCount; }
78 void setCount(int NewCount); //?! - will trim or expand the array as needed
79 void Move(int curidx, int newidx);
80 };
81
82 // GArray is the sortable collection, but requires the comparison operators to be defined
83 template <class OBJ> class GArray:public GVec<OBJ> {
84 protected:
85 bool fUnique;
86 static int DefaultCompareProc(OBJ& item1, OBJ& item2) {
87 //the comparison operators MUST be defined for OBJ class!
88 if ( item1 > item2) return 1;
89 else return (item2 > item1) ? -1 : 0 ;
90 }
91 public:
92 typedef int CompareProc(OBJ& item1, OBJ& item2);
93 protected:
94 CompareProc* fCompareProc;
95 void qSort(int L, int R);
96 public:
97 GArray(CompareProc* cmpFunc=NULL);
98 GArray(bool sorted, bool unique=false);
99 GArray(int init_capacity, bool sorted, bool unique=false);
100 GArray(GArray<OBJ>& array); //copy constructor
101 const GArray<OBJ>& operator=(GArray& array);
102 //~GArray();
103 //assignment operator
104 void setSorted(CompareProc* cmpFunc);
105 //sort the array if cmpFunc not NULL or changes
106 int Add(OBJ* item); // specific implementation if sorted
107 int Add(OBJ& item) { return Add(&item); } //both will CREATE a new OBJ and COPY to it
108 // using OBJ new operator=
109 void Add(GArray<OBJ>& list); //add copies of all items from another list
110 //this will reject identical items in sorted lists only!
111 void setUnique(bool beUnique) { fUnique = beUnique; };
112 void Sort(); //explicit sort may be requested
113 bool Sorted() { return fCompareProc!=NULL; }
114 void Replace(int idx, OBJ& item); //Put, use operator= to copy
115 int Unique() { return fUnique; }
116 int IndexOf(OBJ& item);
117 //this needs the == operator to have been defined for OBJ
118 bool Found(OBJ& item, int& idx); // for sorted arrays only;
119 //search by content; if found, returns true and idx will be the index
120 //of the first item found matching for which CompareProc returns 0
121 bool Exists(OBJ& item); //same as above without existing index info
122 //unsorted only, place item at position idx:
123 void Move(int curidx, int newidx);
124 void Insert(int idx, OBJ* item);
125 void Insert(int idx, OBJ& item) { Insert(idx,&item); }
126 };
127
128 //------- template for array of pointers to objects ---------
129 template <class OBJ> class GPVec {
130 protected:
131 OBJ** fList; //pointer to an array of pointers to objects
132 int fCount; //total number of entries in list
133 int fCapacity; //current allocated size
134 GFreeProc* fFreeProc; //useful for deleting objects
135 //---
136 void Expand();
137 void Grow();
138 void Grow(int idx, OBJ* newitem);
139 void setCount(int NewCount); //will trim/expand the array as needed
140 public:
141 static void DefaultFreeProc(pointer item) {
142 delete (OBJ*)item;
143 }
144 virtual ~GPVec();
145 GPVec(int init_capacity=10, bool free_elements=true); //also the default constructor
146 GPVec(GPVec<OBJ>& list); //copy constructor?
147 GPVec(GPVec<OBJ>* list); //kind of a copy constructor
148 const GPVec<OBJ>& operator=(GPVec& list);
149 OBJ* Get(int i);
150 OBJ* operator[](int i) { return this->Get(i); }
151 void Reverse(); //reverse pointer array; WARNING: will break the sort order if sorted!
152 void freeItem(int idx); //calls fFreeProc (or DefaultFreeProc) on fList[idx] and sets NULL there, doesn't pack!
153 //it will free even if fFreeProc is NULL!
154 void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
155 void setFreeItem(bool doFree) {
156 if (doFree) fFreeProc=DefaultFreeProc;
157 else fFreeProc=NULL;
158 }
159 // -- stack usage:
160 int Push(OBJ* item) { return Add(item); }
161 OBJ* Pop();// Stack use; removes and returns last item,but does NOT FREE it
162 OBJ* Shift(); //Queue use: removes and returns first item, but does NOT FREE it
163 void deallocate_item(OBJ* item); //forcefully call fFreeProc or delete on item
164 void Clear();
165 void Exchange(int idx1, int idx2);
166 void Swap(int idx1, int idx2) { Exchange(idx1, idx2); }
167 OBJ* First() { return (fCount>0)?fList[0]:NULL; }
168 OBJ* Last() { return (fCount>0)?fList[fCount-1]:NULL;}
169 bool isEmpty() { return fCount==0; }
170 bool notEmpty() { return fCount>0; }
171 int Capacity() { return fCapacity; }
172 int Count() { return fCount; }
173 void setCapacity(int NewCapacity);
174 int Add(OBJ* item); //simply append the pointer copy
175 void Add(GPVec<OBJ>& list); //add all pointers from another list
176 void Insert(int idx, OBJ* item);
177 void Move(int curidx, int newidx);
178 void Put(int idx, OBJ* item);
179 void Pack();
180 void Delete(int index); //also frees the item if fFreeProc!=NULL, and shifts the successor items
181 void Forget(int idx); //simply places a NULL at fList[idx], nothing else
182 int RemovePtr(pointer item); //always use linear search to find the pointer! calls Delete() if found
183 int IndexOf(pointer item); //a linear search for pointer address only!
184 };
185
186 template <class OBJ> class GList:public GPVec<OBJ> {
187 protected:
188 bool fUnique;
189 GCompareProc* fCompareProc; //a pointer to a Compare function
190 static int DefaultCompareProc(const pointer item1, const pointer item2) {
191 //the comparison operators MUST be defined for OBJ class!
192 if (*((OBJ*)item1) > *((OBJ*)item2)) return 1;
193 else if (*((OBJ*)item2) > *((OBJ*)item1)) return -1;
194 else return 0;
195 }
196 void QuickSort(int L, int R);
197 public:
198 void sortInsert(int idx, OBJ* item);
199 GList(GCompareProc* compareProc=NULL); //free by default
200 GList(GCompareProc* compareProc, //unsorted by default
201 GFreeProc *freeProc,
202 bool beUnique=false);
203 GList(bool sorted, bool free_elements=true, bool beUnique=false);
204 GList(int init_capacity, bool sorted, bool free_elements=true, bool beUnique=false);
205 GList(GList<OBJ>& list); //copy constructor?
206 GList(GList<OBJ>* list); //kind of a copy constructor
207 const GList<OBJ>& operator=(GList& list);
208 //void Clear();
209 //~GList();
210 void setSorted(GCompareProc* compareProc);
211 //sorted if compareProc not NULL; sort the list if compareProc changes !
212 bool Sorted() { return fCompareProc!=NULL; }
213 void setSorted(bool sorted) {
214 if (sorted) {
215 if (fCompareProc!=&DefaultCompareProc) {
216 fCompareProc=&DefaultCompareProc;
217 Sort();
218 }
219 }
220 else fCompareProc=NULL;
221 }
222 int Add(OBJ* item); //-- specific implementation if sorted
223 void Add(GList<OBJ>& list); //add all pointers from another list
224
225 OBJ* AddIfNew(OBJ* item, bool deleteIfFound=true, int* fidx=NULL);
226 // default: delete item if Found() (and pointers are not equal)!
227 //returns the equal (==) object if it's in the list already
228 //or the item itself if it is unique and actually added
229
230 int AddedIfNew(OBJ* item);
231 // if Found(item) (and pointers are not equal) delete item and returns -1
232 // if added, returns the new item index
233
234
235 int Unique() { return fUnique; }
236 //this will reject identical items in sorted lists only!
237 void setUnique(bool beUnique) { fUnique = beUnique; };
238
239 GCompareProc* GetCompareProc() {return fCompareProc;}
240 int IndexOf(OBJ* item); //this has a specific implementation for sorted lists
241 //if list is sorted, item data is located by binary search
242 //based on the Compare function
243 //if not, a linear search is performed, but
244 //this needs the == operator to have been defined for OBJ
245
246 void Put(int idx, OBJ* item, bool re_sort=false);
247 bool Found(OBJ* item, int & idx); // sorted only;
248 //search by content; if found, returns true and idx will be the index
249 //of the first item found matching for which GTCompareProc returns 0
250 bool Exists(OBJ* item); //same as above without existing index info
251 bool Exists(OBJ& item); //same as above without existing index info
252 void Sort(); //explicit sort may be requested using this function
253 int Remove(OBJ* item); //search for pointer, using binary search if sorted
254 void Insert(int idx, OBJ* item); //unsorted only, place item at position idx
255 void Move(int curidx, int newidx);
256 }; //GList
257
258
259 //basic template for a Stack of pointers (implemented as a linked list)
260 template <class OBJ> class GStack {
261 protected:
262 struct StackOBJ {
263 OBJ* obj;
264 StackOBJ* prev;
265 };
266 int fCount; //total number of elements in stack
267 StackOBJ* base;
268 StackOBJ* top;
269 public:
270 GStack(OBJ* po=NULL) {
271 base=NULL;
272 top=NULL;
273 fCount=0;
274 if (po!=NULL) Push(po);
275 }
276 ~GStack() {
277 while (fCount>0) Pop();
278 }
279 bool isEmpty() { return fCount==0; }
280 int Size() { return fCount; }
281 int Count() { return fCount; }
282 OBJ* Pop() {
283 if (top==NULL) return NULL;
284 fCount--;
285 StackOBJ* ctop=top;
286 if (top==base) base=NULL;
287 OBJ* r=top->obj;
288 top=top->prev;
289 GFREE(ctop);
290 return r;
291 }
292 OBJ* Push(OBJ* o) {
293 fCount++;
294 StackOBJ* ctop=top; //could be NULL
295 GMALLOC(top, sizeof(StackOBJ));
296 top->obj=o;
297 top->prev=ctop;
298 if (base==NULL) base=top;
299 return o;
300 }
301 OBJ* Top() { return ((top==NULL)? NULL : top->obj); }
302 OBJ* Base() { return ((base==NULL)? NULL : base->obj); }
303 };
304
305 //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
306
307 template <class OBJ> GVec<OBJ>::GVec(int init_capacity) {
308 fCount=0;
309 fCapacity=0;
310 fArray=NULL;
311 setCapacity(init_capacity);
312 }
313
314 template <class OBJ> GVec<OBJ>::GVec(GVec<OBJ>& array) { //copy constructor
315 this->fCount=array.fCount;
316 this->fCapacity=array.fCapacity;
317 this->fArray=NULL;
318 if (this->fCapacity>0) {
319 //GMALLOC(fArray, fCapacity*sizeof(OBJ));
320 fArray=new OBJ[this->fCapacity];
321 }
322 this->fCount=array.fCount;
323 // uses OBJ operator=
324 for (int i=0;i<this->fCount;i++) fArray[i]=array[i];
325 }
326
327 template <class OBJ> GArray<OBJ>::GArray(GArray<OBJ>& array):GVec<OBJ>(0) { //copy constructor
328 this->fCount=array.fCount;
329 this->fCapacity=array.fCapacity;
330 this->fArray=NULL;
331 if (this->fCapacity>0) {
332 //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
333 this->fArray=new OBJ[this->fCapacity];
334 }
335 this->fCount=array.fCount;
336 fUnique=array.fUnique;
337 fCompareProc=array.fCompareProc;
338 // uses OBJ operator=
339 for (int i=0;i<this->fCount;i++) this->fArray[i]=array[i];
340 }
341
342 template <class OBJ> const GVec<OBJ>& GVec<OBJ>::operator=(GVec<OBJ>& array) {
343 if (&array==this) return *this;
344 Clear();
345 fCount=array.fCount;
346 fCapacity=array.fCapacity;
347 if (fCapacity>0) {
348 //GMALLOC(fArray, fCapacity*sizeof(OBJ));
349 fArray=new OBJ[this->fCapacity];
350 }
351 fCount=array.fCount;
352 // uses OBJ operator=
353 for (int i=0;i<fCount;i++) {
354 fArray[i]=array[i];
355 }
356 return *this;
357 }
358
359 template <class OBJ> const GArray<OBJ>& GArray<OBJ>::operator=(GArray<OBJ>& array) {
360 if (&array==this) return *this;
361 GVec<OBJ>::Clear();
362 this->fCount=array.fCount;
363 this->fUnique=array.fUnique;
364 this->fCapacity=array.fCapacity;
365 if (this->fCapacity>0) {
366 //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
367 this->fArray=new OBJ[this->fCapacity];
368 }
369 this->fCompareProc=array.fCompareProc;
370 this->fCount=array.fCount;
371 // uses OBJ operator=
372 for (int i=0;i<this->fCount;i++) {
373 this->fArray[i]=array[i];
374 }
375 return *this;
376 }
377
378 template <class OBJ> GArray<OBJ>::GArray(CompareProc* cmpFunc):GVec<OBJ>(0) {
379 fCompareProc = cmpFunc;
380 fUnique = false; //only affects sorted lists
381 }
382
383 template <class OBJ> GArray<OBJ>::GArray(bool sorted, bool unique):GVec<OBJ>(0) {
384 fUnique=unique;
385 fCompareProc=sorted? &DefaultCompareProc : NULL;
386 }
387
388 template <class OBJ> GArray<OBJ>::GArray(int init_capacity,
389 bool sorted, bool unique):GVec<OBJ>(init_capacity) {
390 fUnique=unique;
391 fCompareProc=sorted? &DefaultCompareProc : NULL;
392 }
393
394 template <class OBJ> GVec<OBJ>::~GVec() {
395 this->Clear();
396 }
397
398
399 template <class OBJ> void GVec<OBJ>::setCapacity(int NewCapacity) {
400 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
401 GError(SLISTCAPACITY_ERR, NewCapacity);
402 //error: capacity not within range
403 if (NewCapacity!=fCapacity) {
404 if (NewCapacity==0) {
405 delete[] fArray;
406 }
407 else {
408 //GREALLOC(fArray, NewCapacity*sizeof(OBJ));
409 OBJ* oldArray=fArray;
410 fArray=new OBJ[NewCapacity];
411 for (int i=0;i<this->fCount;i++) {
412 fArray[i] = oldArray[i];
413 }
414 delete[] oldArray;
415 }
416 fCapacity=NewCapacity;
417 }
418 }
419
420 template <class OBJ> void GVec<OBJ>::Clear() {
421 setCount(0);
422 setCapacity(0); //so the array itself is deallocated too!
423 }
424
425 /*
426 template <class OBJ> void GArray<OBJ>::Clear() {
427 CompareProc* fcmp=fCompareProc;
428 fCompareProc=NULL;
429 GVec<OBJ>::setCount(0);
430 GVec<OBJ>::setCapacity(0); //so the array itself is deallocated too!
431 fCompareProc=fcmp;
432 }
433 */
434 template <class OBJ> void GArray<OBJ>::setSorted(CompareProc* cmpFunc) {
435 CompareProc* old_proc=fCompareProc;
436 fCompareProc=cmpFunc;
437 if (fCompareProc!=old_proc && fCompareProc!=NULL)
438 Sort(); //new compare method
439 }
440
441 template <class OBJ> void GVec<OBJ>::Grow() {
442 int delta;
443 if (fCapacity > 64) delta = fCapacity/4;
444 else if (fCapacity > 8) delta = 16;
445 else delta = 4;
446 setCapacity(fCapacity + delta);
447 }
448
449 template <class OBJ> void GVec<OBJ>::Reverse() {
450 int l=0;
451 int r=fCount-1;
452 OBJ c;
453 while (l<r) {
454 c=fArray[l];fArray[l]=fArray[r];
455 fArray[r]=c;
456 l++;r--;
457 }
458 }
459
460 template <class OBJ> void GVec<OBJ>::Grow(int idx, OBJ& item) {
461 int delta;
462 if (fCapacity > 64) delta = fCapacity/4;
463 else if (fCapacity > 8) delta = 16;
464 else delta = 4;
465 int NewCapacity=fCapacity+delta;
466 if (NewCapacity <= fCount || NewCapacity >= MAXLISTSIZE)
467 GError(SLISTCAPACITY_ERR, NewCapacity);
468 //error: capacity not within range
469
470 if (NewCapacity!=fCapacity) {
471 if (NewCapacity==0) {
472 //GFREE(fArray);
473 delete[] fArray;
474 fArray=NULL;
475 }
476 else { //add the new item
477 if (idx==fCount) { //append item
478 //GREALLOC(fArray, NewCapacity*sizeof(OBJ));
479 setCapacity(NewCapacity);
480 fArray[idx]=item;
481 }
482 else { //insert item at idx
483 OBJ* newList;
484 //GMALLOC(newList, NewCapacity*sizeof(OBJ));
485 newList=new OBJ[NewCapacity];
486 //copy data before idx
487 //memmove(&newList[0],&fArray[0], idx*sizeof(OBJ));
488 // operator= required!
489 for (int i=0;i<idx;i++) {
490 newList[i]=fArray[i];
491 }
492 newList[idx]=item;
493 //copy data after idx
494 //memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
495 for (int i=idx+1;i<=fCount;i++) {
496 newList[i]=fArray[i-1];
497 }
498 //memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ));
499 //data copied:
500 //GFREE(fArray);
501 delete[] fArray;
502 fArray=newList;
503 }
504 fCount++;
505 }
506 fCapacity=NewCapacity;
507 }
508 }
509
510 template <class OBJ> int GArray<OBJ>::IndexOf(OBJ& item) {
511 int result=0;
512 if (Found(item, result)) return result;
513 else return -1;
514 }
515
516 template <class OBJ> bool GArray<OBJ>::Exists(OBJ& item) {
517 int result=0;
518 if (Found(item, result)) return true;
519 else return false;
520 }
521
522
523 template <class OBJ> int GVec<OBJ>::Add(OBJ* item) {
524 if (item==NULL) return -1;
525 int result=fCount;
526 if (result==fCapacity) Grow();
527 fArray[result] = *item; //OBJ::operator= must copy OBJ properly!
528 fCount++;
529 return result;
530 }
531
532 template <class OBJ> int GArray<OBJ>::Add(OBJ* item) {
533 if (item==NULL) return -1;
534 int result;
535 if (SORTED) {
536 if (Found(*item, result))
537 if (fUnique) return -1; //cannot add a duplicate!
538 //Found sets result to the position where the item should be!
539 this->idxInsert(result, *item);
540 }
541 else {
542 if (fUnique && Found(*item,result)) return -1; //set behaviour
543 result = this->fCount;
544 if (result==this->fCapacity) GVec<OBJ>::Grow();
545 this->fArray[result] = *item; //operator=, copies the item
546 this->fCount++;
547 }
548 return result;
549 }
550
551
552 template <class OBJ> void GVec<OBJ>::Add(GVec<OBJ>& list) {
553 if (list.Count()==0) return;
554 //simply copy
555 setCapacity(fCapacity+list.fCount);
556 int s=fCount;
557 for (int i=0;i<list.fCount;i++)
558 fArray[s+i]=list.fArray[i];
559 fCount+=list.fCount;
560 }
561
562
563 template <class OBJ> void GArray<OBJ>::Add(GArray<OBJ>& list) {
564 if (list.Count()==0) return;
565 if (SORTED) {
566 for (int i=0;i<list.fCount;i++) Add(&list[i]);
567 }
568 else { //simply copy
569 this->setCapacity(this->fCapacity+list.fCount);
570 int s=this->fCount;
571 for (int i=0;i<list.fCount;i++)
572 this->fArray[s+i]=list.fArray[i];
573 this->fCount+=list.fCount;
574 }
575 }
576
577 template <class OBJ> bool GArray<OBJ>::Found(OBJ& item, int& idx) {
578 //search the list by using CompareProc (if defined)
579 //or == operator for a non-sortable list
580 //for sorted lists, even when the result is false, the idx is
581 //set to the closest matching object!
582 int i;
583 idx=-1;
584 if (this->fCount==0) { idx=0;return false;}
585 if (SORTED) { //binary search based on CompareProc
586 //do the simplest tests first:
587 if ((*fCompareProc)(this->fArray[0],item)>0) {
588 idx=0;
589 return false;
590 }
591 if ((*fCompareProc)(item, this->fArray[this->fCount-1])>0) {
592 idx=this->fCount;
593 return false;
594 }
595
596 int l=0;
597 int h = this->fCount - 1;
598 int c;
599 while (l <= h) {
600 i = (l + h) >> 1;
601 c = (*fCompareProc)(this->fArray[i], item);
602 if (c < 0) l = i + 1;
603 else {
604 h = i - 1;
605 if (c == 0) { //found!
606 idx=i;
607 return true;
608 }
609 }
610 } //while
611 idx = l;
612 return false;
613 }
614 else {//not sorted: use linear search
615 // needs == operator to compare user defined objects !
616 i=0;
617 while (i<this->fCount) {
618 if (this->fArray[i]==item) { //requires operator==
619 idx=i;
620 return true;
621 }
622 i++;
623 }
624 return false;
625 }
626 }
627
628 template <class OBJ> void GVec<OBJ>::idxInsert(int idx, OBJ& item) {
629 //idx must be the new position this new item must have
630 //so the allowed range is [0..fCount]
631 //the old idx item all the above will be shifted to idx+1
632 if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
633 if (fCount==fCapacity) { //need to resize the array
634 Grow(idx, item); //expand and also copy/move data and insert the new item
635 return;
636 }
637 //move data around to make room for the new item
638 if (idx<fCount) {
639 //copy after-idx items (shift up)
640 //memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
641 for (int i=fCount; i>idx; i--) {
642 fArray[i]=fArray[i-1];
643 }
644 }
645 fArray[idx]=item;
646 fCount++;
647 }
648
649 template <class OBJ> void GVec<OBJ>::Insert(int idx, OBJ* item) {
650 //idx can be [0..fCount] so an item can be actually added
651 idxInsert(idx, item);
652 }
653
654 template <class OBJ> void GArray<OBJ>::Insert(int idx, OBJ* item) {
655 //idx can be [0..fCount] so an item can be actually added
656 BE_UNSORTED; //forbid this operation on sorted data
657 idxInsert(idx, item);
658 }
659
660
661 template <class OBJ> void GVec<OBJ>::Move(int curidx, int newidx) {
662 if (curidx!=newidx || newidx>=fCount)
663 GError(SLISTINDEX_ERR, newidx);
664 OBJ tmp=fArray[curidx]; //copy constructor here
665 fArray[curidx]=fArray[newidx];
666 fArray[newidx]=tmp;
667 }
668
669
670 template <class OBJ> void GArray<OBJ>::Move(int curidx, int newidx) {
671 BE_UNSORTED; //cannot do this in a sorted list!
672 if (curidx!=newidx || newidx>=this->fCount)
673 GError(SLISTINDEX_ERR, newidx);
674
675 OBJ tmp=this->fArray[curidx]; //copy constructor here
676 this->fArray[curidx]=this->fArray[newidx];
677 this->fArray[newidx]=tmp;
678 }
679
680 template <class OBJ> void GVec<OBJ>::Replace(int idx, OBJ& item) {
681 TEST_INDEX(idx);
682 fArray[idx]=item;
683 }
684
685 template <class OBJ> void GVec<OBJ>::Exchange(int idx1, int idx2) {
686 TEST_INDEX(idx1);
687 TEST_INDEX(idx2);
688 OBJ item=fArray[idx1];
689 fArray[idx1]=fArray[idx2];
690 fArray[idx2]=item;
691 }
692
693
694 template <class OBJ> void GArray<OBJ>::Replace(int idx, OBJ& item) {
695 //TEST_INDEX(idx);
696 if (idx<0 || idx>=this->fCount) GError(SLISTINDEX_ERR, __FILE__,__LINE__, idx);
697 this->fArray[idx]=item;
698 if ( SORTED ) Sort(); //re-sort ! this could be very expensive, don't do it
699 }
700
701
702 template <class OBJ> void GVec<OBJ>::Delete(int index) {
703 TEST_INDEX(index);
704 fCount--;
705 while (index<fCount) {
706 //move higher elements if any (shift down)
707 //memmove(&fArray[index], &fArray[index+1], (fCount-index)*sizeof(OBJ));
708 fArray[index]=fArray[index+1];
709 index++;
710 }
711 }
712
713 template <class OBJ> void GVec<OBJ>::setCount(int NewCount) {
714 if (NewCount<0 || NewCount > MAXLISTSIZE)
715 GError(SLISTCOUNT_ERR, NewCount);
716 if (NewCount > fCapacity) setCapacity(NewCount);
717 //if (NewCount > fCount)
718 // memset(&fArray[fCount], 0, (NewCount - fCount) * sizeof(OBJ));
719 fCount = NewCount;
720 }
721
722 template <class OBJ> void GArray<OBJ>::qSort(int l, int r) {
723 int i, j;
724 OBJ p,t;
725 do {
726 i = l; j = r;
727 p = this->fArray[(l + r) >> 1];
728 do {
729 while (fCompareProc(this->fArray[i], p) < 0) i++;
730 while (fCompareProc(this->fArray[j], p) > 0) j--;
731 if (i <= j) {
732 t = this->fArray[i];
733 this->fArray[i] = this->fArray[j];
734 this->fArray[j] = t;
735 i++; j--;
736 }
737 } while (i <= j);
738 if (l < j) qSort(l, j);
739 l = i;
740 } while (i < r);
741 }
742
743 template <class OBJ> void GArray<OBJ>::Sort() {
744 if (this->fArray!=NULL && this->fCount>0 && fCompareProc!=NULL)
745 qSort(0, this->fCount-1);
746 }
747
748 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
749 //*=> GPVec and GList implementation -- sortable array of pointers to OBJ
750
751 template <class OBJ> GPVec<OBJ>::GPVec(GPVec& list) { //copy constructor
752 fCount=list.fCount;
753 fCapacity=list.fCapacity;
754 if (fCapacity>0) {
755 GMALLOC(fList, fCapacity*sizeof(OBJ*));
756 }
757 fFreeProc=list.fFreeProc;
758 fCount=list.fCount;
759 memcpy(fList, list.fList, fCount*sizeof(OBJ*));
760 //for (int i=0;i<list.Count();i++) Add(list[i]);
761 }
762
763 template <class OBJ> GPVec<OBJ>::GPVec(GPVec* plist) { //another copy constructor
764 fCount=0;
765 fCapacity=plist->fCapacity;
766 fList=NULL;
767 if (fCapacity>0) {
768 GMALLOC(fList, fCapacity*sizeof(OBJ*));
769 }
770 fFreeProc=plist->fFreeProc;
771 fCount=plist->fCount;
772 memcpy(fList, plist->fList, fCount*sizeof(OBJ*));
773 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
774 }
775
776 template <class OBJ> const GPVec<OBJ>& GPVec<OBJ>::operator=(GPVec& list) {
777 if (&list!=this) {
778 Clear();
779 fFreeProc=list.fFreeProc;
780 //Attention: the object *POINTERS* are copied,
781 // but the actual object content is NOT duplicated
782 for (int i=0;i<list.Count();i++) Add(list[i]);
783 }
784 return *this;
785 }
786
787
788 template <class OBJ> void GPVec<OBJ>::Add(GPVec<OBJ>& list) {
789 if (list.Count()==0) return;
790 //simply copy the pointers! -- the objects will be shared
791 setCapacity(fCapacity+list.fCount);
792 memcpy( & (fList[fCount]), list.fList, list.fCount*sizeof(OBJ*));
793 fCount+=list.fCount;
794 }
795
796
797 template <class OBJ> GList<OBJ>::GList(GList<OBJ>& list):GPVec<OBJ>(list) { //copy constructor
798 fUnique=list.fUnique;
799 fCompareProc=list.fCompareProc;
800 }
801
802 template <class OBJ> GList<OBJ>::GList(GList<OBJ>* plist):GPVec<OBJ>(0) { //another copy constructor
803 this->fCapacity=plist->fCapacity;
804 this->fList=NULL;
805 if (this->fCapacity>0) {
806 GMALLOC(this->fList, this->fCapacity*sizeof(OBJ*));
807 }
808 fUnique=plist->fUnique;
809 fCompareProc=plist->fCompareProc;
810 this->fFreeProc=plist->fFreeProc;
811 this->fCount=plist->fCount;
812 memcpy(this->fList, plist->fList, this->fCount*sizeof(OBJ*));
813 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
814 }
815
816 template <class OBJ> void GList<OBJ>::Add(GList<OBJ>& list) {
817 if (list.Count()==0) return;
818 if (SORTED) {
819 for (int i=0;i<list.Count();i++) Add(list[i]);
820 }
821 else { //simply copy
822 this->setCapacity(this->fCapacity+list.fCount);
823 memcpy( & (this->fList[this->fCount]), list.fList, list.fCount*sizeof(OBJ*));
824 this->fCount+=list.fCount;
825 }
826 }
827
828
829 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc,
830 GFreeProc* freeProc, bool beUnique) {
831 fCompareProc = compareProc;
832 this->fFreeProc = freeProc;
833 fUnique = beUnique; //only affects sorted lists
834 }
835
836 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
837 fCompareProc = compareProc;
838 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
839 fUnique = false; //only affects sorted lists
840 }
841
842 template <class OBJ> void GPVec<OBJ>::Reverse() {
843 int l=0;
844 int r=fCount-1;
845 OBJ* c;
846 while (l<r) {
847 c=fList[l];fList[l]=fList[r];
848 fList[r]=c;
849 l++;r--;
850 }
851 }
852
853 template <class OBJ> GList<OBJ>::GList(bool sorted,
854 bool free_elements, bool beUnique) {
855 if (sorted) {
856 if (free_elements) {
857 fCompareProc=&DefaultCompareProc;
858 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
859 fUnique=beUnique;
860 }
861 else {
862 fCompareProc=&DefaultCompareProc;
863 this->fFreeProc=NULL;
864 fUnique=beUnique;
865 }
866 }
867 else {
868 if (free_elements) {
869 fCompareProc=NULL;
870 this->fFreeProc=GPVec<OBJ>::DefaultFreeProc;
871 fUnique=beUnique;
872 }
873 else {
874 fCompareProc=NULL;
875 this->fFreeProc=NULL;
876 fUnique=beUnique;
877 }
878 }
879 }
880
881 template <class OBJ> GPVec<OBJ>::GPVec(int init_capacity, bool free_elements) {
882 fCount=0;
883 fCapacity=0;
884 fList=NULL;
885 fFreeProc=(free_elements) ? DefaultFreeProc : NULL;
886 setCapacity(init_capacity);
887 }
888
889
890 template <class OBJ> GList<OBJ>::GList(int init_capacity, bool sorted,
891 bool free_elements, bool beUnique):GPVec<OBJ>(init_capacity, free_elements) {
892 if (sorted) {
893 fCompareProc=&DefaultCompareProc;
894 fUnique=beUnique;
895 }
896 else {
897 fCompareProc=NULL;
898 fUnique=beUnique;
899 }
900 }
901
902 template <class OBJ> GPVec<OBJ>::~GPVec() {
903 this->Clear();//this will free the items if fFreeProc is defined
904 }
905
906 /*
907 template <class OBJ> GList<OBJ>::~GList() {
908 this->Clear();//this will free the items if fFreeProc is defined
909 }
910 */
911
912 template <class OBJ> void GPVec<OBJ>::setCapacity(int NewCapacity) {
913 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
914 GError(SLISTCAPACITY_ERR, NewCapacity);
915 //error: capacity not within range
916 if (NewCapacity!=fCapacity) {
917 if (NewCapacity==0) {
918 GFREE(fList);
919 }
920 else {
921 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
922 }
923 fCapacity=NewCapacity;
924 }
925 }
926
927 template <class OBJ> void GPVec<OBJ>::deallocate_item(OBJ* item) {
928 if (item==NULL) return;
929 if (FREEDATA) {
930 (*fFreeProc)(item);
931 }
932 else {
933 delete item;
934 }
935 }
936
937 template <class OBJ> void GPVec<OBJ>::Clear() {
938 if (FREEDATA) {
939 for (int i=0; i<fCount; i++) {
940 (*fFreeProc)(fList[i]);
941 }
942 }
943 setCount(0);
944 setCapacity(0); //so the array itself is deallocated too!
945 }
946
947 template <class OBJ> void GPVec<OBJ>::Exchange(int idx1, int idx2) {
948 //Warning: this will BREAK sort order for sorted GList
949 TEST_INDEX(idx1);
950 TEST_INDEX(idx2);
951 OBJ* item=fList[idx1];
952 fList[idx1]=fList[idx2];
953 fList[idx2]=item;
954 }
955
956 template <class OBJ> void GPVec<OBJ>::Expand() {
957 if (fCount==fCapacity) Grow();
958 //return this;
959 }
960
961 template <class OBJ> OBJ* GPVec<OBJ>::Get(int idx) {
962 TEST_INDEX(idx);
963 return fList[idx];
964 }
965
966 template <class OBJ> const GList<OBJ>& GList<OBJ>::operator=(GList& list) {
967 if (&list!=this) {
968 GPVec<OBJ>::Clear();
969 fCompareProc=list.fCompareProc;
970 this->fFreeProc=list.fFreeProc;
971 //Attention: the object pointers are copied directly,
972 //but the actual objects are NOT duplicated
973 for (int i=0;i<list.Count();i++) Add(list[i]);
974 }
975 return *this;
976 }
977
978 template <class OBJ> void GList<OBJ>::setSorted(GCompareProc* compareProc) {
979 GCompareProc* old_proc=fCompareProc;
980 fCompareProc=compareProc;
981 if (fCompareProc!=old_proc && fCompareProc!=NULL)
982 Sort(); //new compare method
983 }
984
985 template <class OBJ> void GPVec<OBJ>::Grow() {
986 int delta;
987 if (fCapacity > 64) delta = fCapacity/4;
988 else if (fCapacity > 8) delta = 16;
989 else delta = 4;
990 setCapacity(fCapacity + delta);
991 }
992
993 template <class OBJ> void GPVec<OBJ>::Grow(int idx, OBJ* newitem) {
994 int delta;
995 if (fCapacity > 64) delta = fCapacity/4;
996 else if (fCapacity > 8) delta = 16;
997 else delta = 4;
998 // setCapacity(fCapacity + delta);
999 int NewCapacity=fCapacity+delta;
1000 if (NewCapacity <= fCount || NewCapacity > MAXLISTSIZE)
1001 GError(SLISTCAPACITY_ERR, NewCapacity);
1002 //error: capacity not within range
1003 if (NewCapacity!=fCapacity) {
1004 if (NewCapacity==0) {
1005 GFREE(fList);
1006 }
1007 else {//add the new item
1008 if (idx==fCount) {
1009 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
1010 fList[idx]=newitem;
1011 }
1012 else {
1013 OBJ** newList;
1014 GMALLOC(newList, NewCapacity*sizeof(OBJ*));
1015 //copy data before idx
1016 memmove(&newList[0],&fList[0], idx*sizeof(OBJ*));
1017 newList[idx]=newitem;
1018 //copy data after idx
1019 memmove(&newList[idx+1],&fList[idx], (fCount-idx)*sizeof(OBJ*));
1020 memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ*));
1021 //data copied:
1022 GFREE(fList);
1023 fList=newList;
1024 }
1025 fCount++;
1026 }
1027 fCapacity=NewCapacity;
1028 }
1029 }
1030
1031 template <class OBJ> int GPVec<OBJ>::IndexOf(pointer item) {
1032 int result=-1;
1033 for (int i=0;i<fCount;i++) {
1034 if (item==(pointer)fList[i]) return i;
1035 }
1036 return -1;
1037 }
1038
1039 template <class OBJ> int GList<OBJ>::IndexOf(OBJ* item) {
1040 int result=0;
1041 if (Found(item, result)) return result;
1042 else return -1;
1043 }
1044
1045 template <class OBJ> bool GList<OBJ>::Exists(OBJ& item) {
1046 int result=0;
1047 if (Found(&item, result)) return true;
1048 else return false;
1049 }
1050
1051 template <class OBJ> bool GList<OBJ>::Exists(OBJ* item) {
1052 int result=0;
1053 if (Found(item, result)) return true;
1054 else return false;
1055 }
1056
1057 template <class OBJ> int GPVec<OBJ>::Add(OBJ* item) {
1058 int result;
1059 if (item==NULL) return -1;
1060 result = fCount;
1061 if (result==fCapacity) this->Grow();
1062 fList[result]=item;
1063 fCount++;
1064 return fCount-1;
1065 }
1066
1067 template <class OBJ> int GList<OBJ>::Add(OBJ* item) {
1068 int result;
1069 if (item==NULL) return -1;
1070 if (SORTED) {
1071 if (Found(item, result))
1072 if (fUnique) return -1; //duplicates forbidden
1073 //Found sets result to the position where the item should be!
1074 sortInsert(result, item);
1075 }
1076 else {
1077 if (fUnique && Found(item,result)) return -1; //set behaviour
1078 result = this->fCount;
1079 if (result==this->fCapacity) GPVec<OBJ>::Grow();
1080 this->fList[result]=item;
1081 this->fCount++;
1082 }
1083 return result;
1084 }
1085
1086 //by default, it deletes the item if it has an equal in the list!
1087 //returns the existing equal (==) object if it's in the list already
1088 //or returns the item itself if it's unique (and adds it)
1089 template <class OBJ> OBJ* GList<OBJ>::AddIfNew(OBJ* item,
1090 bool deleteIfFound, int* fidx) {
1091 int r;
1092 if (Found(item, r)) {
1093 if (deleteIfFound && (pointer)item != (pointer)(this->fList[r])) {
1094 this->deallocate_item(item);
1095 }
1096 if (fidx!=NULL) *fidx=r;
1097 return this->fList[r]; //found
1098 }
1099 //not found:
1100 if (SORTED) {
1101 //Found() set result to the position where the item should be inserted:
1102 sortInsert(r, item);
1103 }
1104 else {
1105 r = this->fCount;
1106 if (r==this->fCapacity) GPVec<OBJ>::Grow();
1107 this->fList[r]=item;
1108 this->fCount++;
1109 }
1110 if (fidx!=NULL) *fidx=r;
1111 return item;
1112 }
1113
1114 //if item is found already in the list DELETE it and return -1
1115 //otherwise the item is added and its index is returned
1116 template <class OBJ> int GList<OBJ>::AddedIfNew(OBJ* item) {
1117 int r;
1118 if (Found(item, r)) {
1119 if ((pointer)item != (pointer)(this->fList[r])) {
1120 this->deallocate_item(item);
1121 }
1122 return -1;
1123 }
1124 //not found:
1125 if (SORTED) {
1126 //Found() set r to the position where the item should be inserted:
1127 sortInsert(r, item);
1128 }
1129 else {
1130 r = this->fCount;
1131 if (r==this->fCapacity) GPVec<OBJ>::Grow();
1132 this->fList[r]=item;
1133 this->fCount++;
1134 }
1135 return r;
1136 }
1137
1138
1139 template <class OBJ> bool GList<OBJ>::Found(OBJ* item, int& idx) {
1140 //search the list by using CompareProc (if defined)
1141 //or == operator for a non-sortable list
1142 //for sorted lists, even when the result is false, the idx is
1143 //set to the closest matching object!
1144 int i;
1145 idx=-1;
1146 if (this->fCount==0) { idx=0;return false;}
1147 if (SORTED) { //binary search based on CompareProc
1148 //do the simple test first:
1149
1150 if ((*fCompareProc)(this->fList[0],item)>0) {
1151 idx=0;
1152 return false;
1153 }
1154 if ((*fCompareProc)(item, this->fList[this->fCount-1])>0) {
1155 idx=this->fCount;
1156 return false;
1157 }
1158
1159 int l, h, c;
1160 l = 0;
1161 h = this->fCount - 1;
1162 while (l <= h) {
1163 i = (l + h) >> 1;
1164 c = (*fCompareProc)(this->fList[i], item);
1165 if (c < 0) l = i + 1;
1166 else {
1167 h = i - 1;
1168 if (c == 0) {
1169 idx=i;
1170 return true;
1171 }
1172 }
1173 } //while
1174 idx = l;
1175 return false;
1176 }
1177 else {//not sorted: use linear search
1178 // needs == operator to compare user defined objects !
1179 i=0;
1180 while (i<this->fCount) {
1181 if (*this->fList[i]==*item) {
1182 idx=i;
1183 return true;
1184 }
1185 i++;
1186 }
1187 return false;
1188 }
1189 }
1190
1191 template <class OBJ> void GList<OBJ>::sortInsert(int idx, OBJ* item) {
1192 //idx must be the new position this new item must have
1193 //so the allowed range is [0..fCount]
1194 //the old idx item all the above will be shifted to idx+1
1195 if (idx<0 || idx>this->fCount) GError(SLISTINDEX_ERR, idx);
1196 if (this->fCount==this->fCapacity) {
1197 GPVec<OBJ>::Grow(idx, item);
1198 //expand and also copy/move data and insert the new item
1199 return;
1200 }
1201 //room still left, just move data around and insert the new one
1202 if (idx<this->fCount) //copy/move pointers only!
1203 memmove(&(this->fList[idx+1]), &(this->fList[idx]), (this->fCount-idx)*sizeof(OBJ*));
1204 this->fList[idx]=item;
1205 this->fCount++;
1206 }
1207
1208 template <class OBJ> void GPVec<OBJ>::Insert(int idx, OBJ* item) {
1209 //idx can be [0..fCount] so an item can be actually added
1210 if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
1211 if (fCount==fCapacity) {
1212 Grow(idx, item);
1213 return;
1214 }
1215 if (idx<fCount)
1216 memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
1217 fList[idx]=item;
1218 fCount++;
1219 }
1220
1221 template <class OBJ> void GList<OBJ>::Insert(int idx, OBJ* item) {
1222 //idx can be [0..fCount] so an item can be actually added
1223 BE_UNSORTED; //cannot do that with a sorted list!
1224 GPVec<OBJ>::Insert(idx,item);
1225 }
1226
1227 template <class OBJ> void GPVec<OBJ>::Move(int curidx, int newidx) {
1228 //BE_UNSORTED; //cannot do that in a sorted list!
1229 if (curidx!=newidx || newidx>=fCount)
1230 GError(SLISTINDEX_ERR, newidx);
1231 OBJ* p;
1232 p=Get(curidx);
1233 //this is a delete:
1234 fCount--;
1235 if (curidx<fCount)
1236 memmove(&fList[curidx], &fList[curidx+1], (fCount-curidx)*sizeof(OBJ*));
1237 //-this was instead of delete
1238 Insert(newidx, p);
1239 }
1240
1241 template <class OBJ> void GList<OBJ>::Move(int curidx, int newidx) {
1242 BE_UNSORTED; //cannot do this in a sorted list!
1243 GPVec<OBJ>::Move(curidx,newidx);
1244 }
1245
1246 template <class OBJ> void GPVec<OBJ>::Put(int idx, OBJ* item) {
1247 //WARNING: this will never free the replaced item!
1248 TEST_INDEX(idx);
1249 fList[idx]=item;
1250 }
1251
1252 template <class OBJ> void GList<OBJ>::Put(int idx, OBJ* item, bool re_sort) {
1253 //WARNING: this will never free the replaced item!
1254 // this may BREAK the sort order unless the "re_sort" parameter is given
1255 if (idx<0 || idx>this->fCount) GError(SLISTINDEX_ERR, idx);
1256 this->fList[idx]=item;
1257 if (SORTED && item!=NULL && re_sort) Sort(); //re-sort
1258 }
1259
1260
1261 template <class OBJ> void GPVec<OBJ>::Forget(int idx) {
1262 TEST_INDEX(idx);
1263 fList[idx]=NULL; //user should free that somewhere else
1264 }
1265
1266 template <class OBJ> void GPVec<OBJ>::freeItem(int idx) {
1267 TEST_INDEX(idx);
1268 if (fFreeProc!=NULL) {
1269 (*fFreeProc)(fList[idx]);
1270 }
1271 else this->DefaultFreeProc(fList[idx]);
1272 fList[idx]=NULL;
1273 }
1274
1275 template <class OBJ> void GPVec<OBJ>::Delete(int index) {
1276 TEST_INDEX(index);
1277 if (fFreeProc!=NULL && fList[index]!=NULL) {
1278 (*fFreeProc)(fList[index]); //freeItem
1279 }
1280 fList[index]=NULL;
1281 fCount--;
1282 if (index<fCount) //move higher elements if any
1283 memmove(&fList[index], &fList[index+1], (fCount-index)*sizeof(OBJ*));
1284 }
1285
1286 //Stack usage:
1287 template <class OBJ> OBJ* GPVec<OBJ>::Pop() {
1288 if (fCount<=0) return NULL;
1289 fCount--;
1290 OBJ* o=fList[fCount];
1291 fList[fCount]=NULL;
1292 return o;
1293 }
1294
1295 //Queue usage:
1296 template <class OBJ> OBJ* GPVec<OBJ>::Shift() {
1297 if (fCount<=0) return NULL;
1298 fCount--;
1299 OBJ* o=fList[0];
1300 if (fCount>0)
1301 memmove(&fList[0], &fList[1], (fCount)*sizeof(OBJ*));
1302 fList[fCount]=NULL; //not that it matters..
1303 return o;
1304 }
1305
1306 template <class OBJ> int GList<OBJ>::Remove(OBJ* item) {
1307 //removes an item if it's in our list
1308 int result=IndexOf(item);
1309 if (result>=0) GPVec<OBJ>::Delete(result);
1310 return result;
1311 }
1312
1313 //linear search for the pointer address
1314 template <class OBJ> int GPVec<OBJ>::RemovePtr(pointer item) {
1315 if (item==NULL) return -1;
1316 for (int i=0;i<fCount;i++)
1317 if ((pointer)fList[i] == item) {
1318 Delete(i);
1319 return i;
1320 }
1321 return -1; //not found
1322 }
1323
1324 template <class OBJ> void GPVec<OBJ>::Pack() {//also frees items!
1325 for (int i=fCount-1; i>=0; i--)
1326 if (fList[i]==NULL) Delete(i); //shift rest of fList content accordingly
1327 }
1328
1329 template <class OBJ> void GPVec<OBJ>::setCount(int NewCount) {
1330 if (NewCount<0 || NewCount > MAXLISTSIZE)
1331 GError(SLISTCOUNT_ERR, NewCount);
1332 if (NewCount > fCapacity) setCapacity(NewCount);
1333 if (NewCount > fCount)
1334 memset(fList[fCount], 0, (NewCount - fCount) * sizeof(OBJ*));
1335 fCount = NewCount;
1336 }
1337
1338 template <class OBJ> void GList<OBJ>::QuickSort(int L, int R) {
1339 int I, J;
1340 OBJ* P;
1341 OBJ* T;
1342 do {
1343 I = L;
1344 J = R;
1345 P = this->fList[(L + R) >> 1];
1346 do {
1347 while (fCompareProc(this->fList[I], P) < 0) I++;
1348 while (fCompareProc(this->fList[J], P) > 0) J--;
1349 if (I <= J) {
1350 T = this->fList[I];
1351 this->fList[I] = this->fList[J];
1352 this->fList[J] = T;
1353 I++;
1354 J--;
1355 }
1356 }
1357 while (I <= J);
1358 if (L < J) QuickSort(L, J);
1359 L = I;
1360 }
1361 while (I < R);
1362
1363 }
1364
1365 template <class OBJ> void GList<OBJ>::Sort() {
1366 if (this->fList!=NULL && this->fCount>0 && fCompareProc!=NULL)
1367 QuickSort(0, this->fCount-1);
1368 }
1369
1370 //---------------------------------------------------------------------------
1371 #endif