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