Generated on Mon Nov 30 23:53:35 2009 for Gecode by doxygen 1.6.1

channel-int.hpp

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00015  *     $Revision: 9878 $
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(Home 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(Home 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(const Space&, const ModEventDelta&) const {
00091     return PropCost::quadratic(PropCost::LO, xs.size()+ys.size());
00092   }
00093 
00094   template<class View>
00095   size_t
00096   ChannelInt<View>::dispose(Space& home) {
00097     assert(!home.failed());
00098     xs.cancel(home,*this, Gecode::Int::PC_INT_DOM);
00099     ys.cancel(home,*this, PC_SET_ANY);
00100     (void) Propagator::dispose(home);
00101     return sizeof(*this);
00102   }
00103 
00104   template<class View>
00105   Actor*
00106   ChannelInt<View>::copy(Space& home, bool share) {
00107     return new (home) ChannelInt(home,share,*this);
00108   }
00109 
00110   template<class View>
00111   ExecStatus
00112   ChannelInt<View>::propagate(Space& home, const ModEventDelta&) {
00113     int assigned = 0;
00114     for (int v=xs.size(); v--;) {
00115       if (xs[v].assigned()) {
00116         assigned += 1;
00117         for (int i=ys.size(); i--;) {
00118           if (i==xs[v].val()) {
00119             GECODE_ME_CHECK(ys[i].include(home, v));
00120           }
00121           else {
00122             GECODE_ME_CHECK(ys[i].exclude(home, v));
00123           }
00124         }
00125       } else {
00126 
00127         for (int i=ys.size(); i--;) {
00128           if (ys[i].notContains(v)) {
00129             GECODE_ME_CHECK(xs[v].nq(home, i));
00130           }
00131           if (ys[i].contains(v)) {
00132             GECODE_ME_CHECK(xs[v].eq(home, i));
00133           }
00134         }
00135 
00136         Gecode::Int::ViewRanges<Gecode::Int::IntView> xsv(xs[v]);
00137         int min = 0;
00138         for (; xsv(); ++xsv) {
00139           for (int i=min; i<xsv.min(); i++) {
00140             GECODE_ME_CHECK(ys[i].exclude(home, v));
00141           }
00142           min = xsv.max() + 1;
00143         }
00144 
00145       }
00146     }
00147 
00148     return (assigned==xs.size()) ? ES_SUBSUMED(*this,home) : ES_NOFIX;
00149   }
00150 
00151 }}}
00152 
00153 // STATISTICS: set-prop