trees.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_ADTS_TREES_H
#define ELEMENTA_ADTS_TREES_H
 
#include <memory>
#include <algorithm>
#include "elementa/base/fundamentaltypes.h"
#include "elementa/base/exceptions.h"
#include "elementa/base/serial_channels/serializers.h"
#include "elementa/adts/graphs/graphs.h"
 
#include "elementa/base/debugging.h"
 
 
namespace elementa
{
 
namespace adts
{
 
/* ***************************************************************************
 
    Abstract template class: Tree
    
*******************************************************************************/
 
 
template <class Vertex, class Edge>
class Tree
{
 public:
 
    using BGraph = graphs::Graph<Vertex,Edge>;
 
    using Ptr = std::shared_ptr<Tree>;
 
    using Forest = std::vector<Ptr>;
 
 
    Tree(const BGraph & exemplar):
        pgraph_{reinterpret_cast<BGraph *>(exemplar.emptyClone())} {}
 
    Tree(const Tree & oth):pgraph_{nullptr} 
        { copyFrom(oth); }
 
    Tree(Tree && oth): pgraph_{nullptr} 
        { moveFrom(std::move(oth)); }
 
    Tree & operator=(const Tree & oth)
        { if (this != & oth) copyFrom(oth); return(*this); }
 
    Tree & operator=(Tree && oth)
        { if (this != & oth) moveFrom(std::move(oth)); return(*this); }
 
    virtual ~Tree(void) 
        { delete pgraph_; }
 
    bool empty(void) const 
        {ELE_CODE_TRACE_OFF; 
            ELE_CODE_TRACE({},"PGraph_=" << elementa::base::to_number(pgraph_));
            return(pgraph_->empty()); }
 
    BGraph & graph(void) const { return(*pgraph_); }
 
    typename BGraph::viterator root(void) const;
 
 
    graphs::size_edge depth(const typename BGraph::viterator & n)const;
 
    void clear(void) { pgraph_->clear(); }
 
 
    typename BGraph::viterator setRoot(const Vertex & v);
 
 
    typename BGraph::viterator addChild(
                                const typename BGraph::viterator & parent, 
                                const Vertex & v, const Edge & e);
 
    void eraseNode(const typename BGraph::viterator & node);
 
 
    void splice(Tree & oth, const Edge & edgeval);
 
 private:
 
    BGraph * pgraph_;
 
    void copyFrom(const Tree & oth)
        { if (pgraph_ != nullptr) delete pgraph_; 
          pgraph_ = reinterpret_cast<BGraph *>(oth.pgraph_->clone()); }
 
    void moveFrom(Tree && oth)
        { if (pgraph_ != nullptr) delete pgraph_; 
          pgraph_ = oth.pgraph_; 
          oth.pgraph_ = reinterpret_cast<BGraph *>(pgraph_->emptyClone()); }
};
 
 
/* ***************************************************************************
 
    Template class: Szer_TreeText
    
*******************************************************************************/
 
 
template <class Vertex, class Edge>
class Szer_TreeText: public elementa::base::Serializer< Tree<Vertex,Edge> >
{
 public:
 
    using TreeType = Tree<Vertex,Edge>;
 
 
    Szer_TreeText(elementa::base::Serializer<Vertex> & szerv,
                  elementa::base::Serializer<Edge> & szere)
        { szerv_ = &szerv; szere_ = &szere; }
 
    void ser(elementa::base::OutSerCh & chout, const TreeType & tree);
 
    // No deserialization.
 
 private:
 
