this repo has no description
dekker.one
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 <iostream>
39
40namespace Gecode { namespace Set {
41
42 /**
43 * \defgroup TaskActorSetView Set views
44 *
45 * Set propagators and branchings compute with set views.
46 * Set views provide views on set variable implementations,
47 * set constants, and integer variable implementations.
48 * \ingroup TaskActorSet
49 */
50
51 /**
52 * \brief %Set view for set variables
53 * \ingroup TaskActorSetView
54 */
55
56 class SetView : public VarImpView<SetVar> {
57 protected:
58 using VarImpView<SetVar>::x;
59 public:
60 /// \name Constructors and initialization
61 //@{
62 /// Default constructor
63 SetView(void);
64 /// Initialize from set variable \a y
65 SetView(const SetVar& y);
66 /// Initialize from set variable implementation \a y
67 SetView(SetVarImp* y);
68 //@}
69
70 /// \name Value access
71 //@{
72
73 /// Return minimum cardinality
74 unsigned int cardMin(void) const;
75 /// Return maximum cardinality
76 unsigned int cardMax(void) const;
77 /// Return minimum of the least upper bound
78 int lubMin(void) const;
79 /// Return maximum of the least upper bound
80 int lubMax(void) const;
81 /// Return n-th smallest element of the least upper bound
82 int lubMinN(unsigned int n) const;
83 /// Return minimum of the greatest lower bound
84 int glbMin(void) const;
85 /// Return maximum of the greatest lower bound
86 int glbMax(void) const;
87
88 /// Return the number of elements in the greatest lower bound
89 unsigned int glbSize(void) const;
90 /// Return the number of elements in the least upper bound
91 unsigned int lubSize(void) const;
92 /// Return the number of unknown elements
93 unsigned int unknownSize(void) const;
94 //@}
95
96 /// \name Domain tests
97 //@{
98 /// Test whether \a i is in the greatest lower bound
99 bool contains(int i) const;
100 /// Test whether \a i is not in the least upper bound
101 bool notContains(int i) const;
102 //@}
103
104
105 /// \name Domain update by value
106 //@{
107 /// Restrict cardinality to be greater than or equal to \a m
108 ModEvent cardMin(Space& home, unsigned int m);
109 /// Restrict cardinality to be less than or equal to \a m
110 ModEvent cardMax(Space& home, unsigned int m);
111 /**
112 * \brief Update greatest lower bound to include all elements
113 * between and including \a i and \a j
114 */
115 ModEvent include(Space& home,int i,int j);
116 /**
117 * \brief Restrict least upper bound to not contain all elements
118 * between and including \a i and \a j
119 */
120 ModEvent exclude(Space& home,int i,int j);
121 /// Update greatest lower bound to contain \a i
122 ModEvent include(Space& home,int i);
123 /// Restrict least upper bound to not contain \a i
124 ModEvent exclude(Space& home,int i);
125 /**
126 * \brief Update least upper bound to contain at most all elements
127 * between and including \a i and \a j
128 */
129 ModEvent intersect(Space& home,int i,int j);
130 /// Update least upper bound to contain at most the element \a i
131 ModEvent intersect(Space& home,int i);
132 //@}
133
134 /// \name Domain update by range iterator
135 //@{
136
137 /// Remove range sequence described by \a i from least upper bound
138 template<class I> ModEvent excludeI(Space& home, I& i);
139 /// Include range sequence described by \a i in greatest lower bound
140 template<class I> ModEvent includeI(Space& home, I& i);
141 /// Intersect least upper bound with range sequence described by \a i
142 template<class I> ModEvent intersectI(Space& home, I& iter);
143 //@}
144
145 /// \name Delta information for advisors
146 //@{
147 /// Return modification event
148 static ModEvent modevent(const Delta& d);
149 /// Return minimum value just pruned from glb
150 int glbMin(const Delta& d) const;
151 /// Return maximum value just pruned from glb
152 int glbMax(const Delta& d) const;
153 /// Test whether arbitrary values got pruned from glb
154 bool glbAny(const Delta& d) const;
155 /// Return minimum value just pruned from lub
156 int lubMin(const Delta& d) const;
157 /// Return maximum value just pruned from lub
158 int lubMax(const Delta& d) const;
159 /// Test whether arbitrary values got pruned from lub
160 bool lubAny(const Delta& d) const;
161 //@}
162 };
163
164 /**
165 * \brief Print set variable view
166 * \relates Gecode::Set::SetView
167 */
168 template<class Char, class Traits>
169 std::basic_ostream<Char,Traits>&
170 operator <<(std::basic_ostream<Char,Traits>& os, const SetView& x);
171
172
173
174 // Forward declarations for friends
175 class ConstSetView;
176 bool operator ==(const ConstSetView&, const ConstSetView&);
177 bool operator !=(const ConstSetView&, const ConstSetView&);
178
179 /**
180 * \brief Constant view
181 *
182 * A constant set view \f$x\f$ for a set \f$s\f$ provides operations such
183 * that \f$x\f$ behaves like \f$s\f$.
184 * \ingroup TaskActorSetView
185 */
186 class ConstSetView : public ConstView<SetView> {
187 friend class LubRanges<ConstSetView>;
188 friend class GlbRanges<ConstSetView>;
189 friend bool Gecode::Set::operator ==(const Gecode::Set::ConstSetView&,
190 const Gecode::Set::ConstSetView&);
191 friend bool Gecode::Set::operator !=(const Gecode::Set::ConstSetView&,
192 const Gecode::Set::ConstSetView&);
193 private:
194 int *ranges;
195 int size;
196 unsigned int domSize;
197 public:
198 /// \name Constructors and initialization
199 //@{
200 /// Default constructor
201 ConstSetView(void);
202 /// Construct with \a s as the domain
203 ConstSetView(Space& home, const IntSet& s);
204 //@}
205
206 /// \name Value access
207 //@{
208 /// Return minimum cardinality
209 unsigned int cardMin(void) const;
210 /// Return maximum cardinality
211 unsigned int cardMax(void) const;
212 /// Return minimum of the least upper bound
213 int lubMin(void) const;
214 /// Return maximum of the least upper bound
215 int lubMax(void) const;
216 /// Return n-th smallest element of the least upper bound
217 int lubMinN(unsigned int n) const;
218 /// Return minimum of the greatest lower bound
219 int glbMin(void) const;
220 /// Return maximum of the greatest lower bound
221 int glbMax(void) const;
222
223 /// Return the number of elements in the greatest lower bound
224 unsigned int glbSize(void) const;
225 /// Return the number of elements in the least upper bound
226 unsigned int lubSize(void) const;
227 /// Return the number of unknown elements
228 unsigned int unknownSize(void) const;
229 //@}
230
231 /// \name Domain tests
232 //@{
233 /// Test whether \a i is in the greatest lower bound
234 bool contains(int i) const;
235 /// Test whether \a i is not in the least upper bound
236 bool notContains(int i) const;
237 //@}
238
239
240 /// \name Domain update by value
241 //@{
242 /// Restrict cardinality to be greater than or equal to \a m
243 ModEvent cardMin(Space& home, unsigned int m);
244 /// Restrict cardinality to be less than or equal to \a m
245 ModEvent cardMax(Space& home, unsigned int m);
246 /**
247 * \brief Update greatest lower bound to include all elements
248 * between and including \a i and \a j
249 */
250 ModEvent include(Space& home,int i,int j);
251 /**
252 * \brief Restrict least upper bound to not contain all elements
253 * between and including \a i and \a j
254 */
255 ModEvent exclude(Space& home,int i,int j);
256 /// Update greatest lower bound to contain \a i
257 ModEvent include(Space& home,int i);
258 /// Restrict least upper bound to not contain \a i
259 ModEvent exclude(Space& home,int i);
260 /**
261 * \brief Update least upper bound to contain at most all elements
262 * between and including \a i and \a j
263 */
264 ModEvent intersect(Space& home,int i,int j);
265 /// Update least upper bound to contain at most the element \a i
266 ModEvent intersect(Space& home,int i);
267 //@}
268
269 /// \name Domain update by range iterator
270 //@{
271
272 /// Remove range sequence described by \a i from least upper bound
273 template<class I> ModEvent excludeI(Space& home, I& i);
274 /// Include range sequence described by \a i in greatest lower bound
275 template<class I> ModEvent includeI(Space& home, I& i);
276 /// Intersect least upper bound with range sequence described by \a i
277 template<class I> ModEvent intersectI(Space& home, I& iter);
278 //@}
279
280 /// \name Cloning
281 //@{
282 /// Update this view to be a clone of view \a y
283 void update(Space& home, ConstSetView& y);
284 //@}
285
286 /// \name Delta information for advisors
287 //@{
288 /// Return minimum value just pruned from glb
289 int glbMin(const Delta& d) const;
290 /// Return maximum value just pruned from glb
291 int glbMax(const Delta& d) const;
292 /// Test whether arbitrary values got pruned from glb
293 bool glbAny(const Delta& d) const;
294 /// Return minimum value just pruned from lub
295 int lubMin(const Delta& d) const;
296 /// Return maximum value just pruned from lub
297 int lubMax(const Delta& d) const;
298 /// Test whether arbitrary values got pruned from lub
299 bool lubAny(const Delta& d) const;
300 //@}
301
302 /// \name Ordering
303 //@{
304 /// Whether this view comes before view \a y (arbitray order)
305 bool operator <(const ConstSetView& y) const;
306 //@}
307 };
308
309 /**
310 * \brief Print constant set view
311 * \relates Gecode::Set::ConstSetView
312 */
313 template<class Char, class Traits>
314 std::basic_ostream<Char,Traits>&
315 operator <<(std::basic_ostream<Char,Traits>& os, const ConstSetView& x);
316
317 /** \name View comparison
318 * \relates Gecode::Set::ConstSetView
319 */
320 //@{
321 /// Test whether views \a x and \a y are the same
322 bool operator ==(const ConstSetView& x, const ConstSetView& y);
323 /// Test whether views \a x and \a y are not the same
324 bool operator !=(const ConstSetView& x, const ConstSetView& y);
325 //@}
326
327
328 /**
329 * \brief Constant view for the empty set
330 *
331 * A constant set view \f$x\f$ for the empty set provides operations such
332 * that \f$x\f$ behaves like the empty set.
333 * \ingroup TaskActorSetView
334 */
335
336 class EmptyView : public ConstView<SetView> {
337 public:
338 /// \name Constructors and initialization
339 //@{
340 /// Default constructor
341 EmptyView(void);
342 //@}
343
344 /// \name Value access
345 //@{
346 /// Return minimum cardinality
347 unsigned int cardMin(void) const;
348 /// Return maximum cardinality
349 unsigned int cardMax(void) const;
350 /// Return minimum of the least upper bound
351 int lubMin(void) const;
352 /// Return maximum of the least upper bound
353 int lubMax(void) const;
354 /// Return n-th smallest element of the least upper bound
355 int lubMinN(unsigned int n) const;
356 /// Return minimum of the greatest lower bound
357 int glbMin(void) const;
358 /// Return maximum of the greatest lower bound
359 int glbMax(void) const;
360
361 /// Return the number of elements in the greatest lower bound
362 unsigned int glbSize(void) const;
363 /// Return the number of elements in the least upper bound
364 unsigned int lubSize(void) const;
365 /// Return the number of unknown elements
366 unsigned int unknownSize(void) const;
367 //@}
368
369 /// \name Domain tests
370 //@{
371 /// Test whether \a i is in the greatest lower bound
372 bool contains(int i) const;
373 /// Test whether \a i is not in the least upper bound
374 bool notContains(int i) const;
375 //@}
376
377
378 /// \name Domain update by value
379 //@{
380 /// Restrict cardinality to be greater than or equal to \a m
381 ModEvent cardMin(Space& home, unsigned int m);
382 /// Restrict cardinality to be less than or equal to \a m
383 ModEvent cardMax(Space& home, unsigned int m);
384 /**
385 * \brief Update greatest lower bound to include all elements
386 * between and including \a i and \a j
387 */
388 ModEvent include(Space& home,int i,int j);
389 /**
390 * \brief Restrict least upper bound to not contain all elements
391 * between and including \a i and \a j
392 */
393 ModEvent exclude(Space& home,int i,int j);
394 /// Update greatest lower bound to contain \a i
395 ModEvent include(Space& home,int i);
396 /// Restrict least upper bound to not contain \a i
397 ModEvent exclude(Space& home,int i);
398 /**
399 * \brief Update least upper bound to contain at most all elements
400 * between and including \a i and \a j
401 */
402 ModEvent intersect(Space& home,int i,int j);
403 /// Update least upper bound to contain at most the element \a i
404 ModEvent intersect(Space& home,int i);
405 //@}
406
407 /// \name Domain update by range iterator
408 //@{
409
410 /// Remove range sequence described by \a i from least upper bound
411 template<class I> ModEvent excludeI(Space& home, I& i);
412 /// Include range sequence described by \a i in greatest lower bound
413 template<class I> ModEvent includeI(Space& home, I& i);
414 /// Intersect least upper bound with range sequence described by \a i
415 template<class I> ModEvent intersectI(Space& home, I& iter);
416 //@}
417
418 /// \name Delta information for advisors
419 //@{
420 /// Return minimum value just pruned from glb
421 int glbMin(const Delta& d) const;
422 /// Return maximum value just pruned from glb
423 int glbMax(const Delta& d) const;
424 /// Test whether arbitrary values got pruned from glb
425 bool glbAny(const Delta& d) const;
426 /// Return minimum value just pruned from lub
427 int lubMin(const Delta& d) const;
428 /// Return maximum value just pruned from lub
429 int lubMax(const Delta& d) const;
430 /// Test whether arbitrary values got pruned from lub
431 bool lubAny(const Delta& d) const;
432 //@}
433
434 };
435
436 /**
437 * \brief Print empty set view
438 * \relates Gecode::Set::EmptyView
439 */
440 template<class Char, class Traits>
441 std::basic_ostream<Char,Traits>&
442 operator <<(std::basic_ostream<Char,Traits>& os, const EmptyView& x);
443
444
445 /** \name View comparison
446 * \relates Gecode::Set::EmptyView
447 */
448 //@{
449 /// Test whether views \a x and \a y are the same
450 bool operator ==(const EmptyView& x, const EmptyView& y);
451 /// Test whether views \a x and \a y are the same
452 bool operator !=(const EmptyView& x, const EmptyView& y);
453 //@}
454
455
456 /**
457 * \brief Constant view for the universe
458 *
459 * A constant set view \f$x\f$ for the universe provides operations such
460 * that \f$x\f$ behaves like the universe.
461 * \ingroup TaskActorSetView
462 */
463
464 class UniverseView : public ConstView<SetView> {
465 public:
466 /// \name Constructors and initialization
467 //@{
468 /// Default constructor
469 UniverseView(void);
470 //@}
471
472 /// \name Value access
473 //@{
474
475 /// Return minimum cardinality
476 unsigned int cardMin(void) const;
477 /// Return maximum cardinality
478 unsigned int cardMax(void) const;
479 /// Return minimum of the least upper bound
480 int lubMin(void) const;
481 /// Return maximum of the least upper bound
482 int lubMax(void) const;
483 /// Return n-th smallest element of the least upper bound
484 int lubMinN(unsigned int n) const;
485 /// Return minimum of the greatest lower bound
486 int glbMin(void) const;
487 /// Return maximum of the greatest lower bound
488 int glbMax(void) const;
489
490 /// Return the number of elements in the greatest lower bound
491 unsigned int glbSize(void) const;
492 /// Return the number of elements in the least upper bound
493 unsigned int lubSize(void) const;
494 /// Return the number of unknown elements
495 unsigned int unknownSize(void) const;
496 //@}
497
498 /// \name Domain tests
499 //@{
500 /// Test whether \a i is in the greatest lower bound
501 bool contains(int i) const;
502 /// Test whether \a i is not in the least upper bound
503 bool notContains(int i) const;
504 //@}
505
506
507 /// \name Domain update by value
508 //@{
509 /// Restrict cardinality to be greater than or equal to \a m
510 ModEvent cardMin(Space& home, unsigned int m);
511 /// Restrict cardinality to be less than or equal to \a m
512 ModEvent cardMax(Space& home, unsigned int m);
513 /**
514 * \brief Update greatest lower bound to include all elements
515 * between and including \a i and \a j
516 */
517 ModEvent include(Space& home,int i,int j);
518 /**
519 * \brief Restrict least upper bound to not contain all elements
520 * between and including \a i and \a j
521 */
522 ModEvent exclude(Space& home,int i,int j);
523 /// Update greatest lower bound to contain \a i
524 ModEvent include(Space& home,int i);
525 /// Restrict least upper bound to not contain \a i
526 ModEvent exclude(Space& home,int i);
527 /**
528 * \brief Update least upper bound to contain at most all elements
529 * between and including \a i and \a j
530 */
531 ModEvent intersect(Space& home,int i,int j);
532 /// Update least upper bound to contain at most the element \a i
533 ModEvent intersect(Space& home,int i);
534 //@}
535
536 /// \name Domain update by range iterator
537 //@{
538
539 /// Remove range sequence described by \a i from least upper bound
540 template<class I> ModEvent excludeI(Space& home, I& i);
541 /// Include range sequence described by \a i in greatest lower bound
542 template<class I> ModEvent includeI(Space& home, I& i);
543 /// Intersect least upper bound with range sequence described by \a i
544 template<class I> ModEvent intersectI(Space& home, I& iter);
545 //@}
546
547 /// \name Delta information for advisors
548 //@{
549 /// Return minimum value just pruned from glb
550 int glbMin(const Delta& d) const;
551 /// Return maximum value just pruned from glb
552 int glbMax(const Delta& d) const;
553 /// Test whether arbitrary values got pruned from glb
554 bool glbAny(const Delta& d) const;
555 /// Return minimum value just pruned from lub
556 int lubMin(const Delta& d) const;
557 /// Return maximum value just pruned from lub
558 int lubMax(const Delta& d) const;
559 /// Test whether arbitrary values got pruned from lub
560 bool lubAny(const Delta& d) const;
561 //@}
562
563 };
564
565 /**
566 * \brief Print universe set view
567 * \relates Gecode::Set::UniverseView
568 */
569 template<class Char, class Traits>
570 std::basic_ostream<Char,Traits>&
571 operator <<(std::basic_ostream<Char,Traits>& os, const UniverseView& x);
572
573
574 /** \name View comparison
575 * \relates Gecode::Set::UniverseView
576 */
577 //@{
578 /// Test whether views \a x and \a y are the same
579 bool operator ==(const UniverseView& x, const UniverseView& y);
580 /// Test whether views \a x and \a y are the not same
581 bool operator !=(const UniverseView& x, const UniverseView& y);
582 //@}
583
584
585
586 /**
587 * \brief Singleton set view
588 *
589 * A singleton set view \f$s\f$ for an integer view \f$x\f$ provides
590 * operations such that \f$s\f$ behaves like the singleton set \f$\{x\}\f$.
591 * \ingroup TaskActorSetView
592 */
593
594 class SingletonView : public DerivedView<Gecode::Int::IntView> {
595 protected:
596 using DerivedView<Gecode::Int::IntView>::x;
597
598 /// Convert set variable PropCond \a pc to a PropCond for integer variables
599 static PropCond pc_settoint(PropCond pc);
600 /// Convert integer variable ModEvent \a me to a ModEvent for set variables
601 static ModEvent me_inttoset(ModEvent me);
602 /// Convert set variable ModEvent \a me to a ModEvent for integer variables
603 static ModEvent me_settoint(ModEvent me);
604
605 public:
606 /// \name Constructors and initialization
607 //@{
608 /// Default constructor
609 SingletonView(void);
610 /// Initialize with integer view \a y
611 SingletonView(Gecode::Int::IntView& y);
612 /// Initialize with integer variable \a y
613 SingletonView(const Gecode::IntVar& y);
614 //@}
615
616 /// \name Value access
617 //@{
618
619 /// Return minimum cardinality
620 unsigned int cardMin(void) const;
621 /// Return maximum cardinality
622 unsigned int cardMax(void) const;
623 /// Return minimum of the least upper bound
624 int lubMin(void) const;
625 /// Return maximum of the least upper bound
626 int lubMax(void) const;
627 /// Return n-th smallest element of the least upper bound
628 int lubMinN(unsigned int n) const;
629 /// Return minimum of the greatest lower bound
630 int glbMin(void) const;
631 /// Return maximum of the greatest lower bound
632 int glbMax(void) const;
633
634 /// Return the number of elements in the greatest lower bound
635 unsigned int glbSize(void) const;
636 /// Return the number of elements in the least upper bound
637 unsigned int lubSize(void) const;
638 /// Return the number of unknown elements
639 unsigned int unknownSize(void) const;
640 //@}
641
642 /// \name Domain tests
643 //@{
644 /// Test whether \a i is in the greatest lower bound
645 bool contains(int i) const;
646 /// Test whether \a i is not in the least upper bound
647 bool notContains(int i) const;
648 //@}
649
650
651 /// \name Domain update by value
652 //@{
653 /// Restrict cardinality to be greater than or equal to \a m
654 ModEvent cardMin(Space& home, unsigned int m);
655 /// Restrict cardinality to be less than or equal to \a m
656 ModEvent cardMax(Space& home, unsigned int m);
657 /**
658 * \brief Update greatest lower bound to include all elements
659 * between and including \a i and \a j
660 */
661 ModEvent include(Space& home,int i,int j);
662 /**
663 * \brief Restrict least upper bound to not contain all elements
664 * between and including \a i and \a j
665 */
666 ModEvent exclude(Space& home,int i,int j);
667 /// Update greatest lower bound to contain \a i
668 ModEvent include(Space& home,int i);
669 /// Restrict least upper bound to not contain \a i
670 ModEvent exclude(Space& home,int i);
671 /**
672 * \brief Update least upper bound to contain at most all elements
673 * between and including \a i and \a j
674 */
675 ModEvent intersect(Space& home,int i,int j);
676 /// Update least upper bound to contain at most the element \a i
677 ModEvent intersect(Space& home,int i);
678 //@}
679
680 /// \name Domain update by range iterator
681 //@{
682
683 /// Remove range sequence described by \a i from least upper bound
684 template<class I> ModEvent excludeI(Space& home, I& i);
685 /// Include range sequence described by \a i in greatest lower bound
686 template<class I> ModEvent includeI(Space& home, I& i);
687 /// Intersect least upper bound with range sequence described by \a i
688 template<class I> ModEvent intersectI(Space& home, I& iter);
689 //@}
690
691 /// \name View-dependent propagator support
692 //@{
693 /// Schedule propagator \a p with modification event \a me
694 static void schedule(Space& home, Propagator& p, ModEvent me);
695 /// Return modification event for view type in \a med
696 static ModEvent me(const ModEventDelta& med);
697 /// Translate modification event \a me to modification event delta for view
698 static ModEventDelta med(ModEvent);
699 //@}
700
701 /// \name Dependencies
702 //@{
703 /**
704 * \brief Subscribe propagator \a p with propagation condition \a pc to view
705 *
706 * In case \a schedule is false, the propagator is just subscribed but
707 * not scheduled for execution (this must be used when creating
708 * subscriptions during propagation).
709 */
710 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
711 /// Cancel subscription of propagator \a p with propagation condition \a pc to view
712 void cancel(Space& home, Propagator& p, PropCond pc);
713 /// Re-schedule propagator \a p with propagation condition \a pc
714 void reschedule(Space& home, Propagator& p, PropCond pc);
715 /// Subscribe advisor \a a to view
716 void subscribe(Space& home, Advisor& a);
717 /// Cancel subscription of advisor \a a
718 void cancel(Space& home, Advisor& a);
719 //@}
720
721 /// \name Delta information for advisors
722 //@{
723 /// Return modification event
724 static ModEvent modevent(const Delta& d);
725 /// Return minimum value just pruned from glb
726 int glbMin(const Delta& d) const;
727 /// Return maximum value just pruned from glb
728 int glbMax(const Delta& d) const;
729 /// Test whether arbitrary values got pruned from glb
730 bool glbAny(const Delta& d) const;
731 /// Return minimum value just pruned from lub
732 int lubMin(const Delta& d) const;
733 /// Return maximum value just pruned from lub
734 int lubMax(const Delta& d) const;
735 /// Test whether arbitrary values got pruned from lub
736 bool lubAny(const Delta& d) const;
737 //@}
738
739 };
740
741 /**
742 * \brief Print singleton set view
743 * \relates Gecode::Set::SingletonView
744 */
745 template<class Char, class Traits>
746 std::basic_ostream<Char,Traits>&
747 operator <<(std::basic_ostream<Char,Traits>& os, const SingletonView& x);
748
749 /** \name View comparison
750 * \relates Gecode::Set::SingletonView
751 */
752 //@{
753 /// Test whether views \a x and \a y are the same
754 bool operator ==(const SingletonView& x, const SingletonView& y);
755 /// Test whether views \a x and \a y are the not same
756 bool operator !=(const SingletonView& x, const SingletonView& y);
757 //@}
758
759 /**
760 * \brief Complement set view
761 *
762 * A complement set view \f$s\f$ for a set view \f$t\f$ provides
763 * operations such that \f$s\f$ behaves like the complement of \f$\{t\}\f$.
764 * The complement is defined in terms of the set universe.
765 * \ingroup TaskActorSetView
766 */
767
768 template<class View>
769 class ComplementView : public DerivedView<View> {
770 protected:
771 using DerivedView<View>::x;
772
773 public:
774 /// Negate the propagation condition \a pc
775 static PropCond pc_negateset(PropCond pc);
776 /// Negate the modification event \a me
777 static ModEvent me_negateset(ModEvent me);
778
779 /// \name Constructors and initialization
780 //@{
781 /// Default constructor
782 ComplementView(void);
783 /// Initialize with set view \a y
784 explicit ComplementView(View& y);
785 //@}
786
787 /// \name Value access
788 //@{
789
790 /// Return minimum cardinality
791 unsigned int cardMin(void) const;
792 /// Return maximum cardinality
793 unsigned int cardMax(void) const;
794 /// Return minimum of the least upper bound
795 int lubMin(void) const;
796 /// Return maximum of the least upper bound
797 int lubMax(void) const;
798 /// Return \a n-th smallest element of the least upper bound
799 int lubMinN(unsigned int n) const;
800 /// Return minimum of the greatest lower bound
801 int glbMin(void) const;
802 /// Return maximum of the greatest lower bound
803 int glbMax(void) const;
804
805 /// Return the number of elements in the greatest lower bound
806 unsigned int glbSize(void) const;
807 /// Return the number of elements in the least upper bound
808 unsigned int lubSize(void) const;
809 /// Return the number of unknown elements
810 unsigned int unknownSize(void) const;
811 //@}
812
813 /// \name Domain tests
814 //@{
815 /// Test whether \a i is in the greatest lower bound
816 bool contains(int i) const;
817 /// Test whether \a i is not in the least upper bound
818 bool notContains(int i) const;
819 //@}
820
821
822 /// \name Domain update by value
823 //@{
824 /// Restrict cardinality to be greater than or equal to \a m
825 ModEvent cardMin(Space& home, unsigned int m);
826 /// Restrict cardinality to be less than or equal to \a m
827 ModEvent cardMax(Space& home, unsigned int m);
828 /**
829 * \brief Update greatest lower bound to include all elements
830 * between and including \a i and \a j
831 */
832 ModEvent include(Space& home,int i,int j);
833 /**
834 * \brief Restrict least upper bound to not contain all elements
835 * between and including \a i and \a j
836 */
837 ModEvent exclude(Space& home,int i,int j);
838 /// Update greatest lower bound to contain \a i
839 ModEvent include(Space& home,int i);
840 /// Restrict least upper bound to not contain \a i
841 ModEvent exclude(Space& home,int i);
842 /**
843 * \brief Update least upper bound to contain at most all elements
844 * between and including \a i and \a j
845 */
846 ModEvent intersect(Space& home,int i,int j);
847 /// Update least upper bound to contain at most the element \a i
848 ModEvent intersect(Space& home,int i);
849 //@}
850
851 /// \name Domain update by range iterator
852 //@{
853
854 /// Remove range sequence described by \a i from least upper bound
855 template<class I> ModEvent excludeI(Space& home, I& i);
856 /// Include range sequence described by \a i in greatest lower bound
857 template<class I> ModEvent includeI(Space& home, I& i);
858 /// Intersect least upper bound with range sequence described by \a i
859 template<class I> ModEvent intersectI(Space& home, I& iter);
860 //@}
861
862 /// \name View-dependent propagator support
863 //@{
864 /// Schedule propagator \a p with modification event \a me
865 static void schedule(Space& home, Propagator& p, ModEvent me);
866 /// Return modification event for view type in \a med
867 static ModEvent me(const ModEventDelta& med);
868 /// Translate modification event \a me to modification event delta for view
869 static ModEventDelta med(ModEvent);
870 //@}
871
872 /// \name Dependencies
873 //@{
874 /**
875 * \brief Subscribe propagator \a p with propagation condition \a pc to view
876 *
877 * In case \a schedule is false, the propagator is just subscribed but
878 * not scheduled for execution (this must be used when creating
879 * subscriptions during propagation).
880 */
881 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
882 /// Cancel subscription of propagator \a p with propagation condition \a pc to view
883 void cancel(Space& home, Propagator& p, PropCond pc);
884 /// Subscribe advisor \a a to view
885 void subscribe(Space& home, Advisor& a);
886 /// Cancel subscription of advisor \a a
887 void cancel(Space& home, Advisor& a);
888 //@}
889
890 /// \name Delta information for advisors
891 //@{
892 /// Return modification event
893 static ModEvent modevent(const Delta& d);
894 /// Return minimum value just pruned from glb
895 int glbMin(const Delta& d) const;
896 /// Return maximum value just pruned from glb
897 int glbMax(const Delta& d) const;
898 /// Test whether arbitrary values got pruned from glb
899 bool glbAny(const Delta& d) const;
900 /// Return minimum value just pruned from lub
901 int lubMin(const Delta& d) const;
902 /// Return maximum value just pruned from lub
903 int lubMax(const Delta& d) const;
904 /// Test whether arbitrary values got pruned from lub
905 bool lubAny(const Delta& d) const;
906 //@}
907
908 };
909
910 /**
911 * \brief Print complement set view
912 * \relates Gecode::Set::ComplementView
913 */
914 template<class Char, class Traits, class View>
915 std::basic_ostream<Char,Traits>&
916 operator <<(std::basic_ostream<Char,Traits>& os,
917 const ComplementView<View>& x);
918
919 /** \name View comparison
920 * \relates Gecode::Set::ComplementView
921 */
922 //@{
923 /// Test whether views \a x and \a y are the same
924 template<class View>
925 bool operator ==(const ComplementView<View>& x,
926 const ComplementView<View>& y);
927 /// Test whether views \a x and \a y are the not same
928 template<class View>
929 bool operator !=(const ComplementView<View>& x,
930 const ComplementView<View>& y);
931 //@}
932
933 template<class View> class LubDiffRanges;
934 template<class View> class GlbDiffRanges;
935
936 /**
937 * \brief Cached set view
938 *
939 * A cached set view \f$s\f$ for a set view \f$t\f$ adds operations
940 * for cacheing the current domain of \f$t\f$ and comparing the current
941 * domain to the cached domain. Cached views make it easy to implement
942 * incremental propagation algorithms.
943 *
944 * \ingroup TaskActorSetView
945 */
946
947 template<class View>
948 class CachedView : public DerivedView<View> {
949 friend class LubDiffRanges<View>;
950 friend class GlbDiffRanges<View>;
951 protected:
952 using DerivedView<View>::x;
953
954 /// The cached least upper bound
955 LUBndSet lubCache;
956 /// The cached greatest lower bound
957 GLBndSet glbCache;
958
959 public:
960
961 /// \name Constructors and initialization
962 //@{
963 /// Default constructor
964 CachedView(void);
965 /// Initialize with set view \a y
966 explicit CachedView(const View& y);
967 //@}
968
969 /// \name Value access
970 //@{
971
972 /// Return minimum cardinality
973 unsigned int cardMin(void) const;
974 /// Return maximum cardinality
975 unsigned int cardMax(void) const;
976 /// Return minimum of the least upper bound
977 int lubMin(void) const;
978 /// Return maximum of the least upper bound
979 int lubMax(void) const;
980 /// Return \a n-th smallest element of the least upper bound
981 int lubMinN(unsigned int n) const;
982 /// Return minimum of the greatest lower bound
983 int glbMin(void) const;
984 /// Return maximum of the greatest lower bound
985 int glbMax(void) const;
986
987 /// Return the number of elements in the greatest lower bound
988 unsigned int glbSize(void) const;
989 /// Return the number of elements in the least upper bound
990 unsigned int lubSize(void) const;
991 /// Return the number of unknown elements
992 unsigned int unknownSize(void) const;
993 //@}
994
995 /// \name Domain tests
996 //@{
997 /// Test whether \a i is in the greatest lower bound
998 bool contains(int i) const;
999 /// Test whether \a i is not in the least upper bound
1000 bool notContains(int i) const;
1001 //@}
1002
1003
1004 /// \name Domain update by value
1005 //@{
1006 /// Restrict cardinality to be greater than or equal to \a m
1007 ModEvent cardMin(Space& home, unsigned int m);
1008 /// Restrict cardinality to be less than or equal to \a m
1009 ModEvent cardMax(Space& home, unsigned int m);
1010 /**
1011 * \brief Update greatest lower bound to include all elements
1012 * between and including \a i and \a j
1013 */
1014 ModEvent include(Space& home,int i,int j);
1015 /**
1016 * \brief Restrict least upper bound to not contain all elements
1017 * between and including \a i and \a j
1018 */
1019 ModEvent exclude(Space& home,int i,int j);
1020 /// Update greatest lower bound to contain \a i
1021 ModEvent include(Space& home,int i);
1022 /// Restrict least upper bound to not contain \a i
1023 ModEvent exclude(Space& home,int i);
1024 /**
1025 * \brief Update least upper bound to contain at most all elements
1026 * between and including \a i and \a j
1027 */
1028 ModEvent intersect(Space& home,int i,int j);
1029 /// Update least upper bound to contain at most the element \a i
1030 ModEvent intersect(Space& home,int i);
1031 //@}
1032
1033 /// \name Domain update by range iterator
1034 //@{
1035
1036 /// Remove range sequence described by \a i from least upper bound
1037 template<class I> ModEvent excludeI(Space& home, I& i);
1038 /// Include range sequence described by \a i in greatest lower bound
1039 template<class I> ModEvent includeI(Space& home, I& i);
1040 /// Intersect least upper bound with range sequence described by \a i
1041 template<class I> ModEvent intersectI(Space& home, I& iter);
1042 //@}
1043
1044 /// \name View-dependent propagator support
1045 //@{
1046 /// Schedule propagator \a p with modification event \a me
1047 static void schedule(Space& home, Propagator& p, ModEvent me);
1048 /// Return modification event for view type in \a med
1049 static ModEvent me(const ModEventDelta& med);
1050 /// Translate modification event \a me to modification event delta for view
1051 static ModEventDelta med(ModEvent);
1052 //@}
1053
1054 /// \name Dependencies
1055 //@{
1056 /**
1057 * \brief Subscribe propagator \a p with propagation condition \a pc to view
1058 *
1059 * In case \a schedule is false, the propagator is just subscribed but
1060 * not scheduled for execution (this must be used when creating
1061 * subscriptions during propagation).
1062 */
1063 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
1064 /// Cancel subscription of propagator \a p with propagation condition \a pc to view
1065 void cancel(Space& home, Propagator& p, PropCond pc);
1066 /// Subscribe advisor \a a to view
1067 void subscribe(Space& home, Advisor& a);
1068 /// Cancel subscription of advisor \a a
1069 void cancel(Space& home, Advisor& a);
1070 //@}
1071
1072 /// \name Delta information for advisors
1073 //@{
1074 /// Return modification event
1075 static ModEvent modevent(const Delta& d);
1076 /// Return minimum value just pruned from glb
1077 int glbMin(const Delta& d) const;
1078 /// Return maximum value just pruned from glb
1079 int glbMax(const Delta& d) const;
1080 /// Test whether arbitrary values got pruned from glb
1081 bool glbAny(const Delta& d) const;
1082 /// Return minimum value just pruned from lub
1083 int lubMin(const Delta& d) const;
1084 /// Return maximum value just pruned from lub
1085 int lubMax(const Delta& d) const;
1086 /// Test whether arbitrary values got pruned from lub
1087 bool lubAny(const Delta& d) const;
1088 //@}
1089
1090 /// \name Domain cache operations
1091 //@{
1092 /// Initialize cache to bounds \a glb and \a lub
1093 void initCache(Space& home, const IntSet& glb, const IntSet& lub);
1094 /// Update greatest lower bound cache to current domain
1095 void cacheGlb(Space& home);
1096 /// Update least upper bound cache to current domain
1097 void cacheLub(Space& home);
1098 /// Check whether greatest lower bound cache differs from current domain
1099 bool glbModified(void) const;
1100 /// Check whether least upper bound cache differs from current domain
1101 bool lubModified(void) const;
1102 //@}
1103
1104 /// \name Cloning
1105 //@{
1106 /// Update this view to be a clone of view \a y
1107 void update(Space& home, CachedView<View>& y);
1108 //@}
1109 };
1110
1111 /**
1112 * \brief Print cached set view
1113 * \relates Gecode::Set::CachedView
1114 */
1115 template<class Char, class Traits, class View>
1116 std::basic_ostream<Char,Traits>&
1117 operator <<(std::basic_ostream<Char,Traits>& os,
1118 const CachedView<View>& x);
1119
1120 /** \name View comparison
1121 * \relates Gecode::Set::CachedView
1122 */
1123 //@{
1124 /// Test whether views \a x and \a y are the same
1125 template<class View>
1126 bool operator ==(const CachedView<View>& x, const CachedView<View>& y);
1127 /// Test whether views \a x and \a y are the not same
1128 template<class View>
1129 bool operator !=(const CachedView<View>& x, const CachedView<View>& y);
1130 //@}
1131
1132 /**
1133 * \brief %Range iterator for difference of greatest lower bound and cache
1134 * \relates Gecode::Set::CachedView
1135 */
1136 template<class View>
1137 class GlbDiffRanges
1138 : public Iter::Ranges::Diff<GlbRanges<View>,BndSetRanges> {
1139 protected:
1140 /// Lower bound iterator
1141 GlbRanges<View> gr;
1142 /// Cached lower bound
1143 BndSetRanges cr;
1144 public:
1145 /// Constructor
1146 GlbDiffRanges(const CachedView<View>& x);
1147 };
1148
1149 /**
1150 * \brief %Range iterator for difference of least upper bound and cache
1151 * \relates Gecode::Set::CachedView
1152 */
1153 template<class View>
1154 class LubDiffRanges
1155 : public Iter::Ranges::Diff<BndSetRanges,LubRanges<View> > {
1156 protected:
1157 /// Cached upper bound
1158 BndSetRanges cr;
1159 /// Upper bound iterator
1160 LubRanges<View> lr;
1161 public:
1162 /// Constructor
1163 LubDiffRanges(const CachedView<View>& x);
1164 };
1165
1166}}
1167
1168#include <gecode/set/var/set.hpp>
1169
1170#include <gecode/set/view/set.hpp>
1171
1172#include <gecode/set/view/const.hpp>
1173#include <gecode/set/view/singleton.hpp>
1174#include <gecode/set/view/complement.hpp>
1175#include <gecode/set/view/cached.hpp>
1176
1177#include <gecode/set/view/print.hpp>
1178#include <gecode/set/var/print.hpp>
1179
1180// STATISTICS: set-var