sort.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00011 * $Revision: 9692 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <algorithm> 00039 #include <climits> 00040 00041 namespace Gecode { namespace Support { 00042 00044 template<class Type, class Less> 00045 forceinline void 00046 exchange(Type &a, Type &b, Less &less) { 00047 if (less(b,a)) std::swap(a,b); 00048 } 00049 00051 int const QuickSortCutoff = 20; 00052 00054 template<class Type> 00055 class QuickSortStack { 00056 private: 00058 static const int maxsize = sizeof(int) * CHAR_BIT; 00060 Type** tos; 00062 Type* stack[2*maxsize+1]; 00063 public: 00065 QuickSortStack(void); 00067 bool empty(void) const; 00069 void push(Type* l, Type* r); 00071 void pop(Type*& l, Type*& r); 00072 }; 00073 00074 template<class Type> 00075 forceinline 00076 QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) { 00077 *(tos++) = NULL; 00078 } 00079 00080 template<class Type> 00081 forceinline bool 00082 QuickSortStack<Type>::empty(void) const { 00083 return *(tos-1) == NULL; 00084 } 00085 00086 template<class Type> 00087 forceinline void 00088 QuickSortStack<Type>::push(Type* l, Type* r) { 00089 *(tos++) = l; *(tos++) = r; 00090 } 00091 00092 template<class Type> 00093 forceinline void 00094 QuickSortStack<Type>::pop(Type*& l, Type*& r) { 00095 r = *(--tos); l = *(--tos); 00096 } 00097 00099 template<class Type, class Less> 00100 forceinline void 00101 insertion(Type* l, Type* r, Less &less) { 00102 for (Type* i = r; i > l; i--) 00103 exchange(*(i-1),*i,less); 00104 for (Type* i = l+2; i <= r; i++) { 00105 Type* j = i; 00106 Type v = *i; 00107 while (less(v,*(j-1))) { 00108 *j = *(j-1); j--; 00109 } 00110 *j = v; 00111 } 00112 } 00113 00115 template<class Type, class Less> 00116 forceinline Type* 00117 partition(Type* l, Type* r, Less &less) { 00118 Type* i = l-1; 00119 Type* j = r; 00120 Type v = *r; 00121 while (true) { 00122 while (less(*(++i),v)) {} 00123 while (less(v,*(--j))) if (j == l) break; 00124 if (i >= j) break; 00125 std::swap(*i,*j); 00126 } 00127 std::swap(*i,*r); 00128 return i; 00129 } 00130 00132 template<class Type, class Less> 00133 inline void 00134 quicksort(Type* l, Type* r, Less &less) { 00135 QuickSortStack<Type> s; 00136 while (true) { 00137 std::swap(*(l+((r-l) >> 1)),*(r-1)); 00138 exchange(*l,*(r-1),less); 00139 exchange(*l,*r,less); 00140 exchange(*(r-1),*r,less); 00141 Type* i = partition(l+1,r-1,less); 00142 if (i-l > r-i) { 00143 if (r-i > QuickSortCutoff) { 00144 s.push(l,i-1); l=i+1; continue; 00145 } 00146 if (i-l > QuickSortCutoff) { 00147 r=i-1; continue; 00148 } 00149 } else { 00150 if (i-l > QuickSortCutoff) { 00151 s.push(i+1,r); r=i-1; continue; 00152 } 00153 if (r-i > QuickSortCutoff) { 00154 l=i+1; continue; 00155 } 00156 } 00157 if (s.empty()) 00158 break; 00159 s.pop(l,r); 00160 } 00161 } 00162 00164 template<class Type> 00165 class Less { 00166 public: 00167 bool operator ()(const Type& lhs, const Type& rhs) { 00168 return lhs < rhs; 00169 } 00170 }; 00171 00187 template<class Type, class Less> 00188 forceinline void 00189 insertion(Type* x, int n, Less &l) { 00190 if (n < 2) 00191 return; 00192 assert(!l(x[0],x[0])); 00193 insertion(x,x+n-1,l); 00194 } 00195 00207 template<class Type> 00208 forceinline void 00209 insertion(Type* x, int n) { 00210 if (n < 2) 00211 return; 00212 Less<Type> l; 00213 assert(!l(x[0],x[0])); 00214 insertion(x,x+n-1,l); 00215 } 00216 00232 template<class Type, class Less> 00233 forceinline void 00234 quicksort(Type* x, int n, Less &l) { 00235 if (n < 2) 00236 return; 00237 assert(!l(x[0],x[0])); 00238 if (n > QuickSortCutoff) 00239 quicksort(x,x+n-1,l); 00240 insertion(x,x+n-1,l); 00241 } 00242 00254 template<class Type> 00255 forceinline void 00256 quicksort(Type* x, int n) { 00257 if (n < 2) 00258 return; 00259 Less<Type> l; 00260 assert(!l(x[0],x[0])); 00261 if (n > QuickSortCutoff) 00262 quicksort(x,x+n-1,l); 00263 insertion(x,x+n-1,l); 00264 } 00265 00266 }} 00267 00268 // STATISTICS: support-any