diff options
author | Kenneth Heafield <github@kheafield.com> | 2012-10-15 16:58:33 +0400 |
---|---|---|
committer | Kenneth Heafield <github@kheafield.com> | 2012-10-15 16:58:33 +0400 |
commit | 0eb98df0fe32a8e31188fa107f789afd73d81ccf (patch) | |
tree | 6b2f5bb5a21e132f419da1fa7064f94eb74428e6 /search/vertex.cc | |
parent | ed00315c8cf4c0b0f8ebc535cf676139b25ab087 (diff) |
Submodules are evil. Undo it.
Diffstat (limited to 'search/vertex.cc')
-rw-r--r-- | search/vertex.cc | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/search/vertex.cc b/search/vertex.cc new file mode 100644 index 000000000..cc53c0dd5 --- /dev/null +++ b/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 |