Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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() ?
127 x.val() : BndSet::MIN_OF_EMPTY; }
128
129 forceinline int
130 SingletonView::glbMax() const { return x.assigned() ?
131 x.val() : BndSet::MAX_OF_EMPTY; }
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
236 x.reschedule(home,p,pc_settoint(pc));
237 }
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
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
Base-class for advisors.
Definition core.hpp:1294
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
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
IntVarImpFwd(void)
Default constructor.
Definition int.hpp:427
Integer view for integer variables.
Definition view.hpp:129
int val(void) const
Return assigned value (only if assigned)
Definition int.hpp:70
Base-class for propagators.
Definition core.hpp:1066
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
GlbRanges(void)
Default constructor.
void init(const SingletonView &x)
Initialize with ranges for view x.
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.
LubRanges(void)
Default constructor.
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:1744
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
static ModEvent modevent(const Delta &d)
Definition view.hpp:562
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
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
Propagators connecting set and int variables.
Definition int.cpp:105
Finite integer sets.
Definition var-imp.hpp:137
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:773
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56