Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.9.1
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: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13292 $
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 ME_INT_FAILED;
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 ME_INT_FAILED;
210  return one(home);
211  }
212 
214  BoolVarImp::lq(Space& home, int n) {
215  if (n < 0) return ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
328  }
329 
330  template<class I>
332  BoolVarImp::narrow_v(Space& home, I& i, bool) {
333  if (!i())
334  return ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
382  } else {
383  assert(i.val() == 1);
384  return zero(home);
385  }
386  }
387 
388 
389 
390  /*
391  * Dependencies
392  *
393  */
394  forceinline void
396  bool schedule) {
397  // Subscription can be used with integer propagation conditions,
398  // which must be remapped to the single Boolean propagation condition.
400  }
401  forceinline void
404  }
405 
406  forceinline void
409  }
410  forceinline void
413  }
414 
415  forceinline void
417  if (me == ME_GEN_ASSIGNED)
418  BoolVarImpBase::schedule(home,p,me);
419  }
420 
423  return BoolVarImpBase::med(me);
424  }
425 
426 }}
427 
428 // 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
bool assigned(void) const
Test whether variable is assigned.
Definition: bool.hpp:89
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: bool.hpp:201
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: bool.hpp:95
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: bool.hpp:109
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: bool.hpp:105
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: bool.hpp:74
unsigned int BoolStatus
Type for status of a Boolean variable.
Definition: var-imp.hpp:479
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
static const BoolStatus NONE
Status of domain not yet assigned.
Definition: var-imp.hpp:520
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: bool.hpp:402
ModEvent zero_none(Space &home)
Assign unassigned variable to zero.
Definition: bool.cpp:55
int min(void) const
Return minimum of domain.
Definition: bool.hpp:66
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:153
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
bool zero(void) const
Test whether variable is assigned to zero.
Definition: bool.hpp:135
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:755
bool range(void) const
Test whether domain is a range.
Definition: bool.hpp:85
Base-class for advisors.
Definition: core.hpp:926
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Computation spaces.
Definition: core.hpp:1362
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Boolean variable implementation.
Definition: var-imp.hpp:486
Gecode::IntSet d(v, 7)
bool one(void) const
Test whether variable is assigned to one.
Definition: bool.hpp:139
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
BoolStatus status(void) const
Return current domain status.
Definition: bool.hpp:62
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool copied(void) const
Is variable already copied.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
bool none(void) const
Test whether variable is not yet assigned.
Definition: bool.hpp:143
const Gecode::ModEvent ME_BOOL_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:114
void subscribe(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: var-imp.hpp:251
bool in(int n) const
Test whether n is contained in domain.
Definition: bool.hpp:121
BoolVarImp * copy(Space &home, bool share)
Return copy of this variable.
Definition: bool.hpp:258
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p to variable with propagation condition pc.
Definition: bool.hpp:395
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
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:351
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
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
#define forceinline
Definition: config.hpp:132
int val(void) const
Return assigned value (only if assigned)
Definition: bool.hpp:79
Base-class for Bool-variable implementations.
Definition: var-imp.hpp:82
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:100
const Gecode::ModEvent ME_BOOL_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:112
unsigned int bits(void) const
Provide access to free bits.
Gecode toplevel namespace
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: bool.hpp:214
int max(void) const
Return maximum of domain.
Definition: bool.hpp:70
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: bool.hpp:416
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:173
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
VarImp * forward(void) const
Use forward pointer if variable already copied.
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: bool.hpp:227
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