Spaces:

suricodes
/

hindi-sindhi-docker

Paused

hindi-sindhi-docker / mosesdecoder /phrase-extract /PhraseOrientation.cpp

Upload folder using huggingface_hub

fd49381 verified about 2 years ago

16.9 kB

/***********************************************************************
 Moses - statistical machine translation system
 Copyright (C) 2006-2011 University of Edinburgh
 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.
 This library 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
 Lesser General Public License for more details.
 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
***********************************************************************/

#include "PhraseOrientation.h"

#include <iostream>
#include <sstream>
#include <limits>
#include <cassert>

#include <boost/assign/list_of.hpp>

namespace MosesTraining
{

std::vector<float> PhraseOrientation::m_l2rOrientationPriorCounts = boost::assign::list_of(0)(0)(0)(0)(0);
std::vector<float> PhraseOrientation::m_r2lOrientationPriorCounts = boost::assign::list_of(0)(0)(0)(0)(0);

PhraseOrientation::PhraseOrientation(int sourceSize,
                                     int targetSize,
                                     const Alignment &alignment)
  : m_countF(sourceSize)
  , m_countE(targetSize)
{
  // prepare data structures for alignments
  std::vector<std::vector<int> > alignedToS;
  for(int i=0; i<m_countF; ++i) {
    std::vector< int > dummy;
    alignedToS.push_back(dummy);
  }
  for(int i=0; i<m_countE; ++i) {
    std::vector< int > dummy;
    m_alignedToT.push_back(dummy);
  }
  std::vector<int> alignedCountS(m_countF,0);

  for (Alignment::const_iterator a=alignment.begin(); a!=alignment.end(); ++a) {
    alignedToS[a->first].push_back(a->second);
    alignedCountS[a->first]++;
    m_alignedToT[a->second].push_back(a->first);
  }

  Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
}


PhraseOrientation::PhraseOrientation(int sourceSize,
                                     int targetSize,
                                     const Moses::AlignmentInfo &alignTerm,
                                     const Moses::AlignmentInfo &alignNonTerm)
  : m_countF(sourceSize)
  , m_countE(targetSize)
{
  // prepare data structures for alignments
  std::vector<std::vector<int> > alignedToS;
  for(int i=0; i<m_countF; ++i) {
    std::vector< int > dummy;
    alignedToS.push_back(dummy);
  }
  for(int i=0; i<m_countE; ++i) {
    std::vector< int > dummy;
    m_alignedToT.push_back(dummy);
  }
  std::vector<int> alignedCountS(m_countF,0);

  for (Moses::AlignmentInfo::const_iterator it=alignTerm.begin();
       it!=alignTerm.end(); ++it) {
    alignedToS[it->first].push_back(it->second);
    alignedCountS[it->first]++;
    m_alignedToT[it->second].push_back(it->first);
  }

  for (Moses::AlignmentInfo::const_iterator it=alignNonTerm.begin();
       it!=alignNonTerm.end(); ++it) {
    alignedToS[it->first].push_back(it->second);
    alignedCountS[it->first]++;
    m_alignedToT[it->second].push_back(it->first);
  }

  Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
}

PhraseOrientation::PhraseOrientation(int sourceSize,
                                     int targetSize,
                                     const std::vector<std::vector<int> > &alignedToT,
                                     const std::vector<std::vector<int> > &alignedToS,
                                     const std::vector<int> &alignedCountS)
  : m_countF(sourceSize)
  , m_countE(targetSize)
  , m_alignedToT(alignedToT)
{
  Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
}


void PhraseOrientation::Init(int sourceSize,
                             int targetSize,
                             const std::vector<std::vector<int> > &alignedToT,
                             const std::vector<std::vector<int> > &alignedToS,
                             const std::vector<int> &alignedCountS)
{
  for (int startF=0; startF<m_countF; ++startF) {
    for (int endF=startF; endF<m_countF; ++endF) {

      int minE = std::numeric_limits<int>::max();
      int maxE = -1;
      for (int fi=startF; fi<=endF; ++fi) {
        for (size_t i=0; i<alignedToS[fi].size(); ++i) {
          int ei = alignedToS[fi][i];
          if (ei<minE) {
            minE = ei;
          }
          if (ei>maxE) {
            maxE = ei;
          }
        }
      }

      m_minAndMaxAlignedToSourceSpan[ std::pair<int,int>(startF,endF) ] = std::pair<int,int>(minE,maxE);
    }
  }

  // check alignments for target phrase startE...endE
  // loop over continuous phrases which are compatible with the word alignments
  for (int startE=0; startE<m_countE; ++startE) {
    for (int endE=startE; endE<m_countE; ++endE) {

      int minF = std::numeric_limits<int>::max();
      int maxF = -1;
      std::vector< int > usedF = alignedCountS;
      for (int ei=startE; ei<=endE; ++ei) {
        for (size_t i=0; i<alignedToT[ei].size(); ++i) {
          int fi = alignedToT[ei][i];
          if (fi<minF) {
            minF = fi;
          }
          if (fi>maxF) {
            maxF = fi;
          }
          usedF[fi]--;
        }
      }

      m_minAndMaxAlignedToTargetSpan[ std::pair<int,int>(startE,endE) ] = std::pair<int,int>(minF,maxF);

      if (maxF >= 0) { // aligned to any source words at all

        // check if source words are aligned to out of bounds target words
        bool out_of_bounds = false;
        for (int fi=minF; fi<=maxF && !out_of_bounds; ++fi)
          if (usedF[fi]>0) {
            // cout << "out of bounds: " << fi << "\n";
            out_of_bounds = true;
          }

        // cout << "doing if for ( " << minF << "-" << maxF << ", " << startE << "," << endE << ")\n";
        if (!out_of_bounds) {
          // start point of source phrase may retreat over unaligned
          for (int startF=minF;
               (startF>=0 &&
                (startF==minF || alignedCountS[startF]==0)); // unaligned
               startF--) {
            // end point of source phrase may advance over unaligned
            for (int endF=maxF;
                 (endF<m_countF &&
                  (endF==maxF || alignedCountS[endF]==0)); // unaligned
                 endF++) { // at this point we have extracted a phrase

              InsertPhraseVertices(m_topLeft, m_topRight, m_bottomLeft, m_bottomRight,
                                   startF, startE, endF, endE);
            }
          }
        }
      }
    }
  }
}


void PhraseOrientation::InsertVertex( HSentenceVertices & corners, int x, int y )
{
  std::set<int> tmp;
  tmp.insert(x);
  std::pair< HSentenceVertices::iterator, bool > ret = corners.insert( std::pair<int, std::set<int> > (y, tmp) );
  if (ret.second == false) {
    ret.first->second.insert(x);
  }
}


void PhraseOrientation::InsertPhraseVertices(HSentenceVertices & topLeft,
    HSentenceVertices & topRight,
    HSentenceVertices & bottomLeft,
    HSentenceVertices & bottomRight,
    int startF, int startE, int endF, int endE)
{

  InsertVertex(topLeft, startF, startE);
  InsertVertex(topRight, endF, startE);
  InsertVertex(bottomLeft, startF, endE);
  InsertVertex(bottomRight, endF, endE);
}


const std::string PhraseOrientation::GetOrientationInfoString(int startF, int endF, REO_DIR direction) const
{
  boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator foundMinMax
  = m_minAndMaxAlignedToSourceSpan.find( std::pair<int,int>(startF,endF) );

  if ( foundMinMax != m_minAndMaxAlignedToSourceSpan.end() ) {
    int startE = (foundMinMax->second).first;
    int endE   = (foundMinMax->second).second;
//    std::cerr << "Phrase orientation for"
//      << " startF=" << startF
//      << " endF="   << endF
//      << " startE=" << startE
//      << " endE="   << endE
//      << std::endl;
    return GetOrientationInfoString(startF, startE, endF, endE, direction);
  } else {
    std::cerr << "PhraseOrientation::GetOrientationInfoString(): Error: not able to determine phrase orientation" << std::endl;
    std::exit(1);
  }
}


const std::string PhraseOrientation::GetOrientationInfoString(int startF, int startE, int endF, int endE, REO_DIR direction) const
{
  REO_CLASS hierPrevOrient=REO_CLASS_UNKNOWN, hierNextOrient=REO_CLASS_UNKNOWN;

  if ( direction == REO_DIR_L2R || direction == REO_DIR_BIDIR )
    hierPrevOrient = GetOrientationInfo(startF, startE, endF, endE, REO_DIR_L2R);

  if ( direction == REO_DIR_R2L || direction == REO_DIR_BIDIR )
    hierNextOrient = GetOrientationInfo(startF, startE, endF, endE, REO_DIR_R2L);

  switch (direction) {
  case REO_DIR_L2R:
    return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR);
    break;
  case REO_DIR_R2L:
    return GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
    break;
  case REO_DIR_BIDIR:
    return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR) + " " + GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
    break;
  default:
    return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR) + " " + GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
    break;
  }
  return "PhraseOrientationERROR";
}


PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientationInfo(int startF, int endF, REO_DIR direction) const
{
  boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator foundMinMax
  = m_minAndMaxAlignedToSourceSpan.find( std::pair<int,int>(startF,endF) );

  if ( foundMinMax != m_minAndMaxAlignedToSourceSpan.end() ) {
    int startE = (foundMinMax->second).first;
    int endE   = (foundMinMax->second).second;
//    std::cerr << "Phrase orientation for"
//      << " startF=" << startF
//      << " endF="   << endF
//      << " startE=" << startE
//      << " endE="   << endE
//      << std::endl;
    return GetOrientationInfo(startF, startE, endF, endE, direction);
  } else {
    std::cerr << "PhraseOrientation::GetOrientationInfo(): Error: not able to determine phrase orientation" << std::endl;
    std::exit(1);
  }
}


PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientationInfo(int startF, int startE, int endF, int endE, REO_DIR direction) const
{
  if ( direction != REO_DIR_L2R && direction != REO_DIR_R2L ) {
    std::cerr << "PhraseOrientation::GetOrientationInfo(): Error: direction should be either L2R or R2L" << std::endl;
    std::exit(1);
  }

  if ( direction == REO_DIR_L2R )
    return GetOrientHierModel(REO_MODEL_TYPE_MSLR,
                              startF, endF, startE, endE, m_countF-1, 0, 0, 1,
                              &ge, &le,
                              m_bottomRight, m_bottomLeft);

  if ( direction == REO_DIR_R2L )
    return GetOrientHierModel(REO_MODEL_TYPE_MSLR,
                              endF, startF, endE, startE, 0, m_countF-1, m_countE-1, -1,
                              &le, &ge,
                              m_topLeft, m_topRight);

  return REO_CLASS_UNKNOWN;
}


