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 (7 years, 11 months ago) by gpertea
File size: 40139 byte(s)
Log Message:
sync with local source

Line User Rev File contents
1 gpertea 2 //---------------------------------------------------------------------------
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 gpertea 16
12 gpertea 2 #ifdef __LINE__
13 gpertea 16 #define SLISTINDEX_ERR "GList error (%s:%d):Invalid list index: %d\n"
14 gpertea 2 #define TEST_INDEX(x) \
15     if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, __FILE__,__LINE__, x)
16     #else
17 gpertea 16 #define SLISTINDEX_ERR "GList error:Invalid list index: %d\n"
18 gpertea 2 #define TEST_INDEX(x) \
19     if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x, __FILE__,__LINE__)
20     #endif
21    
22 gpertea 16 #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 gpertea 2
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 gpertea 16 //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 gpertea 2 protected:
44     OBJ* fArray;
45     int fCount;
46     int fCapacity;
47 gpertea 16 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 gpertea 2 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 gpertea 16 //~GArray();
103 gpertea 2 //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 gpertea 16 void Replace(int idx, OBJ& item); //Put, use operator= to copy
115     int Unique() { return fUnique; }
116 gpertea 2 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 gpertea 16 void Move(int curidx, int newidx);
124 gpertea 2 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 gpertea 16 template <class OBJ> class GPVec {
130 gpertea 2 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 gpertea 16 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 gpertea 2 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 gpertea 16 const GList<OBJ>& operator=(GList& list);
207     //void Clear();
208     //~GList();
209 gpertea 2 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 gpertea 16 //or the item itself if it is unique and actually added
228 gpertea 2
229 gpertea 16 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 gpertea 2 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 gpertea 16
245     void Put(int idx, OBJ* item, bool re_sort=false);
246 gpertea 2 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 gpertea 16 void Sort(); //explicit sort may be requested using this function
252     int Remove(OBJ* item); //search for pointer, using binary search if sorted
253 gpertea 2 void Insert(int idx, OBJ* item); //unsorted only, place item at position idx
254     void Move(int curidx, int newidx);
255 gpertea 16 }; //GList
256 gpertea 2
257    
258 gpertea 16 //basic template for a Stack of pointers (implemented as a linked list)
259 gpertea 2 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 gpertea 16 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 gpertea 2 GMALLOC(fArray, fCapacity*sizeof(OBJ));
319     }
320 gpertea 16 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 gpertea 2 fUnique=array.fUnique;
334     fCompareProc=array.fCompareProc;
335     // uses OBJ operator=
336 gpertea 16 for (int i=0;i<this->fCount;i++) this->fArray[i]=array[i];
337 gpertea 2 }
338    
339 gpertea 16 template <class OBJ> const GVec<OBJ>& GVec<OBJ>::operator=(GVec<OBJ>& array) {
340 gpertea 2 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 gpertea 16
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 gpertea 2 fCompareProc = cmpFunc;
375     fUnique = false; //only affects sorted lists
376     }
377    
378 gpertea 16 template <class OBJ> GArray<OBJ>::GArray(bool sorted, bool unique):GVec<OBJ>(0) {
379 gpertea 2 fUnique=unique;
380     fCompareProc=sorted? &DefaultCompareProc : NULL;
381     }
382    
383     template <class OBJ> GArray<OBJ>::GArray(int init_capacity,
384 gpertea 16 bool sorted, bool unique):GVec<OBJ>(init_capacity) {
385 gpertea 2 fUnique=unique;
386     fCompareProc=sorted? &DefaultCompareProc : NULL;
387     }
388    
389 gpertea 16 template <class OBJ> GVec<OBJ>::~GVec() {
390     this->Clear();
391 gpertea 2 }
392    
393 gpertea 16
394     template <class OBJ> void GVec<OBJ>::setCapacity(int NewCapacity) {
395 gpertea 2 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 gpertea 16 template <class OBJ> void GVec<OBJ>::Clear() {
410     setCount(0);
411     setCapacity(0); //so the array itself is deallocated too!
412     }
413    
414     /*
415 gpertea 2 template <class OBJ> void GArray<OBJ>::Clear() {
416     CompareProc* fcmp=fCompareProc;
417     fCompareProc=NULL;
418 gpertea 16 GVec<OBJ>::setCount(0);
419     GVec<OBJ>::setCapacity(0); //so the array itself is deallocated too!
420 gpertea 2 fCompareProc=fcmp;
421     }
422 gpertea 16 */
423 gpertea 2 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 gpertea 16 template <class OBJ> void GVec<OBJ>::Grow() {
431 gpertea 2 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 gpertea 16 template <class OBJ> void GVec<OBJ>::Reverse() {
439 gpertea 2 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 gpertea 16 template <class OBJ> void GVec<OBJ>::Grow(int idx, OBJ& item) {
450 gpertea 2 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 gpertea 16 if (NewCapacity==0) {
460 gpertea 2 GFREE(fArray);
461 gpertea 16 }
462 gpertea 2 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 gpertea 16 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 gpertea 2 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 gpertea 16 this->idxInsert(result, *item);
516 gpertea 2 }
517     else {
518     if (fUnique && Found(*item,result)) return -1; //set behaviour
519 gpertea 16 result = this->fCount;
520     if (result==this->fCapacity) GVec<OBJ>::Grow();
521     this->fArray[result] = *item; //operator=, copies the item
522     this->fCount++;
523 gpertea 2 }
524     return result;
525     }
526    
527 gpertea 16
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 gpertea 2 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 gpertea 16 this->setCapacity(this->fCapacity+list.fCount);
546     int s=this->fCount;
547 gpertea 2 for (int i=0;i<list.fCount;i++)
548 gpertea 16 this->fArray[s+i]=list.fArray[i];
549     this->fCount+=list.fCount;
550 gpertea 2 }
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 gpertea 16 if (this->fCount==0) { idx=0;return false;}
561 gpertea 2 if (SORTED) { //binary search based on CompareProc
562     //do the simplest tests first:
563 gpertea 16 if ((*fCompareProc)(this->fArray[0],item)>0) {
564 gpertea 2 idx=0;
565     return false;
566     }
567 gpertea 16 if ((*fCompareProc)(item, this->fArray[this->fCount-1])>0) {
568     idx=this->fCount;
569 gpertea 2 return false;
570     }
571    
572     int l=0;
573 gpertea 16 int h = this->fCount - 1;
574 gpertea 2 int c;
575     while (l <= h) {
576     i = (l + h) >> 1;
577 gpertea 16 c = (*fCompareProc)(this->fArray[i], item);
578 gpertea 2 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 gpertea 16 while (i<this->fCount) {
594     if (this->fArray[i]==item) { //requires operator==
595 gpertea 2 idx=i;
596     return true;
597     }
598     i++;
599     }
600     return false;
601     }
602     }
603    
604 gpertea 16 template <class OBJ> void GVec<OBJ>::idxInsert(int idx, OBJ& item) {
605 gpertea 2 //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 gpertea 16 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 gpertea 2 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 gpertea 16
633     template <class OBJ> void GVec<OBJ>::Move(int curidx, int newidx) {
634 gpertea 2 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 gpertea 16
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 gpertea 2 TEST_INDEX(idx);
654     fArray[idx]=item;
655     }
656    
657 gpertea 16 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 gpertea 2 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 gpertea 16 template <class OBJ> void GVec<OBJ>::setCount(int NewCount) {
674 gpertea 2 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 gpertea 16 p = this->fArray[(l + r) >> 1];
688 gpertea 2 do {
689 gpertea 16 while (fCompareProc(this->fArray[i], p) < 0) i++;
690     while (fCompareProc(this->fArray[j], p) > 0) j--;
691 gpertea 2 if (i <= j) {
692 gpertea 16 t = this->fArray[i];
693     this->fArray[i] = this->fArray[j];
694     this->fArray[j] = t;
695 gpertea 2 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 gpertea 16 if (this->fArray!=NULL && this->fCount>0 && fCompareProc!=NULL)
705     qSort(0, this->fCount-1);
706 gpertea 2 }
707    
708     //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
709 gpertea 16 //*=> GPVec and GList implementation -- sortable array of pointers to OBJ
710 gpertea 2
711 gpertea 16 template <class OBJ> GPVec<OBJ>::GPVec(GPVec& list) { //copy constructor
712 gpertea 2 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 gpertea 16 template <class OBJ> GPVec<OBJ>::GPVec(GPVec* plist) { //another copy constructor
724 gpertea 2 fCount=0;
725     fCapacity=plist->fCapacity;
726 gpertea 16 fList=NULL;
727 gpertea 2 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 gpertea 16 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 gpertea 2 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 gpertea 16 this->setCapacity(this->fCapacity+list.fCount);
783     memcpy( & (this->fList[this->fCount]), list.fList, list.fCount*sizeof(OBJ*));
784     this->fCount+=list.fCount;
785 gpertea 2 }
786     }
787    
788    
789     template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc,
790     GFreeProc* freeProc, bool beUnique) {
791     fCompareProc = compareProc;
792 gpertea 16 this->fFreeProc = freeProc;
793 gpertea 2 fUnique = beUnique; //only affects sorted lists
794     }
795    
796     template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
797     fCompareProc = compareProc;
798 gpertea 16 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
799 gpertea 2 fUnique = false; //only affects sorted lists
800     }
801    
802 gpertea 16 template <class OBJ> void GPVec<OBJ>::Reverse() {
803 gpertea 2 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 gpertea 16 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
819 gpertea 2 fUnique=beUnique;
820     }
821     else {
822     fCompareProc=&DefaultCompareProc;
823 gpertea 16 this->fFreeProc=NULL;
824 gpertea 2 fUnique=beUnique;
825     }
826     }
827     else {
828     if (free_elements) {
829     fCompareProc=NULL;
830 gpertea 16 this->fFreeProc=GPVec<OBJ>::DefaultFreeProc;
831 gpertea 2 fUnique=beUnique;
832     }
833     else {
834     fCompareProc=NULL;
835 gpertea 16 this->fFreeProc=NULL;
836 gpertea 2 fUnique=beUnique;
837     }
838     }
839     }
840    
841 gpertea 16 template <class OBJ> GPVec<OBJ>::GPVec(int init_capacity, bool free_elements) {
842 gpertea 2 fCount=0;
843     fCapacity=0;
844     fList=NULL;
845 gpertea 16 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 gpertea 2 if (sorted) {
853 gpertea 16 fCompareProc=&DefaultCompareProc;
854     fUnique=beUnique;
855     }
856 gpertea 2 else {
857 gpertea 16 fCompareProc=NULL;
858     fUnique=beUnique;
859     }
860 gpertea 2 }
861    
862 gpertea 16 template <class OBJ> GPVec<OBJ>::~GPVec() {
863     this->Clear();//this will free the items if fFreeProc is defined
864     }
865    
866     /*
867 gpertea 2 template <class OBJ> GList<OBJ>::~GList() {
868 gpertea 16 this->Clear();//this will free the items if fFreeProc is defined
869 gpertea 2 }
870 gpertea 16 */
871 gpertea 2
872 gpertea 16 template <class OBJ> void GPVec<OBJ>::setCapacity(int NewCapacity) {
873 gpertea 2 if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
874     GError(SLISTCAPACITY_ERR, NewCapacity);
875     //error: capacity not within range
876     if (NewCapacity!=fCapacity) {
877 gpertea 16 if (NewCapacity==0) {
878 gpertea 2 GFREE(fList);
879 gpertea 16 }
880     else {
881 gpertea 2 GREALLOC(fList, NewCapacity*sizeof(OBJ*));
882 gpertea 16 }
883 gpertea 2 fCapacity=NewCapacity;
884     }
885     }
886    
887 gpertea 16 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 gpertea 2 }
896    
897 gpertea 16 template <class OBJ> void GPVec<OBJ>::Clear() {
898 gpertea 2 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 gpertea 16 template <class OBJ> void GPVec<OBJ>::Exchange(int idx1, int idx2) {
908     //BE_UNSORTED; //cannot do that in a sorted list!
909 gpertea 2 TEST_INDEX(idx1);
910     TEST_INDEX(idx2);
911     OBJ* item=fList[idx1];
912     fList[idx1]=fList[idx2];
913     fList[idx2]=item;
914     }
915    
916 gpertea 16 template <class OBJ> void GPVec<OBJ>::Expand() {
917 gpertea 2 if (fCount==fCapacity) Grow();
918     //return this;
919     }
920    
921 gpertea 16 template <class OBJ> OBJ* GPVec<OBJ>::Get(int idx) {
922 gpertea 2 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 gpertea 16 GPVec<OBJ>::Clear();
929 gpertea 2 fCompareProc=list.fCompareProc;
930 gpertea 16 this->fFreeProc=list.fFreeProc;
931 gpertea 2 //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 gpertea 16 template <class OBJ> void GPVec<OBJ>::Grow() {
946 gpertea 2 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 gpertea 16 template <class OBJ> void GPVec<OBJ>::Grow(int idx, OBJ* newitem) {
954 gpertea 2 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 gpertea 16 if (NewCapacity==0) {
965 gpertea 2 GFREE(fList);
966 gpertea 16 }
967 gpertea 2 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 gpertea 16 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 gpertea 2
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 gpertea 16 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 gpertea 2 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 gpertea 16 result = this->fCount;
1039     if (result==this->fCapacity) GPVec<OBJ>::Grow();
1040     this->fList[result]=item;
1041     this->fCount++;
1042 gpertea 2 }
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 gpertea 16 if (deleteIfFound && (pointer)item != (pointer)(this->fList[r])) {
1054     this->deallocate_item(item);
1055     }
1056 gpertea 2 if (fidx!=NULL) *fidx=r;
1057 gpertea 16 return this->fList[r]; //found
1058 gpertea 2 }
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 gpertea 16 r = this->fCount;
1066     if (r==this->fCapacity) GPVec<OBJ>::Grow();
1067     this->fList[r]=item;
1068     this->fCount++;
1069 gpertea 2 }
1070     if (fidx!=NULL) *fidx=r;
1071     return item;
1072     }
1073    
1074 gpertea 16 //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 gpertea 2 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 gpertea 16 if (this->fCount==0) { idx=0;return false;}
1107 gpertea 2 if (SORTED) { //binary search based on CompareProc
1108     //do the simple test first:
1109    
1110 gpertea 16 if ((*fCompareProc)(this->fList[0],item)>0) {
1111 gpertea 2 idx=0;
1112     return false;
1113     }
1114 gpertea 16 if ((*fCompareProc)(item, this->fList[this->fCount-1])>0) {
1115     idx=this->fCount;
1116 gpertea 2 return false;
1117     }
1118    
1119     int l, h, c;
1120     l = 0;
1121 gpertea 16 h = this->fCount - 1;
1122 gpertea 2 while (l <= h) {
1123     i = (l + h) >> 1;
1124 gpertea 16 c = (*fCompareProc)(this->fList[i], item);
1125 gpertea 2 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 gpertea 16 while (i<this->fCount) {
1141     if (*this->fList[i]==*item) {
1142 gpertea 2 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 gpertea 16 if (idx<0 || idx>this->fCount) GError(SLISTINDEX_ERR, idx);
1156     if (this->fCount==this->fCapacity) {
1157     GPVec<OBJ>::Grow(idx, item);
1158 gpertea 2 //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 gpertea 16 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 gpertea 2 }
1167    
1168 gpertea 16 template <class OBJ> void GPVec<OBJ>::Insert(int idx, OBJ* item) {
1169 gpertea 2 //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 gpertea 16 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 gpertea 2 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 gpertea 16 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 gpertea 2
1206 gpertea 16 template <class OBJ> void GPVec<OBJ>::Put(int idx, OBJ* item) {
1207     //WARNING: this will never free the replaced item!
1208 gpertea 2 TEST_INDEX(idx);
1209     fList[idx]=item;
1210 gpertea 16 }
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 gpertea 2 if (SORTED && item!=NULL && re_sort) Sort(); //re-sort
1217     }
1218    
1219 gpertea 16
1220     template <class OBJ> void GPVec<OBJ>::Forget(int idx) {
1221 gpertea 2 TEST_INDEX(idx);
1222 gpertea 16 fList[idx]=NULL; //user should free that somewhere else
1223 gpertea 2 }
1224    
1225 gpertea 16 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 gpertea 2 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 gpertea 16 template <class OBJ> OBJ* GPVec<OBJ>::Pop() {
1247 gpertea 2 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 gpertea 16 template <class OBJ> OBJ* GPVec<OBJ>::Shift() {
1256 gpertea 2 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 gpertea 16 if (result>=0) GPVec<OBJ>::Delete(result);
1269 gpertea 2 return result;
1270     }
1271    
1272 gpertea 16 //linear search for the pointer address
1273     template <class OBJ> int GPVec<OBJ>::RemovePtr(pointer item) {
1274 gpertea 2 if (item==NULL) return -1;
1275 gpertea 16 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 gpertea 2 }
1282    
1283 gpertea 16 template <class OBJ> void GPVec<OBJ>::Pack() {//also frees items!
1284 gpertea 2 for (int i=fCount-1; i>=0; i--)
1285 gpertea 16 if (fList[i]==NULL) Delete(i); //shift rest of fList content accordingly
1286 gpertea 2 }
1287    
1288 gpertea 16 template <class OBJ> void GPVec<OBJ>::setCount(int NewCount) {
1289 gpertea 2 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 gpertea 16 P = this->fList[(L + R) >> 1];
1305 gpertea 2 do {
1306 gpertea 16 while (fCompareProc(this->fList[I], P) < 0) I++;
1307     while (fCompareProc(this->fList[J], P) > 0) J--;
1308 gpertea 2 if (I <= J) {
1309 gpertea 16 T = this->fList[I];
1310     this->fList[I] = this->fList[J];
1311     this->fList[J] = T;
1312 gpertea 2 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 gpertea 16 if (this->fList!=NULL && this->fCount>0 && fCompareProc!=NULL)
1326     QuickSort(0, this->fCount-1);
1327 gpertea 2 }
1328    
1329     //---------------------------------------------------------------------------
1330     #endif