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
kernel
brancher-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, 2012
8
*
9
* Last modified:
10
* $Date: 2013-02-08 16:47:00 +0100 (Fri, 08 Feb 2013) $ by $Author: schulte $
11
* $Revision: 13278 $
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 {
39
47
48
class
Pos
{
49
public
:
51
const
int
pos
;
53
Pos
(
int
p
);
54
};
55
57
class
GECODE_VTABLE_EXPORT
PosChoice
:
public
Choice
{
58
private
:
60
const
Pos
_pos;
61
public
:
63
PosChoice
(
const
Brancher
&
b
,
unsigned
int
a
,
const
Pos
&
p
);
65
const
Pos
&
pos
(
void
)
const
;
67
virtual
size_t
size
(
void
)
const
;
69
virtual
void
archive(
Archive
& e)
const
;
70
};
71
78
template
<
class
View,
int
n>
79
class
ViewBrancher
:
public
Brancher
{
80
protected
:
82
typedef
typename
BranchTraits<typename View::VarType>::Filter
BranchFilter
;
84
ViewArray<View>
x
;
86
mutable
int
start
;
88
ViewSel<View>
*
vs
[
n
];
90
BranchFilter
bf
;
92
Pos
pos
(
Space
& home);
94
View
view
(
const
Pos
&
p
)
const
;
96
ViewBrancher
(
Space
& home,
bool
shared
,
ViewBrancher<View,n>
&
b
);
98
ViewBrancher
(
Home
home,
ViewArray<View>
&
x
,
99
ViewSel<View>
*
vs
[
n
],
BranchFilter
bf
);
100
public
:
102
virtual
bool
status
(
const
Space
& home)
const
;
104
virtual
size_t
dispose
(
Space
& home);
105
};
106
108
109
110
/*
111
* Position information
112
*
113
*/
114
forceinline
115
Pos::Pos
(
int
p
) :
pos
(p) {}
116
117
/*
118
* Choice with position
119
*
120
*/
121
forceinline
122
PosChoice::PosChoice
(
const
Brancher
&
b
,
unsigned
int
a
,
const
Pos
&
p
)
123
:
Choice
(b,a), _pos(p) {}
124
forceinline
const
Pos
&
125
PosChoice::pos
(
void
)
const
{
126
return
_pos;
127
}
128
forceinline
size_t
129
PosChoice::size
(
void
)
const
{
130
return
sizeof
(
PosChoice
);
131
}
132
forceinline
void
133
PosChoice::archive
(
Archive
& e)
const
{
134
Choice::archive
(e);
135
e << _pos.
pos
;
136
}
137
138
template
<
class
View,
int
n>
139
forceinline
140
ViewBrancher<View,n>::ViewBrancher
(
Home
home,
ViewArray<View>
& x0,
141
ViewSel<View>
* vs0[
n
],
BranchFilter
bf0)
142
:
Brancher
(home),
x
(x0), start(0), bf(bf0) {
143
for
(
int
i
=0;
i
<
n
;
i
++)
144
vs
[
i
] = vs0[
i
];
145
for
(
int
i
=0;
i
<
n
;
i
++)
146
if
(
vs
[
i
]->notice()) {
147
home.
notice
(*
this
,
AP_DISPOSE
);
148
break
;
149
}
150
}
151
152
template
<
class
View,
int
n>
153
forceinline
154
ViewBrancher<View,n>::ViewBrancher
(
Space
& home,
bool
shared
,
155
ViewBrancher<View,n>
& vb)
156
:
Brancher
(home,shared,vb), start(vb.start), bf(vb.bf) {
157
x
.update(home,shared,vb.
x
);
158
for
(
int
i
=0;
i
<
n
;
i
++)
159
vs
[
i
] = vb.
vs
[
i
]->copy(home,shared);
160
}
161
162
template
<
class
View,
int
n>
163
bool
164
ViewBrancher<View,n>::status
(
const
Space
& home)
const
{
165
if
(bf == NULL) {
166
for
(
int
i
=start;
i
<
x
.size();
i
++)
167
if
(!
x
[
i
].
assigned
()) {
168
start =
i
;
169
return
true
;
170
}
171
}
else
{
172
for
(
int
i
=start;
i
<
x
.size();
i
++) {
173
typename
View::VarType y(
x
[
i
].varimp());
174
if
(!
x
[
i
].
assigned
() && bf(home,y,
i
)) {
175
start =
i
;
176
return
true
;
177
}
178
}
179
}
180
return
false
;
181
}
182
183
template
<
class
View,
int
n>
184
inline
Pos
185
ViewBrancher<View,n>::pos
(
Space
& home) {
186
assert(!
x
[start].
assigned
());
187
int
s;
188
if
(bf == NULL) {
189
if
(
n
== 1) {
190
s = vs[0]->select(home,
x
,start);
191
}
else
{
192
Region
r
(home);
193
int
* ties = r.
alloc
<
int
>(
x
.size()-start+1);
194
int
n_ties;
195
vs[0]->ties(home,
x
,start,ties,n_ties);
196
for
(
int
i
=1; (
i
<
n
-1) && (n_ties > 1);
i
++)
197
vs[
i
]->brk(home,
x
,ties,n_ties);
198
if
(n_ties > 1)
199
s = vs[
n
-1]->select(home,
x
,ties,n_ties);
200
else
201
s = ties[0];
202
}
203
}
else
{
204
if
(
n
== 1) {
205
s = vs[0]->select(home,
x
,start,bf);
206
}
else
{
207
Region
r
(home);
208
int
* ties = r.
alloc
<
int
>(
x
.size()-start+1);
209
int
n_ties;
210
vs[0]->ties(home,
x
,start,ties,n_ties,bf);
211
for
(
int
i
=1; (
i
<
n
-1) && (n_ties > 1);
i
++)
212
vs[
i
]->brk(home,
x
,ties,n_ties);
213
if
(n_ties > 1)
214
s = vs[
n
-1]->select(home,
x
,ties,n_ties);
215
else
216
s = ties[0];
217
}
218
}
219
Pos
p
(s);
220
return
p
;
221
}
222
223
template
<
class
View,
int
n>
224
forceinline
View
225
ViewBrancher<View,n>::view
(
const
Pos
&
p
)
const
{
226
return
x
[p.
pos
];
227
}
228
229
template
<
class
View,
int
n>
230
forceinline
size_t
231
ViewBrancher<View,n>::dispose
(
Space
& home) {
232
for
(
int
i
=0;
i
<
n
;
i
++)
233
if
(vs[
i
]->notice()) {
234
home.
ignore
(*
this
,
AP_DISPOSE
);
235
break
;
236
}
237
for
(
int
i
=0;
i
<
n
;
i
++)
238
vs[
i
]->dispose(home);
239
(void)
Brancher::dispose
(home);
240
return
sizeof
(
ViewBrancher<View,n>
);
241
}
242
243
}
244
245
// STATISTICS: kernel-branch