// to be called with countF-1 instead of countF
PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientHierModel(REO_MODEL_TYPE modelType,
    int startF, int endF, int startE, int endE, int countF, int zeroF, int zeroE, int unit,
    bool (*ge)(int, int), bool (*le)(int, int),
    const HSentenceVertices & bottomRight, const HSentenceVertices & bottomLeft) const
{
  bool leftSourceSpanIsAligned = ( (startF != zeroF) && SourceSpanIsAligned(zeroF,startF-unit) );
  bool topTargetSpanIsAligned  = ( (startE != zeroE) && TargetSpanIsAligned(zeroE,startE-unit) );

  if (!topTargetSpanIsAligned && !leftSourceSpanIsAligned)
    return REO_CLASS_LEFT;

  HSentenceVertices::const_iterator it;

  if (//(connectedLeftTop && !connectedRightTop) ||
    ((it = bottomRight.find(startE - unit)) != bottomRight.end() &&
     it->second.find(startF-unit) != it->second.end()))
    return REO_CLASS_LEFT;

  if (modelType == REO_MODEL_TYPE_MONO)
    return REO_CLASS_UNKNOWN;

  if (//(!connectedLeftTop &&  connectedRightTop) ||
    ((it = bottomLeft.find(startE - unit)) != bottomLeft.end() &&
     it->second.find(endF + unit) != it->second.end()))
    return REO_CLASS_RIGHT;

  if (modelType == REO_MODEL_TYPE_MSD)
    return REO_CLASS_UNKNOWN;

  for (int indexF=startF-2*unit; (*ge)(indexF, zeroF); indexF=indexF-unit) {
    if ((it = bottomRight.find(startE - unit)) != bottomRight.end() &&
        it->second.find(indexF) != it->second.end())
      return REO_CLASS_DLEFT;
  }

  for (int indexF=endF+2*unit; (*le)(indexF, countF); indexF=indexF+unit) {
    if ((it = bottomLeft.find(startE - unit)) != bottomLeft.end() &&
        it->second.find(indexF) != it->second.end())
      return REO_CLASS_DRIGHT;
  }

  return REO_CLASS_UNKNOWN;
}

bool PhraseOrientation::SourceSpanIsAligned(int index1, int index2) const
{
  return SpanIsAligned(index1, index2, m_minAndMaxAlignedToSourceSpan);
}

bool PhraseOrientation::TargetSpanIsAligned(int index1, int index2) const
{
  return SpanIsAligned(index1, index2, m_minAndMaxAlignedToTargetSpan);
}

