Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
13 kB · 470 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * * Copyright: * Christian Schulte, 2003 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
namespace Gecode { namespace Int { namespace Linear {
/* * Binary linear propagators * */ template<class Val, class A, class B, PropCond pc> forceinline LinBin<Val,A,B,pc>::LinBin(Home home, A y0, B y1, Val c0) : Propagator(home), x0(y0), x1(y1), c(c0) { x0.subscribe(home,*this,pc); x1.subscribe(home,*this,pc); }
template<class Val, class A, class B, PropCond pc> forceinline LinBin<Val,A,B,pc>::LinBin(Space& home, LinBin<Val,A,B,pc>& p) : Propagator(home,p), c(p.c) { x0.update(home,p.x0); x1.update(home,p.x1); }
template<class Val, class A, class B, PropCond pc> forceinline LinBin<Val,A,B,pc>::LinBin(Space& home, Propagator& p, A y0, B y1, Val c0) : Propagator(home,p), c(c0) { x0.update(home,y0); x1.update(home,y1); }
template<class Val, class A, class B, PropCond pc> PropCost LinBin<Val,A,B,pc>::cost(const Space&, const ModEventDelta&) const { return PropCost::binary(PropCost::LO); }
template<class Val, class A, class B, PropCond pc> void LinBin<Val,A,B,pc>::reschedule(Space& home) { x0.reschedule(home,*this,pc); x1.reschedule(home,*this,pc); }
template<class Val, class A, class B, PropCond pc> forceinline size_t LinBin<Val,A,B,pc>::dispose(Space& home) { x0.cancel(home,*this,pc); x1.cancel(home,*this,pc); (void) Propagator::dispose(home); return sizeof(*this); }
/* * Binary reified linear propagators * */ template<class Val, class A, class B, PropCond pc, class Ctrl> forceinline ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Home home, A y0, B y1, Val c0, Ctrl b0) : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) { x0.subscribe(home,*this,pc); x1.subscribe(home,*this,pc); b.subscribe(home,*this,PC_INT_VAL); }
template<class Val, class A, class B, PropCond pc, class Ctrl> forceinline ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space& home, ReLinBin<Val,A,B,pc,Ctrl>& p) : Propagator(home,p), c(p.c) { x0.update(home,p.x0); x1.update(home,p.x1); b.update(home,p.b); }
template<class Val, class A, class B, PropCond pc, class Ctrl> PropCost ReLinBin<Val,A,B,pc,Ctrl>::cost(const Space&, const ModEventDelta&) const { return PropCost::binary(PropCost::LO); }
template<class Val, class A, class B, PropCond pc, class Ctrl> void ReLinBin<Val,A,B,pc,Ctrl>::reschedule(Space& home) { x0.reschedule(home,*this,pc); x1.reschedule(home,*this,pc); b.reschedule(home,*this,PC_INT_VAL); }
template<class Val, class A, class B, PropCond pc, class Ctrl> forceinline size_t ReLinBin<Val,A,B,pc,Ctrl>::dispose(Space& home) { x0.cancel(home,*this,pc); x1.cancel(home,*this,pc); b.cancel(home,*this,PC_BOOL_VAL); (void) Propagator::dispose(home); return sizeof(*this); }
/* * Binary bounds consistent linear equality * */
template<class Val, class A, class B> forceinline EqBin<Val,A,B>::EqBin(Home home, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus EqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { (void) new (home) EqBin<Val,A,B>(home,x0,x1,c); return ES_OK; }
template<class Val, class A, class B> forceinline EqBin<Val,A,B>::EqBin(Space& home, EqBin<Val,A,B>& p) : LinBin<Val,A,B,PC_INT_BND>(home,p) {}
template<class Val, class A, class B> forceinline EqBin<Val,A,B>::EqBin(Space& home, Propagator& p, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,p,x0,x1,c) {}
template<class Val, class A, class B> Actor* EqBin<Val,A,B>::copy(Space& home) { return new (home) EqBin<Val,A,B>(home,*this); }
/// Describe which view has been modified how enum BinMod { BM_X0_MIN = 1<<0, BM_X0_MAX = 1<<1, BM_X1_MIN = 1<<2, BM_X1_MAX = 1<<3, BM_ALL = BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX };
#define GECODE_INT_PV(CASE,TELL,UPDATE) \ if (bm & (CASE)) { \ bm -= (CASE); ModEvent me = (TELL); \ if (me_failed(me)) return ES_FAILED; \ if (me_modified(me)) bm |= (UPDATE); \ }
template<class Val, class A, class B> ExecStatus EqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { int bm = BM_ALL; do { GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX); GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX); GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN); GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN); } while (bm); return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX; }
#undef GECODE_INT_PV
/* * Reified binary bounds consistent linear equality * */
template<class Val, class A, class B, class Ctrl, ReifyMode rm> forceinline ReEqBin<Val,A,B,Ctrl,rm>::ReEqBin(Home home, A x0, B x1, Val c, Ctrl b) : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
template<class Val, class A, class B, class Ctrl, ReifyMode rm> ExecStatus ReEqBin<Val,A,B,Ctrl,rm>::post(Home home, A x0, B x1, Val c, Ctrl b) { (void) new (home) ReEqBin<Val,A,B,Ctrl,rm>(home,x0,x1,c,b); return ES_OK; }
template<class Val, class A, class B, class Ctrl, ReifyMode rm> forceinline ReEqBin<Val,A,B,Ctrl,rm>::ReEqBin(Space& home, ReEqBin<Val,A,B,Ctrl,rm>& p) : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,p) {}
template<class Val, class A, class B, class Ctrl, ReifyMode rm> Actor* ReEqBin<Val,A,B,Ctrl,rm>::copy(Space& home) { return new (home) ReEqBin<Val,A,B,Ctrl,rm>(home,*this); }
template<class Val, class A, class B, class Ctrl, ReifyMode rm> ExecStatus ReEqBin<Val,A,B,Ctrl,rm>::propagate(Space& home, const ModEventDelta&) { if (b.zero()) { if (rm == RM_IMP) return home.ES_SUBSUMED(*this); GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c))); } if (b.one()) { if (rm == RM_PMI) return home.ES_SUBSUMED(*this); GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c))); } if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) { if (rm != RM_PMI) GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this); } if (x0.assigned() && x1.assigned()) { assert(x0.val() + x1.val() == c); if (rm != RM_IMP) GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this); } return ES_FIX; }
/* * Binary domain consistent linear disequality * */ template<class Val, class A, class B> forceinline NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { (void) new (home) NqBin<Val,A,B>(home,x0,x1,c); return ES_OK; }
template<class Val, class A, class B> forceinline NqBin<Val,A,B>::NqBin(Space& home, NqBin<Val,A,B>& p) : LinBin<Val,A,B,PC_INT_VAL>(home,p) {}
template<class Val, class A, class B> Actor* NqBin<Val,A,B>::copy(Space& home) { return new (home) NqBin<Val,A,B>(home,*this); }
template<class Val, class A, class B> forceinline NqBin<Val,A,B>::NqBin(Space& home, Propagator& p, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_VAL>(home,p,x0,x1,c) {}
template<class Val, class A, class B> PropCost NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const { return PropCost::unary(PropCost::LO); }
template<class Val, class A, class B> ExecStatus NqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { if (x0.assigned()) { GECODE_ME_CHECK(x1.nq(home,c-x0.val())); } else { assert(x1.assigned()); GECODE_ME_CHECK(x0.nq(home,c-x1.val())); } return home.ES_SUBSUMED(*this); }
/* * Binary domain consistent less equal * */
template<class Val, class A, class B> forceinline LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { (void) new (home) LqBin<Val,A,B>(home,x0,x1,c); return ES_OK; }
template<class Val, class A, class B> forceinline LqBin<Val,A,B>::LqBin(Space& home, LqBin<Val,A,B>& p) : LinBin<Val,A,B,PC_INT_BND>(home,p) {}
template<class Val, class A, class B> Actor* LqBin<Val,A,B>::copy(Space& home) { return new (home) LqBin<Val,A,B>(home,*this); }
template<class Val, class A, class B> forceinline LqBin<Val,A,B>::LqBin(Space& home, Propagator& p, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,p,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus LqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { GECODE_ME_CHECK(x0.lq(home,c-x1.min())); GECODE_ME_CHECK(x1.lq(home,c-x0.min())); return (x0.max()+x1.max() <= c) ? home.ES_SUBSUMED(*this) : ES_FIX; }
/* * Binary domain consistent greater equal * */
template<class Val, class A, class B> forceinline GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) { (void) new (home) GqBin<Val,A,B>(home,x0,x1,c); return ES_OK; }
template<class Val, class A, class B> forceinline GqBin<Val,A,B>::GqBin(Space& home, GqBin<Val,A,B>& p) : LinBin<Val,A,B,PC_INT_BND>(home,p) {}
template<class Val, class A, class B> Actor* GqBin<Val,A,B>::copy(Space& home) { return new (home) GqBin<Val,A,B>(home,*this); }
template<class Val, class A, class B> forceinline GqBin<Val,A,B>::GqBin(Space& home, Propagator& p, A x0, B x1, Val c) : LinBin<Val,A,B,PC_INT_BND>(home,p,x0,x1,c) {}
template<class Val, class A, class B> ExecStatus GqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) { GECODE_ME_CHECK(x0.gq(home,c-x1.max())); GECODE_ME_CHECK(x1.gq(home,c-x0.max())); return (x0.min()+x1.min() >= c) ? home.ES_SUBSUMED(*this) : ES_FIX; }
/* * Reified binary domain consistent less equal * */
template<class Val, class A, class B, ReifyMode rm> forceinline ReLqBin<Val,A,B,rm>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b) : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
template<class Val, class A, class B, ReifyMode rm> ExecStatus ReLqBin<Val,A,B,rm>::post(Home home, A x0, B x1, Val c, BoolView b) { (void) new (home) ReLqBin<Val,A,B,rm>(home,x0,x1,c,b); return ES_OK; }
template<class Val, class A, class B, ReifyMode rm> forceinline ReLqBin<Val,A,B,rm>::ReLqBin(Space& home, ReLqBin<Val,A,B,rm>& p) : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,p) {}
template<class Val, class A, class B, ReifyMode rm> Actor* ReLqBin<Val,A,B,rm>::copy(Space& home) { return new (home) ReLqBin<Val,A,B,rm>(home,*this); }
template<class Val, class A, class B, ReifyMode rm> ExecStatus ReLqBin<Val,A,B,rm>::propagate(Space& home, const ModEventDelta&) { if (b.one()) { if (rm == RM_PMI) return home.ES_SUBSUMED(*this); GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c))); } if (b.zero()) { if (rm == RM_IMP) return home.ES_SUBSUMED(*this); GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1))); } if (x0.max() + x1.max() <= c) { if (rm != RM_IMP) GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this); } if (x0.min() + x1.min() > c) { if (rm != RM_PMI) GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this); } return ES_FIX; }
}}}
// STATISTICS: int-prop