ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
Revision: 264
Committed: Mon Aug 27 18:21:11 2012 UTC (6 years, 9 months ago) by gpertea
File size: 20352 byte(s)
Log Message:
minor refactoring etc

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