Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
34namespace Gecode { namespace Int { namespace Sorted {
35
42
43 template<class View, bool Perm>
44 inline void
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 }
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
71
72 template<class View, bool Perm>
73 inline void
75 if (Perm) {
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
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
137
138 template<class View>
139 inline bool
140 perm_bc(Space& home, int tau[],
141 SccComponent sinfo[],
142 int scclist[],
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
Representation of a strongly connected component.
Definition sortsup.hpp:53
Extended Index comparison for ViewArray<Tuple>.
Definition sortsup.hpp:285
Index comparison for ViewArray<Tuple>.
Definition sortsup.hpp:260
Extended view comparison on pairs of views.
Definition sortsup.hpp:350
View comparison on ViewTuples.
Definition sortsup.hpp:319
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Sorted propagators
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition order.hpp:74
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition order.hpp:93
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
void sort_sigma(ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition order.hpp:45
Finite domain integers.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62