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, 4 months ago) by gpertea
File size: 32387 byte(s)
Log Message:
added my gclib source files

Line File contents
1 //---------------------------------------------------------------------------
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