ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 16
Committed: Mon Jul 18 20:56:02 2011 UTC (8 years ago) by gpertea
File size: 40139 byte(s)
Log Message:
sync with local source

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