ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 171
Committed: Tue Feb 14 22:36:26 2012 UTC (7 years, 1 month ago) by gpertea
File size: 41520 byte(s)
Log Message:
wip fqtrim

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