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
00047 template <class View, class Tuple, bool Perm>
00048 inline void
00049 sort_sigma(ViewArray<Tuple>& xz, bool) {
00050 int xs = xz.size();
00051
00052
00053 if (Perm) {
00054 TupleMinIncExt<Tuple> min_inc;
00055 Support::quicksort<Tuple, TupleMinIncExt<Tuple> >(&xz[0], xs, min_inc);
00056 } else {
00057 TupleMinInc<Tuple> min_inc;
00058 Support::quicksort<Tuple, TupleMinInc<Tuple> >(&xz[0], xs, min_inc);
00059 }
00060 }
00061
00070 template <class View, class Tuple, bool Perm>
00071 inline void
00072 sort_tau(ViewArray<Tuple>& xz, int tau[]) {
00073 int xs = xz.size();
00074
00075 if (Perm) {
00076 TupleMaxIncExt<Tuple> ltmax(xz);
00077 Support::quicksort(&(*tau), xs, ltmax);
00078 } else {
00079 TupleMaxInc<Tuple> ltmax(xz);
00080 Support::quicksort(&(*tau), xs, ltmax);
00081 }
00082 }
00083
00091 template <class View, class Tuple>
00092 inline bool
00093 normalize(Space* home,
00094 ViewArray<View>& y,
00095 ViewArray<Tuple>& xz,
00096 bool& nofix) {
00097
00098 int ys = y.size();
00099 for (int i = 1; i < ys; i++) {
00100 ModEvent me_lb = y[i].gq(home, y[i - 1].min());
00101 if (me_failed(me_lb))
00102 return false;
00103 nofix |= (me_modified(me_lb) && y[i - 1].min() != y[i].min());
00104 }
00105
00106 for (int i = ys - 1; i--; ) {
00107 ModEvent me_ub = y[i].lq(home, y[i + 1].max());
00108 if (me_failed(me_ub))
00109 return false;
00110 nofix |= (me_modified(me_ub) && y[i + 1].max() != y[i].max());
00111 }
00112
00113 int xs = xz.size();
00114 for (int i = xs; i--; ) {
00115 ModEvent me = xz[i][0].gq(home, y[0].min());
00116 if (me_failed(me))
00117 return false;
00118 nofix |= (me_modified(me) && xz[i][0].min() != y[0].min());
00119
00120 me = xz[i][0].lq(home, y[xs - 1].max());
00121 if (me_failed(me))
00122 return false;
00123 nofix |= (me_modified(me) && xz[i][0].max() != y[xs - 1].max());
00124 }
00125 return true;
00126 }
00127
00138 template<class View, class Tuple, bool Perm>
00139 inline bool
00140 perm_bc(Space* home, int tau[],
00141 SccComponent sinfo[],
00142 int scclist[],
00143 ViewArray<Tuple>& xz,
00144 bool& crossingedge,
00145 bool& nofix) {
00146
00147 int ps = xz.size();
00148
00149 for (int i = 1; i < ps; i++) {
00150
00151 if (xz[i - 1][0].min() < xz[i][0].min()) {
00152 if (xz[i - 1][1].min() > xz[i][1].min()) {
00153 if (xz[i][1].min() != sinfo[scclist[i]].leftmost) {
00154
00155 if (xz[i][1].assigned()) {
00156 if (xz[i - 1][0].max() < xz[i][0].min()) {
00157
00158
00159 return false;
00160 }
00161 } else {
00162 crossingedge = true;
00163
00164
00165 ModEvent me_z = xz[i][1].gq(home, xz[i - 1][1].min());
00166 if (me_failed(me_z)) {
00167 return false;
00168 }
00169 nofix |= ( me_modified(me_z) &&
00170 xz[i - 1][1].min() != xz[i][1].min());
00171 }
00172 }
00173 }
00174 }
00175 }
00176
00177
00178 for (int i = ps - 1; i--; ) {
00179 if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].max()) {
00180 if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00181 if (xz[tau[i]][1].max() != sinfo[scclist[tau[i]]].rightmost) {
00182
00183 if (xz[tau[i]][1].assigned()) {
00184 if (xz[tau[i + 1]][0].min() > xz[tau[i]][0].max()) {
00185
00186 return false;
00187 }
00188 } else {
00189 crossingedge = true;
00190 ModEvent me_z = xz[tau[i]][1].lq(home, xz[tau[i + 1]][1].max());
00191 if (me_failed(me_z)) {
00192 return false;
00193 }
00194 nofix |= (me_modified(me_z) &&
00195 xz[tau[i + 1]][1].max() != xz[tau[i]][1].max());
00196 }
00197 }
00198 }
00199 }
00200 }
00201
00202 return true;
00203 }
00204
00205 }}}
00206
00207
00208