bool PhraseOrientation::SpanIsAligned(int index1, int index2, const boost::unordered_map< std::pair<int,int> , std::pair<int,int> > &minAndMaxAligned) const
{
  boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator itMinAndMaxAligned =
    minAndMaxAligned.find(std::pair<int,int>(std::min(index1,index2),std::max(index1,index2)));

  if (itMinAndMaxAligned == minAndMaxAligned.end()) {
    std::cerr << "PhraseOrientation::SourceSpanIsAligned(): Error" << std::endl;
    std::exit(1);
  } else {
    if (itMinAndMaxAligned->second.first == std::numeric_limits<int>::max()) {
      return false;
    }
  }
  return true;
}


const std::string PhraseOrientation::GetOrientationString(const REO_CLASS orient, const REO_MODEL_TYPE modelType)
{
  std::ostringstream oss;
  WriteOrientation(oss, orient, modelType);
  return oss.str();
}


void PhraseOrientation::WriteOrientation(std::ostream& out, const REO_CLASS orient, const REO_MODEL_TYPE modelType)
{
  switch(orient) {
  case REO_CLASS_LEFT:
    out << "mono";
    break;
  case REO_CLASS_RIGHT:
    out << "swap";
    break;
  case REO_CLASS_DLEFT:
    out << "dleft";
    break;
  case REO_CLASS_DRIGHT:
    out << "dright";
    break;
  case REO_CLASS_UNKNOWN:
    switch(modelType) {
    case REO_MODEL_TYPE_MONO:
      out << "nomono";
      break;
    case REO_MODEL_TYPE_MSD:
      out << "other";
      break;
    case REO_MODEL_TYPE_MSLR:
      out << "dleft";
      break;
    }
    break;
  }
}


bool PhraseOrientation::IsAligned(int fi, int ei) const
{
  if (ei == -1 && fi == -1)
    return true;

  if (ei <= -1 || fi <= -1)
    return false;

  if (ei == m_countE && fi == m_countF)
    return true;

  if (ei >= m_countE || fi >= m_countF)
    return false;

  for (size_t i=0; i<m_alignedToT[ei].size(); ++i)
    if (m_alignedToT[ei][i] == fi)
      return true;

  return false;
}


void PhraseOrientation::IncrementPriorCount(REO_DIR direction, REO_CLASS orient, float increment)
{
  assert(direction==REO_DIR_L2R || direction==REO_DIR_R2L);
  if (direction == REO_DIR_L2R) {
    m_l2rOrientationPriorCounts[orient] += increment;
  } else if (direction == REO_DIR_R2L) {
    m_r2lOrientationPriorCounts[orient] += increment;
  }
}


