diff options
author | Kenneth Heafield <github@kheafield.com> | 2012-11-15 22:04:07 +0400 |
---|---|---|
committer | Kenneth Heafield <github@kheafield.com> | 2012-11-15 22:04:07 +0400 |
commit | 9340f9f465a29e7653f9285963bcad0fe4a60ec6 (patch) | |
tree | 19d3503d6e0bf7a3dc2f8db744e1083b4c7d2419 /search/vertex.cc | |
parent | 877ade5327f7a736345f3b88c4294faa061826d6 (diff) |
Update incremental search
Diffstat (limited to 'search/vertex.cc')
-rw-r--r-- | search/vertex.cc | 27 |
1 files changed, 20 insertions, 7 deletions
diff --git a/search/vertex.cc b/search/vertex.cc index 11f4631fa..45842982c 100644 --- a/search/vertex.cc +++ b/search/vertex.cc @@ -19,21 +19,34 @@ struct GreaterByBound : public std::binary_function<const VertexNode *, const Ve } // namespace -void VertexNode::SortAndSet(ContextBase &context, VertexNode **parent_ptr) { +void VertexNode::RecursiveSortAndSet(ContextBase &context, VertexNode *&parent_ptr) { if (Complete()) { - assert(end_.Valid()); + assert(end_); assert(extend_.empty()); - bound_ = end_.GetScore(); return; } - if (extend_.size() == 1 && parent_ptr) { - *parent_ptr = extend_[0]; - extend_[0]->SortAndSet(context, parent_ptr); + 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)->SortAndSet(context, &*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(); |