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 #include "support/sort.hh"
00023
00024 namespace Gecode { namespace Int { namespace Sortedness {
00025
00033 template <class View, class Tuple, bool Perm>
00034 forceinline void
00035 sort_sigma(ViewArray<Tuple>& xz, bool fixed) {
00036 int xs = xz.size();
00037
00038 if (fixed) {
00039 TupleMinIncPerm<Tuple> min_inc;
00040 Support::quicksort<Tuple, TupleMinIncPerm<Tuple> >
00041 (&xz[0], xs, min_inc);
00042 } else {
00043 TupleMinInc<Tuple> min_inc;
00044 Support::quicksort<Tuple, TupleMinInc<Tuple> >(&xz[0], xs, min_inc);
00045 }
00046 }
00047
00056 template <class View, class Tuple, bool Perm>
00057 forceinline void
00058 sort_tau(ViewArray<Tuple>& xz, int tau[]) {
00059 int xs = xz.size();
00060 TupleMaxInc<Tuple> ltmax(xz);
00061 Support::quicksort(&(*tau), xs, ltmax);
00062 }
00063
00071 template <class View, class Tuple, bool shared>
00072 forceinline bool
00073 normalize(Space* home,
00074 ViewArray<View>& y,
00075 ViewArray<Tuple>& xz,
00076 bool& nofix) {
00077
00078 int ys = y.size();
00079 for (int i = 1; i < ys; i++) {
00080 if (shared && y[i].modified()) {
00081 nofix = true;
00082 return true;
00083 }
00084 ModEvent me_lb = y[i].gq(home, y[i - 1].min());
00085 if (me_failed(me_lb)) {
00086 return false;
00087 }
00088 nofix |= (me_modified(me_lb) && y[i - 1].min() != y[i].min());
00089 }
00090
00091 for (int i = ys - 1; i--; ) {
00092 if (shared && y[i].modified()) {
00093 nofix = true;
00094 return true;
00095 }
00096
00097 ModEvent me_ub = y[i].lq(home, y[i + 1].max());
00098 if (me_failed(me_ub)) {
00099 return false;
00100 }
00101 nofix |= (me_modified(me_ub) && y[i + 1].max() != y[i].max());
00102 }
00103
00104 int xs = xz.size();
00105 for (int i = xs; i--; ) {
00106 if (shared && xz[i][0].modified()) {
00107 nofix = true;
00108 return true;
00109 }
00110
00111 ModEvent me = xz[i][0].lq(home, y[xs - 1].max());
00112 if (me_failed(me)) {
00113 return false;
00114 }
00115 nofix |= (me_modified(me) && xz[i][0].max() != y[xs - 1].max());
00116 }
00117 return true;
00118 }
00119
00129 template<class View, class Tuple, bool Perm, bool shared>
00130 forceinline bool
00131 perm_bc(Space* home, int tau[],
00132 ViewArray<Tuple>& xz,
00133 bool& crossingedge,
00134 bool& nofix) {
00135
00136 int ps = xz.size();
00137 bool edge_up = false;
00138 for (int i = 1; i < ps; i++) {
00139
00140 if (xz[i][0].min() > xz[i - 1][0].max()) {
00141 if (xz[i][1].min() < xz[i - 1][1].min()) {
00142 edge_up = true;
00143 break;
00144 }
00145 }
00146 }
00147
00148 bool edge_low = false;
00149 for (int i = ps - 1; i--; ) {
00150 if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].min()) {
00151 if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00152 edge_low = true;
00153 break;
00154 }
00155 }
00156 }
00157
00158 if (edge_up && edge_low) {
00159 for (int i = 1; i < ps; i++) {
00160
00161 if (xz[i][0].min() > xz[i - 1][0].max()) {
00162 if (xz[i][1].min() < xz[i - 1][1].min()) {
00163
00164 crossingedge = true;
00165
00166 if (!xz[i][1].assigned() && !xz[i - 1][1].assigned()) {
00167
00168
00169 ModEvent me_z = xz[i][1].gq(home, xz[i - 1][1].min());
00170 if (me_failed(me_z)) {
00171 return false;
00172 }
00173 nofix |= ( me_modified(me_z) &&
00174 xz[i - 1][1].min() != xz[i][1].min());
00175 } else {
00176
00177
00178
00179 if (shared && xz[i - 1][0].modified()) {
00180 nofix = true;
00181 return true;
00182 }
00183
00184 ModEvent me_x = xz[i - 1][0].gq(home,xz[i][0].min());
00185 if (me_failed(me_x)) {
00186 return false;
00187 }
00188 nofix |= (me_modified(me_x) &&
00189 xz[i][0].min() != xz[i - 1][0].min());
00190 }
00191 }
00192 }
00193 }
00194
00195
00196 for (int i = ps - 1; i--; ) {
00197 if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].min()) {
00198 if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00199
00200 crossingedge = true;
00201 if (!xz[tau[i]][1].assigned() && !xz[tau[i + 1]][1].assigned()) {
00202
00203 ModEvent me_z = xz[tau[i]][1].lq(home, xz[tau[i + 1]][1].max());
00204 if (me_failed(me_z)) {
00205 return false;
00206 }
00207 nofix |= (me_modified(me_z) &&
00208 xz[tau[i + 1]][1].max() != xz[tau[i]][1].max());
00209 } else {
00210
00211 if (shared && xz[tau[i + 1]][0].modified()) {
00212 nofix = true;
00213 return true;
00214 }
00215
00216 ModEvent me_x = xz[tau[i + 1]][0].lq(home,xz[tau[i]][0].max());
00217 if (me_failed(me_x)) {
00218 return false;
00219 }
00220 nofix |= (me_modified(me_x) &&
00221 xz[tau[i]][0].max() != xz[tau[i + 1]][0].max());
00222 }
00223 }
00224 }
00225 }
00226 }
00227 return true;
00228 }
00229
00230 }}}
00231
00232
00233