ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 310
Committed: Fri Mar 22 20:06:27 2013 UTC (6 years, 7 months ago) by gpertea
File size: 20829 byte(s)
Log Message:
sync with igm repo

Line File contents
1 //---------------------------------------------------------------------------
2 /*
3 Sortable collections of objects and object pointers
4 */
5 #ifndef _GList_HH
6 #define _GList_HH
7
8 #include "GVec.hh"
9
10 #define GLIST_SORTED_ERR "Operation not allowed on a sorted list!\n"
11 #define GLIST_UNSORTED_ERR "Operation not allowed on an unsorted list!\n"
12
13 //------ useful macros:
14 #define BE_UNSORTED if (fCompareProc!=NULL) { GError(GLIST_SORTED_ERR); return; }
15 #define BE_SORTED if (fCompareProc==NULL) { GError(GLIST_UNSORTED_ERR); return; }
16
17 #define SORTED (fCompareProc!=NULL)
18 #define UNSORTED (fCompareProc==NULL)
19
20 // GArray is the sortable array type, requires the comparison operator < to be defined
21 template <class OBJ> class GArray:public GVec<OBJ> {
22 protected:
23 bool fUnique;
24 static int DefaultCompareProc(const pointer item1, const pointer item2) {
25 //operator< MUST be defined for OBJ class!
26 if (*((OBJ*)item2) < *((OBJ*)item1)) return 1;
27 else if (*((OBJ*)item1) < *((OBJ*)item2)) return -1;
28 else return 0;
29 }
30 GCompareProc* fCompareProc;
31 public:
32 GArray(GCompareProc* cmpFunc=NULL);
33 GArray(bool sorted, bool unique=false);
34 GArray(int init_capacity, bool sorted, bool unique=false);
35 GArray(GArray<OBJ>& array); //copy constructor
36 const GArray<OBJ>& operator=(GArray<OBJ>& array);
37 //~GArray();
38 //assignment operator
39 void setSorted(GCompareProc* cmpFunc);
40 void setSorted(bool sorted) {
41 if (sorted) {
42 if (fCompareProc!=&DefaultCompareProc) {
43 fCompareProc=&DefaultCompareProc;
44 Sort();
45 }
46 }
47 else fCompareProc=NULL;
48 }
49 //sort the array if cmpFunc not NULL or changes
50 int Add(OBJ* item); // specific implementation if sorted
51 int Add(OBJ& item) { return Add(&item); } //both will CREATE a new OBJ and COPY to it
52 // using OBJ new operator=
53 int cAdd(OBJ item) { return Add(&item); }
54 int cPush(OBJ item) { return Add(&item); }
55 int Push(OBJ& item) { return Add(&item); }
56
57 void Add(GArray<OBJ>& list); //add copies of all items from another list
58 //this will reject identical items in sorted lists only!
59 void setUnique(bool beUnique) { fUnique = beUnique; };
60 void Sort(); //explicit sort may be requested
61 bool Sorted() { return fCompareProc!=NULL; }
62 void Replace(int idx, OBJ& item); //Put, use operator= to copy
63 int Unique() { return fUnique; }
64 int IndexOf(OBJ& item);
65 //this needs the == operator to have been defined for OBJ
66 bool Found(OBJ& item, int& idx); // for sorted arrays only;
67 //search by content; if found, returns true and idx will be the index
68 //of the first item found matching for which fCompareProc returns 0
69 bool Exists(OBJ& item); //same as above without existing index info
70 //unsorted only, place item at position idx:
71 void Move(int curidx, int newidx);
72 void Insert(int idx, OBJ* item);
73 void Insert(int idx, OBJ item) { Insert(idx,&item); }
74 };
75
76 //GList is a sortable collection of pointers to objects; requires operator< to be defined, or a custom compare function
77 template <class OBJ> class GList:public GPVec<OBJ> {
78 protected:
79 bool fUnique;
80 GCompareProc* fCompareProc; //a pointer to a Compare function
81
82 static int DefaultCompareProc(const pointer item1, const pointer item2) {
83 //operator< MUST be defined for OBJ class!
84 if (*((OBJ*)item2) < *((OBJ*)item1)) return 1;
85 else if (*((OBJ*)item1) < *((OBJ*)item2)) return -1;
86 else return 0;
87 }
88 public:
89 void sortInsert(int idx, OBJ* item);
90 GList(GCompareProc* compareProc=NULL); //free by default
91 GList(GCompareProc* compareProc, //unsorted by default
92 GFreeProc *freeProc,
93 bool beUnique=false);
94 GList(bool sorted, bool free_elements=true, bool beUnique=false);
95 GList(int init_capacity, bool sorted, bool free_elements=true, bool beUnique=false);
96 GList(GList<OBJ>& list); //copy constructor?
97 GList(GList<OBJ>* list); //kind of a copy constructor
98 const GList<OBJ>& operator=(GList<OBJ>& list);
99 //void Clear();
100 //~GList();
101 void setSorted(GCompareProc* compareProc);
102 //sorted if compareProc not NULL; sort the list if compareProc changes !
103 bool Sorted() { return fCompareProc!=NULL; }
104 void setSorted(bool sorted) {
105 if (sorted) {
106 if (fCompareProc!=&DefaultCompareProc) {
107 fCompareProc=&DefaultCompareProc;
108 Sort();
109 }
110 }
111 else fCompareProc=NULL;
112 }
113 int Add(OBJ* item); //-- specific implementation if sorted
114 void Add(GList<OBJ>& list); //add all pointers from another list
115
116 OBJ* AddIfNew(OBJ* item, bool deleteIfFound=true, int* fidx=NULL);
117 // default: delete item if Found() (and pointers are not equal)!
118 //returns the equal (==) object if it's in the list already
119 //or the item itself if it is unique and actually added
120
121 int AddedIfNew(OBJ* item);
122 // if Found(item) (and pointers are not equal) delete item and returns -1
123 // if added, returns the new item index
124
125
126 int Unique() { return fUnique; }
127 //this will reject identical items in sorted lists only!
128 void setUnique(bool beUnique) { fUnique = beUnique; };
129
130 GCompareProc* GetCompareProc() {return fCompareProc;}
131 int IndexOf(OBJ* item); //this has a specific implementation for sorted lists
132 //if list is sorted, item data is located by binary search
133 //based on the Compare function
134 //if not, a linear search is performed, but
135 //this needs the == operator to have been defined for OBJ
136
137 void Put(int idx, OBJ* item, bool re_sort=false);
138 bool Found(OBJ* item, int & idx); // sorted only;
139 //search by content; if found, returns true and idx will be the index
140 //of the first item found matching for which GTCompareProc returns 0
141 bool Exists(OBJ* item); //same as above without existing index info
142 bool Exists(OBJ& item); //same as above without existing index info
143 void Sort(); //explicit sort may be requested using this function
144 int Remove(OBJ* item); //search for pointer, using binary search if sorted
145 void Insert(int idx, OBJ* item); //unsorted only, place item at position idx
146 void Move(int curidx, int newidx);
147 }; //GList
148
149
150
151 //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
152
153 template <class OBJ> GArray<OBJ>::GArray(GArray<OBJ>& array):GVec<OBJ>(0) { //copy constructor
154 this->fCount=array.fCount;
155 this->fCapacity=array.fCapacity;
156 this->fArray=NULL;
157 if (this->fCapacity>0) {
158 //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
159 this->fArray=new OBJ[this->fCapacity];
160 }
161 this->fCount=array.fCount;
162 fUnique=array.fUnique;
163 fCompareProc=array.fCompareProc;
164 // uses OBJ operator=
165 for (int i=0;i<this->fCount;i++) this->fArray[i]=array[i];
166 }
167
168 template <class OBJ> const GArray<OBJ>& GArray<OBJ>::operator=(GArray<OBJ>& array) {
169 if (&array==this) return *this;
170 GVec<OBJ>::Clear();
171 this->fCount=array.fCount;
172 this->fUnique=array.fUnique;
173 this->fCapacity=array.fCapacity;
174 if (this->fCapacity>0) {
175 //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
176 this->fArray=new OBJ[this->fCapacity];
177 }
178 this->fCompareProc=array.fCompareProc;
179 this->fCount=array.fCount;
180 // uses OBJ operator=
181 for (int i=0;i<this->fCount;i++) {
182 this->fArray[i]=array[i];
183 }
184 return *this;
185 }
186
187 template <class OBJ> GArray<OBJ>::GArray(GCompareProc* cmpFunc):GVec<OBJ>(0) {
188 fCompareProc = cmpFunc;
189 fUnique = false; //only affects sorted lists
190 }
191
192 template <class OBJ> GArray<OBJ>::GArray(bool sorted, bool unique):GVec<OBJ>(0) {
193 fUnique=unique;
194 fCompareProc = sorted ? DefaultCompareProc : NULL;
195 }
196
197 template <class OBJ> GArray<OBJ>::GArray(int init_capacity,
198 bool sorted, bool unique):GVec<OBJ>(init_capacity) {
199 fUnique=unique;
200 fCompareProc=sorted ? DefaultCompareProc : NULL;
201 }
202
203 template <class OBJ> void GArray<OBJ>::setSorted(GCompareProc* cmpFunc) {
204 GCompareProc* old_proc=fCompareProc;
205 fCompareProc=cmpFunc;
206 if (fCompareProc!=old_proc && fCompareProc!=NULL)
207 Sort(); //new compare method
208 }
209
210 template <class OBJ> int GArray<OBJ>::IndexOf(OBJ& item) {
211 int result=0;
212 if (Found(item, result)) return result;
213 else return -1;
214 }
215
216 template <class OBJ> bool GArray<OBJ>::Exists(OBJ& item) {
217 int result=0;
218 if (Found(item, result)) return true;
219 else return false;
220 }
221
222
223 template <class OBJ> int GArray<OBJ>::Add(OBJ* item) {
224 if (item==NULL) return -1;
225 int result;
226 if (SORTED) {
227 if (Found(*item, result))
228 if (fUnique) return -1; //cannot add a duplicate!
229 //Found sets result to the position where the item should be!
230 GVec<OBJ>::Insert(result, *item);
231 }
232 else {
233 if (fUnique && Found(*item,result)) return -1; //set behaviour
234 result = this->fCount;
235 if (result==this->fCapacity) GVec<OBJ>::Grow();
236 this->fArray[result] = *item; //operator=, copies the item
237 this->fCount++;
238 }
239 return result;
240 }
241
242
243 template <class OBJ> void GArray<OBJ>::Add(GArray<OBJ>& list) {
244 if (list.Count()==0) return;
245 if (SORTED) {
246 for (int i=0;i<list.fCount;i++) Add(&list[i]);
247 }
248 else { //simply copy
249 this->setCapacity(this->fCapacity+list.fCount);
250 int s=this->fCount;
251 for (int i=0;i<list.fCount;i++)
252 this->fArray[s+i]=list.fArray[i];
253 this->fCount+=list.fCount;
254 }
255 }
256
257 template <class OBJ> bool GArray<OBJ>::Found(OBJ& item, int& idx) {
258 //search the list by using fCompareProc (if defined)
259 //or == operator for a non-sortable list
260 //for sorted lists, even when the result is false, the idx is
261 //set to the closest matching object!
262 int i;
263 idx=-1;
264 if (this->fCount==0) { idx=0;return false;}
265 if (SORTED) { //binary search based on fCompareProc
266 //do the simplest tests first:
267 if ((*fCompareProc)(&(this->fArray[0]),&item)>0) {
268 idx=0;
269 return false;
270 }
271 if ((*fCompareProc)(&item, &(this->fArray[this->fCount-1]))>0) {
272 idx=this->fCount;
273 return false;
274 }
275
276 int l=0;
277 int h = this->fCount - 1;
278 int c;
279 while (l <= h) {
280 i = (l + h) >> 1;
281 c = (*fCompareProc)(&(this->fArray[i]), &item);
282 if (c < 0) l = i + 1;
283 else {
284 h = i - 1;
285 if (c == 0) { //found!
286 idx=i;
287 return true;
288 }
289 }
290 } //while
291 idx = l;
292 return false;
293 }
294 else {//not sorted: use linear search
295 // needs == operator to compare user defined objects !
296 i=0;
297 while (i<this->fCount) {
298 if (this->fArray[i]==item) { //requires operator==
299 idx=i;
300 return true;
301 }
302 i++;
303 }
304 return false;
305 }
306 }
307
308 template <class OBJ> void GArray<OBJ>::Insert(int idx, OBJ* item) {
309 //idx can be [0..fCount] so an item can be actually added
310 BE_UNSORTED; //forbid this operation on sorted data
311 GVec<OBJ>::Insert(idx, item);
312 }
313
314
315 template <class OBJ> void GArray<OBJ>::Move(int curidx, int newidx) {
316 BE_UNSORTED; //cannot do this in a sorted list!
317 if (curidx!=newidx || newidx>=this->fCount)
318 GError(GVEC_INDEX_ERR, newidx);
319
320 OBJ tmp=this->fArray[curidx]; //copy constructor here
321 this->fArray[curidx]=this->fArray[newidx];
322 this->fArray[newidx]=tmp;
323 }
324
325 template <class OBJ> void GArray<OBJ>::Replace(int idx, OBJ& item) {
326 //TEST_INDEX(idx);
327 if (idx<0 || idx>=this->fCount) GError(GVEC_INDEX_ERR, __FILE__,__LINE__, idx);
328 this->fArray[idx]=item;
329 if ( SORTED ) Sort(); //re-sort ! this could be very expensive, don't do it
330 }
331
332 template <class OBJ> void GArray<OBJ>::Sort() {
333 if (fCompareProc==NULL) { fCompareProc=DefaultCompareProc; }
334 if (this->fArray!=NULL && this->fCount>0)
335 this->qSort(0, this->fCount-1, fCompareProc);
336 }
337
338 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
339 //*=> GList implementation -- sortable array of pointers to OBJ
340
341 template <class OBJ> GList<OBJ>::GList(GList<OBJ>& list):GPVec<OBJ>(list) { //copy constructor
342 fUnique=list.fUnique;
343 fCompareProc=list.fCompareProc;
344 }
345
346 template <class OBJ> GList<OBJ>::GList(GList<OBJ>* plist):GPVec<OBJ>(0) { //another copy constructor
347 this->fCapacity=plist->fCapacity;
348 this->fList=NULL;
349 if (this->fCapacity>0) {
350 GMALLOC(this->fList, this->fCapacity*sizeof(OBJ*));
351 }
352 fUnique=plist->fUnique;
353 fCompareProc=plist->fCompareProc;
354 this->fFreeProc=plist->fFreeProc;
355 this->fCount=plist->fCount;
356 memcpy(this->fList, plist->fList, this->fCount*sizeof(OBJ*));
357 //for (int i=0;i<list->fCount;i++) Add(plist->Get(i));
358 }
359
360 template <class OBJ> void GList<OBJ>::Add(GList<OBJ>& list) {
361 if (list.Count()==0) return;
362 if (SORTED) {
363 for (int i=0;i<list.Count();i++) Add(list[i]);
364 }
365 else { //simply copy
366 this->setCapacity(this->fCapacity+list.fCount);
367 memcpy( & (this->fList[this->fCount]), list.fList, list.fCount*sizeof(OBJ*));
368 this->fCount+=list.fCount;
369 }
370 }
371
372
373 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc,
374 GFreeProc* freeProc, bool beUnique) {
375 fCompareProc = compareProc;
376 this->fFreeProc = freeProc;
377 fUnique = beUnique; //only affects sorted lists
378 }
379
380 template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
381 fCompareProc = compareProc;
382 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
383 fUnique = false; //only affects sorted lists
384 }
385
386 template <class OBJ> GList<OBJ>::GList(bool sorted,
387 bool free_elements, bool beUnique) {
388 if (sorted) {
389 if (free_elements) {
390 fCompareProc=&DefaultCompareProc;
391 this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
392 fUnique=beUnique;
393 }
394 else {
395 fCompareProc=&DefaultCompareProc;
396 this->fFreeProc=NULL;
397 fUnique=beUnique;
398 }
399 }
400 else {
401 if (free_elements) {
402 fCompareProc=NULL;
403 this->fFreeProc=GPVec<OBJ>::DefaultFreeProc;
404 fUnique=beUnique;
405 }
406 else {
407 fCompareProc=NULL;
408 this->fFreeProc=NULL;
409 fUnique=beUnique;
410 }
411 }
412 }
413
414
415 template <class OBJ> GList<OBJ>::GList(int init_capacity, bool sorted,
416 bool free_elements, bool beUnique):GPVec<OBJ>(init_capacity, free_elements) {
417 if (sorted) {
418 fCompareProc=&DefaultCompareProc;
419 fUnique=beUnique;
420 }
421 else {
422 fCompareProc=NULL;
423 fUnique=beUnique;
424 }
425 }
426
427 template <class OBJ> const GList<OBJ>& GList<OBJ>::operator=(GList& list) {
428 if (&list!=this) {
429 GPVec<OBJ>::Clear();
430 fCompareProc=list.fCompareProc;
431 this->fFreeProc=list.fFreeProc;
432 //Attention: the object pointers are copied directly,
433 //but the actual objects are NOT duplicated
434 for (int i=0;i<list.Count();i++) Add(list[i]);
435 }
436 return *this;
437 }
438
439 template <class OBJ> void GList<OBJ>::setSorted(GCompareProc* compareProc) {
440 GCompareProc* old_proc=fCompareProc;
441 fCompareProc=compareProc;
442 if (fCompareProc!=old_proc && fCompareProc!=NULL)
443 Sort(); //new compare method
444 }
445
446 template <class OBJ> int GList<OBJ>::IndexOf(OBJ* item) {
447 int result=0;
448 if (Found(item, result)) return result;
449 else return -1;
450 }
451
452 template <class OBJ> bool GList<OBJ>::Exists(OBJ& item) {
453 int result=0;
454 if (Found(&item, result)) return true;
455 else return false;
456 }
457
458 template <class OBJ> bool GList<OBJ>::Exists(OBJ* item) {
459 int result=0;
460 if (Found(item, result)) return true;
461 else return false;
462 }
463
464 template <class OBJ> int GList<OBJ>::Add(OBJ* item) {
465 int result;
466 if (item==NULL) return -1;
467 if (SORTED) {
468 if (Found(item, result))
469 if (fUnique) return -1; //duplicates forbidden
470 //Found sets result to the position where the item should be!
471 sortInsert(result, item);
472 }
473 else {
474 if (fUnique && Found(item,result)) return -1; //set behaviour
475 result = this->fCount;
476 if (result==this->fCapacity) GPVec<OBJ>::Grow();
477 this->fList[result]=item;
478 this->fCount++;
479 }
480 return result;
481 }
482
483 //by default, it deletes the item if it has an equal in the list!
484 //returns the existing equal (==) object if it's in the list already
485 //or returns the item itself if it's unique (and adds it)
486 template <class OBJ> OBJ* GList<OBJ>::AddIfNew(OBJ* item,
487 bool deleteIfFound, int* fidx) {
488 int r;
489 if (Found(item, r)) {
490 if (deleteIfFound && (pointer)item != (pointer)(this->fList[r])) {
491 this->deallocate_item(item);
492 }
493 if (fidx!=NULL) *fidx=r;
494 return this->fList[r]; //found
495 }
496 //not found:
497 if (SORTED) {
498 //Found() set result to the position where the item should be inserted:
499 sortInsert(r, item);
500 }
501 else {
502 r = this->fCount;
503 if (r==this->fCapacity) GPVec<OBJ>::Grow();
504 this->fList[r]=item;
505 this->fCount++;
506 }
507 if (fidx!=NULL) *fidx=r;
508 return item;
509 }
510
511 //if item is found already in the list DELETE it and return -1
512 //otherwise the item is added and its index is returned
513 template <class OBJ> int GList<OBJ>::AddedIfNew(OBJ* item) {
514 int r;
515 if (Found(item, r)) {
516 if ((pointer)item != (pointer)(this->fList[r])) {
517 this->deallocate_item(item);
518 }
519 return -1;
520 }
521 //not found:
522 if (SORTED) {
523 //Found() set r to the position where the item should be inserted:
524 sortInsert(r, item);
525 }
526 else {
527 r = this->fCount;
528 if (r==this->fCapacity) GPVec<OBJ>::Grow();
529 this->fList[r]=item;
530 this->fCount++;
531 }
532 return r;
533 }
534
535
536 template <class OBJ> bool GList<OBJ>::Found(OBJ* item, int& idx) {
537 //search the list by using fCompareProc (if defined)
538 //or == operator for a non-sortable list
539 //for sorted lists, even when the result is false, the idx is
540 //set to the closest matching object!
541 int i;
542 idx=-1;
543 if (this->fCount==0) { idx=0;return false;}
544 if (SORTED) { //binary search based on fCompareProc
545 //do the simple test first:
546
547 if ((*fCompareProc)(this->fList[0],item)>0) {
548 idx=0;
549 return false;
550 }
551 if ((*fCompareProc)(item, this->fList[this->fCount-1])>0) {
552 idx=this->fCount;
553 return false;
554 }
555
556 int l, h, c;
557 l = 0;
558 h = this->fCount - 1;
559 while (l <= h) {
560 i = (l + h) >> 1;
561 c = (*fCompareProc)(this->fList[i], item);
562 if (c < 0) l = i + 1;
563 else {
564 h = i - 1;
565 if (c == 0) {
566 idx=i;
567 return true;
568 }
569 }
570 } //while
571 idx = l;
572 return false;
573 }
574 else {//not sorted: use linear search
575 // needs == operator to compare user defined objects !
576 i=0;
577 while (i<this->fCount) {
578 if (*this->fList[i]==*item) {
579 idx=i;
580 return true;
581 }
582 i++;
583 }
584 return false;
585 }
586 }
587
588 template <class OBJ> void GList<OBJ>::sortInsert(int idx, OBJ* item) {
589 //idx must be the new position this new item must have
590 //so the allowed range is [0..fCount]
591 //the old idx item all the above will be shifted to idx+1
592 if (idx<0 || idx>this->fCount) GError(GVEC_INDEX_ERR, idx);
593 if (this->fCount==this->fCapacity) {
594 GPVec<OBJ>::Grow(idx, item);
595 //expand and also copy/move data and insert the new item
596 return;
597 }
598 //room still left, just move data around and insert the new one
599 if (idx<this->fCount) //copy/move pointers only!
600 memmove(&(this->fList[idx+1]), &(this->fList[idx]), (this->fCount-idx)*sizeof(OBJ*));
601 this->fList[idx]=item;
602 this->fCount++;
603 }
604
605 template <class OBJ> void GList<OBJ>::Insert(int idx, OBJ* item) {
606 //idx can be [0..fCount] so an item can be actually added
607 BE_UNSORTED; //cannot do that with a sorted list!
608 GPVec<OBJ>::Insert(idx,item);
609 }
610
611 template <class OBJ> void GList<OBJ>::Move(int curidx, int newidx) {
612 BE_UNSORTED; //cannot do this in a sorted list!
613 GPVec<OBJ>::Move(curidx,newidx);
614 }
615
616 template <class OBJ> void GList<OBJ>::Put(int idx, OBJ* item, bool re_sort) {
617 //WARNING: this will never free the replaced item!
618 // this may BREAK the sort order unless the "re_sort" parameter is given
619 if (idx<0 || idx>this->fCount) GError(GVEC_INDEX_ERR, idx);
620 this->fList[idx]=item;
621 if (SORTED && item!=NULL && re_sort) Sort(); //re-sort
622 }
623
624 template <class OBJ> int GList<OBJ>::Remove(OBJ* item) {
625 //removes an item if it's in our list
626 int result=IndexOf(item);
627 if (result>=0) GPVec<OBJ>::Delete(result);
628 return result;
629 }
630
631 template <class OBJ> void GList<OBJ>::Sort() {
632 if (fCompareProc==NULL) fCompareProc = DefaultCompareProc;
633 if (this->fList!=NULL && this->fCount>0)
634 this->qSort(0, this->fCount-1, fCompareProc);
635 }
636
637 //---------------------------------------------------------------------------
638 #endif