main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 13 2014 04:39:32 for Gecode by
doxygen
1.8.1.2
gecode
int
linear
bool-view.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, 2004
8
*
9
* Last modified:
10
* $Date: 2010-03-04 03:32:21 +1100 (Thu, 04 Mar 2010) $ by $Author: schulte $
11
* $Revision: 10364 $
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
Linear {
39
40
/*
41
* Base-class
42
*
43
*/
44
template
<
class
XV,
class
YV>
45
LinBoolView<XV,YV>::LinBoolView
(
Home
home,
46
ViewArray<XV>
& x0, YV y0,
int
c0)
47
:
Propagator
(home), x(x0), y(y0),
c
(c0) {
48
x
.
subscribe
(home,*
this
,
PC_INT_VAL
);
49
y
.subscribe(home,*
this
,
PC_INT_BND
);
50
}
51
52
template
<
class
XV,
class
YV>
53
forceinline
size_t
54
LinBoolView<XV,YV>::dispose
(
Space
& home) {
55
x.cancel(home,*
this
,
PC_INT_VAL
);
56
y.cancel(home,*
this
,
PC_INT_BND
);
57
(void)
Propagator::dispose
(home);
58
return
sizeof
(*this);
59
}
60
61
template
<
class
XV,
class
YV>
62
forceinline
63
LinBoolView<XV,YV>::LinBoolView
(
Space
& home,
bool
share,
LinBoolView
& p)
64
:
Propagator
(home,share,p),
c
(p.
c
) {
65
x
.
update
(home,share,p.
x
);
66
y
.update(home,share,p.
y
);
67
}
68
69
template
<
class
XV,
class
YV>
70
PropCost
71
LinBoolView<XV,YV>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
72
return
PropCost::linear
(
PropCost::LO
, x.size());
73
}
74
75
76
/*
77
* Equality propagator
78
*
79
*/
80
template
<
class
XV,
class
YV>
81
forceinline
82
EqBoolView<XV,YV>::EqBoolView
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
)
83
:
LinBoolView
<XV,YV>(home,x,y,c) {}
84
85
template
<
class
XV,
class
YV>
86
ExecStatus
87
EqBoolView<XV,YV>::post
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
) {
88
if
(y.assigned())
89
return
EqBoolInt<XV>::post
(home,x,y.val()+
c
);
90
int
n = x.
size
();
91
for
(
int
i
= n;
i
--; )
92
if
(x[
i
].
one
()) {
93
x[
i
]=x[--n]; c--;
94
}
else
if
(x[
i
].zero()) {
95
x[
i
]=x[--n];
96
}
97
x.
size
(n);
98
GECODE_ME_CHECK
(y.lq(home,n-c));
99
GECODE_ME_CHECK
(y.gq(home,-c));
100
if
(n == 0)
101
return
ES_OK
;
102
if
(y.min()+c == n) {
103
assert(y.assigned());
104
for
(
int
i
= n;
i
--; )
105
GECODE_ME_CHECK
(x[
i
].one_none(home));
106
return
ES_OK
;
107
}
108
if
(y.max()+c == 0) {
109
assert(y.assigned());
110
for
(
int
i
= n;
i
--; )
111
GECODE_ME_CHECK
(x[
i
].zero_none(home));
112
return
ES_OK
;
113
}
114
(void)
new
(home)
EqBoolView<XV,YV>
(home,x,y,
c
);
115
return
ES_OK
;
116
}
117
118
template
<
class
XV,
class
YV>
119
forceinline
120
EqBoolView<XV,YV>::EqBoolView
(
Space
& home,
bool
share,
EqBoolView<XV,YV>
& p)
121
:
LinBoolView
<XV,YV>(home,share,p) {}
122
123
template
<
class
XV,
class
YV>
124
Actor
*
125
EqBoolView<XV,YV>::copy
(
Space
& home,
bool
share) {
126
return
new
(home)
EqBoolView<XV,YV>
(home,share,*
this
);
127
}
128
129
template
<
class
XV,
class
YV>
130
ExecStatus
131
EqBoolView<XV,YV>::propagate
(
Space
& home,
const
ModEventDelta
&) {
132
int
n = x.size();
133
for
(
int
i
= n;
i
--; )
134
if
(x[
i
].
one
()) {
135
x[
i
]=x[--n];
c
--;
136
}
else
if
(x[
i
].zero()) {
137
x[
i
]=x[--n];
138
}
139
x.
size
(n);
140
GECODE_ME_CHECK
(y.lq(home,n-
c
));
141
GECODE_ME_CHECK
(y.gq(home,-
c
));
142
if
(n == 0)
143
return
home.
ES_SUBSUMED
(*
this
);
144
if
(y.min()+
c
== n) {
145
assert(y.assigned());
146
for
(
int
i
= n;
i
--; )
147
GECODE_ME_CHECK
(x[
i
].one_none(home));
148
return
home.
ES_SUBSUMED
(*
this
);
149
}
150
if
(y.max()+
c
== 0) {
151
assert(y.assigned());
152
for
(
int
i
= n;
i
--; )
153
GECODE_ME_CHECK
(x[
i
].zero_none(home));
154
return
home.
ES_SUBSUMED
(*
this
);
155
}
156
if
(y.assigned())
157
GECODE_REWRITE
(*
this
,
EqBoolInt<XV>::post
(home(*
this
),x,y.val()+
c
));
158
return
ES_FIX
;
159
}
160
161
162
/*
163
* Disequality propagator
164
*
165
*/
166
template
<
class
XV,
class
YV>
167
forceinline
168
NqBoolView<XV,YV>::NqBoolView
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
)
169
:
LinBoolView
<XV,YV>(home,x,y,c) {}
170
171
template
<
class
XV,
class
YV>
172
ExecStatus
173
NqBoolView<XV,YV>::post
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
) {
174
if
(y.assigned())
175
return
NqBoolInt<XV>::post
(home,x,y.val()+
c
);
176
int
n = x.
size
();
177
for
(
int
i
= n;
i
--; )
178
if
(x[
i
].
one
()) {
179
x[
i
]=x[--n]; c--;
180
}
else
if
(x[
i
].zero()) {
181
x[
i
]=x[--n];
182
}
183
x.
size
(n);
184
if
((n-c < y.min() ) || (-c > y.max()))
185
return
ES_OK
;
186
if
(n == 0) {
187
GECODE_ME_CHECK
(y.nq(home,-c));
188
return
ES_OK
;
189
}
190
if
((n == 1) && y.assigned()) {
191
if
(y.val()+c == 1) {
192
GECODE_ME_CHECK
(x[0].zero_none(home));
193
}
else
{
194
assert(y.val()+c == 0);
195
GECODE_ME_CHECK
(x[0].one_none(home));
196
}
197
return
ES_OK
;
198
}
199
(void)
new
(home)
NqBoolView<XV,YV>
(home,x,y,
c
);
200
return
ES_OK
;
201
}
202
203
204
template
<
class
XV,
class
YV>
205
forceinline
206
NqBoolView<XV,YV>::NqBoolView
(
Space
& home,
bool
share,
NqBoolView<XV,YV>
& p)
207
:
LinBoolView
<XV,YV>(home,share,p) {}
208
209
template
<
class
XV,
class
YV>
210
Actor
*
211
NqBoolView<XV,YV>::copy
(
Space
& home,
bool
share) {
212
return
new
(home)
NqBoolView<XV,YV>
(home,share,*
this
);
213
}
214
215
template
<
class
XV,
class
YV>
216
ExecStatus
217
NqBoolView<XV,YV>::propagate
(
Space
& home,
const
ModEventDelta
&) {
218
int
n = x.size();
219
for
(
int
i
= n;
i
--; )
220
if
(x[
i
].
one
()) {
221
x[
i
]=x[--n];
c
--;
222
}
else
if
(x[
i
].zero()) {
223
x[
i
]=x[--n];
224
}
225
x.
size
(n);
226
if
((n-
c
< y.
min
() ) || (-
c
> y.
max
()))
227
return
home.
ES_SUBSUMED
(*
this
);
228
if
(n == 0) {
229
GECODE_ME_CHECK
(y.nq(home,-
c
));
230
return
home.
ES_SUBSUMED
(*
this
);
231
}
232
if
((n == 1) && y.assigned()) {
233
if
(y.val()+
c
== 1) {
234
GECODE_ME_CHECK
(x[0].zero_none(home));
235
}
else
{
236
assert(y.val()+
c
== 0);
237
GECODE_ME_CHECK
(x[0].one_none(home));
238
}
239
return
home.
ES_SUBSUMED
(*
this
);
240
}
241
return
ES_FIX
;
242
}
243
244
245
/*
246
* Greater or equal propagator
247
*
248
*/
249
template
<
class
XV,
class
YV>
250
forceinline
251
GqBoolView<XV,YV>::GqBoolView
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
)
252
:
LinBoolView
<XV,YV>(home,x,y,c) {}
253
254
template
<
class
XV,
class
YV>
255
ExecStatus
256
GqBoolView<XV,YV>::post
(
Home
home,
ViewArray<XV>
& x, YV y,
int
c
) {
257
if
(y.assigned())
258
return
GqBoolInt<XV>::post
(home,x,y.val()+
c
);
259
// Eliminate assigned views
260
int
n = x.
size
();
261
for
(
int
i
= n;
i
--; )
262
if
(x[
i
].
one
()) {
263
x[
i
]=x[--n]; c--;
264
}
else
if
(x[
i
].zero()) {
265
x[
i
]=x[--n];
266
}
267
x.
size
(n);
268
GECODE_ME_CHECK
(y.lq(home,n-c));
269
if
(-c >= y.max())
270
return
ES_OK
;
271
if
(y.min()+c == n) {
272
for
(
int
i
= n;
i
--; )
273
GECODE_ME_CHECK
(x[
i
].one_none(home));
274
return
ES_OK
;
275
}
276
(void)
new
(home)
GqBoolView<XV,YV>
(home,x,y,
c
);
277
return
ES_OK
;
278
}
279
280
281
template
<
class
XV,
class
YV>
282
forceinline
283
GqBoolView<XV,YV>::GqBoolView
(
Space
& home,
bool
share,
GqBoolView<XV,YV>
& p)
284
:
LinBoolView
<XV,YV>(home,share,p) {}
285
286
template
<
class
XV,
class
YV>
287
Actor
*
288
GqBoolView<XV,YV>::copy
(
Space
& home,
bool
share) {
289
return
new
(home)
GqBoolView<XV,YV>
(home,share,*
this
);
290
}
291
292
template
<
class
XV,
class
YV>
293
ExecStatus
294
GqBoolView<XV,YV>::propagate
(
Space
& home,
const
ModEventDelta
&) {
295
int
n = x.size();
296
for
(
int
i
= n;
i
--; )
297
if
(x[
i
].
one
()) {
298
x[
i
]=x[--n];
c
--;
299
}
else
if
(x[
i
].zero()) {
300
x[
i
]=x[--n];
301
}
302
x.
size
(n);
303
GECODE_ME_CHECK
(y.lq(home,n-
c
));
304
if
(-
c
>= y.
max
())
305
return
home.
ES_SUBSUMED
(*
this
);
306
if
(y.min()+
c
== n) {
307
for
(
int
i
= n;
i
--; )
308
GECODE_ME_CHECK
(x[
i
].one_none(home));
309
return
home.
ES_SUBSUMED
(*
this
);
310
}
311
if
(y.assigned())
312
GECODE_REWRITE
(*
this
,
GqBoolInt<XV>::post
(home(*
this
),x,y.val()+
c
));
313
return
ES_FIX
;
314
}
315
316
}}}
317
318
// STATISTICS: int-prop
319