this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2002
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <algorithm>
35#include <climits>
36
37namespace Gecode { namespace Support {
38
39 /// Exchange elements according to order
40 template<class Type, class Less>
41 forceinline void
42 exchange(Type &a, Type &b, Less &less) {
43 if (less(b,a)) std::swap(a,b);
44 }
45
46 /// Perform quicksort only for more elements
47 int const QuickSortCutoff = 20;
48
49 /// Static stack for quicksort
50 template<class Type>
51 class QuickSortStack {
52 private:
53 /// Maximal stacksize quicksort ever needs
54 static const int maxsize = sizeof(int) * CHAR_BIT;
55 /// Top of stack
56 Type** tos;
57 /// Stack entries (terminated by nullptr entry)
58 Type* stack[2*maxsize+1];
59 public:
60 /// Initialize stack as empty
61 QuickSortStack(void);
62 /// Test whether stack is empty
63 bool empty(void) const;
64 /// Push two positions \a l and \a r
65 void push(Type* l, Type* r);
66 /// Pop two positions \a l and \a r
67 void pop(Type*& l, Type*& r);
68 };
69
70 template<class Type>
71 forceinline
72 QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) {
73 *(tos++) = nullptr;
74 }
75
76 template<class Type>
77 forceinline bool
78 QuickSortStack<Type>::empty(void) const {
79 return *(tos-1) == nullptr;
80 }
81
82 template<class Type>
83 forceinline void
84 QuickSortStack<Type>::push(Type* l, Type* r) {
85 *(tos++) = l; *(tos++) = r;
86 }
87
88 template<class Type>
89 forceinline void
90 QuickSortStack<Type>::pop(Type*& l, Type*& r) {
91 r = *(--tos); l = *(--tos);
92 }
93
94 /// Standard insertion sort
95 template<class Type, class Less>
96 forceinline void
97 insertion(Type* l, Type* r, Less &less) {
98 for (Type* i = r; i > l; i--)
99 exchange(*(i-1),*i,less);
100 for (Type* i = l+2; i <= r; i++) {
101 Type* j = i;
102 Type v = *i;
103 while (less(v,*(j-1))) {
104 *j = *(j-1); j--;
105 }
106 *j = v;
107 }
108 }
109
110 /// Standard partioning
111 template<class Type, class Less>
112 forceinline Type*
113 partition(Type* l, Type* r, Less &less) {
114 Type* i = l-1;
115 Type* j = r;
116 Type v = *r;
117 while (true) {
118 while (less(*(++i),v)) {}
119 while (less(v,*(--j))) if (j == l) break;
120 if (i >= j) break;
121 std::swap(*i,*j);
122 }
123 std::swap(*i,*r);
124 return i;
125 }
126
127 /// Standard quick sort
128 template<class Type, class Less>
129 inline void
130 quicksort(Type* l, Type* r, Less &less) {
131 QuickSortStack<Type> s;
132 while (true) {
133 std::swap(*(l+((r-l) >> 1)),*(r-1));
134 exchange(*l,*(r-1),less);
135 exchange(*l,*r,less);
136 exchange(*(r-1),*r,less);
137 Type* i = partition(l+1,r-1,less);
138 if (i-l > r-i) {
139 if (r-i > QuickSortCutoff) {
140 s.push(l,i-1); l=i+1; continue;
141 }
142 if (i-l > QuickSortCutoff) {
143 r=i-1; continue;
144 }
145 } else {
146 if (i-l > QuickSortCutoff) {
147 s.push(i+1,r); r=i-1; continue;
148 }
149 if (r-i > QuickSortCutoff) {
150 l=i+1; continue;
151 }
152 }
153 if (s.empty())
154 break;
155 s.pop(l,r);
156 }
157 }
158
159 /// Comparison class for sorting using \a <
160 template<class Type>
161 class Less {
162 public:
163 bool operator ()(const Type& lhs, const Type& rhs) {
164 return lhs < rhs;
165 }
166 };
167
168 /**
169 * \brief Insertion sort
170 *
171 * Sorts by insertion the \a n first elements of array \a x according
172 * to the order \a l as instance of class \a Less. The class
173 * \a Less must implement the single member function
174 * \code bool operator ()(const Type&, const Type&) \endcode
175 * for comparing elements. Note that the order must be strict, that
176 * is: comparing an element with itself must return false.
177 *
178 * The algorithm is largely based on the following book:
179 * Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
180 *
181 * \ingroup FuncSupport
182 */
183 template<class Type, class Less>
184 forceinline void
185 insertion(Type* x, int n, Less &l) {
186 if (n < 2)
187 return;
188 assert(!l(x[0],x[0]));
189 insertion(x,x+n-1,l);
190 }
191
192 /**
193 * \brief Insertion sort
194 *
195 * Sorts by insertion the \a n first elements of array \a x according
196 * to the order \a <.
197 *
198 * The algorithm is largely based on the following book:
199 * Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
200 *
201 * \ingroup FuncSupport
202 */
203 template<class Type>
204 forceinline void
205 insertion(Type* x, int n) {
206 if (n < 2)
207 return;
208 Less<Type> l;
209 assert(!l(x[0],x[0]));
210 insertion(x,x+n-1,l);
211 }
212
213 /**
214 * \brief Quicksort
215 *
216 * Sorts with quicksort the \a n first elements of array \a x according
217 * to the order \a l as instance of class \a Less. The class
218 * \a Less must implement the single member function
219 * \code bool operator ()(const Type&, const Type&) \endcode
220 * for comparing elements. Note that the order must be strict, that
221 * is: comparing an element with itself must return false.
222 *
223 * The algorithm is largely based on the following book:
224 * Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
225 *
226 * \ingroup FuncSupport
227 */
228 template<class Type, class Less>
229 forceinline void
230 quicksort(Type* x, int n, Less &l) {
231 if (n < 2)
232 return;
233 assert(!l(x[0],x[0]));
234 if (n > QuickSortCutoff)
235 quicksort(x,x+n-1,l);
236 insertion(x,x+n-1,l);
237 }
238
239 /**
240 * \brief Quicksort
241 *
242 * Sorts with quicksort the \a n first elements of array \a x according
243 * to the order \a <.
244 *
245 * The algorithm is largely based on the following book:
246 * Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
247 *
248 * \ingroup FuncSupport
249 */
250 template<class Type>
251 forceinline void
252 quicksort(Type* x, int n) {
253 if (n < 2)
254 return;
255 Less<Type> l;
256 assert(!l(x[0],x[0]));
257 if (n > QuickSortCutoff)
258 quicksort(x,x+n-1,l);
259 insertion(x,x+n-1,l);
260 }
261
262}}
263
264// STATISTICS: support-any