main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 24 2020 14:04:04 for Gecode by
doxygen
1.8.17
gecode
support
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
37
namespace
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>
51
class
QuickSortStack
{
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>
71
forceinline
72
QuickSortStack<Type>::QuickSortStack
(
void
) : tos(&stack[0]) {
73
*(tos++) = NULL;
74
}
75
76
template
<
class
Type>
77
forceinline
bool
78
QuickSortStack<Type>::empty
(
void
)
const
{
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) {
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
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
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Support::partition
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
Definition:
sort.hpp:113
Gecode::Support::QuickSortStack
Static stack for quicksort.
Definition:
sort.hpp:51
Gecode::Support::QuickSortStack::pop
void pop(Type *&l, Type *&r)
Pop two positions l and r.
Definition:
sort.hpp:90
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition:
sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::Support::insertion
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition:
sort.hpp:97
Gecode::Support::QuickSortStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
sort.hpp:78
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::swap
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition:
irt.hpp:37
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Support::Less::operator()
bool operator()(const Type &lhs, const Type &rhs)
Definition:
sort.hpp:163
a
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:259
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Support::QuickSortCutoff
const int QuickSortCutoff
Perform quicksort only for more elements.
Definition:
sort.hpp:47
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::Support::Less
Comparison class for sorting using <.
Definition:
sort.hpp:161
Gecode::Support::QuickSortStack::QuickSortStack
QuickSortStack(void)
Initialize stack as empty.
Definition:
sort.hpp:72
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Support::QuickSortStack::push
void push(Type *l, Type *r)
Push two positions l and r.
Definition:
sort.hpp:84
Gecode::Support::exchange
void exchange(Type &a, Type &b, Less &less)
Exchange elements according to order.
Definition:
sort.hpp:42