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