ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GVec.hh
(Generate patch)
# Line 33 | Line 33
33      OBJ* fArray;
34      int fCount;
35      int fCapacity;
36 +    void qSort(int L, int R, GCompareProc* cmpFunc);
37    public:
38      GVec(int init_capacity=2);
39      GVec(GVec<OBJ>& array); //copy constructor
# Line 52 | Line 53
53      OBJ Shift(); //Queue use: removes and returns a copy of the first item
54  
55      void Add(GVec<OBJ>& list); //append copies of all items from another list
56 +
57      OBJ& Get(int idx) {
58            TEST_INDEX(idx);
59            return fArray[idx];
# Line 87 | Line 89
89      void Move(int curidx, int newidx);
90      bool isEmpty() { return fCount==0; }
91      bool notEmpty() { return fCount>0; }
92 +
93 +    void Sort(GCompareProc* cmpFunc);
94   };
95  
96   //---- template for dynamic array of object pointers
# Line 102 | Line 106
106      void Grow();
107      void Grow(int idx, OBJ* newitem);
108      void setCount(int NewCount); //will trim/expand the array as needed
109 +    void qSort(int L, int R, GCompareProc* cmpFunc);
110    public:  
111      static void DefaultFreeProc(pointer item) {
112        delete (OBJ*)item;
# Line 145 | Line 150
150      void Delete(int index); //also frees the item if fFreeProc!=NULL, and shifts the successor items
151      void Forget(int idx); //simply places a NULL at fList[idx], nothing else
152      int RemovePtr(pointer item); //always use linear search to find the pointer! calls Delete() if found
153 <    int IndexOf(pointer item); //a linear search for pointer address only!
153 >    int IndexOf(pointer item); //a linear search for pointer address!
154 >    void Sort(GCompareProc* cmpFunc);
155   };
156  
151
152
153
157   //-------------------- TEMPLATE IMPLEMENTATION-------------------------------
158  
159   template <class OBJ> GVec<OBJ>::GVec(int init_capacity) {
# Line 422 | Line 425
425    fCount = NewCount;
426   }
427  
428 +
429 + template <class OBJ> void GVec<OBJ>::qSort(int l, int r, GCompareProc* cmpFunc) {
430 + int i, j;
431 + OBJ p,t;
432 + do {
433 +    i = l; j = r;
434 +    p = this->fArray[(l + r) >> 1];
435 +    do {
436 +      while (cmpFunc(&(this->fArray[i]), &p) < 0) i++;
437 +      while (cmpFunc(&(this->fArray[j]), &p) > 0) j--;
438 +      if (i <= j) {
439 +        t = this->fArray[i];
440 +        this->fArray[i] = this->fArray[j];
441 +        this->fArray[j] = t;
442 +        i++; j--;
443 +        }
444 +      } while (i <= j);
445 +    if (l < j) qSort(l, j, cmpFunc);
446 +    l = i;
447 +    } while (i < r);
448 + }
449 +
450 + template <class OBJ> void GVec<OBJ>::Sort(GCompareProc* cmpFunc) {
451 + if (this->fArray!=NULL && this->fCount>0 && cmpFunc!=NULL)
452 +     qSort(0, this->fCount-1, cmpFunc);
453 + }
454 +
455 +
456   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
457   //*=> GPVec implementation
458  
# Line 719 | Line 750
750    fCount = NewCount;
751   }
752  
753 + template <class OBJ> void GPVec<OBJ>::qSort(int L, int R, GCompareProc* cmpFunc) {
754 + int I, J;
755 + OBJ* P;
756 + OBJ* T;
757 + do {
758 +    I = L;
759 +    J = R;
760 +    P = this->fList[(L + R) >> 1];
761 +    do {
762 +      while (cmpFunc(this->fList[I], P) < 0) I++;
763 +      while (cmpFunc(this->fList[J], P) > 0) J--;
764 +      if (I <= J) {
765 +        T = this->fList[I];
766 +        this->fList[I] = this->fList[J];
767 +        this->fList[J] = T;
768 +        I++;
769 +        J--;
770 +        }
771 +      }
772 +    while (I <= J);
773 +    if (L < J) qSort(L, J, cmpFunc);
774 +    L = I;
775 +    }
776 + while (I < R);
777 + }
778 +
779 + template <class OBJ> void GPVec<OBJ>::Sort(GCompareProc* cmpFunc) {
780 + if (this->fList!=NULL && this->fCount>0 && cmpFunc!=NULL)
781 +     qSort(0, this->fCount-1, cmpFunc);
782 + }
783 +
784   //---------------------------------------------------------------------------
785   #endif

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines