00001 /*********************************************************************** 00002 Moses - statistical machine translation system 00003 Copyright (C) 2006-2011 University of Edinburgh 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Lesser General Public 00007 License as published by the Free Software Foundation; either 00008 version 2.1 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Lesser General Public License for more details. 00014 00015 You should have received a copy of the GNU Lesser General Public 00016 License along with this library; if not, write to the Free Software 00017 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00018 ***********************************************************************/ 00019 00020 #pragma once 00021 00022 #include <set> 00023 00024 namespace Moses 00025 { 00026 00027 // pair of Bleu score and index 00028 typedef std::pair<float, size_t> BleuIndexPair; 00029 00030 // A bounded priority queue of BleuIndexPairs. The top item is 00031 // the best scoring hypothesis. The queue assumes ownership of pushed items and 00032 // relinquishes ownership when they are popped. Any remaining items at the 00033 // time of the queue's destruction are deleted. 00034 class HypothesisQueue 00035 { 00036 00037 public: 00038 // Create empty queue with fixed capacity of c. Capacity 0 means unbounded. 00039 HypothesisQueue(size_t c) : m_capacity(c) {} 00040 ~HypothesisQueue(); 00041 00042 bool Empty() { 00043 return m_queue.empty(); 00044 } 00045 00046 // Add the hypo to the queue or delete it if the queue is full and the 00047 // score is no better than the queue's worst score. 00048 void Push(BleuIndexPair hypo); 00049 00050 // Remove the best-scoring detour from the queue and return it. The 00051 // caller is responsible for deleting the object. 00052 BleuIndexPair Pop(); 00053 00054 private: 00055 struct HypothesisOrderer { 00056 bool operator()(BleuIndexPair a, 00057 BleuIndexPair b) { 00058 return (a.first > b.first); 00059 } 00060 }; 00061 00062 typedef std::multiset<BleuIndexPair, HypothesisOrderer> HypoQueueType; 00063 //typedef std::set<BleuIndexPair, HypothesisOrderer> HypoQueueType; 00064 00065 HypoQueueType m_queue; 00066 const size_t m_capacity; 00067 }; 00068 00069 } // namespace Moses