///////////////////////////////////////////////////////////////////////////////
// //
// This file is part of ModelBlocks. Copyright 2009, ModelBlocks developers. //
// //
// ModelBlocks is free software: you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation, either version 3 of the License, or //
// (at your option) any later version. //
// //
// ModelBlocks is distributed in the hope that it will be useful, //
// but WITHOUT ANY WARRANTY; without even the implied warranty of //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
// GNU General Public License for more details. //
// //
// You should have received a copy of the GNU General Public License //
// along with ModelBlocks. If not, see . //
// //
// ModelBlocks developers designate this particular file as subject to //
// the "Moses" exception as provided by ModelBlocks developers in //
// the LICENSE file that accompanies this code. //
// //
///////////////////////////////////////////////////////////////////////////////
#ifndef _NL_BEAM__
#define _NL_BEAM__
#include "nl-heap.h"
#include "nl-hash.h"
//#include
//#include
#include
////////////////////////////////////////////////////////////////////////////////
/*
template
class SafePtr {
private:
R* pr;
static R rDummy;
public:
SafePtr ( ) : pr(NULL) { }
SafePtr ( R& r ) : pr(&r) { }
bool operator== ( const SafePtr& spr ) const { return(pr==spr.pr); }
bool operator!= ( const SafePtr& spr ) const { return(!(pr==spr.pr)); }
R& set ( ) { assert(pr); return (pr!=NULL) ? *pr : rDummy; }
const R& get ( ) const { return (pr!=NULL) ? *pr : rDummy; }
};
template
R SafePtr::rDummy = R();
template
class ScoredPtr : public SafePtr {
public:
S scr;
ScoredPtr ( ) : SafePtr() , scr() { }
ScoredPtr ( S s, R& r ) : SafePtr(r), scr(s) { }
S& setScore() { return scr; }
S getScore() const { return scr; }
};
*/
////////////////////////////////////////////////////////////////////////////////
template
class ScoredIter : public C::iterator {
private:
//static C cDummy;
S s;
public:
ScoredIter ( ) : C::iterator(0,0), s() { }
ScoredIter ( S s1, const typename C::iterator& i1 ) : C::iterator(i1), s(s1) { }
//ScoredIter ( ) : C::iterator(cDummy.end()), s() { }
S& setScore() { return s; }
S getScore() const { return s; }
};
//template C ScoredIter::cDummy;
////////////////////////////////////////////////////////////////////////////////
template
class Beam {
public:
typedef std::pair ID;
typedef std::pair > KID;
typedef std::tr1::unordered_multimap,SimpleHashEqual > BeamMap;
typedef MinHeap > BeamHeap;
private:
BeamMap mkid;
BeamHeap hspkid;
public:
// Constructor methods...
Beam ( int i ) : mkid(2*i), hspkid(i) { for(int j=0;j(s,mkid.insert(KID(k,ID(i,d)))); }
// Extraction methods...
const ScoredIter& getMin ( ) const { return hspkid.getMin(); }
const ScoredIter& get ( int i ) const { return hspkid.get(i); }
void sort ( SafeArray1D,std::pair,S> >& ) ;
void write(FILE *pf){
/* for (typename BeamMap::const_iterator i = mkid.begin(); i != mkid.end(); i++){
i->first.write(pf);
fprintf(pf, " %d ", i->second.first);
// i->second.second.write(pf);
fprintf(pf, "\n");
}
*/
for(int i=0; ifirst.write(pf);
fprintf(pf, "\n");
}
}
};
template
bool Beam::tryAdd ( const K& k, const D& d, const S& s ) {
// If score good enough to get into beam...
if ( s > hspkid.getMin().getScore() ) {
typename BeamMap::const_iterator i = mkid.find(k);
// If key in beam already...
if ( i != mkid.end() ) {
// If same key in beam now has better score...
if ( s > hspkid.get(i->second.first).getScore() ) {
// Update score (and data associated with that score)...
hspkid.set(i->second.first).setScore() = s;
hspkid.set(i->second.first)->second.second = d;
// Update heap...
int iStart = i->second.first; int iDeeper = hspkid.fixIncr(iStart);
// Fix pointers in hash...
for ( int j = iDeeper+1; j>=iStart+1; j/=2 ) hspkid.set(j-1)->second.first = j-1;
}
}
// If x not in beam already, add...
else {
// Remove min from map (via pointer in heap)...
mkid.erase ( hspkid.getMin() );
// Insert new entry at min...
set(0,k,d,s);
// Update heap...
int iStart = 0; int iDeeper = hspkid.fixIncr(iStart);
// Fix pointers in hash...
for ( int j = iDeeper+1; j>=iStart+1; j/=2 ) hspkid.set(j-1)->second.first = j-1;
}
}
return ( LogProb() != hspkid.getMin().getScore() ); // true = beam full, false = beam still has gaps
}
template
void Beam::sort ( SafeArray1D,std::pair,S> >& akdsOut ) {
for ( int i=0; ifirst; // copy min key to output key.
akdsOut.set(hspkid.getSize()-i-1).first.second = hspkid.getMin()->second.second; // copy min dat to output dat.
akdsOut.set(hspkid.getSize()-i-1).second = hspkid.getMin().getScore(); // copy min scr to output scr.
hspkid.setMin().setScore() = LogProb(1); // get min out of the way.
hspkid.fixIncr(0); // repair heap.
}
}
////////////////////////////////////////////////////////////////////////////////
#endif //_NL_BEAM__