treepath.hpp

#ifndef TREEPATH_H
#define TREEPATH_H

#include <QtCore/QLinkedList>

#include <iostream>

/*
 * inspired by:
 *
 * http://stackoverflow.com/questions/1005551/construct-a-tree-structure-from-list-of-string-paths
 *
 * a simple qt gui could use this:
 * http://qt-project.org/doc/qt-5.0/qtwidgets/itemviews-simpletreemodel.html
 */

template<typename T>
class TreeNode;


template<typename T>
struct Visitor
{
    virtual void visitNode(TreeNode<T> * node) = 0;
};


template<typename T>
struct Visitable
{
    virtual void accept(Visitor<T> * visitor) = 0;
};


template<typename T>
struct TreeNode : public Visitable<T>
{
    QLinkedList<TreeNode*> children;
    const T data;

    TreeNode(const T & d)
      : data(d)
    {
    }

    virtual void accept(Visitor<T> * visitor)
    {
        visitor->visitNode(this);
    }

    TreeNode* child(const T & data)
    {
        foreach (TreeNode * child, children )
            if (child->data == data)
                return child;

        TreeNode* childNode = new TreeNode(data);
        children.append(childNode);
        return childNode;
    }
};

class PrintIndentedVisitor : public Visitor<QString>
{
    int m_indent;
public:
    PrintIndentedVisitor(int i)
      : m_indent(i)
    {
    }

    virtual void visitNode(TreeNode<QString> * node)
    {
      std::cout << std::string(m_indent, ' ') << node->data.toStdString() << std::endl;

      //visit children
      m_indent += 2;
      foreach (TreeNode<QString> * child, node->children)
        child->accept(this);
      m_indent -= 2;
    }
};

#endif // TREEPATH_H


//
// sample usage below:
//


//  typedef TreeNode<QString> NodeType;

//  NodeType root("/");

//  NodeType * current = &root;

//  QStringList paths;
//  paths.append("x1/x2/x3");
//  paths.append("x1/x2/x4");
//  paths.append("x1/x5");

//  foreach (const QString & path, paths)
//  {
//    NodeType * node = current;

//    foreach (const QString & data, path.split("/"))
//    {
//      current = current->child(data);
//    }

//    current = node;
//  }

//  root.accept(new PrintIndentedVisitor(0));