Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
singleton.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 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * Guido Tack, 2004
11 * Christian Schulte, 2004
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38namespace Gecode { namespace Set {
39
42
46
50
53 switch(pc) {
54 case PC_SET_VAL:
55 case PC_SET_CGLB:
56 case PC_SET_CARD:
58 default:
60 }
61 }
62
65 switch(me) {
67 return ME_SET_FAILED;
69 return ME_SET_NONE;
71 return ME_SET_VAL;
73 return ME_SET_LUB;
74 default:
75 return ME_SET_LUB;
76 }
77 }
78
81 switch(me) {
82 case ME_SET_FAILED:
84 case ME_SET_NONE:
86 case ME_SET_VAL:
88 default:
90 }
91 }
92
93 forceinline unsigned int
95 return x.assigned() ? 1U : 0U;
96 }
97
98 forceinline unsigned int
99 SingletonView::lubSize(void) const { return x.size(); }
100
101 forceinline unsigned int
103 return lubSize() - glbSize();
104 }
105
106 forceinline bool
107 SingletonView::contains(int n) const { return x.assigned() ?
108 (x.val()==n) : false; }
109
110 forceinline bool
111 SingletonView::notContains(int n) const { return !x.in(n); }
112
113 forceinline unsigned int
114 SingletonView::cardMin() const { return 1; }
115
116 forceinline unsigned int
117 SingletonView::cardMax() const { return 1; }
118
119 forceinline int
120 SingletonView::lubMin() const { return x.min(); }
121
122 forceinline int
123 SingletonView::lubMax() const { return x.max(); }
124
125 forceinline int
126 SingletonView::glbMin() const { return x.assigned() ?
128
129 forceinline int
130 SingletonView::glbMax() const { return x.assigned() ?
132
134 SingletonView::cardMin(Space&, unsigned int c) {
135 return c<=1 ? ME_SET_NONE : ME_SET_FAILED;
136 }
137
139 SingletonView::cardMax(Space&, unsigned int c) {
140 return c<1 ? ME_SET_FAILED : ME_SET_NONE;
141 }
142
145 return me_inttoset(x.eq(home,c));
146 }
147
150 return me_inttoset(x.eq(home,c));
151 }
152
154 SingletonView::intersect(Space& home,int i, int j) {
155 ModEvent me1 = me_inttoset(x.gq(home,i));
156 ModEvent me2 = me_inttoset(x.lq(home,j));
157 if (me_failed(me1) || me_failed(me2))
158 return ME_SET_FAILED;
159 switch (me1) {
160 case ME_SET_NONE:
161 case ME_SET_LUB:
162 return me2;
163 case ME_SET_VAL:
164 return ME_SET_VAL;
165 default:
167 return ME_SET_VAL;
168 }
169 }
170
173 return me_inttoset(x.nq(home,c));
174 }
175
177 SingletonView::include(Space& home, int j, int k) {
178 return j==k ? me_inttoset(x.eq(home,j)) : ME_SET_FAILED ;
179 }
180
182 SingletonView::exclude(Space& home, int j, int k) {
183 ModEvent me1 = me_inttoset(x.gr(home,j));
184 ModEvent me2 = me_inttoset(x.le(home,k));
185 if (me_failed(me1) || me_failed(me2))
186 return ME_SET_FAILED;
187 switch (me1) {
188 case ME_SET_NONE:
189 case ME_SET_LUB:
190 return me2;
191 case ME_SET_VAL:
192 return ME_SET_VAL;
193 default:
195 return ME_SET_VAL;
196 }
197 }
198
199 template<class I> ModEvent
201 return me_inttoset(x.minus_r(home,iter));
202 }
203
204 template<class I> ModEvent
206 if (!iter())
207 return ME_SET_NONE;
208
209 if (iter.min()!=iter.max())
210 return ME_SET_FAILED;
211
212 int val = iter.min();
213 ++iter;
214 if ( iter() )
215 return ME_SET_FAILED;
216
217 return me_inttoset(x.eq(home, val));
218 }
219
220 template<class I> ModEvent
222 return me_inttoset(x.inter_r(home,iter));
223 }
224
225 forceinline void
227 bool schedule) {
228 x.subscribe(home,p,pc_settoint(pc),schedule);
229 }
230 forceinline void
232 x.cancel(home,p,pc_settoint(pc));
233 }
234 forceinline void
238
239 forceinline void
241 x.subscribe(home,a);
242 }
243 forceinline void
245 x.cancel(home,a);
246 }
247
248
249 forceinline void
261
262
263 /*
264 * Delta information for advisors
265 *
266 * For SingletonViews, a glb change means that the view is assigned.
267 * Thus, the delta for the glb is always equal to the delta for the lub.
268 *
269 */
270
275
276 forceinline int
277 SingletonView::glbMin(const Delta& d) const { return x.min(d); }
278
279 forceinline int
280 SingletonView::glbMax(const Delta& d) const { return x.max(d); }
281
282 forceinline bool
283 SingletonView::glbAny(const Delta& d) const { return x.any(d); }
284
285 forceinline int
286 SingletonView::lubMin(const Delta& d) const { return x.min(d); }
287
288 forceinline int
289 SingletonView::lubMax(const Delta& d) const { return x.max(d); }
290
291 forceinline bool
292 SingletonView::lubAny(const Delta& d) const { return x.any(d); }
293
294 forceinline bool
296 return x.base() == y.base();
297 }
298
299 forceinline bool
301 return x.base() != y.base();
302 }
303
304
305 /*
306 * Iterators
307 *
308 */
309
314 template<>
316 public:
318
319
320 LubRanges(void);
322 LubRanges(const SingletonView& x);
324 void init(const SingletonView& x);
326 };
327
330
333 Gecode::Int::IntVarImpFwd(s.base().varimp()) {}
334
335 forceinline void
339
344 template<>
346 private:
347 int val;
348 bool flag;
349 public:
351
352
353 GlbRanges(void);
355 GlbRanges(const SingletonView& x);
357 void init(const SingletonView& x);
358
360
361
362 bool operator ()(void) const;
364 void operator ++(void);
366
368
369
370 int min(void) const;
372 int max(void) const;
374 unsigned int width(void) const;
376 };
377
380
381 forceinline void
383 if (s.base().assigned()) {
384 val = s.base().val();
385 flag = true;
386 } else {
387 val = 0;
388 flag = false;
389 }
390 }
391
396
397 forceinline bool
398 GlbRanges<SingletonView>::operator ()(void) const { return flag; }
399
400 forceinline void
402
403 forceinline int
404 GlbRanges<SingletonView>::min(void) const { return val; }
405 forceinline int
406 GlbRanges<SingletonView>::max(void) const { return val; }
407 forceinline unsigned int
408 GlbRanges<SingletonView>::width(void) const { return 1; }
409
410}}
411
412// STATISTICS: set-var
413
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition core.hpp:1292
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Base-class for derived views.
Definition view.hpp:230
View base(void) const
Return view from which this view is derived.
Definition view.hpp:605
Integer variables.
Definition int.hh:371
Range iterator for ranges of integer variable implementation.
Definition var-imp.hpp:392
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition int.hpp:432
Integer view for integer variables.
Definition view.hpp:129
unsigned int size(void) const
Return size (cardinality) of domain.
Definition int.hpp:81
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition int.hpp:186
int min(void) const
Return minimum of domain.
Definition int.hpp:58
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition int.hpp:148
bool in(int n) const
Test whether n is contained in domain.
Definition int.hpp:107
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition int.hpp:130
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition int.hpp:191
int val(void) const
Return assigned value (only if assigned)
Definition int.hpp:70
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition int.hpp:230
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition int.hpp:157
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Base-class for propagators.
Definition core.hpp:1064
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition var-imp.hpp:110
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition var-imp.hpp:112
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
bool operator()(void) const
Test whether iterator is still at a range or done.
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
void operator++(void)
Move iterator to next range (if possible)
GlbRanges(void)
Default constructor.
Range iterator for the least upper bound.
Definition var-imp.hpp:317
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Singleton set view.
Definition view.hpp:594
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
bool contains(int i) const
Test whether i is in the greatest lower bound.
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
unsigned int cardMin(void) const
Return minimum cardinality.
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition singleton.hpp:99
int lubMax(void) const
Return maximum of the least upper bound.
int glbMax(void) const
Return maximum of the greatest lower bound.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
unsigned int cardMax(void) const
Return maximum cardinality.
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition singleton.hpp:94
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
int glbMin(void) const
Return minimum of the greatest lower bound.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
unsigned int unknownSize(void) const
Return the number of unknown elements.
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
bool notContains(int i) const
Test whether i is not in the least upper bound.
SingletonView(void)
Default constructor.
Definition singleton.hpp:41
static PropCond pc_settoint(PropCond pc)
Convert set variable PropCond pc to a PropCond for integer variables.
Definition singleton.hpp:52
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
static ModEvent me_inttoset(ModEvent me)
Convert integer variable ModEvent me to a ModEvent for set variables.
Definition singleton.hpp:64
static ModEvent me_settoint(ModEvent me)
Convert set variable ModEvent me to a ModEvent for integer variables.
Definition singleton.hpp:80
int lubMin(void) const
Return minimum of the least upper bound.
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
static ModEvent modevent(const Delta &d)
Return modification event.
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Computation spaces.
Definition core.hpp:1742
static ModEventDelta med(ModEvent me)
Definition view.hpp:557
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
static void schedule(Space &home, Propagator &p, ModEvent me)
Definition view.hpp:547
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:527
static ModEvent modevent(const Delta &d)
Definition view.hpp:562
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
void varimp(VarImpType *y)
Set variable implementation to y.
Definition view.hpp:484
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:82
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:52
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:401
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:406
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:142
const Gecode::PropCond PC_SET_CARD
Propagate when the cardinality of a view changes.
Definition var-type.hpp:216
const Gecode::PropCond PC_SET_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:207
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition var-type.hpp:156
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:138
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition var-type.hpp:238
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
int PropCond
Type for propagation conditions.
Definition core.hpp:72
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
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56