Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
40namespace 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
79namespace 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
112 RangeList(void);
114 RangeList(int min, int max);
116 RangeList(int min, int max, RangeList* p, RangeList* n);
118
120
121
122 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
137 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
214 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
240 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
254 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
265 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
277 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
314 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
362
363
364 private:
366 GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home);
367 public:
369
370
371 IntVarImp* copy(Space& home);
373
375
376
377 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
393 private:
395 const IntVarImp::RangeList* p;
397 const IntVarImp::RangeList* c;
398 public:
400
401
402 IntVarImpFwd(void);
404 IntVarImpFwd(const IntVarImp* x);
406 void init(const IntVarImp* x);
408
410
411
412 bool operator ()(void) const;
414 void operator ++(void);
416
418
419
420 int min(void) const;
422 int max(void) const;
424 unsigned int width(void) const;
426 };
427
436 private:
438 const IntVarImp::RangeList* n;
440 const IntVarImp::RangeList* c;
441 public:
443
444
445 IntVarImpBwd(void);
447 IntVarImpBwd(const IntVarImp* x);
449 void init(const IntVarImp* x);
451
453
454
455 bool operator ()(void) const;
457 void operator ++(void);
459
461
462
463 int min(void) const;
465 int max(void) const;
467 unsigned int width(void) const;
469 };
470
471}}
472
474
475namespace Gecode {
476
477 class IntVar;
478 class BoolVar;
479}
480
481namespace Gecode { namespace Int {
482
484 typedef unsigned int BoolStatus;
485
491 class BoolVarImp : public BoolVarImpBase {
492 friend class ::Gecode::BoolVar;
493 private:
504
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
519 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
533 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
554 bool zero(void) const;
556 bool one(void) const;
558 bool none(void) const;
560
562
563
564 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
577 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
614 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
636 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);
694
696
697
698 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
716 BoolVarImp* copy(Space& home);
718
719 };
720
721}}
722
724
725// STATISTICS: int-var
726
Base-class for advisors.
Definition core.hpp:1294
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
FreeList(void)
Use uninitialized.
Definition manager.hpp:241
FreeList * next(void) const
Return next freelist object.
Definition manager.hpp:248
Integer sets.
Definition int.hh:174
BoolVarImpBase(Gecode::Space &home, BoolVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:300
Boolean variable implementation.
Definition var-imp.hpp:491
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition bool.hpp:201
bool zero(void) const
Test whether variable is assigned to zero.
Definition bool.hpp:131
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition bool.hpp:238
unsigned int size(void) const
Return size (cardinality) of domain.
Definition bool.hpp:96
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition bool.hpp:351
static const int BITS
How many bits does the status have.
Definition var-imp.hpp:519
bool none(void) const
Test whether variable is not yet assigned.
Definition bool.hpp:139
int max(void) const
Return maximum of domain.
Definition bool.hpp:66
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition bool.hpp:227
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition bool.hpp:405
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition bool.hpp:332
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition bool.hpp:91
bool one(void) const
Test whether variable is assigned to one.
Definition bool.hpp:135
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition bool.hpp:276
int min(void) const
Return minimum of domain.
Definition bool.hpp:62
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition bool.hpp:297
ModEvent one_none(Space &home)
Assign unassigned variable to one.
Definition bool.cpp:42
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition bool.hpp:165
static const BoolStatus NONE
Status of domain not yet assigned.
Definition var-imp.hpp:525
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p to variable with propagation condition pc.
Definition bool.cpp:60
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p.
Definition bool.cpp:68
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition bool.hpp:70
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
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition bool.hpp:314
static const BoolStatus ZERO
Status of domain assigned to zero.
Definition var-imp.hpp:521
bool assigned(void) const
Test whether variable is assigned.
Definition bool.hpp:85
bool in(int n) const
Test whether n is contained in domain.
Definition bool.hpp:117
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition bool.cpp:51
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition bool.hpp:214
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition bool.hpp:101
bool range(void) const
Test whether domain is a range.
Definition bool.hpp:81
static const BoolStatus ONE
Status of domain assigned to one.
Definition var-imp.hpp:523
BoolStatus status(void) const
Return current domain status.
Definition bool.hpp:58
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition bool.hpp:370
int val(void) const
Return assigned value (only if assigned)
Definition bool.hpp:75
static ModEvent modevent(const Delta &d)
Return modification event.
Definition bool.hpp:149
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition bool.hpp:395
friend class BoolVarImp
Definition var-imp.hpp:53
IntDelta(void)
Create integer delta as providing no information.
Definition delta.hpp:37
friend class IntVarImp
Definition var-imp.hpp:52
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition var-imp.hpp:252
IntVarImpBase(Gecode::Space &home, IntVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:239
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition int.hpp:492
void operator++(void)
Move iterator to previous range (if possible)
Definition int.hpp:479
int max(void) const
Return largest value of range.
Definition int.hpp:488
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:484
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition int.hpp:470
IntVarImpBwd(void)
Default constructor.
Definition int.hpp:465
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition int.hpp:432
IntVarImpFwd(void)
Default constructor.
Definition int.hpp:427
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition int.hpp:437
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition int.hpp:454
int min(void) const
Return smallest value of range.
Definition int.hpp:446
void operator++(void)
Move iterator to next range (if possible)
Definition int.hpp:441
int max(void) const
Return largest value of range.
Definition int.hpp:450
Lists of ranges (intervals)
Definition var-imp.hpp:102
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition int.hpp:106
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition int.hpp:84
int _max
Maximum of range.
Definition var-imp.hpp:107
int _min
Minimum of range.
Definition var-imp.hpp:105
RangeList(void)
Default constructor (noop)
Definition int.hpp:49
int min(void) const
Return minimum.
Definition int.hpp:98
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition int.hpp:70
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition int.hpp:66
int max(void) const
Return maximum.
Definition int.hpp:102
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition int.hpp:134
Integer variable implementation.
Definition var-imp.hpp:89
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
RangeList * lst(void) const
Return last element of rangelist.
Definition int.hpp:173
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition int.hpp:248
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:386
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition int.cpp:46
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition int.hpp:835
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition int.hpp:268
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition int.hpp:842
bool in(int n) const
Test whether n is contained in domain.
Definition int.hpp:286
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition int.hpp:991
bool assigned(void) const
Test whether variable is assigned.
Definition int.hpp:242
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:365
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition int.hpp:408
int max(void) const
Return maximum of domain.
Definition int.hpp:228
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition int.hpp:849
int val(void) const
Return assigned value (only if assigned)
Definition int.hpp:232
RangeList * fst(void) const
Return first element of rangelist.
Definition int.hpp:163
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 size(void) const
Return size (cardinality) of domain.
Definition int.hpp:253
int min(void) const
Return minimum of domain.
Definition int.hpp:224
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition int.hpp:258
RangeList dom
Domain information.
Definition var-imp.hpp:188
unsigned int holes
Size of holes in the domain.
Definition var-imp.hpp:200
bool range(void) const
Test whether domain is a range.
Definition int.hpp:238
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition int.hpp:503
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition int.cpp:317
friend class IntVarImpBwd
Definition var-imp.hpp:91
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 int.hpp:670
friend class IntVarImpFwd
Definition var-imp.hpp:90
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition int.hpp:678
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:344
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition int.hpp:305
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition int.hpp:333
Base-class for propagators.
Definition core.hpp:1066
Computation spaces.
Definition core.hpp:1744
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4277
#define GECODE_INT_EXPORT
Definition int.hh:81
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Finite domain integers.
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition var-imp.hpp:484
Gecode toplevel namespace
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62