Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
var-imp.hpp
Go to the documentation of this file.
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 
40 namespace Gecode { namespace Int {
41 
42  class IntVarImp;
43  class BoolVarImp;
44 
51  class IntDelta : public Delta {
52  friend class IntVarImp;
53  friend class BoolVarImp;
54  private:
55  int _min;
56  int _max;
57  public:
59  IntDelta(void);
61  IntDelta(int min, int max);
63  IntDelta(int min);
64  private:
66  int min(void) const;
68  int max(void) const;
70  unsigned int width(void) const;
72  bool any(void) const;
73  };
74 
75 }}
76 
78 
79 namespace Gecode { namespace Int {
80 
81  class IntVarImpFwd;
82  class IntVarImpBwd;
83 
89  class IntVarImp : public IntVarImpBase {
90  friend class IntVarImpFwd;
91  friend class IntVarImpBwd;
92  protected:
102  class RangeList : public FreeList {
103  protected:
105  int _min;
107  int _max;
108  public:
110 
111  RangeList(void);
114  RangeList(int min, int max);
116  RangeList(int min, int max, RangeList* p, RangeList* n);
118 
120 
121  int min(void) const;
124  int max(void) const;
126  unsigned int width(void) const;
127 
129  RangeList* next(const RangeList* p) const;
131  RangeList* prev(const RangeList* n) const;
133 
135 
136  void min(int n);
139  void max(int n);
140 
142  void prevnext(RangeList* p, RangeList* n);
144  void next(RangeList* o, RangeList* n);
146  void prev(RangeList* o, RangeList* n);
148  void fix(RangeList* n);
150 
152 
153 
158  void dispose(Space& home, RangeList* p, RangeList* l);
164  void dispose(Space& home, RangeList* l);
166  void dispose(Space& home);
167 
169  static void* operator new(size_t s, Space& home);
171  static void* operator new(size_t s, void* p);
173  static void operator delete(void*);
175  static void operator delete(void*, Space&);
177  static void operator delete(void*, void*);
179  };
180 
192  RangeList* fst(void) const;
194  void fst(RangeList* f);
196  RangeList* lst(void) const;
198  void lst(RangeList* l);
200  unsigned int holes;
201 
202  protected:
204  IntVarImp(Space& home, IntVarImp& x);
205  public:
207  IntVarImp(Space& home, int min, int max);
209  IntVarImp(Space& home, const IntSet& d);
210 
212 
213  int min(void) const;
216  int max(void) const;
218  int val(void) const;
220  GECODE_INT_EXPORT int med(void) const;
221 
223  unsigned int size(void) const;
225  unsigned int width(void) const;
227  unsigned int regret_min(void) const;
229  unsigned int regret_max(void) const;
231 
232  private:
234  GECODE_INT_EXPORT bool in_full(int n) const;
235 
236  public:
238 
239  bool range(void) const;
242  bool assigned(void) const;
243 
245  bool in(int n) const;
247  bool in(long long int n) const;
249 
250  protected:
252 
253  const RangeList* ranges_fwd(void) const;
256  const RangeList* ranges_bwd(void) const;
258 
259  private:
261  bool closer_min(int b) const;
263 
264  GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n);
267  GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n);
269  GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n);
271  GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n);
273  public:
275 
276  ModEvent lq(Space& home, int n);
279  ModEvent lq(Space& home, long long int n);
280 
282  ModEvent gq(Space& home, int n);
284  ModEvent gq(Space& home, long long int n);
285 
287  ModEvent nq(Space& home, int n);
289  ModEvent nq(Space& home, long long int n);
290 
292  ModEvent eq(Space& home, int n);
294  ModEvent eq(Space& home, long long int n);
296 
313  template<class I>
315  ModEvent narrow_r(Space& home, I& i, bool depends=true);
317  template<class I>
318  ModEvent inter_r(Space& home, I& i, bool depends=true);
320  template<class I>
321  ModEvent minus_r(Space& home, I& i, bool depends=true);
323  template<class I>
324  ModEvent narrow_v(Space& home, I& i, bool depends=true);
326  template<class I>
327  ModEvent inter_v(Space& home, I& i, bool depends=true);
329  template<class I>
330  ModEvent minus_v(Space& home, I& i, bool depends=true);
332 
334 
335 
343  GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
354  GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
356 
358 
359  static ModEventDelta med(ModEvent me);
362 
363 
364  private:
366  GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home);
367  public:
369 
370  IntVarImp* copy(Space& home);
373 
375 
376  static int min(const Delta& d);
379  static int max(const Delta& d);
381  static unsigned int width(const Delta& d);
383  static bool any(const Delta& d);
385  };
386 
387 
392  class IntVarImpFwd {
393  private:
395  const IntVarImp::RangeList* p;
397  const IntVarImp::RangeList* c;
398  public:
400 
401  IntVarImpFwd(void);
404  IntVarImpFwd(const IntVarImp* x);
406  void init(const IntVarImp* x);
408 
410 
411  bool operator ()(void) const;
414  void operator ++(void);
416 
418 
419  int min(void) const;
422  int max(void) const;
424  unsigned int width(void) const;
426  };
427 
435  class IntVarImpBwd {
436  private:
438  const IntVarImp::RangeList* n;
440  const IntVarImp::RangeList* c;
441  public:
443 
444  IntVarImpBwd(void);
447  IntVarImpBwd(const IntVarImp* x);
449  void init(const IntVarImp* x);
451 
453 
454  bool operator ()(void) const;
457  void operator ++(void);
459 
461 
462  int min(void) const;
465  int max(void) const;
467  unsigned int width(void) const;
469  };
470 
471 }}
472 
474 
475 namespace Gecode {
476 
477  class IntVar;
478  class BoolVar;
479 }
480 
481 namespace Gecode { namespace Int {
482 
484  typedef unsigned int BoolStatus;
485 
491  class BoolVarImp : public BoolVarImpBase {
492  friend class ::Gecode::BoolVar;
493  private:
505  GECODE_INT_EXPORT static BoolVarImp s_one;
506  GECODE_INT_EXPORT static BoolVarImp s_zero;
507 
509  BoolVarImp(Space& home, BoolVarImp& x);
511  BoolVarImp(int n);
512  public:
514  BoolVarImp(Space& home, int min, int max);
515 
517 
518  static const int BITS = 2;
521  static const BoolStatus ZERO = 0;
523  static const BoolStatus ONE = 3;
525  static const BoolStatus NONE = 2;
527  BoolStatus status(void) const;
529 
531 
532  int min(void) const;
535  int max(void) const;
537  int val(void) const;
539  int med(void) const;
540 
542  unsigned int size(void) const;
544  unsigned int width(void) const;
546  unsigned int regret_min(void) const;
548  unsigned int regret_max(void) const;
550 
552 
553  bool zero(void) const;
556  bool one(void) const;
558  bool none(void) const;
560 
562 
563  bool range(void) const;
566  bool assigned(void) const;
567 
569  bool in(int n) const;
571  bool in(long long int n) const;
573 
575 
576  ModEvent lq(Space& home, int n);
579  ModEvent lq(Space& home, long long int n);
580 
582  ModEvent gq(Space& home, int n);
584  ModEvent gq(Space& home, long long int n);
585 
587  ModEvent nq(Space& home, int n);
589  ModEvent nq(Space& home, long long int n);
590 
592  ModEvent eq(Space& home, int n);
594  ModEvent eq(Space& home, long long int n);
596 
613  template<class I>
615  ModEvent narrow_r(Space& home, I& i, bool depends=true);
617  template<class I>
618  ModEvent inter_r(Space& home, I& i, bool depends=true);
620  template<class I>
621  ModEvent minus_r(Space& home, I& i, bool depends=true);
623  template<class I>
624  ModEvent narrow_v(Space& home, I& i, bool depends=true);
626  template<class I>
627  ModEvent inter_v(Space& home, I& i, bool depends=true);
629  template<class I>
630  ModEvent minus_v(Space& home, I& i, bool depends=true);
632 
634 
635  ModEvent zero(Space& home);
638  ModEvent one(Space& home);
644 
645  public:
647 
648 
658  GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
665  void cancel(Space& home, Propagator& p, PropCond pc);
674  GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
676  void cancel(Space& home, Advisor& a, bool fail);
678 
680 
681 
688  static void schedule(Space& home, Propagator& p, ModEvent me);
692  static ModEventDelta med(ModEvent me);
694 
696 
697  static ModEvent modevent(const Delta& d);
700  static int min(const Delta& d);
702  static int max(const Delta& d);
704  static unsigned int width(const Delta& d);
706  static bool any(const Delta& d);
708  static bool zero(const Delta& d);
710  static bool one(const Delta& d);
712 
714 
715  BoolVarImp* copy(Space& home);
718 
719  };
720 
721 }}
722 
724 
725 // STATISTICS: int-var
726 
BoolStatus status(void) const
Return current domain status.
Definition: bool.hpp:58
static const int BITS
How many bits does the status have.
Definition: var-imp.hpp:519
static const BoolStatus NONE
Status of domain not yet assigned.
Definition: var-imp.hpp:525
int max(void) const
Return maximum.
Definition: int.hpp:102
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:408
Post propagator for SetVar x
Definition: set.hh:767
Base-class for Bool-variable implementations.
Definition: var-imp.hpp:93
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:286
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:492
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:173
int min(void) const
Return minimum of domain.
Definition: int.hpp:224
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:134
RangeList(void)
Default constructor (noop)
Definition: int.hpp:49
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:84
bool one(void) const
Test whether variable is assigned to one.
Definition: bool.hpp:135
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:365
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:70
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:238
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:386
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:392
Backward iterator for ranges of integer variable implementations.
Definition: var-imp.hpp:435
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:475
int min(void) const
Return smallest value of range.
Definition: int.hpp:446
bool zero(void) const
Test whether variable is assigned to zero.
Definition: bool.hpp:131
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:305
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:91
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: bool.hpp:370
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Computation spaces.
Definition: core.hpp:1742
IntDelta(void)
Create integer delta as providing no information.
Definition: delta.hpp:37
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p to variable with propagation condition pc.
Definition: bool.cpp:60
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: bool.hpp:314
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:310
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:190
static const BoolStatus ONE
Status of domain assigned to one.
Definition: var-imp.hpp:523
IntVarImpFwd(void)
Default constructor.
Definition: int.hpp:427
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:242
bool assigned(void) const
Test whether variable is assigned.
Definition: bool.hpp:85
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition: bool.cpp:51
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:248
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:484
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: int.cpp:362
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:258
int _max
Maximum of range.
Definition: var-imp.hpp:107
Integer variable implementation.
Definition: var-imp.hpp:89
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: bool.hpp:227
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:46
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:232
bool range(void) const
Test whether domain is a range.
Definition: bool.hpp:81
bool in(int n) const
Test whether n is contained in domain.
Definition: bool.hpp:117
Gecode toplevel namespace
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:470
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:163
Base-class for propagators.
Definition: core.hpp:1064
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:66
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:479
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: bool.hpp:395
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:268
Integer sets.
Definition: int.hh:174
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
int max(void) const
Return maximum of domain.
Definition: bool.hpp:66
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:465
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
#define GECODE_INT_EXPORT
Definition: int.hh:81
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:454
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:248
BoolVarImp * copy(Space &home)
Return copy of this variable.
Definition: bool.hpp:258
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: bool.hpp:105
Boolean variable implementation.
Definition: var-imp.hpp:491
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: bool.hpp:405
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: bool.hpp:149
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:670
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:842
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:96
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: bool.hpp:201
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:200
int max(void) const
Return largest value of range.
Definition: int.hpp:450
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition: int.hpp:991
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition: var-imp.hpp:252
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition: int.cpp:368
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: bool.hpp:297
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int ModEvent
Type for modification events.
Definition: core.hpp:62
RangeList dom
Domain information.
Definition: var-imp.hpp:188
Base-class for freelist-managed objects.
Definition: manager.hpp:98
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:835
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:53
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
int max(void) const
Return largest value of range.
Definition: int.hpp:488
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:253
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:106
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:333
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: bool.hpp:276
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: bool.hpp:332
Gecode::IntSet d(v, 7)
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:849
Base-class for advisors.
Definition: core.hpp:1292
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:678
int _min
Minimum of range.
Definition: var-imp.hpp:105
Integer delta information for advisors.
Definition: var-imp.hpp:51
void operator++(void)
Move iterator to next range (if possible)
Definition: int.hpp:441
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4270
static const BoolStatus ZERO
Status of domain assigned to zero.
Definition: var-imp.hpp:521
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: bool.hpp:351
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition: bool.cpp:68
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: bool.hpp:214
int val(void) const
Return assigned value (only if assigned)
Definition: bool.hpp:75
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: bool.hpp:70
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: bool.hpp:101
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Min _min("Int::Min")
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int min(void) const
Return minimum of domain.
Definition: bool.hpp:62
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool none(void) const
Test whether variable is not yet assigned.
Definition: bool.hpp:139
Gecode::IntArgs i({1, 2, 3, 4})
int min(void) const
Return minimum.
Definition: int.hpp:98
ModEvent one_none(Space &home)
Assign unassigned variable to one.
Definition: bool.cpp:42
Max _max("Int::Max")
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: bool.hpp:165
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: int.hpp:503
int min(void) const
Return smallest value of range.
Definition: int.hpp:484
Lists of ranges (intervals)
Definition: var-imp.hpp:102
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:344
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:437
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:317
int max(void) const
Return maximum of domain.
Definition: int.hpp:228
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: bool.hpp:238