gecode » int » rel
lex.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-14 12:19:49 +0200 (Wed, 14 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9909 $
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 namespace Gecode { namespace Int { namespace Rel {
00039 
00040   template<class View>
00041   inline
00042   Lex<View>::Lex(Home home,
00043                  ViewArray<View>& x0, ViewArray<View>& y0, bool s)
00044     : Propagator(home), x(x0), y(y0), strict(s) {
00045     x.subscribe(home, *this, PC_INT_BND);
00046     y.subscribe(home, *this, PC_INT_BND);
00047   }
00048 
00049   template<class View>
00050   forceinline
00051   Lex<View>::Lex(Space& home, bool share, Lex<View>& p)
00052     : Propagator(home,share,p), strict(p.strict) {
00053     x.update(home,share,p.x);
00054     y.update(home,share,p.y);
00055   }
00056 
00057   template<class View>
00058   Actor*
00059   Lex<View>::copy(Space& home, bool share) {
00060     return new (home) Lex<View>(home,share,*this);
00061   }
00062 
00063   template<class View>
00064   PropCost
00065   Lex<View>::cost(const Space&, const ModEventDelta&) const {
00066     return PropCost::linear(PropCost::LO, x.size());
00067   }
00068 
00069   template<class View>
00070   ExecStatus
00071   Lex<View>::propagate(Space& home, const ModEventDelta&) {
00072     /*
00073      * State 1
00074      *
00075      */
00076     {
00077       int i = 0;
00078       int n = x.size();
00079 
00080       while ((i < n) && (x[i].min() == y[i].max())) {
00081         // case: =, >=
00082         GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00083         GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00084         i++;
00085       }
00086 
00087       if (i == n) // case: $
00088         return strict ? ES_FAILED : ES_SUBSUMED(*this,sizeof(*this));
00089 
00090       // Possible cases left: <, <=, > (yields failure), ?
00091       GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00092       GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00093 
00094       if (x[i].max() < y[i].min()) // case: < (after tell)
00095         return ES_SUBSUMED(*this,home);
00096 
00097       // x[i] can never be equal to y[i] (otherwise: >=)
00098       assert(!(x[i].assigned() && y[i].assigned() &&
00099                x[i].val() == y[i].val()));
00100       // Remove all elements between 0...i-1 as they are assigned and equal
00101       x.drop_fst(i); y.drop_fst(i);
00102       // After this, execution continues at [1]
00103     }
00104 
00105     /*
00106      * State 2
00107      *   prefix: (?|<=)
00108      *
00109      */
00110     {
00111       int i = 1;
00112       int n = x.size();
00113 
00114       while ((i < n) &&
00115              (x[i].min() == y[i].max()) &&
00116              (x[i].max() == y[i].min())) { // case: =
00117         assert(x[i].assigned() && y[i].assigned() &&
00118                (x[i].val() == y[i].val()));
00119         i++;
00120       }
00121 
00122       if (i == n) { // case: $
00123         if (strict)
00124           goto rewrite_le;
00125         else
00126           goto rewrite_lq;
00127       }
00128 
00129       if (x[i].max() < y[i].min()) // case: <
00130         goto rewrite_lq;
00131 
00132       if (x[i].min() > y[i].max()) // case: >
00133         goto rewrite_le;
00134 
00135       if (i > 1) {
00136         // Remove equal elements [1...i-1], keep element [0]
00137         x[i-1]=x[0]; x.drop_fst(i-1);
00138         y[i-1]=y[0]; y.drop_fst(i-1);
00139       }
00140     }
00141 
00142     if (x[1].max() <= y[1].min()) {
00143       // case: <= (invariant: not =, <)
00144       /*
00145        * State 3
00146        *   prefix: (?|<=),<=
00147        *
00148        */
00149       int i = 2;
00150       int n = x.size();
00151 
00152       while ((i < n) && (x[i].max() == y[i].min())) // case: <=, =
00153         i++;
00154 
00155       if (i == n) { // case: $
00156         if (strict)
00157           return ES_FIX;
00158         else
00159           goto rewrite_lq;
00160       }
00161 
00162       if (x[i].max() < y[i].min()) // case: <
00163         goto rewrite_lq;
00164 
00165       if (x[i].min() > y[i].max()) { // case: >
00166         // Eliminate [i]...[n-1]
00167         for (int j=i; j<n; j++) {
00168           x[j].cancel(home,*this,PC_INT_BND);
00169           y[j].cancel(home,*this,PC_INT_BND);
00170         }
00171         x.size(i); y.size(i);
00172         strict = true;
00173       }
00174 
00175       return ES_FIX;
00176     }
00177 
00178     if (x[1].min() >= y[1].max()) {
00179       // case: >= (invariant: not =, >)
00180       /*
00181        * State 4
00182        *   prefix: (?|<=) >=
00183        *
00184        */
00185       int i = 2;
00186       int n = x.size();
00187 
00188       while ((i < n) && (x[i].min() == y[i].max()))
00189         // case: >=, =
00190         i++;
00191 
00192       if (i == n) { // case: $
00193         if (strict)
00194           goto rewrite_le;
00195         else
00196           return ES_FIX;
00197       }
00198 
00199       if (x[i].min() > y[i].max()) // case: >
00200         goto rewrite_le;
00201 
00202       if (x[i].max() < y[i].min()) { // case: <
00203         // Eliminate [i]...[n-1]
00204         for (int j=i; j<n; j++) {
00205           x[j].cancel(home,*this,PC_INT_BND);
00206           y[j].cancel(home,*this,PC_INT_BND);
00207         }
00208         x.size(i); y.size(i);
00209         strict = false;
00210       }
00211 
00212       return ES_FIX;
00213     }
00214 
00215     return ES_FIX;
00216 
00217   rewrite_le:
00218     GECODE_REWRITE(*this,Le<View>::post(home(*this),x[0],y[0]));
00219   rewrite_lq:
00220     GECODE_REWRITE(*this,Lq<View>::post(home(*this),x[0],y[0]));
00221   }
00222 
00223   template<class View>
00224   ExecStatus
00225   Lex<View>::post(Home home,
00226                   ViewArray<View>& x, ViewArray<View>& y, bool strict){
00227     if (x.size() == 0)
00228       return strict ? ES_FAILED : ES_OK;
00229     if (x.size() == 1) {
00230       if (strict)
00231         return Le<View>::post(home,x[0],y[0]);
00232       else
00233         return Lq<View>::post(home,x[0],y[0]);
00234     }
00235     (void) new (home) Lex<View>(home,x,y,strict);
00236     return ES_OK;
00237   }
00238 
00239   template<class View>
00240   size_t
00241   Lex<View>::dispose(Space& home) {
00242     assert(!home.failed());
00243     x.cancel(home,*this,PC_INT_BND);
00244     y.cancel(home,*this,PC_INT_BND);
00245     (void) Propagator::dispose(home);
00246     return sizeof(*this);
00247   }
00248 
00249 }}}
00250 
00251 // STATISTICS: int-prop