Generated on Mon Aug 25 11:35:43 2008 for Gecode by doxygen 1.5.6

channel-int.icc

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *     Gabor Szokoli <szokoli@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Guido Tack, 2004
00010  *     Christian Schulte, 2004
00011  *     Gabor Szokoli, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2008-02-06 18:48:22 +0100 (Wed, 06 Feb 2008) $ by $Author: schulte $
00015  *     $Revision: 6102 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #include "gecode/int.hh"
00043 
00044 namespace Gecode { namespace Set { namespace Int {
00045       
00046   template <class View>
00047   forceinline
00048   ChannelInt<View>::ChannelInt(Space* home, 
00049                              ViewArray<Gecode::Int::IntView>& xs0,
00050                              ViewArray<View>& ys0)
00051     : Propagator(home), xs(xs0), ys(ys0) {
00052     xs.subscribe(home,this, Gecode::Int::PC_INT_DOM);
00053     ys.subscribe(home,this, PC_SET_ANY);
00054   }
00055       
00056   template <class View>
00057   forceinline
00058   ChannelInt<View>::ChannelInt(Space* home, bool share, ChannelInt& p)
00059     : Propagator(home,share,p) {
00060     xs.update(home,share,p.xs);
00061     ys.update(home,share,p.ys);
00062   }
00063 
00064   template <class View>
00065   forceinline ExecStatus
00066   ChannelInt<View>::post(Space* home, ViewArray<Gecode::Int::IntView>& xs,
00067                           ViewArray<View>& ys) {
00068     // Sharing of ys is taken care of in the propagator:
00069     // The ys are propagated to be disjoint, so shared variables
00070     // result in failure.
00071     unsigned int xssize = xs.size();
00072     for (int i=ys.size(); i--;) {
00073       GECODE_ME_CHECK(ys[i].exclude(home, xssize, Limits::max));
00074       GECODE_ME_CHECK(ys[i].exclude(home, Limits::min, -1));
00075     }
00076     unsigned int yssize = ys.size();
00077     if (yssize > static_cast<unsigned int>(Gecode::Int::Limits::max))
00078       return ES_FAILED;
00079     for (int i=xs.size(); i--;) {
00080       GECODE_ME_CHECK(xs[i].gq(home, 0));
00081       GECODE_ME_CHECK(xs[i].le(home, static_cast<int>(yssize)));
00082     }
00083 
00084     (void) new (home) ChannelInt(home,xs,ys);
00085     return ES_OK;
00086   }
00087 
00088   template <class View>
00089   PropCost
00090   ChannelInt<View>::cost(ModEventDelta) const { return PC_QUADRATIC_LO; }
00091 
00092   template <class View>
00093   size_t
00094   ChannelInt<View>::dispose(Space* home) {
00095     assert(!home->failed());
00096     xs.cancel(home,this, Gecode::Int::PC_INT_DOM);
00097     ys.cancel(home,this, PC_SET_ANY);
00098     (void) Propagator::dispose(home);
00099     return sizeof(*this);
00100   }
00101 
00102   template <class View>
00103   Actor*
00104   ChannelInt<View>::copy(Space* home, bool share) {
00105     return new (home) ChannelInt(home,share,*this);
00106   }
00107 
00108   template <class View>
00109   ExecStatus
00110   ChannelInt<View>::propagate(Space* home, ModEventDelta) {
00111     int assigned = 0;
00112     for (int v=xs.size(); v--;) {
00113       if (xs[v].assigned()) {
00114         assigned += 1;
00115         for (int i=ys.size(); i--;) {
00116           if (i==xs[v].val()) {
00117             GECODE_ME_CHECK(ys[i].include(home, v));
00118           }
00119           else {
00120             GECODE_ME_CHECK(ys[i].exclude(home, v));
00121           }
00122         }
00123       } else {
00124 
00125         for (int i=ys.size(); i--;) {
00126           if (ys[i].notContains(v)) {
00127             GECODE_ME_CHECK(xs[v].nq(home, i));
00128           }
00129           if (ys[i].contains(v)) {
00130             GECODE_ME_CHECK(xs[v].eq(home, i));
00131           }
00132         }
00133 
00134         Gecode::Int::ViewRanges<Gecode::Int::IntView> xsv(xs[v]);
00135         int min = 0;
00136         for (; xsv(); ++xsv) {
00137           for (int i=min; i<xsv.min(); i++) {
00138             GECODE_ME_CHECK(ys[i].exclude(home, v));
00139           }
00140           min = xsv.max() + 1;
00141         }
00142 
00143       }
00144     }
00145 
00146     return (assigned==xs.size()) ? ES_SUBSUMED(this,home) : ES_NOFIX;
00147   }
00148 
00149   template <class View>
00150   Support::Symbol
00151   ChannelInt<View>::ati(void) {
00152     return Reflection::mangle<View>("Gecode::Set::Int::ChannelInt");
00153   }
00154 
00155   template <class View>
00156   Reflection::ActorSpec
00157   ChannelInt<View>::spec(const Space* home, Reflection::VarMap& m) const {
00158     Reflection::ActorSpec s(ati());
00159     return s << xs.spec(home, m) << ys.spec(home, m);
00160   }
00161 
00162   template <class View>
00163   void
00164   ChannelInt<View>::post(Space* home, Reflection::VarMap& vars,
00165                          const Reflection::ActorSpec& spec) {
00166     spec.checkArity(2);
00167     ViewArray<Gecode::Int::IntView> x0(home, vars, spec[0]);
00168     ViewArray<View> x1(home, vars, spec[1]);
00169     (void) new (home) ChannelInt<View>(home,x0,x1);
00170   }
00171 
00172 }}}
00173 
00174 // STATISTICS: set-prop