Generated on Fri Aug 24 2012 04:52:12 for Gecode by doxygen 1.8.1.2
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: 2010-07-29 01:35:33 +1000 (Thu, 29 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11294 $
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(double 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, double n) {
208  if (n <= 0) return ME_INT_NONE;
209  if (n > 1) return ME_INT_FAILED;
210  return one(home);
211  }
212 
213 
215  BoolVarImp::lq(Space& home, int n) {
216  if (n < 0) return ME_INT_FAILED;
217  if (n >= 1) return ME_INT_NONE;
218  return zero(home);
219  }
221  BoolVarImp::lq(Space& home, double n) {
222  if (n < 0) return ME_INT_FAILED;
223  if (n >= 1) return ME_INT_NONE;
224  return zero(home);
225  }
226 
227 
229  BoolVarImp::eq(Space& home, int n) {
230  if ((n < 0) || (n > 1)) return ME_INT_FAILED;
231  return (n == 0) ? zero(home): one(home);
232  }
234  BoolVarImp::eq(Space& home, double n) {
235  if ((n < 0) || (n > 1)) return ME_INT_FAILED;
236  return (n == 0) ? zero(home): one(home);
237  }
238 
239 
241  BoolVarImp::nq(Space& home, int n) {
242  if ((n < 0) || (n > 1)) return ME_INT_NONE;
243  return (n == 0) ? one(home): zero(home);
244  }
246  BoolVarImp::nq(Space& home, double n) {
247  if ((n < 0) || (n > 1)) return ME_INT_NONE;
248  return (n == 0) ? one(home): zero(home);
249  }
250 
251 
252  /*
253  * Copying a variable
254  *
255  */
256 
258  BoolVarImp::BoolVarImp(Space& home, bool share, BoolVarImp& x)
259  : BoolVarImpBase(home,share,x) {}
261  BoolVarImp::copy(Space& home, bool share) {
262  if (copied())
263  return static_cast<BoolVarImp*>(forward());
264  else if (zero())
265  return &s_zero;
266  else if (one())
267  return &s_one;
268  else
269  return new (home) BoolVarImp(home,share,*this);
270  }
271 
272 
273  /*
274  * Iterator-based domain operations
275  *
276  */
277  template<class I>
279  BoolVarImp::narrow_r(Space& home, I& i, bool) {
280  // Is new domain empty?
281  if (!i())
282  return ME_INT_FAILED;
283  assert((i.min() == 0) || (i.min() == 1));
284  assert((i.max() == 0) || (i.max() == 1));
285  if (i.max() == 0) {
286  assert(!one());
287  // Assign domain to be zero (domain cannot be one)
288  return zero(home);
289  }
290  if (i.min() == 1) {
291  // Assign domain to be one (domain cannot be zero)
292  assert(!zero());
293  return one(home);
294  }
295  assert(none());
296  return ME_INT_NONE;
297  }
298  template<class I>
300  BoolVarImp::inter_r(Space& home, I& i, bool) {
301  // Skip all ranges that are too small
302  while (i() && (i.max() < 0))
303  ++i;
304  // Is new domain empty?
305  if (!i() || (i.min() > 1))
306  return ME_INT_FAILED;
307  assert(i.min() <= 1);
308  if (i.min() == 1)
309  return one(home);
310  if (i.max() == 0)
311  return zero(home);
312  assert((i.min() <= 0) && (i.max() >= 1));
313  return ME_INT_NONE;
314  }
315  template<class I>
317  BoolVarImp::minus_r(Space& home, I& i, bool) {
318  // Skip all ranges that are too small
319  while (i() && (i.max() < 0))
320  ++i;
321  // Is new domain empty?
322  if (!i() || (i.min() > 1))
323  return ME_INT_NONE;
324  assert(i.min() <= 1);
325  if (i.min() == 1)
326  return zero(home);
327  if (i.max() == 0)
328  return one(home);
329  assert((i.min() <= 0) && (i.max() >= 1));
330  return ME_INT_FAILED;
331  }
332 
333  template<class I>
335  BoolVarImp::narrow_v(Space& home, I& i, bool) {
336  if (!i())
337  return ME_INT_FAILED;
338  if (!none())
339  return ME_INT_NONE;
340  if (i.val() == 0) {
341  do {
342  ++i;
343  } while (i() && (i.val() == 0));
344  if (!i())
345  return zero_none(home);
346  return ME_INT_NONE;
347  } else {
348  assert(i.val() == 1);
349  return one_none(home);
350  }
351  }
352  template<class I>
354  BoolVarImp::inter_v(Space& home, I& i, bool) {
355  while (i() && (i.val() < 0))
356  ++i;
357  if (!i() || (i.val() > 1))
358  return ME_INT_FAILED;
359  if (i.val() == 0) {
360  do {
361  ++i;
362  } while (i() && (i.val() == 0));
363  if (!i() || (i.val() > 1))
364  return zero(home);
365  return ME_INT_NONE;
366  } else {
367  assert(i.val() == 1);
368  return one(home);
369  }
370  }
371  template<class I>
373  BoolVarImp::minus_v(Space& home, I& i, bool) {
374  while (i() && (i.val() < 0))
375  ++i;
376  if (!i() || (i.val() > 1))
377  return ME_INT_NONE;
378  if (i.val() == 0) {
379  do {
380  ++i;
381  } while (i() && (i.val() == 0));
382  if (!i() || (i.val() > 1))
383  return one(home);
384  return ME_INT_FAILED;
385  } else {
386  assert(i.val() == 1);
387  return zero(home);
388  }
389  }
390 
391 
392 
393  /*
394  * Dependencies
395  *
396  */
397  forceinline void
399  bool schedule) {
400  // Subscription can be used with integer propagation conditions,
401  // which must be remapped to the single Boolean propagation condition.
403  }
404  forceinline void
407  }
408 
409  forceinline void
412  }
413  forceinline void
416  }
417 
418  forceinline void
420  if (me == ME_GEN_ASSIGNED)
421  BoolVarImpBase::schedule(home,p,me);
422  }
423 
426  return BoolVarImpBase::med(me);
427  }
428 
429 }}
430 
431 // STATISTICS: int-var