Generated on Thu Mar 22 10:39:35 2012 for Gecode by doxygen 1.6.3

dom.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, 2007
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-09-06 14:19:49 +0200 (Tue, 06 Sep 2011) $ by $Author: schulte $
00011  *     $Revision: 12393 $
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 Circuit {
00039 
00040   /*
00041    * The actual propagator
00042    *
00043    */
00044   template<class View, class Offset>
00045   forceinline
00046   Dom<View,Offset>::Dom(Home home, ViewArray<View>& x, Offset& o)
00047     : Base<View,Offset>(home,x,o) {}
00048 
00049   template<class View, class Offset>
00050   forceinline
00051   Dom<View,Offset>::Dom(Space& home, bool share, Dom<View,Offset>& p)
00052     : Base<View,Offset>(home,share,p) {}
00053 
00054   template<class View, class Offset>
00055   Actor*
00056   Dom<View,Offset>::copy(Space& home, bool share) {
00057     return new (home) Dom<View,Offset>(home,share,*this);
00058   }
00059 
00060   template<class View, class Offset>
00061   PropCost
00062   Dom<View,Offset>::cost(const Space&, const ModEventDelta& med) const {
00063     if (View::me(med) == Int::ME_INT_VAL)
00064       return PropCost::linear(PropCost::LO, x.size());
00065     else
00066       return PropCost::quadratic(PropCost::HI, x.size());
00067   }
00068 
00069   template<class View, class Offset>
00070   ExecStatus
00071   Dom<View,Offset>::propagate(Space& home, const ModEventDelta& med) {
00072     if (View::me(med) == Int::ME_INT_VAL) {
00073       GECODE_ES_CHECK((Int::Distinct::prop_val<View,true>(home,y)));
00074       ExecStatus escv = connected(home);
00075       if (escv != ES_FIX)
00076         return escv;
00077       if (y.size() < 2)
00078         return home.ES_SUBSUMED(*this);
00079       return home.ES_FIX_PARTIAL(*this,View::med(Int::ME_INT_DOM));
00080     }
00081 
00082     if (dc.available()) {
00083       GECODE_ES_CHECK(dc.sync(home));
00084     } else {
00085       GECODE_ES_CHECK(dc.init(home,y));
00086     }
00087     bool assigned;
00088     GECODE_ES_CHECK(dc.propagate(home,assigned));
00089 
00090     ExecStatus esc = connected(home);
00091     if (esc != ES_FIX)
00092       return esc;
00093 
00094     // Elminiate assigned views from y, as they have been assigned
00095     // and propagated by domain consistent propagation. This is required
00096     // as we need to know how many assigned views actually exist.
00097     if (assigned)
00098       for (int i=y.size(); i--; )
00099         if (y[i].assigned())
00100           y.move_lst(i);
00101 
00102     return path(home);
00103   }
00104 
00105   template<class View, class Offset>
00106   ExecStatus
00107   Dom<View,Offset>::post(Home home, ViewArray<View>& x, Offset& o) {
00108     int n = x.size();
00109     if (n == 1) {
00110       GECODE_ME_CHECK(o(x[0]).eq(home,0));
00111     } else if (n == 2) {
00112       GECODE_ME_CHECK(o(x[0]).eq(home,1));
00113       GECODE_ME_CHECK(o(x[1]).eq(home,0));
00114     } else {
00115       for (int i=n; i--; ) {
00116         GECODE_ME_CHECK(o(x[i]).gq(home,0));
00117         GECODE_ME_CHECK(o(x[i]).le(home,n));
00118         GECODE_ME_CHECK(o(x[i]).nq(home,i));
00119       }
00120       (void) new (home) Dom<View,Offset>(home,x,o);
00121     }
00122     return ES_OK;
00123   }
00124 
00125 }}}
00126 
00127 // STATISTICS: int-prop
00128