Generated on Sat Feb 7 2015 02:01:17 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
15  * $Revision: 13292 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <cmath>
43 
44 namespace Gecode { namespace Int {
45 
46  class IntVarImp;
47  class BoolVarImp;
48 
55  class IntDelta : public Delta {
56  friend class IntVarImp;
57  friend class BoolVarImp;
58  private:
59  int _min;
60  int _max;
61  public:
63  IntDelta(void);
65  IntDelta(int min, int max);
67  IntDelta(int min);
68  private:
70  int min(void) const;
72  int max(void) const;
74  bool any(void) const;
75  };
76 
77 }}
78 
80 
81 namespace Gecode { namespace Int {
82 
83  class IntVarImpFwd;
84  class IntVarImpBwd;
85 
91  class IntVarImp : public IntVarImpBase {
92  friend class IntVarImpFwd;
93  friend class IntVarImpBwd;
94  protected:
104  class RangeList : public FreeList {
105  protected:
107  int _min;
109  int _max;
110  public:
112 
113  RangeList(void);
116  RangeList(int min, int max);
118  RangeList(int min, int max, RangeList* p, RangeList* n);
120 
122 
123  int min(void) const;
126  int max(void) const;
128  unsigned int width(void) const;
129 
131  RangeList* next(const RangeList* p) const;
133  RangeList* prev(const RangeList* n) const;
135 
137 
138  void min(int n);
141  void max(int n);
142 
144  void prevnext(RangeList* p, RangeList* n);
146  void next(RangeList* o, RangeList* n);
148  void prev(RangeList* o, RangeList* n);
150  void fix(RangeList* n);
152 
154 
155 
160  void dispose(Space& home, RangeList* p, RangeList* l);
166  void dispose(Space& home, RangeList* l);
168  void dispose(Space& home);
169 
171  static void* operator new(size_t s, Space& home);
173  static void* operator new(size_t s, void* p);
175  static void operator delete(void*);
177  static void operator delete(void*, Space&);
179  static void operator delete(void*, void*);
181  };
182 
194  RangeList* fst(void) const;
196  void fst(RangeList* f);
198  RangeList* lst(void) const;
200  void lst(RangeList* l);
202  unsigned int holes;
203 
204  protected:
206  IntVarImp(Space& home, bool share, IntVarImp& x);
207  public:
209  IntVarImp(Space& home, int min, int max);
211  IntVarImp(Space& home, const IntSet& d);
212 
214 
215  int min(void) const;
218  int max(void) const;
220  int val(void) const;
222  GECODE_INT_EXPORT int med(void) const;
223 
225  unsigned int size(void) const;
227  unsigned int width(void) const;
229  unsigned int regret_min(void) const;
231  unsigned int regret_max(void) const;
233 
234  private:
236  GECODE_INT_EXPORT bool in_full(int n) const;
237 
238  public:
240 
241  bool range(void) const;
244  bool assigned(void) const;
245 
247  bool in(int n) const;
249  bool in(long long int n) const;
251 
252  protected:
254 
255  const RangeList* ranges_fwd(void) const;
258  const RangeList* ranges_bwd(void) const;
260 
261  private:
263  bool closer_min(int b) const;
265 
266  GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n);
269  GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n);
271  GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n);
273  GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n);
275  public:
277 
278  ModEvent lq(Space& home, int n);
281  ModEvent lq(Space& home, long long int n);
282 
284  ModEvent gq(Space& home, int n);
286  ModEvent gq(Space& home, long long int n);
287 
289  ModEvent nq(Space& home, int n);
291  ModEvent nq(Space& home, long long int n);
292 
294  ModEvent eq(Space& home, int n);
296  ModEvent eq(Space& home, long long int n);
298 
315  template<class I>
317  ModEvent narrow_r(Space& home, I& i, bool depends=true);
319  template<class I>
320  ModEvent inter_r(Space& home, I& i, bool depends=true);
322  template<class I>
323  ModEvent minus_r(Space& home, I& i, bool depends=true);
325  template<class I>
326  ModEvent narrow_v(Space& home, I& i, bool depends=true);
328  template<class I>
329  ModEvent inter_v(Space& home, I& i, bool depends=true);
331  template<class I>
332  ModEvent minus_v(Space& home, I& i, bool depends=true);
334 
336 
337 
345  void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
347  void cancel(Space& home, Propagator& p, PropCond pc);
349  void subscribe(Space& home, Advisor& a);
351  void cancel(Space& home, Advisor& a);
353 
355 
356  static ModEventDelta med(ModEvent me);
359 
360 
361  private:
363  GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home, bool share);
364  public:
366 
367  IntVarImp* copy(Space& home, bool share);
370 
372 
373  static int min(const Delta& d);
376  static int max(const Delta& d);
378  static bool any(const Delta& d);
380  };
381 
382 
387  class IntVarImpFwd {
388  private:
390  const IntVarImp::RangeList* p;
392  const IntVarImp::RangeList* c;
393  public:
395 
396  IntVarImpFwd(void);
399  IntVarImpFwd(const IntVarImp* x);
401  void init(const IntVarImp* x);
403 
405 
406  bool operator ()(void) const;
409  void operator ++(void);
411 
413 
414  int min(void) const;
417  int max(void) const;
419  unsigned int width(void) const;
421  };
422 
430  class IntVarImpBwd {
431  private:
433  const IntVarImp::RangeList* n;
435  const IntVarImp::RangeList* c;
436  public:
438 
439  IntVarImpBwd(void);
442  IntVarImpBwd(const IntVarImp* x);
444  void init(const IntVarImp* x);
446 
448 
449  bool operator ()(void) const;
452  void operator ++(void);
454 
456 
457  int min(void) const;
460  int max(void) const;
462  unsigned int width(void) const;
464  };
465 
466 }}
467 
469 
470 namespace Gecode {
471 
472  class IntVar;
473  class BoolVar;
474 }
475 
476 namespace Gecode { namespace Int {
477 
479  typedef unsigned int BoolStatus;
480 
486  class BoolVarImp : public BoolVarImpBase {
487  friend class ::Gecode::BoolVar;
488  private:
500  GECODE_INT_EXPORT static BoolVarImp s_one;
501  GECODE_INT_EXPORT static BoolVarImp s_zero;
502 
504  BoolVarImp(Space& home, bool share, BoolVarImp& x);
506  BoolVarImp(int n);
507  public:
509  BoolVarImp(Space& home, int min, int max);
510 
512 
513  static const int BITS = 2;
516  static const BoolStatus ZERO = 0;
518  static const BoolStatus ONE = 3;
520  static const BoolStatus NONE = 2;
522  BoolStatus status(void) const;
524 
526 
527  int min(void) const;
530  int max(void) const;
532  int val(void) const;
534  int med(void) const;
535 
537  unsigned int size(void) const;
539  unsigned int width(void) const;
541  unsigned int regret_min(void) const;
543  unsigned int regret_max(void) const;
545 
547 
548  bool zero(void) const;
551  bool one(void) const;
553  bool none(void) const;
555 
557 
558  bool range(void) const;
561  bool assigned(void) const;
562 
564  bool in(int n) const;
566  bool in(long long int n) const;
568 
570 
571  ModEvent lq(Space& home, int n);
574  ModEvent lq(Space& home, long long int n);
575 
577  ModEvent gq(Space& home, int n);
579  ModEvent gq(Space& home, long long int n);
580 
582  ModEvent nq(Space& home, int n);
584  ModEvent nq(Space& home, long long int n);
585 
587  ModEvent eq(Space& home, int n);
589  ModEvent eq(Space& home, long long int n);
591 
608  template<class I>
610  ModEvent narrow_r(Space& home, I& i, bool depends=true);
612  template<class I>
613  ModEvent inter_r(Space& home, I& i, bool depends=true);
615  template<class I>
616  ModEvent minus_r(Space& home, I& i, bool depends=true);
618  template<class I>
619  ModEvent narrow_v(Space& home, I& i, bool depends=true);
621  template<class I>
622  ModEvent inter_v(Space& home, I& i, bool depends=true);
624  template<class I>
625  ModEvent minus_v(Space& home, I& i, bool depends=true);
627 
629 
630  ModEvent zero(Space& home);
633  ModEvent one(Space& home);
639 
640  public:
642 
643 
653  void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
660  void cancel(Space& home, Propagator& p, PropCond pc);
662  void subscribe(Space& home, Advisor& a);
664  void cancel(Space& home, Advisor& a);
666 
668 
669 
676  static void schedule(Space& home, Propagator& p, ModEvent me);
678  static ModEventDelta med(ModEvent me);
680 
682 
683  static ModEvent modevent(const Delta& d);
686  static int min(const Delta& d);
688  static int max(const Delta& d);
690  static bool any(const Delta& d);
692  static bool zero(const Delta& d);
694  static bool one(const Delta& d);
696 
698 
699  BoolVarImp* copy(Space& home, bool share);
702 
703  };
704 
705 }}
706 
708 
709 // STATISTICS: int-var
710 
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:408
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: bool.hpp:314
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:386
bool assigned(void) const
Test whether variable is assigned.
Definition: bool.hpp:89
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:257
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: bool.hpp:201
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: int.hpp:1006
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:95
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: bool.hpp:109
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:138
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: bool.hpp:105
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: bool.hpp:74
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:88
int min(void) const
Return minimum.
Definition: int.hpp:102
int min(void) const
Return smallest value of range.
Definition: int.hpp:484
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:479
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:192
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:57
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:475
static const BoolStatus NONE
Status of domain not yet assigned.
Definition: var-imp.hpp:520
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: bool.hpp:402
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: int.hpp:1002
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition: bool.cpp:55
int min(void) const
Return minimum of domain.
Definition: bool.hpp:66
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
bool zero(void) const
Test whether variable is assigned to zero.
Definition: bool.hpp:135
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: bool.hpp:370
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: bool.hpp:165
Base-class for propagators.
Definition: core.hpp:755
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:437
FreeList * next(void) const
Return next freelist object.
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:365
bool range(void) const
Test whether domain is a range.
Definition: bool.hpp:85
IntVarImpFwd(void)
Default constructor.
Definition: int.hpp:427
Base-class for advisors.
Definition: core.hpp:926
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1362
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:177
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:470
Min _min("Int::Min")
Boolean variable implementation.
Definition: var-imp.hpp:486
RangeList(void)
Default constructor (noop)
Definition: int.hpp:53
Gecode::IntSet d(v, 7)
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:454
static const BoolStatus ONE
Status of domain assigned to one.
Definition: var-imp.hpp:518
bool one(void) const
Test whether variable is assigned to one.
Definition: bool.hpp:139
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:236
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:465
BoolStatus status(void) const
Return current domain status.
Definition: bool.hpp:62
int _max
Maximum of range.
Definition: var-imp.hpp:109
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:246
int max(void) const
Return largest value of range.
Definition: int.hpp:450
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Max _max("Int::Max")
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:479
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:242
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
int max(void) const
Return maximum.
Definition: int.hpp:106
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:387
bool none(void) const
Test whether variable is not yet assigned.
Definition: bool.hpp:143
Backward iterator for ranges of integer variable implementations.
Definition: var-imp.hpp:430
int min(void) const
Return smallest value of range.
Definition: int.hpp:446
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:272
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:70
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:670
Integer sets.
Definition: int.hh:171
IntVarImp * copy(Space &home, bool share)
Return copy of this variable.
Definition: int.hpp:991
bool in(int n) const
Test whether n is contained in domain.
Definition: bool.hpp:121
BoolVarImp * copy(Space &home, bool share)
Return copy of this variable.
Definition: bool.hpp:258
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p to variable with propagation condition pc.
Definition: bool.hpp:395
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:202
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:314
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:849
static const BoolStatus ZERO
Status of domain assigned to zero.
Definition: var-imp.hpp:516
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:835
Integer delta information for advisors.
Definition: var-imp.hpp:55
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: bool.hpp:351
Integer variable implementation.
Definition: var-imp.hpp:91
RangeList dom
Domain information.
Definition: var-imp.hpp:190
IntVarImp(Space &home, bool share, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:319
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:842
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
Lists of ranges (intervals)
Definition: var-imp.hpp:104
ModEvent one_none(Space &home)
Assign unassigned variable to one.
Definition: bool.cpp:46
int max(void) const
Return maximum of domain.
Definition: int.hpp:232
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: bool.hpp:297
void operator++(void)
Move iterator to next range (if possible)
Definition: int.hpp:441
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:110
IntDelta(void)
Create integer delta as providing no information.
Definition: delta.hpp:41
int val(void) const
Return assigned value (only if assigned)
Definition: bool.hpp:79
Base-class for Bool-variable implementations.
Definition: var-imp.hpp:82
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: bool.hpp:238
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:74
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:678
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:100
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:492
Base-class for freelist-managed objects.
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:290
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:50
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:333
Gecode toplevel namespace
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:309
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: bool.hpp:214
int max(void) const
Return maximum of domain.
Definition: bool.hpp:70
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: bool.hpp:416
int _min
Minimum of range.
Definition: var-imp.hpp:107
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: bool.hpp:332
#define GECODE_INT_EXPORT
Definition: int.hh:78
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: bool.hpp:153
int max(void) const
Return largest value of range.
Definition: int.hpp:488
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
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 minimum of domain.
Definition: int.hpp:228
static const int BITS
How many bits does the status have.
Definition: var-imp.hpp:514
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:167
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:262
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:252
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:344
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: bool.hpp:227
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: bool.hpp:276