this repo has no description
dekker.one
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
34namespace Gecode { namespace Int {
35
36 /*
37 * Creation of new variable implementations
38 *
39 */
40 forceinline
41 BoolVarImp::BoolVarImp(int n) {
42 assert(bits() == 0);
43 bits() |= (n << 1) | n;
44 }
45 forceinline
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 */
57 forceinline BoolStatus
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
101 BoolVarImp::regret_min(void) const {
102 return assigned() ? 1U : 0U;
103 }
104 forceinline unsigned int
105 BoolVarImp::regret_max(void) const {
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 */
148 forceinline ModEvent
149 BoolVarImp::modevent(const Delta&) {
150 return ME_BOOL_VAL;
151 }
152 forceinline int
153 BoolVarImp::min(const Delta& d) {
154 return static_cast<const IntDelta&>(d).min();
155 }
156 forceinline int
157 BoolVarImp::max(const Delta& d) {
158 return static_cast<const IntDelta&>(d).min();
159 }
160 forceinline unsigned int
161 BoolVarImp::width(const Delta& d) {
162 return static_cast<const IntDelta&>(d).width();
163 }
164 forceinline bool
165 BoolVarImp::any(const Delta&) {
166 return false;
167 }
168 forceinline bool
169 BoolVarImp::zero(const Delta& d) {
170 return static_cast<const IntDelta&>(d).min() != 0;
171 }
172 forceinline bool
173 BoolVarImp::one(const Delta& d) {
174 return static_cast<const IntDelta&>(d).min() == 0;
175 }
176
177
178 /*
179 * Boolean tell operations
180 *
181 */
182 forceinline ModEvent
183 BoolVarImp::zero(Space& home) {
184 if (one()) return ME_BOOL_FAILED;
185 if (zero()) return ME_BOOL_NONE;
186 return zero_none(home);
187 }
188 forceinline ModEvent
189 BoolVarImp::one(Space& home) {
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 */
200 forceinline ModEvent
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 }
206 forceinline ModEvent
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
213 forceinline ModEvent
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 }
219 forceinline ModEvent
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
226 forceinline ModEvent
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 }
231 forceinline ModEvent
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
237 forceinline ModEvent
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 }
242 forceinline ModEvent
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
254 forceinline
255 BoolVarImp::BoolVarImp(Space& home, BoolVarImp& x)
256 : BoolVarImpBase(home,x) {}
257 forceinline BoolVarImp*
258 BoolVarImp::copy(Space& home) {
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>
275 forceinline ModEvent
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>
296 forceinline ModEvent
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>
313 forceinline ModEvent
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>
331 forceinline ModEvent
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>
350 forceinline ModEvent
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>
369 forceinline ModEvent
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
395 BoolVarImp::cancel(Space& home, Propagator& p, PropCond) {
396 BoolVarImpBase::cancel(home,p,PC_BOOL_VAL);
397 }
398
399 forceinline void
400 BoolVarImp::cancel(Space& home, Advisor& a, bool fail) {
401 BoolVarImpBase::cancel(home,a,fail);
402 }
403
404 forceinline void
405 BoolVarImp::schedule(Space& home, Propagator& p, ModEvent) {
406 BoolVarImpBase::schedule(home,p,ME_BOOL_VAL);
407 }
408
409 forceinline ModEventDelta
410 BoolVarImp::med(ModEvent me) {
411 return BoolVarImpBase::med(me);
412 }
413
414}}
415
416// STATISTICS: int-var