Generated on Fri Jul 21 2023 00:00:00 for Gecode by doxygen 1.9.6
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
45 : DerivedView<Gecode::Int::IntView>(y) {}
46
49 : DerivedView<Gecode::Int::IntView>(y) {}
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
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
252 }
256 }
259 return SetView::med(me_settoint(me));
260 }
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
274 }
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
338 }
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
394 init(s);
395 }
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.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition: core.hpp:1294
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
Gecode::Int::IntView x
View from which this view is derived.
Definition: view.hpp:238
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: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
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.
Definition: singleton.hpp:182
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: singleton.hpp:292
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: singleton.hpp:107
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
Definition: singleton.hpp:154
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: singleton.hpp:114
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: singleton.hpp:235
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.
Definition: singleton.hpp:123
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: singleton.hpp:130
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: singleton.hpp:254
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: singleton.hpp:221
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: singleton.hpp:117
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: singleton.hpp:283
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.
Definition: singleton.hpp:205
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: singleton.hpp:126
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: singleton.hpp:231
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: singleton.hpp:102
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: singleton.hpp:226
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: singleton.hpp:111
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.
Definition: singleton.hpp:177
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: singleton.hpp:200
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.
Definition: singleton.hpp:120
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: singleton.hpp:250
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: singleton.hpp:272
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: singleton.hpp:258
Computation spaces.
Definition: core.hpp:1744
static ModEventDelta med(ModEvent me)
Translate modification event me to modification event delta for view.
Definition: view.hpp:557
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event 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)
Return modification event.
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: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