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