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