main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:45 for Gecode by
doxygen
1.8.3.1
gecode
search
sequential
path.hh
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, 2003
8
*
9
* Last modified:
10
* $Date: 2010-07-22 19:59:14 +1000 (Thu, 22 Jul 2010) $ by $Author: schulte $
11
* $Revision: 11248 $
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
#ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
39
#define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
40
41
#include <
gecode/search.hh
>
42
43
namespace
Gecode {
namespace
Search {
namespace
Sequential {
44
58
class
Path
{
59
public
:
61
class
Edge
{
62
protected
:
64
Space
*
_space
;
66
unsigned
int
_alt
;
68
const
Choice
*
_choice
;
69
public
:
71
Edge
(
void
);
73
Edge
(
Space
* s,
Space
*
c
);
74
76
Space
*
space
(
void
)
const
;
78
void
space
(
Space
* s);
79
81
const
Choice
*
choice
(
void
)
const
;
82
84
unsigned
int
alt
(
void
)
const
;
86
bool
rightmost
(
void
)
const
;
88
void
next
(
void
);
89
91
void
dispose
(
void
);
92
};
93
protected
:
95
Support::DynamicStack<Edge,Heap>
ds
;
96
public
:
98
Path
(
void
);
100
const
Choice
*
push
(
Worker
& stat,
Space
* s,
Space
*
c
);
102
bool
next
(
Worker
& s);
104
Edge
&
top
(
void
)
const
;
106
bool
empty
(
void
)
const
;
108
int
lc
(
void
)
const
;
110
void
unwind
(
int
l);
112
void
commit
(
Space
* s,
int
i
)
const
;
114
Space
*
recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s);
116
Space
*
recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s,
117
const
Space
* best,
int
&
mark
);
119
int
entries
(
void
)
const
;
121
size_t
size
(
void
)
const
;
123
void
reset
(
void
);
124
};
125
126
127
/*
128
* Edge for recomputation
129
*
130
*/
131
forceinline
132
Path::Edge::Edge
(
void
) {}
133
134
forceinline
135
Path::Edge::Edge
(
Space
* s,
Space
*
c
)
136
: _space(c), _alt(0), _choice(s->choice()) {}
137
138
forceinline
Space
*
139
Path::Edge::space
(
void
)
const
{
140
return
_space;
141
}
142
forceinline
void
143
Path::Edge::space
(
Space
* s) {
144
_space = s;
145
}
146
147
forceinline
unsigned
int
148
Path::Edge::alt
(
void
)
const
{
149
return
_alt;
150
}
151
forceinline
bool
152
Path::Edge::rightmost
(
void
)
const
{
153
return
_alt+1 == _choice->alternatives();
154
}
155
forceinline
void
156
Path::Edge::next
(
void
) {
157
_alt++;
158
}
159
160
forceinline
const
Choice
*
161
Path::Edge::choice
(
void
)
const
{
162
return
_choice;
163
}
164
165
forceinline
void
166
Path::Edge::dispose
(
void
) {
167
delete
_space;
168
delete
_choice;
169
}
170
171
172
173
/*
174
* Depth-first stack with recomputation
175
*
176
*/
177
178
forceinline
179
Path::Path
(
void
) :
ds
(
heap
) {}
180
181
forceinline
const
Choice
*
182
Path::push
(
Worker
& stat,
Space
* s,
Space
*
c
) {
183
Edge
sn(s,c);
184
ds
.push(sn);
185
stat.
stack_depth
(static_cast<unsigned long int>(
ds
.entries()));
186
return
sn.
choice
();
187
}
188
189
forceinline
bool
190
Path::next
(
Worker
& stat) {
191
while
(!
ds
.empty())
192
if
(
ds
.top().rightmost()) {
193
stat.
pop
(
ds
.top().space(),
ds
.top().choice());
194
ds
.pop().dispose();
195
}
else
{
196
ds
.top().next();
197
return
true
;
198
}
199
return
false
;
200
}
201
202
forceinline
Path::Edge
&
203
Path::top
(
void
)
const
{
204
assert(!
ds
.empty());
205
return
ds
.top();
206
}
207
208
forceinline
bool
209
Path::empty
(
void
)
const
{
210
return
ds
.empty();
211
}
212
213
forceinline
void
214
Path::commit
(
Space
* s,
int
i
)
const
{
215
const
Edge
& n =
ds
[
i
];
216
s->
commit
(*n.
choice
(),n.
alt
());
217
}
218
219
forceinline
int
220
Path::lc
(
void
)
const
{
221
int
l =
ds
.entries()-1;
222
while
(
ds
[l].space() == NULL)
223
l--;
224
return
l;
225
}
226
227
forceinline
int
228
Path::entries
(
void
)
const
{
229
return
ds
.entries();
230
}
231
232
forceinline
size_t
233
Path::size
(
void
)
const
{
234
return
ds
.size();
235
}
236
237
forceinline
void
238
Path::unwind
(
int
l) {
239
assert((
ds
[l].space() == NULL) ||
ds
[l].space()->failed());
240
int
n =
ds
.entries();
241
for
(
int
i
=l;
i
<n;
i
++)
242
ds
.pop().dispose();
243
assert(
ds
.entries() == l);
244
}
245
246
inline
void
247
Path::reset
(
void
) {
248
while
(!
ds
.empty())
249
ds
.pop().dispose();
250
}
251
252
forceinline
Space
*
253
Path::recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& stat) {
254
assert(!
ds
.empty());
255
// Recompute space according to path
256
// Also say distance to copy (d == 0) requires immediate copying
257
258
// Check for LAO
259
if
((
ds
.top().space() != NULL) &&
ds
.top().rightmost()) {
260
Space
* s =
ds
.top().space();
261
stat.
lao
(s);
262
s->
commit
(*
ds
.top().choice(),
ds
.top().alt());
263
assert(
ds
.entries()-1 ==
lc
());
264
ds
.top().space(NULL);
265
d = 0;
266
return
s;
267
}
268
// General case for recomputation
269
int
l =
lc
();
// Position of last clone
270
int
n =
ds
.entries();
// Number of stack entries
271
// New distance, if no adaptive recomputation
272
d =
static_cast<
unsigned
int
>
(n - l);
273
274
Space
* s =
ds
[l].space()->clone();
// Last clone
275
276
if
(d < a_d) {
277
// No adaptive recomputation
278
for
(
int
i
=l;
i
<n;
i
++)
279
commit
(s,
i
);
280
}
else
{
281
int
m
= l +
static_cast<
int
>
(d >> 1);
// Middle between copy and top
282
int
i
= l;
// To iterate over all entries
283
// Recompute up to middle
284
for
(; i<
m
; i++ )
285
commit
(s,i);
286
// Skip over all rightmost branches
287
for
(; (i<n) &&
ds
[i].rightmost(); i++)
288
commit
(s,i);
289
// Is there any point to make a copy?
290
if
(i<n-1) {
291
// Propagate to fixpoint
292
SpaceStatus
ss = s->
status
(stat);
293
/*
294
* Again, the space might already propagate to failure (due to
295
* weakly monotonic propagators).
296
*/
297
if
(ss ==
SS_FAILED
) {
298
// s must be deleted as it is not on the stack
299
delete
s;
300
stat.
fail
++;
301
unwind
(i);
302
return
NULL;
303
}
304
ds
[
i
].space(s->
clone
());
305
stat.
adapt
(
ds
[i].space());
306
d =
static_cast<
unsigned
int
>
(n-
i
);
307
}
308
// Finally do the remaining commits
309
for
(; i<n; i++)
310
commit
(s,i);
311
}
312
return
s;
313
}
314
315
forceinline
Space
*
316
Path::recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& stat,
317
const
Space
* best,
int
&
mark
) {
318
assert(!
ds
.empty());
319
// Recompute space according to path
320
// Also say distance to copy (d == 0) requires immediate copying
321
322
// Check for LAO
323
if
((
ds
.top().space() != NULL) &&
ds
.top().rightmost()) {
324
Space
* s =
ds
.top().space();
325
stat.
lao
(s);
326
s->
commit
(*
ds
.top().choice(),
ds
.top().alt());
327
assert(
ds
.entries()-1 ==
lc
());
328
if
(mark >
ds
.entries()-1) {
329
mark =
ds
.entries()-1;
330
s->
constrain
(*best);
331
}
332
ds
.top().space(NULL);
333
d = 0;
334
return
s;
335
}
336
// General case for recomputation
337
int
l =
lc
();
// Position of last clone
338
int
n =
ds
.entries();
// Number of stack entries
339
// New distance, if no adaptive recomputation
340
d =
static_cast<
unsigned
int
>
(n - l);
341
342
Space
* s =
ds
[l].space();
// Last clone
343
344
if
(l < mark) {
345
mark = l;
346
s->
constrain
(*best);
347
// The space on the stack could be failed now as an additional
348
// constraint might have been added.
349
if
(s->
status
(stat) ==
SS_FAILED
) {
350
// s does not need deletion as it is on the stack (unwind does this)
351
stat.
fail
++;
352
unwind
(l);
353
return
NULL;
354
}
355
// It is important to replace the space on the stack with the
356
// copy: a copy might be much smaller due to flushed caches
357
// of propagators
358
Space
*
c
= s->
clone
();
359
ds
[l].space(c);
360
stat.
constrained
(s,c);
361
}
else
{
362
s = s->
clone
();
363
}
364
365
if
(d < a_d) {
366
// No adaptive recomputation
367
for
(
int
i
=l;
i
<n;
i
++)
368
commit
(s,
i
);
369
}
else
{
370
int
m
= l +
static_cast<
int
>
(d >> 1);
// Middle between copy and top
371
int
i
= l;
// To iterate over all entries
372
// Recompute up to middle
373
for
(; i<
m
; i++ )
374
commit
(s,i);
375
// Skip over all rightmost branches
376
for
(; (i<n) &&
ds
[i].rightmost(); i++)
377
commit
(s,i);
378
// Is there any point to make a copy?
379
if
(i<n-1) {
380
// Propagate to fixpoint
381
SpaceStatus
ss = s->
status
(stat);
382
/*
383
* Again, the space might already propagate to failure
384
*
385
* This can be for two reasons:
386
* - constrain is true, so we fail
387
* - the space has weakly monotonic propagators
388
*/
389
if
(ss ==
SS_FAILED
) {
390
// s must be deleted as it is not on the stack
391
delete
s;
392
stat.
fail
++;
393
unwind
(i);
394
return
NULL;
395
}
396
ds
[
i
].space(s->
clone
());
397
stat.
adapt
(
ds
[i].space());
398
d =
static_cast<
unsigned
int
>
(n-
i
);
399
}
400
// Finally do the remaining commits
401
for
(; i<n; i++)
402
commit
(s,i);
403
}
404
return
s;
405
}
406
407
}}}
408
409
#endif
410
411
// STATISTICS: search-sequential