00001
00002 #ifndef __n_best_list_h
00003 #define __n_best_list_h
00004 #include <algorithm>
00005 #include "moses/TranslationModel/UG/generic/sorting/VectorIndexSorter.h"
00006
00007
00008
00009
00010
00011
00012
00013 namespace Moses
00014 {
00015
00016 template<typename THINGY, typename CMP>
00017 class
00018 NBestList
00019 {
00020 std::vector<uint32_t> m_heap;
00021 std::vector<THINGY> m_list;
00022 VectorIndexSorter<THINGY, CMP, uint32_t> m_better;
00023 mutable std::vector<uint32_t> m_order;
00024 mutable bool m_changed;
00025 public:
00026 NBestList(size_t const max_size, CMP const& cmp);
00027 NBestList(size_t const max_size);
00028 bool add(THINGY const& item);
00029 THINGY const& operator[](int i) const;
00030 THINGY const& get_unsorted(int i) const;
00031 size_t size() const {
00032 return m_heap.size();
00033 }
00034 };
00035
00036 template<typename THINGY, typename CMP>
00037 NBestList<THINGY,CMP>::
00038 NBestList(size_t const max_size, CMP const& cmp)
00039 : m_better(m_list, cmp), m_changed(false)
00040 {
00041 m_heap.reserve(max_size);
00042 }
00043
00044 template<typename THINGY, typename CMP>
00045 NBestList<THINGY,CMP>::
00046 NBestList(size_t const max_size)
00047 : m_better(m_heap), m_changed(false)
00048 {
00049 m_heap.reserve(max_size);
00050 }
00051
00052 template<typename THINGY, typename CMP>
00053 bool
00054 NBestList<THINGY,CMP>::
00055 add(THINGY const& item)
00056 {
00057 if (m_heap.size() == m_heap.capacity())
00058 {
00059 if (m_better.Compare(item, m_list[m_heap.at(0)]))
00060 {
00061 pop_heap(m_heap.begin(),m_heap.end(),m_better);
00062 m_list[m_heap.back()] = item;
00063 }
00064 else return false;
00065 }
00066 else
00067 {
00068 m_list.push_back(item);
00069 m_heap.push_back(m_heap.size());
00070 }
00071 push_heap(m_heap.begin(),m_heap.end(),m_better);
00072 return m_changed = true;
00073 }
00074
00075 template<typename THINGY, typename CMP>
00076 THINGY const&
00077 NBestList<THINGY,CMP>::
00078 operator[](int i) const
00079 {
00080 if (m_changed)
00081 {
00082 m_order.assign(m_heap.begin(),m_heap.end());
00083 for (size_t k = m_heap.size(); k != 0; --k)
00084 pop_heap(m_order.begin(), m_order.begin()+k,m_better);
00085 m_changed = false;
00086 }
00087 if (i < 0) i += m_order.size();
00088 return m_list[m_order.at(i)];
00089 }
00090
00091 template<typename THINGY, typename CMP>
00092 THINGY const&
00093 NBestList<THINGY,CMP>::
00094 get_unsorted(int i) const
00095 {
00096 if (i < 0) i += m_heap.size();
00097 return m_list[m_heap.at(i)];
00098 }
00099
00100 }
00101 #endif