--- /dev/null
+/*
+ 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
+
+
+
+
+
+
+
+