mult.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Vincent Barichard <Vincent.Barichard@univ-angers.fr>
*
* Copyright:
* Christian Schulte, 2004
* Vincent Barichard, 2012
*
* 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 Float { namespace Arithmetic {
template<class View>
forceinline bool
pos(const View& x) {
return x.min() >= 0.0;
}
template<class View>
forceinline bool
neg(const View& x) {
return x.max() <= 0.0;
}
template<class View>
forceinline bool
any(const View& x) {
return (x.min() <= 0.0) && (x.max() >= 0.0);
}
/*
* Propagator for x * y = x
*
*/
template<class View>
forceinline
MultZeroOne<View>::MultZeroOne(Home home, View x0, View x1)
: BinaryPropagator<View,PC_FLOAT_BND>(home,x0,x1) {}
template<class View>
forceinline ExecStatus
MultZeroOne<View>::post(Home home, View x0, View x1) {
switch (rtest_eq(x0,0.0)) {
case RT_FALSE:
GECODE_ME_CHECK(x1.eq(home,1.0));
break;
case RT_TRUE:
break;
case RT_MAYBE:
switch (rtest_eq(x1,1.0)) {
case RT_FALSE:
GECODE_ME_CHECK(x0.eq(home,0.0));
break;
case RT_TRUE:
break;
case RT_MAYBE:
(void) new (home) MultZeroOne<View>(home,x0,x1);
break;
default: GECODE_NEVER;
}
break;
default: GECODE_NEVER;
}
return ES_OK;
}
template<class View>
forceinline
MultZeroOne<View>::MultZeroOne(Space& home, MultZeroOne<View>& p)
: BinaryPropagator<View,PC_FLOAT_BND>(home,p) {}
template<class View>
Actor*
MultZeroOne<View>::copy(Space& home) {
return new (home) MultZeroOne<View>(home,*this);
}
template<class View>
ExecStatus
MultZeroOne<View>::propagate(Space& home, const ModEventDelta&) {
switch (rtest_eq(x0,0.0)) {
case RT_FALSE:
GECODE_ME_CHECK(x1.eq(home,1.0));
break;
case RT_TRUE:
break;
case RT_MAYBE:
switch (rtest_eq(x1,1.0)) {
case RT_FALSE:
GECODE_ME_CHECK(x0.eq(home,0.0));
break;
case RT_TRUE:
break;
case RT_MAYBE:
return ES_FIX;
default: GECODE_NEVER;
}
break;
default: GECODE_NEVER;
}
return home.ES_SUBSUMED(*this);
}
/*
* Positive bounds consistent multiplication
*
*/
template<class VA, class VB, class VC>
forceinline
MultPlus<VA,VB,VC>::MultPlus(Home home, VA x0, VB x1, VC x2)
: MixTernaryPropagator<VA,PC_FLOAT_BND,VB,PC_FLOAT_BND,VC,PC_FLOAT_BND>
(home,x0,x1,x2) {}
template<class VA, class VB, class VC>
forceinline
MultPlus<VA,VB,VC>::MultPlus(Space& home, MultPlus<VA,VB,VC>& p)
: MixTernaryPropagator<VA,PC_FLOAT_BND,VB,PC_FLOAT_BND,VC,PC_FLOAT_BND>
(home,p) {}
template<class VA, class VB, class VC>
Actor*
MultPlus<VA,VB,VC>::copy(Space& home) {
return new (home) MultPlus<VA,VB,VC>(home,*this);
}
template<class VA, class VB, class VC>
ExecStatus
MultPlus<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
if (x1.min() != 0.0)
GECODE_ME_CHECK(x0.eq(home,x2.val() / x1.val()));
if (x0.min() != 0.0)
GECODE_ME_CHECK(x1.eq(home,x2.val() / x0.val()));
GECODE_ME_CHECK(x2.eq(home,x0.val() * x1.val()));
if (x0.assigned() && x1.assigned() && x2.assigned())
return home.ES_SUBSUMED(*this);
return ES_NOFIX;
}
template<class VA, class VB, class VC>
forceinline ExecStatus
MultPlus<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
GECODE_ME_CHECK(x0.gq(home,0.0));
GECODE_ME_CHECK(x1.gq(home,0.0));
Rounding r;
GECODE_ME_CHECK(x2.gq(home,r.mul_down(x0.min(),x1.min())));
(void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
return ES_OK;
}
/*
* Bounds consistent multiplication
*
*/
template<class View>
forceinline
Mult<View>::Mult(Home home, View x0, View x1, View x2)
: TernaryPropagator<View,PC_FLOAT_BND>(home,x0,x1,x2) {}
template<class View>
forceinline
Mult<View>::Mult(Space& home, Mult<View>& p)
: TernaryPropagator<View,PC_FLOAT_BND>(home,p) {}
template<class View>
Actor*
Mult<View>::copy(Space& home) {
return new (home) Mult<View>(home,*this);
}
template<class View>
ExecStatus
Mult<View>::propagate(Space& home, const ModEventDelta&) {
Rounding r;
if (pos(x0)) {
if (pos(x1) || pos(x2)) goto rewrite_ppp;
if (neg(x1) || neg(x2)) goto rewrite_pnn;
goto prop_pxx;
}
if (neg(x0)) {
if (neg(x1) || pos(x2)) goto rewrite_nnp;
if (pos(x1) || neg(x2)) goto rewrite_npn;
goto prop_nxx;
}
if (pos(x1)) {
if (pos(x2)) goto rewrite_ppp;
if (neg(x2)) goto rewrite_npn;
goto prop_xpx;
}
if (neg(x1)) {
if (pos(x2)) goto rewrite_nnp;
if (neg(x2)) goto rewrite_pnn;
goto prop_xnx;
}
assert(any(x0) && any(x1));
GECODE_ME_CHECK(x2.lq(home,std::max(r.mul_up(x0.max(),x1.max()),
r.mul_up(x0.min(),x1.min()))));
GECODE_ME_CHECK(x2.gq(home,std::min(r.mul_down(x0.min(),x1.max()),
r.mul_down(x0.max(),x1.min()))));
if (pos(x2)) {
if (r.div_up(x2.min(),x1.min()) < x0.min())
GECODE_ME_CHECK(x0.gq(home,0));
if (r.div_up(x2.min(),x0.min()) < x1.min())
GECODE_ME_CHECK(x1.gq(home,0));
}
if (neg(x2)) {
if (r.div_up(x2.max(),x1.max()) < x0.min())
GECODE_ME_CHECK(x0.gq(home,0));
if (r.div_up(x2.max(),x0.max()) < x1.min())
GECODE_ME_CHECK(x1.gq(home,0));
}
if (x0.assigned()) {
assert((x0.val() == 0.0) && (x2.val() == 0.0));
return home.ES_SUBSUMED(*this);
}
if (x1.assigned()) {
assert((x1.val() == 0.0) && (x2.val() == 0.0));
return home.ES_SUBSUMED(*this);
}
return ES_NOFIX;
prop_xpx:
std::swap(x0,x1);
prop_pxx:
assert(pos(x0) && any(x1) && any(x2));
GECODE_ME_CHECK(x2.lq(home,r.mul_up(x0.max(),x1.max())));
GECODE_ME_CHECK(x2.gq(home,r.mul_down(x0.max(),x1.min())));
if (pos(x2)) goto rewrite_ppp;
if (neg(x2)) goto rewrite_pnn;
GECODE_ME_CHECK(x1.lq(home,r.div_up(x2.max(),x0.min())));
GECODE_ME_CHECK(x1.gq(home,r.div_down(x2.min(),x0.min())));
if (x0.assigned() && x1.assigned()) {
GECODE_ME_CHECK(x2.eq(home,x0.val()*x1.val()));
return home.ES_SUBSUMED(*this);
}
return ES_NOFIX;
prop_xnx:
std::swap(x0,x1);
prop_nxx:
assert(neg(x0) && any(x1) && any(x2));
GECODE_ME_CHECK(x2.lq(home,r.mul_up(x0.min(),x1.min())));
GECODE_ME_CHECK(x2.gq(home,r.mul_down(x0.min(),x1.max())));
if (pos(x2)) goto rewrite_nnp;
if (neg(x2)) goto rewrite_npn;
if (x0.max() != 0.0) {
GECODE_ME_CHECK(x1.lq(home,r.div_up(x2.min(),x0.max())));
GECODE_ME_CHECK(x1.gq(home,r.div_down(x2.max(),x0.max())));
}
if (x0.assigned() && x1.assigned()) {
GECODE_ME_CHECK(x2.eq(home,x0.val()*x1.val()));
return home.ES_SUBSUMED(*this);
}
return ES_NOFIX;
rewrite_ppp:
GECODE_REWRITE(*this,(MultPlus<FloatView,FloatView,FloatView>
::post(home(*this),x0,x1,x2)));
rewrite_nnp:
GECODE_REWRITE(*this,(MultPlus<MinusView,MinusView,FloatView>
::post(home(*this),MinusView(x0),MinusView(x1),x2)));
rewrite_pnn:
std::swap(x0,x1);
rewrite_npn:
GECODE_REWRITE(*this,(MultPlus<MinusView,FloatView,MinusView>
::post(home(*this),MinusView(x0),x1,MinusView(x2))));
}
template<class View>
ExecStatus
Mult<View>::post(Home home, View x0, View x1, View x2) {
if (x0 == x1)
return Sqr<View>::post(home,x0,x2);
if (x0 == x2)
return MultZeroOne<View>::post(home,x0,x1);
if (x1 == x2)
return MultZeroOne<View>::post(home,x1,x0);
if (pos(x0)) {
if (pos(x1) || pos(x2)) goto post_ppp;
if (neg(x1) || neg(x2)) goto post_pnn;
} else if (neg(x0)) {
if (neg(x1) || pos(x2)) goto post_nnp;
if (pos(x1) || neg(x2)) goto post_npn;
} else if (pos(x1)) {
if (pos(x2)) goto post_ppp;
if (neg(x2)) goto post_npn;
} else if (neg(x1)) {
if (pos(x2)) goto post_nnp;
if (neg(x2)) goto post_pnn;
}
{
GECODE_ME_CHECK(x2.eq(home,x0.val()*x1.val()));
(void) new (home) Mult<View>(home,x0,x1,x2);
}
return ES_OK;
post_ppp:
return MultPlus<FloatView,FloatView,FloatView>::post(home,x0,x1,x2);
post_nnp:
return MultPlus<MinusView,MinusView,FloatView>::post(home,
MinusView(x0),MinusView(x1),x2);
post_pnn:
std::swap(x0,x1);
post_npn:
return MultPlus<MinusView,FloatView,MinusView>::post(home,
MinusView(x0),x1,MinusView(x2));
}
}}}
// STATISTICS: float-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::BinaryPropagator< View, PC_FLOAT_BND >::x0
View x0
Definition pattern.hpp:87
Gecode::BinaryPropagator< View, PC_FLOAT_BND >::BinaryPropagator
BinaryPropagator(Space &home, BinaryPropagator &p)
Gecode::BinaryPropagator< View, PC_FLOAT_BND >::x1
View x1
Definition pattern.hpp:87
Gecode::Float::Arithmetic::MultPlus
Bounds consistent positive multiplication propagator.
Definition arithmetic.hh:245
Gecode::Float::Arithmetic::MultPlus::post
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition mult.hpp:169
Gecode::Float::Arithmetic::MultPlus::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition mult.hpp:150
Gecode::Float::Arithmetic::MultPlus::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition mult.hpp:156
Gecode::Float::Arithmetic::MultPlus::MultPlus
MultPlus(Home home, VA x0, VB x1, VC x2)
Constructor for posting.
Definition mult.hpp:138
Gecode::Float::Arithmetic::MultZeroOne::post
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition mult.hpp:69
Gecode::Float::Arithmetic::MultZeroOne::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition mult.hpp:107
Gecode::Float::Arithmetic::MultZeroOne::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition mult.hpp:101
Gecode::Float::Arithmetic::MultZeroOne::MultZeroOne
MultZeroOne(Space &home, MultZeroOne< View > &p)
Constructor for cloning p.
Definition mult.hpp:96
Gecode::Float::Arithmetic::Mult::post
static ExecStatus post(Home home, View x0, View x1, View x2)
Post propagator .
Definition mult.hpp:314
Gecode::Float::Arithmetic::Mult::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition mult.hpp:195
Gecode::Float::Arithmetic::Mult::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition mult.hpp:201
Gecode::Float::Arithmetic::Mult::Mult
Mult(Space &home, Mult< View > &p)
Constructor for cloning p.
Definition mult.hpp:190
Gecode::Float::Arithmetic::Sqr::post
static ExecStatus post(Home home, View x0, View x1)
Post propagator for .
Definition sqr-sqrt.hpp:105
Gecode::Float::MinusView
Minus float view.
Definition view.hpp:154
Gecode::Float::Rounding
Floating point rounding policy.
Definition float.hh:154
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::MixTernaryPropagator< VA, PC_FLOAT_BND, VB, PC_FLOAT_BND, VC, PC_FLOAT_BND >::x0
VA x0
Definition pattern.hpp:240
Gecode::MixTernaryPropagator< VA, PC_FLOAT_BND, VB, PC_FLOAT_BND, VC, PC_FLOAT_BND >::x1
VB x1
Definition pattern.hpp:242
Gecode::MixTernaryPropagator< VA, PC_FLOAT_BND, VB, PC_FLOAT_BND, VC, PC_FLOAT_BND >::x2
VC x2
Definition pattern.hpp:244
Gecode::MixTernaryPropagator< VA, PC_FLOAT_BND, VB, PC_FLOAT_BND, VC, PC_FLOAT_BND >::MixTernaryPropagator
MixTernaryPropagator(Space &home, MixTernaryPropagator &p)
Definition pattern.hpp:661
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::TernaryPropagator< View, PC_FLOAT_BND >::x2
View x2
Definition pattern.hpp:116
Gecode::TernaryPropagator< View, PC_FLOAT_BND >::x1
View x1
Definition pattern.hpp:116
Gecode::TernaryPropagator< View, PC_FLOAT_BND >::x0
View x0
Definition pattern.hpp:116
Gecode::TernaryPropagator< View, PC_FLOAT_BND >::TernaryPropagator
TernaryPropagator(Space &home, TernaryPropagator &p)
Gecode::View
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
GECODE_REWRITE
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
Gecode::Float::Arithmetic
Arithmetic propagators
Gecode::Float::Arithmetic::any
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition mult.hpp:53
Gecode::Float::Arithmetic::pos
bool pos(const View &x)
Test whether x is postive.
Definition mult.hpp:41
Gecode::Float::Arithmetic::neg
bool neg(const View &x)
Test whether x is negative.
Definition mult.hpp:47
Gecode::Float
Floating point numbers.
Gecode::Float::RT_TRUE
@ RT_TRUE
Relation does hold.
Definition view.hpp:536
Gecode::Float::RT_FALSE
@ RT_FALSE
Relation does not hold.
Definition view.hpp:534
Gecode::Float::RT_MAYBE
@ RT_MAYBE
Relation may hold or not.
Definition view.hpp:535
Gecode::Float::rtest_eq
RelTest rtest_eq(View x, View y)
Test whether views x and y are equal.
Definition rel-test.hpp:40
Gecode::Float::PC_FLOAT_BND
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:292
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56