gecode » set » int
channel-bool.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9878 $
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 Int {
00041 
00042   template<class View>
00043   template<class A>
00044   forceinline
00045   ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home,
00046                                                 ChannelBool<View>& p,
00047                                                 Council<A>& c, int index)
00048     : Advisor(home,p,c), idx(index) {
00049     if (idx == -1)
00050       p.y.subscribe(home,*this);
00051     else {
00052       p.x[idx].subscribe(home,*this);
00053     }
00054   }
00055 
00056   template<class View>
00057   forceinline
00058   ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home, bool share,
00059                                                 IndexAdvisor& a)
00060     : Advisor(home,share,a), idx(a.idx) {}
00061 
00062   template<class View>
00063   forceinline int
00064   ChannelBool<View>::IndexAdvisor::index(void) const {
00065     return idx;
00066   }
00067 
00068   template<class View>
00069   template<class A>
00070   forceinline void
00071   ChannelBool<View>::IndexAdvisor::dispose(Space& home, Council<A>& c) {
00072     ChannelBool<View>& p = static_cast<ChannelBool<View>&>(propagator());
00073     if (idx == -1)
00074       p.y.cancel(home,*this);
00075     else {
00076       p.x[idx].cancel(home,*this);
00077     }
00078     Advisor::dispose(home,c);
00079   }
00080 
00081   template<class View>
00082   forceinline
00083   ChannelBool<View>::ChannelBool(Home home,
00084                                  ViewArray<Gecode::Int::BoolView>& x0,
00085                                  View y0)
00086     : Super(home,x0,y0), co(home), running(false) {
00087       bool assigned = false;
00088       for (int i=x.size(); i--;) {
00089         if (x[i].zero()) {
00090           assigned = true;
00091           SetDelta d;
00092           zeros.include(home, i, i, d);
00093         } else if (x[i].one()) {
00094           assigned = true;
00095           SetDelta d;
00096           ones.include(home, i, i, d);
00097         } else {
00098           (void) new (home) IndexAdvisor(home,*this,co,i);
00099         }
00100       }
00101       if (assigned)
00102         Gecode::Int::BoolView::schedule(home, *this, Gecode::Int::ME_BOOL_VAL);
00103       View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
00104       (void) new (home) IndexAdvisor(home,*this,co,-1);
00105     }
00106 
00107   template<class View>
00108   forceinline
00109   ChannelBool<View>::ChannelBool(Space& home, bool share, ChannelBool& p)
00110     : Super(home,share,p), running(false) {
00111     co.update(home, share, p.co);
00112   }
00113 
00114   template<class View>
00115   forceinline ExecStatus
00116   ChannelBool<View>::post(Home home, ViewArray<Gecode::Int::BoolView>& x,
00117                           View y) {
00118     GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1));
00119     (void) new (home) ChannelBool(home,x,y);
00120     return ES_OK;
00121   }
00122 
00123   template<class View>
00124   PropCost
00125   ChannelBool<View>::cost(const Space&, const ModEventDelta&) const {
00126     return PropCost::quadratic(PropCost::LO, x.size()+1);
00127   }
00128 
00129   template<class View>
00130   size_t
00131   ChannelBool<View>::dispose(Space& home) {
00132     assert(!home.failed());
00133     co.dispose(home);
00134     (void) Super::dispose(home);
00135     return sizeof(*this);
00136   }
00137 
00138   template<class View>
00139   Actor*
00140   ChannelBool<View>::copy(Space& home, bool share) {
00141     return new (home) ChannelBool(home,share,*this);
00142   }
00143 
00144   template<class View>
00145   ExecStatus
00146   ChannelBool<View>::propagate(Space& home, const ModEventDelta&) {
00147     running = true;
00148     if (zeros.size() > 0) {
00149       BndSetRanges zi(zeros);
00150       GECODE_ME_CHECK(y.excludeI(home, zi));
00151       zeros.init(home);
00152     }
00153     if (ones.size() > 0) {
00154       BndSetRanges oi(ones);
00155       GECODE_ME_CHECK(y.includeI(home, oi));
00156       ones.init(home);
00157     }
00158     running = false;
00159 
00160     if (delta.glbMin() != 1 || delta.glbMax() != 0) {
00161       if (!delta.glbAny()) {
00162         for (int i=delta.glbMin(); i<=delta.glbMax(); i++)
00163           GECODE_ME_CHECK(x[i].one(home));
00164       } else {
00165         GlbRanges<View> glb(y);
00166         for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) {
00167           GECODE_ME_CHECK(x[gv.val()].one(home));
00168         }
00169       }
00170     }
00171     if (delta.lubMin() != 1 || delta.lubMax() != 0) {
00172       if (!delta.lubAny()) {
00173         for (int i=delta.lubMin(); i<=delta.lubMax(); i++)
00174           GECODE_ME_CHECK(x[i].zero(home));
00175       } else {
00176         int cur = 0;
00177         for (LubRanges<View> lub(y); lub(); ++lub) {
00178           for (; cur < lub.min(); cur++) {
00179             GECODE_ME_CHECK(x[cur].zero(home));
00180           }
00181           cur = lub.max() + 1;
00182         }
00183         for (; cur < x.size(); cur++) {
00184           GECODE_ME_CHECK(x[cur].zero(home));
00185         }
00186       }
00187     }
00188 
00189     new (&delta) SetDelta();
00190 
00191     return y.assigned() ? ES_SUBSUMED(*this,home) : ES_FIX;
00192   }
00193 
00194   template<class View>
00195   ExecStatus
00196   ChannelBool<View>::advise(Space& home, Advisor& _a, const Delta& _d) {
00197     IndexAdvisor& a = static_cast<IndexAdvisor&>(_a);
00198     const SetDelta& d = static_cast<const SetDelta&>(_d);
00199 
00200     ModEvent me = View::modevent(d);
00201     int index = a.index();
00202     if ( (running && index == -1 && me != ME_SET_VAL)
00203          || (index == -1 && me == ME_SET_CARD) ) {
00204       return ES_OK;
00205     }
00206 
00207     if (index >= 0) {
00208       if (x[index].zero()) {
00209         SetDelta dummy;
00210         zeros.include(home, index, index, dummy);
00211       } else {
00212         assert(x[index].one());
00213         SetDelta dummy;
00214         ones.include(home, index, index, dummy);
00215       }
00216       return ES_SUBSUMED_NOFIX(a, home, co);
00217     }
00218 
00219     if ((a.index() == -1) && Rel::testSetEventLB(me)) {
00220       if (d.glbAny()) {
00221         new (&delta)
00222           SetDelta(2,0, delta.lubMin(), delta.lubMax());
00223       } else {
00224         if (delta.glbMin() == 1 && delta.glbMax() == 0) {
00225           new (&delta)
00226             SetDelta(d.glbMin(), d.glbMax(),
00227                      delta.lubMin(), delta.lubMax());
00228         } else {
00229           if (delta.glbMin() != 2 || delta.glbMax() != 0) {
00230             if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin())
00231                 ||
00232                 (delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax())
00233                ) {
00234                  new (&delta)
00235                    SetDelta(std::min(delta.glbMin(), d.glbMin()),
00236                             std::max(delta.glbMax(), d.glbMax()),
00237                             delta.lubMin(), delta.lubMax());
00238             } else {
00239               new (&delta)
00240                 SetDelta(2, 0, delta.lubMin(), delta.lubMax());
00241             }
00242           }
00243         }
00244       }
00245     }
00246     if ((a.index() == -1) && Rel::testSetEventUB(me)) {
00247       if (d.lubAny()) {
00248         new (&delta)
00249           SetDelta(delta.glbMin(), delta.glbMax(), 2,0);
00250       } else {
00251         if (delta.lubMin() == 1 && delta.lubMax() == 0) {
00252           new (&delta)
00253             SetDelta(delta.glbMin(), delta.glbMax(),
00254                      d.lubMin(), d.lubMax());
00255         } else {
00256           if (delta.lubMin() != 2 || delta.lubMax() != 0) {
00257             if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin())
00258                 ||
00259                 (delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax())
00260                ) {
00261                  new (&delta)
00262                    SetDelta(delta.lubMin(), delta.lubMax(),
00263                             std::min(delta.lubMin(), d.lubMin()),
00264                             std::max(delta.lubMax(), d.lubMax())
00265                             );
00266             } else {
00267               new (&delta)
00268                 SetDelta(delta.glbMin(), delta.glbMax(), 2, 0);
00269             }
00270           }
00271         }
00272       }
00273     }
00274 
00275     if (y.assigned())
00276       return ES_SUBSUMED_NOFIX(a, home, co);
00277     else
00278       return ES_NOFIX;
00279   }
00280 
00281 }}}
00282 
00283 // STATISTICS: set-prop