narrowing.hpp
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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 namespace Gecode { namespace Int { namespace Sorted {
00035
00052 template<class View>
00053 inline void
00054 computesccs(ViewArray<View>& x, ViewArray<View>& y,
00055 int phi[], SccComponent sinfo[], int scclist[]) {
00056
00057
00058 int xs = x.size();
00059 Region r;
00060 Support::StaticStack<int,Region> cs(r,xs);
00061
00062
00063 for (int j = 0; j < xs; j++) {
00064 int yjmin = y[j].min();
00065 while (!cs.empty() && x[phi[sinfo[cs.top()].rightmost]].max() < yjmin) {
00066
00067 cs.pop();
00068 }
00069
00070
00071
00072
00073 int i = phi[j];
00074 int ximin = x[i].min();
00075 while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) {
00076
00077
00078
00079 int top = cs.top();
00080
00081 sinfo[sinfo[j].leftmost].left = top;
00082 sinfo[top].right = sinfo[j].leftmost;
00083
00084 sinfo[j].leftmost = sinfo[top].leftmost;
00085
00086 sinfo[sinfo[top].leftmost].rightmost = j;
00087 cs.pop();
00088 }
00089 cs.push(j);
00090 }
00091 cs.reset();
00092
00093
00094
00095
00096
00097 for (int i = 0; i < xs; i++) {
00098 if (sinfo[i].left == i) {
00099 int scc = sinfo[i].rightmost;
00100 int z = i;
00101
00102 while (sinfo[z].right != z) {
00103 sinfo[z].rightmost = scc;
00104 scclist[phi[z]] = scc;
00105 z = sinfo[z].right;
00106 }
00107 sinfo[z].rightmost = scc;
00108 scclist[phi[z]] = scc;
00109 }
00110 }
00111 }
00112
00128 template<class View, bool Perm>
00129 inline bool
00130 narrow_domx(Space& home,
00131 ViewArray<View>& x,
00132 ViewArray<View>& y,
00133 ViewArray<View>& z,
00134 int tau[],
00135 int[],
00136 int scclist[],
00137 SccComponent sinfo[],
00138 bool& nofix) {
00139
00140 int xs = x.size();
00141
00142
00143 for (int i = 0; i < xs; i++) {
00144
00145 int xmin = x[i].min();
00146
00147
00148
00149
00150
00151
00152
00153 int start = sinfo[scclist[i]].leftmost;
00154 while (y[start].max() < xmin) {
00155 start = sinfo[start].right;
00156 }
00157
00158 if (Perm) {
00159
00160
00161
00162 ModEvent me_plb = z[i].gq(home, start);
00163 if (me_failed(me_plb)) {
00164 return false;
00165 }
00166 nofix |= (me_modified(me_plb) && start != z[i].min());
00167 }
00168
00169 ModEvent me_lb = x[i].gq(home, y[start].min());
00170 if (me_failed(me_lb)) {
00171 return false;
00172 }
00173 nofix |= (me_modified(me_lb) &&
00174 y[start].min() != x[i].min());
00175
00176 int ptau = tau[xs - 1 - i];
00177 int xmax = x[ptau].max();
00178
00179
00180
00181
00182
00183
00184
00185 start = sinfo[scclist[ptau]].rightmost;
00186 while (y[start].min() > xmax) {
00187 start = sinfo[start].left;
00188 }
00189
00190 if (Perm) {
00191
00192
00193 ModEvent me_pub = z[ptau].lq(home, start);
00194 if (me_failed(me_pub)) {
00195 return false;
00196 }
00197 nofix |= (me_modified(me_pub) && start != z[ptau].max());
00198 }
00199
00200 ModEvent me_ub = x[ptau].lq(home, y[start].max());
00201 if (me_failed(me_ub)) {
00202 return false;
00203 }
00204 nofix |= (me_modified(me_ub) &&
00205 y[start].max() != x[ptau].max());
00206 }
00207 return true;
00208 }
00209
00220 template<class View>
00221 inline bool
00222 narrow_domy(Space& home,
00223 ViewArray<View>& x, ViewArray<View>& y,
00224 int phi[], int phiprime[], bool& nofix) {
00225 for (int i=x.size(); i--; ) {
00226 ModEvent me_lb = y[i].gq(home, x[phiprime[i]].min());
00227 if (me_failed(me_lb)) {
00228 return false;
00229 }
00230 nofix |= (me_modified(me_lb) &&
00231 x[phiprime[i]].min() != y[i].min());
00232
00233 ModEvent me_ub = y[i].lq(home, x[phi[i]].max());
00234 if (me_failed(me_ub)) {
00235 return false;
00236 }
00237 nofix |= (me_modified(me_ub) &&
00238 x[phi[i]].max() != y[i].max());
00239 }
00240 return true;
00241 }
00242
00243 }}}
00244
00245
00246