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 * Gabor Szokoli <szokoli@gecode.org> 9 * 10 * Copyright: 11 * Guido Tack, 2004 12 * Christian Schulte, 2004 13 * Gabor Szokoli, 2004 14 * 15 * This file is part of Gecode, the generic constraint 16 * development environment: 17 * http://www.gecode.org 18 * 19 * Permission is hereby granted, free of charge, to any person obtaining 20 * a copy of this software and associated documentation files (the 21 * "Software"), to deal in the Software without restriction, including 22 * without limitation the rights to use, copy, modify, merge, publish, 23 * distribute, sublicense, and/or sell copies of the Software, and to 24 * permit persons to whom the Software is furnished to do so, subject to 25 * the following conditions: 26 * 27 * The above copyright notice and this permission notice shall be 28 * included in all copies or substantial portions of the Software. 29 * 30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 37 * 38 */ 39 40 #include <iostream> 41 42 namespace Gecode { namespace Set { 43 44 class SetVarImp; 45 class LUBndSet; 46 class GLBndSet; 47 48 /** 49 * \brief Finite set delta information for advisors 50 * 51 */ 52 class SetDelta : public Delta { 53 friend class SetVarImp; 54 friend class LUBndSet; 55 friend class GLBndSet; 56 private: 57 int _glbMin; ///< Minimum glb value just pruned 58 int _glbMax; ///< Largest glb value just pruned 59 int _lubMin; ///< Minimum lub value just pruned 60 int _lubMax; ///< Largest lub value just pruned 61 public: 62 /// Create set delta as providing no information (if \a any is true) 63 SetDelta(void); 64 /// Create set delta with \a min and \a max 65 SetDelta(int glbMin, int glbMax, int lubMin, int lubMax); 66 /// Return glb minimum 67 int glbMin(void) const; 68 /// Return glb maximum 69 int glbMax(void) const; 70 /// Return lub minimum 71 int lubMin(void) const; 72 /// Return lub maximum 73 int lubMax(void) const; 74 /// Test whether delta represents any domain change in glb 75 bool glbAny(void) const; 76 /// Test whether delta represents any domain change in lub 77 bool lubAny(void) const; 78 }; 79 80 }} 81 82 #include <gecode/set/var-imp/delta.hpp> 83 84 namespace Gecode { namespace Set { 85 86 /** 87 * \brief Sets of integers 88 */ 89 class BndSet { 90 private: 91 RangeList* first; 92 RangeList* last; 93 protected: 94 /// The size of this set 95 unsigned int _size; 96 /// The cardinality this set represents 97 unsigned int _card; 98 /// Set first range to \a r 99 void fst(RangeList* r); 100 /// Set last range to \a r 101 void lst(RangeList* r); 102 103 /// Return first range 104 RangeList* fst(void) const; 105 /// Return last range 106 RangeList* lst(void) const; 107 108 public: 109 /// Returned by empty sets when asked for their maximum element 110 static const int MAX_OF_EMPTY = Limits::min-1; 111 /// Returned by empty sets when asked for their minimum element 112 static const int MIN_OF_EMPTY = Limits::max+1; 113 114 /// \name Constructors and initialization 115 //@{ 116 /// Default constructor. Creates an empty set. 117 BndSet(void); 118 /// Initialize as the set \f$ \{i,\dots,j\}\f$ 119 BndSet(Space& home, int i, int j); 120 /// Initialize as the set represented by \a s 121 GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s); 122 //@} 123 124 /// \name Memory management 125 //@{ 126 /// Free memory used by this set 127 void dispose(Space& home); 128 //@} 129 130 /// \name Value access 131 //@{ 132 /// Return smallest element 133 int min(void) const; 134 /// Return greatest element 135 int max(void) const; 136 /// Return \a n -th smallest element 137 int minN(unsigned int n) const; 138 /// Return size 139 unsigned int size(void) const; 140 /// Return cardinality 141 unsigned int card(void) const; 142 /// Set cardinality 143 void card(unsigned int c); 144 //@} 145 146 /// \name Tests 147 //@{ 148 /// Test whether this set is empty 149 bool empty(void) const; 150 /// Test whether \a i is an element of this set 151 bool in(int i) const; 152 //@} 153 154 /// \name Update operations 155 //@{ 156 /// Make this set equal to \a s 157 void become(Space& home, const BndSet& s); 158 //@} 159 160 /// \name Range list access for iteration 161 //@{ 162 /// Return range list for iteration 163 RangeList* ranges(void) const; 164 //@} 165 166 protected: 167 /// Overwrite the ranges with those represented by \a i 168 template<class I> bool overwrite(Space& home,I& i); 169 170 public: 171 /// \name Cloning 172 //@{ 173 /// Update this set to be a clone of set \a x 174 void update(Space& home, BndSet& x); 175 //@} 176 177 /// Check whether internal invariants hold 178 GECODE_SET_EXPORT bool isConsistent(void) const; 179 }; 180 181 /** 182 * \brief Range iterator for integer sets 183 * 184 */ 185 class BndSetRanges : public Iter::Ranges::RangeList { 186 public: 187 /// \name Constructors and initialization 188 //@{ 189 /// Default constructor 190 BndSetRanges(void); 191 /// Initialize with BndSet \a s 192 BndSetRanges(const BndSet& s); 193 /// Initialize with BndSet \a s 194 void init(const BndSet& s); 195 //@} 196 }; 197 198 /** 199 * \brief Growing sets of integers 200 * 201 * These sets provide operations for monotonically growing the set. 202 * Growing sets are used for implementing the greatest lower bound of 203 * set variables. 204 */ 205 class GLBndSet : public BndSet { 206 private: 207 /// Include the set \f$\{i,\dots,j\}\f$ in this set 208 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&); 209 public: 210 /// \name Constructors and initialization 211 //@{ 212 /// Default constructor. Creates an empty set. 213 GLBndSet(void); 214 /// Default constructor. Creates an empty set. 215 GLBndSet(Space&); 216 /// Initialize as the set \f$ \{i,\dots,j\}\f$ 217 GLBndSet(Space& home, int i, int j); 218 /// Initialize as the set represented by \a s 219 GLBndSet(Space& home, const IntSet& s); 220 /// Initialize as the empty set 221 void init(Space& home); 222 //@} 223 224 /// \name Update operations 225 //@{ 226 /// Include the set \f$\{i,\dots,j\}\f$ in this set 227 bool include(Space& home,int i,int j,SetDelta& d); 228 /// Include the set represented by \a i in this set 229 template<class I> bool includeI(Space& home,I& i); 230 //@} 231 private: 232 GLBndSet(const GLBndSet&); 233 const GLBndSet& operator =(const GLBndSet&); 234 }; 235 236 /** 237 * \brief Shrinking sets of integers 238 * 239 * These sets provide operations for monotonically shrinking the set. 240 * Shrinking sets are used for implementing the least upper bound of 241 * set variables. 242 */ 243 class LUBndSet: public BndSet{ 244 private: 245 GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&); 246 GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j); 247 public: 248 /// \name Constructors and initialization 249 //@{ 250 /// Default constructor. Creates an empty set. 251 LUBndSet(void); 252 /// Initialize as the full set including everything between Limits::min and Limits::max 253 LUBndSet(Space& home); 254 /// Initialize as the set \f$ \{i,\dots,j\}\f$ 255 LUBndSet(Space& home, int i, int j); 256 /// Initialize as the set represented by \a s 257 LUBndSet(Space& home, const IntSet& s); 258 /// Initialize as the full set including everything between Limits::min and Limits::max 259 void init(Space& home); 260 //@} 261 262 /// \name Update operations 263 //@{ 264 /// Exclude the set \f$\{i,\dots,j\}\f$ from this set 265 bool exclude(Space& home, int i, int j, SetDelta& d); 266 /// Intersect this set with the set \f$\{i,\dots,j\}\f$ 267 bool intersect(Space& home, int i, int j); 268 /// Exclude all elements not in the set represented by \a i from this set 269 template<class I> bool intersectI(Space& home, I& i); 270 /// Exclude all elements in the set represented by \a i from this set 271 template<class I> bool excludeI(Space& home, I& i); 272 /// Exclude all elements from this set 273 void excludeAll(Space& home); 274 //@} 275 private: 276 LUBndSet(const LUBndSet&); 277 const LUBndSet& operator =(const LUBndSet&); 278 }; 279 280 /* 281 * Iterators 282 * 283 */ 284 285 286 /** 287 * \brief A complement iterator spezialized for the %BndSet limits 288 * 289 * \ingroup TaskActorSet 290 */ 291 template<class I> 292 class RangesCompl : 293 public Iter::Ranges::Compl<Limits::min, Limits::max, I> { 294 public: 295 /// \name Constructors and initialization 296 //@{ 297 /// Default constructor 298 RangesCompl(void); 299 /// Initialize with iterator \a i 300 RangesCompl(I& i); 301 /// Initialize with iterator \a i 302 void init(I& i); 303 //@} 304 }; 305 306 /** 307 * \brief Range iterator for the least upper bound 308 * 309 * This class provides (by specialization) a range iterator 310 * for the least upper bounds of all set views. 311 * 312 * Note that this template class serves only as a specification 313 * of the interface of the various specializations. 314 * 315 * \ingroup TaskActorSet 316 */ 317 template<class T> class LubRanges { 318 public: 319 /// \name Constructors and initialization 320 //@{ 321 /// Default constructor 322 LubRanges(void); 323 /// Initialize with least upper bound ranges for set variable \a x 324 LubRanges(const T& x); 325 /// Initialize with least upper bound ranges for set variable \a x 326 void init(const T& x); 327 //@} 328 329 /// \name Iteration control 330 //@{ 331 /// Test whether iterator is still at a range or done 332 bool operator ()(void) const; 333 /// Move iterator to next range (if possible) 334 void operator ++(void); 335 //@} 336 337 /// \name Range access 338 //@{ 339 /// Return smallest value of range 340 int min(void) const; 341 /// Return largest value of range 342 int max(void) const; 343 /// Return width of range (distance between minimum and maximum) 344 unsigned int width(void) const; 345 //@} 346 }; 347 348 /** 349 * \brief Range iterator for the greatest lower bound 350 * 351 * This class provides (by specialization) a range iterator 352 * for the greatest lower bounds of all set views. 353 * 354 * Note that this template class serves only as a specification 355 * of the interface of the various specializations. 356 * 357 * \ingroup TaskActorSet 358 */ 359 template<class T> class GlbRanges { 360 public: 361 /// \name Constructors and initialization 362 //@{ 363 /// Default constructor 364 GlbRanges(void); 365 /// Initialize with greatest lower bound ranges for set variable \a x 366 GlbRanges(const T& x); 367 /// Initialize with greatest lower bound ranges for set variable \a x 368 void init(const T& x); 369 //@} 370 371 /// \name Iteration control 372 //@{ 373 /// Test whether iterator is still at a range or done 374 bool operator ()(void) const; 375 /// Move iterator to next range (if possible) 376 void operator ++(void); 377 //@} 378 379 /// \name Range access 380 //@{ 381 /// Return smallest value of range 382 int min(void) const; 383 /// Return largest value of range 384 int max(void) const; 385 /// Return width of range (distance between minimum and maximum) 386 unsigned int width(void) const; 387 //@} 388 }; 389 390 /** 391 * \brief Range iterator for the unknown set 392 * 393 * This class provides a range iterator 394 * for the unknown set of all set views. The unknown set is the 395 * difference between least upper and greatest lower bound, i.e. 396 * those elements which still may be in the set, but are not yet 397 * known to be in. 398 * 399 * \ingroup TaskActorSet 400 */ 401 template<class T> 402 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{ 403 private: 404 LubRanges<T> i1; 405 GlbRanges<T> i2; 406 public: 407 /// \name Constructors and initialization 408 //@{ 409 /// Default constructor 410 UnknownRanges(void); 411 /// Initialize with unknown set ranges for set variable \a x 412 UnknownRanges(const T& x); 413 /// Initialize with unknown set ranges for set variable \a x 414 void init(const T& x); 415 //@} 416 }; 417 418 }} 419 420 #include <gecode/set/var-imp/integerset.hpp> 421 #include <gecode/set/var-imp/iter.hpp> 422 423 namespace Gecode { namespace Set { 424 425 /** 426 * \brief Finite integer set variable implementation 427 * 428 * \ingroup Other 429 */ 430 class SetVarImp : public SetVarImpBase { 431 friend class LubRanges<SetVarImp*>; 432 friend class GlbRanges<SetVarImp*>; 433 private: 434 /// The least upper bound of the domain 435 LUBndSet lub; 436 /// The greatest lower bound of the domain 437 GLBndSet glb; 438 439 protected: 440 /// Constructor for cloning \a x 441 SetVarImp(Space& home, SetVarImp& x); 442 public: 443 /// \name Constructors and initialization 444 //@{ 445 /// Initialize with empty lower and full upper bound 446 SetVarImp(Space& home); 447 /** 448 * \brief Initialize with given bounds and cardinality 449 * 450 * Creates a set variable \f$s\f$ with 451 * \f$\mathit{glb}(s)=\{\mathit{glbMin},\dots,\mathit{glbMax}\}\f$, 452 * \f$\mathit{lub}(s)=\{\mathit{lubMin},\dots,\mathit{lubMax}\}\f$, and 453 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$ 454 */ 455 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax, 456 unsigned int cardMin = 0, 457 unsigned int cardMax = Limits::card); 458 /** 459 * \brief Initialize with given bounds and cardinality 460 * 461 * Creates a set variable \f$s\f$ with 462 * \f$\mathit{glb}(s)=\mathit{glbD}\f$, 463 * \f$\mathit{lub}(s)=\{\mathit{lubMin},\dots,\mathit{lubMax}\}\f$, and 464 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$ 465 */ 466 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax, 467 unsigned int cardMin,unsigned int cardMax); 468 /** 469 * \brief Initialize with given bounds and cardinality 470 * 471 * Creates a set variable \f$s\f$ with 472 * \f$\mathit{glb}(s)=\{\mathit{glbMin},\dots,\mathit{glbMax}\}\f$, 473 * \f$\mathit{lub}(s)=\mathit{lubD}\f$, and 474 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$ 475 */ 476 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD, 477 unsigned int cardMin,unsigned int cardMax); 478 /** 479 * \brief Initialize with given bounds and cardinality 480 * 481 * Creates a set variable \f$s\f$ with 482 * \f$\mathit{glb}(s)=\mathit{glbD}\f$, 483 * \f$\mathit{lub}(s)=\mathit{lubD}\f$, and 484 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$ 485 */ 486 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD, 487 unsigned int cardMin,unsigned int cardMax); 488 //@} 489 490 /// \name Value access 491 //@{ 492 /// Return current cardinality minimum 493 unsigned int cardMin(void) const; 494 /// Return current cardinality maximum 495 unsigned int cardMax(void) const; 496 /// Return minimum of the least upper bound 497 int lubMin(void) const; 498 /// Return maximum of the least upper bound 499 int lubMax(void) const; 500 /// Return \a n -th smallest element in the least upper bound 501 int lubMinN(unsigned int n) const; 502 /// Return minimum of the greatest lower bound 503 int glbMin(void) const; 504 /// Return maximum of the greatest lower bound 505 int glbMax(void) const; 506 /// Return the size of the greatest lower bound 507 unsigned int glbSize(void) const; 508 /// Return the size of the least upper bound 509 unsigned int lubSize(void) const; 510 //@} 511 512 /// \name Domain tests 513 //@{ 514 /// Test whether variable is assigned 515 bool assigned(void) const; 516 /// Test whether \a n is contained in greatest lower bound 517 bool knownIn(int n) const; 518 /// Test whether \a n is not contained in least upper bound 519 bool knownOut(int) const; 520 //@} 521 522 private: 523 /// \name Domain update by range iterator, implementations 524 //@{ 525 /// Include set described by \a i in the greatest lower bound 526 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i); 527 /// Exclude set described by \a i from the least upper bound 528 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i); 529 /// Exclude everything but set described by \a i from the least upper bound 530 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i); 531 //@} 532 533 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d); 534 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d); 535 536 /// \name Cardinality update implementation 537 //@{ 538 /// Restrict cardinality to be at least n 539 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home); 540 /// Restrict cardinality to be at most n 541 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home); 542 //@} 543 544 public: 545 546 /// \name Domain update by value 547 //@{ 548 /// Include \a n in the greatest lower bound 549 ModEvent include(Space& home,int n); 550 /// Include the range \f$\{i,\dots,j\}\f$ in the greatest lower bound 551 ModEvent include(Space& home,int i,int j); 552 /// Exclude \a n from the least upper bound 553 ModEvent exclude(Space& home,int n); 554 /// Exclude the range \f$\{i,\dots,j\}\f$ from the least upper bound 555 ModEvent exclude(Space& home,int i,int j); 556 /// Exclude everything but \a n from the least upper bound 557 ModEvent intersect(Space& home,int n); 558 /// Exclude everything but the range \f$\{i,\dots,j\}\f$ from the least upper bound 559 ModEvent intersect(Space& home,int i,int j); 560 /// Restrict cardinality to be at least n 561 ModEvent cardMin(Space& home,unsigned int n); 562 /// Restrict cardinality to be at most n 563 ModEvent cardMax(Space& home,unsigned int n); 564 //@} 565 566 /// \name Domain update by range iterator 567 //@{ 568 /// Include set described by \a i in the greatest lower bound 569 template<class I> ModEvent includeI(Space& home,I& i); 570 /// Exclude set described by \a i from the least upper bound 571 template<class I> ModEvent excludeI(Space& home,I& i); 572 /// Exclude everything but set described by \a i from the least upper bound 573 template<class I> ModEvent intersectI(Space& home,I& i); 574 //@} 575 576 public: 577 /// \name Dependencies 578 //@{ 579 /** 580 * \brief Subscribe propagator \a p with propagation condition \a pc to variable 581 * 582 * In case \a schedule is false, the propagator is just subscribed but 583 * not scheduled for execution (this must be used when creating 584 * subscriptions during propagation). 585 */ 586 GECODE_SET_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); 587 /// Re-schedule propagator \a p with propagation condition \a pc 588 GECODE_SET_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc); 589 /** \brief Subscribe advisor \a a to variable 590 * 591 * The advisor \a a is only subscribed if \a assigned is false. 592 * 593 * If \a fail is true, the advisor \a a is also run when a variable 594 * operation triggers failure. This feature is undocumented. 595 * 596 */ 597 GECODE_SET_EXPORT void subscribe(Space& home, Advisor& a, bool fail); 598 //@} 599 600 private: 601 /// Return copy of not-yet copied variable 602 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home); 603 604 public: 605 /// \name Cloning 606 //@{ 607 /// Return copy of this variable 608 SetVarImp* copy(Space& home); 609 //@} 610 611 /// \name Delta information for advisors 612 //@{ 613 /// Return minimum value just pruned from glb 614 static int glbMin(const Delta& d); 615 /// Return maximum value just pruned from glb 616 static int glbMax(const Delta& d); 617 /// Test whether arbitrary values got pruned from glb 618 static bool glbAny(const Delta& d); 619 /// Return minimum value just pruned from lub 620 static int lubMin(const Delta& d); 621 /// Return maximum value just pruned from lub 622 static int lubMax(const Delta& d); 623 /// Test whether arbitrary values got pruned from lub 624 static bool lubAny(const Delta& d); 625 //@} 626 627 }; 628 629 class SetView; 630 631 }} 632 633 #include <gecode/set/var-imp/set.hpp> 634 635 // STATISTICS: set-var 636