Generated on Thu Jul 25 2019 00:00:00 for Gecode by doxygen 1.8.15
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: 2017-03-09 09:51:58 +0100 (Thu, 09 Mar 2017) $ by $Author: schulte $
11  * $Revision: 15565 $
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 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, bool share, BoolVarImp& x)
256  : BoolVarImpBase(home,share,x) {}
258  BoolVarImp::copy(Space& home, bool share) {
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,share,*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
400  BoolVarImp::cancel(Space& home, Advisor& a, bool fail) {
402  }
403 
404  forceinline void
406  if (me == ME_GEN_ASSIGNED)
408  }
409 
412  return BoolVarImpBase::med(me);
413  }
414 
415 }}
416 
417 // 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
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:4277
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:484
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
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:55
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:100
int ModEvent
Type for modification events.
Definition: core.hpp:142
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:1092
Base-class for advisors.
Definition: core.hpp:1294
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4321
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:95
Computation spaces.
Definition: core.hpp:1748
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:4532
Boolean variable implementation.
Definition: var-imp.hpp:491
Gecode::IntSet d(v, 7)
int min(void) const
Return minimum of domain.
Definition: bool.hpp:66
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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:4315
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4271
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
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
BoolVarImp * copy(Space &home, bool share)
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:109
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
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: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:281
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:297
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
#define forceinline
Definition: config.hpp:173
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:4615
Post propagator for SetVar x
Definition: set.hh:784
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:153
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:4245
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:227
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: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