Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
15  * $Revision$
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  unsigned int width(void) const;
76  bool any(void) const;
77  };
78 
79 }}
80 
82 
83 namespace Gecode { namespace Int {
84 
85  class IntVarImpFwd;
86  class IntVarImpBwd;
87 
93  class IntVarImp : public IntVarImpBase {
94  friend class IntVarImpFwd;
95  friend class IntVarImpBwd;
96  protected:
106  class RangeList : public FreeList {
107  protected:
109  int _min;
111  int _max;
112  public:
114 
115  RangeList(void);
118  RangeList(int min, int max);
120  RangeList(int min, int max, RangeList* p, RangeList* n);
122 
124 
125  int min(void) const;
128  int max(void) const;
130  unsigned int width(void) const;
131 
133  RangeList* next(const RangeList* p) const;
135  RangeList* prev(const RangeList* n) const;
137 
139 
140  void min(int n);
143  void max(int n);
144 
146  void prevnext(RangeList* p, RangeList* n);
148  void next(RangeList* o, RangeList* n);
150  void prev(RangeList* o, RangeList* n);
152  void fix(RangeList* n);
154 
156 
157 
162  void dispose(Space& home, RangeList* p, RangeList* l);
168  void dispose(Space& home, RangeList* l);
170  void dispose(Space& home);
171 
173  static void* operator new(size_t s, Space& home);
175  static void* operator new(size_t s, void* p);
177  static void operator delete(void*);
179  static void operator delete(void*, Space&);
181  static void operator delete(void*, void*);
183  };
184 
196  RangeList* fst(void) const;
198  void fst(RangeList* f);
200  RangeList* lst(void) const;
202  void lst(RangeList* l);
204  unsigned int holes;
205 
206  protected:
208  IntVarImp(Space& home, IntVarImp& x);
209  public:
211  IntVarImp(Space& home, int min, int max);
213  IntVarImp(Space& home, const IntSet& d);
214 
216 
217  int min(void) const;
220  int max(void) const;
222  int val(void) const;
224  GECODE_INT_EXPORT int med(void) const;
225 
227  unsigned int size(void) const;
229  unsigned int width(void) const;
231  unsigned int regret_min(void) const;
233  unsigned int regret_max(void) const;
235 
236  private:
238  GECODE_INT_EXPORT bool in_full(int n) const;
239 
240  public:
242 
243  bool range(void) const;
246  bool assigned(void) const;
247 
249  bool in(int n) const;
251  bool in(long long int n) const;
253 
254  protected:
256 
257  const RangeList* ranges_fwd(void) const;
260  const RangeList* ranges_bwd(void) const;
262 
263  private:
265  bool closer_min(int b) const;
267 
268  GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n);
271  GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n);
273  GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n);
275  GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n);
277  public:
279 
280  ModEvent lq(Space& home, int n);
283  ModEvent lq(Space& home, long long int n);
284 
286  ModEvent gq(Space& home, int n);
288  ModEvent gq(Space& home, long long int n);
289 
291  ModEvent nq(Space& home, int n);
293  ModEvent nq(Space& home, long long int n);
294 
296  ModEvent eq(Space& home, int n);
298  ModEvent eq(Space& home, long long int n);
300 
317  template<class I>
319  ModEvent narrow_r(Space& home, I& i, bool depends=true);
321  template<class I>
322  ModEvent inter_r(Space& home, I& i, bool depends=true);
324  template<class I>
325  ModEvent minus_r(Space& home, I& i, bool depends=true);
327  template<class I>
328  ModEvent narrow_v(Space& home, I& i, bool depends=true);
330  template<class I>
331  ModEvent inter_v(Space& home, I& i, bool depends=true);
333  template<class I>
334  ModEvent minus_v(Space& home, I& i, bool depends=true);
336 
338 
339 
347  GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
358  GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
360 
362 
363  static ModEventDelta med(ModEvent me);
366 
367 
368  private:
370  GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home);
371  public:
373 
374  IntVarImp* copy(Space& home);
377 
379 
380  static int min(const Delta& d);
383  static int max(const Delta& d);
385  static unsigned int width(const Delta& d);
387  static bool any(const Delta& d);
389  };
390 
391 
396  class IntVarImpFwd {
397  private:
399  const IntVarImp::RangeList* p;
401  const IntVarImp::RangeList* c;
402  public:
404 
405  IntVarImpFwd(void);
408  IntVarImpFwd(const IntVarImp* x);
410  void init(const IntVarImp* x);
412 
414 
415  bool operator ()(void) const;
418  void operator ++(void);
420 
422 
423  int min(void) const;
426  int max(void) const;
428  unsigned int width(void) const;
430  };
431 
439  class IntVarImpBwd {
440  private:
442  const IntVarImp::RangeList* n;
444  const IntVarImp::RangeList* c;
445  public:
447 
448  IntVarImpBwd(void);
451  IntVarImpBwd(const IntVarImp* x);
453  void init(const IntVarImp* x);
455 
457 
458  bool operator ()(void) const;
461  void operator ++(void);
463 
465 
466  int min(void) const;
469  int max(void) const;
471  unsigned int width(void) const;
473  };
474 
475 }}
476 
478 
479 namespace Gecode {
480 
481  class IntVar;
482  class BoolVar;
483 }
484 
485 namespace Gecode { namespace Int {
486 
488  typedef unsigned int BoolStatus;
489 
495  class BoolVarImp : public BoolVarImpBase {
496  friend class ::Gecode::BoolVar;
497  private:
509  GECODE_INT_EXPORT static BoolVarImp s_one;
510  GECODE_INT_EXPORT static BoolVarImp s_zero;
511 
513  BoolVarImp(Space& home, BoolVarImp& x);
515  BoolVarImp(int n);
516  public:
518  BoolVarImp(Space& home, int min, int max);
519 
521 
522  static const int BITS = 2;
525  static const BoolStatus ZERO = 0;
527  static const BoolStatus ONE = 3;
529  static const BoolStatus NONE = 2;
531  BoolStatus status(void) const;
533 
535 
536  int min(void) const;
539  int max(void) const;
541  int val(void) const;
543  int med(void) const;
544 
546  unsigned int size(void) const;
548  unsigned int width(void) const;
550  unsigned int regret_min(void) const;
552  unsigned int regret_max(void) const;
554 
556 
557  bool zero(void) const;
560  bool one(void) const;
562  bool none(void) const;
564 
566 
567  bool range(void) const;
570  bool assigned(void) const;
571 
573  bool in(int n) const;
575  bool in(long long int n) const;
577 
579 
580  ModEvent lq(Space& home, int n);
583  ModEvent lq(Space& home, long long int n);
584 
586  ModEvent gq(Space& home, int n);
588  ModEvent gq(Space& home, long long int n);
589 
591  ModEvent nq(Space& home, int n);
593  ModEvent nq(Space& home, long long int n);
594 
596  ModEvent eq(Space& home, int n);
598  ModEvent eq(Space& home, long long int n);
600 
617  template<class I>
619  ModEvent narrow_r(Space& home, I& i, bool depends=true);
621  template<class I>
622  ModEvent inter_r(Space& home, I& i, bool depends=true);
624  template<class I>
625  ModEvent minus_r(Space& home, I& i, bool depends=true);
627  template<class I>
628  ModEvent narrow_v(Space& home, I& i, bool depends=true);
630  template<class I>
631  ModEvent inter_v(Space& home, I& i, bool depends=true);
633  template<class I>
634  ModEvent minus_v(Space& home, I& i, bool depends=true);
636 
638 
639  ModEvent zero(Space& home);
642  ModEvent one(Space& home);
644  GECODE_INT_EXPORT ModEvent zero_none(Space& home);
646  GECODE_INT_EXPORT ModEvent one_none(Space& home);
648 
649  public:
651 
652 
662  GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
669  void cancel(Space& home, Propagator& p, PropCond pc);
678  GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
680  void cancel(Space& home, Advisor& a, bool fail);
682 
684 
685 
692  static void schedule(Space& home, Propagator& p, ModEvent me);
696  static ModEventDelta med(ModEvent me);
698 
700 
701  static ModEvent modevent(const Delta& d);
704  static int min(const Delta& d);
706  static int max(const Delta& d);
708  static unsigned int width(const Delta& d);
710  static bool any(const Delta& d);
712  static bool zero(const Delta& d);
714  static bool one(const Delta& d);
716 
718 
719  BoolVarImp* copy(Space& home);
722 
723  };
724 
725 }}
726 
728 
729 // STATISTICS: int-var
730 
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:50
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:488
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:194
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:57
int ModEvent
Type for modification events.
Definition: core.hpp:64
Base-class for propagators.
Definition: core.hpp:1016
Base-class for advisors.
Definition: core.hpp:1218
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1668
Min _min("Int::Min")
Boolean variable implementation.
Definition: var-imp.hpp:495
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
int _max
Maximum of range.
Definition: var-imp.hpp:111
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Max _max("Int::Max")
int PropCond
Type for propagation conditions.
Definition: core.hpp:74
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
unsigned int size(I &i)
Size of all ranges of range iterator i.
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:2030
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:396
Backward iterator for ranges of integer variable implementations.
Definition: var-imp.hpp:439
Integer sets.
Definition: int.hh:174
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:204
Boolean integer variables.
Definition: int.hh:492
Integer delta information for advisors.
Definition: var-imp.hpp:55
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer variable implementation.
Definition: var-imp.hpp:93
RangeList dom
Domain information.
Definition: var-imp.hpp:192
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
Lists of ranges (intervals)
Definition: var-imp.hpp:106
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Integer variables.
Definition: int.hh:351
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
IntDelta(void)
Create integer delta as providing no information.
Definition: delta.hpp:41
Base-class for Bool-variable implementations.
Definition: var-imp.hpp:93
Base-class for freelist-managed objects.
Definition: manager.hpp:102
Post propagator for SetVar x
Definition: set.hh:769
friend class BoolVarImp
Definition: var-imp.hpp:57
Gecode toplevel namespace
friend class IntVarImp
Definition: var-imp.hpp:56
int _min
Minimum of range.
Definition: var-imp.hpp:109
#define GECODE_INT_EXPORT
Definition: int.hh:81
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91