BinaryTreeNode.hpp

/*
 * BinaryTreeNode.hpp
 * 
 * Copyright 2018 Fernando Pujaico Rivera <fernando.pujaico.rivera@gmail.com>
 * 
 * This program 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 2 of the License, or
 * (at your option) any later version.
 * 
 * This program 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 this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02110-1301, USA.
 * 
 */
 
#ifndef __PDS_BINARYTREENODE_HPP__
#define __PDS_BINARYTREENODE_HPP__
 
 
namespace Pds{
 
 
template <typename Datum>
class BinaryTreeNode
{
 
public:
 
    Datum *P;
 
    Pds::BinaryTreeNode<Datum> *LeftNode;
    
    Pds::BinaryTreeNode<Datum> *RightNode;
 
public:
 
    BinaryTreeNode(void);
    
    BinaryTreeNode(const Datum &Value);
    
    BinaryTreeNode( const Datum &Value,
                    Pds::BinaryTreeNode<Datum> *LeftNodePtr,
                    Pds::BinaryTreeNode<Datum> *RightNodePtr);
    
    BinaryTreeNode( const Datum &Value,
                    const Pds::BinaryTreeNode<Datum> &LeftNode,
                    const Pds::BinaryTreeNode<Datum> &RightNode);
    
    BinaryTreeNode(const Pds::BinaryTreeNode<Datum> &B);
 
    
    ~BinaryTreeNode(); 
    
public:
 
    Pds::BinaryTreeNode<Datum>& operator = (const Pds::BinaryTreeNode<Datum> &B);
    
    bool Copy(const Pds::BinaryTreeNode<Datum> &B);
    
    void MakeEmpty(void);
public:
 
    bool IsEmpty(void) const;
 
    bool HasChild0(void) const;
    
    bool HasChild1(void) const;
    
public:
 
    Datum GetVal(void) const;
 
    const Pds::BinaryTreeNode<Datum>* GetChild0(void) const;
 
    const Pds::BinaryTreeNode<Datum>* GetChild1(void) const;
    
public:
 
    void Print(const std::string &str="") const;
    
    void PrintNode(const std::string &str,const std::string &enddata="") const;
 
public:
 
    void ExportDotInStreamFile( std::ofstream &streamfile,
                                std::string (*FuncDatumToString)(const Datum &)
                                ) const;
 
 
    bool ExportDotFile( const std::string &filename,
                        std::string (*FuncDatumToString)(const Datum &)
                        ) const;
 
 
public:
 
    bool ExportXmlToStringStream(   std::stringstream &sstream, 
                                    std::string (*FuncDatumToXmlString)(const Datum &)
                                    ) const;
 
    bool ExportXmlToStream( std::ofstream &myfile, 
                            std::string (*FuncDatumToXmlString)(const Datum &)
                            ) const;
                            
    std::string ExportXmlToString( std::string (*FuncDatumToXmlString)(const Datum &) ) const;
    
