00001 #ifndef SEARCH_NBEST__
00002 #define SEARCH_NBEST__
00003
00004 #include "search/applied.hh"
00005 #include "search/config.hh"
00006 #include "search/edge.hh"
00007
00008 #include <boost/pool/object_pool.hpp>
00009
00010 #include <cstddef>
00011 #include <queue>
00012 #include <vector>
00013 #include <cassert>
00014
00015 namespace search {
00016
00017 class NBestList;
00018
00019 class NBestList {
00020 private:
00021 class RevealedRef {
00022 public:
00023 explicit RevealedRef(History history)
00024 : in_(static_cast<NBestList*>(history)), index_(0) {}
00025
00026 private:
00027 friend class NBestList;
00028
00029 NBestList *in_;
00030 std::size_t index_;
00031 };
00032
00033 typedef GenericApplied<RevealedRef> QueueEntry;
00034
00035 public:
00036 NBestList(std::vector<PartialEdge> &existing, util::Pool &entry_pool, std::size_t keep);
00037
00038 Score TopAfterConstructor() const;
00039
00040 const std::vector<Applied> &Extract(util::Pool &pool, std::size_t n);
00041
00042 private:
00043 Score Visit(util::Pool &pool, std::size_t index);
00044
00045 Applied Get(util::Pool &pool, std::size_t index);
00046
00047 void MoveTop(util::Pool &pool);
00048
00049 typedef std::vector<Applied> Revealed;
00050 Revealed revealed_;
00051
00052 typedef std::priority_queue<QueueEntry> Queue;
00053 Queue queue_;
00054 };
00055
00056 class NBest {
00057 public:
00058 typedef std::vector<PartialEdge> Combine;
00059
00060 explicit NBest(const NBestConfig &config) : config_(config) {}
00061
00062 void Add(std::vector<PartialEdge> &existing, PartialEdge addition) const {
00063 existing.push_back(addition);
00064 }
00065
00066 NBestComplete Complete(std::vector<PartialEdge> &partials);
00067
00068 const std::vector<Applied> &Extract(History root);
00069
00070 private:
00071 const NBestConfig config_;
00072
00073 boost::object_pool<NBestList> list_pool_;
00074
00075 util::Pool entry_pool_;
00076 };
00077
00078 }
00079
00080 #endif // SEARCH_NBEST__