gistfile1.cpp

#include <iostream>
#include <string>
#include <vector>
#include <memory>

#include <boost/optional.hpp>


class node;
typedef std::shared_ptr<node> node_ptr;
typedef std::vector<node_ptr> node_collection;

class node {
public:
  explicit node(std::string const& name)
    : name(name) {}

  std::string const& get_name() const {
    return name;
  }

  node_collection const& get_nodes() const {
    return nodes;
  }

  void add(node_ptr child) {
    nodes.emplace_back(child);
  }

private:
  std::string name;
  node_collection nodes;

public:
  static node_ptr make(std::string const& name) {
    return std::make_shared<node>(name);
  }
};


node_ptr create_tree() {
  //        a
  //      /   \
  //     b     c
  //    / \   / \
  //   d   e f   g
  auto b = node::make("b");
  b->add(node::make("d"));
  b->add(node::make("e"));

  auto c = node::make("c");
  c->add(node::make("f"));
  c->add(node::make("g"));

  auto a = node::make("a");
  a->add(b);
  a->add(c);
  return a;
}


class path;
typedef std::shared_ptr<path> path_ptr;
typedef boost::optional<path_ptr> optional_path_ptr;

class path {
public:
  path(node_ptr const& value, optional_path_ptr const& parent)
    : value(value)
    , parent(parent)
  {}

  node_ptr get_value() {
    return value;
  }

  optional_path_ptr get_parent() {
    return parent;
  }

private:
  node_ptr value;
  optional_path_ptr parent;
};


optional_path_ptr find(node_ptr const& root, std::string const& name, optional_path_ptr const& cont) {
  auto const p = std::make_shared<path>(root, cont);
  if (root->get_name() == name)
    return p;

  auto const& nodes = root->get_nodes();
  for (auto const& e: nodes) {
    auto found = find(e, name, p);
    if (found)
      return found;
  }

  return boost::none;
}

optional_path_ptr find(node_ptr const& root, std::string const& name) {
  return find(root, name, boost::none);
}


int main() {
  auto root = create_tree();
  auto p = find(root, "d");
  while (p) {
    std::cout << (*p)->get_value()->get_name() << std::endl;
    p = (*p)->get_parent();
  }
}