Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
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 namespace Gecode { namespace Int {
39 
40  /*
41  * Creation of new variable implementations
42  *
43  */
45  BoolVarImp::BoolVarImp(int n) {
46  assert(bits() == 0);
47  bits() |= (n << 1) | n;
48  }
50  BoolVarImp::BoolVarImp(Space& home, int min, int max)
51  : BoolVarImpBase(home) {
52  assert(bits() == 0);
53  bits() |= (max << 1) | min;
54  }
55 
56 
57  /*
58  * Operations on Boolean variable implementations
59  *
60  */
62  BoolVarImp::status(void) const {
63  return bits() & 3;
64  }
65  forceinline int
66  BoolVarImp::min(void) const {
67  return static_cast<int>(bits() & 1);
68  }
69  forceinline int
70  BoolVarImp::max(void) const {
71  return static_cast<int>((bits() & 2) >> 1);
72  }
73  forceinline int
74  BoolVarImp::med(void) const {
75  return min();
76  }
77 
78  forceinline int
79  BoolVarImp::val(void) const {
80  assert(status() != NONE);
81  return min();
82  }
83 
84  forceinline bool
85  BoolVarImp::range(void) const {
86  return true;
87  }
88  forceinline bool
89  BoolVarImp::assigned(void) const {
90  return status() != NONE;
91  }
92 
93 
94  forceinline unsigned int
95  BoolVarImp::width(void) const {
96  return assigned() ? 1U : 2U;
97  }
98 
99  forceinline unsigned int
100  BoolVarImp::size(void) const {
101  return assigned() ? 1U : 2U;
102  }
103 
104  forceinline unsigned int
106  return assigned() ? 1U : 0U;
107  }
108  forceinline unsigned int
110  return assigned() ? 1U : 0U;
111  }
112 
113 
114 
115  /*
116  * Tests
117  *
118  */
119 
120  forceinline bool
121  BoolVarImp::in(int n) const {
122  return (n >= min()) && (n <= max());
123  }
124  forceinline bool
125  BoolVarImp::in(long long int n) const {
126  return (n >= min()) && (n <= max());
127  }
128 
129 
130  /*
131  * Boolean domain tests
132  *
133  */
134  forceinline bool
135  BoolVarImp::zero(void) const {
136  return status() < NONE;
137  }
138  forceinline bool
139  BoolVarImp::one(void) const {
140  return status() > NONE;
141  }
142  forceinline bool
143  BoolVarImp::none(void) const {
144  return status() == NONE;
145  }
146 
147 
148  /*
149  * Support for delta information
150  *
151  */
154  return ME_BOOL_VAL;
155  }
156  forceinline int
158  return static_cast<const IntDelta&>(d).min();
159  }
160  forceinline int
162  return static_cast<const IntDelta&>(d).min();
163  }
164  forceinline unsigned int
166  return static_cast<const IntDelta&>(d).width();
167  }
168  forceinline bool
170  return false;
171  }
172  forceinline bool
174  return static_cast<const IntDelta&>(d).min() != 0;
175  }
176  forceinline bool
178  return static_cast<const IntDelta&>(d).min() == 0;
179  }
180 
181 
182  /*
183  * Boolean tell operations
184  *
185  */
188  if (one()) return ME_BOOL_FAILED;
189  if (zero()) return ME_BOOL_NONE;
190  return zero_none(home);
191  }
194  if (one()) return ME_BOOL_NONE;
195  if (zero()) return ME_BOOL_FAILED;
196  return one_none(home);
197  }
198 
199 
200  /*
201  * Tell operations
202  *
203  */
205  BoolVarImp::gq(Space& home, int n) {
206  if (n <= 0) return ME_INT_NONE;
207  if (n > 1) return fail(home);
208  return one(home);
209  }
211  BoolVarImp::gq(Space& home, long long int n) {
212  if (n <= 0) return ME_INT_NONE;
213  if (n > 1) return fail(home);
214  return one(home);
215  }
216 
218  BoolVarImp::lq(Space& home, int n) {
219  if (n < 0) return fail(home);
220  if (n >= 1) return ME_INT_NONE;
221  return zero(home);
222  }
224  BoolVarImp::lq(Space& home, long long int n) {
225  if (n < 0) return fail(home);
226  if (n >= 1) return ME_INT_NONE;
227  return zero(home);
228  }
229 
231  BoolVarImp::eq(Space& home, int n) {
232  if ((n < 0) || (n > 1)) return fail(home);
233  return (n == 0) ? zero(home): one(home);
234  }
236  BoolVarImp::eq(Space& home, long long int n) {
237  if ((n < 0) || (n > 1)) return fail(home);
238  return (n == 0) ? zero(home): one(home);
239  }
240 
242  BoolVarImp::nq(Space& home, int n) {
243  if ((n < 0) || (n > 1)) return ME_INT_NONE;
244  return (n == 0) ? one(home): zero(home);
245  }
247  BoolVarImp::nq(Space& home, long long int n) {
248  if ((n < 0) || (n > 1)) return ME_INT_NONE;
249  return (n == 0) ? one(home): zero(home);
250  }
251 
252 
253  /*
254  * Copying a variable
255  *
256  */
257 
259  BoolVarImp::BoolVarImp(Space& home, BoolVarImp& x)
260  : BoolVarImpBase(home,x) {}
263  if (copied())
264  return static_cast<BoolVarImp*>(forward());
265  else if (zero())
266  return &s_zero;
267  else if (one())
268  return &s_one;
269  else
270  return new (home) BoolVarImp(home,*this);
271  }
272 
273 
274  /*
275  * Iterator-based domain operations
276  *
277  */
278  template<class I>
280  BoolVarImp::narrow_r(Space& home, I& i, bool) {
281  // Is new domain empty?
282  if (!i())
283  return fail(home);
284  assert((i.min() == 0) || (i.min() == 1));
285  assert((i.max() == 0) || (i.max() == 1));
286  if (i.max() == 0) {
287  assert(!one());
288  // Assign domain to be zero (domain cannot be one)
289  return zero(home);
290  }
291  if (i.min() == 1) {
292  // Assign domain to be one (domain cannot be zero)
293  assert(!zero());
294  return one(home);
295  }
296  assert(none());
297  return ME_INT_NONE;
298  }
299  template<class I>
301  BoolVarImp::inter_r(Space& home, I& i, bool) {
302  // Skip all ranges that are too small
303  while (i() && (i.max() < 0))
304  ++i;
305  // Is new domain empty?
306  if (!i() || (i.min() > 1))
307  return fail(home);
308  assert(i.min() <= 1);
309  if (i.min() == 1)
310  return one(home);
311  if (i.max() == 0)
312  return zero(home);
313  assert((i.min() <= 0) && (i.max() >= 1));
314  return ME_INT_NONE;
315  }
316  template<class I>
318  BoolVarImp::minus_r(Space& home, I& i, bool) {
319  // Skip all ranges that are too small
320  while (i() && (i.max() < 0))
321  ++i;
322  // Is new domain empty?
323  if (!i() || (i.min() > 1))
324  return ME_INT_NONE;
325  assert(i.min() <= 1);
326  if (i.min() == 1)
327  return zero(home);
328  if (i.max() == 0)
329  return one(home);
330  assert((i.min() <= 0) && (i.max() >= 1));
331  return fail(home);
332  }
333 
334  template<class I>
336  BoolVarImp::narrow_v(Space& home, I& i, bool) {
337  if (!i())
338  return fail(home);
339  if (!none())
340  return ME_INT_NONE;
341  if (i.val() == 0) {
342  do {
343  ++i;
344  } while (i() && (i.val() == 0));
345  if (!i())
346  return zero_none(home);
347  return ME_INT_NONE;
348  } else {
349  assert(i.val() == 1);
350  return one_none(home);
351  }
352  }
353  template<class I>
355  BoolVarImp::inter_v(Space& home, I& i, bool) {
356  while (i() && (i.val() < 0))
357  ++i;
358  if (!i() || (i.val() > 1))
359  return fail(home);
360  if (i.val() == 0) {
361  do {
362  ++i;
363  } while (i() && (i.val() == 0));
364  if (!i() || (i.val() > 1))
365  return zero(home);
366  return ME_INT_NONE;
367  } else {
368  assert(i.val() == 1);
369  return one(home);
370  }
371  }
372  template<class I>
374  BoolVarImp::minus_v(Space& home, I& i, bool) {
375  while (i() && (i.val() < 0))
376  ++i;
377  if (!i() || (i.val() > 1))
378  return ME_INT_NONE;
379  if (i.val() == 0) {
380  do {
381  ++i;
382  } while (i() && (i.val() == 0));
383  if (!i() || (i.val() > 1))
384  return one(home);
385  return fail(home);
386  } else {
387  assert(i.val() == 1);
388  return zero(home);
389  }
390  }
391 
392 
393 
394  /*
395  * Dependencies
396  *
397  */
398  forceinline void
401  }
402 
403  forceinline void
405  BoolVarImpBase::cancel(home,a,fail);
406  }
407 
408  forceinline void
410  if (me == ME_GEN_ASSIGNED)
411  BoolVarImpBase::schedule(home,p,me);
412  }
413 
416  return BoolVarImpBase::med(me);
417  }
418 
419 }}
420 
421 // STATISTICS: int-var
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: bool.hpp:318
BoolVarImp * copy(Space &home)
Return copy of this variable.
Definition: bool.hpp:262
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: bool.hpp:205
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4079
bool in(int n) const
Test whether n is contained in domain.
Definition: bool.hpp:121
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:488
static const BoolStatus NONE
Status of domain not yet assigned.
Definition: var-imp.hpp:529
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: bool.hpp:399
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition: bool.cpp:55
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:71
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:100
int ModEvent
Type for modification events.
Definition: core.hpp:64
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: bool.hpp:374
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: bool.hpp:169
Base-class for propagators.
Definition: core.hpp:1016
Base-class for advisors.
Definition: core.hpp:1218
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4123
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:95
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
bool zero(void) const
Test whether variable is assigned to zero.
Definition: bool.hpp:135
bool assigned(void) const
Test whether variable is assigned.
Definition: bool.hpp:89
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:4334
Boolean variable implementation.
Definition: var-imp.hpp:495
Gecode::IntSet d(v, 7)
int min(void) const
Return minimum of domain.
Definition: bool.hpp:66
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4117
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4073
int PropCond
Type for propagation conditions.
Definition: core.hpp:74
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:70
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: bool.hpp:109
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:355
BoolStatus status(void) const
Return current domain status.
Definition: bool.hpp:62
bool range(void) const
Test whether domain is a range.
Definition: bool.hpp:85
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
ModEvent one_none(Space &home)
Assign unassigned variable to one.
Definition: bool.cpp:46
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: bool.hpp:301
bool none(void) const
Test whether variable is not yet assigned.
Definition: bool.hpp:143
int val(void) const
Return assigned value (only if assigned)
Definition: bool.hpp:79
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:242
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4417
Post propagator for SetVar x
Definition: set.hh:769
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:218
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: bool.hpp:409
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: bool.hpp:336
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: bool.hpp:153
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4047
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:105
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: bool.hpp:74
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: bool.hpp:231
bool one(void) const
Test whether variable is assigned to one.
Definition: bool.hpp:139
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: bool.hpp:280
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