Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
complement.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
38#include <sstream>
39
40namespace Gecode { namespace Set {
41
42 template<class View>
45
46 template<class View>
50
51 template<class View>
54 switch(me) {
55 case ME_SET_LUB : return ME_SET_GLB;
56 case ME_SET_GLB : return ME_SET_LUB;
57 case ME_SET_CLUB : return ME_SET_CGLB;
58 case ME_SET_CGLB : return ME_SET_CLUB;
59 default: return me;
60 }
61 }
62
63 template<class View>
66 switch(pc) {
67 case PC_SET_CLUB : return PC_SET_CGLB;
68 case PC_SET_CGLB : return PC_SET_CLUB;
69 default: return pc;
70 }
71 }
72
73 template<class View>
74 forceinline unsigned int
76 return Limits::card - x.lubSize();
77 }
78
79 template<class View>
80 forceinline unsigned int
82 return Limits::card - x.glbSize();
83 }
84
85 template<class View>
86 forceinline unsigned int
88 return lubSize() - glbSize();
89 }
90
91 template<class View>
92 forceinline bool
94
95 template<class View>
96 forceinline bool
98
99 template<class View>
100 forceinline unsigned int
102 return Limits::card - x.cardMax();
103 }
104
105 template<class View>
106 forceinline unsigned int
108 return Limits::card - x.cardMin();
109 }
110
111 template<class View>
112 forceinline int
114 GlbRanges<View> lb(x);
116 if (lbc()) {
117 return lbc.min();
118 } else {
120 }
121 }
122
123 template<class View>
124 forceinline int
126 GlbRanges<View> lb(x);
128 if (lbc()) {
129 while(lbc()) ++lbc;
130 return lbc.max();
131 } else {
133 }
134 }
135
136 template<class View>
137 forceinline int
139 LubRanges<View> ub(x);
141 if (ubc()) {
142 return ubc.min();
143 } else {
145 }
146 }
147
148 template<class View>
149 forceinline int
151 LubRanges<View> ub(x);
153 if (ubc()) {
154 while (ubc()) ++ubc;
155 return ubc.max();
156 } else {
158 }
159 }
160
161 template<class View>
163 ComplementView<View>::cardMin(Space& home, unsigned int c) {
164 if (c < Limits::card)
165 return me_negateset(x.cardMax(home, Limits::card - c));
166 return ME_SET_NONE;
167 }
168
169 template<class View>
171 ComplementView<View>::cardMax(Space& home, unsigned int c) {
172 if (c < Limits::card)
173 return me_negateset(x.cardMin(home, Limits::card - c));
174 return ME_SET_NONE;
175 }
176
177 template<class View>
180 return me_negateset((x.exclude(home, c)));
181 }
182
183 template<class View>
186 return me_negateset((x.include(home, c)));
187 }
188
189 template<class View>
194 return me_negateset((x.includeI(home, csi)));
195 }
196
197 template<class View>
202 return me_negateset((x.includeI(home, csi)));
203 }
204
205 template<class View>
208 return me_negateset(x.exclude(home,j,k));
209 }
210
211 template<class View>
214 return me_negateset(x.include(home,j,k));
215 }
216
217 template<class View>
218 template<class I> ModEvent
220 return me_negateset(x.includeI(home,iter));
221 }
222
223 template<class View>
224 template<class I> ModEvent
226 return me_negateset(x.excludeI(home,iter));
227 }
228
229 template<class View>
230 template<class I> ModEvent
232 RangesCompl<I> c(iter);
233 return me_negateset(x.includeI(home,c));
234 }
235
236 template<class View>
237 forceinline void
239 bool schedule) {
240 x.subscribe(home,p, pc_negateset(pc),schedule);
241 }
242
243 template<class View>
244 forceinline void
246 x.cancel(home,p, pc_negateset(pc));
247 }
248
249 template<class View>
250 forceinline void
252 x.subscribe(home,a);
253 }
254
255 template<class View>
256 forceinline void
258 x.cancel(home,a);
259 }
260
261 template<class View>
262 forceinline void
264 return View::schedule(home,p,me_negateset(me));
265 }
266 template<class View>
269 return me_negateset(View::me(med));
270 }
271
272 template<class View>
275 return me_negateset(View::med(me));
276 }
277
278 /*
279 * Delta information for advisors
280 *
281 */
282
283 template<class View>
286 return me_negateset(View::modevent(d));
287 }
288
289 template<class View>
290 forceinline int
292 return x.lubMin(d);
293 }
294
295 template<class View>
296 forceinline int
298 return x.lubMax(d);
299 }
300
301 template<class View>
302 forceinline bool
304 return x.lubAny(d);
305 }
306
307 template<class View>
308 forceinline int
310 return x.glbMin(d);
311 }
312
313 template<class View>
314 forceinline int
316 return x.glbMax(d);
317 }
318
319 template<class View>
320 forceinline bool
322 return x.glbAny(d);
323 }
324
325
330 template<class View>
331 class LubRanges<ComplementView<View> > {
332 private:
335 public:
337
338
339 LubRanges(void) {}
343 void init(const ComplementView<View>& x);
345
347
348
349 bool operator ()(void) const;
351 void operator ++(void);
353
355
356
357 int min(void) const;
359 int max(void) const;
361 unsigned int width(void) const;
363 };
364
365 template<class View>
368 : lb(s.base()), lbc(lb) {}
369
370 template<class View>
371 forceinline void
373 lb.init(s.base());
374 lbc.init(lb);
375 }
376
377 template<class View>
378 forceinline bool
379 LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
380
381 template<class View>
382 forceinline void
383 LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
384
385 template<class View>
386 forceinline int
387 LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
388
389 template<class View>
390 forceinline int
391 LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
392
393 template<class View>
394 forceinline unsigned int
395 LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
396
405 template<class View>
407 public LubRanges<View> {
408 public:
410
411
412 LubRanges(void) {}
418 };
419
420 template<class View>
425
426 template<class View>
427 forceinline void
432
437 template<class View>
438 class GlbRanges<ComplementView<View> > {
439 private:
442 public:
444
445
446 GlbRanges(void) {}
450 void init(const ComplementView<View> & x);
452
454
455
456 bool operator ()(void) const;
458 void operator ++(void);
460
462
463
464 int min(void) const;
466 int max(void) const;
468 unsigned int width(void) const;
470 };
471
472 template<class View>
475 : ub(s.base()), ubc(ub) {}
476
477 template<class View>
478 forceinline void
480 ub.init(s.base());
481 ubc.init(ub);
482 }
483
484 template<class View>
485 forceinline bool
486 GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
487
488 template<class View>
489 forceinline void
490 GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
491
492 template<class View>
493 forceinline int
494 GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
495
496 template<class View>
497 forceinline int
498 GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
499
500 template<class View>
501 forceinline unsigned int
502 GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
503
512 template<class View>
514 public GlbRanges<View> {
515 public:
517
518
519 GlbRanges(void) {}
525 };
526
527 template<class View>
532
533 template<class View>
534 forceinline void
539
540 template<class Char, class Traits, class View>
541 std::basic_ostream<Char,Traits>&
542 operator <<(std::basic_ostream<Char,Traits>& os,
543 const ComplementView<View>& x) {
544 std::basic_ostringstream<Char,Traits> s;
545 s.copyfmt(os); s.width(0);
546 s << "(" << x.base() << ")^C";
547 return os << s.str();
548 }
549
550
551 template<class View>
552 forceinline bool
554 return x.base() == y.base();
555 }
556
557 template<class View>
558 forceinline bool
560 return x.base() != y.base();
561 }
562
563}}
564
565// STATISTICS: set-var
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
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
Range iterator for singleton range.
Base-class for propagators.
Definition core.hpp:1064
unsigned int cardMax(void) const
Return cardinality maximum.
Definition set.hpp:81
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition set.hpp:75
int lubMin(void) const
Return minimum element of least upper bound.
Definition set.hpp:84
unsigned int lubSize(void) const
Return number of elements in the least upper bound.
Definition set.hpp:66
int lubMax(void) const
Return maximum element of least upper bound.
Definition set.hpp:87
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
bool contains(int i) const
Test whether i is in greatest lower bound.
Definition set.hpp:72
unsigned int cardMin(void) const
Return cardinality minimum.
Definition set.hpp:78
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
Complement set view.
Definition view.hpp:769
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
static ModEvent me_negateset(ModEvent me)
Negate the modification event me.
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
bool contains(int i) const
Test whether i is in the greatest lower bound.
unsigned int cardMax(void) const
Return maximum cardinality.
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
int glbMin(void) const
Return minimum of the greatest lower bound.
int glbMax(void) const
Return maximum of the greatest lower bound.
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
int lubMax(void) const
Return maximum of the least upper bound.
bool notContains(int i) const
Test whether i is not in the least upper bound.
int lubMin(void) const
Return minimum of the least upper bound.
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
static PropCond pc_negateset(PropCond pc)
Negate the propagation condition pc.
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
ComplementView(void)
Default constructor.
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
unsigned int cardMin(void) const
Return minimum cardinality.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
unsigned int unknownSize(void) const
Return the number of unknown elements.
static ModEvent modevent(const Delta &d)
Return modification event.
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
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int max(void) const
Return largest value of range.
bool operator()(void) const
Test whether iterator is still at a range or done.
void operator++(void)
Move iterator to next range (if possible)
int min(void) const
Return smallest value of range.
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Computation spaces.
Definition core.hpp:1742
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition idx-view.hpp:167
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:401
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:406
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition var-type.hpp:179
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition var-type.hpp:164
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition var-type.hpp:186
const Gecode::PropCond PC_SET_CLUB
Propagate when the cardinality or the least upper bound of a view changes.
Definition var-type.hpp:227
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition var-type.hpp:156
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
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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