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