00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef _QSORT_H
00019 #define _QSORT_H
00020
00021
00022 namespace LA {
00023
00024 template<typename INDEX, typename COMPAR>
00025 int genqsort(INDEX l, INDEX r,COMPAR (*cmp)(const INDEX, const INDEX), void (*swap)(const INDEX,const INDEX))
00026 {
00027 INDEX i,j,piv;
00028 int parity=0;
00029
00030 if(r<=l) return parity;
00031 if(cmp(r,l)<0) {parity^=1; swap(l,r);}
00032 if(r-l==1) return parity;
00033 piv= l+(r-l)/2;
00034 if(cmp(piv,l)<0) {parity^=1; swap(l,piv);}
00035 if(cmp(r,piv)<0) {parity^=1; swap(r,piv);}
00036 if(r-l==2) return parity;
00037
00038
00039 i=l+1; j=r-1;
00040 do{
00041
00042
00043 while(cmp(i++,piv)<0);
00044 i--;
00045 while(cmp(j--,piv)>0);
00046 j++;
00047 if(i<j)
00048 {
00049
00050 parity^=1; swap(i,j);
00051 if(i==piv) piv=j; else if(j==piv) piv=i;
00052 }
00053 if(i<=j) {i++; j--;}
00054 }while(i<=j);
00055
00056 if(j-l < r-i)
00057 {if(l<j) parity ^=genqsort(l,j,cmp,swap); if(i<r) parity ^=genqsort(i,r,cmp,swap);}
00058 else
00059 {if(i<r) parity ^=genqsort(i,r,cmp,swap); if(l<j) parity ^=genqsort(l,j,cmp,swap);}
00060 return parity;
00061 }
00062
00063
00064
00065
00066
00067 template<int type, typename SORTABLE, typename INDEX, typename PERMINDEX>
00068 int memqsort(SORTABLE &object, PERMINDEX *perm, INDEX l, INDEX r)
00069 {
00070 INDEX i,j,piv;
00071 int parity=0;
00072
00073 if(r<=l) return parity;
00074 if(LA_sort_traits<SORTABLE,INDEX,type>::compare(object,l,r)) {parity^=1; object.swap(l,r); if(perm) {PERMINDEX tmp=perm[l]; perm[l]=perm[r]; perm[r]=tmp;}}
00075 if(r-l==1) return parity;
00076 piv= l+(r-l)/2;
00077 if(LA_sort_traits<SORTABLE,INDEX,type>::compare(object,l,piv)) {parity^=1; object.swap(l,piv); if(perm) {PERMINDEX tmp=perm[l]; perm[l]=perm[piv]; perm[piv]=tmp;}}
00078 if(LA_sort_traits<SORTABLE,INDEX,type>::compare(object,piv,r)) {parity^=1; object.swap(r,piv); if(perm) {PERMINDEX tmp=perm[r]; perm[r]=perm[piv]; perm[piv]=tmp;}}
00079 if(r-l==2) return parity;
00080
00081
00082 i=l+1; j=r-1;
00083 do{
00084
00085
00086 while(LA_sort_traits<SORTABLE,INDEX,type>::compare(object,piv,i++));
00087 i--;
00088 while(LA_sort_traits<SORTABLE,INDEX,type>::compare(object,j--,piv));
00089 j++;
00090 if(i<j)
00091 {
00092
00093 parity^=1; object.swap(i,j); if(perm) {PERMINDEX tmp=perm[i]; perm[i]=perm[j]; perm[j]=tmp;}
00094 if(i==piv) piv=j; else if(j==piv) piv=i;
00095 }
00096 if(i<=j) {i++; j--;}
00097 }while(i<=j);
00098
00099 if(j-l < r-i)
00100 {if(l<j) parity ^=memqsort<type,SORTABLE,INDEX,PERMINDEX>(object,perm,l,j); if(i<r) parity ^=memqsort<type,SORTABLE,INDEX,PERMINDEX>(object,perm,i,r);}
00101 else
00102 {if(i<r) parity ^=memqsort<type,SORTABLE,INDEX,PERMINDEX>(object,perm,i,r); if(l<j) parity ^=memqsort<type,SORTABLE,INDEX,PERMINDEX>(object,perm,l,j);}
00103 return parity;
00104 }
00105
00106
00107 template<typename S, typename PERMINDEX>
00108 int ptrqsortup(S *l, S *r, PERMINDEX *perm=NULL)
00109 {
00110 S *i,*j,*piv;
00111 int parity=0;
00112
00113 if(r-l<=0) return parity;
00114 if(*l > *r) {parity^=1; {S tmp; tmp=*l; *l= *r; *r=tmp;} if(perm) {PERMINDEX tmp=*perm; *perm=perm[r-l]; perm[r-l]=tmp;}}
00115 if(r-l==1) return parity;
00116 piv= l+(r-l)/2;
00117 if(*l>*piv) {parity^=1; {S tmp; tmp=*l; *l=*piv; *piv=tmp;} if(perm) {PERMINDEX tmp= *perm; *perm=perm[piv-l]; perm[piv-l]=tmp;}}
00118 if(*piv>*r) {parity^=1; {S tmp; tmp=*r; *r=*piv; *piv=tmp;} if(perm) {PERMINDEX tmp=perm[r-l]; perm[r-l]=perm[piv-l]; perm[piv-l]=tmp;}}
00119 if(r-l==2) return parity;
00120
00121
00122 i=l+1; j=r-1;
00123 do{
00124
00125
00126 while(*piv > *i++);
00127 i--;
00128 while(*j-- > *piv);
00129 j++;
00130 if(i<j)
00131 {
00132
00133 parity^=1; {S tmp; tmp=*i; *i=*j; *j=tmp;} if(perm) {PERMINDEX tmp=perm[i-l]; perm[i-l]=perm[j-l]; perm[j-l]=tmp;}
00134 if(i==piv) piv=j; else if(j==piv) piv=i;
00135 }
00136 if(i<=j) {i++; j--;}
00137 }while(i<=j);
00138
00139 if(j-l < r-i)
00140 {if(l<j) parity ^=ptrqsortup(l,j,perm); if(i<r) parity ^=ptrqsortup(i,r,perm+(i-l));}
00141 else
00142 {if(i<r) parity ^=ptrqsortup(i,r,perm+(i-l)); if(l<j) parity ^=ptrqsortup(l,j,perm);}
00143 return parity;
00144 }
00145
00146
00147 template<typename S, typename PERMINDEX>
00148 int ptrqsortdown(S *l, S *r, PERMINDEX *perm=NULL)
00149 {
00150 S *i,*j,*piv;
00151 int parity=0;
00152
00153 if(r-l<=0) return parity;
00154 if(*l < *r) {parity^=1; {S tmp; tmp=*l; *l= *r; *r=tmp;} if(perm) {PERMINDEX tmp=*perm; *perm=perm[r-l]; perm[r-l]=tmp;}}
00155 if(r-l==1) return parity;
00156 piv= l+(r-l)/2;
00157 if(*l<*piv) {parity^=1; {S tmp; tmp=*l; *l=*piv; *piv=tmp;} if(perm) {PERMINDEX tmp= *perm; *perm=perm[piv-l]; perm[piv-l]=tmp;}}
00158 if(*piv<*r) {parity^=1; {S tmp; tmp=*r; *r=*piv; *piv=tmp;} if(perm) {PERMINDEX tmp=perm[r-l]; perm[r-l]=perm[piv-l]; perm[piv-l]=tmp;}}
00159 if(r-l==2) return parity;
00160
00161
00162 i=l+1; j=r-1;
00163 do{
00164
00165
00166 while(*piv < *i++);
00167 i--;
00168 while(*j-- < *piv);
00169 j++;
00170 if(i<j)
00171 {
00172
00173 parity^=1; {S tmp; tmp=*i; *i=*j; *j=tmp;} if(perm) {PERMINDEX tmp=perm[i-l]; perm[i-l]=perm[j-l]; perm[j-l]=tmp;}
00174 if(i==piv) piv=j; else if(j==piv) piv=i;
00175 }
00176 if(i<=j) {i++; j--;}
00177 }while(i<=j);
00178
00179 if(j-l < r-i)
00180 {if(l<j) parity ^=ptrqsortdown(l,j,perm); if(i<r) parity ^=ptrqsortdown(i,r,perm+(i-l));}
00181 else
00182 {if(i<r) parity ^=ptrqsortdown(i,r,perm+(i-l)); if(l<j) parity ^=ptrqsortdown(l,j,perm);}
00183 return parity;
00184 }
00185
00186 }
00187 #endif