Generated on Mon May 5 05:53:58 2008 for Gecode by doxygen 1.5.5

propagate.icc

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