move moses2 to root

6 files changed, 804 insertions, 0 deletions

diff --git a/moses2/defer/CubePruningCardinalStack/Misc.cpp b/moses2/defer/CubePruningCardinalStack/Misc.cpp
new file mode 100644
index 000000000..8918fdf52
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Misc.cpp
@@ -0,0 +1,161 @@
+/*
+ * CubePruning.cpp
+ *
+ *  Created on: 27 Nov 2015
+ *      Author: hieu
+ */
+
+#include "Misc.h"
+#include "Stack.h"
+#include "../Manager.h"
+#include "../../MemPool.h"
+#include "../../System.h"
+
+using namespace std;
+
+namespace Moses2
+{
+
+namespace NSCubePruningCardinalStack
+{
+
+////////////////////////////////////////////////////////////////////////
+QueueItem *QueueItem::Create(QueueItem *currItem,
+		Manager &mgr,
+		CubeEdge &edge,
+		size_t hypoIndex,
+		size_t tpIndex,
+		std::deque<QueueItem*> &queueItemRecycler)
+{
+	QueueItem *ret;
+	if (currItem) {
+		// reuse incoming queue item to create new item
+		ret = currItem;
+		ret->Init(mgr, edge, hypoIndex, tpIndex);
+	}
+	else if (!queueItemRecycler.empty()) {
+		// use item from recycle bin
+		ret = queueItemRecycler.back();
+		ret->Init(mgr, edge, hypoIndex, tpIndex);
+		queueItemRecycler.pop_back();
+	}
+	else {
+		// create new item
+		ret = new (mgr.GetPool().Allocate<QueueItem>()) QueueItem(mgr, edge, hypoIndex, tpIndex);
+	}
+
+	return ret;
+}
+
+QueueItem::QueueItem(Manager &mgr, CubeEdge &edge, size_t hypoIndex, size_t tpIndex)
+:edge(&edge)
+,hypoIndex(hypoIndex)
+,tpIndex(tpIndex)
+{
+	CreateHypothesis(mgr);
+}
+
+void QueueItem::Init(Manager &mgr, CubeEdge &edge, size_t hypoIndex, size_t tpIndex)
+{
+	this->edge = &edge;
+	this->hypoIndex = hypoIndex;
+	this->tpIndex = tpIndex;
+
+	CreateHypothesis(mgr);
+}
+
+void QueueItem::CreateHypothesis(Manager &mgr)
+{
+	const Hypothesis *prevHypo = edge->hypos[hypoIndex];
+	const TargetPhrase &tp = edge->tps[tpIndex];
+
+	//cerr << "hypoIndex=" << hypoIndex << endl;
+	//cerr << "edge.hypos=" << edge.hypos.size() << endl;
+	//cerr << prevHypo << endl;
+	//cerr << *prevHypo << endl;
+
+	hypo = Hypothesis::Create(mgr.GetSystemPool(), mgr);
+	hypo->Init(mgr, *prevHypo, edge->path, tp, edge->newBitmap, edge->estimatedScore);
+	hypo->EvaluateWhenApplied();
+}
+
+////////////////////////////////////////////////////////////////////////
+CubeEdge::CubeEdge(
+		Manager &mgr,
+		const Hypotheses &hypos,
+		const InputPath &path,
+		const TargetPhrases &tps,
+		const Bitmap &newBitmap)
+:hypos(hypos)
+,path(path)
+,tps(tps)
+,newBitmap(newBitmap)
+{
+	estimatedScore = mgr.GetEstimatedScores().CalcEstimatedScore(newBitmap);
+}
+
+std::ostream& operator<<(std::ostream &out, const CubeEdge &obj)
+{
+	out << obj.newBitmap;
+	return out;
+}
+
+bool
+CubeEdge::SetSeenPosition(const size_t x, const size_t y, SeenPositions &seenPositions) const
+{
+  //UTIL_THROW_IF2(x >= (1<<17), "Error");
+  //UTIL_THROW_IF2(y >= (1<<17), "Error");
+
+  SeenPositionItem val(this, (x<<16) + y);
+  std::pair<SeenPositions::iterator, bool> pairRet = seenPositions.insert(val);
+  return pairRet.second;
+}
+
+void CubeEdge::CreateFirst(Manager &mgr,
+		Queue &queue,
+		SeenPositions &seenPositions,
+		std::deque<QueueItem*> &queueItemRecycler)
+{
+	assert(hypos.size());
+	assert(tps.GetSize());
+
+	QueueItem *item = QueueItem::Create(NULL, mgr, *this, 0, 0, queueItemRecycler);
+	queue.push(item);
+	bool setSeen = SetSeenPosition(0, 0, seenPositions);
+	assert(setSeen);
+}
+
+void CubeEdge::CreateNext(Manager &mgr,
+		QueueItem *item,
+		Queue &queue,
+		SeenPositions &seenPositions,
+		std::deque<QueueItem*> &queueItemRecycler)
+{
+    size_t hypoIndex = item->hypoIndex;
+	size_t tpIndex = item->tpIndex;
+
+	if (hypoIndex + 1 < hypos.size() && SetSeenPosition(hypoIndex + 1, tpIndex, seenPositions)) {
+		// reuse incoming queue item to create new item
+		QueueItem *newItem = QueueItem::Create(item, mgr, *this, hypoIndex + 1, tpIndex, queueItemRecycler);
+		assert(newItem == item);
+		queue.push(newItem);
+		item = NULL;
+	}
+
+	if (tpIndex + 1 < tps.GetSize() && SetSeenPosition(hypoIndex, tpIndex + 1, seenPositions)) {
+		QueueItem *newItem = QueueItem::Create(item, mgr, *this, hypoIndex, tpIndex + 1, queueItemRecycler);
+		queue.push(newItem);
+		item = NULL;
+	}
+
+	if (item) {
+		// recycle unused queue item
+		queueItemRecycler.push_back(item);
+	}
+}
+
+}
+
+}
+
+
diff --git a/moses2/defer/CubePruningCardinalStack/Misc.h b/moses2/defer/CubePruningCardinalStack/Misc.h
new file mode 100644
index 000000000..b86c88519
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Misc.h
@@ -0,0 +1,112 @@
+/*
+ * CubePruning.h
+ *
+ *  Created on: 27 Nov 2015
+ *      Author: hieu
+ */
+#pragma once
+#include <boost/pool/pool_alloc.hpp>
+#include <boost/unordered_map.hpp>
+#include <boost/unordered_set.hpp>
+#include <vector>
+#include <queue>
+#include "../../legacy/Range.h"
+#include "../Hypothesis.h"
+#include "../../TypeDef.h"
+#include "../../Vector.h"
+#include "Stack.h"
+
+namespace Moses2
+{
+
+class Manager;
+class InputPath;
+class TargetPhrases;
+class Bitmap;
+
+namespace NSCubePruningCardinalStack
+{
+class CubeEdge;
+
+///////////////////////////////////////////
+class QueueItem
+{
+	~QueueItem(); // NOT IMPLEMENTED. Use MemPool
+public:
+	static QueueItem *Create(QueueItem *currItem,
+			Manager &mgr,
+			CubeEdge &edge,
+			size_t hypoIndex,
+			size_t tpIndex,
+			std::deque<QueueItem*> &queueItemRecycler);
+	QueueItem(Manager &mgr, CubeEdge &edge, size_t hypoIndex, size_t tpIndex);
+
+	void Init(Manager &mgr, CubeEdge &edge, size_t hypoIndex, size_t tpIndex);
+
+	CubeEdge *edge;
+	size_t hypoIndex, tpIndex;
+	Hypothesis *hypo;
+
+protected:
+	void CreateHypothesis(Manager &mgr);
+};
+
+///////////////////////////////////////////
+class QueueItemOrderer
+{
+public:
+  bool operator()(QueueItem* itemA, QueueItem* itemB) const {
+	  HypothesisFutureScoreOrderer orderer;
+	  return !orderer(itemA->hypo, itemB->hypo);
+  }
+};
+
+///////////////////////////////////////////
+class CubeEdge
+{
+  friend std::ostream& operator<<(std::ostream &, const CubeEdge &);
+
+public:
+	typedef std::priority_queue<QueueItem*,
+				std::vector<QueueItem*>,
+				QueueItemOrderer> Queue;
+
+	typedef std::pair<const CubeEdge*, int> SeenPositionItem;
+	typedef boost::unordered_set<SeenPositionItem,
+			boost::hash<SeenPositionItem>,
+			std::equal_to<SeenPositionItem>
+			> SeenPositions;
+
+	const Hypotheses &hypos;
+	const InputPath &path;
+	const TargetPhrases &tps;
+	const Bitmap &newBitmap;
+	SCORE estimatedScore;
+
+	CubeEdge(Manager &mgr,
+			const Hypotheses &hypos,
+			const InputPath &path,
+			const TargetPhrases &tps,
+			const Bitmap &newBitmap);
+
+  bool SetSeenPosition(const size_t x, const size_t y, SeenPositions &seenPositions) const;
+
+  void CreateFirst(Manager &mgr,
+		  Queue &queue,
+		  SeenPositions &seenPositions,
+		  std::deque<QueueItem*> &queueItemRecycler);
+  void CreateNext(Manager &mgr,
+		  QueueItem *item,
+		  Queue &queue,
+		  SeenPositions &seenPositions,
+		  std::deque<QueueItem*> &queueItemRecycler);
+
+protected:
+
+};
+
+}
+
+}
+
+
diff --git a/moses2/defer/CubePruningCardinalStack/Search.cpp b/moses2/defer/CubePruningCardinalStack/Search.cpp
new file mode 100644
index 000000000..d4899ae46
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Search.cpp
@@ -0,0 +1,206 @@
+/*
+ * Search.cpp
+ *
+ *  Created on: 16 Nov 2015
+ *      Author: hieu
+ */
+#include <boost/foreach.hpp>
+#include "Search.h"
+#include "Stack.h"
+#include "../Manager.h"
+#include "../Hypothesis.h"
+#include "../../InputPaths.h"
+#include "../../InputPath.h"
+#include "../../System.h"
+#include "../../Sentence.h"
+#include "../../TranslationTask.h"
+#include "../../legacy/Util2.h"
+
+using namespace std;
+
+namespace Moses2
+{
+
+namespace NSCubePruningCardinalStack
+{
+
+////////////////////////////////////////////////////////////////////////
+Search::Search(Manager &mgr)
+:Moses2::Search(mgr)
+,m_stack(mgr)
+
+,m_queue(QueueItemOrderer(), std::vector<QueueItem* >() )
+
+,m_seenPositions()
+{
+}
+
+Search::~Search()
+{
+}
+
+void Search::Decode()
+{
+	// init cue edges
+	m_cubeEdges.resize(mgr.GetInput().GetSize() + 1);
+	for (size_t i = 0; i < m_cubeEdges.size(); ++i) {
+		m_cubeEdges[i] = new (mgr.GetPool().Allocate<CubeEdges>()) CubeEdges();
+	}
+
+	const Bitmap &initBitmap = mgr.GetBitmaps().GetInitialBitmap();
+	Hypothesis *initHypo = Hypothesis::Create(mgr.GetSystemPool(), mgr);
+	initHypo->Init(mgr, mgr.GetInputPaths().GetBlank(), mgr.GetInitPhrase(), initBitmap);
+	initHypo->EmptyHypothesisState(mgr.GetInput());
+
+	m_stack.Add(initHypo, mgr.GetHypoRecycle());
+	PostDecode(0);
+
+	for (size_t stackInd = 1; stackInd < mgr.GetInput().GetSize() + 1; ++stackInd) {
+		//cerr << "stackInd=" << stackInd << endl;
+		m_stack.Clear();
+		Decode(stackInd);
+		PostDecode(stackInd);
+
+		//m_stack.DebugCounts();
+		//cerr << m_stacks << endl;
+	}
+
+}
+
+void Search::Decode(size_t stackInd)
+{
+	Recycler<Hypothesis*> &hypoRecycler  = mgr.GetHypoRecycle();
+
+	// reuse queue from previous stack. Clear it first
+	std::vector<QueueItem*> &container = Container(m_queue);
+	//cerr << "container=" << container.size() << endl;
+	BOOST_FOREACH(QueueItem *item, container) {
+		// recycle unused hypos from queue
+		Hypothesis *hypo = item->hypo;
+		hypoRecycler.Recycle(hypo);
+
+		// recycle queue item
+		m_queueItemRecycler.push_back(item);
+	}
+	container.clear();
+
+	m_seenPositions.clear();
+
+	// add top hypo from every edge into queue
+	CubeEdges &edges = *m_cubeEdges[stackInd];
+
+	BOOST_FOREACH(CubeEdge *edge, edges) {
+		//cerr << *edge << " ";
+		edge->CreateFirst(mgr, m_queue, m_seenPositions, m_queueItemRecycler);
+	}
+
+	/*
+	cerr << "edges: ";
+	boost::unordered_set<const Bitmap*> uniqueBM;
+	BOOST_FOREACH(CubeEdge *edge, edges) {
+		uniqueBM.insert(&edge->newBitmap);
+		//cerr << *edge << " ";
+	}
+	cerr << edges.size() << " " << uniqueBM.size();
+	cerr << endl;
+	*/
+
+	size_t pops = 0;
+	while (!m_queue.empty() && pops < mgr.system.popLimit) {
+		// get best hypo from queue, add to stack
+		//cerr << "queue=" << queue.size() << endl;
+		QueueItem *item = m_queue.top();
+		m_queue.pop();
+
+		CubeEdge *edge = item->edge;
+
+		// add hypo to stack
+		Hypothesis *hypo = item->hypo;
+		//cerr << "hypo=" << *hypo << " " << hypo->GetBitmap() << endl;
+		m_stack.Add(hypo, hypoRecycler);
+
+		edge->CreateNext(mgr, item, m_queue, m_seenPositions, m_queueItemRecycler);
+
+		++pops;
+	}
+
+	/*
+	// create hypo from every edge. Increase diversity
+	while (!m_queue.empty()) {
+		QueueItem *item = m_queue.top();
+		m_queue.pop();
+
+		if (item->hypoIndex == 0 && item->tpIndex == 0) {
+			CubeEdge &edge = item->edge;
+
+			// add hypo to stack
+			Hypothesis *hypo = item->hypo;
+			//cerr << "hypo=" << *hypo << " " << hypo->GetBitmap() << endl;
+			m_stacks.Add(hypo, mgr.GetHypoRecycle());
+		}
+	}
+	*/
+}
+
+void Search::PostDecode(size_t stackInd)
+{
+  MemPool &pool = mgr.GetPool();
+
+  Stack::SortedHypos sortedHypos = m_stack.GetSortedAndPruneHypos(mgr);
+
+  BOOST_FOREACH(const Stack::SortedHypos::value_type &val, sortedHypos) {
+	  const Bitmap &hypoBitmap = *val.first.first;
+	  size_t hypoEndPos = val.first.second;
+	  //cerr << "key=" << hypoBitmap << " " << hypoEndPos << endl;
+
+	  // create edges to next hypos from existing hypos
+	  const InputPaths &paths = mgr.GetInputPaths();
+
+	  BOOST_FOREACH(const InputPath *path, paths) {
+  		const Range &pathRange = path->range;
+  		//cerr << "pathRange=" << pathRange << endl;
+
+  		if (!path->IsUsed()) {
+  			continue;
+  		}
+  		if (!CanExtend(hypoBitmap, hypoEndPos, pathRange)) {
+  			continue;
+  		}
+
+  		const Bitmap &newBitmap = mgr.GetBitmaps().GetBitmap(hypoBitmap, pathRange);
+  		size_t numWords = newBitmap.GetNumWordsCovered();
+
+  		CubeEdges &edges = *m_cubeEdges[numWords];
+
+		// sort hypo for a particular bitmap and hypoEndPos
+  		Hypotheses &sortedHypos = *val.second;
+
+  	    size_t numPt = mgr.system.mappings.size();
+  	    for (size_t i = 0; i < numPt; ++i) {
+  	    	const TargetPhrases *tps = path->targetPhrases[i];
+  			if (tps && tps->GetSize()) {
+  		  		CubeEdge *edge = new (pool.Allocate<CubeEdge>()) CubeEdge(mgr, sortedHypos, *path, *tps, newBitmap);
+  		  		edges.push_back(edge);
+  			}
+  		}
+  	  }
+  }
+
+}
+
+const Hypothesis *Search::GetBestHypo() const
+{
+	std::vector<const Hypothesis*> sortedHypos = m_stack.GetBestHypos(1);
+
+	const Hypothesis *best = NULL;
+	if (sortedHypos.size()) {
+		best = sortedHypos[0];
+	}
+	return best;
+}
+
+}
+
+}
+
+
diff --git a/moses2/defer/CubePruningCardinalStack/Search.h b/moses2/defer/CubePruningCardinalStack/Search.h
new file mode 100644
index 000000000..e772926a2
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Search.h
@@ -0,0 +1,57 @@
+/*
+ * Search.h
+ *
+ *  Created on: 16 Nov 2015
+ *      Author: hieu
+ */
+
+#pragma once
+#include <boost/pool/pool_alloc.hpp>
+#include "../Search.h"
+#include "Misc.h"
+#include "Stack.h"
+#include "../../legacy/Range.h"
+
+namespace Moses2
+{
+
+class Bitmap;
+class Hypothesis;
+class InputPath;
+class TargetPhrases;
+
+namespace NSCubePruningCardinalStack
+{
+
+class Search : public Moses2::Search
+{
+public:
+	Search(Manager &mgr);
+	virtual ~Search();
+
+	virtual void Decode();
+	const Hypothesis *GetBestHypo() const;
+
+protected:
+	Stack m_stack;
+
+	CubeEdge::Queue m_queue;
+	CubeEdge::SeenPositions m_seenPositions;
+
+	// CUBE PRUNING VARIABLES
+	// setup
+	typedef std::vector<CubeEdge*> CubeEdges;
+	std::vector<CubeEdges*> m_cubeEdges;
+
+	std::deque<QueueItem*> m_queueItemRecycler;
+
+	// CUBE PRUNING
+	// decoding
+	void Decode(size_t stackInd);
+	void PostDecode(size_t stackInd);
+};
+
+}
+
+}
+
diff --git a/moses2/defer/CubePruningCardinalStack/Stack.cpp b/moses2/defer/CubePruningCardinalStack/Stack.cpp
new file mode 100644
index 000000000..0c296d8ca
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Stack.cpp
@@ -0,0 +1,200 @@
+/*
+ * Stack.cpp
+ *
+ *  Created on: 24 Oct 2015
+ *      Author: hieu
+ */
+#include <algorithm>
+#include <boost/foreach.hpp>
+#include "Stack.h"
+#include "../Hypothesis.h"
+#include "../Manager.h"
+#include "../../Scores.h"
+#include "../../System.h"
+
+using namespace std;
+
+namespace Moses2
+{
+
+namespace NSCubePruningCardinalStack
+{
+
+///////////////////////////////////////////////////////////////
+Stack::Stack(const Manager &mgr)
+:m_mgr(mgr)
+,m_coll()
+{
+}
+
+Stack::~Stack() {
+	// TODO Auto-generated destructor stub
+}
+
+void Stack::Add(const Hypothesis *hypo, Recycler<Hypothesis*> &hypoRecycle)
+{
+  std::pair<_HCType::iterator, bool> addRet = m_coll.insert(hypo);
+
+  // CHECK RECOMBINATION
+  if (addRet.second) {
+	// equiv hypo doesn't exists
+  }
+  else {
+	  const Hypothesis *hypoExisting = *addRet.first;
+	  if (hypo->GetScores().GetTotalScore() > hypoExisting->GetScores().GetTotalScore()) {
+		  // incoming hypo is better than the one we have
+		  const Hypothesis *const &hypoExisting1 = *addRet.first;
+		  const Hypothesis *&hypoExisting2 = const_cast<const Hypothesis *&>(hypoExisting1);
+		  hypoExisting2 = hypo;
+
+		  Hypothesis *hypoToBeDeleted = const_cast<Hypothesis*>(hypoExisting);
+		  hypoRecycle.Recycle(hypoToBeDeleted);
+	  }
+	  else {
+		  // already storing the best hypo. discard incoming hypo
+		  Hypothesis *hypoToBeDeleted = const_cast<Hypothesis*>(hypo);
+		  hypoRecycle.Recycle(hypoToBeDeleted);
+	  }
+  }
+}
+
+std::vector<const Hypothesis*> Stack::GetBestHypos(size_t num) const
+{
+  std::vector<const Hypothesis*> ret;
+  ret.insert(ret.end(), m_coll.begin(), m_coll.end());
+
+  std::vector<const Hypothesis*>::iterator iterMiddle;
+  iterMiddle = (num == 0 || ret.size() < num)
+			   ? ret.end()
+			   : ret.begin()+num;
+
+  std::partial_sort(ret.begin(), iterMiddle, ret.end(),
+		  HypothesisFutureScoreOrderer());
+
+  return ret;
+}
+
+size_t Stack::GetHypoSize() const
+{
+	return m_coll.size();
+}
+
+void Stack::Clear()
+{
+
+	m_coll.clear();
+}
+
+Stack::SortedHypos Stack::GetSortedAndPruneHypos(const Manager &mgr) const
+{
+  SortedHypos ret;
+
+  MemPool &pool = mgr.GetPool();
+
+  // prune and sort
+  Hypotheses *allHypos = new (pool.Allocate<Hypotheses>()) Hypotheses(pool, GetHypoSize());
+  size_t i = 0;
+  BOOST_FOREACH(const Hypothesis *hypo, m_coll) {
+	  (*allHypos)[i++] = hypo;
+  }
+  SortAndPruneHypos(mgr, *allHypos);
+
+  // divide hypos by [bitmap, last end pos]
+  BOOST_FOREACH(const Hypothesis *hypo, *allHypos) {
+	  HypoCoverage key(&hypo->GetBitmap(), hypo->GetInputPath().range.GetEndPos());
+
+	  Hypotheses *hypos;
+	  SortedHypos::iterator iter;
+	  iter = ret.find(key);
+	  if (iter == ret.end()) {
+		  hypos = new (pool.Allocate<Hypotheses>()) Hypotheses(pool);
+		  ret[key] = hypos;
+	  }
+	  else {
+		  hypos = iter->second;
+	  }
+	  hypos->push_back(hypo);
+  }
+
+  return ret;
+}
+
+
+//Stack::SortedHypos Stack::GetSortedAndPruneHypos(const Manager &mgr) const
+//{
+//  SortedHypos ret;
+//
+//  MemPool &pool = mgr.GetPool();
+//
+//  // divide hypos by [bitmap, last end pos]
+//  BOOST_FOREACH(const Hypothesis *hypo, m_coll) {
+//	  HypoCoverage key(&hypo->GetBitmap(), hypo->GetInputPath().range.GetEndPos());
+//
+//	  Hypotheses *hypos;
+//	  SortedHypos::iterator iter;
+//	  iter = ret.find(key);
+//	  if (iter == ret.end()) {
+//		  hypos = new (pool.Allocate<Hypotheses>()) Hypotheses(pool);
+//		  ret[key] = hypos;
+//	  }
+//	  else {
+//		  hypos = iter->second;
+//	  }
+//	  hypos->push_back(hypo);
+//  }
+//
+//  // put into real return variable and sort
+//  BOOST_FOREACH(SortedHypos::value_type &val, ret) {
+//	  Hypotheses &hypos = *val.second;
+//	  SortAndPruneHypos(mgr, hypos);
+//  }
+//
+//  return ret;
+//}
+
+void Stack::SortAndPruneHypos(const Manager &mgr, Hypotheses &hypos) const
+{
+  size_t stackSize = mgr.system.stackSize;
+  Recycler<Hypothesis*> &recycler = mgr.GetHypoRecycle();
+
+  /*
+  cerr << "UNSORTED hypos:" << endl;
+  for (size_t i = 0; i < hypos.size(); ++i) {
+	  const Hypothesis *hypo = hypos[i];
+	  cerr << *hypo << endl;
+  }
+  cerr << endl;
+  */
+  Hypotheses::iterator iterMiddle;
+  iterMiddle = (stackSize == 0 || hypos.size() < stackSize)
+			   ? hypos.end()
+			   : hypos.begin() + stackSize;
+
+  std::partial_sort(hypos.begin(), iterMiddle, hypos.end(),
+		  HypothesisFutureScoreOrderer());
+
+  // prune
+  if (stackSize && hypos.size() > stackSize) {
+	  for (size_t i = stackSize; i < hypos.size(); ++i) {
+		  Hypothesis *hypo = const_cast<Hypothesis*>(hypos[i]);
+		  recycler.Recycle(hypo);
+	  }
+	  hypos.resize(stackSize);
+  }
+
+  /*
+  cerr << "sorted hypos:" << endl;
+  for (size_t i = 0; i < hypos.size(); ++i) {
+	  const Hypothesis *hypo = hypos[i];
+	  cerr << hypo << " " << *hypo << endl;
+  }
+  cerr << endl;
+  */
+
+}
+
+
+}
+
+}
+
diff --git a/moses2/defer/CubePruningCardinalStack/Stack.h b/moses2/defer/CubePruningCardinalStack/Stack.h
new file mode 100644
index 000000000..d6ae80577
--- /dev/null
+++ b/moses2/defer/CubePruningCardinalStack/Stack.h
@@ -0,0 +1,68 @@
+/*
+ * Stack.h
+ *
+ *  Created on: 24 Oct 2015
+ *      Author: hieu
+ */
+#pragma once
+#include <boost/unordered_map.hpp>
+#include <boost/unordered_set.hpp>
+#include <deque>
+#include "../Hypothesis.h"
+#include "../../TypeDef.h"
+#include "../../Vector.h"
+#include "../../MemPool.h"
+#include "../../Recycler.h"
+#include "../../legacy/Util2.h"
+
+namespace Moses2
+{
+
+class Manager;
+
+namespace NSCubePruningCardinalStack
+{
+typedef Vector<const Hypothesis*>  Hypotheses;
+
+
+/////////////////////////////////////////////
+class Stack {
+protected:
+	typedef boost::unordered_set<const Hypothesis*,
+			  UnorderedComparer<Hypothesis>,
+			  UnorderedComparer<Hypothesis>
+			   > _HCType;
+
+public:
+	typedef std::pair<const Bitmap*, size_t> HypoCoverage;
+	typedef boost::unordered_map<HypoCoverage, Hypotheses*> SortedHypos;
+
+	Stack(const Manager &mgr);
+	virtual ~Stack();
+
+	size_t GetHypoSize() const;
+
+	_HCType &GetColl()
+	{ return m_coll; }
+	const _HCType &GetColl() const
+	{ return m_coll; }
+
+	void Add(const Hypothesis *hypo, Recycler<Hypothesis*> &hypoRecycle);
+
+	std::vector<const Hypothesis*> GetBestHypos(size_t num) const;
+	void Clear();
+
+	SortedHypos GetSortedAndPruneHypos(const Manager &mgr) const;
+	void SortAndPruneHypos(const Manager &mgr, Hypotheses &hypos) const;
+
+protected:
+	const Manager &m_mgr;
+	_HCType m_coll;
+
+};
+
+}
+
+}
+
+