Generated on Fri Oct 19 11:24:57 2018 for Gecode by doxygen 1.6.3

nq.hpp

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, 2004
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <algorithm>
00035 
00036 namespace Gecode { namespace Int { namespace Rel {
00037 
00038   /*
00039    * Disequality
00040    *
00041    */
00042   template<class V0, class V1>
00043   forceinline
00044   Nq<V0,V1>::Nq(Home home, V0 x0, V1 x1)
00045     : MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>(home,x0,x1) {}
00046 
00047   template<class V0, class V1>
00048   ExecStatus
00049   Nq<V0,V1>::post(Home home, V0 x0, V1 x1){
00050     if (x0.assigned()) {
00051       GECODE_ME_CHECK(x1.nq(home,x0.val()));
00052     } else if (x1.assigned()) {
00053       GECODE_ME_CHECK(x0.nq(home,x1.val()));
00054     } else if (x0 == x1) {
00055       return ES_FAILED;
00056     } else {
00057       (void) new (home) Nq<V0,V1>(home,x0,x1);
00058     }
00059     return ES_OK;
00060   }
00061 
00062   template<class V0, class V1>
00063   forceinline
00064   Nq<V0,V1>::Nq(Space& home, Nq<V0,V1>& p)
00065     : MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>(home,p) {}
00066 
00067   template<class V0, class V1>
00068   Actor*
00069   Nq<V0,V1>::copy(Space& home) {
00070     return new (home) Nq<V0,V1>(home,*this);
00071   }
00072 
00073   template<class V0, class V1>
00074   PropCost
00075   Nq<V0,V1>::cost(const Space&, const ModEventDelta&) const {
00076     return PropCost::unary(PropCost::LO);
00077   }
00078 
00079   template<class V0, class V1>
00080   ExecStatus
00081   Nq<V0,V1>::propagate(Space& home, const ModEventDelta&) {
00082     if (x0.assigned()) {
00083       GECODE_ME_CHECK(x1.nq(home,x0.val()));
00084     } else {
00085       GECODE_ME_CHECK(x0.nq(home,x1.val()));
00086     }
00087     return home.ES_SUBSUMED(*this);
00088   }
00089 
00090 
00091   /*
00092    * Nary disequality propagator
00093    */
00094   template<class View>
00095   forceinline
00096   NaryNq<View>::NaryNq(Home home, ViewArray<View>& x)
00097     : NaryPropagator<View,PC_INT_VAL>(home,x) {}
00098 
00099   template<class View>
00100   PropCost
00101   NaryNq<View>::cost(const Space&, const ModEventDelta&) const {
00102     return PropCost::linear(PropCost::LO,x.size());
00103   }
00104 
00105   template<class View>
00106   forceinline
00107   NaryNq<View>::NaryNq(Space& home, NaryNq<View>& p)
00108     : NaryPropagator<View,PC_INT_VAL>(home,p) {}
00109 
00110   template<class View>
00111   Actor*
00112   NaryNq<View>::copy(Space& home) {
00113     return new (home) NaryNq<View>(home,*this);
00114   }
00115 
00116   template<class View>
00117   inline ExecStatus
00118   NaryNq<View>::post(Home home, ViewArray<View>& x) {
00119     x.unique();
00120     // Try to find an assigned view
00121     int n = x.size();
00122     if (n <= 1)
00123       return ES_FAILED;
00124     for (int i=n; i--; )
00125       if (x[i].assigned()) {
00126         std::swap(x[0],x[i]);
00127         break;
00128       }
00129     if (x[0].assigned()) {
00130       int v = x[0].val();
00131       // Eliminate all equal views and possibly find disequal view
00132       for (int i=n-1; i>0; i--)
00133         if (!x[i].in(v)) {
00134           return ES_OK;
00135         } else if (x[i].assigned()) {
00136           assert(x[i].val() == v);
00137           x[i]=x[--n];
00138         }
00139       x.size(n);
00140     }
00141     if (n == 1)
00142       return ES_FAILED;
00143     if (n == 2)
00144       return Nq<View,View>::post(home,x[0],x[1]);
00145     (void) new (home) NaryNq(home,x);
00146     return ES_OK;
00147   }
00148 
00149   template<class View>
00150   forceinline size_t
00151   NaryNq<View>::dispose(Space& home) {
00152     (void) NaryPropagator<View,PC_INT_VAL>::dispose(home);
00153     return sizeof(*this);
00154   }
00155 
00156   template<class View>
00157   ExecStatus
00158   NaryNq<View>::propagate(Space& home, const ModEventDelta&) {
00159     // Make sure that x[0] is assigned
00160     if (!x[0].assigned()) {
00161       // Note that there is at least one assigned view
00162       for (int i=1; true; i++)
00163         if (x[i].assigned()) {
00164           std::swap(x[0],x[i]);
00165           break;
00166         }
00167     }
00168     int v = x[0].val();
00169     int n = x.size();
00170     for (int i=n-1; i>0; i--)
00171       if (!x[i].in(v)) {
00172         x.size(n);
00173         return home.ES_SUBSUMED(*this);
00174       } else if (x[i].assigned()) {
00175         assert(x[i].val() == v);
00176         x[i] = x[--n];
00177       }
00178     x.size(n);
00179     if (n == 1)
00180       return ES_FAILED;
00181     if (n == 2) {
00182       GECODE_ME_CHECK(x[1].nq(home,v));
00183       return home.ES_SUBSUMED(*this);
00184     }
00185     return ES_FIX;
00186   }
00187 
00188 
00189 
00190 }}}
00191 
00192 // STATISTICS: int-prop