---

nodeprint.h

Go to the documentation of this file.

/***************************************************************************
*  @file    print.h
*  @version 1.0
*
*  @author  Ingo Herwig, TU Darmstadt, FG Regelsystemtheorie und Robotik
*  @author  Eva Brucherseifer, TU Darmstadt, FG Regelsystemtheorie und Robotik
*  @date    2001
*
***************************************************************************/

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

#ifndef NODEPRINT_H
#define NODEPRINT_H

#include <map>
#include "node.h"
#include "nodevisitor.h"
#include "nodeoutputstrategy.h"
#include "nodeiterator.h"

namespace treecomp
{

/**
 * Position holds the x- ,y-coordinate of a point
 */
struct Position
{
    double x;
    double y;
};



// =====================
// === LayoutVisitor ===
// =====================
/**
 * The LayoutVisitor is used to position the tree nodes on a plane.
 * It uses a simple algorithm that positions the nodes on a discrete array with distance 1 so that
 * all leaves are equal distant from their neugbours.
 * The positions are stored in a map thet is provided by 'getMap()'.
 *
 * Yes, that is not the best layout algorithm... If anyone needs a better one, you might
 * convince me to backport the better one I have ;-)
 */

template<class _TContent, class _TIter>
class LayoutVisitor
    : public NodeVisitor<typename _TIter::const_iterator, const Node<_TContent>,
        const NormalNode<_TContent>,const RootNode<_TContent> >
{
public:
    typedef LayoutVisitor<_TContent,_TIter> _Self;
    typedef NodeVisitor<typename _TIter::const_iterator, const Node<_TContent>,
        const NormalNode<_TContent>,const RootNode<_TContent> >
        _Base;

    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone() const { return new _Self(*this); }
    virtual ~LayoutVisitor() {}

    virtual void operator()(_TIter& iter);
    virtual void visitNormalNode(const NormalNode<_TContent>* node);
    virtual void visitRootNode(const RootNode<_TContent>* node);

    virtual std::map<const Node<_TContent>*, Position> getMap() const { return m_map; }

protected:
    void addNode(const Node<_TContent>* node, Position pos);
    Position calculatePosition(const Node<_TContent>* node);
    
    std::map<const Node<_TContent>*, Position> m_map;
private:
    virtual LayoutVisitor& operator=(const LayoutVisitor&) {return *this;}
};



// ==============================
// === TEXGraphOutputStrategy ===
// ==============================
/**
 * This strategy writes the nodes in TEX format.
 * It uses a position-map that is created by 'LayoutVisitor' and
 * set with the method 'setMap()'.
 */
template<class _TContent>
class TEXGraphOutputStrategy : public StreamOutputStrategy<_TContent>
{
public:
    explicit TEXGraphOutputStrategy<_TContent>(std::ostream* out=&std::cout, double scale=1, double border=5)
        : StreamOutputStrategy<_TContent>(out), m_width(0), m_height(0), m_scale(scale), m_border(border) {}
    virtual TEXGraphOutputStrategy<_TContent>* construct() const { return new TEXGraphOutputStrategy<_TContent>; }
    virtual TEXGraphOutputStrategy<_TContent>* clone() const { return new TEXGraphOutputStrategy<_TContent>(*this); }
    virtual ~TEXGraphOutputStrategy() {}

    virtual void writeHeader();
    virtual void writeFooter();
    virtual void writeNormalNode(const NormalNode<_TContent>* node);
    virtual void writeRootNode(const RootNode<_TContent>* node);