    bool ImportXmlFromString(   const std::string &str,
                                Datum (*FuncXmlStringToDatum)(const std::string &)
                                );
    
    
}; // Class BinaryTreeNode
 
} // namespace Pds
 
 
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::BinaryTreeNode(void)
{
    this->P=NULL;
    this->LeftNode=NULL;
    this->RightNode=NULL;
    
    return;
}
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::BinaryTreeNode(const Datum &Value)
{
    this->P=new Datum(Value);
    this->LeftNode=NULL;
    this->RightNode=NULL;
    
    return;
}
 
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::BinaryTreeNode( const Datum &Value,
                                            Pds::BinaryTreeNode<Datum> *LeftNodePtr,
                                            Pds::BinaryTreeNode<Datum> *RightNodePtr)
{
    this->P=new Datum(Value);
    this->LeftNode=LeftNodePtr;
    this->RightNode=RightNodePtr;
    return;
}
 
 
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::BinaryTreeNode( const Datum &Value,
                                            const Pds::BinaryTreeNode<Datum> &LeftNode,
                                            const Pds::BinaryTreeNode<Datum> &RightNode)
{
    this->P=new Datum(Value);
    
    if(LeftNode.IsEmpty())
        this->LeftNode =NULL;
    else
        this->LeftNode =new Pds::BinaryTreeNode<Datum>(LeftNode);
    
    if(RightNode.IsEmpty())
        this->RightNode =NULL;
    else
        this->RightNode=new Pds::BinaryTreeNode<Datum>(RightNode);
 
    return;
}
 
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::BinaryTreeNode(const Pds::BinaryTreeNode<Datum> &Node)
{
    this->P=NULL;
    this->LeftNode=NULL;
    this->RightNode=NULL;
    
    this->Copy(Node);
 
    return;
}
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>::~BinaryTreeNode(void)
{
    this->MakeEmpty();
}
 
 
template <typename Datum>
Pds::BinaryTreeNode<Datum>& Pds::BinaryTreeNode<Datum>::operator = (const Pds::BinaryTreeNode<Datum> &A)
{
    if(false==this->Copy(A))
        this->MakeEmpty();
 
    //std::cout<<"used copy assignment\n";
    return *this;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::Copy(const Pds::BinaryTreeNode<Datum> &Node)
{    
    if(this!=&Node) //Comprueba que no se esté intentando igualar un objeto a sí mismo
    {
        if(Node.IsEmpty())
        {
            this->MakeEmpty();
            return true;
        }
        
        this->P=new Datum(*Node.P);
        if( this->P==NULL )
        {
            this->MakeEmpty();
            return false;
        }
        
        if(Node.LeftNode!=NULL)    this->LeftNode =new Pds::BinaryTreeNode<Datum>(*Node.LeftNode);
        if(Node.RightNode!=NULL)   this->RightNode=new Pds::BinaryTreeNode<Datum>(*Node.RightNode);
        
        if( (this->LeftNode==NULL)&&(Node.LeftNode!=NULL) )
        {
            this->MakeEmpty();
            return false;
        }
        
        if( (this->RightNode==NULL)&&(Node.RightNode!=NULL) )
        {
            this->MakeEmpty();
            return false;
        }
    }
    
    return true;
}
 
 
template <typename Datum>
void Pds::BinaryTreeNode<Datum>::MakeEmpty(void)
{
    if(this->P!=NULL)
    {
        delete this->P;
        this->P=NULL;
    }
    
    if(this->LeftNode!=NULL)
    {
        delete this->LeftNode;
        this->LeftNode=NULL;
    }
    
    if(this->RightNode!=NULL)
    {
        delete this->RightNode;
        this->RightNode=NULL;
    }
}
 
template <typename Datum>
void Pds::BinaryTreeNode<Datum>::Print(const std::string &str) const
{
    std::cout<<str;
    
    if(this->IsEmpty())   return;
    
    std::cout<<"\n"<<*(this->P);
    
    if(this->LeftNode!=NULL)
    {
        std::cout<<"CALL0\n";
        this->LeftNode->Print(str+std::to_string(0));
    }
    else    std::cout<<"NULL0\n";
    
    if(this->RightNode!=NULL)
    {
        std::cout<<"CALL1\n";
        this->RightNode->Print(str+std::to_string(1));
    }
    else    std::cout<<"NULL1\n";
 
    std::cout<<"END\n";
}
 
template <typename Datum>
void Pds::BinaryTreeNode<Datum>::PrintNode(const std::string &str,const std::string &enddata) const
{
    std::cout<<str;
    if(this->P!=NULL)
    {
        std::cout<<*(this->P);
    }
    
    std::cout<<enddata;
    
    std::cout<<this->LeftNode<<"\n";
    
    std::cout<<this->RightNode<<"\n";
}
 
template <typename Datum>
Datum Pds::BinaryTreeNode<Datum>::GetVal(void) const
{
    Datum ERROR;
    if(this->P==NULL)   return ERROR;
    
    return *(this->P);
}
 
template <typename Datum>
const Pds::BinaryTreeNode<Datum>* Pds::BinaryTreeNode<Datum>::GetChild0(void) const 
{
    return this->LeftNode;
}
 
template <typename Datum>
const Pds::BinaryTreeNode<Datum>* Pds::BinaryTreeNode<Datum>::GetChild1(void) const 
{
    return this->RightNode;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::IsEmpty(void) const
{
    if(this->P==NULL)   return true;
    
    return false;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::HasChild0(void) const
{
    if(this->LeftNode!=NULL)   return true;
    
    return false;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::HasChild1(void) const
{
    if(this->RightNode!=NULL)   return true;
    
    return false;
}
 
template <typename Datum>
void Pds::BinaryTreeNode<Datum>::ExportDotInStreamFile( std::ofstream &myfile, 
                                                        std::string (*FuncDatumToString)(const Datum &)
                                                        ) const
{
    if(this->IsEmpty())   return;
    
    std::string STRING=FuncDatumToString(*(this->P));
    
    myfile <<"N"<<(unsigned long)this<<"\t[ label =\""<<STRING<<"\"];\n";
    
    if(this->LeftNode!=NULL)    myfile  <<"N"<<(unsigned long)this
                                        <<"\t->\tN"<<(unsigned long)this->LeftNode
                                        <<"\t[label = \"0\"];\n";
    
    if(this->RightNode!=NULL)   myfile  <<"N"<<(unsigned long)this
                                        <<"\t->\tN"<<(unsigned long)this->RightNode
                                        <<"\t[label = \"1\"];\n";
    
    
    if(this->LeftNode!=NULL)    this->LeftNode->ExportDotInStreamFile(myfile,FuncDatumToString);
    if(this->RightNode!=NULL)   this->RightNode->ExportDotInStreamFile(myfile,FuncDatumToString);
    
    return;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::ExportDotFile( const std::string &filename, 
                                                std::string (*FuncDatumToString)(const Datum &)
                                                ) const
{
    std::ofstream myfile;
    myfile.open(filename);
    if (myfile.is_open())
    {
        myfile <<"// dot -Tpng -o "<<filename<<".png "<<filename<<"\n";
        myfile <<"digraph G {\n";
        this->ExportDotInStreamFile(myfile,FuncDatumToString);
        myfile <<"}\n";
        
        myfile.close();
        
        return true;
    }
    
    return false;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::ExportXmlToStringStream(   std::stringstream &sstream, 
                                                            std::string (*FuncDatumToXmlString)(const Datum &)
                                                            ) const
{
    sstream<<"<"<<Pds::Ra::Tag::BinaryTreeNode<<">\n";
    
    if(this->IsEmpty()==false)
    {
        sstream<<"<Datum>\n";
        sstream<<FuncDatumToXmlString(*this->P);
        sstream<<"</Datum>\n";
 
        sstream<<"<LeftNode>\n";
        if(this->LeftNode!=NULL)
        {
            this->LeftNode->ExportXmlToStringStream(sstream,FuncDatumToXmlString);
        }
        sstream<<"</LeftNode>\n";
 
        sstream<<"<RightNode>\n";
        if(this->RightNode!=NULL)
        {
            this->RightNode->ExportXmlToStringStream(sstream,FuncDatumToXmlString);
        }
        sstream<<"</RightNode>\n";
    }
    
    sstream<<"</"<<Pds::Ra::Tag::BinaryTreeNode<<">\n";
    
    return true;
}
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::ExportXmlToStream( std::ofstream &myfile,
                                                    std::string (*FuncDatumToXmlString)(const Datum &)
                                                    ) const
{
    if(myfile.is_open()==false) return false;
    
    std::stringstream ss;
    this->ExportXmlToStringStream(ss,FuncDatumToXmlString);
    myfile<<ss.str();
    
    return true;
}
 
template <typename Datum>
std::string Pds::BinaryTreeNode<Datum>::ExportXmlToString(  std::string (*FuncDatumToXmlString)(const Datum &)
                                                            ) const
{
    if(this->IsEmpty()) return "";
    
    std::stringstream ss;
    this->ExportXmlToStringStream(ss,FuncDatumToXmlString);
    
    return ss.str();
}
 
 
template <typename Datum>
bool Pds::BinaryTreeNode<Datum>::ImportXmlFromString(   const std::string &str,
                                                        Datum (*FuncXmlStringToDatum)(const std::string &)
                                                        )
{
    unsigned int n;
    this->MakeEmpty();
    
    unsigned int L=2*Pds::Ra::Tag::BinaryTreeNode.size()+5;
    
    if(str.length()<=L)     return false;
    
    std::string StrInNode;
    StrInNode=Pds::Ra::FirstSubInString(str,
                                        "<" +Pds::Ra::Tag::BinaryTreeNode+">",
                                        "</"+Pds::Ra::Tag::BinaryTreeNode+">"
                                        );
    StrInNode=Pds::Ra::Trim(StrInNode);
    
    if(StrInNode.size()==0)   return false;
 
    std::vector<std::string> dat;
    std::vector<std::string> tag;
    dat=Pds::Ra::SubsXmlInString(StrInNode,false,tag);
    
    std::string StrInDatum="";
    std::string StrInLeftNode="";
    std::string StrInRightNode="";
    
    for(n=0;n<tag.size();n++)
    {
        if(tag[n].compare("Datum")==0)
        {
            StrInDatum=dat[n];
        }
        else if(tag[n].compare("LeftNode")==0)
        {
            StrInLeftNode=dat[n];
        }
        else if(tag[n].compare("RightNode")==0)
        {
            StrInRightNode=dat[n];
        }
    }
    
    if(StrInDatum.size()==0)        return false;
    
    this->P= new Datum();
    *(this->P)=FuncXmlStringToDatum(StrInDatum);
    
    if(StrInLeftNode.size()>L)
    {
        this->LeftNode = new Pds::BinaryTreeNode<Datum>();
        this->LeftNode->ImportXmlFromString(StrInLeftNode,FuncXmlStringToDatum);
    }
    
    if(StrInRightNode.size()>L)
    {
        this->RightNode = new Pds::BinaryTreeNode<Datum>();
        this->RightNode->ImportXmlFromString(StrInRightNode,FuncXmlStringToDatum);
    }
    
    
    return true;
}
 
#endif