main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:19 for Gecode by
doxygen
1.8.1.1
gecode
int
var-imp
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
*/
44
forceinline
45
BoolVarImp::BoolVarImp(
int
n) {
46
assert(
bits
() == 0);
47
bits
() |= (n << 1) | n;
48
}
49
forceinline
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
*/
61
forceinline
BoolStatus
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
105
BoolVarImp::regret_min
(
void
)
const
{
106
return
assigned
() ? 1U : 0U;
107
}
108
forceinline
unsigned
int
109
BoolVarImp::regret_max
(
void
)
const
{
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
*/
152
forceinline
ModEvent
153
BoolVarImp::modevent
(
const
Delta
&) {
154
return
ME_BOOL_VAL
;
155
}
156
forceinline
int
157
BoolVarImp::min
(
const
Delta
&
d
) {
158
return
static_cast<
const
IntDelta
&
>
(
d
).
min
();
159
}
160
forceinline
int
161
BoolVarImp::max
(
const
Delta
&
d
) {
162
return
static_cast<
const
IntDelta
&
>
(
d
).
min
();
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
ME_INT_FAILED
;
204
return
one
(home);
205
}
206
forceinline
ModEvent
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
214
forceinline
ModEvent
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
}
220
forceinline
ModEvent
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
228
forceinline
ModEvent
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
}
233
forceinline
ModEvent
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
240
forceinline
ModEvent
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
}
245
forceinline
ModEvent
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
257
forceinline
258
BoolVarImp::BoolVarImp(
Space
& home,
bool
share,
BoolVarImp
& x)
259
:
BoolVarImpBase
(home,share,x) {}
260
forceinline
BoolVarImp
*
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>
278
forceinline
ModEvent
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>
299
forceinline
ModEvent
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>
316
forceinline
ModEvent
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>
334
forceinline
ModEvent
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>
353
forceinline
ModEvent
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>
372
forceinline
ModEvent
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
398
BoolVarImp::subscribe
(
Space
& home,
Propagator
& p,
PropCond
,
399
bool
schedule) {
400
// Subscription can be used with integer propagation conditions,
401
// which must be remapped to the single Boolean propagation condition.
402
BoolVarImpBase::subscribe
(home,p,
PC_BOOL_VAL
,
assigned
(),schedule);
403
}
404
forceinline
void
405
BoolVarImp::cancel
(
Space
& home,
Propagator
& p,
PropCond
) {
406
BoolVarImpBase::cancel
(home,p,
PC_BOOL_VAL
,
assigned
());
407
}
408
409
forceinline
void
410
BoolVarImp::subscribe
(
Space
& home,
Advisor
&
a
) {
411
BoolVarImpBase::subscribe
(home,a,
assigned
());
412
}
413
forceinline
void
414
BoolVarImp::cancel
(
Space
& home,
Advisor
&
a
) {
415
BoolVarImpBase::cancel
(home,a,
assigned
());
416
}
417
418
forceinline
void
419
BoolVarImp::schedule
(
Space
& home,
Propagator
& p,
ModEvent
me) {
420
if
(me ==
ME_GEN_ASSIGNED
)
421
BoolVarImpBase::schedule
(home,p,me);
422
}
423
424
forceinline
ModEventDelta
425
BoolVarImp::med
(
ModEvent
me) {
426
return
BoolVarImpBase::med
(me);
427
}
428
429
}}
430
431
// STATISTICS: int-var