Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
sort.hpp
Go to the documentation of this file.
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
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
47 int const QuickSortCutoff = 20;
48
50 template<class Type>
52 private:
54 static const int maxsize = sizeof(int) * CHAR_BIT;
56 Type** tos;
58 Type* stack[2*maxsize+1];
59 public:
61 QuickSortStack(void);
63 bool empty(void) const;
65 void push(Type* l, Type* r);
67 void pop(Type*& l, Type*& r);
68 };
69
70 template<class Type>
72 QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) {
73 *(tos++) = NULL;
74 }
75
76 template<class Type>
77 forceinline bool
79 return *(tos-1) == NULL;
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
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
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
128 template<class Type, class Less>
129 inline void
130 quicksort(Type* l, Type* r, Less &less) {
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
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
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
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
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
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
Comparison class for sorting using <.
Definition sort.hpp:161
bool operator()(const Type &lhs, const Type &rhs)
Definition sort.hpp:163
Static stack for quicksort.
Definition sort.hpp:51
QuickSortStack(void)
Initialize stack as empty.
Definition sort.hpp:72
void pop(Type *&l, Type *&r)
Pop two positions l and r.
Definition sort.hpp:90
bool empty(void) const
Test whether stack is empty.
Definition sort.hpp:78
void push(Type *l, Type *r)
Push two positions l and r.
Definition sort.hpp:84
Support algorithms and datastructures
void exchange(Type &a, Type &b, Less &less)
Exchange elements according to order.
Definition sort.hpp:42
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
int const QuickSortCutoff
Perform quicksort only for more elements.
Definition sort.hpp:47
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
Definition sort.hpp:113
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition sort.hpp:97
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
Post propagator for SetVar x
Definition set.hh:773
#define forceinline
Definition config.hpp:194