    elementa::base::Serializer<Vertex> * szerv_;
    elementa::base::Serializer<Edge> * szere_;
 
static_assert(
    (sizeof(graphs::size_vertex)<=8) &&
    (sizeof(graphs::size_edge)<=8),
    "Serialization requires 64 bits or less for size_vertex and size_edge");
};
 
 
 
/* ===========================================================================
 
        ========== IMPLEMENTATION OF TEMPLATES ==========
 
============================================================================= */
 
 
/* ***************************************************************************
 
    Template class: Tree
    
*******************************************************************************/
 
template <class Vertex, class Edge>
typename Tree<Vertex,Edge>::BGraph::viterator 
    Tree<Vertex,Edge>::root(void) const
{
    if (pgraph_->size_vertices()==0) return(pgraph_->vrangeAll().end());
    return(pgraph_->vrangeAll().begin());
}   
 
template <class Vertex, class Edge>
graphs::size_edge Tree<Vertex,Edge>::depth(
            const typename Tree<Vertex,Edge>::BGraph::viterator & n) const
{
    graphs::size_edge res{0};
    typename Tree<Vertex,Edge>::BGraph::eiterator eparent;
    typename Tree<Vertex,Edge>::BGraph::viterator node{n};
    do
    {
        eparent = pgraph_->erangeEntering(node).begin();
        if (!eparent.isEnd())
        {
            ++res;
            node = pgraph_->origin(eparent);
        }
    } while (!eparent.isEnd());
    return(res);
}
 
template <class Vertex, class Edge>
typename Tree<Vertex,Edge>::BGraph::viterator 
    Tree<Vertex,Edge>::setRoot(const Vertex & v)
{ELE_CODE_TRACE_OFF;
 
    if (pgraph_->size_vertices() == 0) 
    {
        ELE_CODE_TRACE({},"Creating root node in empty tree.");
        return(pgraph_->insert(v));
    }
    ELE_CODE_TRACE({},"Changing existing root node content.");
    typename BGraph::viterator it = pgraph_->vrangeAll().begin();
    *it = v;
    return(it);
}
 
template <class Vertex, class Edge>
typename Tree<Vertex,Edge>::BGraph::viterator 
    Tree<Vertex,Edge>::addChild(
   const typename Tree<Vertex,Edge>::BGraph::viterator & parent, 
   const Vertex & v, const Edge & e)
{ELE_CODE_TRACE_OFF;
 
    ELE_CODE_TRACE({},"Adding new child to parent " << parent.to_string());
    if ( (!parent.valid()) || (parent.isEnd()) )
        ELE_CODE_INVARG("Cannot add a child to an invalid parent");
    ELE_CODE_TRACE({},"Inserting new vertex in the tree (to parent " <<
                      parent.to_string() << ")" << std::endl);
    auto it = pgraph_->insert(v);
    ELE_CODE_TRACE({},std::endl << "New vertex inserted in the tree. Parent: "<< 
                      parent.to_string() << ". Child: " << it.to_string());
    ELE_CODE_TRACE({},"Inserting new edge to connect vertex in the tree");
    pgraph_->connect(parent,it,e);
    ELE_CODE_TRACE({},"Child added.");
    return(it);
}
 
template <class Vertex, class Edge>
void Tree<Vertex,Edge>::eraseNode(
    const typename Tree<Vertex,Edge>::BGraph::viterator & node)
{ELE_CODE_TRACE_OFF;
 
    typename BGraph::VectorOfVIts vinds;
    auto eit = pgraph_->erangeDepthFirst(node).begin();
    typename BGraph::viterator v0,v1;
    while (!eit.isEnd())
    {
        ELE_CODE_TRACE({},"eraseNode adding a connection");
        pgraph_->connection(eit,v0,v1);
        if (std::find(vinds.begin(),vinds.end(),v0) == vinds.end())
            vinds.push_back(v0);
        if (std::find(vinds.begin(),vinds.end(),v1) == vinds.end())
            vinds.push_back(v1); 
        ++eit;
    }
    ELE_CODE_TRACE({},"erasing all collected connections");
    pgraph_->erase(vinds);
}
 
template <class Vertex, class Edge>
void Tree<Vertex,Edge>::splice(Tree & oth, const Edge & edge)
{ELE_CODE_TRACE_OFF;
 
    if (oth.empty()) return;
 
    ELE_CODE_TRACE({},"Copying root iterators for merging");
    typename Tree<Vertex,Edge>::BGraph::VectorOfVIts svits,svothits;
    svothits.push_back(oth.root());
    svits.push_back(root());
    ELE_CODE_TRACE({},"My root: " << root().to_string() << ", inside svits: " <<
                      svits[0].to_string());
    ELE_CODE_TRACE({},"Oth root: " << root().to_string() << 
                      ", inside svothits: "<< svothits[0].to_string());
    ELE_CODE_TRACE({},"Doing the graph splice");
    pgraph_->splice(*oth.pgraph_,&svothits,nullptr,&svits,nullptr);
    ELE_CODE_TRACE({},"Doing the graph connect");
    pgraph_->connect(svits[0],svothits[0],edge);
    ELE_CODE_TRACE({},"Graph merge done, other tree clearing");
    oth.clear();
}
 
 
/* ***************************************************************************
 
    Template class: Szer_TreeText
    
*******************************************************************************/
 
template <class Vertex, class Edge>
void Szer_TreeText<Vertex,Edge>::ser(elementa::base::OutSerCh & chout,
                                     const TreeType & tree)
{ELE_CODE_TRACE_OFF;
 
    ELE_CODE_TRACE({},"");
 
    if (tree.empty()) return;
 
    ELE_CODE_TRACE({},"Tree to serialize is not empty: " <<
                      tree.graph().size_vertices() << " vertices, " << 
                      tree.graph().size_edges() << " edges");
 
    auto writenewline = [](elementa::base::OutSerCh & chout)
    {
        chout.put('\n');
        elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
    };
 
    auto writebranch = [](elementa::base::OutSerCh & chout, 
                          graphs::size_edge start,
                          // how many tabs before leaving parent
                          unsigned length) // how many chars until child
    {
        if (start > 0)
        {
            for (unsigned char g = 0; g<2; ++g)
            {
                for (unsigned f = 0; f < start; ++f)
                {
                    chout.put('\t');
                    elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
                }
                chout.put('|');
                elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
                if (g == 0)
                {
                    chout.put('\n');
                    elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
                }
            }
        }
        if (length > 0)
        {
            for (unsigned f = 0; f < length; ++f)
            {
                chout.put('_'); // must be shorter than '\t'
                elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
            }
        }
    };
 
    auto vit = tree.root();
    ELE_CODE_TRACE({},"Serializing root: " << vit.to_string());
    szerv_->ser(chout,*vit);
    ELE_CODE_TRACE({},"Root serialized ok");
    writenewline(chout);
 
    ELE_CODE_TRACE({},"Serializing others from root: " << vit.to_string());
    const auto & gr = const_cast<TreeType &>(tree).graph(); // const just wiped 
                                                            // out temporarily
                                                            // to get graph()
 
    auto eit = gr.erangeDepthFirst(vit).begin();
    bool changelevel{true};
    graphs::size_edge level{0};
    while (!eit.isEnd())
    {
        // serializes destination node of eit with its previous branch
        auto vchildit = gr.destination(eit);
        if (changelevel) level = tree.depth(vchildit);
        writebranch(chout,level,2);
        chout.put('(');
        elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
        szere_->ser(chout,*eit);
        chout.put(')');
        elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
        chout.put(' ');
        elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
        szerv_->ser(chout,*vchildit);
        writenewline(chout);
    
        changelevel = ( (!gr.toLeaf(eit)) ||
                        (gr.toLastChild(eit,gr.origin(eit))) );
 
        ++eit;
    }
}
 
 // Trees
 
 
} // end adts namespace
 
} // end elementa namespace
 
 
#endif