ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 115
Committed: Mon Nov 7 21:25:03 2011 UTC (7 years, 8 months ago) by gpertea
File size: 41338 byte(s)
Log Message:
fixed horrendous bug in GList.hh (resizing GVec)

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