00001 #pragma once
00002
00003 #include <queue>
00004 #include <vector>
00005
00006 namespace Moses
00007 {
00008 namespace Syntax
00009 {
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 template<typename T>
00025 class BoundedPriorityContainer
00026 {
00027 public:
00028 typedef typename std::vector<T>::iterator Iterator;
00029 typedef typename std::vector<T>::const_iterator ConstIterator;
00030
00031 BoundedPriorityContainer(std::size_t);
00032
00033 Iterator Begin() {
00034 return m_elements.begin();
00035 }
00036 Iterator End() {
00037 return m_elements.begin()+m_size;
00038 }
00039
00040 ConstIterator Begin() const {
00041 return m_elements.begin();
00042 }
00043 ConstIterator End() const {
00044 return m_elements.begin()+m_size;
00045 }
00046
00047
00048 std::size_t Size() const {
00049 return m_size;
00050 }
00051
00052
00053
00054
00055
00056
00057
00058
00059 void LazyClear() {
00060 m_size = 0;
00061 while (!m_queue.empty()) {
00062 m_queue.pop();
00063 }
00064 }
00065
00066
00067
00068
00069
00070
00071 bool Insert(const T &, float);
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081 bool SwapIn(T &, float);
00082
00083
00084
00085 bool WouldAccept(float priority) {
00086 return m_size < m_limit || priority > m_queue.top().first;
00087 }
00088
00089 private:
00090 typedef std::pair<float, int> PriorityIndexPair;
00091
00092 class PriorityIndexPairOrderer
00093 {
00094 public:
00095 bool operator()(const PriorityIndexPair &p,
00096 const PriorityIndexPair &q) const {
00097 return p.first > q.first;
00098 }
00099 };
00100
00101
00102
00103 typedef std::priority_queue<PriorityIndexPair,
00104 std::vector<PriorityIndexPair>,
00105 PriorityIndexPairOrderer> Queue;
00106
00107
00108
00109 std::vector<T> m_elements;
00110
00111
00112 std::size_t m_size;
00113
00114
00115 const std::size_t m_limit;
00116
00117
00118 Queue m_queue;
00119 };
00120
00121 template<typename T>
00122 BoundedPriorityContainer<T>::BoundedPriorityContainer(std::size_t limit)
00123 : m_size(0)
00124 , m_limit(limit)
00125 {
00126 m_elements.reserve(m_limit);
00127 }
00128
00129 template<typename T>
00130 bool BoundedPriorityContainer<T>::Insert(const T &t, float priority)
00131 {
00132 if (m_size < m_limit) {
00133 PriorityIndexPair pair(priority, m_size);
00134 m_queue.push(pair);
00135 if (m_size < m_elements.size()) {
00136 m_elements[m_size] = t;
00137 } else {
00138 m_elements.push_back(t);
00139 }
00140 ++m_size;
00141 return true;
00142 } else if (priority > m_queue.top().first) {
00143 PriorityIndexPair pair = m_queue.top();
00144 m_queue.pop();
00145 pair.first = priority;
00146 m_elements[pair.second] = t;
00147 m_queue.push(pair);
00148 return true;
00149 }
00150 return false;
00151 }
00152
00153 template<typename T>
00154 bool BoundedPriorityContainer<T>::SwapIn(T &t, float priority)
00155 {
00156 if (m_size < m_limit) {
00157 PriorityIndexPair pair(priority, m_size);
00158 m_queue.push(pair);
00159 if (m_size < m_elements.size()) {
00160 swap(m_elements[m_size], t);
00161 } else {
00162 m_elements.push_back(t);
00163 }
00164 ++m_size;
00165 return true;
00166 } else if (priority > m_queue.top().first) {
00167 PriorityIndexPair pair = m_queue.top();
00168 m_queue.pop();
00169 pair.first = priority;
00170 swap(m_elements[pair.second], t);
00171 m_queue.push(pair);
00172 return true;
00173 }
00174 return false;
00175 }
00176
00177 }
00178 }