Generated on Wed Nov 1 15:04:39 2006 for Gecode by doxygen 1.4.5

sortedness.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00010  *     $Revision: 3512 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 namespace Gecode { namespace Int { namespace Sortedness {
00023 
00024 
00025   /*
00026    * Summary of the propagation algorithm as implemented in the
00027    * propagate method below:
00028    *
00029    * STEP 1: Normalize the domains of the y variables
00030    * STEP 2: Sort the domains of the x variables according to their lower
00031    *         and upper endpoints
00032    * STEP 3: Compute the matchings phi and phiprime with
00033    *         Glover's matching algorithm
00034    * STEP 4: Compute the strongly connected components in
00035    *         the oriented intersection graph
00036    * STEP 5: Narrow the domains of the variables
00037    *
00038    */
00039 
00056   template<class View, class Tuple, bool Perm>
00057   ExecStatus
00058   bounds_propagation(Space* home,
00059                      ViewArray<Tuple>& xz,
00060                      ViewArray<View>& y,
00061                      bool& repairpass,
00062                      bool& nofix,
00063                      bool& match_fixed){
00064 
00065     int n        = xz.size();
00066 
00067     GECODE_AUTOARRAY(int, tau,      n);
00068     GECODE_AUTOARRAY(int, phi,      n);
00069     GECODE_AUTOARRAY(int, phiprime, n);
00070     GECODE_AUTOARRAY(OfflineMinItem, sequence, n);
00071     GECODE_AUTOARRAY(int, vertices, n);
00072 
00073     if (match_fixed) {
00074       // sorting is determined
00075       // sigma and tau coincide
00076       for (int i = xz.size(); i--; ) {
00077         int pi = xz[i][1].val();
00078         tau[pi] = i;
00079       }
00080     } else {
00081       for (int i = n; i--; ) {
00082         tau[i] = i;
00083       }
00084     }
00085 
00086     bool yval    = true;
00087     bool ysorted = true;
00088     for (int i = n; i--; ) {
00089       yval    &= y[i].assigned();
00090       if (i) {
00091         ysorted &= (y[i].min() <= y[i - 1].min() &&
00092                     y[i].max() <= y[i - 1].max());
00093       }
00094     }
00095 
00096     if (Perm) {
00097 
00098       // normalized and sorted
00099       // collect all bounds
00100 
00101       // minimum bound
00102       int mib = y[0].min();
00103       // maximum bound
00104       int mab = y[n - 1].max();
00105       // interval size
00106       int ivs = (mab - mib + 1);
00107       GECODE_AUTOARRAY(Rank, allbnd, ivs);
00108       int iter = mib;
00109       int idx = 0;
00110       while(iter <= mab && idx < n) {
00111         if (y[idx].min() > iter) {
00112           // idx cannot be zero because consisteny in posting
00113           assert(idx > 0);
00114           allbnd[iter - mib].min = idx;
00115           allbnd[iter - mib].max = idx - 1;
00116           iter++;
00117         } else {
00118           if (y[idx].min() <= iter && iter <= y[idx].max() ) {
00119             allbnd[iter - mib].min = idx;
00120             allbnd[iter - mib].max = idx;
00121             iter++;
00122           } else {
00123             idx++;
00124           }
00125         }
00126       }
00127 
00128       iter = mab;
00129       idx = n -1;
00130       while(iter >= mib && idx >= 0) {
00131         if (y[idx].min() > iter) {
00132           // idx cannot be zero because consisteny in posting
00133           assert(idx > 0);
00134           allbnd[iter - mib].max = idx - 1;
00135           iter--;
00136         } else {
00137           if (y[idx].min() <= iter && iter <= y[idx].max() ) {
00138             allbnd[iter - mib].max = idx;
00139             iter--;
00140           } else {
00141             idx--;
00142           }
00143         }
00144       }
00145 
00146       for (int i = n; i--; ) {
00147         // minimum reachable y-variable
00148         int minr = allbnd[xz[i][0].min() - mib].min;
00149         int maxr = allbnd[xz[i][0].max() - mib].max;
00150 
00151         ModEvent me = xz[i][0].gq(home, y[minr].min());
00152         if (me_failed(me)) {
00153           return ES_FAILED;
00154         }
00155         nofix |= (me_modified(me) &&
00156                   xz[i][0].min() != y[minr].min());
00157 
00158         me = xz[i][0].lq(home, y[maxr].max());
00159         if (me_failed(me)) {
00160           return ES_FAILED;
00161         }
00162         nofix |= (me_modified(me) &&
00163                   xz[i][0].min() != y[maxr].max());
00164 
00165         me = xz[i][1].gq(home, minr);
00166         if (me_failed(me)) {
00167           return ES_FAILED;
00168         }
00169         nofix |= (me_modified(me) &&  xz[i][1].min() != minr);
00170 
00171         me = xz[i][1].lq(home, maxr);
00172         if (me_failed(me)) {
00173           return ES_FAILED;
00174         }
00175         nofix |= (me_modified(me) &&  xz[i][1].max() != maxr);
00176 
00177       }
00178 
00179       // channel information from x to y through permutation variables in z
00180       if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00181         return ES_FAILED;
00182       }
00183       if (nofix) {
00184         return ES_NOFIX;
00185       }
00186     }
00187 
00188     /*
00189      * STEP 1:
00190      *  normalization is implemented in "sortedness/order.icc"
00191      *    o  setting the lower bounds of the y_i domains (\lb E_i)
00192      *       to max(\lb E_{i-1},\lb E_i)
00193      *    o  setting the upper bounds of the y_i domains (\ub E_i)
00194      *       to min(\ub E_i,\ub E_{i+1})
00195      */
00196 
00197     if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00198       return ES_FAILED;
00199     }
00200 
00201     if (Perm) {
00202       // check consistency of channeling after normalization
00203       if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00204         return ES_FAILED;
00205       }
00206       if (nofix) {
00207         return ES_NOFIX;
00208       }
00209     }
00210 
00211 
00212     // if bounds have changed we have to recreate sigma to restore
00213     // optimized dropping of variables
00214 
00215     sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00216 
00217     bool subsumed   = true;
00218     bool array_subs = false;
00219     int  dropfst  = 0;
00220     bool noperm_bc = false;
00221 
00222     if (!(check_subsumption<View, Tuple, Perm>
00223           (home, xz, y, subsumed, dropfst)) ||
00224         !(array_assigned<View, Tuple, Perm>
00225           (home, xz, y, array_subs, match_fixed, nofix, noperm_bc))) {
00226       return ES_FAILED;
00227     }
00228 
00229     if (subsumed || array_subs) {
00230       return ES_SUBSUMED;
00231     }
00232 
00233 
00234     /*
00235      * STEP 2: creating tau
00236      * Sort the domains of the x variables according
00237      * to their lower bounds, where we use an
00238      * intermediate array of integers for sorting
00239      */
00240     sort_tau<View, Tuple, Perm>(xz, tau);
00241 
00242     /*
00243      * STEP 3:
00244      *  Compute the matchings \phi and \phi' between
00245      *  the x and the y variables
00246      *  with Glover's matching algorithm.
00247      *        o  phi is computed with the glover function
00248      *        o  phiprime is computed with the revglover function
00249      *  glover and revglover are implemented in "sortedness/matching.icc"
00250      */
00251 
00252     if (!match_fixed) {
00253       if (!glover<View, Tuple, Perm>
00254           (home, xz, y, tau, phi, sequence, vertices)) {
00255         return ES_FAILED;
00256       }
00257     } else {
00258       for (int i = xz.size(); i--; ) {
00259         phi[i]      = xz[i][1].val();
00260         phiprime[i] = phi[i];
00261       }
00262     }
00263 
00264     if(!yval) {
00265       // phiprime is not needed to narrow the domains of the x-variables
00266       if (!match_fixed) {
00267         if (!revglover<View, Tuple, Perm>
00268             (home, xz, y, tau, phiprime, sequence, vertices)) {
00269           return ES_FAILED;
00270         }
00271       }
00272 
00273       if (!narrow_domy<View, Tuple, Perm>
00274           (home, xz, y, phi, phiprime, nofix)) {
00275         return ES_FAILED;
00276       }
00277 
00278       if (nofix && !match_fixed) {
00279         // data structures (matching) destroyed by domains with holes
00280         
00281         for (int i = y.size(); i--; ) {
00282           phi[i] = 0;
00283           phiprime[i] = 0;
00284         }
00285         if (!glover<View, Tuple, Perm>
00286             (home, xz, y, tau, phi, sequence, vertices)) {
00287           return ES_FAILED;
00288         }
00289         
00290         if (!revglover<View, Tuple, Perm>
00291             (home, xz, y, tau, phiprime, sequence, vertices)) {
00292           return ES_FAILED;
00293         }
00294 
00295         if (!narrow_domy<View, Tuple, Perm>
00296             (home, xz, y, phi, phiprime, nofix)) {
00297           return ES_FAILED;
00298         }
00299       }
00300     }
00301 
00302     /*
00303      * STEP 4:
00304      *  Compute the strongly connected components in
00305      *  the oriented intersection graph
00306      *  the computation of the sccs is implemented in
00307      *  "sortedness/narrowing.icc" in the function narrow_domx
00308      */
00309 
00310     GECODE_AUTOARRAY(int,          scclist, n);
00311     GECODE_AUTOARRAY(SccComponent, sinfo  , n);
00312 
00313     for(int i = n; i--; ) {
00314       sinfo[i].left       = i;
00315       sinfo[i].right      = i;
00316       sinfo[i].rightmost  = i;
00317       sinfo[i].leftmost   = i;
00318     }
00319 
00320     computesccs<View>(home, xz, y, phi, sinfo, scclist);
00321 
00322     /*
00323      * STEP 5:
00324      *  Narrow the domains of the variables
00325      *  Also implemented in "sortedness/narrowing.icc"
00326      *  in the functions narrow_domx and narrow_domy
00327      */
00328 
00329     if (!narrow_domx<View, Tuple, Perm>
00330         (home, xz, y, tau, phi, scclist, sinfo, nofix)) {
00331       return ES_FAILED;
00332     }
00333 
00334     if (Perm) {
00335       if (!noperm_bc) {
00336         if (!perm_bc<View, Tuple, Perm>
00337             (home, tau, sinfo, scclist, xz, repairpass, nofix)) {
00338           return ES_FAILED;
00339         }
00340       }
00341 
00342       // channeling also needed after normal propagation steps
00343       // in order to ensure consistency after possible modification in perm_bc
00344       if (!channel<View, Tuple, Perm>(home, xz, y, nofix)) {
00345         return ES_FAILED;
00346       }
00347       if (nofix) {
00348         return ES_NOFIX;
00349       }
00350     }
00351 
00352     sort_tau<View, Tuple, Perm>(xz, tau);
00353 
00354     if (Perm) {
00355       // special case of sccs of size 2 denoted by permutation variables
00356       // used to enforce consistency from x to y
00357       // case of the upper bound ordering tau
00358       for (int i = xz.size() - 1; i--; ) {
00359         // two x variables are in the same scc of size 2
00360         if (xz[tau[i]][1].min() == xz[tau[i+1]][1].min() &&
00361             xz[tau[i]][1].max() == xz[tau[i+1]][1].max() &&
00362             xz[tau[i]][1].size() == 2 && xz[tau[i]][1].range()) {
00363           // if bounds are strictly smaller
00364           if (xz[tau[i]][0].max() < xz[tau[i+1]][0].max()) {
00365             ModEvent me = y[xz[tau[i]][1].min()].lq(home, xz[tau[i]][0].max());
00366             if (me_failed(me)) {
00367               return ES_FAILED;
00368             }
00369             nofix |= (y[xz[tau[i]][1].min()].modified() &&
00370                       y[xz[tau[i]][1].min()].max() != xz[tau[i]][0].max());
00371         
00372             me = y[xz[tau[i+1]][1].max()].lq(home, xz[tau[i+1]][0].max());
00373             if (me_failed(me)) {
00374               return ES_FAILED;
00375             }
00376             nofix |= (y[xz[tau[i+1]][1].max()].modified() &&
00377                       y[xz[tau[i+1]][1].max()].max() != xz[tau[i+1]][0].max());
00378           }
00379         }
00380       }
00381     }
00382     return nofix ? ES_NOFIX : ES_FIX;
00383   }
00384 
00385   template<class View, class Tuple, bool Perm>
00386   forceinline Sortedness<View, Tuple, Perm>::
00387   Sortedness(Space* home, bool share, Sortedness<View, Tuple, Perm>& p):
00388     Propagator(home, share, p),
00389     reachable(p.reachable) {
00390     xz.update(home, share, p.xz);
00391     y.update(home, share, p.y);
00392     w.update(home, share, p.w);
00393   }
00394 
00395   template<class View, class Tuple, bool Perm>
00396   Sortedness<View, Tuple, Perm>::
00397   Sortedness(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0):
00398     Propagator(home), xz(xz0), y(y0), w(home, y0), reachable(-1) {
00399     xz.subscribe(home, this, PC_INT_BND);
00400     y.subscribe(home, this, PC_INT_BND);
00401 
00402   }
00403 
00404   template<class View, class Tuple, bool Perm>
00405   size_t
00406   Sortedness<View, Tuple, Perm>::dispose(Space* home) {
00407     assert(!home->failed());
00408     xz.cancel(home,this, PC_INT_BND);
00409     y.cancel(home,this, PC_INT_BND);
00410     (void) Propagator::dispose(home);
00411     return sizeof(*this);
00412   }
00413 
00414   template<class View, class Tuple, bool Perm>
00415   Actor* Sortedness<View, Tuple, Perm>::copy(Space* home, bool share) {
00416     return new (home) Sortedness<View, Tuple, Perm>(home, share, *this);
00417   }
00418 
00419   template<class View, class Tuple, bool Perm>
00420   PropCost Sortedness<View, Tuple, Perm>::cost(void) const {
00421     return cost_hi(xz.size(), PC_LINEAR_HI);
00422   }
00423 
00424   template<class View, class Tuple, bool Perm>
00425   ExecStatus
00426   Sortedness<View, Tuple, Perm>::propagate(Space* home) {
00427 
00428     int  n           = xz.size();
00429     bool secondpass  = false;
00430     bool nofix       = false;
00431     int  dropfst     = 0;
00432 
00433     bool subsumed    = false;
00434     bool array_subs  = false;
00435     bool match_fixed = false;
00436 
00437     // normalization of x and y
00438     if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00439       return ES_FAILED;
00440     }
00441 
00442     // create sigma sorting
00443     sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00444 
00445     bool noperm_bc = false;
00446     if (!array_assigned<View, Tuple, Perm>
00447         (home, xz, y, array_subs, match_fixed, nofix, noperm_bc)) {
00448       return ES_FAILED;
00449     }
00450 
00451     if (array_subs) {
00452       return ES_SUBSUMED;
00453     }
00454 
00455     sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00456 
00457     // in this case check_subsumptions is guaranteed to find
00458     // the xs ordered by sigma
00459 
00460     if (!check_subsumption<View, Tuple, Perm>
00461         (home, xz, y, subsumed, dropfst)) {
00462       return ES_FAILED;
00463     }
00464 
00465     if (subsumed) {
00466       return ES_SUBSUMED;
00467     }   
00468 
00469     if (Perm) {
00470       // dropping possibly yields inconsistent indices on permutation variables
00471       if (dropfst) {
00472         reachable = w[dropfst - 1].max();
00473         bool unreachable = true;
00474         for (int i = xz.size(); unreachable && i-- ; ) {
00475           unreachable &= (reachable < xz[i][0].min());
00476         }
00477 
00478         if (unreachable) {
00479           xz.drop_fst(dropfst, home, this, PC_INT_BND);
00480           y.drop_fst (dropfst, home, this, PC_INT_BND);
00481         } else {
00482           dropfst = 0;
00483         }
00484       }
00485 
00486       n = xz.size();
00487 
00488       if (n < 2) {
00489         if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00490           return ES_FAILED;
00491         } else {
00492           if (Perm) {
00493             GECODE_ME_CHECK(xz[0][1].eq(home, w.size() - 1));
00494           }
00495           Rel::EqBnd<View,View>::post(home, xz[0][0], y[0]);
00496           return ES_SUBSUMED;
00497 
00498         }
00499       }
00500 
00501       // check whether shifting the permutation variables
00502       // is necessary after dropping x and y vars
00503       // highest reachable index
00504       int  valid = n - 1;
00505       int  index = 0;
00506       int  shift = 0;
00507 
00508       for (int i = n; i--; ){
00509         if (xz[i][1].max() > index) {
00510           index = xz[i][1].max();
00511         }
00512         if (index > valid) {
00513           shift = index - valid;
00514         }
00515       }
00516 
00517       if (shift) {
00518         ViewArray<ViewTuple<OffsetView,2> > oxz(home, n);
00519         ViewArray<OffsetView> oy(home, n);
00520 
00521         for (int i = n; i--; ) {
00522 
00523           GECODE_ME_CHECK(xz[i][1].gq(home, shift));
00524 
00525           oxz[i][1] = OffsetView(xz[i][1], -shift);
00526           oxz[i][0] = OffsetView(xz[i][0], 0);
00527           oy[i] = OffsetView(y[i], 0);
00528         }
00529 
00530         GECODE_ES_CHECK((bounds_propagation<OffsetView,
00531                          ViewTuple<OffsetView,2>, Perm>
00532                          (home, oxz, oy, secondpass, nofix, match_fixed)));
00533 
00534         if (secondpass) {
00535           GECODE_ES_CHECK((bounds_propagation<OffsetView,
00536                            ViewTuple<OffsetView,2>, Perm>
00537                            (home, oxz, oy, secondpass, nofix, match_fixed)));
00538         }
00539       } else {
00540         GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00541                          (home, xz, y, secondpass, nofix, match_fixed)));
00542 
00543         if (secondpass) {
00544           GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00545                            (home, xz, y, secondpass, nofix, match_fixed)));
00546         }
00547       }
00548     } else {
00549       // dropping has no consequences
00550       if (dropfst) {
00551         xz.drop_fst(dropfst, home, this, PC_INT_BND);
00552         y.drop_fst (dropfst, home, this, PC_INT_BND);
00553       }
00554 
00555       n = xz.size();
00556 
00557       if (n < 2) {
00558         if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00559           return ES_FAILED;
00560         } else {
00561           Rel::EqBnd<View,View>::post(home, xz[0][0], y[0]);
00562           return ES_SUBSUMED;
00563         }
00564       }
00565       GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm>
00566                        (home, xz, y, secondpass, nofix, match_fixed)));
00567       // no second pass possible if there are no permvars
00568     }
00569 
00570     if (!normalize<View, Tuple>(home, y, xz, nofix)) {
00571       return ES_FAILED;
00572     }
00573 
00574     GECODE_AUTOARRAY(int, tau,      n);
00575     if (match_fixed) {
00576       // sorting is determined
00577       // sigma and tau coincide
00578       for (int i = xz.size(); i--; ) {
00579         int pi = xz[i][1].val();
00580         tau[pi] = i;
00581       }
00582     } else {
00583       for (int i = n; i--; ) {
00584         tau[i] = i;
00585       }
00586     }
00587 
00588     sort_tau<View, Tuple, Perm>(xz, tau);
00589     // recreate consistency for already assigned subparts
00590     // in order of the upper bounds starting at the end of the array
00591     bool xbassigned = true;
00592     for (int i = xz.size(); i--; ) {
00593       if (xz[tau[i]][0].assigned() && xbassigned) {
00594         ModEvent me = y[i].eq(home, xz[tau[i]][0].val());
00595         if (me_failed(me)) {
00596           return ES_FAILED;
00597         }
00598       } else {
00599         xbassigned = false;
00600       }
00601     }
00602 
00603     subsumed   = true;
00604     array_subs = false;
00605     noperm_bc  = false;
00606 
00607     // creating sorting anew
00608     sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00609 
00610     if (Perm) {
00611       for (int i = 0; i < xz.size() - 1; i++) {
00612         // special case of subsccs of size2 for the lower bounds
00613         // two x variables are in the same scc of size 2
00614         if (xz[i][1].min() == xz[i+1][1].min() &&
00615             xz[i][1].max() == xz[i+1][1].max() &&
00616             xz[i][1].size() == 2 && xz[i][1].range()) {
00617           if (xz[i][0].min() < xz[i+1][0].min()) {
00618             ModEvent me = y[xz[i][1].min()].gq(home, xz[i][0].min());
00619             if (me_failed(me)) {
00620               return ES_FAILED;
00621             }
00622             nofix |= (y[xz[i][1].min()].modified() &&
00623                       y[xz[i][1].min()].min() != xz[i][0].min());
00624 
00625             me = y[xz[i+1][1].max()].gq(home, xz[i+1][0].min());
00626             if (me_failed(me)) {
00627               return ES_FAILED;
00628             }
00629             nofix |= (y[xz[i+1][1].max()].modified() &&
00630                       y[xz[i+1][1].max()].min() != xz[i+1][0].min());
00631           }
00632         }
00633       }
00634     }
00635 
00636     // check assigned
00637     // should be sorted
00638     bool xassigned = true;
00639     for (int i = 0; i < xz.size(); i++) {
00640       if (xz[i][0].assigned() && xassigned) {
00641         ModEvent me = y[i].eq(home, xz[i][0].val());
00642         if (me_failed(me)) {
00643           return ES_FAILED;
00644         }
00645       } else {
00646         xassigned = false;
00647       }
00648     }
00649 
00650     // sorted check bounds
00651     // final check that variables are consitent with least and greatest possible
00652     // values
00653     int tlb = std::min(xz[0][0].min(), y[0].min());
00654     int tub = std::max(xz[xz.size() - 1][0].max(), y[y.size() - 1].max());
00655     for (int i = xz.size(); i--; ) {
00656       ModEvent me = y[i].lq(home, tub);
00657       if (me_failed(me)) {
00658         return ES_FAILED;
00659       }
00660       nofix |= y[i].modified() && y[i].max() != tub;
00661 
00662       me = y[i].gq(home, tlb);
00663       if (me_failed(me)) {
00664         return ES_FAILED;
00665       }
00666       nofix |= y[i].modified() && y[i].min() != tlb;
00667 
00668       me = xz[i][0].lq(home, tub);
00669       if (me_failed(me)) {
00670         return ES_FAILED;
00671       }
00672       nofix |= xz[i][0].modified() && xz[i][0].max() != tub;
00673 
00674       me = xz[i][0].gq(home, tlb);
00675       if (me_failed(me)) {
00676         return ES_FAILED;
00677       }
00678       nofix |= xz[i][0].modified() && xz[i][0].min() != tlb;
00679     }
00680 
00681     if (!array_assigned<View, Tuple, Perm>
00682         (home, xz, y, array_subs, match_fixed, nofix, noperm_bc)) {
00683       return ES_FAILED;
00684     }
00685 
00686     if (array_subs) {
00687       return ES_SUBSUMED;
00688     }
00689 
00690     if (!check_subsumption<View, Tuple, Perm>
00691         (home, xz, y, subsumed, dropfst)) {
00692       return ES_FAILED;
00693     }
00694 
00695     if (subsumed) {
00696       return ES_SUBSUMED;
00697     }
00698 
00699     return nofix ? ES_NOFIX : ES_FIX;
00700   }
00701 
00702   template<class View, class Tuple, bool Perm>
00703   ExecStatus
00704   Sortedness<View, Tuple, Perm>::
00705   post(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0) {
00706     int n = xz0.size();
00707     if (n < 2) {
00708       if ((xz0[0][0].max() < y0[0].min()) || (y0[0].max() < xz0[0][0].min())) {
00709         return ES_FAILED;
00710       } else {
00711         Rel::EqBnd<View,View>::post(home, xz0[0][0], y0[0]);
00712         if (Perm) {
00713           GECODE_ME_CHECK(xz0[0][1].eq(home, 0));
00714         }
00715       }
00716     } else {
00717       new (home) Sortedness<View, Tuple, Perm>(home, xz0, y0);
00718     }
00719     return ES_OK;
00720   }
00721 
00722 }}}
00723 
00724 // STATISTICS: int-prop
00725 
00726 
00727