Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
bool.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  * Copyright:
7  * Christian Schulte, 2006
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Int {
35 
36  /*
37  * Creation of new variable implementations
38  *
39  */
41  BoolVarImp::BoolVarImp(int n) {
42  assert(bits() == 0);
43  bits() |= (n << 1) | n;
44  }
46  BoolVarImp::BoolVarImp(Space& home, int min, int max)
47  : BoolVarImpBase(home) {
48  assert(bits() == 0);
49  bits() |= (max << 1) | min;
50  }
51 
52 
53  /*
54  * Operations on Boolean variable implementations
55  *
56  */
58  BoolVarImp::status(void) const {
59  return bits() & 3;
60  }
61  forceinline int
62  BoolVarImp::min(void) const {
63  return static_cast<int>(bits() & 1);
64  }
65  forceinline int
66  BoolVarImp::max(void) const {
67  return static_cast<int>((bits() & 2) >> 1);
68  }
69  forceinline int
70  BoolVarImp::med(void) const {
71  return min();
72  }
73 
74  forceinline int
75  BoolVarImp::val(void) const {
76  assert(status() != NONE);
77  return min();
78  }
79 
80  forceinline bool
81  BoolVarImp::range(void) const {
82  return true;
83  }
84  forceinline bool
85  BoolVarImp::assigned(void) const {
86  return status() != NONE;
87  }
88 
89 
90  forceinline unsigned int
91  BoolVarImp::width(void) const {
92  return assigned() ? 1U : 2U;
93  }
94 
95  forceinline unsigned int
96  BoolVarImp::size(void) const {
97  return assigned() ? 1U : 2U;
98  }
99 
100  forceinline unsigned int
102  return assigned() ? 1U : 0U;
103  }
104  forceinline unsigned int
106  return assigned() ? 1U : 0U;
107  }
108 
109 
110 
111  /*
112  * Tests
113  *
114  */
115 
116  forceinline bool
117  BoolVarImp::in(int n) const {
118  return (n >= min()) && (n <= max());
119  }
120  forceinline bool
121  BoolVarImp::in(long long int n) const {
122  return (n >= min()) && (n <= max());
123  }
124 
125 
126  /*
127  * Boolean domain tests
128  *
129  */
130  forceinline bool
131  BoolVarImp::zero(void) const {
132  return status() < NONE;
133  }
134  forceinline bool
135  BoolVarImp::one(void) const {
136  return status() > NONE;
137  }
138  forceinline bool
139  BoolVarImp::none(void) const {
140  return status() == NONE;
141  }
142 
143 
144  /*
145  * Support for delta information
146  *
147  */
150  return ME_BOOL_VAL;
151  }
152  forceinline int
154  return static_cast<const IntDelta&>(d).min();
155  }
156  forceinline int
158  return static_cast<const IntDelta&>(d).min();
159  }
160  forceinline unsigned int
162  return static_cast<const IntDelta&>(d).width();
163  }
164  forceinline bool
166  return false;
167  }
168  forceinline bool
170  return static_cast<const IntDelta&>(d).min() != 0;
171  }
172  forceinline bool
174  return static_cast<const IntDelta&>(d).min() == 0;
175  }
176 
177 
178  /*
179  * Boolean tell operations
180  *
181  */
184  if (one()) return ME_BOOL_FAILED;
185  if (zero()) return ME_BOOL_NONE;
186  return zero_none(home);
187  }
190  if (one()) return ME_BOOL_NONE;
191  if (zero()) return ME_BOOL_FAILED;
192  return one_none(home);
193  }
194 
195 
196  /*
197  * Tell operations
198  *
199  */
201  BoolVarImp::gq(Space& home, int n) {
202  if (n <= 0) return ME_INT_NONE;
203  if (n > 1) return fail(home);
204  return one(home);
205  }
207  BoolVarImp::gq(Space& home, long long int n) {
208  if (n <= 0) return ME_INT_NONE;
209  if (n > 1) return fail(home);
210  return one(home);
211  }
212 
214  BoolVarImp::lq(Space& home, int n) {
215  if (n < 0) return fail(home);
216  if (n >= 1) return ME_INT_NONE;
217  return zero(home);
218  }
220  BoolVarImp::lq(Space& home, long long int n) {
221  if (n < 0) return fail(home);
222  if (n >= 1) return ME_INT_NONE;
223  return zero(home);
224  }
225 
227  BoolVarImp::eq(Space& home, int n) {
228  if ((n < 0) || (n > 1)) return fail(home);
229  return (n == 0) ? zero(home): one(home);
230  }
232  BoolVarImp::eq(Space& home, long long int n) {
233  if ((n < 0) || (n > 1)) return fail(home);
234  return (n == 0) ? zero(home): one(home);
235  }
236 
238  BoolVarImp::nq(Space& home, int n) {
239  if ((n < 0) || (n > 1)) return ME_INT_NONE;
240  return (n == 0) ? one(home): zero(home);
241  }
243  BoolVarImp::nq(Space& home, long long int n) {
244  if ((n < 0) || (n > 1)) return ME_INT_NONE;
245  return (n == 0) ? one(home): zero(home);
246  }
247 
248 
249  /*
250  * Copying a variable
251  *
252  */
253 
255  BoolVarImp::BoolVarImp(Space& home, BoolVarImp& x)
256  : BoolVarImpBase(home,x) {}
259  if (copied())
260  return static_cast<BoolVarImp*>(forward());
261  else if (zero())
262  return &s_zero;
263  else if (one())
264  return &s_one;
265  else
266  return new (home) BoolVarImp(home,*this);
267  }
268 
269 
270  /*
271  * Iterator-based domain operations
272  *
273  */
274  template<class I>
276  BoolVarImp::narrow_r(Space& home, I& i, bool) {
277  // Is new domain empty?
278  if (!i())
279  return fail(home);
280  assert((i.min() == 0) || (i.min() == 1));
281  assert((i.max() == 0) || (i.max() == 1));
282  if (i.max() == 0) {
283  assert(!one());
284  // Assign domain to be zero (domain cannot be one)
285  return zero(home);
286  }
287  if (i.min() == 1) {
288  // Assign domain to be one (domain cannot be zero)
289  assert(!zero());
290  return one(home);
291  }
292  assert(none());
293  return ME_INT_NONE;
294  }
295  template<class I>
297  BoolVarImp::inter_r(Space& home, I& i, bool) {
298  // Skip all ranges that are too small
299  while (i() && (i.max() < 0))
300  ++i;
301  // Is new domain empty?
302  if (!i() || (i.min() > 1))
303  return fail(home);
304  assert(i.min() <= 1);
305  if (i.min() == 1)
306  return one(home);
307  if (i.max() == 0)
308  return zero(home);
309  assert((i.min() <= 0) && (i.max() >= 1));
310  return ME_INT_NONE;
311  }
312  template<class I>
314  BoolVarImp::minus_r(Space& home, I& i, bool) {
315  // Skip all ranges that are too small
316  while (i() && (i.max() < 0))
317  ++i;
318  // Is new domain empty?
319  if (!i() || (i.min() > 1))
320  return ME_INT_NONE;
321  assert(i.min() <= 1);
322  if (i.min() == 1)
323  return zero(home);
324  if (i.max() == 0)
325  return one(home);
326  assert((i.min() <= 0) && (i.max() >= 1));
327  return fail(home);
328  }
329 
330  template<class I>
332  BoolVarImp::narrow_v(Space& home, I& i, bool) {
333  if (!i())
334  return fail(home);
335  if (!none())
336  return ME_INT_NONE;
337  if (i.val() == 0) {
338  do {
339  ++i;
340  } while (i() && (i.val() == 0));
341  if (!i())
342  return zero_none(home);
343  return ME_INT_NONE;
344  } else {
345  assert(i.val() == 1);
346  return one_none(home);
347  }
348  }
349  template<class I>
351  BoolVarImp::inter_v(Space& home, I& i, bool) {
352  while (i() && (i.val() < 0))
353  ++i;
354  if (!i() || (i.val() > 1))
355  return fail(home);
356  if (i.val() == 0) {
357  do {
358  ++i;
359  } while (i() && (i.val() == 0));
360  if (!i() || (i.val() > 1))
361  return zero(home);
362  return ME_INT_NONE;
363  } else {
364  assert(i.val() == 1);
365  return one(home);
366  }
367  }
368  template<class I>
370  BoolVarImp::minus_v(Space& home, I& i, bool) {
371  while (i() && (i.val() < 0))
372  ++i;
373  if (!i() || (i.val() > 1))
374  return ME_INT_NONE;
375  if (i.val() == 0) {
376  do {
377  ++i;
378  } while (i() && (i.val() == 0));
379  if (!i() || (i.val() > 1))
380  return one(home);
381  return fail(home);
382  } else {
383  assert(i.val() == 1);
384  return zero(home);
385  }
386  }
387 
388 
389 
390  /*
391  * Dependencies
392  *
393  */
394  forceinline void
397  }
398 
399  forceinline void
401  BoolVarImpBase::cancel(home,a,fail);
402  }
403 
404  forceinline void
407  }
408 
411  return BoolVarImpBase::med(me);
412  }
413 
414 }}
415 
416 // STATISTICS: int-var
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: bool.hpp:314
BoolVarImp * copy(Space &home)
Return copy of this variable.
Definition: bool.hpp:258
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: bool.hpp:201
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4155
bool in(int n) const
Test whether n is contained in domain.
Definition: bool.hpp:117
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:484
static const BoolStatus NONE
Status of domain not yet assigned.
Definition: var-imp.hpp:525
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: bool.hpp:395
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition: bool.cpp:51
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:96
int ModEvent
Type for modification events.
Definition: core.hpp:62
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:1023
Base-class for advisors.
Definition: core.hpp:1251
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4203
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:91
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
bool zero(void) const
Test whether variable is assigned to zero.
Definition: bool.hpp:131
bool assigned(void) const
Test whether variable is assigned.
Definition: bool.hpp:85
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4414
Boolean variable implementation.
Definition: var-imp.hpp:491
Gecode::IntSet d(v, 7)
int min(void) const
Return minimum of domain.
Definition: bool.hpp:62
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4197
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4149
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
const Gecode::ModEvent ME_BOOL_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:114
int max(void) const
Return maximum of domain.
Definition: bool.hpp:66
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: bool.hpp:105
Integer delta information for advisors.
Definition: var-imp.hpp:51
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: bool.hpp:351
BoolStatus status(void) const
Return current domain status.
Definition: bool.hpp:58
bool range(void) const
Test whether domain is a range.
Definition: bool.hpp:81
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
ModEvent one_none(Space &home)
Assign unassigned variable to one.
Definition: bool.cpp:42
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: bool.hpp:297
bool none(void) const
Test whether variable is not yet assigned.
Definition: bool.hpp:139
int val(void) const
Return assigned value (only if assigned)
Definition: bool.hpp:75
Base-class for Bool-variable implementations.
Definition: var-imp.hpp:93
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: bool.hpp:238
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4497
Post propagator for SetVar x
Definition: set.hh:767
const Gecode::ModEvent ME_BOOL_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:112
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition: var-imp.hpp:313
Gecode toplevel namespace
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: bool.hpp:214
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
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: bool.hpp:149
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4123
BoolVarImpBase(void)
Constructor for creating static instance of variable.
Definition: var-imp.hpp:293
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: bool.hpp:101
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: bool.hpp:70
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: bool.hpp:227
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
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:126
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:116