diff options
author | Kenneth Heafield <github@kheafield.com> | 2012-09-11 14:30:16 +0100 |
---|---|---|
committer | Kenneth Heafield <github@kheafield.com> | 2012-09-11 14:31:42 +0100 |
commit | 58d7f847cd5b3c56682e834a2d9b897c6943fafc (patch) | |
tree | 04b370b0d92240a4a60dbf921548c927e0a5f00d /klm/search/vertex.cc | |
parent | 7aa4baf365a80380bebacfc4d4a1ef1b9d757590 (diff) |
Add search library to cdec (not used yet)
Diffstat (limited to 'klm/search/vertex.cc')
-rw-r--r-- | klm/search/vertex.cc | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/klm/search/vertex.cc b/klm/search/vertex.cc new file mode 100644 index 00000000..cc53c0dd --- /dev/null +++ b/klm/search/vertex.cc @@ -0,0 +1,48 @@ +#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::SortAndSet(ContextBase &context, VertexNode **parent_ptr) { + if (Complete()) { + assert(end_); + assert(extend_.empty()); + bound_ = end_->Bound(); + return; + } + if (extend_.size() == 1 && parent_ptr) { + *parent_ptr = extend_[0]; + extend_[0]->SortAndSet(context, parent_ptr); + context.DeleteVertexNode(this); + return; + } + for (std::vector<VertexNode*>::iterator i = extend_.begin(); i != extend_.end(); ++i) { + (*i)->SortAndSet(context, &*i); + } + std::sort(extend_.begin(), extend_.end(), GreaterByBound()); + bound_ = extend_.front()->Bound(); +} + +namespace { +VertexNode kBlankVertexNode; +} // namespace + +PartialVertex kBlankPartialVertex(kBlankVertexNode); + +} // namespace search |