ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 60
Committed: Fri Sep 9 18:00:55 2011 UTC (7 years, 10 months ago) by gpertea
File size: 40460 byte(s)
Log Message:
made sure Swap (Exchange) is available for GList, GVec

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 fully 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 }
321 this->fCount=array.fCount;
322 // uses OBJ operator=
323 for (int i=0;i<this->fCount;i++) fArray[i]=array[i];
324 }
325
326 template <class OBJ> GArray<OBJ>::GArray(GArray<OBJ>& array):GVec<OBJ>(0) { //copy constructor
327 this->fCount=array.fCount;
328 this->fCapacity=array.fCapacity;
329 this->fArray=NULL;
330 if (this->fCapacity>0) {
331 GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
332 }
333 this->fCount=array.fCount;
334 fUnique=array.fUnique;
335 fCompareProc=array.fCompareProc;
336 // uses OBJ operator=
337 for (int i=0;i<this->fCount;i++) this->fArray[i]=array[i];
338 }
339
340 template <class OBJ> const GVec<OBJ>& GVec<OBJ>::operator=(GVec<OBJ>& array) {
341 if (&array==this) return *this;
342 Clear();
343 fCount=array.fCount;
344 fCapacity=array.fCapacity;
345 if (fCapacity>0) {
346 GMALLOC(fArray, fCapacity*sizeof(OBJ));
347 }
348 fCount=array.fCount;
349 // uses OBJ operator=
350 for (int i=0;i<fCount;i++) {
351 fArray[i]=array[i];
352 }
353 return *this;
354 }
355
356 template <class OBJ> const GArray<OBJ>& GArray<OBJ>::operator=(GArray<OBJ>& array) {
357 if (&array==this) return *this;
358 GVec<OBJ>::Clear();
359 this->fCount=array.fCount;
360 this->fUnique=array.fUnique;
361 this->fCapacity=array.fCapacity;
362 if (this->fCapacity>0) {
363 GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
364 }
365 this->fCompareProc=array.fCompareProc;
366 this->fCount=array.fCount;
367 // uses OBJ operator=
368 for (int i=0;i<this->fCount;i++) {
369 this->fArray[i]=array[i];
370 }
371 return *this;
372 }
373
374 template <class OBJ> GArray<OBJ>::GArray(CompareProc* cmpFunc):GVec<OBJ>(0) {
375 fCompareProc = cmpFunc;
376 fUnique = false; //only affects sorted lists
377 }
378
379 template <class OBJ> GArray<OBJ>::GArray(bool sorted, bool unique):GVec<OBJ>(0) {
380 fUnique=unique;
381 fCompareProc=sorted? &DefaultCompareProc : NULL;
382 }
383
384 template <class OBJ> GArray<OBJ>::GArray(int init_capacity,
385 bool sorted, bool unique):GVec<OBJ>(init_capacity) {
386 fUnique=unique;
387 fCompareProc=sorted? &DefaultCompareProc : NULL;
388 }
389
390 template <class OBJ> GVec<OBJ>::~GVec() {
391 this->Clear();
392 }
393
394
395 template <class OBJ> void GVec<OBJ>::setCapacity(int NewCapacity) {
396 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
397 GError(SLISTCAPACITY_ERR, NewCapacity);
398 //error: capacity not within range
399 if (NewCapacity!=fCapacity) {
400 if (NewCapacity==0) {
401 GFREE(fArray);
402 }
403 else {
404 GREALLOC(fArray, NewCapacity*sizeof(OBJ));
405 }
406 fCapacity=NewCapacity;
407 }
408 }
409
410 template <class OBJ> void GVec<OBJ>::Clear() {
411 setCount(0);
412 setCapacity(0); //so the array itself is deallocated too!
413 }
414
415 /*
416 template <class OBJ> void GArray<OBJ>::Clear() {
417 CompareProc* fcmp=fCompareProc;
418 fCompareProc=NULL;
419 GVec<OBJ>::setCount(0);
420 GVec<OBJ>::setCapacity(0); //so the array itself is deallocated too!
421 fCompareProc=fcmp;
422 }
423 */
424 template <class OBJ> void GArray<OBJ>::setSorted(CompareProc* cmpFunc) {
425 CompareProc* old_proc=fCompareProc;
426 fCompareProc=cmpFunc;
427 if (fCompareProc!=old_proc && fCompareProc!=NULL)
428 Sort(); //new compare method
429 }
430
431 template <class OBJ> void GVec<OBJ>::Grow() {
432 int delta;
433 if (fCapacity > 64) delta = fCapacity/4;
434 else if (fCapacity > 8) delta = 16;
435 else delta = 4;
436 setCapacity(fCapacity + delta);
437 }
438
439 template <class OBJ> void GVec<OBJ>::Reverse() {
440 int l=0;
441 int r=fCount-1;
442 OBJ c;
443 while (l<r) {
444 c=fArray[l];fArray[l]=fArray[r];
445 fArray[r]=c;
446 l++;r--;
447 }
448 }
449
450 template <class OBJ> void GVec<OBJ>::Grow(int idx, OBJ& item) {
451 int delta;
452 if (fCapacity > 64) delta = fCapacity/4;
453 else if (fCapacity > 8) delta = 16;
454 else delta = 4;
455 int NewCapacity=fCapacity+delta;
456 if (NewCapacity <= fCount || NewCapacity >= MAXLISTSIZE)
457 GError(SLISTCAPACITY_ERR, NewCapacity);
458 //error: capacity not within range
459 if (NewCapacity!=fCapacity) {
460 if (NewCapacity==0) {
461 GFREE(fArray);
462 }
463 else { //add the new item
464 if (idx==fCount) { //append item
465 GREALLOC(fArray, NewCapacity*sizeof(OBJ));
466 fArray[idx]=item;
467 }
468 else { //insert item at idx
469 OBJ* newList;
470 GMALLOC(newList, NewCapacity*sizeof(OBJ));
471 //copy data before idx
472 memmove(&newList[0],&fArray[0], idx*sizeof(OBJ));
473 newList[idx]=item; // operator=
474 //copy data after idx
475 memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
476 memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ));
477 //data copied:
478 GFREE(fArray);
479 fArray=newList;
480 }
481 fCount++;
482 }
483 fCapacity=NewCapacity;
484 }
485 }
486
487 template <class OBJ> int GArray<OBJ>::IndexOf(OBJ& item) {
488 int result=0;
489 if (Found(item, result)) return result;
490 else return -1;
491 }
492
493 template <class OBJ> bool GArray<OBJ>::Exists(OBJ& item) {
494 int result=0;
495 if (Found(item, result)) return true;
496 else return false;
497 }
498
499
500 template <class OBJ> int GVec<OBJ>::Add(OBJ* item) {
501 if (item==NULL) return -1;
502 int result=fCount;
503 if (result==fCapacity) Grow();
504 fArray[result] = *item; //OBJ::operator= must copy OBJ properly!
505 fCount++;
506 return result;
507 }
508
509 template <class OBJ> int GArray<OBJ>::Add(OBJ* item) {
510 if (item==NULL) return -1;
511 int result;
512 if (SORTED) {
513 if (Found(*item, result))
514 if (fUnique) return -1; //cannot add a duplicate!
515 //Found sets result to the position where the item should be!
516 this->idxInsert(result, *item);
517 }
518 else {
519 if (fUnique && Found(*item,result)) return -1; //set behaviour
520 result = this->fCount;
521 if (result==this->fCapacity) GVec<OBJ>::Grow();
522 this->fArray[result] = *item; //operator=, copies the item
523 this->fCount++;
524 }
525 return result;
526 }
527
528
529 template <class OBJ> void GVec<OBJ>::Add(GVec<OBJ>& list) {
530 if (list.Count()==0) return;
531 //simply copy
532 setCapacity(fCapacity+list.fCount);
533 int s=fCount;
534 for (int i=0;i<list.fCount;i++)
535 fArray[s+i]=list.fArray[i];
536 fCount+=list.fCount;
537 }
538
539
540 template <class OBJ> void GArray<OBJ>::Add(GArray<OBJ>& list) {
541 if (list.Count()==0) return;
542 if (SORTED) {
543 for (int i=0;i<list.fCount;i++) Add(&list[i]);
544 }
545 else { //simply copy
546 this->setCapacity(this->fCapacity+list.fCount);
547 int s=this->fCount;
548 for (int i=0;i<list.fCount;i++)
549 this->fArray[s+i]=list.fArray[i];
550 this->fCount+=list.fCount;
551 }
552 }
553
554 template <class OBJ> bool GArray<OBJ>::Found(OBJ& item, int& idx) {
555 //search the list by using CompareProc (if defined)
556 //or == operator for a non-sortable list
557 //for sorted lists, even when the result is false, the idx is
558 //set to the closest matching object!
559 int i;
560 idx=-1;
561 if (this->fCount==0) { idx=0;return false;}
562 if (SORTED) { //binary search based on CompareProc
563 //do the simplest tests first:
564 if ((*fCompareProc)(this->fArray[0],item)>0) {
565 idx=0;
566 return false;
567 }
568 if ((*fCompareProc)(item, this->fArray[this->fCount-1])>0) {
569 idx=this->fCount;
570 return false;
571 }
572
573 int l=0;
574 int h = this->fCount - 1;
575 int c;
576 while (l <= h) {
577 i = (l + h) >> 1;
578 c = (*fCompareProc)(this->fArray[i], item);
579 if (c < 0) l = i + 1;
580 else {
581 h = i - 1;
582 if (c == 0) { //found!
583 idx=i;
584 return true;
585 }
586 }
587 } //while
588 idx = l;
589 return false;
590 }
591 else {//not sorted: use linear search
592 // needs == operator to compare user defined objects !
593 i=0;
594 while (i<this->fCount) {
595 if (this->fArray[i]==item) { //requires operator==
596 idx=i;
597 return true;
598 }
599 i++;
600 }
601 return false;
602 }
603 }
604
605 template <class OBJ> void GVec<OBJ>::idxInsert(int idx, OBJ& item) {
606 //idx must be the new position this new item must have
607 //so the allowed range is [0..fCount]
608 //the old idx item all the above will be shifted to idx+1
609 if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
610 if (fCount==fCapacity) { //need to resize
611 Grow(idx, item);
612 //expand and also copy/move data and insert the new item
613 return;
614 }
615 //move data around to make room for the new item
616 if (idx<fCount)
617 memmove(&fArray[idx+1], &fArray[idx], (fCount-idx)*sizeof(OBJ));
618 fArray[idx]=item;
619 fCount++;
620 }
621
622 template <class OBJ> void GVec<OBJ>::Insert(int idx, OBJ* item) {
623 //idx can be [0..fCount] so an item can be actually added
624 idxInsert(idx, item);
625 }
626
627 template <class OBJ> void GArray<OBJ>::Insert(int idx, OBJ* item) {
628 //idx can be [0..fCount] so an item can be actually added
629 BE_UNSORTED; //forbid this operation on sorted data
630 idxInsert(idx, item);
631 }
632
633
634 template <class OBJ> void GVec<OBJ>::Move(int curidx, int newidx) {
635 if (curidx!=newidx || newidx>=fCount)
636 GError(SLISTINDEX_ERR, newidx);
637 OBJ tmp=fArray[curidx]; //copy constructor here
638 fArray[curidx]=fArray[newidx];
639 fArray[newidx]=tmp;
640 }
641
642
643 template <class OBJ> void GArray<OBJ>::Move(int curidx, int newidx) {
644 BE_UNSORTED; //cannot do this in a sorted list!
645 if (curidx!=newidx || newidx>=this->fCount)
646 GError(SLISTINDEX_ERR, newidx);
647
648 OBJ tmp=this->fArray[curidx]; //copy constructor here
649 this->fArray[curidx]=this->fArray[newidx];
650 this->fArray[newidx]=tmp;
651 }
652
653 template <class OBJ> void GVec<OBJ>::Replace(int idx, OBJ& item) {
654 TEST_INDEX(idx);
655 fArray[idx]=item;
656 }
657
658 template <class OBJ> void GVec<OBJ>::Exchange(int idx1, int idx2) {
659 TEST_INDEX(idx1);
660 TEST_INDEX(idx2);
661 OBJ item=fArray[idx1];
662 fArray[idx1]=fArray[idx2];
663 fArray[idx2]=item;
664 }
665
666
667 template <class OBJ> void GArray<OBJ>::Replace(int idx, OBJ& item) {
668 //TEST_INDEX(idx);
669 if (idx<0 || idx>=this->fCount) GError(SLISTINDEX_ERR, __FILE__,__LINE__, idx);
670 this->fArray[idx]=item;
671 if ( SORTED ) Sort(); //re-sort ! this could be very expensive, don't do it
672 }
673
674
675 template <class OBJ> void GVec<OBJ>::Delete(int index) {
676 TEST_INDEX(index);
677 //fArray[index]=NULL;
678 fCount--;
679 if (index<fCount) //move higher elements if any
680 memmove(&fArray[index], &fArray[index+1], (fCount-index)*sizeof(OBJ));
681 }
682
683 template <class OBJ> void GVec<OBJ>::setCount(int NewCount) {
684 if (NewCount<0 || NewCount > MAXLISTSIZE)
685 GError(SLISTCOUNT_ERR, NewCount);
686 if (NewCount > fCapacity) setCapacity(NewCount);
687 if (NewCount > fCount)
688 memset(&fArray[fCount], 0, (NewCount - fCount) * sizeof(OBJ));
689 fCount = NewCount;
690 }
691
692 template <class OBJ> void GArray<OBJ>::qSort(int l, int r) {
693 int i, j;
694 OBJ p,t;
695 do {
696 i = l; j = r;
697 p = this->fArray[(l + r) >> 1];
698 do {
699 while (fCompareProc(this->fArray[i], p) < 0) i++;
700 while (fCompareProc(this->fArray[j], p) > 0) j--;
701 if (i <= j) {
702 t = this->fArray[i];
703 this->fArray[i] = this->fArray[j];
704 this->fArray[j] = t;
705 i++; j--;
706 }
707 } while (i <= j);
708 if (l < j) qSort(l, j);
709 l = i;
710 } while (i < r);
711 }
712
713 template <class OBJ> void GArray<OBJ>::Sort() {
714 if (this->fArray!=NULL && this->fCount>0 && fCompareProc!=NULL)
715 qSort(0, this->fCount-1);
716 }
717
718 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
719 //*=> GPVec and GList implementation -- sortable array of pointers to OBJ
720
721 template <class OBJ> GPVec<OBJ>::GPVec(GPVec& list) { //copy constructor
722 fCount=list.fCount;
723 fCapacity=list.fCapacity;
724 if (fCapacity>0) {
725 GMALLOC(fList, fCapacity*sizeof(OBJ*));
726 }
727 fFreeProc=list.fFreeProc;
728 fCount=list.fCount;
729 memcpy(fList, list.fList, fCount*sizeof(OBJ*));
730 //for (int i=0;i<list.Count();i++) Add(list[i]);
731 }
732
733 template <class OBJ> GPVec<OBJ>::GPVec(GPVec* plist) { //another copy constructor
734 fCount=0;
735 fCapacity=plist->fCapacity;
736 fList=NULL;
737 if (fCapacity>0) {
738 GMALLOC(fList, fCapacity*sizeof(OBJ*));
739 }
740 fFreeProc=plist->fFreeProc;
741 fCount=plist->fCount;
742 memcpy(fList, plist->fList, fCount*sizeof(OBJ*));
743 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
744 }
745
746 template <class OBJ> const GPVec<OBJ>& GPVec<OBJ>::operator=(GPVec& list) {
747 if (&list!=this) {
748 Clear();
749 fFreeProc=list.fFreeProc;
750 //Attention: the object *POINTERS* are copied,
751 // but the actual object content is NOT duplicated
752 for (int i=0;i<list.Count();i++) Add(list[i]);
753 }
754 return *this;
755 }
756
757
758 template <class OBJ> void GPVec<OBJ>::Add(GPVec<OBJ>& list) {
759 if (list.Count()==0) return;
760 //simply copy the pointers! -- the objects will be shared
761 setCapacity(fCapacity+list.fCount);
762 memcpy( & (fList[fCount]), list.fList, list.fCount*sizeof(OBJ*));
763 fCount+=list.fCount;
764 }
765
766
767 template <class OBJ> GList<OBJ>::GList(GList<OBJ>& list):GPVec<OBJ>(list) { //copy constructor
768 fUnique=list.fUnique;
769 fCompareProc=list.fCompareProc;
770 }
771
772 template <class OBJ> GList<OBJ>::GList(GList<OBJ>* plist):GPVec<OBJ>(0) { //another copy constructor
773 this->fCapacity=plist->fCapacity;
774 this->fList=NULL;
775 if (this->fCapacity>0) {
776 GMALLOC(this->fList, this->fCapacity*sizeof(OBJ*));
777 }
778 fUnique=plist->fUnique;
779 fCompareProc=plist->fCompareProc;
780 this->fFreeProc=plist->fFreeProc;
781 this->fCount=plist->fCount;
782 memcpy(this->fList, plist->fList, this->fCount*sizeof(OBJ*));
783 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
784 }
785
786 template <class OBJ> void GList<OBJ>::Add(GList<OBJ>& list) {
787 if (list.Count()==0) return;
788 if (SORTED) {
789 for (int i=0;i<list.Count();i++) Add(list[i]);
790 }
791 else { //simply copy
792 this->setCapacity(this->fCapacity+list.fCount);
793 memcpy( & (this->fList[this->fCount]), list.fList, list.fCount*sizeof(OBJ*));
794 this->fCount+=list.fCount;
795 }
796 }
797
798
799 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc,
800 GFreeProc* freeProc, bool beUnique) {
801 fCompareProc = compareProc;
802 this->fFreeProc = freeProc;
803 fUnique = beUnique; //only affects sorted lists
804 }
805
806 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
807 fCompareProc = compareProc;
808 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
809 fUnique = false; //only affects sorted lists
810 }
811
812 template <class OBJ> void GPVec<OBJ>::Reverse() {
813 int l=0;
814 int r=fCount-1;
815 OBJ* c;
816 while (l<r) {
817 c=fList[l];fList[l]=fList[r];
818 fList[r]=c;
819 l++;r--;
820 }
821 }
822
823 template <class OBJ> GList<OBJ>::GList(bool sorted,
824 bool free_elements, bool beUnique) {
825 if (sorted) {
826 if (free_elements) {
827 fCompareProc=&DefaultCompareProc;
828 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
829 fUnique=beUnique;
830 }
831 else {
832 fCompareProc=&DefaultCompareProc;
833 this->fFreeProc=NULL;
834 fUnique=beUnique;
835 }
836 }
837 else {
838 if (free_elements) {
839 fCompareProc=NULL;
840 this->fFreeProc=GPVec<OBJ>::DefaultFreeProc;
841 fUnique=beUnique;
842 }
843 else {
844 fCompareProc=NULL;
845 this->fFreeProc=NULL;
846 fUnique=beUnique;
847 }
848 }
849 }
850
851 template <class OBJ> GPVec<OBJ>::GPVec(int init_capacity, bool free_elements) {
852 fCount=0;
853 fCapacity=0;
854 fList=NULL;
855 fFreeProc=(free_elements) ? DefaultFreeProc : NULL;
856 setCapacity(init_capacity);
857 }
858
859
860 template <class OBJ> GList<OBJ>::GList(int init_capacity, bool sorted,
861 bool free_elements, bool beUnique):GPVec<OBJ>(init_capacity, free_elements) {
862 if (sorted) {
863 fCompareProc=&DefaultCompareProc;
864 fUnique=beUnique;
865 }
866 else {
867 fCompareProc=NULL;
868 fUnique=beUnique;
869 }
870 }
871
872 template <class OBJ> GPVec<OBJ>::~GPVec() {
873 this->Clear();//this will free the items if fFreeProc is defined
874 }
875
876 /*
877 template <class OBJ> GList<OBJ>::~GList() {
878 this->Clear();//this will free the items if fFreeProc is defined
879 }
880 */
881
882 template <class OBJ> void GPVec<OBJ>::setCapacity(int NewCapacity) {
883 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
884 GError(SLISTCAPACITY_ERR, NewCapacity);
885 //error: capacity not within range
886 if (NewCapacity!=fCapacity) {
887 if (NewCapacity==0) {
888 GFREE(fList);
889 }
890 else {
891 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
892 }
893 fCapacity=NewCapacity;
894 }
895 }
896
897 template <class OBJ> void GPVec<OBJ>::deallocate_item(OBJ* item) {
898 if (item==NULL) return;
899 if (FREEDATA) {
900 (*fFreeProc)(item);
901 }
902 else {
903 delete item;
904 }
905 }
906
907 template <class OBJ> void GPVec<OBJ>::Clear() {
908 if (FREEDATA) {
909 for (int i=0; i<fCount; i++) {
910 (*fFreeProc)(fList[i]);
911 }
912 }
913 setCount(0);
914 setCapacity(0); //so the array itself is deallocated too!
915 }
916
917 template <class OBJ> void GPVec<OBJ>::Exchange(int idx1, int idx2) {
918 //Warning: this will BREAK sort order for sorted GList
919 TEST_INDEX(idx1);
920 TEST_INDEX(idx2);
921 OBJ* item=fList[idx1];
922 fList[idx1]=fList[idx2];
923 fList[idx2]=item;
924 }
925
926 template <class OBJ> void GPVec<OBJ>::Expand() {
927 if (fCount==fCapacity) Grow();
928 //return this;
929 }
930
931 template <class OBJ> OBJ* GPVec<OBJ>::Get(int idx) {
932 TEST_INDEX(idx);
933 return fList[idx];
934 }
935
936 template <class OBJ> const GList<OBJ>& GList<OBJ>::operator=(GList& list) {
937 if (&list!=this) {
938 GPVec<OBJ>::Clear();
939 fCompareProc=list.fCompareProc;
940 this->fFreeProc=list.fFreeProc;
941 //Attention: the object pointers are copied directly,
942 //but the actual objects are NOT duplicated
943 for (int i=0;i<list.Count();i++) Add(list[i]);
944 }
945 return *this;
946 }
947
948 template <class OBJ> void GList<OBJ>::setSorted(GCompareProc* compareProc) {
949 GCompareProc* old_proc=fCompareProc;
950 fCompareProc=compareProc;
951 if (fCompareProc!=old_proc && fCompareProc!=NULL)
952 Sort(); //new compare method
953 }
954
955 template <class OBJ> void GPVec<OBJ>::Grow() {
956 int delta;
957 if (fCapacity > 64) delta = fCapacity/4;
958 else if (fCapacity > 8) delta = 16;
959 else delta = 4;
960 setCapacity(fCapacity + delta);
961 }
962
963 template <class OBJ> void GPVec<OBJ>::Grow(int idx, OBJ* newitem) {
964 int delta;
965 if (fCapacity > 64) delta = fCapacity/4;
966 else if (fCapacity > 8) delta = 16;
967 else delta = 4;
968 // setCapacity(fCapacity + delta);
969 int NewCapacity=fCapacity+delta;
970 if (NewCapacity <= fCount || NewCapacity > MAXLISTSIZE)
971 GError(SLISTCAPACITY_ERR, NewCapacity);
972 //error: capacity not within range
973 if (NewCapacity!=fCapacity) {
974 if (NewCapacity==0) {
975 GFREE(fList);
976 }
977 else {//add the new item
978 if (idx==fCount) {
979 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
980 fList[idx]=newitem;
981 }
982 else {
983 OBJ** newList;
984 GMALLOC(newList, NewCapacity*sizeof(OBJ*));
985 //copy data before idx
986 memmove(&newList[0],&fList[0], idx*sizeof(OBJ*));
987 newList[idx]=newitem;
988 //copy data after idx
989 memmove(&newList[idx+1],&fList[idx], (fCount-idx)*sizeof(OBJ*));
990 memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ*));
991 //data copied:
992 GFREE(fList);
993 fList=newList;
994 }
995 fCount++;
996 }
997 fCapacity=NewCapacity;
998 }
999 }
1000
1001 template <class OBJ> int GPVec<OBJ>::IndexOf(pointer item) {
1002 int result=-1;
1003 for (int i=0;i<fCount;i++) {
1004 if (item==(pointer)fList[i]) return i;
1005 }
1006 return -1;
1007 }
1008
1009 template <class OBJ> int GList<OBJ>::IndexOf(OBJ* item) {
1010 int result=0;
1011 if (Found(item, result)) return result;
1012 else return -1;
1013 }
1014
1015 template <class OBJ> bool GList<OBJ>::Exists(OBJ& item) {
1016 int result=0;
1017 if (Found(&item, result)) return true;
1018 else return false;
1019 }
1020
1021 template <class OBJ> bool GList<OBJ>::Exists(OBJ* item) {
1022 int result=0;
1023 if (Found(item, result)) return true;
1024 else return false;
1025 }
1026
1027 template <class OBJ> int GPVec<OBJ>::Add(OBJ* item) {
1028 int result;
1029 if (item==NULL) return -1;
1030 result = fCount;
1031 if (result==fCapacity) this->Grow();
1032 fList[result]=item;
1033 fCount++;
1034 return fCount-1;
1035 }
1036
1037 template <class OBJ> int GList<OBJ>::Add(OBJ* item) {
1038 int result;
1039 if (item==NULL) return -1;
1040 if (SORTED) {
1041 if (Found(item, result))
1042 if (fUnique) return -1; //duplicates forbidden
1043 //Found sets result to the position where the item should be!
1044 sortInsert(result, item);
1045 }
1046 else {
1047 if (fUnique && Found(item,result)) return -1; //set behaviour
1048 result = this->fCount;
1049 if (result==this->fCapacity) GPVec<OBJ>::Grow();
1050 this->fList[result]=item;
1051 this->fCount++;
1052 }
1053 return result;
1054 }
1055
1056 //by default, it deletes the item if it has an equal in the list!
1057 //returns the existing equal (==) object if it's in the list already
1058 //or returns the item itself if it's unique (and adds it)
1059 template <class OBJ> OBJ* GList<OBJ>::AddIfNew(OBJ* item,
1060 bool deleteIfFound, int* fidx) {
1061 int r;
1062 if (Found(item, r)) {
1063 if (deleteIfFound && (pointer)item != (pointer)(this->fList[r])) {
1064 this->deallocate_item(item);
1065 }
1066 if (fidx!=NULL) *fidx=r;
1067 return this->fList[r]; //found
1068 }
1069 //not found:
1070 if (SORTED) {
1071 //Found() set result to the position where the item should be inserted:
1072 sortInsert(r, item);
1073 }
1074 else {
1075 r = this->fCount;
1076 if (r==this->fCapacity) GPVec<OBJ>::Grow();
1077 this->fList[r]=item;
1078 this->fCount++;
1079 }
1080 if (fidx!=NULL) *fidx=r;
1081 return item;
1082 }
1083
1084 //if item is found already in the list DELETE it and return -1
1085 //otherwise the item is added and its index is returned
1086 template <class OBJ> int GList<OBJ>::AddedIfNew(OBJ* item) {
1087 int r;
1088 if (Found(item, r)) {
1089 if ((pointer)item != (pointer)(this->fList[r])) {
1090 this->deallocate_item(item);
1091 }
1092 return -1;
1093 }
1094 //not found:
1095 if (SORTED) {
1096 //Found() set r to the position where the item should be inserted:
1097 sortInsert(r, item);
1098 }
1099 else {
1100 r = this->fCount;
1101 if (r==this->fCapacity) GPVec<OBJ>::Grow();
1102 this->fList[r]=item;
1103 this->fCount++;
1104 }
1105 return r;
1106 }
1107
1108
1109 template <class OBJ> bool GList<OBJ>::Found(OBJ* item, int& idx) {
1110 //search the list by using CompareProc (if defined)
1111 //or == operator for a non-sortable list
1112 //for sorted lists, even when the result is false, the idx is
1113 //set to the closest matching object!
1114 int i;
1115 idx=-1;
1116 if (this->fCount==0) { idx=0;return false;}
1117 if (SORTED) { //binary search based on CompareProc
1118 //do the simple test first:
1119
1120 if ((*fCompareProc)(this->fList[0],item)>0) {
1121 idx=0;
1122 return false;
1123 }
1124 if ((*fCompareProc)(item, this->fList[this->fCount-1])>0) {
1125 idx=this->fCount;
1126 return false;
1127 }
1128
1129 int l, h, c;
1130 l = 0;
1131 h = this->fCount - 1;
1132 while (l <= h) {
1133 i = (l + h) >> 1;
1134 c = (*fCompareProc)(this->fList[i], item);
1135 if (c < 0) l = i + 1;
1136 else {
1137 h = i - 1;
1138 if (c == 0) {
1139 idx=i;
1140 return true;
1141 }
1142 }
1143 } //while
1144 idx = l;
1145 return false;
1146 }
1147 else {//not sorted: use linear search
1148 // needs == operator to compare user defined objects !
1149 i=0;
1150 while (i<this->fCount) {
1151 if (*this->fList[i]==*item) {
1152 idx=i;
1153 return true;
1154 }
1155 i++;
1156 }
1157 return false;
1158 }
1159 }
1160
1161 template <class OBJ> void GList<OBJ>::sortInsert(int idx, OBJ* item) {
1162 //idx must be the new position this new item must have
1163 //so the allowed range is [0..fCount]
1164 //the old idx item all the above will be shifted to idx+1
1165 if (idx<0 || idx>this->fCount) GError(SLISTINDEX_ERR, idx);
1166 if (this->fCount==this->fCapacity) {
1167 GPVec<OBJ>::Grow(idx, item);
1168 //expand and also copy/move data and insert the new item
1169 return;
1170 }
1171 //room still left, just move data around and insert the new one
1172 if (idx<this->fCount) //copy/move pointers only!
1173 memmove(&(this->fList[idx+1]), &(this->fList[idx]), (this->fCount-idx)*sizeof(OBJ*));
1174 this->fList[idx]=item;
1175 this->fCount++;
1176 }
1177
1178 template <class OBJ> void GPVec<OBJ>::Insert(int idx, OBJ* item) {
1179 //idx can be [0..fCount] so an item can be actually added
1180 if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
1181 if (fCount==fCapacity) {
1182 Grow(idx, item);
1183 return;
1184 }
1185 if (idx<fCount)
1186 memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
1187 fList[idx]=item;
1188 fCount++;
1189 }
1190
1191 template <class OBJ> void GList<OBJ>::Insert(int idx, OBJ* item) {
1192 //idx can be [0..fCount] so an item can be actually added
1193 BE_UNSORTED; //cannot do that with a sorted list!
1194 GPVec<OBJ>::Insert(idx,item);
1195 }
1196
1197 template <class OBJ> void GPVec<OBJ>::Move(int curidx, int newidx) {
1198 //BE_UNSORTED; //cannot do that in a sorted list!
1199 if (curidx!=newidx || newidx>=fCount)
1200 GError(SLISTINDEX_ERR, newidx);
1201 OBJ* p;
1202 p=Get(curidx);
1203 //this is a delete:
1204 fCount--;
1205 if (curidx<fCount)
1206 memmove(&fList[curidx], &fList[curidx+1], (fCount-curidx)*sizeof(OBJ*));
1207 //-this was instead of delete
1208 Insert(newidx, p);
1209 }
1210
1211 template <class OBJ> void GList<OBJ>::Move(int curidx, int newidx) {
1212 BE_UNSORTED; //cannot do this in a sorted list!
1213 GPVec<OBJ>::Move(curidx,newidx);
1214 }
1215
1216 template <class OBJ> void GPVec<OBJ>::Put(int idx, OBJ* item) {
1217 //WARNING: this will never free the replaced item!
1218 TEST_INDEX(idx);
1219 fList[idx]=item;
1220 }
1221
1222 template <class OBJ> void GList<OBJ>::Put(int idx, OBJ* item, bool re_sort) {
1223 //WARNING: this will never free the replaced item!
1224 // this may BREAK the sort order unless the "re_sort" parameter is given
1225 if (idx<0 || idx>this->fCount) GError(SLISTINDEX_ERR, idx);
1226 this->fList[idx]=item;
1227 if (SORTED && item!=NULL && re_sort) Sort(); //re-sort
1228 }
1229
1230
1231 template <class OBJ> void GPVec<OBJ>::Forget(int idx) {
1232 TEST_INDEX(idx);
1233 fList[idx]=NULL; //user should free that somewhere else
1234 }
1235
1236 template <class OBJ> void GPVec<OBJ>::freeItem(int idx) {
1237 TEST_INDEX(idx);
1238 if (fFreeProc!=NULL) {
1239 (*fFreeProc)(fList[idx]);
1240 }
1241 else this->DefaultFreeProc(fList[idx]);
1242 fList[idx]=NULL;
1243 }
1244
1245 template <class OBJ> void GPVec<OBJ>::Delete(int index) {
1246 TEST_INDEX(index);
1247 if (fFreeProc!=NULL && fList[index]!=NULL) {
1248 (*fFreeProc)(fList[index]); //freeItem
1249 }
1250 fList[index]=NULL;
1251 fCount--;
1252 if (index<fCount) //move higher elements if any
1253 memmove(&fList[index], &fList[index+1], (fCount-index)*sizeof(OBJ*));
1254 }
1255
1256 //Stack usage:
1257 template <class OBJ> OBJ* GPVec<OBJ>::Pop() {
1258 if (fCount<=0) return NULL;
1259 fCount--;
1260 OBJ* o=fList[fCount];
1261 fList[fCount]=NULL;
1262 return o;
1263 }
1264
1265 //Queue usage:
1266 template <class OBJ> OBJ* GPVec<OBJ>::Shift() {
1267 if (fCount<=0) return NULL;
1268 fCount--;
1269 OBJ* o=fList[0];
1270 if (fCount>0)
1271 memmove(&fList[0], &fList[1], (fCount)*sizeof(OBJ*));
1272 fList[fCount]=NULL; //not that it matters..
1273 return o;
1274 }
1275
1276 template <class OBJ> int GList<OBJ>::Remove(OBJ* item) {
1277 //removes an item if it's in our list
1278 int result=IndexOf(item);
1279 if (result>=0) GPVec<OBJ>::Delete(result);
1280 return result;
1281 }
1282
1283 //linear search for the pointer address
1284 template <class OBJ> int GPVec<OBJ>::RemovePtr(pointer item) {
1285 if (item==NULL) return -1;
1286 for (int i=0;i<fCount;i++)
1287 if ((pointer)fList[i] == item) {
1288 Delete(i);
1289 return i;
1290 }
1291 return -1; //not found
1292 }
1293
1294 template <class OBJ> void GPVec<OBJ>::Pack() {//also frees items!
1295 for (int i=fCount-1; i>=0; i--)
1296 if (fList[i]==NULL) Delete(i); //shift rest of fList content accordingly
1297 }
1298
1299 template <class OBJ> void GPVec<OBJ>::setCount(int NewCount) {
1300 if (NewCount<0 || NewCount > MAXLISTSIZE)
1301 GError(SLISTCOUNT_ERR, NewCount);
1302 if (NewCount > fCapacity) setCapacity(NewCount);
1303 if (NewCount > fCount)
1304 memset(fList[fCount], 0, (NewCount - fCount) * sizeof(OBJ*));
1305 fCount = NewCount;
1306 }
1307
1308 template <class OBJ> void GList<OBJ>::QuickSort(int L, int R) {
1309 int I, J;
1310 OBJ* P;
1311 OBJ* T;
1312 do {
1313 I = L;
1314 J = R;
1315 P = this->fList[(L + R) >> 1];
1316 do {
1317 while (fCompareProc(this->fList[I], P) < 0) I++;
1318 while (fCompareProc(this->fList[J], P) > 0) J--;
1319 if (I <= J) {
1320 T = this->fList[I];
1321 this->fList[I] = this->fList[J];
1322 this->fList[J] = T;
1323 I++;
1324 J--;
1325 }
1326 }
1327 while (I <= J);
1328 if (L < J) QuickSort(L, J);
1329 L = I;
1330 }
1331 while (I < R);
1332
1333 }
1334
1335 template <class OBJ> void GList<OBJ>::Sort() {
1336 if (this->fList!=NULL && this->fCount>0 && fCompareProc!=NULL)
1337 QuickSort(0, this->fCount-1);
1338 }
1339
1340 //---------------------------------------------------------------------------
1341 #endif