main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:39 for Gecode by
doxygen
1.8.3.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: 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
*/
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
(
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
*/
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,
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
213
forceinline
ModEvent
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
}
219
forceinline
ModEvent
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
226
forceinline
ModEvent
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
}
231
forceinline
ModEvent
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
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,
bool
share,
BoolVarImp
&
x
)
256
:
BoolVarImpBase
(home,share,x) {}
257
forceinline
BoolVarImp
*
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>
275
forceinline
ModEvent
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>
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
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>
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
ME_INT_FAILED
;
328
}
329
330
template
<
class
I>
331
forceinline
ModEvent
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>
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
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>
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
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
395
BoolVarImp::subscribe
(
Space
& home,
Propagator
&
p
,
PropCond
,
396
bool
schedule) {
397
// Subscription can be used with integer propagation conditions,
398
// which must be remapped to the single Boolean propagation condition.
399
BoolVarImpBase::subscribe
(home,p,
PC_BOOL_VAL
,
assigned
(),schedule);
400
}
401
forceinline
void
402
BoolVarImp::cancel
(
Space
& home,
Propagator
&
p
,
PropCond
) {
403
BoolVarImpBase::cancel
(home,p,
PC_BOOL_VAL
,
assigned
());
404
}
405
406
forceinline
void
407
BoolVarImp::subscribe
(
Space
& home,
Advisor
&
a
) {
408
BoolVarImpBase::subscribe
(home,a,
assigned
());
409
}
410
forceinline
void
411
BoolVarImp::cancel
(
Space
& home,
Advisor
&
a
) {
412
BoolVarImpBase::cancel
(home,a,
assigned
());
413
}
414
415
forceinline
void
416
BoolVarImp::schedule
(
Space
& home,
Propagator
&
p
,
ModEvent
me) {
417
if
(me ==
ME_GEN_ASSIGNED
)
418
BoolVarImpBase::schedule
(home,p,me);
419
}
420
421
forceinline
ModEventDelta
422
BoolVarImp::med
(
ModEvent
me) {
423
return
BoolVarImpBase::med
(me);
424
}
425
426
}}
427
428
// STATISTICS: int-var