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