Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
re-lq.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, 2011
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 Set { namespace Rel {
35
36 template<class View0, class View1, ReifyMode rm, bool strict>
38 ReLq<View0,View1,rm,strict>::ReLq(Home home, View0 y0, View1 y1,
40 : Propagator(home), x0(y0), x1(y1), b(y2) {
42 x0.subscribe(home,*this, PC_SET_ANY);
43 x1.subscribe(home,*this, PC_SET_ANY);
44 }
45
46 template<class View0, class View1, ReifyMode rm, bool strict>
49 : Propagator(home,p) {
50 x0.update(home,p.x0);
51 x1.update(home,p.x1);
52 b.update(home,p.b);
53 }
54
55 template<class View0, class View1, ReifyMode rm, bool strict>
61
62 template<class View0, class View1, ReifyMode rm, bool strict>
63 void
65 b.reschedule(home,*this, Gecode::Int::PC_INT_VAL);
66 x0.reschedule(home,*this, PC_SET_ANY);
67 x1.reschedule(home,*this, PC_SET_ANY);
68 }
69
70 template<class View0, class View1, ReifyMode rm, bool strict>
71 forceinline size_t
73 b.cancel(home,*this, Gecode::Int::PC_INT_VAL);
74 x0.cancel(home,*this, PC_SET_ANY);
75 x1.cancel(home,*this, PC_SET_ANY);
76 (void) Propagator::dispose(home);
77 return sizeof(*this);
78 }
79
80 template<class View0, class View1, ReifyMode rm, bool strict>
82 ReLq<View0,View1,rm,strict>::post(Home home, View0 x0, View1 x1,
84 if (!same(x0,x1)) {
85 (void) new (home) ReLq<View0,View1,rm,strict>(home,x0,x1,b);
86 } else {
87 if (strict) {
88 if (rm != RM_PMI) {
89 GECODE_ME_CHECK(b.zero(home));
90 }
91 } else {
92 if (rm != RM_IMP) {
93 GECODE_ME_CHECK(b.one(home));
94 }
95 }
96 }
97 return ES_OK;
98 }
99
100 template<class View0, class View1, ReifyMode rm, bool strict>
101 Actor*
103 return new (home) ReLq<View0,View1,rm,strict>(home,*this);
104 }
105
106 template<class View0, class View1, ReifyMode rm, bool strict>
109 if (b.one()) {
110 if (rm == RM_PMI)
111 return home.ES_SUBSUMED(*this);
112 GECODE_REWRITE(*this,(Lq<View0,View1,strict>::post(home(*this),x0,x1)));
113 }
114 if (b.zero()) {
115 if (rm == RM_IMP)
116 return home.ES_SUBSUMED(*this);
117 GECODE_REWRITE(*this,
118 (Lq<View1,View0,!strict>::post(home(*this),x1,x0)));
119 }
120 if (x0.cardMax() == 0) {
121 if ( (!strict) || x1.cardMin() > 0) {
122 if (rm != RM_IMP)
123 GECODE_ME_CHECK(b.one_none(home));
124 return home.ES_SUBSUMED(*this);
125 }
126 if (strict && x1.cardMax() == 0) {
127 if (rm != RM_PMI)
128 GECODE_ME_CHECK(b.zero_none(home));
129 return home.ES_SUBSUMED(*this);
130 }
131 }
132
133 if (x0.assigned() && x1.assigned()) {
134 // directly test x0<=x1
135 int min01;
136 {
137 GlbRanges<View0> x0l(x0);
138 GlbRanges<View1> x1l(x1);
140 if (!d()) {
141 if ((!strict) && x0.cardMax() == x1.cardMax()) {
142 // equal
143 if (rm != RM_IMP)
144 GECODE_ME_CHECK(b.one_none(home));
145 } else {
146 // subset
147 if (rm != RM_PMI)
148 GECODE_ME_CHECK(b.zero_none(home));
149 }
150 return home.ES_SUBSUMED(*this);
151 }
152 min01 = d.min();
153 }
154 int min10;
155 {
156 GlbRanges<View0> x0l(x0);
157 GlbRanges<View1> x1l(x1);
159 if (!d()) {
160 if (strict && x0.cardMax() == x1.cardMax()) {
161 // equal
162 if (rm != RM_PMI)
163 GECODE_ME_CHECK(b.zero_none(home));
164 } else {
165 // subset
166 if (rm != RM_IMP)
167 GECODE_ME_CHECK(b.one_none(home));
168 }
169 return home.ES_SUBSUMED(*this);
170 }
171 min10 = d.min();
172 }
173
174 assert(min01 != min10);
175 if (min01<min10) {
176 if (rm != RM_IMP)
177 GECODE_ME_CHECK(b.one_none(home));
178 } else {
179 if (rm != RM_PMI)
180 GECODE_ME_CHECK(b.zero_none(home));
181 }
182 return home.ES_SUBSUMED(*this);
183 }
184
185 // min(x0lb - x1ub) < min(x1ub) -> b=0
186 if (x1.cardMax() > 0) {
187 GlbRanges<View0> x0l(x0);
188 LubRanges<View1> x1u(x1);
189 int x1umin=x1u.min();
191 if (d() && d.min() < x1umin) {
192 if (rm != RM_PMI)
193 GECODE_ME_CHECK(b.zero_none(home));
194 return home.ES_SUBSUMED(*this);
195 }
196 }
197 // min(x1lb - x0ub) < min(x0ub) -> b=1
198 if (x0.cardMax() > 0) {
199 LubRanges<View0> x0u(x0);
200 GlbRanges<View1> x1l(x1);
201 int x0umin=x0u.min();
203 if (d() && d.min() < x0umin) {
204 if (rm != RM_IMP)
205 GECODE_ME_CHECK(b.one_none(home));
206 return home.ES_SUBSUMED(*this);
207 }
208 }
209
210 return ES_FIX;
211 }
212
213}}}
214
215// STATISTICS: set-prop
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Home class for posting propagators
Definition core.hpp:856
int min(int i) const
Return minimum of range at position i.
Boolean view for Boolean variables.
Definition view.hpp:1380
ReLq(Space &home, ReLq &p)
Constructor for cloning p.
Definition lq-le.hpp:454
static ExecStatus post(Home home, View x0, View x1, CtrlView b)
Post propagator for .
Definition lq-le.hpp:420
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition lq-le.hpp:459
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition lq-le.hpp:465
Range iterator for computing set difference.
Propagation cost.
Definition core.hpp:486
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:4805
Base-class for propagators.
Definition core.hpp:1064
virtual void reschedule(Space &home)=0
Schedule function.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Range iterator for the least upper bound.
Definition var-imp.hpp:317
int min(void) const
Return smallest value of range.
Propagator for set less than or equal
Definition rel.hh:208
Reified propagator for set less than or equal
Definition rel.hh:234
Gecode::Int::BoolView b
Definition rel.hh:238
Computation spaces.
Definition core.hpp:1742
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition view.hpp:567
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
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_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
@ RM_IMP
Implication for reification.
Definition int.hh:862
@ RM_PMI
Inverse implication for reification.
Definition int.hh:869
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:82
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition var-type.hpp:248
Gecode toplevel namespace
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
#define forceinline
Definition config.hpp:187