Generated on Tue May 22 09:40:05 2018 for Gecode by doxygen 1.6.3

bool.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  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int.hh>
00035 
00036 namespace Gecode { namespace Set { namespace Channel {
00037 
00038   template<class View>
00039   template<class A>
00040   forceinline
00041   ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home,
00042                                                 ChannelBool<View>& p,
00043                                                 Council<A>& c, int index)
00044     : Advisor(home,p,c), idx(index) {
00045     if (idx == -1)
00046       p.y.subscribe(home,*this);
00047     else {
00048       p.x[idx].subscribe(home,*this);
00049     }
00050   }
00051 
00052   template<class View>
00053   forceinline
00054   ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home, IndexAdvisor& a)
00055     : Advisor(home,a), idx(a.idx) {}
00056 
00057   template<class View>
00058   forceinline int
00059   ChannelBool<View>::IndexAdvisor::index(void) const {
00060     return idx;
00061   }
00062 
00063   template<class View>
00064   template<class A>
00065   forceinline void
00066   ChannelBool<View>::IndexAdvisor::dispose(Space& home, Council<A>& c) {
00067     ChannelBool<View>& p = static_cast<ChannelBool<View>&>(propagator());
00068     if (idx == -1)
00069       p.y.cancel(home,*this);
00070     else {
00071       p.x[idx].cancel(home,*this);
00072     }
00073     Advisor::dispose(home,c);
00074   }
00075 
00076   template<class View>
00077   forceinline
00078   ChannelBool<View>::ChannelBool(Home home,
00079                                  ViewArray<Gecode::Int::BoolView>& x0,
00080                                  View y0)
00081     : Super(home,x0,y0), co(home), running(false) {
00082       bool assigned = false;
00083       for (int i=x.size(); i--;) {
00084         if (x[i].zero()) {
00085           assigned = true;
00086           SetDelta d;
00087           zeros.include(home, i, i, d);
00088         } else if (x[i].one()) {
00089           assigned = true;
00090           SetDelta d;
00091           ones.include(home, i, i, d);
00092         } else {
00093           (void) new (home) IndexAdvisor(home,*this,co,i);
00094         }
00095       }
00096       if (assigned)
00097         Gecode::Int::BoolView::schedule(home, *this, Gecode::Int::ME_BOOL_VAL);
00098       View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
00099       if (y.assigned()) {
00100         if (y.glbSize()==static_cast<unsigned int>(y.glbMax()-y.glbMin()+1)) {
00101           new (&delta) SetDelta(y.glbMin(),y.glbMax(),1,0);
00102         } else {
00103           new (&delta) SetDelta(2,0,1,0);
00104         }
00105       }
00106       (void) new (home) IndexAdvisor(home,*this,co,-1);
00107     }
00108 
00109   template<class View>
00110   forceinline
00111   ChannelBool<View>::ChannelBool(Space& home, ChannelBool& p)
00112     : Super(home,p), running(false) {
00113     co.update(home, p.co);
00114   }
00115 
00116   template<class View>
00117   forceinline ExecStatus
00118   ChannelBool<View>::post(Home home, ViewArray<Gecode::Int::BoolView>& x,
00119                           View y) {
00120     GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1));
00121     (void) new (home) ChannelBool(home,x,y);
00122     return ES_OK;
00123   }
00124 
00125   template<class View>
00126   PropCost
00127   ChannelBool<View>::cost(const Space&, const ModEventDelta&) const {
00128     return PropCost::quadratic(PropCost::LO, x.size()+1);
00129   }
00130 
00131   template<class View>
00132   void
00133   ChannelBool<View>::reschedule(Space& home) {
00134     x.reschedule(home,*this,Gecode::Int::PC_BOOL_VAL);
00135     View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
00136   }
00137 
00138   template<class View>
00139   forceinline size_t
00140   ChannelBool<View>::dispose(Space& home) {
00141     co.dispose(home);
00142     (void) Super::dispose(home);
00143     return sizeof(*this);
00144   }
00145 
00146   template<class View>
00147   Actor*
00148   ChannelBool<View>::copy(Space& home) {
00149     return new (home) ChannelBool(home,*this);
00150   }
00151 
00152   template<class View>
00153   ExecStatus
00154   ChannelBool<View>::propagate(Space& home, const ModEventDelta&) {
00155     running = true;
00156     if (zeros.size() > 0) {
00157       BndSetRanges zi(zeros);
00158       GECODE_ME_CHECK(y.excludeI(home, zi));
00159       zeros.init(home);
00160     }
00161     if (ones.size() > 0) {
00162       BndSetRanges oi(ones);
00163       GECODE_ME_CHECK(y.includeI(home, oi));
00164       ones.init(home);
00165     }
00166     running = false;
00167 
00168     if (delta.glbMin() != 1 || delta.glbMax() != 0) {
00169       if (!delta.glbAny()) {
00170         for (int i=delta.glbMin(); i<=delta.glbMax(); i++)
00171           GECODE_ME_CHECK(x[i].one(home));
00172       } else {
00173         GlbRanges<View> glb(y);
00174         for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) {
00175           GECODE_ME_CHECK(x[gv.val()].one(home));
00176         }
00177       }
00178     }
00179     if (delta.lubMin() != 1 || delta.lubMax() != 0) {
00180       if (!delta.lubAny()) {
00181         for (int i=delta.lubMin(); i<=delta.lubMax(); i++)
00182           GECODE_ME_CHECK(x[i].zero(home));
00183       } else {
00184         int cur = 0;
00185         for (LubRanges<View> lub(y); lub(); ++lub) {
00186           for (; cur < lub.min(); cur++) {
00187             GECODE_ME_CHECK(x[cur].zero(home));
00188           }
00189           cur = lub.max() + 1;
00190         }
00191         for (; cur < x.size(); cur++) {
00192           GECODE_ME_CHECK(x[cur].zero(home));
00193         }
00194       }
00195     }
00196 
00197     new (&delta) SetDelta();
00198 
00199     return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00200   }
00201 
00202   template<class View>
00203   ExecStatus
00204   ChannelBool<View>::advise(Space& home, Advisor& _a, const Delta& _d) {
00205     IndexAdvisor& a = static_cast<IndexAdvisor&>(_a);
00206     const SetDelta& d = static_cast<const SetDelta&>(_d);
00207 
00208     ModEvent me = View::modevent(d);
00209     int index = a.index();
00210     if ( (running && index == -1 && me != ME_SET_VAL)
00211          || (index == -1 && me == ME_SET_CARD) ) {
00212       return ES_OK;
00213     }
00214 
00215     if (index >= 0) {
00216       if (x[index].zero()) {
00217         SetDelta dummy;
00218         zeros.include(home, index, index, dummy);
00219       } else {
00220         assert(x[index].one());
00221         SetDelta dummy;
00222         ones.include(home, index, index, dummy);
00223       }
00224       return home.ES_NOFIX_DISPOSE( co, a);
00225     }
00226 
00227     if ((a.index() == -1) && Rel::testSetEventLB(me)) {
00228       if (d.glbAny()) {
00229         new (&delta)
00230           SetDelta(2,0, delta.lubMin(), delta.lubMax());
00231       } else {
00232         if (delta.glbMin() == 1 && delta.glbMax() == 0) {
00233           new (&delta)
00234             SetDelta(d.glbMin(), d.glbMax(),
00235                      delta.lubMin(), delta.lubMax());
00236         } else {
00237           if (delta.glbMin() != 2 || delta.glbMax() != 0) {
00238             if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin())
00239                 ||
00240                 (delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax())
00241                ) {
00242                  new (&delta)
00243                    SetDelta(std::min(delta.glbMin(), d.glbMin()),
00244                             std::max(delta.glbMax(), d.glbMax()),
00245                             delta.lubMin(), delta.lubMax());
00246             } else {
00247               new (&delta)
00248                 SetDelta(2, 0, delta.lubMin(), delta.lubMax());
00249             }
00250           }
00251         }
00252       }
00253     }
00254     if ((a.index() == -1) && Rel::testSetEventUB(me)) {
00255       if (d.lubAny()) {
00256         new (&delta)
00257           SetDelta(delta.glbMin(), delta.glbMax(), 2,0);
00258       } else {
00259         if (delta.lubMin() == 1 && delta.lubMax() == 0) {
00260           new (&delta)
00261             SetDelta(delta.glbMin(), delta.glbMax(),
00262                      d.lubMin(), d.lubMax());
00263         } else {
00264           if (delta.lubMin() != 2 || delta.lubMax() != 0) {
00265             if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin())
00266                 ||
00267                 (delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax())
00268                ) {
00269                  new (&delta)
00270                    SetDelta(delta.lubMin(), delta.lubMax(),
00271                             std::min(delta.lubMin(), d.lubMin()),
00272                             std::max(delta.lubMax(), d.lubMax())
00273                             );
00274             } else {
00275               new (&delta)
00276                 SetDelta(delta.glbMin(), delta.glbMax(), 2, 0);
00277             }
00278           }
00279         }
00280       }
00281     }
00282     if (y.assigned())
00283       return home.ES_NOFIX_DISPOSE( co, a);
00284     else
00285       return ES_NOFIX;
00286   }
00287 
00288 }}}
00289 
00290 // STATISTICS: set-prop