Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
bool.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 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
34#include <gecode/int.hh>
35
36namespace Gecode { namespace Set { namespace Channel {
37
38 template<class View>
39 template<class A>
43 Council<A>& c, int index)
44 : Advisor(home,p,c), idx(index) {
45 if (idx == -1)
46 p.y.subscribe(home,*this);
47 else {
48 p.x[idx].subscribe(home,*this);
49 }
50 }
51
52 template<class View>
56
57 template<class View>
58 forceinline int
60 return idx;
61 }
62
63 template<class View>
64 template<class A>
65 forceinline void
68 if (idx == -1)
69 p.y.cancel(home,*this);
70 else {
71 p.x[idx].cancel(home,*this);
72 }
73 Advisor::dispose(home,c);
74 }
75
76 template<class View>
80 View y0)
81 : Super(home,x0,y0), co(home), running(false) {
82 bool assigned = false;
83 for (int i=x.size(); i--;) {
84 if (x[i].zero()) {
85 assigned = true;
86 SetDelta d;
87 zeros.include(home, i, i, d);
88 } else if (x[i].one()) {
89 assigned = true;
90 SetDelta d;
91 ones.include(home, i, i, d);
92 } else {
93 (void) new (home) IndexAdvisor(home,*this,co,i);
94 }
95 }
96 if (assigned)
98 View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
99 if (y.assigned()) {
100 if (y.glbSize()==static_cast<unsigned int>(y.glbMax()-y.glbMin()+1)) {
101 new (&delta) SetDelta(y.glbMin(),y.glbMax(),1,0);
102 } else {
103 new (&delta) SetDelta(2,0,1,0);
104 }
105 }
106 (void) new (home) IndexAdvisor(home,*this,co,-1);
107 }
108
109 template<class View>
112 : Super(home,p), running(false) {
113 co.update(home, p.co);
114 }
115
116 template<class View>
119 View y) {
120 GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1));
121 (void) new (home) ChannelBool(home,x,y);
122 return ES_OK;
123 }
124
125 template<class View>
128 return PropCost::quadratic(PropCost::LO, x.size()+1);
129 }
130
131 template<class View>
132 void
134 x.reschedule(home,*this,Gecode::Int::PC_BOOL_VAL);
135 View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
136 }
137
138 template<class View>
139 forceinline size_t
141 co.dispose(home);
142 (void) Super::dispose(home);
143 return sizeof(*this);
144 }
145
146 template<class View>
147 Actor*
149 return new (home) ChannelBool(home,*this);
150 }
151
152 template<class View>
155 running = true;
156 if (zeros.size() > 0) {
157 BndSetRanges zi(zeros);
158 GECODE_ME_CHECK(y.excludeI(home, zi));
159 zeros.init(home);
160 }
161 if (ones.size() > 0) {
162 BndSetRanges oi(ones);
163 GECODE_ME_CHECK(y.includeI(home, oi));
164 ones.init(home);
165 }
166 running = false;
167
168 if (delta.glbMin() != 1 || delta.glbMax() != 0) {
169 if (!delta.glbAny()) {
170 for (int i=delta.glbMin(); i<=delta.glbMax(); i++)
171 GECODE_ME_CHECK(x[i].one(home));
172 } else {
173 GlbRanges<View> glb(y);
174 for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) {
175 GECODE_ME_CHECK(x[gv.val()].one(home));
176 }
177 }
178 }
179 if (delta.lubMin() != 1 || delta.lubMax() != 0) {
180 if (!delta.lubAny()) {
181 for (int i=delta.lubMin(); i<=delta.lubMax(); i++)
182 GECODE_ME_CHECK(x[i].zero(home));
183 } else {
184 int cur = 0;
185 for (LubRanges<View> lub(y); lub(); ++lub) {
186 for (; cur < lub.min(); cur++) {
187 GECODE_ME_CHECK(x[cur].zero(home));
188 }
189 cur = lub.max() + 1;
190 }
191 for (; cur < x.size(); cur++) {
192 GECODE_ME_CHECK(x[cur].zero(home));
193 }
194 }
195 }
196
197 new (&delta) SetDelta();
198
199 return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
200 }
201
202 template<class View>
205 IndexAdvisor& a = static_cast<IndexAdvisor&>(_a);
206 const SetDelta& d = static_cast<const SetDelta&>(_d);
207
208 ModEvent me = View::modevent(d);
209 int index = a.index();
210 if ( (running && index == -1 && me != ME_SET_VAL)
211 || (index == -1 && me == ME_SET_CARD) ) {
212 return ES_OK;
213 }
214
215 if (index >= 0) {
216 if (x[index].zero()) {
217 SetDelta dummy;
218 zeros.include(home, index, index, dummy);
219 } else {
220 assert(x[index].one());
221 SetDelta dummy;
222 ones.include(home, index, index, dummy);
223 }
224 return home.ES_NOFIX_DISPOSE( co, a);
225 }
226
227 if ((a.index() == -1) && Rel::testSetEventLB(me)) {
228 if (d.glbAny()) {
229 new (&delta)
230 SetDelta(2,0, delta.lubMin(), delta.lubMax());
231 } else {
232 if (delta.glbMin() == 1 && delta.glbMax() == 0) {
233 new (&delta)
234 SetDelta(d.glbMin(), d.glbMax(),
235 delta.lubMin(), delta.lubMax());
236 } else {
237 if (delta.glbMin() != 2 || delta.glbMax() != 0) {
238 if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin())
239 ||
240 (delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax())
241 ) {
242 new (&delta)
243 SetDelta(std::min(delta.glbMin(), d.glbMin()),
244 std::max(delta.glbMax(), d.glbMax()),
245 delta.lubMin(), delta.lubMax());
246 } else {
247 new (&delta)
248 SetDelta(2, 0, delta.lubMin(), delta.lubMax());
249 }
250 }
251 }
252 }
253 }
254 if ((a.index() == -1) && Rel::testSetEventUB(me)) {
255 if (d.lubAny()) {
256 new (&delta)
257 SetDelta(delta.glbMin(), delta.glbMax(), 2,0);
258 } else {
259 if (delta.lubMin() == 1 && delta.lubMax() == 0) {
260 new (&delta)
261 SetDelta(delta.glbMin(), delta.glbMax(),
262 d.lubMin(), d.lubMax());
263 } else {
264 if (delta.lubMin() != 2 || delta.lubMax() != 0) {
265 if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin())
266 ||
267 (delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax())
268 ) {
269 new (&delta)
270 SetDelta(delta.lubMin(), delta.lubMax(),
271 std::min(delta.lubMin(), d.lubMin()),
272 std::max(delta.lubMax(), d.lubMax())
273 );
274 } else {
275 new (&delta)
276 SetDelta(delta.glbMin(), delta.glbMax(), 2, 0);
277 }
278 }
279 }
280 }
281 }
282 if (y.assigned())
283 return home.ES_NOFIX_DISPOSE( co, a);
284 else
285 return ES_NOFIX;
286 }
287
288}}}
289
290// STATISTICS: set-prop
int p
Number of positive literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
Base-class for advisors.
Definition core.hpp:1292
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:3864
Council of advisors
Definition core.hpp:1241
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Home class for posting propagators
Definition core.hpp:856
Value iterator from range iterator.
Propagation cost.
Definition core.hpp:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
unsigned int glbSize(void) const
Return number of elements in the greatest lower bound.
Definition set.hpp:63
int glbMin(void) const
Return minimum element of greatest lower bound.
Definition set.hpp:90
int glbMax(void) const
Return maximum of greatest lower bound.
Definition set.hpp:93
Range iterator for integer sets.
Definition var-imp.hpp:185
Advisor storing a single index
Definition channel.hh:166
IndexAdvisor(Space &home, ChannelBool< View > &p, Council< A > &c, int index)
Constructor for creation.
Definition bool.hpp:41
int index(void) const
Access index.
Definition bool.hpp:59
void dispose(Space &home, Council< A > &c)
Delete advisor.
Definition bool.hpp:66
Propagator for channelling between set variable and its characteristic function
Definition channel.hh:151
ChannelBool(Space &home, ChannelBool &p)
Constructor for cloning p.
Definition bool.hpp:111
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition bool.hpp:140
Council< IndexAdvisor > co
Council for managing advisors.
Definition channel.hh:185
GLBndSet ones
Accumulated one Booleans.
Definition channel.hh:191
bool running
Flag whether propagation is currently running.
Definition channel.hh:193
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Finite set delta information for advisors.
Definition var-imp.hpp:52
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
static void schedule(Space &home, Propagator &p, ModEvent me)
Definition view.hpp:547
View arrays.
Definition array.hpp:253
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3887
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
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:116
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:126
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:83
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:87
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:142
const Gecode::ModEvent ME_SET_CARD
Domain operation has changed the variable cardinality.
Definition var-type.hpp:148
const Gecode::ModEvent ME_SET_BB
Domain operation has changed both greatest lower and least upper bound.
Definition var-type.hpp:172
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition filter.cpp:131
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_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:187