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