blob: 45842982cebdc014e8e45966d109a06c7b155978 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include "search/vertex.hh"
#include "search/context.hh"
#include <algorithm>
#include <functional>
#include <assert.h>
namespace search {
namespace {
struct GreaterByBound : public std::binary_function<const VertexNode *, const VertexNode *, bool> {
bool operator()(const VertexNode *first, const VertexNode *second) const {
return first->Bound() > second->Bound();
}
};
} // namespace
void VertexNode::RecursiveSortAndSet(ContextBase &context, VertexNode *&parent_ptr) {
if (Complete()) {
assert(end_);
assert(extend_.empty());
return;
}
if (extend_.size() == 1) {
parent_ptr = extend_[0];
extend_[0]->RecursiveSortAndSet(context, parent_ptr);
context.DeleteVertexNode(this);
return;
}
for (std::vector<VertexNode*>::iterator i = extend_.begin(); i != extend_.end(); ++i) {
(*i)->RecursiveSortAndSet(context, *i);
}
std::sort(extend_.begin(), extend_.end(), GreaterByBound());
bound_ = extend_.front()->Bound();
}
void VertexNode::SortAndSet(ContextBase &context) {
// This is the root. The root might be empty.
if (extend_.empty()) {
bound_ = -INFINITY;
return;
}
// The root cannot be replaced. There's always one transition.
for (std::vector<VertexNode*>::iterator i = extend_.begin(); i != extend_.end(); ++i) {
(*i)->RecursiveSortAndSet(context, *i);
}
std::sort(extend_.begin(), extend_.end(), GreaterByBound());
bound_ = extend_.front()->Bound();
}
} // namespace search
|
