Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
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
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
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
98  ViewArray<View>& y,
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[],
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 
Index comparison for ViewArray.
Definition: sortsup.hpp:265
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition: order.hpp:78
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
int ModEvent
Type for modification events.
Definition: core.hpp:146
View comparison on ViewTuples.
Definition: sortsup.hpp:324
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1362
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition: order.hpp:97
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:66
void sort_sigma(Space &home, ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition: order.hpp:49
View arrays.
Definition: array.hpp:234
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
Representation of a strongly connected component.
Definition: sortsup.hpp:57
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Extended Index comparison for ViewArray.
Definition: sortsup.hpp:290
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
Extended view comparison on pairs of views.
Definition: sortsup.hpp:355