main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:15 for Gecode by
doxygen
1.8.1.1
gecode
int
bool
lq.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: 2011-06-20 19:16:03 +1000 (Mon, 20 Jun 2011) $ by $Author: schulte $
11
* $Revision: 12058 $
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 {
namespace
Bool {
39
40
/*
41
* Less or equal propagator
42
*
43
*/
44
45
template
<
class
BV>
46
forceinline
47
Lq<BV>::Lq
(
Home
home, BV b0, BV
b1
)
48
:
BoolBinary
<BV,BV>(home,b0,b1) {}
49
50
template
<
class
BV>
51
forceinline
52
Lq<BV>::Lq
(
Space
& home,
bool
share,
Lq<BV>
& p)
53
:
BoolBinary
<BV,BV>(home,share,p) {}
54
55
template
<
class
BV>
56
Actor
*
57
Lq<BV>::copy
(
Space
& home,
bool
share) {
58
return
new
(home)
Lq<BV>
(home,share,*
this
);
59
}
60
61
template
<
class
BV>
62
inline
ExecStatus
63
Lq<BV>::post
(
Home
home, BV b0, BV
b1
) {
64
if
(b0.zero()) {
65
return
ES_OK
;
66
}
else
if
(b0.one()) {
67
GECODE_ME_CHECK
(b1.one(home));
68
}
else
if
(b1.zero()) {
69
GECODE_ME_CHECK
(b0.zero(home));
70
}
else
if
(b1.one()) {
71
return
ES_OK
;
72
}
else
{
73
(void)
new
(home)
Lq<BV>
(home,b0,
b1
);
74
}
75
return
ES_OK
;
76
}
77
78
template
<
class
BV>
79
ExecStatus
80
Lq<BV>::propagate
(
Space
& home,
const
ModEventDelta
&) {
81
#define GECODE_INT_STATUS(S0,S1) \
82
((BV::S0<<(1*BV::BITS))|(BV::S1<<(0*BV::BITS)))
83
switch
((x0.status()<<(1*BV::BITS)) | (x1.status()<<(0*BV::BITS))) {
84
case
GECODE_INT_STATUS
(NONE,NONE):
85
GECODE_NEVER
;
86
case
GECODE_INT_STATUS
(NONE,ZERO):
87
GECODE_ME_CHECK
(x0.zero_none(home));
break
;
88
case
GECODE_INT_STATUS
(NONE,ONE):
89
case
GECODE_INT_STATUS
(ZERO,NONE):
90
case
GECODE_INT_STATUS
(ZERO,ZERO):
91
case
GECODE_INT_STATUS
(ZERO,ONE):
92
break
;
93
case
GECODE_INT_STATUS
(ONE,NONE):
94
GECODE_ME_CHECK
(x1.one_none(home));
break
;
95
case
GECODE_INT_STATUS
(ONE,ZERO):
96
return
ES_FAILED
;
97
case
GECODE_INT_STATUS
(ONE,ONE):
98
break
;
99
default
:
100
GECODE_NEVER
;
101
}
102
return
home.
ES_SUBSUMED
(*
this
);
103
#undef GECODE_INT_STATUS
104
}
105
106
107
/*
108
* N-ary Boolean less or equal propagator
109
*
110
*/
111
112
template
<
class
VX>
113
forceinline
114
NaryLq<VX>::NaryLq
(
Home
home,
ViewArray<VX>
& x)
115
:
NaryPropagator
<VX,
PC_BOOL_NONE
>(home,x),
116
run(false), n_zero(0), n_one(0),
c
(home) {
117
x.
subscribe
(home,*
new
(home)
Advisor
(home,*
this
,
c
));
118
}
119
120
template
<
class
VX>
121
forceinline
122
NaryLq<VX>::NaryLq
(
Space
& home,
bool
share,
NaryLq<VX>
& p)
123
:
NaryPropagator
<VX,
PC_BOOL_NONE
>(home,share,p),
124
run(false), n_zero(0), n_one(0) {
125
c
.
update
(home,share,p.
c
);
126
}
127
128
template
<
class
VX>
129
Actor
*
130
NaryLq<VX>::copy
(
Space
& home,
bool
share) {
131
return
new
(home)
NaryLq<VX>
(home,share,*
this
);
132
}
133
134
template
<
class
VX>
135
inline
ExecStatus
136
NaryLq<VX>::post
(
Home
home,
ViewArray<VX>
& x) {
137
int
i
= 0;
138
while
(i < x.
size
())
139
if
(x[i].zero()) {
140
// All x[j] left of i must be zero as well
141
for
(
int
j=i; j--; )
142
GECODE_ME_CHECK
(x[j].zero_none(home));
143
x.
drop_fst
(i+1); i=0;
144
}
else
if
(x[i].
one
()) {
145
// All x[j] right of i must be one as well
146
for
(
int
j=i+1; j<x.
size
(); j++)
147
GECODE_ME_CHECK
(x[j].
one
(home));
148
x.
drop_lst
(i-1);
break
;
149
}
else
{
150
i++;
151
}
152
153
if
(x.
size
() == 2)
154
return
Lq<VX>::post
(home,x[0],x[1]);
155
if
(x.
size
() > 2)
156
(
void
)
new
(home)
NaryLq
(home,x);
157
return
ES_OK
;
158
}
159
160
template
<
class
VX>
161
PropCost
162
NaryLq<VX>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
163
return
PropCost::binary
(
PropCost::LO
);
164
}
165
166
template
<
class
VX>
167
ExecStatus
168
NaryLq<VX>::advise
(
Space
&,
Advisor
&,
const
Delta
&
d
) {
169
if
(VX::zero(d))
170
n_zero++;
171
else
172
n_one++;
173
return
run ?
ES_FIX
:
ES_NOFIX
;
174
}
175
176
template
<
class
VX>
177
forceinline
size_t
178
NaryLq<VX>::dispose
(
Space
& home) {
179
Advisors<Advisor>
as(
c
);
180
x.cancel(home,as.
advisor
());
181
c
.dispose(home);
182
(void)
NaryPropagator<VX,PC_BOOL_NONE>::dispose
(home);
183
return
sizeof
(*this);
184
}
185
186
template
<
class
VX>
187
ExecStatus
188
NaryLq<VX>::propagate
(
Space
& home,
const
ModEventDelta
&) {
189
run =
true
;
190
while
(n_zero > 0) {
191
int
i
= 0;
192
while
(x[i].none())
193
i++;
194
if
(x[i].
one
())
195
return
ES_FAILED
;
196
// As the x[j] might be shared, only zero() but not zero_none()
197
for
(
int
j=i; j--; )
198
GECODE_ME_CHECK
(x[j].zero(home));
199
n_zero -= i + 1;
200
assert(n_zero >= 0);
201
x.drop_fst(i+1);
202
}
203
204
while
(n_one > 0) {
205
int
i
= x.
size
() - 1;
206
while
(x[i].none())
207
i--;
208
assert(x[i].
one
());
209
// As the x[j] might be shared, only one() but not one_none()
210
for
(
int
j=i+1; j<x.size(); j++)
211
GECODE_ME_CHECK
(x[j].
one
(home));
212
n_one -= x.size() -
i
;
213
assert(n_one >= 0);
214
x.drop_lst(i-1);
215
}
216
217
if
(x.size() < 2)
218
return
home.
ES_SUBSUMED
(*
this
);
219
220
run =
false
;
221
return
ES_FIX
;
222
}
223
224
225
/*
226
* Less posting
227
*
228
*/
229
230
template
<
class
BV>
231
forceinline
ExecStatus
232
Le<BV>::post
(
Home
home, BV b0, BV
b1
) {
233
GECODE_ME_CHECK
(b0.zero(home));
234
GECODE_ME_CHECK
(b1.one(home));
235
return
ES_OK
;
236
}
237
238
}}}
239
240
// STATISTICS: int-prop
241