Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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
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
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
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[],
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 
Post propagator for SetVar x
Definition: set.hh:767
Pair of views.
Definition: sortsup.hpp:333
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void sort_sigma(ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition: order.hpp:45
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
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 max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition: order.hpp:74
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Computation spaces.
Definition: core.hpp:1742
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
Gecode toplevel namespace
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:50
Extended Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:285
Handle to region.
Definition: region.hpp:55
View z
Definition: sortsup.hpp:336
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:260
View x
Definition: sortsup.hpp:335
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:62
int ModEvent
Type for modification events.
Definition: core.hpp:62
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition: order.hpp:93
Representation of a strongly connected component.
Definition: sortsup.hpp:53
Extended view comparison on pairs of views.
Definition: sortsup.hpp:350
View comparison on ViewTuples.
Definition: sortsup.hpp:319
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
View arrays.
Definition: array.hpp:253
Gecode::IntArgs i({1, 2, 3, 4})