Generated on Wed Mar 19 07:30:00 2008 for Gecode by doxygen 1.5.5

lex.icc

Go to the documentation of this file.
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: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00011  *     $Revision: 6017 $
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(Space* home,
00043                  ViewArray<ViewTuple<View,2> >& xy, bool s)
00044     : NaryPropagator<ViewTuple<View,2>,PC_INT_BND>(home,xy), strict(s) {}
00045 
00046   template <class View>
00047   forceinline
00048   Lex<View>::Lex(Space* home, bool share, Lex<View>& p)
00049     : NaryPropagator<ViewTuple<View,2>,PC_INT_BND>(home,share,p),
00050       strict(p.strict) {}
00051 
00052   template <class View>
00053   Actor*
00054   Lex<View>::copy(Space* home, bool share) {
00055     return new (home) Lex<View>(home,share,*this);
00056   }
00057 
00058   template <class View>
00059   inline Support::Symbol
00060   Lex<View>::ati(void) {
00061     return Reflection::mangle<View>("Gecode::Int::Rel::Lex");
00062   }
00063 
00064   template <class View>
00065   Reflection::ActorSpec
00066   Lex<View>::spec(const Space* home, Reflection::VarMap& m) const {
00067     return NaryPropagator<ViewTuple<View,2>,PC_INT_BND>
00068       ::spec(home, m, ati()) << strict;
00069   }
00070 
00071   template <class View>
00072   void
00073   Lex<View>::post(Space* home, Reflection::VarMap& vars,
00074   const Reflection::ActorSpec& spec) {
00075     spec.checkArity(2);
00076     ViewArray<ViewTuple<View,2> > x(home, vars, spec[0]);
00077     bool strict = spec[1]->toInt();
00078     (void) new (home) Lex<View>(home, x, strict);
00079   }
00080 
00081   template <class View>
00082   ExecStatus
00083   Lex<View>::propagate(Space* home, ModEventDelta) {
00084     /*
00085      * State 1
00086      *
00087      */
00088     {
00089       int i = 0;
00090       int n = x.size();
00091 
00092       while ((i < n) && (x[i][0].min() == x[i][1].max())) {
00093         // case: =, >=
00094         GECODE_ME_CHECK(x[i][0].lq(home,x[i][1].max()));
00095         GECODE_ME_CHECK(x[i][1].gq(home,x[i][0].min()));
00096         i++;
00097       }
00098 
00099       if (i == n) // case: $
00100         return strict ? ES_FAILED : ES_SUBSUMED(this,sizeof(*this));
00101 
00102       // Possible cases left: <, <=, > (yields failure), ?
00103       GECODE_ME_CHECK(x[i][0].lq(home,x[i][1].max()));
00104       GECODE_ME_CHECK(x[i][1].gq(home,x[i][0].min()));
00105 
00106       if (x[i][0].max() < x[i][1].min()) // case: < (after tell)
00107         return ES_SUBSUMED(this,home);
00108 
00109       // x[i][0] can never be equal to x[i][1] (otherwise: >=)
00110       assert(!(x[i][0].assigned() && x[i][1].assigned() &&
00111                x[i][0].val() == x[i][1].val()));
00112       // Remove all elements between 0...i-1 as they are assigned and equal
00113       x.drop_fst(i);
00114       // After this, execution continues at [1]
00115     }
00116 
00117     /*
00118      * State 2
00119      *   prefix: (?|<=)
00120      *
00121      */
00122     {
00123       int i = 1;
00124       int n = x.size();
00125 
00126       while ((i < n) &&
00127              (x[i][0].min() == x[i][1].max()) &&
00128              (x[i][0].max() == x[i][1].min())) { // case: =
00129         assert(x[i][0].assigned() && x[i][1].assigned() &&
00130                (x[i][0].val() == x[i][1].val()));
00131         i++;
00132       }
00133 
00134       if (i == n) { // case: $
00135         if (strict)
00136           goto rewrite_le;
00137         else
00138           goto rewrite_lq;
00139       }
00140 
00141       if (x[i][0].max() < x[i][1].min()) // case: <
00142         goto rewrite_lq;
00143 
00144       if (x[i][0].min() > x[i][1].max()) // case: >
00145         goto rewrite_le;
00146 
00147       if (i > 1) {
00148         // Remove equal elements [1...i-1], keep element [0]
00149         x[i-1]=x[0]; x.drop_fst(i-1);
00150       }
00151     }
00152 
00153     if (x[1][0].max() <= x[1][1].min()) {
00154       // case: <= (invariant: not =, <)
00155       /*
00156        * State 3
00157        *   prefix: (?|<=),<=
00158        *
00159        */
00160       int i = 2;
00161       int n = x.size();
00162 
00163       while ((i < n) && (x[i][0].max() == x[i][1].min())) // case: <=, =
00164         i++;
00165 
00166       if (i == n) { // case: $
00167         if (strict)
00168           return ES_FIX;
00169         else
00170           goto rewrite_lq;
00171       }
00172 
00173       if (x[i][0].max() < x[i][1].min()) // case: <
00174         goto rewrite_lq;
00175 
00176       if (x[i][0].min() > x[i][1].max()) { // case: >
00177         // Eliminate [i]...[n-1]
00178         for (int j=i; j<n; j++)
00179           x[j].cancel(home,this,PC_INT_BND);
00180         x.size(i);
00181         strict = true;
00182       }
00183 
00184       return ES_FIX;
00185     }
00186 
00187     if (x[1][0].min() >= x[1][1].max()) {
00188       // case: >= (invariant: not =, >)
00189       /*
00190        * State 4
00191        *   prefix: (?|<=) >=
00192        *
00193        */
00194       int i = 2;
00195       int n = x.size();
00196 
00197       while ((i < n) && (x[i][0].min() == x[i][1].max()))
00198         // case: >=, =
00199         i++;
00200 
00201       if (i == n) { // case: $
00202         if (strict)
00203           goto rewrite_le;
00204         else
00205           return ES_FIX;
00206       }
00207 
00208       if (x[i][0].min() > x[i][1].max()) // case: >
00209         goto rewrite_le;
00210 
00211       if (x[i][0].max() < x[i][1].min()) { // case: <
00212         // Eliminate [i]...[n-1]
00213         for (int j=i; j<n; j++)
00214           x[j].cancel(home,this,PC_INT_BND);
00215         x.size(i);
00216         strict = false;
00217       }
00218 
00219       return ES_FIX;
00220     }
00221 
00222     return ES_FIX;
00223 
00224   rewrite_le:
00225     GECODE_REWRITE(this,Le<View>::post(home,x[0][0],x[0][1]));
00226   rewrite_lq:
00227     GECODE_REWRITE(this,Lq<View>::post(home,x[0][0],x[0][1]));
00228   }
00229 
00230   template <class View>
00231   ExecStatus
00232   Lex<View>::post(Space* home,
00233                   ViewArray<ViewTuple<View,2> >& xy, bool strict){
00234     if (xy.size() == 0)
00235       return strict ? ES_FAILED : ES_OK;
00236     if (xy.size() == 1)
00237       if (strict)
00238         return Le<View>::post(home,xy[0][0],xy[0][1]);
00239       else
00240         return Lq<View>::post(home,xy[0][0],xy[0][1]);
00241     (void) new (home) Lex<View>(home,xy,strict);
00242     return ES_OK;
00243   }
00244 
00245 }}}
00246 
00247 // STATISTICS: int-prop
00248