/*  Copyright by Matthias Hoechsmann (C) 2002-2004  =====================================                                     You may use, copy and distribute this file freely as long as you  - do not change the file,  - leave this copyright notice in the file,  - do not make any profit with the distribution of this file  - give credit where credit is due  You are not allowed to copy or distribute this file otherwise  The commercial usage and distribution of this file is prohibited  Please report bugs and suggestions to <mhoechsm@TechFak.Uni-Bielefeld.DE>*/#ifndef _PPFOREST_T_CPP_#define _PPFOREST_T_CPP_#include "misc.h"#include "ppforest.h"/* ****************************************** *//*    Constructor and Destruktor functions    *//* ****************************************** */template <class L> PPForest<L>::PPForest(size_type size): PPForestBase(size){	m_lb=new L[size];}template <class L>PPForest<L>::PPForest(const PPForest<L> &ppf) : PPForestBase(ppf){	m_lb=new L[ppf.size()];	// copy labels	for(size_type i=0;i<size();i++)		m_lb[i]=ppf.m_lb[i];} template <class L>PPForest<L>::PPForest(istream &s){  /*  // read ppforest from file  // first of all save the size  s.read(static_cast<char*>(m_size),sizeof(PPForestBase::size_type));  // initialize structures  ::PPForestBase(m_size);    m_lb=new L[ppf.size()];  // save the arrays  s.read(static_cast<char*>(m_lb),sizeof(label_type)*m_size);  s.read(static_cast<char*>(m_rb),sizeof(PPForestBase::size_type)*m_size);  s.read(static_cast<char*>(m_noc),sizeof(PPForestBase::size_type)*m_size);  s.read(static_cast<char*>(m_sumUpCSF),sizeof(PPForestBase::size_type)*m_size);  s.read(static_cast<char*>(m_rmb),sizeof(PPForestBase::size_type)*m_size);      */}template <class L> PPForest<L>::~PPForest(){   DELETE_ARRAY(m_lb);}/* ****************************************** *//*            Private functions               *//* ****************************************** */template<class L>void PPForest<L>::print(ostream &s,size_type node,bool brackets) const{	if(brackets)		s << "(";	s <<  "{" << node << "}";	showLabel(s,m_lb[node]);	if(m_noc[node])		print(s,node+1,true);	if(m_rb[node])		print(s,m_rb[node],false);	if(brackets)		s << ")";	}/** Calculate maximal score of csf (i,j) for a certain Algebra. *  It is assumed that a perfect match of the forest obtains the best *  possible score. */template <class L>template <class R>R PPForest<L>::maxScore(const Algebra<R,L> &alg, size_type i, size_type j) const{	R down, over;	if(j==0)		return 0;	if(isLeave(i))	{		over=maxScore(alg,rb(i),j-1);		return alg.replace(label(i),0,label(i),over);	}	else	{		down=maxScore(alg,i+1,noc(i));		over=maxScore(alg,rb(i),j-1);		return alg.replace(label(i),down,label(i),over);	}}  /** Calculate maximal score of csf (i,j) for a certain RNA_Algebra. *  It is assumed that a perfect match of the forest obtains the best *  possible score. */template <class L>template <class R>R PPForest<L>::maxScore(const RNA_Algebra<R,L> &alg, Uint i, Uint j) const{	R down, over;	if(j==0)		return 0;	if(isLeave(i))	{		over=maxScore(alg,rb(i),j-1);		return alg.replace(label(i),0,label(i),over);	}	else	{		down=maxScore(alg,i+1+1,noc(i)-2);		over=maxScore(alg,rb(i),j-1);		return alg.replacepair(label(i+1),label(i+1),down,label(getRightmostBrotherIndex(i+1)),label(getRightmostBrotherIndex(i+1)),over);	}}  /* ****************************************** *//*            Protected function              *//* ****************************************** */template <class L>void PPForest<L>::initialize(size_type size){	PPForestBase::initialize(size);	m_lb=new L[size];}/* ****************************************** *//*             Public functions               *//* ****************************************** */template<class L>void PPForest<L>::printDot(ostream &s) const{	size_type i,h;	s << "digraph forest" << endl << "{" << endl;	// edges	for(i=0;i<m_size;i++)	{		s << i;		if(m_noc[i])		{			s << " -> {";			h=i+1;			for(Uint r=0;r<getMaxLength(i+1);r++)			{				s << h << " ";				h=m_rb[h];			}			s << "}";	  	     	    		}		s << endl;	}	// labels	s << endl << endl;	for(i=0;i<m_size;i++)	{		s << i << "[label=\"";		showLabel(s,m_lb[i]);		s << "\"]" << endl;	}	s << "}";}template<class L>void PPForest<L>::save(ostream &s) const{  /*	  // save the pforest to stream in binary format    // first of all save the size  s.write(reinterpret_cast<char*>(&m_size),sizeof(PPForestBase::size_type));  // save the arrays  s.write(reinterpret_cast<char*>(m_lb),sizeof(label_type)*m_size);  s.write(reinterpret_cast<char*>(m_rb),sizeof(PPForestBase::size_type)*m_size);  s.write(reinterpret_cast<char*>(m_noc),sizeof(PPForestBase::size_type)*m_size);  s.write(reinterpret_cast<char*>(m_sumUpCSF),sizeof(PPForestBase::size_type)*m_size);  s.write(reinterpret_cast<char*>(m_rmb),sizeof(PPForestBase::size_type)*m_size);  */} template <class L>ostream& operator<< (ostream &s, PPForest<L> &ppf){  ppf.print(s,0,true);	  return s;}#endif