this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2002
11 * Guido Tack, 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 <cmath>
39
40namespace Gecode { namespace Int {
41
42 class IntVarImp;
43 class BoolVarImp;
44
45 /**
46 * \brief Integer delta information for advisors
47 *
48 * Note that the same delta information is used for both
49 * integer and Boolean variables and views.
50 */
51 class IntDelta : public Delta {
52 friend class IntVarImp;
53 friend class BoolVarImp;
54 private:
55 int _min; ///< Smallest value just pruned
56 int _max; ///< Largest value just pruned
57 public:
58 /// Create integer delta as providing no information
59 IntDelta(void);
60 /// Create integer delta with \a min and \a max
61 IntDelta(int min, int max);
62 /// Create integer delta with \a min
63 IntDelta(int min);
64 private:
65 /// Return minimum
66 int min(void) const;
67 /// Return maximum
68 int max(void) const;
69 /// Return width
70 unsigned int width(void) const;
71 /// Test whether any domain change has happened
72 bool any(void) const;
73 };
74
75}}
76
77#include <gecode/int/var-imp/delta.hpp>
78
79namespace Gecode { namespace Int {
80
81 class IntVarImpFwd;
82 class IntVarImpBwd;
83
84 /**
85 * \brief Integer variable implementation
86 *
87 * \ingroup Other
88 */
89 class IntVarImp : public IntVarImpBase {
90 friend class IntVarImpFwd;
91 friend class IntVarImpBwd;
92 protected:
93 /**
94 * \brief Lists of ranges (intervals)
95 *
96 * Range lists are doubly-linked storing the pointer to both
97 * the next and the previous element in a single pointer.
98 * That means that the next element is only available when
99 * the previous element is supplied as additional information.
100 * The same holds true for access to the previous element.
101 */
102 class RangeList : public FreeList {
103 protected:
104 /// Minimum of range
105 int _min;
106 /// Maximum of range
107 int _max;
108 public:
109 /// \name Constructors
110 //@{
111 /// Default constructor (noop)
112 RangeList(void);
113 /// Initialize with minimum \a min and maximum \a max
114 RangeList(int min, int max);
115 /// Initialize with minimum \a min and maximum \a max and predecessor \a p and successor \a n
116 RangeList(int min, int max, RangeList* p, RangeList* n);
117 //@}
118
119 /// \name Access
120 //@{
121 /// Return minimum
122 int min(void) const;
123 /// Return maximum
124 int max(void) const;
125 /// Return width (distance between maximum and minimum)
126 unsigned int width(void) const;
127
128 /// Return next element (from previous \a p)
129 RangeList* next(const RangeList* p) const;
130 /// Return previous element (from next \a n)
131 RangeList* prev(const RangeList* n) const;
132 //@}
133
134 /// \name Update
135 //@{
136 /// Set minimum to \a n
137 void min(int n);
138 /// Set maximum to \a n
139 void max(int n);
140
141 /// Set previous element to \a p and next element to \a n
142 void prevnext(RangeList* p, RangeList* n);
143 /// Set next element from \a o to \a n
144 void next(RangeList* o, RangeList* n);
145 /// Set previous element from \a o to \a n
146 void prev(RangeList* o, RangeList* n);
147 /// Restore simple link to next element (so that it becomes a true free list)
148 void fix(RangeList* n);
149 //@}
150
151 /// \name Memory management
152 //@{
153 /**
154 * \brief Free memory for all elements between this and \a l (inclusive)
155 *
156 * \a p must be the pointer to the previous element of \c this.
157 */
158 void dispose(Space& home, RangeList* p, RangeList* l);
159 /**
160 * \brief Free memory for all elements between this and \a l (inclusive)
161 *
162 * This routine assumes that the list has already been fixed.
163 */
164 void dispose(Space& home, RangeList* l);
165 /// Free memory for this element
166 void dispose(Space& home);
167
168 /// Allocate memory from space
169 static void* operator new(size_t s, Space& home);
170 /// Placement new
171 static void* operator new(size_t s, void* p);
172 /// No-op (for exceptions)
173 static void operator delete(void*);
174 /// No-op (use dispose instead)
175 static void operator delete(void*, Space&);
176 /// No-op (use dispose instead)
177 static void operator delete(void*, void*);
178 //@}
179 };
180
181 /**
182 * \brief Domain information
183 *
184 * Provides fast access to minimum and maximum of the
185 * entire domain and links to the first element
186 * of a RangeList defining the domain.
187 */
188 RangeList dom;
189 /// Link the last element
190 RangeList* _lst;
191 /// Return first element of rangelist
192 RangeList* fst(void) const;
193 /// Set first element of rangelist
194 void fst(RangeList* f);
195 /// Return last element of rangelist
196 RangeList* lst(void) const;
197 /// Set last element of rangelist
198 void lst(RangeList* l);
199 /// Size of holes in the domain
200 unsigned int holes;
201
202 protected:
203 /// Constructor for cloning \a x
204 IntVarImp(Space& home, IntVarImp& x);
205 public:
206 /// Initialize with range domain
207 IntVarImp(Space& home, int min, int max);
208 /// Initialize with domain specified by \a d
209 IntVarImp(Space& home, const IntSet& d);
210
211 /// \name Value access
212 //@{
213 /// Return minimum of domain
214 int min(void) const;
215 /// Return maximum of domain
216 int max(void) const;
217 /// Return assigned value (only if assigned)
218 int val(void) const;
219 /// Return median of domain (greatest element not greater than the median)
220 GECODE_INT_EXPORT int med(void) const;
221
222 /// Return size (cardinality) of domain
223 unsigned int size(void) const;
224 /// Return width of domain (distance between maximum and minimum)
225 unsigned int width(void) const;
226 /// Return regret of domain minimum (distance to next larger value)
227 unsigned int regret_min(void) const;
228 /// Return regret of domain maximum (distance to next smaller value)
229 unsigned int regret_max(void) const;
230 //@}
231
232 private:
233 /// Test whether \a n is contained in domain (full domain)
234 GECODE_INT_EXPORT bool in_full(int n) const;
235
236 public:
237 /// \name Domain tests
238 //@{
239 /// Test whether domain is a range
240 bool range(void) const;
241 /// Test whether variable is assigned
242 bool assigned(void) const;
243
244 /// Test whether \a n is contained in domain
245 bool in(int n) const;
246 /// Test whether \a n is contained in domain
247 bool in(long long int n) const;
248 //@}
249
250 protected:
251 /// \name Range list access for iteration
252 //@{
253 /// Return range list for forward iteration
254 const RangeList* ranges_fwd(void) const;
255 /// Return range list for backward iteration
256 const RangeList* ranges_bwd(void) const;
257 //@}
258
259 private:
260 /// Test whether \a n is closer to the minimum or maximum
261 bool closer_min(int b) const;
262 /// \name Domain update by value (full domain)
263 //@{
264 /// Restrict domain values to be less or equal than \a n
265 GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n);
266 /// Restrict domain values to be greater or equal than \a n
267 GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n);
268 /// Restrict domain values to be equal to current minimum of domain
269 GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n);
270 /// Restrict domain values to be different from \a n
271 GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n);
272 //@}
273 public:
274 /// \name Domain update by value
275 //@{
276 /// Restrict domain values to be less or equal than \a n
277 ModEvent lq(Space& home, int n);
278 /// Restrict domain values to be less or equal than \a n
279 ModEvent lq(Space& home, long long int n);
280
281 /// Restrict domain values to be greater or equal than \a n
282 ModEvent gq(Space& home, int n);
283 /// Restrict domain values to be greater or equal than \a n
284 ModEvent gq(Space& home, long long int n);
285
286 /// Restrict domain values to be different from \a n
287 ModEvent nq(Space& home, int n);
288 /// Restrict domain values to be different from \a n
289 ModEvent nq(Space& home, long long int n);
290
291 /// Restrict domain values to be equal to \a n
292 ModEvent eq(Space& home, int n);
293 /// Restrict domain values to be equal to \a n
294 ModEvent eq(Space& home, long long int n);
295 //@}
296
297 /**
298 * \name Domain update by iterator
299 *
300 * Variable domains can be both updated by range and value iterators.
301 * Value iterators do not need to be strict in that the same value
302 * is allowed to occur more than once in the iterated sequence.
303 *
304 * The argument \a depends must be true, if the iterator
305 * passed as argument depends on the variable implementation
306 * on which the operation is invoked. In this case, the variable
307 * implementation is only updated after the iterator has been
308 * consumed. Otherwise, the domain might be updated concurrently
309 * while following the iterator.
310 *
311 */
312 //@{
313 /// Replace domain by ranges described by \a i
314 template<class I>
315 ModEvent narrow_r(Space& home, I& i, bool depends=true);
316 /// Intersect domain with ranges described by \a i
317 template<class I>
318 ModEvent inter_r(Space& home, I& i, bool depends=true);
319 /// Remove from domain the ranges described by \a i
320 template<class I>
321 ModEvent minus_r(Space& home, I& i, bool depends=true);
322 /// Replace domain by values described by \a i
323 template<class I>
324 ModEvent narrow_v(Space& home, I& i, bool depends=true);
325 /// Intersect domain with values described by \a i
326 template<class I>
327 ModEvent inter_v(Space& home, I& i, bool depends=true);
328 /// Remove from domain the values described by \a i
329 template<class I>
330 ModEvent minus_v(Space& home, I& i, bool depends=true);
331 //@}
332
333 /// \name Dependencies
334 //@{
335 /**
336 * \brief Subscribe propagator \a p with propagation condition \a pc to variable
337 *
338 * In case \a schedule is false, the propagator is just subscribed but
339 * not scheduled for execution (this must be used when creating
340 * subscriptions during propagation).
341 *
342 */
343 GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
344 /// Re-schedule propagator \a p
345 GECODE_INT_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc);
346 /** \brief Subscribe advisor \a a to variable
347 *
348 * The advisor \a a is only subscribed if \a assigned is false.
349 *
350 * If \a fail is true, the advisor \a a is also run when a variable
351 * operation triggers failure. This feature is undocumented.
352 *
353 */
354 GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
355 //@}
356
357 /// \name Variable implementation-dependent propagator support
358 //@{
359 /// Translate modification event \a me to modification event delta for view
360 static ModEventDelta med(ModEvent me);
361 //@}
362
363
364 private:
365 /// Return copy of not-yet copied variable
366 GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home);
367 public:
368 /// \name Cloning
369 //@{
370 /// Return copy of this variable
371 IntVarImp* copy(Space& home);
372 //@}
373
374 /// \name Delta information for advisors
375 //@{
376 /// Return minimum value just pruned
377 static int min(const Delta& d);
378 /// Return maximum value just pruned
379 static int max(const Delta& d);
380 /// Return width of values just pruned
381 static unsigned int width(const Delta& d);
382 /// Test whether arbitrary values got pruned
383 static bool any(const Delta& d);
384 //@}
385 };
386
387
388 /**
389 * \brief Range iterator for ranges of integer variable implementation
390 *
391 */
392 class IntVarImpFwd {
393 private:
394 /// Previous range
395 const IntVarImp::RangeList* p;
396 /// Current range
397 const IntVarImp::RangeList* c;
398 public:
399 /// \name Constructors and initialization
400 //@{
401 /// Default constructor
402 IntVarImpFwd(void);
403 /// Initialize with ranges from variable implementation \a x
404 IntVarImpFwd(const IntVarImp* x);
405 /// Initialize with ranges from variable implementation \a x
406 void init(const IntVarImp* x);
407 //@}
408
409 /// \name Iteration control
410 //@{
411 /// Test whether iterator is still at a range or done
412 bool operator ()(void) const;
413 /// Move iterator to next range (if possible)
414 void operator ++(void);
415 //@}
416
417 /// \name Range access
418 //@{
419 /// Return smallest value of range
420 int min(void) const;
421 /// Return largest value of range
422 int max(void) const;
423 /// Return width of range (distance between minimum and maximum)
424 unsigned int width(void) const;
425 //@}
426 };
427
428 /**
429 * \brief Backward iterator for ranges of integer variable implementations
430 *
431 * Note that this iterator is not a range iterator as the ranges
432 * are not iterated in increasing but in decreasing order.
433 *
434 */
435 class IntVarImpBwd {
436 private:
437 /// Next range
438 const IntVarImp::RangeList* n;
439 /// Current range
440 const IntVarImp::RangeList* c;
441 public:
442 /// \name Constructors and initialization
443 //@{
444 /// Default constructor
445 IntVarImpBwd(void);
446 /// Initialize with ranges from variable implementation \a x
447 IntVarImpBwd(const IntVarImp* x);
448 /// Initialize with ranges from variable implementation \a x
449 void init(const IntVarImp* x);
450 //@}
451
452 /// \name Iteration control
453 //@{
454 /// Test whether iterator is still at a range or done
455 bool operator ()(void) const;
456 /// Move iterator to previous range (if possible)
457 void operator ++(void);
458 //@}
459
460 /// \name Range access
461 //@{
462 /// Return smallest value of range
463 int min(void) const;
464 /// Return largest value of range
465 int max(void) const;
466 /// Return width of range (distance between minimum and maximum)
467 unsigned int width(void) const;
468 //@}
469 };
470
471}}
472
473#include <gecode/int/var-imp/int.hpp>
474
475namespace Gecode {
476
477 class IntVar;
478 class BoolVar;
479}
480
481namespace Gecode { namespace Int {
482
483 /// Type for status of a Boolean variable
484 typedef unsigned int BoolStatus;
485
486 /**
487 * \brief Boolean variable implementation
488 *
489 * \ingroup Other
490 */
491 class BoolVarImp : public BoolVarImpBase {
492 friend class ::Gecode::BoolVar;
493 private:
494 /**
495 * \brief Domain information
496 *
497 * - The bit at position 0 corresponds to the minimum
498 * - The bit at position 1 corresponds to the maximum
499 * - Interpreted as an unsigned, that is: 0 represents
500 * a variable assigned to 0, 3 represents a variable
501 * assigned to 1, and 2 represents an unassigned variable.
502 * - No other values are possible.
503 */
504
505 GECODE_INT_EXPORT static BoolVarImp s_one;
506 GECODE_INT_EXPORT static BoolVarImp s_zero;
507
508 /// Constructor for cloning \a x
509 BoolVarImp(Space& home, BoolVarImp& x);
510 /// Initialize static instance assigned to \a n
511 BoolVarImp(int n);
512 public:
513 /// Initialize with range domain
514 BoolVarImp(Space& home, int min, int max);
515
516 /// \name Domain status access
517 //@{
518 /// How many bits does the status have
519 static const int BITS = 2;
520 /// Status of domain assigned to zero
521 static const BoolStatus ZERO = 0;
522 /// Status of domain assigned to one
523 static const BoolStatus ONE = 3;
524 /// Status of domain not yet assigned
525 static const BoolStatus NONE = 2;
526 /// Return current domain status
527 BoolStatus status(void) const;
528 //@}
529
530 /// \name Value access
531 //@{
532 /// Return minimum of domain
533 int min(void) const;
534 /// Return maximum of domain
535 int max(void) const;
536 /// Return assigned value (only if assigned)
537 int val(void) const;
538 /// Return median of domain (greatest element not greater than the median)
539 int med(void) const;
540
541 /// Return size (cardinality) of domain
542 unsigned int size(void) const;
543 /// Return width of domain (distance between maximum and minimum)
544 unsigned int width(void) const;
545 /// Return regret of domain minimum (distance to next larger value)
546 unsigned int regret_min(void) const;
547 /// Return regret of domain maximum (distance to next smaller value)
548 unsigned int regret_max(void) const;
549 //@}
550
551 /// \name Boolean domain tests
552 //@{
553 /// Test whether variable is assigned to zero
554 bool zero(void) const;
555 /// Test whether variable is assigned to one
556 bool one(void) const;
557 /// Test whether variable is not yet assigned
558 bool none(void) const;
559 //@}
560
561 /// \name Domain tests
562 //@{
563 /// Test whether domain is a range
564 bool range(void) const;
565 /// Test whether variable is assigned
566 bool assigned(void) const;
567
568 /// Test whether \a n is contained in domain
569 bool in(int n) const;
570 /// Test whether \a n is contained in domain
571 bool in(long long int n) const;
572 //@}
573
574 /// \name Domain update by value
575 //@{
576 /// Restrict domain values to be less or equal than \a n
577 ModEvent lq(Space& home, int n);
578 /// Restrict domain values to be less or equal than \a n
579 ModEvent lq(Space& home, long long int n);
580
581 /// Restrict domain values to be greater or equal than \a n
582 ModEvent gq(Space& home, int n);
583 /// Restrict domain values to be greater or equal than \a n
584 ModEvent gq(Space& home, long long int n);
585
586 /// Restrict domain values to be different from \a n
587 ModEvent nq(Space& home, int n);
588 /// Restrict domain values to be different from \a n
589 ModEvent nq(Space& home, long long int n);
590
591 /// Restrict domain values to be equal to \a n
592 ModEvent eq(Space& home, int n);
593 /// Restrict domain values to be equal to \a n
594 ModEvent eq(Space& home, long long int n);
595 //@}
596
597 /**
598 * \name Domain update by iterator
599 *
600 * Variable domains can be both updated by range and value iterators.
601 * Value iterators do not need to be strict in that the same value
602 * is allowed to occur more than once in the iterated sequence.
603 *
604 * The argument \a depends must be true, if the iterator
605 * passed as argument depends on the variable implementation
606 * on which the operation is invoked. In this case, the variable
607 * implementation is only updated after the iterator has been
608 * consumed. Otherwise, the domain might be updated concurrently
609 * while following the iterator.
610 *
611 */
612 //@{
613 /// Replace domain by ranges described by \a i
614 template<class I>
615 ModEvent narrow_r(Space& home, I& i, bool depends=true);
616 /// Intersect domain with ranges described by \a i
617 template<class I>
618 ModEvent inter_r(Space& home, I& i, bool depends=true);
619 /// Remove from domain the ranges described by \a i
620 template<class I>
621 ModEvent minus_r(Space& home, I& i, bool depends=true);
622 /// Replace domain by values described by \a i
623 template<class I>
624 ModEvent narrow_v(Space& home, I& i, bool depends=true);
625 /// Intersect domain with values described by \a i
626 template<class I>
627 ModEvent inter_v(Space& home, I& i, bool depends=true);
628 /// Remove from domain the values described by \a i
629 template<class I>
630 ModEvent minus_v(Space& home, I& i, bool depends=true);
631 //@}
632
633 /// \name Boolean update operations
634 //@{
635 /// Assign variable to zero
636 ModEvent zero(Space& home);
637 /// Assign variable to one
638 ModEvent one(Space& home);
639 /// Assign unassigned variable to zero
640 GECODE_INT_EXPORT ModEvent zero_none(Space& home);
641 /// Assign unassigned variable to one
642 GECODE_INT_EXPORT ModEvent one_none(Space& home);
643 //@}
644
645 public:
646 /// \name Dependencies
647 //@{
648 /**
649 * \brief Subscribe propagator \a p to variable with propagation condition \a pc
650 *
651 * In case \a schedule is false, the propagator is just subscribed but
652 * not scheduled for execution (this must be used when creating
653 * subscriptions during propagation).
654 *
655 * The propagation condition \a pc can be a propagation condition
656 * for integer variables, which will be mapped to PC_BOOL_VAL.
657 */
658 GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
659 /**
660 * \brief Cancel subscription of propagator \a p with propagation condition \a pc
661 *
662 * The propagation condition \a pc can be a propagation condition
663 * for integer variables, which will be mapped to PC_BOOL_VAL.
664 */
665 void cancel(Space& home, Propagator& p, PropCond pc);
666 /** \brief Subscribe advisor \a a to variable
667 *
668 * The advisor \a a is only subscribed if \a assigned is false.
669 *
670 * If \a fail is true, the advisor \a a is also run when a variable
671 * operation triggers failure. This feature is undocumented.
672 *
673 */
674 GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
675 /// Cancel subscription of advisor \a a
676 void cancel(Space& home, Advisor& a, bool fail);
677 //@}
678
679 /// \name Variable implementation-dependent propagator support
680 //@{
681 /**
682 * \brief Schedule propagator \a p with modification event \a me
683 *
684 * The modfication event \a me can be a modification event for
685 * integer variables, however \a me will be ignored if it is not
686 * ME_INT_VAL (or ME_BOOL_VAL).
687 */
688 static void schedule(Space& home, Propagator& p, ModEvent me);
689 /// Re-schedule propagator \a p
690 GECODE_INT_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc);
691 /// Translate modification event \a me to modification event delta for view
692 static ModEventDelta med(ModEvent me);
693 //@}
694
695 /// \name Support for delta information for advisors
696 //@{
697 /// Return modification event
698 static ModEvent modevent(const Delta& d);
699 /// Return minimum value just pruned
700 static int min(const Delta& d);
701 /// Return maximum value just pruned
702 static int max(const Delta& d);
703 /// Return width of values just pruned
704 static unsigned int width(const Delta& d);
705 /// Test whether arbitrary values got pruned
706 static bool any(const Delta& d);
707 /// Test whether a variable has been assigned to zero
708 static bool zero(const Delta& d);
709 /// Test whether a variable has been assigned to one
710 static bool one(const Delta& d);
711 //@}
712
713 /// \name Cloning
714 //@{
715 /// Return copy of this variable
716 BoolVarImp* copy(Space& home);
717 //@}
718
719 };
720
721}}
722
723#include <gecode/int/var-imp/bool.hpp>
724
725// STATISTICS: int-var
726