Tree data structure - first part of implementation

main.cpp

#include "node.h"
#include "nodeiter.h"

#include <iostream>
#include <memory>
#include <list>
using namespace std;

int main()
{
    Node<int> tree;

    cin >> tree;
    cout << tree << endl;

    for ( auto x : tree)
    {
        cout << x.get_value();
        cout << endl;
    }

    return 0;
}

node.h

#ifndef NODE_H_
#define NODE_H_

#include <iosfwd>
#include <memory>
#include <list>

template <typename T> class Node;
template <typename T> class NodeIter;

template <typename X>
std::ostream& operator << (std::ostream& s, const Node<X>& n);

template < typename T >
class Node
{
public:
    /** \brief Default constructor */
    Node();
    /** \brief Value constructor, creates node with the specified value */
    Node(const T& value);
    /** \brief Copy constructor */
    Node(const Node<T>& n);

    typedef typename std::shared_ptr<Node<T>> shared_type;

    /** \brief Add a new child to this node with a specified value */
    shared_type add_child(const T& value);
    /** \brief Add the specified node as child */
    shared_type add_child(Node<T>* node);
    /** \brief Add the specified node as child */
    shared_type add_child(shared_type node);

    /** \brief Get the value stored in this node */
    T& get_value();
    /** \brief Get the value stored in this node */
    const T& get_value() const;
    /** \brief Set the value in this node */
    void set_value(const T& value);

    /** \brief Output stream operator */
    template < typename X >
    friend std::ostream& operator << (std::ostream& s, const Node<X>& n);

    /** \brief Input stream operator */
    template < typename X >
    friend std::istream& operator >> (std::istream& s, Node<X>& n);

    /** \brief Return iterator to the first item in the tree */
    NodeIter<T> begin() { return NodeIter<T>(this); }
    /** \brief Return iterator after the last element */
    NodeIter<T> end() { return NodeIter<T>(); }

    template <typename X>
    friend class NodeIter;

    /** \brief Assignment operator */
    Node<T>& operator = (const Node<T>& n);

private:
    T p_value;
    Node<T>* p_parent;
    std::list<shared_type> p_children;
};

#include "node.hpp"

#endif

node.hpp

#ifndef NODE_HPP_
#define NODE_HPP_

#include "node.h"
#include <iostream>
#include <stdexcept>
using namespace std;

template<typename T>
Node<T>::Node() : p_value(), p_parent(nullptr), p_children() {}

template<typename T>
Node<T>::Node(const T& value) : p_value(value), p_parent(nullptr), p_children() {}

template<typename T>
Node<T>::Node(const Node<T>& n) : p_value(n.p_value), p_parent(n.p_parent), p_children(n.p_children) {}

template< typename T>
shared_ptr<Node<T>> Node<T>::add_child(const T& value)
{
	return add_child(make_shared<Node<T>>(value));
}

template< typename T >
shared_ptr<Node<T>> Node<T>::add_child(Node<T>* node)
{
	return shared_ptr<Node<T>>(node);
}

template < typename T >
shared_ptr<Node<T>> Node<T>::add_child(shared_ptr<Node<T>> node)
{
	node->p_parent = this;
	p_children.push_back(node);

	return node;
}

template <typename T>
T& Node<T>::get_value() { return p_value; }

template <typename T>
const T& Node<T>::get_value() const { return p_value; }

template <typename T>
void Node<T>::set_value(const T& value) { p_value = value; }

template <typename T>
ostream& operator << (ostream& s, const Node<T>& n)
{
	s << "{ " << n.p_value << " ";
	if (n.p_children.size() > 0)
	{
		for (auto c : n.p_children)
			s << *c << " ";
	}
	s << "}";

	return s;
}

template <typename T>
std::istream& operator >> (std::istream& s, Node<T>& n)
{
    // on the begining of each node is {

	char zav;
	T value;
	cin >> zav;
	if (zav != '{')
		throw runtime_error("Unexpected character on the begining of a node, while parsing a tree.");

    // after { we are expecting a node value

	cin >> value;
	if (cin.bad())
		throw runtime_error("Unexpected character in the place of a value, while parsing a tree.");

	n.set_value(value);

	do
	{
        // read all spaces
		while (isspace(zav = cin.peek()))
			cin.ignore();

        // after a value, we can have end of the node "}" or beginning of new child node "{"
		if (zav != '{' && zav != '}')
			throw runtime_error("Unexpected character when expecting a brace.");

        // if this is a child node, prepare the node and recurively read it
		if (zav == '{')
		{
			auto child = make_shared<Node<T>>();
			cin >> *child;
			n.add_child(child);
		}
	} while (zav != '}');

    // don't forget to read the "}"
	cin >> zav;

	return s;
}

template<typename T>
Node<T>& Node<T>::operator = (const Node<T>& n)
{
	p_value = n.p_value;
	p_parent = n.p_parent;
	p_children = n.p_children;
}

#endif

nodeiter.h

#ifndef TREE_H_
#define TREE_H_

#include <list>
#include <stack>

#include "node.h"

template < typename T >
class NodeIter
{
public:
    NodeIter() : p_current(nullptr), p_path() {}
    NodeIter(Node<T>* head) : p_current(head), p_path() {}
    NodeIter(const NodeIter<T>& i) : p_current(i.p_current), p_path(i.p_path) {}

    bool operator != (const NodeIter<T>& i) const;
    const NodeIter<T>& operator++ ();
    Node<T> operator *();

    NodeIter<T>& operator = (const NodeIter<T>& i);

private:
    Node<T>* p_current;
    typedef typename Node<T>::shared_type shared_type;
    typedef typename std::list<shared_type>::iterator child_iter;
    std::stack<child_iter> p_path;
};


#include "nodeiter.hpp"

#endif

nodeiter.hpp

#ifndef TREE_HPP_
#define TREE_HPP_

#include "nodeiter.h"
#include <stdexcept>
#include <stack>

template < typename T >
const NodeIter<T>& NodeIter<T>::operator++ ()
{
    // can't iterate further if p_current is NULL
	if (p_current == NULL)
		return *this;

    // depth-first => if we have children, go to first child
	if (p_current->p_children.size() != 0)
	{
		p_path.push(p_current->p_children.begin());
		p_current = p_current->p_children.begin()->get();
	}
    // if we don't have children, but have sisters, jump to next sister
	else if (next(p_path.top()) != p_current->p_parent->p_children.end())
	{
		++p_path.top();
		p_current = p_path.top()->get();
	}
    // if we don't have children and no more sisters, backtrack
	else
	{
        // go up, untill we find a node that has a sister we haven't visited
		while (p_path.size() != 0 && next(p_path.top()) == p_current->p_parent->p_children.end())
		{
			p_path.pop();
			p_current = p_current->p_parent;
		}

        // if there is no such sister we end up on top => end of the iteration
		if (p_path.size() == 0)
		{
			p_current = NULL;
			p_path = stack<child_iter>{};
			return *this;
		}

        // we found a sister, jump to it
		++p_path.top();
		p_current = p_path.top()->get();
	}

	return *this;
}

template <typename T>
bool NodeIter<T>::operator != (const NodeIter<T>& i) const
{
	return p_current != i.p_current || p_path != i.p_path;
}

template <typename T>
Node<T> NodeIter<T>::operator *() { return *p_current; }

template <typename T>
NodeIter<T>& NodeIter<T>::operator = (const NodeIter<T>& i)
{
	p_current = i.p_current;
	p_path = i.p_path;
	return *this;
}

#endif