tree.hpp

/*
 * tree.hpp
 *
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)

 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Created on: Jul 2, 2016
 * Author: Jan Travnicek
 */

#ifndef __TREE_HPP_
#define __TREE_HPP_

#include <memory>
#include <sstream>
#include <string>

#include "tree_base.hpp"
#include "vector.hpp"

#include <extensions/compare.hpp>
#include <extensions/iterator.hpp>

namespace ext {

/**
 * \brief
 * Class introducing a tree with interface trying to be close to the interface of standard library containers.
 *
 * The tree is a hierarchical structure of nodes with parent child relationship, where the children are ordered and indexed by integers.
 *
 * \tparam T the type of values inside nodes of the tree
 */
template < class T >
class tree {
	/**
	 * \brief
	 * The value in the root node of the tree
	 */
	T m_data;

	/**
	 * \brief
	 * Pointer to the parent of the node. Null pointer for root of a tree.
	 */
	tree * m_parent;

	/**
	 * \brief
	 * Container of children of the root node of the tree.
	 *
	 * The children are trees themselves, hence the subtree of a tree is itself a tree.
	 */
	ext::vector < tree > m_children;

public:
	/**
	 * \brief
	 * Getter of the parent node. Null if the node is root.
	 *
	 * \return pointer to the parent node
	 */
	tree * getParent ( ) {
		return m_parent;
	}

	/**
	 * \brief
	 * Getter of the parent node. Null if the node is root.
	 *
	 * \return pointer to the parent node
	 */
	const tree * getParent ( ) const {
		return m_parent;
	}

	/**
	 * \brief
	 * Getter of the value in the root node.
	 *
	 * \return the value in the root node
	 */
	T & getData ( ) {
		return m_data;
	}

	/**
	 * \brief
	 * Getter of the value in the root node.
	 *
	 * \return the value in the root node
	 */
	const T & getData ( ) const {
		return m_data;
	}

	/**
	 * \brief
	 * Getter of children of the root node.
	 *
	 * \return children of the root node
	 */
	ext::vector < tree > & getChildren ( ) {
		return m_children;
	}

	/**
	 * \brief
	 * Getter of children of the root node.
	 *
	 * \return children of the root node
	 */
	const ext::vector < tree > & getChildren ( ) const {
		return m_children;
	}

	/**
	 * \brief
	 * The iterator type over children of the node
	 */
	typedef typename ext::vector < tree >::const_iterator const_children_iterator;

	/**
	 * \brief
	 * The iterator type over children of the node
	 */
	typedef typename ext::vector < tree >::iterator children_iterator;

	/**
	 * \brief
	 * The iterator type over structure of the tree representing nodes and node_ends
	 *
	 * The iterator performs a top to bottom, left to right or depth first travrsal stopping at each node twice. Once as it enters it the first time and second time when it leaves it (on the way to its parent).
	 */
	class const_structure_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		/**
		 * \brief
		 * The underlying iterator within some list of children.
		 */
		typename ext::vector < tree >::const_iterator node;

		/**
		 * \brief
		 * The depth of the current pointed to node.
		 */
		unsigned level;

		/**
		 * \brief
		 * True if the iterator is pointing to a tree node in the first visit, false in the second (leaving case).
		 */
		bool virtual_node;

		/**
		 * \brief
		 * True if the iterator is one position after the last valid iterator value.
		 */
		bool isEnd;

	public:
		/**
		 * \brief
		 * Constructor of the iterator based on the iterator to child list
		 *
		 * \param n the iterator to child list
		 */
		const_structure_iterator ( typename ext::vector < tree >::const_iterator n ) : node ( n ), level ( 0 ), virtual_node ( false ), isEnd ( false ) {
		}

		/**
		 * \brief
		 * Advance the iterator.
		 *
		 * \return the updated iterator
		 */
		const_structure_iterator & operator ++( ) {
			if ( virtual_node ) {
				const tree * parent = node->getParent ( );
				++node;

				if ( parent != nullptr ) {
					if ( node == parent->getChildren ( ).end ( ) ) {
						--level;
						node = typename ext::vector < tree >::const_iterator ( parent );
					} else {
						virtual_node = false;
					}