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