ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GList.hh
(Generate patch)
# Line 8 | Line 8
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"
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"
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"
23 < #define SLISTCOUNT_ERR "GList error: invalid count: %d"
24 < #define SLISTSORTED_ERR "Operation not allowed on a sorted list!"
25 < #define SLISTUNSORTED_ERR "Operation not allowed on an unsorted list!"
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; }
# Line 36 | Line 37
37       if (x<0 || x>=fCount) GError(SLISTINDEX_ERR, x) */
38  
39  
40 < //template for array of objects
41 < template <class OBJ> class GArray {
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 <    bool fUnique;
47 >  public:
48 >    GVec(int init_capacity=20);
49 >    GVec(GVec<OBJ>& array); //copy constructor
50 >    const GVec<OBJ>& operator=(GVec& array); //copy operator
51 >    virtual ~GVec();
52 >    void idxInsert(int idx, OBJ& item);
53 >    void Grow();
54 >    void Grow(int idx, OBJ& item);
55 >    void Reverse(); //WARNING: will break the sort order if SORTED!
56 >    int Add(OBJ* item); // simply append to the end of fArray, reallocating as needed
57 >    int Add(OBJ& item) { return Add(&item); } //both will CREATE a new OBJ and COPY to it
58 >                       // using OBJ new operator=
59 >    void Add(GVec<OBJ>& list); //append copies of all items from another list
60 >    OBJ& Get(int idx) {
61 >          TEST_INDEX(idx);
62 >          return fArray[idx];
63 >          }
64 >    OBJ& operator[](int i) {
65 >          TEST_INDEX(i);
66 >          return fArray[i];
67 >          }
68 >    void Clear();
69 >    void Insert(int idx, OBJ* item);
70 >    void Delete(int index);
71 >    void Replace(int idx, OBJ& item); //Put, use operator= to copy
72 >    void Exchange(int idx1, int idx2);
73 >    void Swap(int idx1, int idx2)  { Exchange(idx1, idx2); }
74 >    int  Capacity() { return fCapacity; }
75 >    //this will reject identical items in sorted lists only!
76 >    void setCapacity(int NewCapacity);
77 >    int  Count() { return fCount; }
78 >    void setCount(int NewCount); //?! - will trim or expand the array as needed
79 >    void Move(int curidx, int newidx);
80 > };
81  
82 + // GArray is the sortable collection, but requires the comparison operators to be defined
83 + template <class OBJ> class GArray:public GVec<OBJ> {
84 +  protected:
85 +    bool fUnique;
86      static int DefaultCompareProc(OBJ& item1, OBJ& item2) {
87        //the comparison operators MUST be defined for OBJ class!
88        if ( item1 > item2) return 1;
# Line 53 | Line 92
92      typedef int CompareProc(OBJ& item1, OBJ& item2);
93    protected:
94      CompareProc* fCompareProc;
56    void idxInsert(int idx, OBJ& item);
57    void Grow();
58    void Grow(int idx, OBJ& item);
95      void qSort(int L, int R);
96    public:
97      GArray(CompareProc* cmpFunc=NULL);
# Line 63 | Line 99
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 <    virtual ~GArray();
102 >    //~GArray();
103      //assignment operator
104      void setSorted(CompareProc* cmpFunc);
105      //sort the array if cmpFunc not NULL or changes
70    void Reverse(); //WARNING: will break the sort order if SORTED!
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
75    OBJ& Get(int idx) {
76          TEST_INDEX(idx);
77          return fArray[idx];
78          }
79    OBJ& operator[](int i) {
80          TEST_INDEX(i);
81          return fArray[i];
82          }
83    void Clear();
84    void Delete(int index);
85    void Exchange(int idx1, int idx2);
86    int Capacity() { return fCapacity; }
87    int Unique() { return fUnique; }
110      //this will reject identical items in sorted lists only!
111      void setUnique(bool beUnique) { fUnique = beUnique; };
90    void setCapacity(int NewCapacity);
91    int Count() { return fCount; }
92    void setCount(int NewCount);
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;
# Line 99 | Line 120
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); }
104    void Replace(int idx, OBJ& item); //Put, use operator= to copy
105    void Move(int curidx, int newidx);
126   };
127  
128   //------- template for array of pointers to objects ---------
129 < template <class OBJ> class GList {
129 > template <class OBJ> class GPVec {
130    protected:
131      OBJ** fList; //pointer to an array of pointers to objects
132      int fCount; //total number of entries in list
133      int fCapacity; //current allocated size
134 +    GFreeProc* fFreeProc; //useful for deleting objects
135 +    //---
136 +    void Expand();
137 +    void Grow();
138 +    void Grow(int idx, OBJ* newitem);
139 +    void setCount(int NewCount); //will trim/expand the array as needed
140 +  public:  
141 +    static void DefaultFreeProc(pointer item) {
142 +      delete (OBJ*)item;
143 +      }
144 +    virtual ~GPVec();
145 +    GPVec(int init_capacity=10, bool free_elements=true); //also the default constructor
146 +    GPVec(GPVec<OBJ>& list); //copy constructor?
147 +    GPVec(GPVec<OBJ>* list); //kind of a copy constructor
148 +    const GPVec<OBJ>& operator=(GPVec& list);
149 +    OBJ* Get(int i);
150 +    OBJ* operator[](int i) { return this->Get(i); }
151 +    void Reverse(); //reverse pointer array; WARNING: will break the sort order if sorted!
152 +    void freeItem(int idx); //calls fFreeProc (or DefaultFreeProc) on fList[idx] and sets NULL there, doesn't pack!
153 +                      //it will free even if fFreeProc is NULL!
154 +    void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
155 +    void setFreeItem(bool doFree) {
156 +       if (doFree) fFreeProc=DefaultFreeProc;
157 +             else  fFreeProc=NULL;
158 +       }
159 +    // -- stack usage:
160 +    int Push(OBJ* item) { return Add(item); }
161 +    OBJ* Pop();// Stack use; removes and returns last item,but does NOT FREE it
162 +    OBJ* Shift(); //Queue use: removes and returns first item, but does NOT FREE it
163 +    void deallocate_item(OBJ* item); //forcefully call fFreeProc or delete on item
164 +    void Clear();
165 +    void Exchange(int idx1, int idx2);
166 +    void Swap(int idx1, int idx2)  { Exchange(idx1, idx2); }
167 +    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
116    GFreeProc* fFreeProc; //useful for deleting objects
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        }
123    void Expand();
124    void Grow();
196      void QuickSort(int L, int R);
197    public:
198      void sortInsert(int idx, OBJ* item);
128    static void DefaultFreeProc(pointer item) {
129      delete (OBJ*)item;
130      }
199      GList(GCompareProc* compareProc=NULL); //free by default
200      GList(GCompareProc* compareProc, //unsorted by default
201          GFreeProc *freeProc,
# Line 136 | Line 204
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 <    virtual ~GList();
208 <    void Reverse(); //reverse pointer array; WARNING: will break the sort order if sorted!
209 <    void freeItem(int idx);
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 !
144    void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
145    void setFreeItem(bool doFree) {
146       if (doFree) fFreeProc=DefaultFreeProc;
147             else  fFreeProc=NULL;
148       }
212      bool Sorted() { return fCompareProc!=NULL; }
213      void setSorted(bool sorted) {
214       if (sorted) {
# Line 162 | Line 225
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 it addsit
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  
167    // -- stack usage:
168    int Push(OBJ* item) { return Add(item); }
169    OBJ* Pop();// Stack use; removes and returns last item,but does NOT FREE it
170    OBJ* Shift(); //Queue use: removes and returns first item, but does NOT FREE it
171    void Clear();
172    void Delete(int index);
173    void Forget(int idx);
174    void Exchange(int idx1, int idx2);
175    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; }
235      int Unique() { return fUnique; }
236      //this will reject identical items in sorted lists only!
237      void setUnique(bool beUnique) { fUnique = beUnique; };
238  
184    void setCapacity(int NewCapacity);
185    int Count() { return fCount; }
186    void setCount(int NewCount);
239      GCompareProc* GetCompareProc() {return fCompareProc;}
188    OBJ* Get(int idx);
189    OBJ* operator[](int i);
190    void Grow(int idx, OBJ* item);
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 <    void Put(int idx, OBJ* item, bool re_sort=false);
204 <    int Remove(OBJ* item); //search for pointer, using binary search if sorted
205 <    int RemovePtr(OBJ* item); //always use linear search to find the pointer!
206 <    void Pack();
207 <    void Sort(); //explicit sort may be requested using this function
208 <    const GList<OBJ>& operator=(GList& list);
209 < };
256 > }; //GList
257  
258  
259 < //basic template for a Stack of pointers
259 > //basic template for a Stack of pointers (implemented as a linked list)
260   template <class OBJ> class GStack {
261   protected:
262     struct StackOBJ {
# Line 257 | Line 304
304  
305   //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
306  
307 < template <class OBJ> GArray<OBJ>::GArray(GArray& array) { //copy constructor
308 < fCount=array.fCount;
309 < fCapacity=array.fCapacity;
310 < if (fCapacity>0) {
311 <    GMALLOC(fArray, fCapacity*sizeof(OBJ));
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 >    //GMALLOC(fArray, fCapacity*sizeof(OBJ));
320 >    fArray=new OBJ[this->fCapacity];
321      }
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 +    //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
333 +    this->fArray=new OBJ[this->fCapacity];
334 +    }
335 + this->fCount=array.fCount;
336   fUnique=array.fUnique;
337   fCompareProc=array.fCompareProc;
268 fCount=array.fCount;
338   // uses OBJ operator=
339 < for (int i=0;i<fCount;i++) fArray[i]=array[i];
339 > for (int i=0;i<this->fCount;i++) this->fArray[i]=array[i];
340   }
341  
342 < template <class OBJ> const GArray<OBJ>& GArray<OBJ>::operator=(GArray& array) {
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;
277 fUnique=array.fUnique;
346   fCapacity=array.fCapacity;
347   if (fCapacity>0) {
348 <    GMALLOC(fArray, fCapacity*sizeof(OBJ));
348 >    //GMALLOC(fArray, fCapacity*sizeof(OBJ));
349 >    fArray=new OBJ[this->fCapacity];
350      }
282 fCompareProc=array.fCompareProc;
351   fCount=array.fCount;
352   // uses OBJ operator=
353   for (int i=0;i<fCount;i++) {
# Line 287 | Line 355
355     }
356   return *this;
357   }
358 < template <class OBJ> GArray<OBJ>::GArray(CompareProc* cmpFunc) {
359 <  fCount=0;
360 <  fCapacity=0;
361 <  fArray=NULL;
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 >    //GMALLOC(this->fArray, this->fCapacity*sizeof(OBJ));
367 >    this->fArray=new OBJ[this->fCapacity];
368 >    }
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) {
299 <  fCount=0;
300 <  fCapacity=0;
301 <  fArray=NULL;
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) {
308 <  fCount=0;
309 <  fCapacity=0;
310 <  fArray=NULL;
389 >                        bool sorted, bool unique):GVec<OBJ>(init_capacity) {
390    fUnique=unique;
391    fCompareProc=sorted? &DefaultCompareProc : NULL;
313  setCapacity(init_capacity);
392   }
393  
394 < template <class OBJ> GArray<OBJ>::~GArray() {
395 < Clear();//this will free the items if fFreeProc is defined
394 > template <class OBJ> GVec<OBJ>::~GVec() {
395 > this->Clear();
396   }
397  
398 < template <class OBJ> void GArray<OBJ>::setCapacity(int NewCapacity) {
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 <      GFREE(fArray);
405 >      //GFREE(fArray);
406 >      delete[] fArray;
407        }
408      else {
409 <      GREALLOC(fArray, NewCapacity*sizeof(OBJ));
409 >      //GREALLOC(fArray, NewCapacity*sizeof(OBJ));
410 >      OBJ* oldArray=fArray;
411 >      fArray=new OBJ[NewCapacity];
412 >      for (int i=0;i<this->fCount;i++) {
413 >        fArray[i] = oldArray[i];
414 >        }
415        }
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 <  setCount(0);
430 <  setCapacity(0); //so the array itself is deallocated too!
429 >  GVec<OBJ>::setCount(0);
430 >  GVec<OBJ>::setCapacity(0); //so the array itself is deallocated too!
431    fCompareProc=fcmp;
432   }
433 <
433 > */
434   template <class OBJ> void GArray<OBJ>::setSorted(CompareProc* cmpFunc) {
435    CompareProc* old_proc=fCompareProc;
436    fCompareProc=cmpFunc;
# Line 347 | Line 438
438         Sort(); //new compare method
439   }
440  
441 < template <class OBJ> void GArray<OBJ>::Grow() {
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;
# Line 355 | Line 446
446    setCapacity(fCapacity + delta);
447   }
448  
449 < template <class OBJ> void GArray<OBJ>::Reverse() {
449 > template <class OBJ> void GVec<OBJ>::Reverse() {
450    int l=0;
451    int r=fCount-1;
452    OBJ c;
# Line 366 | Line 457
457       }
458   }
459  
460 < template <class OBJ> void GArray<OBJ>::Grow(int idx, OBJ& item) {
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;
# Line 375 | Line 466
466    if (NewCapacity <= fCount || NewCapacity >= MAXLISTSIZE)
467      GError(SLISTCAPACITY_ERR, NewCapacity);
468      //error: capacity not within range
469 +
470    if (NewCapacity!=fCapacity) {
471 <    if (NewCapacity==0)
472 <      GFREE(fArray);
471 >    if (NewCapacity==0) {
472 >      //GFREE(fArray);
473 >      delete[] fArray;
474 >      fArray=NULL;
475 >      }
476      else { //add the new item
477        if (idx==fCount) { //append item
478 <         GREALLOC(fArray, NewCapacity*sizeof(OBJ));
478 >         //GREALLOC(fArray, NewCapacity*sizeof(OBJ));
479 >         setCapacity(NewCapacity);
480           fArray[idx]=item;
481           }
482         else { //insert item at idx
483          OBJ* newList;
484 <        GMALLOC(newList, NewCapacity*sizeof(OBJ));
484 >        //GMALLOC(newList, NewCapacity*sizeof(OBJ));
485 >        newList=new OBJ[NewCapacity];
486          //copy data before idx
487 <        memmove(&newList[0],&fArray[0], idx*sizeof(OBJ));
488 <        newList[idx]=item; // operator=
487 >        //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          //copy data after idx
494 <        memmove(&newList[idx+1],&fArray[idx], (fCount-idx)*sizeof(OBJ));
495 <        memset(&newList[fCount+1], 0, (NewCapacity-fCount-1)*sizeof(OBJ));
494 >        //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          //data copied:
500 <        GFREE(fArray);
500 >        //GFREE(fArray);
501 >        delete[] fArray;
502          fArray=newList;
503          }
504        fCount++;
# Line 415 | Line 520
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;
# Line 422 | Line 536
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 <   idxInsert(result, *item);
539 >   this->idxInsert(result, *item);
540     }
541    else {
542     if (fUnique && Found(*item,result)) return -1; //set behaviour
543 <   result = fCount;
544 <   if (result==fCapacity) Grow();
545 <   fArray[result] = *item; //operator=, copies the item
546 <   fCount++;
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 <    setCapacity(fCapacity+list.fCount);
570 <    int s=fCount;
569 >    this->setCapacity(this->fCapacity+list.fCount);
570 >    int s=this->fCount;
571      for (int i=0;i<list.fCount;i++)
572 <           fArray[s+i]=list.fArray[i];
573 <    fCount+=list.fCount;
572 >           this->fArray[s+i]=list.fArray[i];
573 >    this->fCount+=list.fCount;
574      }
575   }
576  
# Line 455 | Line 581
581   //set to the closest matching object!
582   int i;
583   idx=-1;
584 < if (fCount==0) { idx=0;return false;}
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)(fArray[0],item)>0) {
587 >   if ((*fCompareProc)(this->fArray[0],item)>0) {
588                         idx=0;
589                         return false;
590                         }
591 <   if ((*fCompareProc)(item, fArray[fCount-1])>0) {
592 <                       idx=fCount;
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 = fCount - 1;
597 >   int h = this->fCount - 1;
598     int c;
599     while (l <= h) {
600         i = (l + h) >> 1;
601 <       c = (*fCompareProc)(fArray[i], item);
601 >       c = (*fCompareProc)(this->fArray[i], item);
602         if (c < 0)  l = i + 1;
603           else {
604              h = i - 1;
# Line 488 | Line 614
614   else {//not sorted: use linear search
615     // needs == operator to compare user defined objects !
616     i=0;
617 <   while (i<fCount) {
618 <      if (fArray[i]==item) { //requires operator==
617 >   while (i<this->fCount) {
618 >      if (this->fArray[i]==item) { //requires operator==
619           idx=i;
620           return true;
621           }
# Line 499 | Line 625
625     }
626   }
627  
628 < template <class OBJ> void GArray<OBJ>::idxInsert(int idx, OBJ& item) {
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 < if (fCount==fCapacity) { //need to resize
634 <    Grow(idx, item);
509 <    //expand and also copy/move data and insert the new item
633 > if (fCount==fCapacity) { //need to resize the array
634 >    Grow(idx, item); //expand and also copy/move data and insert the new item
635      return;
636      }
637   //move data around to make room for the new item
638 < if (idx<fCount)
639 <      memmove(&fArray[idx+1], &fArray[idx], (fCount-idx)*sizeof(OBJ));
638 > 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   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 < template <class OBJ> void GArray<OBJ>::Move(int curidx, int newidx) {
661 < BE_UNSORTED; //cannot do this in a sorted list!
660 >
661 > template <class OBJ> void GVec<OBJ>::Move(int curidx, int newidx) {
662   if (curidx!=newidx || newidx>=fCount)
663       GError(SLISTINDEX_ERR, newidx);
529
664   OBJ tmp=fArray[curidx]; //copy constructor here
665   fArray[curidx]=fArray[newidx];
666   fArray[newidx]=tmp;
667   }
668  
669 < template <class OBJ> void GArray<OBJ>::Replace(int idx, OBJ& item) {
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;
538 if ( SORTED ) Sort(); //re-sort !
683   }
684  
685 < template <class OBJ> void GArray<OBJ>::Delete(int index) {
685 > 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 > 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);
543 //fArray[index]=NULL;
704   fCount--;
705 < if (index<fCount) //move higher elements if any
706 <   memmove(&fArray[index], &fArray[index+1], (fCount-index)*sizeof(OBJ));
705 > 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   }
712  
713 < template <class OBJ> void GArray<OBJ>::setCount(int NewCount) {
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 <  if (NewCount > fCount)
718 <    memset(&fArray[fCount], 0, (NewCount - fCount) * sizeof(OBJ));
717 >  //if (NewCount > fCount)
718 >  //  memset(&fArray[fCount], 0, (NewCount - fCount) * sizeof(OBJ));
719    fCount = NewCount;
720   }
721  
# Line 560 | Line 724
724   OBJ p,t;
725   do {
726      i = l; j = r;
727 <    p = fArray[(l + r) >> 1];
727 >    p = this->fArray[(l + r) >> 1];
728      do {
729 <      while (fCompareProc(fArray[i], p) < 0) i++;
730 <      while (fCompareProc(fArray[j], p) > 0) j--;
729 >      while (fCompareProc(this->fArray[i], p) < 0) i++;
730 >      while (fCompareProc(this->fArray[j], p) > 0) j--;
731        if (i <= j) {
732 <        t = fArray[i];
733 <        fArray[i] = fArray[j];
734 <        fArray[j] = t;
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);
# Line 577 | Line 741
741   }
742  
743   template <class OBJ> void GArray<OBJ>::Sort() {
744 < if (fArray!=NULL && fCount>0 && fCompareProc!=NULL)
745 <     qSort(0, fCount-1);
744 > if (this->fArray!=NULL && this->fCount>0 && fCompareProc!=NULL)
745 >     qSort(0, this->fCount-1);
746   }
747  
584
585
586
587
748   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
749 < //*=> GList implementation -- sortable array of pointers to OBJ
749 > //*=> GPVec and GList implementation -- sortable array of pointers to OBJ
750  
751 < template <class OBJ> OBJ* GList<OBJ>::operator[](int i) {
592 <          TEST_INDEX(i);
593 <          return fList[i];
594 <          }
595 <
596 < template <class OBJ> GList<OBJ>::GList(GList& list) { //copy constructor
751 > template <class OBJ> GPVec<OBJ>::GPVec(GPVec& list) { //copy constructor
752   fCount=list.fCount;
598 fUnique=list.fUnique;
753   fCapacity=list.fCapacity;
754   if (fCapacity>0) {
755        GMALLOC(fList, fCapacity*sizeof(OBJ*));
756        }
603 fCompareProc=list.fCompareProc;
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> GList<OBJ>::GList(GList* plist) { //another copy constructor
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       }
616 fUnique=plist->fUnique;
617 fCompareProc=plist->fCompareProc;
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 <    setCapacity(fCapacity+list.fCount);
823 <    memcpy( & (fList[fCount]), list.fList, list.fCount*sizeof(OBJ*));
824 <    fCount+=list.fCount;
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) {
639  fCount=0;
640  fCapacity=0;
641  fList=NULL;
831    fCompareProc = compareProc;
832 <  fFreeProc    = freeProc;
832 >  this->fFreeProc    = freeProc;
833    fUnique = beUnique; //only affects sorted lists
834   }
835  
836   template <class OBJ> GList<OBJ>::GList(GCompareProc* compareProc) {
648  fCount=0;
649  fCapacity=0;
650  fList=NULL;
837    fCompareProc = compareProc;
838 <  fFreeProc    = &DefaultFreeProc;
838 >  this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
839    fUnique = false; //only affects sorted lists
840   }
841  
842 < template <class OBJ> void GList<OBJ>::Reverse() {
842 > template <class OBJ> void GPVec<OBJ>::Reverse() {
843    int l=0;
844    int r=fCount-1;
845    OBJ* c;
# Line 664 | Line 850
850       }
851   }
852  
667
853   template <class OBJ> GList<OBJ>::GList(bool sorted,
854      bool free_elements, bool beUnique) {
670  fCount=0;
671  fCapacity=0;
672  fList=NULL;
855    if (sorted) {
856       if (free_elements) {
857          fCompareProc=&DefaultCompareProc;
858 <        fFreeProc=&DefaultFreeProc;
858 >        this->fFreeProc = GPVec<OBJ>::DefaultFreeProc;
859          fUnique=beUnique;
860          }
861         else {
862          fCompareProc=&DefaultCompareProc;
863 <        fFreeProc=NULL;
863 >        this->fFreeProc=NULL;
864          fUnique=beUnique;
865          }
866       }
867     else {
868       if (free_elements) {
869          fCompareProc=NULL;
870 <        fFreeProc=&DefaultFreeProc;
870 >        this->fFreeProc=GPVec<OBJ>::DefaultFreeProc;
871          fUnique=beUnique;
872          }
873        else {
874          fCompareProc=NULL;
875 <        fFreeProc=NULL;
875 >        this->fFreeProc=NULL;
876          fUnique=beUnique;
877          }
878       }
879   }
880  
881 < template <class OBJ> GList<OBJ>::GList(int init_capacity, bool sorted,
700 <    bool free_elements, bool beUnique) {
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 <     if (free_elements) {
894 <        fCompareProc=&DefaultCompareProc;
895 <        fFreeProc=&DefaultFreeProc;
708 <        fUnique=beUnique;
709 <        }
710 <       else {
711 <        fCompareProc=&DefaultCompareProc;
712 <        fFreeProc=NULL;
713 <        fUnique=beUnique;
714 <        }
715 <     }
893 >      fCompareProc=&DefaultCompareProc;
894 >      fUnique=beUnique;
895 >      }
896     else {
897 <     if (free_elements) {
898 <        fCompareProc=NULL;
899 <        fFreeProc=&DefaultFreeProc;
720 <        fUnique=beUnique;
721 <        }
722 <      else {
723 <        fCompareProc=NULL;
724 <        fFreeProc=NULL;
725 <        fUnique=beUnique;
726 <        }
727 <     }
728 < setCapacity(init_capacity);
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 < Clear();//this will free the items if fFreeProc is defined
908 > this->Clear();//this will free the items if fFreeProc is defined
909   }
910 + */
911  
912 < template <class OBJ> void GList<OBJ>::setCapacity(int NewCapacity) {
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)
917 >   if (NewCapacity==0) {
918        GFREE(fList);
919 <    else
919 >      }
920 >    else {
921        GREALLOC(fList, NewCapacity*sizeof(OBJ*));
922 +      }
923     fCapacity=NewCapacity;
924     }
925   }
926  
927 < template <class OBJ> void GList<OBJ>::freeItem(int idx) {
928 <  TEST_INDEX(idx);
929 <  (*fFreeProc)(fList[idx]);
930 <  fList[idx]=NULL;
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 GList<OBJ>::Clear() {
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     }
760 GCompareProc* fcmp=fCompareProc;
761 fCompareProc=NULL;
943   setCount(0);
944   setCapacity(0); //so the array itself is deallocated too!
764 fCompareProc=fcmp;
945   }
946  
947 <
948 < template <class OBJ> void GList<OBJ>::Exchange(int idx1, int idx2) {
769 < BE_UNSORTED; //cannot do that in a sorted list!
947 > template <class OBJ> void GPVec<OBJ>::Exchange(int idx1, int idx2) {
948 > //Warning: this will BREAK sort order for sorted GList
949   TEST_INDEX(idx1);
950   TEST_INDEX(idx2);
951   OBJ* item=fList[idx1];
# Line 774 | Line 953
953   fList[idx2]=item;
954   }
955  
956 <
778 < template <class OBJ> void GList<OBJ>::Expand()
779 < {
956 > template <class OBJ> void GPVec<OBJ>::Expand() {
957   if (fCount==fCapacity) Grow();
958   //return this;
959   }
960  
961 <
785 < template <class OBJ> OBJ* GList<OBJ>::Get(int idx)
786 < {
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 <     Clear();
968 >     GPVec<OBJ>::Clear();
969       fCompareProc=list.fCompareProc;
970 <     fFreeProc=list.fFreeProc;
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]);
# Line 807 | Line 982
982         Sort(); //new compare method
983   }
984  
985 < template <class OBJ> void GList<OBJ>::Grow() {
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;
# Line 815 | Line 990
990    setCapacity(fCapacity + delta);
991   }
992  
993 < template <class OBJ> void GList<OBJ>::Grow(int idx, OBJ* newitem) {
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;
# Line 826 | Line 1001
1001      GError(SLISTCAPACITY_ERR, NewCapacity);
1002      //error: capacity not within range
1003    if (NewCapacity!=fCapacity) {
1004 <    if (NewCapacity==0)
1004 >    if (NewCapacity==0) {
1005        GFREE(fList);
1006 +      }
1007      else  {//add the new item
1008        if (idx==fCount) {
1009           GREALLOC(fList, NewCapacity*sizeof(OBJ*));
# Line 852 | Line 1028
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;
# Line 871 | Line 1054
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;
# Line 882 | Line 1075
1075     }
1076    else {
1077     if (fUnique && Found(item,result)) return -1; //set behaviour
1078 <   result = fCount;
1079 <   if (result==fCapacity) Grow();
1080 <   fList[result]=item;
1081 <   fCount++;
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   }
# Line 897 | Line 1090
1090                                       bool deleteIfFound, int* fidx) {
1091   int r;
1092   if (Found(item, r)) {
1093 <    if (deleteIfFound && (pointer)item != (pointer)fList[r]) delete item;
1093 >    if (deleteIfFound && (pointer)item != (pointer)(this->fList[r])) {
1094 >       this->deallocate_item(item);
1095 >       }
1096      if (fidx!=NULL) *fidx=r;
1097 <    return fList[r]; //found
1097 >    return this->fList[r]; //found
1098      }
1099   //not found:
1100   if (SORTED) {
# Line 907 | Line 1102
1102     sortInsert(r, item);
1103     }
1104    else {
1105 <   r = fCount;
1106 <   if (r==fCapacity) Grow();
1107 <   fList[r]=item;
1108 <   fCount++;
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
# Line 923 | Line 1143
1143   //set to the closest matching object!
1144   int i;
1145   idx=-1;
1146 < if (fCount==0) { idx=0;return false;}
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)(fList[0],item)>0) {
1150 >   if ((*fCompareProc)(this->fList[0],item)>0) {
1151                         idx=0;
1152                         return false;
1153                         }
1154 <   if ((*fCompareProc)(item, fList[fCount-1])>0) {
1155 <                       idx=fCount;
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 = fCount - 1;
1161 >   h = this->fCount - 1;
1162     while (l <= h) {
1163         i = (l + h) >> 1;
1164 <       c = (*fCompareProc)(fList[i], item);
1164 >       c = (*fCompareProc)(this->fList[i], item);
1165         if (c < 0)  l = i + 1;
1166           else {
1167              h = i - 1;
# Line 957 | Line 1177
1177   else {//not sorted: use linear search
1178     // needs == operator to compare user defined objects !
1179     i=0;
1180 <   while (i<fCount) {
1181 <      if (*fList[i]==*item) {
1180 >   while (i<this->fCount) {
1181 >      if (*this->fList[i]==*item) {
1182           idx=i;
1183           return true;
1184           }
# Line 972 | Line 1192
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>fCount) GError(SLISTINDEX_ERR, idx);
1196 < if (fCount==fCapacity) {
1197 <    Grow(idx, item);
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<fCount) //copy/move pointers only!
1203 <      memmove(&fList[idx+1], &fList[idx], (fCount-idx)*sizeof(OBJ*));
1204 < fList[idx]=item;
1205 < fCount++;
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 GList<OBJ>::Insert(int idx, OBJ* item) {
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
990 BE_UNSORTED; //cannot do that with a sorted list!
1210   if (idx<0 || idx>fCount) GError(SLISTINDEX_ERR, idx);
1211   if (fCount==fCapacity) {
1212     Grow(idx, item);
# Line 999 | Line 1218
1218   fCount++;
1219   }
1220  
1221 < template <class OBJ> void GList<OBJ>::Move(int curidx, int newidx) {
1222 < BE_UNSORTED; //cannot do that in a sorted list!
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;
# Line 1013 | Line 1238
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 GList<OBJ>::Put(int idx, OBJ* item, bool re_sort) {
1247 < //WARNING: this will never free the replaced item!!!
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 + // this may BREAK the sort order unless the "re_sort" parameter is given
1255 + 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 < template <class OBJ> void GList<OBJ>::Forget(int idx) {
1260 >
1261 > template <class OBJ> void GPVec<OBJ>::Forget(int idx) {
1262   TEST_INDEX(idx);
1263 < fList[idx]=NULL;
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 GList<OBJ>::Delete(int index) {
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
# Line 1038 | Line 1284
1284   }
1285  
1286   //Stack usage:
1287 < template <class OBJ> OBJ* GList<OBJ>::Pop() {
1287 > template <class OBJ> OBJ* GPVec<OBJ>::Pop() {
1288   if (fCount<=0) return NULL;
1289   fCount--;
1290   OBJ* o=fList[fCount];
# Line 1047 | Line 1293
1293   }
1294  
1295   //Queue usage:
1296 < template <class OBJ> OBJ* GList<OBJ>::Shift() {
1296 > template <class OBJ> OBJ* GPVec<OBJ>::Shift() {
1297   if (fCount<=0) return NULL;
1298   fCount--;
1299   OBJ* o=fList[0];
# Line 1060 | Line 1306
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) Delete(result);
1309 > if (result>=0) GPVec<OBJ>::Delete(result);
1310   return result;
1311   }
1312  
1313 < //linear search for the pointer
1314 < template <class OBJ> int GList<OBJ>::RemovePtr(OBJ* item) {
1069 < int i;
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 (i=0;i<fCount;i++)
1317 <   if (fList[i]==item) break;
1318 < if (i==fCount) return -1; //not found
1319 < Delete(i);
1320 < return i;
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 <
1079 < template <class OBJ> void GList<OBJ>::Pack()  {//also frees items!
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); //also shift contents of fList accordingly
1326 >    if (fList[i]==NULL) Delete(i); //shift rest of fList content accordingly
1327   }
1328  
1329 < template <class OBJ> void GList<OBJ>::setCount(int NewCount) {
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);
# Line 1097 | Line 1342
1342   do {
1343      I = L;
1344      J = R;
1345 <    P = fList[(L + R) >> 1];
1345 >    P = this->fList[(L + R) >> 1];
1346      do {
1347 <      while (fCompareProc(fList[I], P) < 0) I++;
1348 <      while (fCompareProc(fList[J], P) > 0) J--;
1347 >      while (fCompareProc(this->fList[I], P) < 0) I++;
1348 >      while (fCompareProc(this->fList[J], P) > 0) J--;
1349        if (I <= J) {
1350 <        T = fList[I];
1351 <        fList[I] = fList[J];
1352 <        fList[J] = T;
1350 >        T = this->fList[I];
1351 >        this->fList[I] = this->fList[J];
1352 >        this->fList[J] = T;
1353          I++;
1354          J--;
1355          }
# Line 1118 | Line 1363
1363   }
1364  
1365   template <class OBJ> void GList<OBJ>::Sort() {
1366 < if (fList!=NULL && fCount>0 && fCompareProc!=NULL)
1367 <     QuickSort(0, fCount-1);
1366 > if (this->fList!=NULL && this->fCount>0 && fCompareProc!=NULL)
1367 >     QuickSort(0, this->fCount-1);
1368   }
1369  
1370   //---------------------------------------------------------------------------

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines