main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 31 2012 16:21:27 for Gecode by
doxygen
1.8.1.2
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: 2009-09-09 05:10:29 +1000 (Wed, 09 Sep 2009) $ by $Author: schulte $
11
* $Revision: 9692 $
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