narrowing.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "support/static-stack.hh"
00023
00024 namespace Gecode { namespace Int { namespace Sortedness {
00025
00032 class SccComponent {
00033 public:
00035 int leftmost;
00037 int left;
00039 int right;
00041 int rightmost;
00042 };
00043
00044
00045
00062 template<class View, class Tuple>
00063 forceinline void
00064 computesccs(Space* home,
00065 ViewArray<Tuple>& xz,
00066 ViewArray<View>& y,
00067 int phi[],
00068 SccComponent sinfo[],
00069 int scclist[]) {
00070
00071
00072 int xs = xz.size();
00073 Support::StaticStack<int> cs(xs);
00074
00075
00076 for (int j = 0; j < xs; j++) {
00077
00078 int yjmin = y[j].min();
00079 while (!cs.empty() && xz[phi[sinfo[cs.top()].rightmost]][0].max() < yjmin) {
00080
00081 cs.pop();
00082 }
00083
00084
00085
00086
00087 int i = phi[j];
00088 int ximin = xz[i][0].min();
00089 while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) {
00090
00091
00092
00093 int top = cs.top();
00094
00095 sinfo[sinfo[j].leftmost].left = top;
00096 sinfo[top].right = sinfo[j].leftmost;
00097
00098 sinfo[j].leftmost = sinfo[top].leftmost;
00099
00100 sinfo[sinfo[top].leftmost].rightmost = j;
00101 cs.pop();
00102 }
00103 cs.push(j);
00104 }
00105 cs.reset();
00106
00107
00108
00109
00110 for (int i = 0; i < xs; i++) {
00111 if (sinfo[i].left == i) {
00112 int scc = sinfo[i].rightmost;
00113 int z = i;
00114
00115 while (sinfo[z].right != z) {
00116 sinfo[z].rightmost = scc;
00117 scclist[phi[z]] = scc;
00118 z = sinfo[z].right;
00119 }
00120 sinfo[z].rightmost = scc;
00121 scclist[phi[z]] = scc;
00122 }
00123 }
00124 }
00125
00141 template<class View, class Tuple, bool Perm, bool shared>
00142 forceinline bool
00143 narrow_domx(Space* home,
00144 ViewArray<Tuple>& xz,
00145 ViewArray<View>& y,
00146 int tau[],
00147 int phi[],
00148 int scclist[],
00149 SccComponent sinfo[],
00150 bool& nofix) {
00151
00152 int xs = xz.size();
00153
00154
00155 for (int i = 0; i < xs; i++) {
00156
00157 int xmin = xz[i][0].min();
00158
00159
00160
00161
00162
00163
00164 int start = sinfo[scclist[i]].leftmost;
00165 while (y[start].max() < xmin) {
00166 start = sinfo[start].right;
00167 }
00168
00169 sinfo[scclist[i]].leftmost = start;
00170 if (Perm) {
00171
00172
00173
00174 ModEvent me_plb = xz[i][1].gq(home, start);
00175 if (me_failed(me_plb)) {
00176 return false;
00177 }
00178 nofix |= (me_modified(me_plb) && start != xz[i][1].min());
00179 }
00180
00181 if (shared && xz[i][0].modified()) {
00182 nofix = true;
00183 return true;
00184 }
00185 ModEvent me_lb = xz[i][0].gq(home, y[start].min());
00186 if (me_failed(me_lb)) {
00187 return false;
00188 }
00189 nofix |= (me_modified(me_lb) &&
00190 y[start].min() != xz[i][0].min());
00191
00192 int ptau = tau[xs - 1 - i];
00193 int xmax = xz[ptau][0].max();
00194
00195
00196
00197
00198
00199
00200 start = sinfo[scclist[ptau]].rightmost;
00201 while (y[start].min() > xmax) {
00202 start = sinfo[start].left;
00203 }
00204
00205 sinfo[scclist[ptau]].rightmost = start;
00206
00207 if (Perm) {
00208
00209
00210 ModEvent me_pub = xz[ptau][1].lq(home, start);
00211 if (me_failed(me_pub)) {
00212 return false;
00213 }
00214 nofix |= (me_modified(me_pub) && start != xz[ptau][1].max());
00215 }
00216
00217 if (shared && xz[ptau][0].modified()) {
00218 nofix = true;
00219 return true;
00220 }
00221
00222 ModEvent me_ub = xz[ptau][0].lq(home, y[start].max());
00223 if (me_failed(me_ub)) {
00224 return false;
00225 }
00226 nofix |= (me_modified(me_ub) &&
00227 y[start].max() != xz[ptau][0].max());
00228 }
00229 return true;
00230 }
00231
00242 template<class View, class Tuple, bool Perm, bool shared>
00243 forceinline bool
00244 narrow_domy(Space* home,
00245 ViewArray<Tuple>& xz,
00246 ViewArray<View>& y,
00247 int phi[],
00248 int phiprime[],
00249 bool& nofix) {
00250
00251 int xs = xz.size();
00252 for (int i = xs; i--; ) {
00253 if (shared && y[i].modified()) {
00254 nofix = true;
00255 return true;
00256 }
00257 ModEvent me_lb = y[i].gq(home, xz[phiprime[i]][0].min());
00258 if (me_failed(me_lb)) {
00259 return false;
00260 }
00261 nofix |= (me_modified(me_lb) &&
00262 xz[phiprime[i]][0].min() != y[i].min());
00263
00264 if (shared && y[i].modified()) {
00265 nofix = true;
00266 return true;
00267 }
00268
00269 ModEvent me_ub = y[i].lq(home, xz[phi[i]][0].max());
00270 if (me_failed(me_ub)) {
00271 return false;
00272 }
00273 nofix |= (me_modified(me_ub) &&
00274 xz[phi[i]][0].max() != y[i].max());
00275 }
00276 return true;
00277 }
00278
00279 }}}
00280
00281
00282