Generated on Thu Apr 11 13:59:08 2019 for Gecode by doxygen 1.6.3

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  *  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 #include <gecode/int.hh>
00039 
00040 namespace Gecode { namespace Set { namespace Channel {
00041 
00042   template<class View>
00043   forceinline
00044   ChannelInt<View>::ChannelInt(Home home,
00045                                ViewArray<Gecode::Int::CachedView<
00046                                 Gecode::Int::IntView> >& xs0,
00047                                ViewArray<CachedView<View> >& ys0)
00048     : Propagator(home), xs(xs0), ys(ys0) {
00049     for (int i=xs.size(); i--;)
00050       xs[i].initCache(home,IntSet(0,ys.size()-1));
00051     for (int i=ys.size(); i--;)
00052       ys[i].initCache(home,IntSet::empty,IntSet(0,xs.size()-1));
00053     xs.subscribe(home,*this, Gecode::Int::PC_INT_DOM);
00054     ys.subscribe(home,*this, PC_SET_ANY);
00055   }
00056 
00057   template<class View>
00058   forceinline
00059   ChannelInt<View>::ChannelInt(Space& home, ChannelInt& p)
00060     : Propagator(home,p) {
00061     xs.update(home,p.xs);
00062     ys.update(home,p.ys);
00063   }
00064 
00065   template<class View>
00066   forceinline ExecStatus
00067   ChannelInt<View>::post(Home home,
00068                          ViewArray<Gecode::Int::CachedView<
00069                           Gecode::Int::IntView> >& xs,
00070                          ViewArray<CachedView<View> >& ys) {
00071     // Sharing of ys is taken care of in the propagator:
00072     // The ys are propagated to be disjoint, so shared variables
00073     // result in failure.
00074     int xssize = xs.size();
00075     for (int i=ys.size(); i--;) {
00076       GECODE_ME_CHECK(ys[i].exclude(home, xssize, Limits::max));
00077       GECODE_ME_CHECK(ys[i].exclude(home, Limits::min, -1));
00078     }
00079     int yssize = ys.size();
00080     if (yssize > Gecode::Int::Limits::max)
00081       return ES_FAILED;
00082     for (int i=xs.size(); i--;) {
00083       GECODE_ME_CHECK(xs[i].gq(home, 0));
00084       GECODE_ME_CHECK(xs[i].le(home, static_cast<int>(yssize)));
00085     }
00086 
00087     (void) new (home) ChannelInt(home,xs,ys);
00088     return ES_OK;
00089   }
00090 
00091   template<class View>
00092   PropCost
00093   ChannelInt<View>::cost(const Space&, const ModEventDelta&) const {
00094     return PropCost::quadratic(PropCost::LO, xs.size()+ys.size());
00095   }
00096 
00097   template<class View>
00098   void
00099   ChannelInt<View>::reschedule(Space& home) {
00100     xs.reschedule(home,*this, Gecode::Int::PC_INT_DOM);
00101     ys.reschedule(home,*this, PC_SET_ANY);
00102   }
00103 
00104   template<class View>
00105   forceinline size_t
00106   ChannelInt<View>::dispose(Space& home) {
00107     xs.cancel(home,*this, Gecode::Int::PC_INT_DOM);
00108     ys.cancel(home,*this, PC_SET_ANY);
00109     (void) Propagator::dispose(home);
00110     return sizeof(*this);
00111   }
00112 
00113   template<class View>
00114   Actor*
00115   ChannelInt<View>::copy(Space& home) {
00116     return new (home) ChannelInt(home,*this);
00117   }
00118 
00119   template<class View>
00120   ExecStatus
00121   ChannelInt<View>::propagate(Space& home, const ModEventDelta&) {
00122     int assigned = 0;
00123     for (int v=xs.size(); v--;) {
00124       if (xs[v].assigned()) {
00125         assigned++;
00126         if (xs[v].modified())
00127           GECODE_ME_CHECK(ys[xs[v].val()].include(home,v));
00128       }
00129       if (xs[v].modified()) {
00130         Gecode::Int::ViewDiffRanges<Gecode::Int::IntView> d(xs[v]);
00131         Iter::Ranges::ToValues<Gecode::Int::ViewDiffRanges<
00132           Gecode::Int::IntView> > dv(d);
00133         for (; dv(); ++dv)
00134           GECODE_ME_CHECK(ys[dv.val()].exclude(home, v));
00135         xs[v].cache(home);
00136       }
00137     }
00138 
00139     for (int i=ys.size(); i--;) {
00140       if (ys[i].glbModified()) {
00141         GlbDiffRanges<View> yilb(ys[i]);
00142         Iter::Ranges::ToValues<GlbDiffRanges<View> > dv(yilb);
00143         for (;dv();++dv)
00144           GECODE_ME_CHECK(xs[dv.val()].eq(home,i));
00145         ys[i].cacheGlb(home);
00146       }
00147       if (ys[i].lubModified()) {
00148         LubDiffRanges<View> yiub(ys[i]);
00149         Iter::Ranges::ToValues<LubDiffRanges<View> > dv(yiub);
00150         for (;dv();++dv)
00151           GECODE_ME_CHECK(xs[dv.val()].nq(home,i));
00152         ys[i].cacheLub(home);
00153       }
00154     }
00155 
00156     return (assigned==xs.size()) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00157   }
00158 
00159 }}}
00160 
00161 // STATISTICS: set-prop