main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
int
sorted
order.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5
*
6
* Copyright:
7
* Patrick Pekczynski, 2004
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
namespace
Gecode
{
namespace
Int {
namespace
Sorted {
35
43
template
<
class
View,
bool
Perm>
44
inline
void
45
sort_sigma
(
ViewArray<View>
&
x
,
ViewArray<View>
&
z
) {
46
if
(Perm) {
47
Region
r
;
48
ViewPair<View>
* xz =
r
.alloc<
ViewPair<View>
>(
x
.size());
49
for
(
int
i
=
x
.size();
i
--; ) {
50
xz[
i
].
x
=
x
[
i
]; xz[
i
].
z
=
z
[
i
];
51
}
52
TupleMinIncExt<View>
min_inc;
53
Support::quicksort<ViewPair<View>,
TupleMinIncExt<View>
>
54
(&xz[0],
x
.size(), min_inc);
55
for
(
int
i
=
x
.size();
i
--; ) {
56
x
[
i
]=xz[
i
].
x
;
z
[
i
]=xz[
i
].z;
57
}
58
}
else
{
59
TupleMinInc<View>
min_inc;
60
Support::quicksort<View,TupleMinInc<View> >(&
x
[0],
x
.size(), min_inc);
61
}
62
}
63
72
template
<
class
View,
bool
Perm>
73
inline
void
74
sort_tau
(
ViewArray<View>
&
x
,
ViewArray<View>
&
z
,
int
tau[]) {
75
if
(Perm) {
76
TupleMaxIncExt<View>
ltmax(
x
,
z
);
77
Support::quicksort
(&(*tau),
x
.size(), ltmax);
78
}
else
{
79
TupleMaxInc<View>
ltmax(
x
);
80
Support::quicksort
(&(*tau),
x
.size(), ltmax);
81
}
82
}
83
91
template
<
class
View>
92
inline
bool
93
normalize
(
Space
& home,
94
ViewArray<View>
&
y
,
95
ViewArray<View>
&
x
,
96
bool
& nofix) {
97
98
int
ys =
y
.size();
99
for
(
int
i
= 1;
i
< ys;
i
++) {
100
ModEvent
me_lb =
y
[
i
].gq(home,
y
[
i
- 1].
min
());
101
if
(
me_failed
(me_lb))
102
return
false
;
103
nofix |= (
me_modified
(me_lb) &&
y
[
i
- 1].min() !=
y
[
i
].min());
104
}
105
106
for
(
int
i
= ys - 1;
i
--; ) {
107
ModEvent
me_ub =
y
[
i
].lq(home,
y
[
i
+ 1].
max
());
108
if
(
me_failed
(me_ub))
109
return
false
;
110
nofix |= (
me_modified
(me_ub) &&
y
[
i
+ 1].max() !=
y
[
i
].max());
111
}
112
113
int
xs =
x
.size();
114
for
(
int
i
= xs;
i
--; ) {
115
ModEvent
me =
x
[
i
].gq(home,
y
[0].
min
());
116
if
(
me_failed
(me))
117
return
false
;
118
nofix |= (
me_modified
(me) &&
x
[
i
].min() !=
y
[0].min());
119
120
me =
x
[
i
].lq(home,
y
[xs - 1].
max
());
121
if
(
me_failed
(me))
122
return
false
;
123
nofix |= (
me_modified
(me) &&
x
[
i
].max() !=
y
[xs - 1].max());
124
}
125
return
true
;
126
}
127
138
template
<
class
View>
139
inline
bool
140
perm_bc
(
Space
& home,
int
tau[],
141
SccComponent
sinfo[],
142
int
scclist[],
143
ViewArray<View>
&
x
,
144
ViewArray<View>
&
z
,
145
bool
& crossingedge,
146
bool
& nofix) {
147
148
int
ps =
x
.size();
149
150
for
(
int
i
= 1;
i
< ps;
i
++) {
151
// if there are "crossed edges"
152
if
(
x
[
i
- 1].
min
() <
x
[
i
].
min
()) {
153
if
(
z
[
i
- 1].
min
() >
z
[
i
].
min
()) {
154
if
(
z
[
i
].
min
() != sinfo[scclist[
i
]].leftmost) {
155
// edge does not take part in solution
156
if
(
z
[
i
].
assigned
()) {
// vital edge do not remove it
157
if
(
x
[
i
- 1].
max
() <
x
[
i
].
min
()) {
158
// invalid permutation
159
// the upper bound sorting cannot fix this
160
return
false
;
161
}
162
}
else
{
163
crossingedge =
true
;
164
// and the permutation can still be changed
165
// fix the permutation, i.e. modify z
166
ModEvent
me_z =
z
[
i
].gq(home,
z
[
i
- 1].
min
());
167
if
(
me_failed
(me_z)) {
168
return
false
;
169
}
170
nofix |= (
me_modified
(me_z) &&
171
z
[
i
- 1].min() !=
z
[
i
].min());
172
}
173
}
174
}
175
}
176
}
177
178
// the same check as above for the upper bounds
179
for
(
int
i
= ps - 1;
i
--; ) {
180
if
(
x
[tau[
i
]].
max
() <
x
[tau[
i
+ 1]].max()) {
181
if
(
z
[tau[
i
]].
max
() >
z
[tau[
i
+ 1]].max()) {
182
if
(
z
[tau[
i
]].
max
() != sinfo[scclist[tau[
i
]]].
rightmost
) {
183
// edge does not take part in solution
184
if
(
z
[tau[
i
]].
assigned
()) {
185
if
(
x
[tau[
i
+ 1]].
min
() >
x
[tau[
i
]].max()) {
186
// invalid permutation
187
return
false
;
188
}
189
}
else
{
190
crossingedge =
true
;
191
ModEvent
me_z =
z
[tau[
i
]].lq(home,
z
[tau[
i
+ 1]].
max
());
192
if
(
me_failed
(me_z)) {
193
return
false
;
194
}
195
nofix |= (
me_modified
(me_z) &&
196
z
[tau[
i
+ 1]].max() !=
z
[tau[
i
]].max());
197
}
198
}
199
}
200
}
201
}
202
203
return
true
;
204
}
205
206
}}}
207
208
// STATISTICS: int-prop
209
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Int::Sorted::ViewPair
Pair of views.
Definition:
sortsup.hpp:333
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:767
Gecode::Int::Sorted::sort_sigma
void sort_sigma(ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition:
order.hpp:45
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition:
modevent.hpp:54
Gecode::Int::Sorted::perm_bc
bool perm_bc(Space &home, int tau[], SccComponent sinfo[], int scclist[], ViewArray< View > &x, ViewArray< View > &z, bool &crossingedge, bool &nofix)
Bounds consistency on the permutation views.
Definition:
order.hpp:140
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:43
Gecode::Int::Sorted::sort_tau
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition:
order.hpp:74
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:767
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition:
sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::VarImpVar::x
VarImp * x
Pointer to variable implementation.
Definition:
var.hpp:50
Gecode::Int::Sorted::TupleMaxIncExt
Extended Index comparison for ViewArray<Tuple>.
Definition:
sortsup.hpp:285
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::Int::Sorted::ViewPair::z
View z
Definition:
sortsup.hpp:336
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Int::Sorted::TupleMaxInc
Index comparison for ViewArray<Tuple>.
Definition:
sortsup.hpp:260
Gecode::Int::Sorted::ViewPair::x
View x
Definition:
sortsup.hpp:335
Gecode::Int::Sorted::SccComponent::rightmost
int rightmost
Rightmost reachable y-node in a scc.
Definition:
sortsup.hpp:62
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition:
core.hpp:62
Gecode::Int::Sorted::normalize
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition:
order.hpp:93
Gecode::Int::Sorted::SccComponent
Representation of a strongly connected component.
Definition:
sortsup.hpp:53
Gecode::Int::Sorted::TupleMinIncExt
Extended view comparison on pairs of views.
Definition:
sortsup.hpp:350
Gecode::Int::Sorted::TupleMinInc
View comparison on ViewTuples.
Definition:
sortsup.hpp:319
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition:
modevent.hpp:59
Gecode::ViewArray
View arrays.
Definition:
array.hpp:253
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})