ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 2
Committed: Mon Mar 22 22:03:27 2010 UTC (9 years, 6 months ago) by gpertea
File size: 32387 byte(s)
Log Message:
added my gclib source files

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     #ifdef __LINE__
12     #define SLISTINDEX_ERR "GList error (%s:%d):Invalid list index: %d"
13     #define TEST_INDEX(x) \
14     if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, __FILE__,__LINE__, x)
15     #else
16     #define SLISTINDEX_ERR "GList error:Invalid list index: %d"
17     #define TEST_INDEX(x) \
18     if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x, __FILE__,__LINE__)
19     #endif
20    
21     #define SLISTCAPACITY_ERR "GList error: invalid capacity: %d"
22     #define SLISTCOUNT_ERR "GList error: invalid count: %d"
23     #define SLISTSORTED_ERR "Operation not allowed on a sorted list!"
24     #define SLISTUNSORTED_ERR "Operation not allowed on an unsorted list!"
25    
26     // ------ macros:
27     #define BE_UNSORTED if (fCompareProc!=NULL) { GError(SLISTSORTED_ERR); return; }
28     #define BE_SORTED if (fCompareProc==NULL) { GError(SLISTUNSORTED_ERR); return; }
29    
30     #define MAXLISTSIZE INT_MAX-1
31    
32     #define SORTED (fCompareProc!=NULL)
33     #define UNSORTED (fCompareProc==NULL)
34     #define FREEDATA (fFreeProc!=NULL)
35     /* #define TEST_INDEX(x) assert(x>=0 && x<fCount); \
36     if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x) */
37    
38    
39     //template for array of objects
40     template <class OBJ> class GArray {
41     protected:
42     OBJ* fArray;
43     int fCount;
44     int fCapacity;
45     bool fUnique;
46    
47     static int DefaultCompareProc(OBJ& item1, OBJ& item2) {
48     //the comparison operators MUST be defined for OBJ class!
49     if ( item1 > item2) return 1;
50     else return (item2 > item1) ? -1 : 0 ;
51     }
52     public:
53     typedef int CompareProc(OBJ& item1, OBJ& item2);
54     protected:
55     CompareProc* fCompareProc;
56     void idxInsert(int idx, OBJ& item);
57     void Grow();
58     void Grow(int idx, OBJ& item);
59     void qSort(int L, int R);
60     public:
61     GArray(CompareProc* cmpFunc=NULL);
62     GArray(bool sorted, bool unique=false);
63     GArray(int init_capacity, bool sorted, bool unique=false);
64     GArray(GArray<OBJ>& array); //copy constructor
65     const GArray<OBJ>& operator=(GArray& array);
66     virtual ~GArray();
67     //assignment operator
68     void setSorted(CompareProc* cmpFunc);
69     //sort the array if cmpFunc not NULL or changes
70     void Reverse(); //WARNING: will break the sort order if SORTED!
71     int Add(OBJ* item); // specific implementation if sorted
72     int Add(OBJ& item) { return Add(&item); } //both will CREATE a new OBJ and COPY to it
73     // using OBJ new operator=
74     void Add(GArray<OBJ>& list); //add copies of all items from another list
75     OBJ& Get(int idx) {
76     TEST_INDEX(idx);
77     return fArray[idx];
78     }
79     OBJ& operator[](int i) {
80     TEST_INDEX(i);
81     return fArray[i];
82     }
83     void Clear();
84     void Delete(int index);
85     void Exchange(int idx1, int idx2);
86     int Capacity() { return fCapacity; }
87     int Unique() { return fUnique; }
88     //this will reject identical items in sorted lists only!
89     void setUnique(bool beUnique) { fUnique = beUnique; };
90     void setCapacity(int NewCapacity);
91     int Count() { return fCount; }
92     void setCount(int NewCount);
93     void Sort(); //explicit sort may be requested
94     bool Sorted() { return fCompareProc!=NULL; }
95     int IndexOf(OBJ& item);
96     //this needs the == operator to have been defined for OBJ
97     bool Found(OBJ& item, int& idx); // for sorted arrays only;
98     //search by content; if found, returns true and idx will be the index
99     //of the first item found matching for which CompareProc returns 0
100     bool Exists(OBJ& item); //same as above without existing index info
101     //unsorted only, place item at position idx:
102     void Insert(int idx, OBJ* item);
103     void Insert(int idx, OBJ& item) { Insert(idx,&item); }
104     void Replace(int idx, OBJ& item); //Put, use operator= to copy
105     void Move(int curidx, int newidx);
106     };
107    
108     //------- template for array of pointers to objects ---------
109     template <class OBJ> class GList {
110     protected:
111     OBJ** fList; //pointer to an array of pointers to objects
112     int fCount; //total number of entries in list
113     int fCapacity; //current allocated size
114     bool fUnique;
115     GCompareProc* fCompareProc; //a pointer to a Compare function
116     GFreeProc* fFreeProc; //useful for deleting objects
117     static int DefaultCompareProc(const pointer item1, const pointer item2) {
118     //the comparison operators MUST be defined for OBJ class!
119     if (*((OBJ*)item1) > *((OBJ*)item2)) return 1;
120     else if (*((OBJ*)item2) > *((OBJ*)item1)) return -1;
121     else return 0;
122     }
123     void Expand();
124     void Grow();
125     void QuickSort(int L, int R);
126     public:
127     void sortInsert(int idx, OBJ* item);
128     static void DefaultFreeProc(pointer item) {
129     delete (OBJ*)item;
130     }
131     GList(GCompareProc* compareProc=NULL); //free by default
132     GList(GCompareProc* compareProc, //unsorted by default
133     GFreeProc *freeProc,
134     bool beUnique=false);
135     GList(bool sorted, bool free_elements=true, bool beUnique=false);
136     GList(int init_capacity, bool sorted, bool free_elements=true, bool beUnique=false);
137     GList(GList<OBJ>& list); //copy constructor?
138     GList(GList<OBJ>* list); //kind of a copy constructor
139     virtual ~GList();
140     void Reverse(); //reverse pointer array; WARNING: will break the sort order if sorted!
141     void freeItem(int idx);
142     void setSorted(GCompareProc* compareProc);
143     //sorted if compareProc not NULL; sort the list if compareProc changes !
144     void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
145     void setFreeItem(bool doFree) {
146     if (doFree) fFreeProc=DefaultFreeProc;
147     else fFreeProc=NULL;
148     }
149     bool Sorted() { return fCompareProc!=NULL; }
150     void setSorted(bool sorted) {
151     if (sorted) {
152     if (fCompareProc!=&DefaultCompareProc) {
153     fCompareProc=&DefaultCompareProc;
154     Sort();
155     }
156     }
157     else fCompareProc=NULL;
158     }
159     int Add(OBJ* item); //-- specific implementation if sorted
160     void Add(GList<OBJ>& list); //add all pointers from another list
161    
162     OBJ* AddIfNew(OBJ* item, bool deleteIfFound=true, int* fidx=NULL);
163     // default: delete item if Found() (and pointers are not equal)!
164     //returns the equal (==) object if it's in the list already
165     //or the item itself if it is unique, and it addsit
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 Clear();
172     void Delete(int index);
173     void Forget(int idx);
174     void Exchange(int idx1, int idx2);
175     OBJ* First() { return (fCount>0)?fList[0]:NULL; }
176     OBJ* Last() { return (fCount>0)?fList[fCount-1]:NULL;}
177     bool isEmpty() { return fCount==0; }
178     bool notEmpty() { return fCount>0; }
179     int Capacity() { return fCapacity; }
180     int Unique() { return fUnique; }
181     //this will reject identical items in sorted lists only!
182     void setUnique(bool beUnique) { fUnique = beUnique; };
183    
184     void setCapacity(int NewCapacity);
185     int Count() { return fCount; }
186     void setCount(int NewCount);
187     GCompareProc* GetCompareProc() {return fCompareProc;}
188     OBJ* Get(int idx);
189     OBJ* operator[](int i);
190     void Grow(int idx, OBJ* item);
191     int IndexOf(OBJ* item); //this has a specific implementation for sorted lists
192     //if list is sorted, item data is located by binary search
193     //based on the Compare function
194     //if not, a linear search is performed, but
195     //this needs the == operator to have been defined for OBJ
196     bool Found(OBJ* item, int & idx); // sorted only;
197     //search by content; if found, returns true and idx will be the index
198     //of the first item found matching for which GTCompareProc returns 0
199     bool Exists(OBJ* item); //same as above without existing index info
200     bool Exists(OBJ& item); //same as above without existing index info
201     void Insert(int idx, OBJ* item); //unsorted only, place item at position idx
202     void Move(int curidx, int newidx);
203     void Put(int idx, OBJ* item, bool re_sort=false);
204     int Remove(OBJ* item); //search for pointer, using binary search if sorted
205     int RemovePtr(OBJ* item); //always use linear search to find the pointer!
206     void Pack();
207     void Sort(); //explicit sort may be requested using this function
208     const GList<OBJ>& operator=(GList& list);
209     };
210    
211    
212     //basic template for a Stack of pointers
213     template <class OBJ> class GStack {
214     protected:
215     struct StackOBJ {
216     OBJ* obj;
217     StackOBJ* prev;
218     };
219     int fCount; //total number of elements in stack
220     StackOBJ* base;
221     StackOBJ* top;
222     public:
223     GStack(OBJ* po=NULL) {
224     base=NULL;
225     top=NULL;
226     fCount=0;
227     if (po!=NULL) Push(po);
228     }
229     ~GStack() {
230     while (fCount>0) Pop();
231     }
232     bool isEmpty() { return fCount==0; }
233     int Size() { return fCount; }
234     int Count() { return fCount; }
235     OBJ* Pop() {
236     if (top==NULL) return NULL;
237     fCount--;
238     StackOBJ* ctop=top;
239     if (top==base) base=NULL;
240     OBJ* r=top->obj;
241     top=top->prev;
242     GFREE(ctop);
243     return r;
244     }
245     OBJ* Push(OBJ* o) {
246     fCount++;
247     StackOBJ* ctop=top; //could be NULL
248     GMALLOC(top, sizeof(StackOBJ));
249     top->obj=o;
250     top->prev=ctop;
251     if (base==NULL) base=top;
252     return o;
253     }
254     OBJ* Top() { return ((top==NULL)? NULL : top->obj); }
255     OBJ* Base() { return ((base==NULL)? NULL : base->obj); }
256     };
257    
258     //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
259    
260     template <class OBJ> GArray<OBJ>::GArray(GArray& array) { //copy constructor
261     fCount=array.fCount;
262     fCapacity=array.fCapacity;
263     if (fCapacity>0) {
264     GMALLOC(fArray, fCapacity*sizeof(OBJ));
265     }
266     fUnique=array.fUnique;
267     fCompareProc=array.fCompareProc;
268     fCount=array.fCount;
269     // uses OBJ operator=
270     for (int i=0;i<fCount;i++) fArray[i]=array[i];
271     }
272    
273     template <class OBJ> const GArray<OBJ>& GArray<OBJ>::operator=(GArray& array) {
274     if (&array==this) return *this;
275     Clear();
276     fCount=array.fCount;
277     fUnique=array.fUnique;
278     fCapacity=array.fCapacity;
279     if (fCapacity>0) {
280     GMALLOC(fArray, fCapacity*sizeof(OBJ));
281     }
282     fCompareProc=array.fCompareProc;
283     fCount=array.fCount;
284     // uses OBJ operator=
285     for (int i=0;i<fCount;i++) {
286     fArray[i]=array[i];
287     }
288     return *this;
289     }
290     template <class OBJ> GArray<OBJ>::GArray(CompareProc* cmpFunc) {
291     fCount=0;
292     fCapacity=0;
293     fArray=NULL;
294     fCompareProc = cmpFunc;
295     fUnique = false; //only affects sorted lists
296     }
297    
298     template <class OBJ> GArray<OBJ>::GArray(bool sorted, bool unique) {
299     fCount=0;
300     fCapacity=0;
301     fArray=NULL;
302     fUnique=unique;
303     fCompareProc=sorted? &DefaultCompareProc : NULL;
304     }
305    
306     template <class OBJ> GArray<OBJ>::GArray(int init_capacity,
307     bool sorted, bool unique) {
308     fCount=0;
309     fCapacity=0;
310     fArray=NULL;
311     fUnique=unique;
312     fCompareProc=sorted? &DefaultCompareProc : NULL;
313     setCapacity(init_capacity);
314     }
315    
316     template <class OBJ> GArray<OBJ>::~GArray() {
317     Clear();//this will free the items if fFreeProc is defined
318     }
319    
320     template <class OBJ> void GArray<OBJ>::setCapacity(int NewCapacity) {
321     if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
322     GError(SLISTCAPACITY_ERR, NewCapacity);
323     //error: capacity not within range
324     if (NewCapacity!=fCapacity) {
325     if (NewCapacity==0) {
326     GFREE(fArray);
327     }
328     else {
329     GREALLOC(fArray, NewCapacity*sizeof(OBJ));
330     }
331     fCapacity=NewCapacity;
332     }
333     }
334    
335     template <class OBJ> void GArray<OBJ>::Clear() {
336     CompareProc* fcmp=fCompareProc;
337     fCompareProc=NULL;
338     setCount(0);
339     setCapacity(0); //so the array itself is deallocated too!
340     fCompareProc=fcmp;
341     }
342    
343     template <class OBJ> void GArray<OBJ>::setSorted(CompareProc* cmpFunc) {
344     CompareProc* old_proc=fCompareProc;
345     fCompareProc=cmpFunc;
346     if (fCompareProc!=old_proc && fCompareProc!=NULL)
347     Sort(); //new compare method
348     }
349    
350     template <class OBJ> void GArray<OBJ>::Grow() {
351     int delta;
352     if (fCapacity > 64) delta = fCapacity/4;
353     else if (fCapacity > 8) delta = 16;
354     else delta = 4;
355     setCapacity(fCapacity + delta);
356     }
357    
358     template <class OBJ> void GArray<OBJ>::Reverse() {
359     int l=0;
360     int r=fCount-1;
361     OBJ c;
362     while (l<r) {
363     c=fArray[l];fArray[l]=fArray[r];
364     fArray[r]=c;
365     l++;r--;
366     }
367     }
368    
369     template <class OBJ> void GArray<OBJ>::Grow(int idx, OBJ& item) {
370     int delta;
371     if (fCapacity > 64) delta = fCapacity/4;
372     else if (fCapacity > 8) delta = 16;
373     else delta = 4;
374     int NewCapacity=fCapacity+delta;
375     if (NewCapacity <= fCount || NewCapacity >= MAXLISTSIZE)
376     GError(SLISTCAPACITY_ERR, NewCapacity);
377     //error: capacity not within range
378     if (NewCapacity!=fCapacity) {
379     if (NewCapacity==0)
380     GFREE(fArray);
381     else { //add the new item
382     if (idx==fCount) { //append item
383     GREALLOC(fArray, NewCapacity*sizeof(OBJ));
384     fArray[idx]=item;
385     }
386     else { //insert item at idx
387     OBJ* newList;
388     GMALLOC(newList, NewCapacity*sizeof(OBJ));
389     //copy data before idx
390     memmove(&newList[0],&fArray[0], idx*sizeof(OBJ));
391     newList[idx]=item; // operator=
392     //copy data after idx
393     memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
394     memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ));
395     //data copied:
396     GFREE(fArray);
397     fArray=newList;
398     }
399     fCount++;
400     }
401     fCapacity=NewCapacity;
402     }
403     }
404    
405     template <class OBJ> int GArray<OBJ>::IndexOf(OBJ& item) {
406     int result=0;
407     if (Found(item, result)) return result;
408     else return -1;
409     }
410    
411     template <class OBJ> bool GArray<OBJ>::Exists(OBJ& item) {
412     int result=0;
413     if (Found(item, result)) return true;
414     else return false;
415     }
416    
417    
418     template <class OBJ> int GArray<OBJ>::Add(OBJ* item) {
419     if (item==NULL) return -1;
420     int result;
421     if (SORTED) {
422     if (Found(*item, result))
423     if (fUnique) return -1; //cannot add a duplicate!
424     //Found sets result to the position where the item should be!
425     idxInsert(result, *item);
426     }
427     else {
428     if (fUnique && Found(*item,result)) return -1; //set behaviour
429     result = fCount;
430     if (result==fCapacity) Grow();
431     fArray[result] = *item; //operator=, copies the item
432     fCount++;
433     }
434     return result;
435     }
436    
437     template <class OBJ> void GArray<OBJ>::Add(GArray<OBJ>& list) {
438     if (list.Count()==0) return;
439     if (SORTED) {
440     for (int i=0;i<list.fCount;i++) Add(&list[i]);
441     }
442     else { //simply copy
443     setCapacity(fCapacity+list.fCount);
444     int s=fCount;
445     for (int i=0;i<list.fCount;i++)
446     fArray[s+i]=list.fArray[i];
447     fCount+=list.fCount;
448     }
449     }
450    
451     template <class OBJ> bool GArray<OBJ>::Found(OBJ& item, int& idx) {
452     //search the list by using CompareProc (if defined)
453     //or == operator for a non-sortable list
454     //for sorted lists, even when the result is false, the idx is
455     //set to the closest matching object!
456     int i;
457     idx=-1;
458     if (fCount==0) { idx=0;return false;}
459     if (SORTED) { //binary search based on CompareProc
460     //do the simplest tests first:
461     if ((*fCompareProc)(fArray[0],item)>0) {
462     idx=0;
463     return false;
464     }
465     if ((*fCompareProc)(item, fArray[fCount-1])>0) {
466     idx=fCount;
467     return false;
468     }
469    
470     int l=0;
471     int h = fCount - 1;
472     int c;
473     while (l <= h) {
474     i = (l + h) >> 1;
475     c = (*fCompareProc)(fArray[i], item);
476     if (c < 0) l = i + 1;
477     else {
478     h = i - 1;
479     if (c == 0) { //found!
480     idx=i;
481     return true;
482     }
483     }
484     } //while
485     idx = l;
486     return false;
487     }
488     else {//not sorted: use linear search
489     // needs == operator to compare user defined objects !
490     i=0;
491     while (i<fCount) {
492     if (fArray[i]==item) { //requires operator==
493     idx=i;
494     return true;
495     }
496     i++;
497     }
498     return false;
499     }
500     }
501    
502     template <class OBJ> void GArray<OBJ>::idxInsert(int idx, OBJ& item) {
503     //idx must be the new position this new item must have
504     //so the allowed range is [0..fCount]
505     //the old idx item all the above will be shifted to idx+1
506     if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
507     if (fCount==fCapacity) { //need to resize
508     Grow(idx, item);
509     //expand and also copy/move data and insert the new item
510     return;
511     }
512     //move data around to make room for the new item
513     if (idx<fCount)
514     memmove(&fArray[idx+1], &fArray[idx], (fCount-idx)*sizeof(OBJ));
515     fArray[idx]=item;
516     fCount++;
517     }
518    
519     template <class OBJ> void GArray<OBJ>::Insert(int idx, OBJ* item) {
520     //idx can be [0..fCount] so an item can be actually added
521     BE_UNSORTED; //forbid this operation on sorted data
522     idxInsert(idx, item);
523     }
524    
525     template <class OBJ> void GArray<OBJ>::Move(int curidx, int newidx) {
526     BE_UNSORTED; //cannot do this in a sorted list!
527     if (curidx!=newidx || newidx>=fCount)
528     GError(SLISTINDEX_ERR, newidx);
529    
530     OBJ tmp=fArray[curidx]; //copy constructor here
531     fArray[curidx]=fArray[newidx];
532     fArray[newidx]=tmp;
533     }
534    
535     template <class OBJ> void GArray<OBJ>::Replace(int idx, OBJ& item) {
536     TEST_INDEX(idx);
537     fArray[idx]=item;
538     if ( SORTED ) Sort(); //re-sort !
539     }
540    
541     template <class OBJ> void GArray<OBJ>::Delete(int index) {
542     TEST_INDEX(index);
543     //fArray[index]=NULL;
544     fCount--;
545     if (index<fCount) //move higher elements if any
546     memmove(&fArray[index], &fArray[index+1], (fCount-index)*sizeof(OBJ));
547     }
548    
549     template <class OBJ> void GArray<OBJ>::setCount(int NewCount) {
550     if (NewCount<0 || NewCount > MAXLISTSIZE)
551     GError(SLISTCOUNT_ERR, NewCount);
552     if (NewCount > fCapacity) setCapacity(NewCount);
553     if (NewCount > fCount)
554     memset(&fArray[fCount], 0, (NewCount - fCount) * sizeof(OBJ));
555     fCount = NewCount;
556     }
557    
558     template <class OBJ> void GArray<OBJ>::qSort(int l, int r) {
559     int i, j;
560     OBJ p,t;
561     do {
562     i = l; j = r;
563     p = fArray[(l + r) >> 1];
564     do {
565     while (fCompareProc(fArray[i], p) < 0) i++;
566     while (fCompareProc(fArray[j], p) > 0) j--;
567     if (i <= j) {
568     t = fArray[i];
569     fArray[i] = fArray[j];
570     fArray[j] = t;
571     i++; j--;
572     }
573     } while (i <= j);
574     if (l < j) qSort(l, j);
575     l = i;
576     } while (i < r);
577     }
578    
579     template <class OBJ> void GArray<OBJ>::Sort() {
580     if (fArray!=NULL && fCount>0 && fCompareProc!=NULL)
581     qSort(0, fCount-1);
582     }
583    
584    
585    
586    
587    
588     //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
589     //*=> GList implementation -- sortable array of pointers to OBJ
590    
591     template <class OBJ> OBJ* GList<OBJ>::operator[](int i) {
592     TEST_INDEX(i);
593     return fList[i];
594     }
595    
596     template <class OBJ> GList<OBJ>::GList(GList& list) { //copy constructor
597     fCount=list.fCount;
598     fUnique=list.fUnique;
599     fCapacity=list.fCapacity;
600     if (fCapacity>0) {
601     GMALLOC(fList, fCapacity*sizeof(OBJ*));
602     }
603     fCompareProc=list.fCompareProc;
604     fFreeProc=list.fFreeProc;
605     fCount=list.fCount;
606     memcpy(fList, list.fList, fCount*sizeof(OBJ*));
607     //for (int i=0;i<list.Count();i++) Add(list[i]);
608     }
609    
610     template <class OBJ> GList<OBJ>::GList(GList* plist) { //another copy constructor
611     fCount=0;
612     fCapacity=plist->fCapacity;
613     if (fCapacity>0) {
614     GMALLOC(fList, fCapacity*sizeof(OBJ*));
615     }
616     fUnique=plist->fUnique;
617     fCompareProc=plist->fCompareProc;
618     fFreeProc=plist->fFreeProc;
619     fCount=plist->fCount;
620     memcpy(fList, plist->fList, fCount*sizeof(OBJ*));
621     //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
622     }
623    
624     template <class OBJ> void GList<OBJ>::Add(GList<OBJ>& list) {
625     if (list.Count()==0) return;
626     if (SORTED) {
627     for (int i=0;i<list.Count();i++) Add(list[i]);
628     }
629     else { //simply copy
630     setCapacity(fCapacity+list.fCount);
631     memcpy( & (fList[fCount]), list.fList, list.fCount*sizeof(OBJ*));
632     fCount+=list.fCount;
633     }
634     }
635    
636    
637     template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc,
638     GFreeProc* freeProc, bool beUnique) {
639     fCount=0;
640     fCapacity=0;
641     fList=NULL;
642     fCompareProc = compareProc;
643     fFreeProc = freeProc;
644     fUnique = beUnique; //only affects sorted lists
645     }
646    
647     template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
648     fCount=0;
649     fCapacity=0;
650     fList=NULL;
651     fCompareProc = compareProc;
652     fFreeProc = &DefaultFreeProc;
653     fUnique = false; //only affects sorted lists
654     }
655    
656     template <class OBJ> void GList<OBJ>::Reverse() {
657     int l=0;
658     int r=fCount-1;
659     OBJ* c;
660     while (l<r) {
661     c=fList[l];fList[l]=fList[r];
662     fList[r]=c;
663     l++;r--;
664     }
665     }
666    
667    
668     template <class OBJ> GList<OBJ>::GList(bool sorted,
669     bool free_elements, bool beUnique) {
670     fCount=0;
671     fCapacity=0;
672     fList=NULL;
673     if (sorted) {
674     if (free_elements) {
675     fCompareProc=&DefaultCompareProc;
676     fFreeProc=&DefaultFreeProc;
677     fUnique=beUnique;
678     }
679     else {
680     fCompareProc=&DefaultCompareProc;
681     fFreeProc=NULL;
682     fUnique=beUnique;
683     }
684     }
685     else {
686     if (free_elements) {
687     fCompareProc=NULL;
688     fFreeProc=&DefaultFreeProc;
689     fUnique=beUnique;
690     }
691     else {
692     fCompareProc=NULL;
693     fFreeProc=NULL;
694     fUnique=beUnique;
695     }
696     }
697     }
698    
699     template <class OBJ> GList<OBJ>::GList(int init_capacity, bool sorted,
700     bool free_elements, bool beUnique) {
701     fCount=0;
702     fCapacity=0;
703     fList=NULL;
704     if (sorted) {
705     if (free_elements) {
706     fCompareProc=&DefaultCompareProc;
707     fFreeProc=&DefaultFreeProc;
708     fUnique=beUnique;
709     }
710     else {
711     fCompareProc=&DefaultCompareProc;
712     fFreeProc=NULL;
713     fUnique=beUnique;
714     }
715     }
716     else {
717     if (free_elements) {
718     fCompareProc=NULL;
719     fFreeProc=&DefaultFreeProc;
720     fUnique=beUnique;
721     }
722     else {
723     fCompareProc=NULL;
724     fFreeProc=NULL;
725     fUnique=beUnique;
726     }
727     }
728     setCapacity(init_capacity);
729     }
730    
731     template <class OBJ> GList<OBJ>::~GList() {
732     Clear();//this will free the items if fFreeProc is defined
733     }
734    
735     template <class OBJ> void GList<OBJ>::setCapacity(int NewCapacity) {
736     if (NewCapacity < fCount || NewCapacity > MAXLISTSIZE)
737     GError(SLISTCAPACITY_ERR, NewCapacity);
738     //error: capacity not within range
739     if (NewCapacity!=fCapacity) {
740     if (NewCapacity==0)
741     GFREE(fList);
742     else
743     GREALLOC(fList, NewCapacity*sizeof(OBJ*));
744     fCapacity=NewCapacity;
745     }
746     }
747    
748     template <class OBJ> void GList<OBJ>::freeItem(int idx) {
749     TEST_INDEX(idx);
750     (*fFreeProc)(fList[idx]);
751     fList[idx]=NULL;
752     }
753    
754     template <class OBJ> void GList<OBJ>::Clear() {
755     if (FREEDATA) {
756     for (int i=0; i<fCount; i++) {
757     (*fFreeProc)(fList[i]);
758     }
759     }
760     GCompareProc* fcmp=fCompareProc;
761     fCompareProc=NULL;
762     setCount(0);
763     setCapacity(0); //so the array itself is deallocated too!
764     fCompareProc=fcmp;
765     }
766    
767    
768     template <class OBJ> void GList<OBJ>::Exchange(int idx1, int idx2) {
769     BE_UNSORTED; //cannot do that in a sorted list!
770     TEST_INDEX(idx1);
771     TEST_INDEX(idx2);
772     OBJ* item=fList[idx1];
773     fList[idx1]=fList[idx2];
774     fList[idx2]=item;
775     }
776    
777    
778     template <class OBJ> void GList<OBJ>::Expand()
779     {
780     if (fCount==fCapacity) Grow();
781     //return this;
782     }
783    
784    
785     template <class OBJ> OBJ* GList<OBJ>::Get(int idx)
786     {
787     TEST_INDEX(idx);
788     return fList[idx];
789     }
790    
791     template <class OBJ> const GList<OBJ>& GList<OBJ>::operator=(GList& list) {
792     if (&list!=this) {
793     Clear();
794     fCompareProc=list.fCompareProc;
795     fFreeProc=list.fFreeProc;
796     //Attention: the object pointers are copied directly,
797     //but the actual objects are NOT duplicated
798     for (int i=0;i<list.Count();i++) Add(list[i]);
799     }
800     return *this;
801     }
802    
803     template <class OBJ> void GList<OBJ>::setSorted(GCompareProc* compareProc) {
804     GCompareProc* old_proc=fCompareProc;
805     fCompareProc=compareProc;
806     if (fCompareProc!=old_proc && fCompareProc!=NULL)
807     Sort(); //new compare method
808     }
809    
810     template <class OBJ> void GList<OBJ>::Grow() {
811     int delta;
812     if (fCapacity > 64) delta = fCapacity/4;
813     else if (fCapacity > 8) delta = 16;
814     else delta = 4;
815     setCapacity(fCapacity + delta);
816     }
817    
818     template <class OBJ> void GList<OBJ>::Grow(int idx, OBJ* newitem) {
819     int delta;
820     if (fCapacity > 64) delta = fCapacity/4;
821     else if (fCapacity > 8) delta = 16;
822     else delta = 4;
823     // setCapacity(fCapacity + delta);
824     int NewCapacity=fCapacity+delta;
825     if (NewCapacity <= fCount || NewCapacity > MAXLISTSIZE)
826     GError(SLISTCAPACITY_ERR, NewCapacity);
827     //error: capacity not within range
828     if (NewCapacity!=fCapacity) {
829     if (NewCapacity==0)
830     GFREE(fList);
831     else {//add the new item
832     if (idx==fCount) {
833     GREALLOC(fList, NewCapacity*sizeof(OBJ*));
834     fList[idx]=newitem;
835     }
836     else {
837     OBJ** newList;
838     GMALLOC(newList, NewCapacity*sizeof(OBJ*));
839     //copy data before idx
840     memmove(&newList[0],&fList[0], idx*sizeof(OBJ*));
841     newList[idx]=newitem;
842     //copy data after idx
843     memmove(&newList[idx+1],&fList[idx], (fCount-idx)*sizeof(OBJ*));
844     memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ*));
845     //data copied:
846     GFREE(fList);
847     fList=newList;
848     }
849     fCount++;
850     }
851     fCapacity=NewCapacity;
852     }
853     }
854    
855    
856     template <class OBJ> int GList<OBJ>::IndexOf(OBJ* item) {
857     int result=0;
858     if (Found(item, result)) return result;
859     else return -1;
860     }
861    
862     template <class OBJ> bool GList<OBJ>::Exists(OBJ& item) {
863     int result=0;
864     if (Found(&item, result)) return true;
865     else return false;
866     }
867    
868     template <class OBJ> bool GList<OBJ>::Exists(OBJ* item) {
869     int result=0;
870     if (Found(item, result)) return true;
871     else return false;
872     }
873    
874     template <class OBJ> int GList<OBJ>::Add(OBJ* item) {
875     int result;
876     if (item==NULL) return -1;
877     if (SORTED) {
878     if (Found(item, result))
879     if (fUnique) return -1; //duplicates forbidden
880     //Found sets result to the position where the item should be!
881     sortInsert(result, item);
882     }
883     else {
884     if (fUnique && Found(item,result)) return -1; //set behaviour
885     result = fCount;
886     if (result==fCapacity) Grow();
887     fList[result]=item;
888     fCount++;
889     }
890     return result;
891     }
892    
893     //by default, it deletes the item if it has an equal in the list!
894     //returns the existing equal (==) object if it's in the list already
895     //or returns the item itself if it's unique (and adds it)
896     template <class OBJ> OBJ* GList<OBJ>::AddIfNew(OBJ* item,
897     bool deleteIfFound, int* fidx) {
898     int r;
899     if (Found(item, r)) {
900     if (deleteIfFound && (pointer)item != (pointer)fList[r]) delete item;
901     if (fidx!=NULL) *fidx=r;
902     return fList[r]; //found
903     }
904     //not found:
905     if (SORTED) {
906     //Found() set result to the position where the item should be inserted:
907     sortInsert(r, item);
908     }
909     else {
910     r = fCount;
911     if (r==fCapacity) Grow();
912     fList[r]=item;
913     fCount++;
914     }
915     if (fidx!=NULL) *fidx=r;
916     return item;
917     }
918    
919     template <class OBJ> bool GList<OBJ>::Found(OBJ* item, int& idx) {
920     //search the list by using CompareProc (if defined)
921     //or == operator for a non-sortable list
922     //for sorted lists, even when the result is false, the idx is
923     //set to the closest matching object!
924     int i;
925     idx=-1;
926     if (fCount==0) { idx=0;return false;}
927     if (SORTED) { //binary search based on CompareProc
928     //do the simple test first:
929    
930     if ((*fCompareProc)(fList[0],item)>0) {
931     idx=0;
932     return false;
933     }
934     if ((*fCompareProc)(item, fList[fCount-1])>0) {
935     idx=fCount;
936     return false;
937     }
938    
939     int l, h, c;
940     l = 0;
941     h = fCount - 1;
942     while (l <= h) {
943     i = (l + h) >> 1;
944     c = (*fCompareProc)(fList[i], item);
945     if (c < 0) l = i + 1;
946     else {
947     h = i - 1;
948     if (c == 0) {
949     idx=i;
950     return true;
951     }
952     }
953     } //while
954     idx = l;
955     return false;
956     }
957     else {//not sorted: use linear search
958     // needs == operator to compare user defined objects !
959     i=0;
960     while (i<fCount) {
961     if (*fList[i]==*item) {
962     idx=i;
963     return true;
964     }
965     i++;
966     }
967     return false;
968     }
969     }
970    
971     template <class OBJ> void GList<OBJ>::sortInsert(int idx, OBJ* item) {
972     //idx must be the new position this new item must have
973     //so the allowed range is [0..fCount]
974     //the old idx item all the above will be shifted to idx+1
975     if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
976     if (fCount==fCapacity) {
977     Grow(idx, item);
978     //expand and also copy/move data and insert the new item
979     return;
980     }
981     //room still left, just move data around and insert the new one
982     if (idx<fCount) //copy/move pointers only!
983     memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
984     fList[idx]=item;
985     fCount++;
986     }
987    
988     template <class OBJ> void GList<OBJ>::Insert(int idx, OBJ* item) {
989     //idx can be [0..fCount] so an item can be actually added
990     BE_UNSORTED; //cannot do that with a sorted list!
991     if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
992     if (fCount==fCapacity) {
993     Grow(idx, item);
994     return;
995     }
996     if (idx<fCount)
997     memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
998     fList[idx]=item;
999     fCount++;
1000     }
1001    
1002     template <class OBJ> void GList<OBJ>::Move(int curidx, int newidx) {
1003     BE_UNSORTED; //cannot do that in a sorted list!
1004     if (curidx!=newidx || newidx>=fCount)
1005     GError(SLISTINDEX_ERR, newidx);
1006     OBJ* p;
1007     p=Get(curidx);
1008     //this is a delete:
1009     fCount--;
1010     if (curidx<fCount)
1011     memmove(&fList[curidx], &fList[curidx+1], (fCount-curidx)*sizeof(OBJ*));
1012     //-this was instead of delete
1013     Insert(newidx, p);
1014     }
1015    
1016    
1017     template <class OBJ> void GList<OBJ>::Put(int idx, OBJ* item, bool re_sort) {
1018     //WARNING: this will never free the replaced item!!!
1019     TEST_INDEX(idx);
1020     fList[idx]=item;
1021     if (SORTED && item!=NULL && re_sort) Sort(); //re-sort
1022     }
1023    
1024     template <class OBJ> void GList<OBJ>::Forget(int idx) {
1025     TEST_INDEX(idx);
1026     fList[idx]=NULL;
1027     }
1028    
1029     template <class OBJ> void GList<OBJ>::Delete(int index) {
1030     TEST_INDEX(index);
1031     if (fFreeProc!=NULL && fList[index]!=NULL) {
1032     (*fFreeProc)(fList[index]); //freeItem
1033     }
1034     fList[index]=NULL;
1035     fCount--;
1036     if (index<fCount) //move higher elements if any
1037     memmove(&fList[index], &fList[index+1], (fCount-index)*sizeof(OBJ*));
1038     }
1039    
1040     //Stack usage:
1041     template <class OBJ> OBJ* GList<OBJ>::Pop() {
1042     if (fCount<=0) return NULL;
1043     fCount--;
1044     OBJ* o=fList[fCount];
1045     fList[fCount]=NULL;
1046     return o;
1047     }
1048    
1049     //Queue usage:
1050     template <class OBJ> OBJ* GList<OBJ>::Shift() {
1051     if (fCount<=0) return NULL;
1052     fCount--;
1053     OBJ* o=fList[0];
1054     if (fCount>0)
1055     memmove(&fList[0], &fList[1], (fCount)*sizeof(OBJ*));
1056     fList[fCount]=NULL; //not that it matters..
1057     return o;
1058     }
1059    
1060     template <class OBJ> int GList<OBJ>::Remove(OBJ* item) {
1061     //removes an item if it's in our list
1062     int result=IndexOf(item);
1063     if (result>=0) Delete(result);
1064     return result;
1065     }
1066    
1067     //linear search for the pointer
1068     template <class OBJ> int GList<OBJ>::RemovePtr(OBJ* item) {
1069     int i;
1070     if (item==NULL) return -1;
1071     for (i=0;i<fCount;i++)
1072     if (fList[i]==item) break;
1073     if (i==fCount) return -1; //not found
1074     Delete(i);
1075     return i;
1076     }
1077    
1078    
1079     template <class OBJ> void GList<OBJ>::Pack() {//also frees items!
1080     for (int i=fCount-1; i>=0; i--)
1081     if (fList[i]==NULL) Delete(i); //also shift contents of fList accordingly
1082     }
1083    
1084     template <class OBJ> void GList<OBJ>::setCount(int NewCount) {
1085     if (NewCount<0 || NewCount > MAXLISTSIZE)
1086     GError(SLISTCOUNT_ERR, NewCount);
1087     if (NewCount > fCapacity) setCapacity(NewCount);
1088     if (NewCount > fCount)
1089     memset(fList[fCount], 0, (NewCount - fCount) * sizeof(OBJ*));
1090     fCount = NewCount;
1091     }
1092    
1093     template <class OBJ> void GList<OBJ>::QuickSort(int L, int R) {
1094     int I, J;
1095     OBJ* P;
1096     OBJ* T;
1097     do {
1098     I = L;
1099     J = R;
1100     P = fList[(L + R) >> 1];
1101     do {
1102     while (fCompareProc(fList[I], P) < 0) I++;
1103     while (fCompareProc(fList[J], P) > 0) J--;
1104     if (I <= J) {
1105     T = fList[I];
1106     fList[I] = fList[J];
1107     fList[J] = T;
1108     I++;
1109     J--;
1110     }
1111     }
1112     while (I <= J);
1113     if (L < J) QuickSort(L, J);
1114     L = I;
1115     }
1116     while (I < R);
1117    
1118     }
1119    
1120     template <class OBJ> void GList<OBJ>::Sort() {
1121     if (fList!=NULL && fCount>0 && fCompareProc!=NULL)
1122     QuickSort(0, fCount-1);
1123     }
1124    
1125     //---------------------------------------------------------------------------
1126     #endif