    virtual void setScale(double scale) { m_scale = scale; }
    virtual void setPositionMap(std::map<const Node<_TContent>*, Position> pMap) { m_pMap = pMap; }

protected:
    virtual void writeEdge(const Node<_TContent>* node);
    virtual std::string formatName(std::string name);
    virtual int getMapIndex(const Node<_TContent>* node);
    std::map<const Node<_TContent>*, Position> m_pMap;
    double m_width;
    double m_height;
    double m_scale;
    double m_border;
};


// =================== Template definition =================================


// =====================
// === LayoutVisitor ===
// =====================

/**
 * Start the layout process
 * @param iter The NodeIterator that iterates over all nodes to visit
 */
template<class _TContent, class _TIter>
//void LayoutVisitor<_TContent>::start(NodeIterator<_TContent>* iter)
void LayoutVisitor<_TContent,_TIter>::operator()(_TIter& iter)
{
    init(iter);
    m_map.clear();
    iterate(this);
}

/**
 * Take a NormalNode and put it in the list
 * @param node The NormalNode to visit
 */
template<class _TContent, class _TIter>
void LayoutVisitor<_TContent,_TIter>::visitNormalNode(const NormalNode<_TContent>* node)
{
    addNode(node, calculatePosition(node));
}

/**
 * Take a RootNode and put its subtree in the list
 * @param node The RootNode to visit
 */
template<class _TContent, class _TIter>
void LayoutVisitor<_TContent,_TIter>::visitRootNode(const RootNode<_TContent>* node)
{
    addNode(node, calculatePosition(node));
}

/**
 * Take a Node and put it in the list
 * @param node The Node to add
 */
template<class _TContent, class _TIter>
void LayoutVisitor<_TContent,_TIter>::addNode(const Node<_TContent>* node, Position position)
{
    m_map.insert( typename std::map<const Node<_TContent>*, Position>::value_type(node, position) );
}

/**
 * Calculate node position using the described algorithm
 * @param node The Node to calculate the position for
 */
template<class _TContent, class _TIter>
Position LayoutVisitor<_TContent,_TIter>::calculatePosition(const Node<_TContent>* node)
{
    Position pos;
    const Node<_TContent>* parent = node->getParent();
    if (!parent)
    {
        // start here
        pos.x = 0.0;
        pos.y = 0.0;
    }
    else
    {
        Position parentPos = m_map[parent];
        pos.y = parentPos.y + 1;
        const std::list<Node<_TContent>*>* siblings = parent->getChildren();
        if (siblings->front() == node)
            pos.x = parentPos.x;
        else
        {
            // find leftmost sibling of node
            typename std::list<Node<_TContent>*>::const_iterator nlIter = find(siblings->begin(), siblings->end(), node);
            const Node<_TContent>* leftSibling = *(--nlIter);
            // find x-coordinate rightmost descendant of leftmost sibling
            double maxX = 0;
            typename Node<_TContent>::const_all_iterator anIter = leftSibling->beginAll();
            for (; anIter != leftSibling->endAll(); ++anIter)
                if (m_map[anIter()].x >= maxX)
                    maxX = m_map[anIter()].x;
            pos.x = maxX + 2;
            // reposition parents
            while (parent)
            {
                m_map[parent].x += 1;
                parent = parent->getParent();
            }
        }
    }
    return pos;
}



// ==============================
// === TEXGraphOutputStrategy ===
// ==============================
/**
 * Write the TEX header
 */
template<class _TContent>
void TEXGraphOutputStrategy<_TContent>::writeHeader()
{
    // calculate bounding box
    m_width = 0;
    m_height = 0;
    typename std::map<const Node<_TContent>*, Position>::const_iterator pmIter;
    for (pmIter = m_pMap.begin(); pmIter != m_pMap.end(); ++pmIter)
    {
        if ((*pmIter).second.x >= m_width)
            m_width = (*pmIter).second.x;
        if ((*pmIter).second.y >= m_height)
            m_height = (*pmIter).second.y;
    }
    m_width *= m_scale;
    m_height *= m_scale;

    *m_out << "%% This is a generated file!\n"
    << "%% Requires pstricks and pst-node styles.\n"
    << "\\begin{figure}[htb]\n"
    << "\\begin{center}\n"
    << "\\psset{unit=1mm, arrows=-, nodesep=0pt, fillstyle=solid}\n"
    << "\\begin{pspicture}(" << m_width + 2*m_border << ',' << m_height + 2*m_border << ")\n";
    //    *m_out << "\\put(0,0){\\framebox(" << m_width + 2*m_border << ',' << m_height + 2*m_border << "){}}\n";
}

/**
 * Write the TEX footer
 */
template<class _TContent>
void TEXGraphOutputStrategy<_TContent>::writeFooter()
{
    // get tree root for naming
    const Node<_TContent>* root = (*(m_pMap.begin())).first;
    while(root->getParent())
        root = root->getParent();
    std::string treeName = formatName(root->getName());
    std::string caption = treeName;
    std::string label = treeName;
    if (treeName[0] == '\\')
    {
        caption = "$" + treeName + "$"; // math mode for symbols
        label.erase(label.begin());
    }
    *m_out << "\\end{pspicture}\n";
    *m_out << "\\caption{" << caption << "}\n";
    *m_out << "\\label{tree: " << label << "}\n";
    *m_out << "\\end{center}\n";
    *m_out << "\\end{figure}\n";
}

/**
 * Write the normalNode content
 */
template<class _TContent>
void TEXGraphOutputStrategy<_TContent>::writeNormalNode(const NormalNode<_TContent>* node)
{
    if (m_pMap.count(node))
    {
        // write node name in oval
        *m_out << "\\rput(" << (m_border + m_pMap[node].x * m_scale) << ','
        << m_border + m_height - m_pMap[node].y * m_scale
        << "){\\Rnode{" << getMapIndex(node) << "}{{\\footnotesize \\psovalbox{\\(" << formatName(node->getName()) << "\\)}}}}\n";

        writeEdge(node);
    }
    else
    {
        *m_out << "Error: Didn't find node " + node->getName() + " in position map\n";
    }
}

/**
 * Write the RootNode content
 */
template<class _TContent>
void TEXGraphOutputStrategy<_TContent>::writeRootNode(const RootNode<_TContent>* node)
{
    if (m_pMap.count(node))
    {
        // write node name in oval
        *m_out << "\\rput(" << (m_border + m_pMap[node].x * m_scale) << ','
        << m_border + m_height - m_pMap[node].y * m_scale
        << "){\\Rnode{" << getMapIndex(node) << "}{{\\footnotesize \\psovalbox{\\(\\bf " << formatName(node->getName()) << "\\)}}}}\n";

        writeEdge(node);
    }
    else
    {
        *m_out << "Error: Didn't find node " + node->getName() + " in position map\n";
    }
}

/**
 * Write the edge to the parent
 */
template<class _TContent>
void TEXGraphOutputStrategy<_TContent>::writeEdge(const Node<_TContent>* node)
{
    if (node->getParent())
    {
        int parentIndex = getMapIndex(node->getParent());
        int nodeIndex = getMapIndex(node);
        if (node->isFixed())
        {
            *m_out << "\\ncline[doubleline=true]{" << parentIndex << "}{" << nodeIndex << "}\n";
        }
        else
        {
            *m_out << "\\ncline[doubleline=false]{" << parentIndex << "}{" << nodeIndex << "}\n";
        }
    }
}

/**
 * Takes the word in quotation marks as name if existing
 */
template<class _TContent>
std::string 
TEXGraphOutputStrategy<_TContent>::formatName(std::string name)
{
    std::string::size_type start = name.find("\"");
    if (start < name.size())
    {
        std::string::size_type end = name.find("\"", start+1);
        name=name.substr(start+1, end-start-1);
    }
    return name;
}

/**
 * Returns the index of the node in the position map
 */
template<class _TContent>
int TEXGraphOutputStrategy<_TContent>::getMapIndex(const Node<_TContent>* node)
{
    int i = 0;
    typename std::map<const Node<_TContent>*, Position>::const_iterator pmIter;
    for (pmIter = m_pMap.begin(); pmIter != m_pMap.end(); ++pmIter)
    {
        if (node == (*pmIter).first)
            return i;
        ++i;
    }
    return 0;
}


} // namespace treecomp


#endif //PRINT_H

---