void PhraseOrientation::WritePriorCounts(std::ostream& out, const REO_MODEL_TYPE modelType)
{
  std::map<std::string,float> l2rOrientationPriorCountsMap;
  std::map<std::string,float> r2lOrientationPriorCountsMap;
  for (int orient=0; orient<=REO_CLASS_UNKNOWN; ++orient) {
    l2rOrientationPriorCountsMap[GetOrientationString((REO_CLASS)orient, modelType)] += m_l2rOrientationPriorCounts[orient];
  }
  for (int orient=0; orient<=REO_CLASS_UNKNOWN; ++orient) {
    r2lOrientationPriorCountsMap[GetOrientationString((REO_CLASS)orient, modelType)] += m_r2lOrientationPriorCounts[orient];
  }
  for (std::map<std::string,float>::const_iterator l2rOrientationPriorCountsMapIt = l2rOrientationPriorCountsMap.begin();
       l2rOrientationPriorCountsMapIt != l2rOrientationPriorCountsMap.end(); ++l2rOrientationPriorCountsMapIt) {
    out << "L2R_" << l2rOrientationPriorCountsMapIt->first << " " << l2rOrientationPriorCountsMapIt->second << std::endl;
  }
  for (std::map<std::string,float>::const_iterator r2lOrientationPriorCountsMapIt = r2lOrientationPriorCountsMap.begin();
       r2lOrientationPriorCountsMapIt != r2lOrientationPriorCountsMap.end(); ++r2lOrientationPriorCountsMapIt) {
    out << "R2L_" << r2lOrientationPriorCountsMapIt->first << " " << r2lOrientationPriorCountsMapIt->second << std::endl;
  }
}

}  // namespace MosesTraining

	/***********************************************************************
	Moses - statistical machine translation system
	Copyright (C) 2006-2011 University of Edinburgh

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library 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
	Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with this library; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	***********************************************************************/

	#include "PhraseOrientation.h"

	#include <iostream>
	#include <sstream>
	#include <limits>
	#include <cassert>

	#include <boost/assign/list_of.hpp>

	namespace MosesTraining
	{

	std::vector<float> PhraseOrientation::m_l2rOrientationPriorCounts = boost::assign::list_of(0)(0)(0)(0)(0);
	std::vector<float> PhraseOrientation::m_r2lOrientationPriorCounts = boost::assign::list_of(0)(0)(0)(0)(0);

	PhraseOrientation::PhraseOrientation(int sourceSize,
	int targetSize,
	const Alignment &alignment)
	: m_countF(sourceSize)
	, m_countE(targetSize)
	{
	// prepare data structures for alignments
	std::vector<std::vector<int> > alignedToS;
	for(int i=0; i<m_countF; ++i) {
	std::vector< int > dummy;
	alignedToS.push_back(dummy);
	}
	for(int i=0; i<m_countE; ++i) {
	std::vector< int > dummy;
	m_alignedToT.push_back(dummy);
	}
	std::vector<int> alignedCountS(m_countF,0);

	for (Alignment::const_iterator a=alignment.begin(); a!=alignment.end(); ++a) {
	alignedToS[a->first].push_back(a->second);
	alignedCountS[a->first]++;
	m_alignedToT[a->second].push_back(a->first);
	}

	Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
	}


	PhraseOrientation::PhraseOrientation(int sourceSize,
	int targetSize,
	const Moses::AlignmentInfo &alignTerm,
	const Moses::AlignmentInfo &alignNonTerm)
	: m_countF(sourceSize)
	, m_countE(targetSize)
	{
	// prepare data structures for alignments
	std::vector<std::vector<int> > alignedToS;
	for(int i=0; i<m_countF; ++i) {
	std::vector< int > dummy;
	alignedToS.push_back(dummy);
	}
	for(int i=0; i<m_countE; ++i) {
	std::vector< int > dummy;
	m_alignedToT.push_back(dummy);
	}
	std::vector<int> alignedCountS(m_countF,0);

	for (Moses::AlignmentInfo::const_iterator it=alignTerm.begin();
	it!=alignTerm.end(); ++it) {
	alignedToS[it->first].push_back(it->second);
	alignedCountS[it->first]++;
	m_alignedToT[it->second].push_back(it->first);
	}

	for (Moses::AlignmentInfo::const_iterator it=alignNonTerm.begin();
	it!=alignNonTerm.end(); ++it) {
	alignedToS[it->first].push_back(it->second);
	alignedCountS[it->first]++;
	m_alignedToT[it->second].push_back(it->first);
	}

	Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
	}

	PhraseOrientation::PhraseOrientation(int sourceSize,
	int targetSize,
	const std::vector<std::vector<int> > &alignedToT,
	const std::vector<std::vector<int> > &alignedToS,
	const std::vector<int> &alignedCountS)
	: m_countF(sourceSize)
	, m_countE(targetSize)
	, m_alignedToT(alignedToT)
	{
	Init(sourceSize, targetSize, m_alignedToT, alignedToS, alignedCountS);
	}


	void PhraseOrientation::Init(int sourceSize,
	int targetSize,
	const std::vector<std::vector<int> > &alignedToT,
	const std::vector<std::vector<int> > &alignedToS,
	const std::vector<int> &alignedCountS)
	{
	for (int startF=0; startF<m_countF; ++startF) {
	for (int endF=startF; endF<m_countF; ++endF) {

	int minE = std::numeric_limits<int>::max();
	int maxE = -1;
	for (int fi=startF; fi<=endF; ++fi) {
	for (size_t i=0; i<alignedToS[fi].size(); ++i) {
	int ei = alignedToS[fi][i];
	if (ei<minE) {
	minE = ei;
	}
	if (ei>maxE) {
	maxE = ei;
	}
	}
	}

	m_minAndMaxAlignedToSourceSpan[ std::pair<int,int>(startF,endF) ] = std::pair<int,int>(minE,maxE);
	}
	}

	// check alignments for target phrase startE...endE
	// loop over continuous phrases which are compatible with the word alignments
	for (int startE=0; startE<m_countE; ++startE) {
	for (int endE=startE; endE<m_countE; ++endE) {

	int minF = std::numeric_limits<int>::max();
	int maxF = -1;
	std::vector< int > usedF = alignedCountS;
	for (int ei=startE; ei<=endE; ++ei) {
	for (size_t i=0; i<alignedToT[ei].size(); ++i) {
	int fi = alignedToT[ei][i];
	if (fi<minF) {
	minF = fi;
	}
	if (fi>maxF) {
	maxF = fi;
	}
	usedF[fi]--;
	}
	}

	m_minAndMaxAlignedToTargetSpan[ std::pair<int,int>(startE,endE) ] = std::pair<int,int>(minF,maxF);

	if (maxF >= 0) { // aligned to any source words at all

	// check if source words are aligned to out of bounds target words
	bool out_of_bounds = false;
	for (int fi=minF; fi<=maxF && !out_of_bounds; ++fi)
	if (usedF[fi]>0) {
	// cout << "out of bounds: " << fi << "\n";
	out_of_bounds = true;
	}

	// cout << "doing if for ( " << minF << "-" << maxF << ", " << startE << "," << endE << ")\n";
	if (!out_of_bounds) {
	// start point of source phrase may retreat over unaligned
	for (int startF=minF;
	(startF>=0 &&
	(startF==minF \|\| alignedCountS[startF]==0)); // unaligned
	startF--) {
	// end point of source phrase may advance over unaligned
	for (int endF=maxF;
	(endF<m_countF &&
	(endF==maxF \|\| alignedCountS[endF]==0)); // unaligned
	endF++) { // at this point we have extracted a phrase

	InsertPhraseVertices(m_topLeft, m_topRight, m_bottomLeft, m_bottomRight,
	startF, startE, endF, endE);
	}
	}
	}
	}
	}
	}
	}


	void PhraseOrientation::InsertVertex( HSentenceVertices & corners, int x, int y )
	{
	std::set<int> tmp;
	tmp.insert(x);
	std::pair< HSentenceVertices::iterator, bool > ret = corners.insert( std::pair<int, std::set<int> > (y, tmp) );
	if (ret.second == false) {
	ret.first->second.insert(x);
	}
	}


	void PhraseOrientation::InsertPhraseVertices(HSentenceVertices & topLeft,
	HSentenceVertices & topRight,
	HSentenceVertices & bottomLeft,
	HSentenceVertices & bottomRight,
	int startF, int startE, int endF, int endE)
	{

	InsertVertex(topLeft, startF, startE);
	InsertVertex(topRight, endF, startE);
	InsertVertex(bottomLeft, startF, endE);
	InsertVertex(bottomRight, endF, endE);
	}


	const std::string PhraseOrientation::GetOrientationInfoString(int startF, int endF, REO_DIR direction) const
	{
	boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator foundMinMax
	= m_minAndMaxAlignedToSourceSpan.find( std::pair<int,int>(startF,endF) );

	if ( foundMinMax != m_minAndMaxAlignedToSourceSpan.end() ) {
	int startE = (foundMinMax->second).first;
	int endE = (foundMinMax->second).second;
	// std::cerr << "Phrase orientation for"
	// << " startF=" << startF
	// << " endF=" << endF
	// << " startE=" << startE
	// << " endE=" << endE
	// << std::endl;
	return GetOrientationInfoString(startF, startE, endF, endE, direction);
	} else {
	std::cerr << "PhraseOrientation::GetOrientationInfoString(): Error: not able to determine phrase orientation" << std::endl;
	std::exit(1);
	}
	}


	const std::string PhraseOrientation::GetOrientationInfoString(int startF, int startE, int endF, int endE, REO_DIR direction) const
	{
	REO_CLASS hierPrevOrient=REO_CLASS_UNKNOWN, hierNextOrient=REO_CLASS_UNKNOWN;

	if ( direction == REO_DIR_L2R \|\| direction == REO_DIR_BIDIR )
	hierPrevOrient = GetOrientationInfo(startF, startE, endF, endE, REO_DIR_L2R);

	if ( direction == REO_DIR_R2L \|\| direction == REO_DIR_BIDIR )
	hierNextOrient = GetOrientationInfo(startF, startE, endF, endE, REO_DIR_R2L);

	switch (direction) {
	case REO_DIR_L2R:
	return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR);
	break;
	case REO_DIR_R2L:
	return GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
	break;
	case REO_DIR_BIDIR:
	return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR) + " " + GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
	break;
	default:
	return GetOrientationString(hierPrevOrient, REO_MODEL_TYPE_MSLR) + " " + GetOrientationString(hierNextOrient, REO_MODEL_TYPE_MSLR);
	break;
	}
	return "PhraseOrientationERROR";
	}


	PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientationInfo(int startF, int endF, REO_DIR direction) const
	{
	boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator foundMinMax
	= m_minAndMaxAlignedToSourceSpan.find( std::pair<int,int>(startF,endF) );

	if ( foundMinMax != m_minAndMaxAlignedToSourceSpan.end() ) {
	int startE = (foundMinMax->second).first;
	int endE = (foundMinMax->second).second;
	// std::cerr << "Phrase orientation for"
	// << " startF=" << startF
	// << " endF=" << endF
	// << " startE=" << startE
	// << " endE=" << endE
	// << std::endl;
	return GetOrientationInfo(startF, startE, endF, endE, direction);
	} else {
	std::cerr << "PhraseOrientation::GetOrientationInfo(): Error: not able to determine phrase orientation" << std::endl;
	std::exit(1);
	}
	}


	PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientationInfo(int startF, int startE, int endF, int endE, REO_DIR direction) const
	{
	if ( direction != REO_DIR_L2R && direction != REO_DIR_R2L ) {
	std::cerr << "PhraseOrientation::GetOrientationInfo(): Error: direction should be either L2R or R2L" << std::endl;
	std::exit(1);
	}

	if ( direction == REO_DIR_L2R )
	return GetOrientHierModel(REO_MODEL_TYPE_MSLR,
	startF, endF, startE, endE, m_countF-1, 0, 0, 1,
	&ge, &le,
	m_bottomRight, m_bottomLeft);

	if ( direction == REO_DIR_R2L )
	return GetOrientHierModel(REO_MODEL_TYPE_MSLR,
	endF, startF, endE, startE, 0, m_countF-1, m_countE-1, -1,
	&le, &ge,
	m_topLeft, m_topRight);

	return REO_CLASS_UNKNOWN;
	}


	// to be called with countF-1 instead of countF
	PhraseOrientation::REO_CLASS PhraseOrientation::GetOrientHierModel(REO_MODEL_TYPE modelType,
	int startF, int endF, int startE, int endE, int countF, int zeroF, int zeroE, int unit,
	bool (ge)(int, int), bool (le)(int, int),
	const HSentenceVertices & bottomRight, const HSentenceVertices & bottomLeft) const
	{
	bool leftSourceSpanIsAligned = ( (startF != zeroF) && SourceSpanIsAligned(zeroF,startF-unit) );
	bool topTargetSpanIsAligned = ( (startE != zeroE) && TargetSpanIsAligned(zeroE,startE-unit) );

	if (!topTargetSpanIsAligned && !leftSourceSpanIsAligned)
	return REO_CLASS_LEFT;

	HSentenceVertices::const_iterator it;

	if (//(connectedLeftTop && !connectedRightTop) \|\|
	((it = bottomRight.find(startE - unit)) != bottomRight.end() &&
	it->second.find(startF-unit) != it->second.end()))
	return REO_CLASS_LEFT;

	if (modelType == REO_MODEL_TYPE_MONO)
	return REO_CLASS_UNKNOWN;

	if (//(!connectedLeftTop && connectedRightTop) \|\|
	((it = bottomLeft.find(startE - unit)) != bottomLeft.end() &&
	it->second.find(endF + unit) != it->second.end()))
	return REO_CLASS_RIGHT;

	if (modelType == REO_MODEL_TYPE_MSD)
	return REO_CLASS_UNKNOWN;

	for (int indexF=startF-2unit; (ge)(indexF, zeroF); indexF=indexF-unit) {
	if ((it = bottomRight.find(startE - unit)) != bottomRight.end() &&
	it->second.find(indexF) != it->second.end())
	return REO_CLASS_DLEFT;
	}

	for (int indexF=endF+2unit; (le)(indexF, countF); indexF=indexF+unit) {
	if ((it = bottomLeft.find(startE - unit)) != bottomLeft.end() &&
	it->second.find(indexF) != it->second.end())
	return REO_CLASS_DRIGHT;
	}

	return REO_CLASS_UNKNOWN;
	}

	bool PhraseOrientation::SourceSpanIsAligned(int index1, int index2) const
	{
	return SpanIsAligned(index1, index2, m_minAndMaxAlignedToSourceSpan);
	}

	bool PhraseOrientation::TargetSpanIsAligned(int index1, int index2) const
	{
	return SpanIsAligned(index1, index2, m_minAndMaxAlignedToTargetSpan);
	}

	bool PhraseOrientation::SpanIsAligned(int index1, int index2, const boost::unordered_map< std::pair<int,int> , std::pair<int,int> > &minAndMaxAligned) const
	{
	boost::unordered_map< std::pair<int,int> , std::pair<int,int> >::const_iterator itMinAndMaxAligned =
	minAndMaxAligned.find(std::pair<int,int>(std::min(index1,index2),std::max(index1,index2)));

	if (itMinAndMaxAligned == minAndMaxAligned.end()) {
	std::cerr << "PhraseOrientation::SourceSpanIsAligned(): Error" << std::endl;
	std::exit(1);
	} else {
	if (itMinAndMaxAligned->second.first == std::numeric_limits<int>::max()) {
	return false;
	}
	}
	return true;
	}


	const std::string PhraseOrientation::GetOrientationString(const REO_CLASS orient, const REO_MODEL_TYPE modelType)
	{
	std::ostringstream oss;
	WriteOrientation(oss, orient, modelType);
	return oss.str();
	}


	void PhraseOrientation::WriteOrientation(std::ostream& out, const REO_CLASS orient, const REO_MODEL_TYPE modelType)
	{
	switch(orient) {
	case REO_CLASS_LEFT:
	out << "mono";
	break;
	case REO_CLASS_RIGHT:
	out << "swap";
	break;
	case REO_CLASS_DLEFT:
	out << "dleft";
	break;
	case REO_CLASS_DRIGHT:
	out << "dright";
	break;
	case REO_CLASS_UNKNOWN:
	switch(modelType) {
	case REO_MODEL_TYPE_MONO:
	out << "nomono";
	break;
	case REO_MODEL_TYPE_MSD:
	out << "other";
	break;
	case REO_MODEL_TYPE_MSLR:
	out << "dleft";
	break;
	}
	break;
	}
	}


	bool PhraseOrientation::IsAligned(int fi, int ei) const
	{
	if (ei == -1 && fi == -1)
	return true;

	if (ei <= -1 \|\| fi <= -1)
	return false;

	if (ei == m_countE && fi == m_countF)
	return true;

	if (ei >= m_countE \|\| fi >= m_countF)
	return false;

	for (size_t i=0; i<m_alignedToT[ei].size(); ++i)
	if (m_alignedToT[ei][i] == fi)
	return true;

	return false;
	}


	void PhraseOrientation::IncrementPriorCount(REO_DIR direction, REO_CLASS orient, float increment)
	{
	assert(direction==REO_DIR_L2R \|\| direction==REO_DIR_R2L);
	if (direction == REO_DIR_L2R) {
	m_l2rOrientationPriorCounts[orient] += increment;
	} else if (direction == REO_DIR_R2L) {
	m_r2lOrientationPriorCounts[orient] += increment;
	}
	}


	void PhraseOrientation::WritePriorCounts(std::ostream& out, const REO_MODEL_TYPE modelType)
	{
	std::map<std::string,float> l2rOrientationPriorCountsMap;
	std::map<std::string,float> r2lOrientationPriorCountsMap;
	for (int orient=0; orient<=REO_CLASS_UNKNOWN; ++orient) {
	l2rOrientationPriorCountsMap[GetOrientationString((REO_CLASS)orient, modelType)] += m_l2rOrientationPriorCounts[orient];
	}
	for (int orient=0; orient<=REO_CLASS_UNKNOWN; ++orient) {
	r2lOrientationPriorCountsMap[GetOrientationString((REO_CLASS)orient, modelType)] += m_r2lOrientationPriorCounts[orient];
	}
	for (std::map<std::string,float>::const_iterator l2rOrientationPriorCountsMapIt = l2rOrientationPriorCountsMap.begin();
	l2rOrientationPriorCountsMapIt != l2rOrientationPriorCountsMap.end(); ++l2rOrientationPriorCountsMapIt) {
	out << "L2R_" << l2rOrientationPriorCountsMapIt->first << " " << l2rOrientationPriorCountsMapIt->second << std::endl;
	}
	for (std::map<std::string,float>::const_iterator r2lOrientationPriorCountsMapIt = r2lOrientationPriorCountsMap.begin();
	r2lOrientationPriorCountsMapIt != r2lOrientationPriorCountsMap.end(); ++r2lOrientationPriorCountsMapIt) {
	out << "R2L_" << r2lOrientationPriorCountsMapIt->first << " " << r2lOrientationPriorCountsMapIt->second << std::endl;
	}
	}

	} // namespace MosesTraining