main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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
* Last modified:
10
* $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11
* $Revision: 13068 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
namespace
Gecode
{
namespace
Int {
namespace
Sorted {
39
47
template
<
class
View,
bool
Perm>
48
inline
void
49
sort_sigma
(
Space
& home,
ViewArray<View>
&
x
,
ViewArray<View>
&
z
) {
50
if
(Perm) {
51
Region
r
(home);
52
ViewPair<View>
* xz =
r
.alloc<
ViewPair<View>
>(
x
.size());
53
for
(
int
i
=
x
.size();
i
--; ) {
54
xz[
i
].
x
=
x
[
i
]; xz[
i
].
z
=
z
[
i
];
55
}
56
TupleMinIncExt<View>
min_inc;
57
Support::quicksort<ViewPair<View>,
TupleMinIncExt<View>
>
58
(&xz[0],
x
.size(), min_inc);
59
for
(
int
i
=
x
.size();
i
--; ) {
60
x
[
i
]=xz[
i
].
x
;
z
[
i
]=xz[
i
].z;
61
}
62
}
else
{
63
TupleMinInc<View>
min_inc;
64
Support::quicksort<View,TupleMinInc<View> >(&
x
[0],
x
.size(), min_inc);
65
}
66
}
67
76
template
<
class
View,
bool
Perm>
77
inline
void
78
sort_tau
(
ViewArray<View>
&
x
,
ViewArray<View>
&
z
,
int
tau[]) {
79
if
(Perm) {
80
TupleMaxIncExt<View>
ltmax(
x
,
z
);
81
Support::quicksort
(&(*tau),
x
.size(), ltmax);
82
}
else
{
83
TupleMaxInc<View>
ltmax(
x
);
84
Support::quicksort
(&(*tau),
x
.size(), ltmax);
85
}
86
}
87
95
template
<
class
View>
96
inline
bool
97
normalize
(
Space
& home,
98
ViewArray<View>
&
y
,
99
ViewArray<View>
&
x
,
100
bool
& nofix) {
101
102
int
ys =
y
.size();
103
for
(
int
i
= 1;
i
< ys;
i
++) {
104
ModEvent
me_lb =
y
[
i
].gq(home,
y
[
i
- 1].
min
());
105
if
(
me_failed
(me_lb))
106
return
false
;
107
nofix |= (
me_modified
(me_lb) &&
y
[
i
- 1].min() !=
y
[
i
].min());
108
}
109
110
for
(
int
i
= ys - 1;
i
--; ) {
111
ModEvent
me_ub =
y
[
i
].lq(home,
y
[
i
+ 1].
max
());
112
if
(
me_failed
(me_ub))
113
return
false
;
114
nofix |= (
me_modified
(me_ub) &&
y
[
i
+ 1].max() !=
y
[
i
].max());
115
}
116
117
int
xs =
x
.size();
118
for
(
int
i
= xs;
i
--; ) {
119
ModEvent
me =
x
[
i
].gq(home,
y
[0].
min
());
120
if
(
me_failed
(me))
121
return
false
;
122
nofix |= (
me_modified
(me) &&
x
[
i
].min() !=
y
[0].min());
123
124
me =
x
[
i
].lq(home,
y
[xs - 1].
max
());
125
if
(
me_failed
(me))
126
return
false
;
127
nofix |= (
me_modified
(me) &&
x
[
i
].max() !=
y
[xs - 1].max());
128
}
129
return
true
;
130
}
131
142
template
<
class
View>
143
inline
bool
144
perm_bc
(
Space
& home,
int
tau[],
145
SccComponent
sinfo[],
146
int
scclist[],
147
ViewArray<View>
&
x
,
148
ViewArray<View>
&
z
,
149
bool
& crossingedge,
150
bool
& nofix) {
151
152
int
ps =
x
.size();
153
154
for
(
int
i
= 1;
i
< ps;
i
++) {
155
// if there are "crossed edges"
156
if
(
x
[
i
- 1].
min
() <
x
[
i
].
min
()) {
157
if
(
z
[
i
- 1].
min
() >
z
[
i
].
min
()) {
158
if
(
z
[
i
].
min
() != sinfo[scclist[
i
]].leftmost) {
159
// edge does not take part in solution
160
if
(
z
[
i
].
assigned
()) {
// vital edge do not remove it
161
if
(
x
[
i
- 1].
max
() <
x
[
i
].
min
()) {
162
// invalid permutation
163
// the upper bound sorting cannot fix this
164
return
false
;
165
}
166
}
else
{
167
crossingedge =
true
;
168
// and the permutation can still be changed
169
// fix the permutation, i.e. modify z
170
ModEvent
me_z =
z
[
i
].gq(home,
z
[
i
- 1].
min
());
171
if
(
me_failed
(me_z)) {
172
return
false
;
173
}
174
nofix |= (
me_modified
(me_z) &&
175
z
[
i
- 1].min() !=
z
[
i
].min());
176
}
177
}
178
}
179
}
180
}
181
182
// the same check as above for the upper bounds
183
for
(
int
i
= ps - 1;
i
--; ) {
184
if
(
x
[tau[
i
]].
max
() <
x
[tau[
i
+ 1]].max()) {
185
if
(
z
[tau[
i
]].
max
() >
z
[tau[
i
+ 1]].max()) {
186
if
(
z
[tau[
i
]].
max
() != sinfo[scclist[tau[
i
]]].
rightmost
) {
187
// edge does not take part in solution
188
if
(
z
[tau[
i
]].
assigned
()) {
189
if
(
x
[tau[
i
+ 1]].
min
() >
x
[tau[
i
]].max()) {
190
// invalid permutation
191
return
false
;
192
}
193
}
else
{
194
crossingedge =
true
;
195
ModEvent
me_z =
z
[tau[
i
]].lq(home,
z
[tau[
i
+ 1]].
max
());
196
if
(
me_failed
(me_z)) {
197
return
false
;
198
}
199
nofix |= (
me_modified
(me_z) &&
200
z
[tau[
i
+ 1]].max() !=
z
[tau[
i
]].max());
201
}
202
}
203
}
204
}
205
}
206
207
return
true
;
208
}
209
210
}}}
211
212
// STATISTICS: int-prop
213
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::Int::Sorted::ViewPair
Pair of views.
Definition:
sortsup.hpp:338
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition:
modevent.hpp:58
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:144
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:53
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:47
Gecode::Int::Sorted::sort_tau
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition:
order.hpp:78
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:784
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition:
sort.hpp:134
Gecode
Gecode toplevel namespace
Gecode::VarImpVar::x
VarImp * x
Pointer to variable implementation.
Definition:
var.hpp:54
Gecode::Int::Sorted::TupleMaxIncExt
Extended Index comparison for ViewArray<Tuple>.
Definition:
sortsup.hpp:290
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::Int::Sorted::ViewPair::z
View z
Definition:
sortsup.hpp:341
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Int::Sorted::TupleMaxInc
Index comparison for ViewArray<Tuple>.
Definition:
sortsup.hpp:265
Gecode::Int::Sorted::ViewPair::x
View x
Definition:
sortsup.hpp:340
Gecode::Int::Sorted::SccComponent::rightmost
int rightmost
Rightmost reachable y-node in a scc.
Definition:
sortsup.hpp:66
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition:
core.hpp:142
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:97
Gecode::Int::Sorted::SccComponent
Representation of a strongly connected component.
Definition:
sortsup.hpp:57
Gecode::Int::Sorted::sort_sigma
void sort_sigma(Space &home, ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition:
order.hpp:49
Gecode::Int::Sorted::TupleMinIncExt
Extended view comparison on pairs of views.
Definition:
sortsup.hpp:355
Gecode::Int::Sorted::TupleMinInc
View comparison on ViewTuples.
Definition:
sortsup.hpp:324
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:71
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition:
modevent.hpp:63
Gecode::ViewArray
View arrays.
Definition:
array.hpp:234