main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:37 for Gecode by
doxygen
1.8.3.1
gecode
set
channel
set.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Denys Duchier <denys.duchier@univ-orleans.fr>
5
*
6
* Copyright:
7
* Denys Duchier, 2011
8
*
9
* Last modified:
10
* $Date: 2011-11-03 11:52:07 +0100 (Thu, 03 Nov 2011) $ by $Author: tack $
11
* $Revision: 12452 $
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
Set {
namespace
Channel {
39
40
template
<
typename
View>
41
forceinline
42
ChannelSet<View>::ChannelSet
(
Home
home,
43
ViewArray
<
CachedView<View>
>& xs0,
44
ViewArray
<
CachedView<View>
>& ys0)
45
:
Propagator
(home), xs(xs0), ys(ys0)
46
{
47
for
(
int
i
=
xs
.size();
i
--;)
48
xs
[
i
].initCache(home,
IntSet::empty
,
IntSet
(0,
ys
.size()-1));
49
for
(
int
i
=
ys
.size();
i
--;)
50
ys
[
i
].initCache(home,
IntSet::empty
,
IntSet
(0,
xs
.size()-1));
51
xs
.subscribe(home,*
this
,
PC_SET_ANY
);
52
ys
.subscribe(home,*
this
,
PC_SET_ANY
);
53
}
54
55
template
<
typename
View>
56
forceinline
57
ChannelSet<View>::ChannelSet
(
Space
& home,
bool
share,
ChannelSet
&
p
)
58
:
Propagator
(home, share, p)
59
{
60
xs
.update(home, share, p.
xs
);
61
ys
.update(home, share, p.
ys
);
62
}
63
64
template
<
typename
View>
65
forceinline
ExecStatus
66
ChannelSet<View>::post
(
Home
home,
67
ViewArray
<
CachedView<View>
>& xs,
68
ViewArray
<
CachedView<View>
>& ys)
69
{
70
int
xssize = xs.size();
71
for
(
int
i
=ys.
size
();
i
--;)
72
{
73
GECODE_ME_CHECK
(ys[
i
].
exclude
(home, xssize,
Limits::max
));
74
GECODE_ME_CHECK
(ys[
i
].
exclude
(home,
Limits::min
, -1));
75
}
76
int
yssize = ys.size();
77
for
(
int
i
=xs.
size
();
i
--;)
78
{
79
GECODE_ME_CHECK
(xs[
i
].
exclude
(home, yssize,
Limits::max
));
80
GECODE_ME_CHECK
(xs[
i
].
exclude
(home,
Limits::min
, -1));
81
}
82
(void)
new
(home)
ChannelSet
(home,xs,ys);
83
return
ES_OK
;
84
}
85
86
template
<
typename
View>
87
PropCost
88
ChannelSet<View>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
89
{
90
return
PropCost::quadratic
(
PropCost::HI
, xs.size()+ys.size());
91
}
92
93
template
<
typename
View>
94
forceinline
size_t
95
ChannelSet<View>::dispose
(
Space
& home)
96
{
97
xs.cancel(home, *
this
,
PC_SET_ANY
);
98
ys.cancel(home, *
this
,
PC_SET_ANY
);
99
(void)
Propagator::dispose
(home);
100
return
sizeof
(*this);
101
}
102
103
template
<
typename
View>
104
Actor
*
105
ChannelSet<View>::copy
(
Space
& home,
bool
share)
106
{
107
return
new
(home)
ChannelSet
(home,share,*
this
);
108
}
109
110
template
<
typename
View>
111
ExecStatus
112
ChannelSet<View>::propagate
(
Space
& home,
const
ModEventDelta
&)
113
{
114
int
assigned
= 0;
115
bool
again =
true
;
116
while
(again)
117
{
118
assigned = 0;
119
again =
false
;
120
for
(
int
i
=xs.
size
();
i
--;)
121
{
122
if
(xs[
i
].
assigned
())
123
++assigned;
124
if
(xs[
i
].glbModified())
125
{
126
GlbDiffRanges<View>
xilb(xs[
i
]);
127
Iter::Ranges::ToValues<GlbDiffRanges<View>
> dv(xilb);
128
for
(;dv();++dv)
129
GECODE_ME_CHECK
(ys[dv.
val
()].include(home,i));
130
xs[
i
].cacheGlb(home);
131
again =
true
;
132
}
133
if
(xs[
i
].lubModified())
134
{
135
LubDiffRanges<View>
xiub(xs[
i
]);
136
Iter::Ranges::ToValues<LubDiffRanges<View>
> dv(xiub);
137
for
(;dv();++dv)
138
GECODE_ME_CHECK
(ys[dv.
val
()].exclude(home,i));
139
xs[
i
].cacheLub(home);
140
again =
true
;
141
}
142
}
143
for
(
int
i
=ys.
size
();
i
--;)
144
{
145
if
(ys[
i
].
assigned
())
146
++assigned;
147
if
(ys[
i
].glbModified())
148
{
149
GlbDiffRanges<View>
yilb(ys[
i
]);
150
Iter::Ranges::ToValues<GlbDiffRanges<View>
> dv(yilb);
151
for
(;dv();++dv)
152
GECODE_ME_CHECK
(xs[dv.
val
()].include(home,i));
153
ys[
i
].cacheGlb(home);
154
again =
true
;
155
}
156
if
(ys[
i
].lubModified())
157
{
158
LubDiffRanges<View>
yiub(ys[
i
]);
159
Iter::Ranges::ToValues<LubDiffRanges<View>
> dv(yiub);
160
for
(;dv();++dv)
161
GECODE_ME_CHECK
(xs[dv.
val
()].exclude(home,i));
162
ys[
i
].cacheLub(home);
163
again =
true
;
164
}
165
}
166
}
167
168
return
(assigned == xs.size()+ys.size()) ? home.
ES_SUBSUMED
(*
this
) :
ES_FIX
;
169
}
170
}}}
171
172
// STATISTICS: set-prop