Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
eq.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Int { namespace Bool {
35
36 template<class BVA, class BVB>
38 Eq<BVA,BVB>::Eq(Home home, BVA b0, BVB b1)
39 : BoolBinary<BVA,BVB>(home,b0,b1) {}
40
41 template<class BVA, class BVB>
44 : BoolBinary<BVA,BVB>(home,p) {}
45
46 template<class BVA, class BVB>
49 BVA b0, BVB b1)
50 : BoolBinary<BVA,BVB>(home,p,b0,b1) {}
51
52 template<class BVA, class BVB>
53 Actor*
55 return new (home) Eq<BVA,BVB>(home,*this);
56 }
57
58 template<class BVA, class BVB>
59 inline ExecStatus
60 Eq<BVA,BVB>::post(Home home, BVA b0, BVB b1) {
61 switch (bool_test(b0,b1)) {
62 case BT_SAME: return ES_OK;
63 case BT_COMP: return ES_FAILED;
64 case BT_NONE:
65 if (b0.zero()) {
66 GECODE_ME_CHECK(b1.zero(home));
67 } else if (b0.one()) {
68 GECODE_ME_CHECK(b1.one(home));
69 } else if (b1.zero()) {
70 GECODE_ME_CHECK(b0.zero(home));
71 } else if (b1.one()) {
72 GECODE_ME_CHECK(b0.one(home));
73 } else {
74 (void) new (home) Eq<BVA,BVB>(home,b0,b1);
75 }
76 break;
77 default: GECODE_NEVER;
78 }
79 return ES_OK;
80 }
81
82 template<class BVA, class BVB>
85#define GECODE_INT_STATUS(S0,S1) \
86 ((BVA::S0<<(1*BVA::BITS))|(BVB::S1<<(0*BVB::BITS)))
87 switch ((x0.status() << (1*BVA::BITS)) | (x1.status() << (0*BVB::BITS))) {
88 case GECODE_INT_STATUS(NONE,NONE):
90 case GECODE_INT_STATUS(NONE,ZERO):
91 GECODE_ME_CHECK(x0.zero_none(home)); break;
92 case GECODE_INT_STATUS(NONE,ONE):
93 GECODE_ME_CHECK(x0.one_none(home)); break;
94 case GECODE_INT_STATUS(ZERO,NONE):
95 GECODE_ME_CHECK(x1.zero_none(home)); break;
96 case GECODE_INT_STATUS(ZERO,ZERO):
97 break;
98 case GECODE_INT_STATUS(ZERO,ONE):
99 return ES_FAILED;
100 case GECODE_INT_STATUS(ONE,NONE):
101 GECODE_ME_CHECK(x1.one_none(home)); break;
102 case GECODE_INT_STATUS(ONE,ZERO):
103 return ES_FAILED;
104 case GECODE_INT_STATUS(ONE,ONE):
105 break;
106 default:
108 }
109 return home.ES_SUBSUMED(*this);
110#undef GECODE_INT_STATUS
111 }
112
113 template<class BV>
117
118 template<class BV>
122
123 template<class BV>
124 Actor*
126 return new (home) NaryEq<BV>(home,*this);
127 }
128
129 template<class BV>
130 inline ExecStatus
132 x.unique();
133 int n = x.size();
134 if (n < 2)
135 return ES_OK;
136 if (n == 2)
137 return Eq<BV,BV>::post(home,x[0],x[1]);
138 for (int i=n; i--; )
139 if (x[i].assigned()) {
140 if (x[i].one()) {
141 for (int j=0; j<i; j++)
142 GECODE_ME_CHECK(x[j].one(home));
143 for (int j=i+1; j<n; j++)
144 GECODE_ME_CHECK(x[j].one_none(home));
145 } else {
146 for (int j=0; j<i; j++)
147 GECODE_ME_CHECK(x[j].zero(home));
148 for (int j=i+1; j<n; j++)
149 GECODE_ME_CHECK(x[j].zero_none(home));
150 }
151 return ES_OK;
152 }
153 (void) new (home) NaryEq<BV>(home,x);
154 return ES_OK;
155 }
156
157 template<class BV>
159 NaryEq<BV>::cost(const Space&, const ModEventDelta&) const {
161 }
162
163 template<class BV>
166 int n=x.size();
167 int i=0;
168 while (true) {
169 if (x[i].assigned()) {
170 if (x[i].one()) {
171 for (int j=0; j<i; j++)
172 GECODE_ME_CHECK(x[j].one_none(home));
173 for (int j=i+1; j<n; j++)
174 GECODE_ME_CHECK(x[j].one(home));
175 } else {
176 for (int j=0; j<i; j++)
177 GECODE_ME_CHECK(x[j].zero_none(home));
178 for (int j=i+1; j<n; j++)
179 GECODE_ME_CHECK(x[j].zero(home));
180 }
181 return home.ES_SUBSUMED(*this);
182 }
183 i++;
184 }
186 return ES_FIX;
187 }
188
189}}}
190
191// STATISTICS: int-prop
192
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
Home class for posting propagators
Definition core.hpp:856
Base-class for binary Boolean propagators.
Definition bool.hh:55
Boolean equality propagator.
Definition bool.hh:105
static ExecStatus post(Home home, BVA x0, BVB x1)
Post propagator .
Definition eq.hpp:60
Eq(Home home, BVA b0, BVB b1)
Constructor for posting.
Definition eq.hpp:38
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:54
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:84
n-ary Boolean equality propagator
Definition bool.hh:133
static ExecStatus post(Home home, ViewArray< BV > &x)
Post propagator .
Definition eq.hpp:131
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:165
NaryEq(Home home, ViewArray< BV > &x)
Constructor for posting.
Definition eq.hpp:115
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition eq.hpp:159
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:125
n-ary propagator
Definition pattern.hpp:142
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4813
Base-class for propagators.
Definition core.hpp:1064
Computation spaces.
Definition core.hpp:1742
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_INT_STATUS(S0, S1)
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:126
BoolTest bool_test(const BoolView &b0, const BoolView &b1)
Definition bool-test.hpp:41
@ BT_NONE
No sharing.
Definition view.hpp:1785
@ BT_COMP
Same variable but complement.
Definition view.hpp:1787
@ BT_SAME
Same variable.
Definition view.hpp:1786
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56