00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <algorithm>
00035 #include <climits>
00036
00037 namespace Gecode { namespace Support {
00038
00040 template<class Type, class Less>
00041 forceinline void
00042 exchange(Type &a, Type &b, Less &less) {
00043 if (less(b,a)) std::swap(a,b);
00044 }
00045
00047 int const QuickSortCutoff = 20;
00048
00050 template<class Type>
00051 class QuickSortStack {
00052 private:
00054 static const int maxsize = sizeof(int) * CHAR_BIT;
00056 Type** tos;
00058 Type* stack[2*maxsize+1];
00059 public:
00061 QuickSortStack(void);
00063 bool empty(void) const;
00065 void push(Type* l, Type* r);
00067 void pop(Type*& l, Type*& r);
00068 };
00069
00070 template<class Type>
00071 forceinline
00072 QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) {
00073 *(tos++) = NULL;
00074 }
00075
00076 template<class Type>
00077 forceinline bool
00078 QuickSortStack<Type>::empty(void) const {
00079 return *(tos-1) == NULL;
00080 }
00081
00082 template<class Type>
00083 forceinline void
00084 QuickSortStack<Type>::push(Type* l, Type* r) {
00085 *(tos++) = l; *(tos++) = r;
00086 }
00087
00088 template<class Type>
00089 forceinline void
00090 QuickSortStack<Type>::pop(Type*& l, Type*& r) {
00091 r = *(--tos); l = *(--tos);
00092 }
00093
00095 template<class Type, class Less>
00096 forceinline void
00097 insertion(Type* l, Type* r, Less &less) {
00098 for (Type* i = r; i > l; i--)
00099 exchange(*(i-1),*i,less);
00100 for (Type* i = l+2; i <= r; i++) {
00101 Type* j = i;
00102 Type v = *i;
00103 while (less(v,*(j-1))) {
00104 *j = *(j-1); j--;
00105 }
00106 *j = v;
00107 }
00108 }
00109
00111 template<class Type, class Less>
00112 forceinline Type*
00113 partition(Type* l, Type* r, Less &less) {
00114 Type* i = l-1;
00115 Type* j = r;
00116 Type v = *r;
00117 while (true) {
00118 while (less(*(++i),v)) {}
00119 while (less(v,*(--j))) if (j == l) break;
00120 if (i >= j) break;
00121 std::swap(*i,*j);
00122 }
00123 std::swap(*i,*r);
00124 return i;
00125 }
00126
00128 template<class Type, class Less>
00129 inline void
00130 quicksort(Type* l, Type* r, Less &less) {
00131 QuickSortStack<Type> s;
00132 while (true) {
00133 std::swap(*(l+((r-l) >> 1)),*(r-1));
00134 exchange(*l,*(r-1),less);
00135 exchange(*l,*r,less);
00136 exchange(*(r-1),*r,less);
00137 Type* i = partition(l+1,r-1,less);
00138 if (i-l > r-i) {
00139 if (r-i > QuickSortCutoff) {
00140 s.push(l,i-1); l=i+1; continue;
00141 }
00142 if (i-l > QuickSortCutoff) {
00143 r=i-1; continue;
00144 }
00145 } else {
00146 if (i-l > QuickSortCutoff) {
00147 s.push(i+1,r); r=i-1; continue;
00148 }
00149 if (r-i > QuickSortCutoff) {
00150 l=i+1; continue;
00151 }
00152 }
00153 if (s.empty())
00154 break;
00155 s.pop(l,r);
00156 }
00157 }
00158
00160 template<class Type>
00161 class Less {
00162 public:
00163 bool operator ()(const Type& lhs, const Type& rhs) {
00164 return lhs < rhs;
00165 }
00166 };
00167
00183 template<class Type, class Less>
00184 forceinline void
00185 insertion(Type* x, int n, Less &l) {
00186 if (n < 2)
00187 return;
00188 assert(!l(x[0],x[0]));
00189 insertion(x,x+n-1,l);
00190 }
00191
00203 template<class Type>
00204 forceinline void
00205 insertion(Type* x, int n) {
00206 if (n < 2)
00207 return;
00208 Less<Type> l;
00209 assert(!l(x[0],x[0]));
00210 insertion(x,x+n-1,l);
00211 }
00212
00228 template<class Type, class Less>
00229 forceinline void
00230 quicksort(Type* x, int n, Less &l) {
00231 if (n < 2)
00232 return;
00233 assert(!l(x[0],x[0]));
00234 if (n > QuickSortCutoff)
00235 quicksort(x,x+n-1,l);
00236 insertion(x,x+n-1,l);
00237 }
00238
00250 template<class Type>
00251 forceinline void
00252 quicksort(Type* x, int n) {
00253 if (n < 2)
00254 return;
00255 Less<Type> l;
00256 assert(!l(x[0],x[0]));
00257 if (n > QuickSortCutoff)
00258 quicksort(x,x+n-1,l);
00259 insertion(x,x+n-1,l);
00260 }
00261
00262 }}
00263
00264