ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 151
Committed: Fri Jan 13 22:56:48 2012 UTC (7 years, 10 months ago) by gpertea
File size: 41500 byte(s)
Log Message:
wip: trans-spliced and fusion transcripts

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