Generated on Sat Jul 29 2017 12:41:24 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: 2017-03-09 09:51:58 +0100 (Thu, 09 Mar 2017) $ by $Author: schulte $
15  * $Revision: 15565 $
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  GECODE_INT_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
356  GECODE_INT_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
358 
360 
361  static ModEventDelta med(ModEvent me);
364 
365 
366  private:
368  GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home, bool share);
369  public:
371 
372  IntVarImp* copy(Space& home, bool share);
375 
377 
378  static int min(const Delta& d);
381  static int max(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, bool share, 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);
640  GECODE_INT_EXPORT ModEvent zero_none(Space& home);
642  GECODE_INT_EXPORT ModEvent one_none(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 bool any(const Delta& d);
706  static bool zero(const Delta& d);
708  static bool one(const Delta& d);
710 
712 
713  BoolVarImp* copy(Space& home, bool share);
716 
717  };
718 
719 }}
720 
722 
723 // STATISTICS: int-var
724 
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:484
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
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1092
Base-class for advisors.
Definition: core.hpp:1294
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1748
Min _min("Int::Min")
Boolean variable implementation.
Definition: var-imp.hpp:491
Gecode::IntSet d(v, 7)
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
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: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:152
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.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:1901
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
Integer sets.
Definition: int.hh:174
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:202
Boolean integer variables.
Definition: int.hh:494
Integer delta information for advisors.
Definition: var-imp.hpp:55
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer variable implementation.
Definition: var-imp.hpp:91
RangeList dom
Domain information.
Definition: var-imp.hpp:190
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
Lists of ranges (intervals)
Definition: var-imp.hpp:104
Integer variables.
Definition: int.hh:353
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.
Post propagator for SetVar x
Definition: set.hh:784
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:107
#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:169