main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:08 for Gecode by
doxygen
1.8.1.2
gecode
int
channel
link-multi.cpp
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, 2007
8
*
9
* Last modified:
10
* $Date: 2011-07-07 19:23:22 +1000 (Thu, 07 Jul 2011) $ by $Author: schulte $
11
* $Revision: 12155 $
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
#include <
gecode/int/channel.hh
>
39
40
namespace
Gecode {
namespace
Int {
namespace
Channel {
41
43
class
BoolIter
{
44
private
:
46
const
ViewArray<BoolView>
& x;
48
const
int
o;
50
int
i;
51
public
:
53
BoolIter
(
const
ViewArray<BoolView>
& x0,
int
o0);
55
bool
operator ()
(
void
)
const
;
57
int
val
(
void
)
const
;
59
void
operator ++
(
void
);
60
};
61
62
forceinline
63
BoolIter::BoolIter
(
const
ViewArray<BoolView>
& x0,
int
o0) :
64
x(x0), o(o0),
i
(0) {
65
while
((i<x.
size
()) && !x[i].zero())
66
i++;
67
}
68
forceinline
bool
69
BoolIter::operator ()
(
void
)
const
{
70
return
i<x.
size
();
71
}
72
forceinline
int
73
BoolIter::val
(
void
)
const
{
74
assert(x[i].zero());
75
return
i+o;
76
}
77
forceinline
void
78
BoolIter::operator ++
(
void
) {
79
do
{
80
i++;
81
}
while
((i<x.
size
()) && !x[i].zero());
82
}
83
84
85
forceinline
86
LinkMulti::LinkMulti(
Space
& home,
bool
share,
LinkMulti
& p)
87
:
MixNaryOnePropagator
<
BoolView
,
PC_BOOL_NONE
,
IntView
,
PC_INT_DOM
>
88
(home,share,p), status(S_NONE), o(p.o) {
89
assert(p.status == S_NONE);
90
c
.
update
(home,share,p.c);
91
}
92
93
Actor
*
94
LinkMulti::copy
(
Space
& home,
bool
share) {
95
return
new
(home)
LinkMulti
(home,share,*
this
);
96
}
97
98
forceinline
size_t
99
LinkMulti::dispose
(
Space
& home) {
100
Advisors<Advisor>
as(c);
101
x
.
cancel
(home,as.
advisor
());
102
c.
dispose
(home);
103
(void)
MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>
104
::
dispose
(home);
105
return
sizeof
(*this);
106
}
107
108
PropCost
109
LinkMulti::cost
(
const
Space
&,
const
ModEventDelta
& med)
const
{
110
if
((status == S_ONE) || (
IntView::me
(med) ==
ME_INT_VAL
))
111
return
PropCost::unary
(
PropCost::LO
);
112
else
113
return
PropCost::linear
(
PropCost::LO
,
x
.
size
());
114
}
115
116
ExecStatus
117
LinkMulti::advise
(
Space
&,
Advisor
&,
const
Delta
&
d
) {
118
if
(status == S_RUN)
119
return
ES_FIX
;
120
// Detect a one
121
if
(
BoolView::one
(d))
122
status = S_ONE;
123
return
ES_NOFIX
;
124
}
125
126
ExecStatus
127
LinkMulti::propagate
(
Space
& home,
const
ModEventDelta
& med) {
128
int
n =
x
.
size
();
129
130
// Always maintain the invariant that y lies inside the x-array
131
assert((
y
.
min
()-o >= 0) && (
y
.
max
()-o < n));
132
133
if
(
y
.
assigned
()) {
134
status = S_RUN;
135
int
j=
y
.
val
()-o;
136
GECODE_ME_CHECK
(
x
[j].
one
(home));
137
for
(
int
i
=0;
i
<j;
i
++)
138
GECODE_ME_CHECK
(
x
[
i
].zero(home));
139
for
(
int
i
=j+1;
i
<n;
i
++)
140
GECODE_ME_CHECK
(
x
[
i
].zero(home));
141
return
home.
ES_SUBSUMED
(*
this
);
142
}
143
144
// Check whether there is a one
145
if
(status == S_ONE) {
146
status = S_RUN;
147
for
(
int
i
=0;
true
;
i
++)
148
if
(
x
[
i
].
one
()) {
149
for
(
int
j=0; j<
i
; j++)
150
GECODE_ME_CHECK
(
x
[j].zero(home));
151
for
(
int
j=i+1; j<n; j++)
152
GECODE_ME_CHECK
(
x
[j].zero(home));
153
GECODE_ME_CHECK
(
y
.
eq
(home,i+o));
154
return
home.
ES_SUBSUMED
(*
this
);
155
}
156
GECODE_NEVER
;
157
}
158
159
status = S_RUN;
160
161
redo:
162
163
// Assign all Boolean views to zero that are outside bounds
164
{
165
int
min
=
y
.
min
()-o;
166
for
(
int
i
=0;
i
<
min
;
i
++)
167
GECODE_ME_CHECK
(
x
[
i
].zero(home));
168
x
.
drop_fst
(min); o +=
min
; n =
x
.
size
();
169
170
int
max
=
y
.
max
()-o;
171
for
(
int
i
=max+1;
i
<n;
i
++)
172
GECODE_ME_CHECK
(
x
[
i
].zero(home));
173
x
.
drop_lst
(max); n =
x
.
size
();
174
}
175
176
{
177
// Remove zeros on the left
178
int
i
=0;
179
while
((i < n) &&
x
[i].zero()) i++;
180
if
(i >= n)
181
return
ES_FAILED
;
182
x
.
drop_fst
(i); o +=
i
; n =
x
.
size
();
183
}
184
185
{
186
// Remove zeros on the right
187
int
i
=n-1;
188
while
((i >= 0) &&
x
[i].zero()) i--;
189
assert(i >= 0);
190
x
.
drop_lst
(i); n =
x
.
size
();
191
}
192
193
assert(n >= 1);
194
195
// Is there only one left?
196
if
(n == 1) {
197
GECODE_ME_CHECK
(
x
[0].
one
(home));
198
GECODE_ME_CHECK
(
y
.
eq
(home,o));
199
return
home.
ES_SUBSUMED
(*
this
);
200
}
201
202
// Update bounds
203
GECODE_ME_CHECK
(
y
.
gq
(home,o));
204
GECODE_ME_CHECK
(
y
.
lq
(home,o+n-1));
205
if
((
y
.
min
() > o) || (
y
.
max
() < o+n-1))
206
goto
redo;
207
208
assert((n >= 2) &&
x
[0].none() &&
x
[n-1].none());
209
assert((
y
.
min
()-o == 0) && (
y
.
max
()-o == n-1));
210
211
// Propagate from y to Boolean views
212
if
((
IntView::me
(med) ==
ME_INT_BND
) || (
IntView::me
(med) ==
ME_INT_DOM
)) {
213
ViewValues<IntView>
v
(
y
);
214
int
i
=0;
215
do
{
216
int
j = v.
val
()-o;
217
if
(i < j) {
218
GECODE_ME_CHECK
(
x
[i].zero(home));
219
++
i
;
220
}
else
if
(i > j) {
221
++
v
;
222
}
else
{
223
assert(i == j);
224
++
i
; ++
v
;
225
}
226
}
while
(
v
() && (i < n));
227
}
228
229
// Propagate from Boolean views to y
230
if
(
BoolView::me
(med) ==
ME_BOOL_VAL
) {
231
BoolIter
bv(
x
,o);
232
GECODE_ME_CHECK
(
y
.
minus_v
(home,bv,
false
));
233
}
234
status = S_NONE;
235
return
ES_FIX
;
236
}
237
238
}}}
239
240
// STATISTICS: int-prop
241