////////////////////////////////////////////////////////////////////////////////
//
// Paella
// Copyright (C) 2015 - Thomas FORGIONE, Emilie JALRAS, Marion LENFANT, Thierry MALON, Amandine PAILLOUX
// Authors :
//     Thomas FORGIONE
//     Emilie JALRAS
//     Marion LENFANT
//     Thierry MALON
//     Amandine PAILLOUX
//
// This file is part of the project Paella
// This software is provided 'as-is', without any express or implied warranty.
// In no event will the authors be held liable for any damages arising from the use of this software.
//
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it freely,
// subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented;
//    you must not claim that you wrote the original software.
//    If you use this software in a product, an acknowledgment
//    in the product documentation would be appreciated but is not required.
//
// 2. Altered source versions must be plainly marked as such,
//    and must not be misrepresented as being the original software.
//
// 3. This notice may not be removed or altered from any source distribution.
////////////////////////////////////////////////////////////////////////////////
#ifndef TREE_HPP
#define TREE_HPP

#include <iostream>
#include <vector>
#include <algorithm>

namespace geo
{
using Path = std::vector<unsigned int>;

template<typename T>
class Tree;

///////////////////////////////////////////////////////
/// \ingroup geometry
/// \brief Class to store trees with nodes and children
///////////////////////////////////////////////////////
template <typename T>
class Tree
{
    public:
        ///////////////////////////////////////////////////////////
        /// \brief default constructor
        ///
        /// Builds an empty tree, and uses the default constructor on the node
        ///////////////////////////////////////////////////////////
        Tree() : node{}, children{} {};

        ///////////////////////////////////////////////////////////
        /// \brief usual constructor
        /// \param t value of the node
        ///
        /// Creates a tree with no children and with t as node
        ///////////////////////////////////////////////////////////
        Tree(T t) : node{std::move(t)}, children{} {};

        ///////////////////////////////////////////////////////////
        /// \brief returns the subtree after the path is done
        /// \pre the path must exist in this tree
        /// \param p path to apply to the tree
        /// \param offset index of the next element of the path to take
        /// \return a reference to the subtree
        ///////////////////////////////////////////////////////////
        Tree<T> const& applyPath(Path const& p, unsigned int offset = 0) const
        {
            if (offset == p.size())
            {
                return *this;
            }
            else
            {
                return children[p[offset]].applyPath(p, offset+1);
            }
        };

        ///////////////////////////////////////////////////////////
        /// \brief returns the subtree after the path is done
        /// \pre the path must exist in this tree
        /// \param p path to apply to the tree
        /// \return a const reference to the subtree
        ///////////////////////////////////////////////////////////
        Tree<T>& applyPath(Path const& p)
        {
            return const_cast<Tree<T>&>(static_cast<const Tree*>(this)->applyPath(p));
        }

        ///////////////////////////////////////////////////////////
        /// \brief returns the subtree after the path is done and calls operator()
        ///        on the nodes during the path
        /// \pre the path must exist in this tree
        /// \param p path to apply to the tree
        /// \param offset index of the next element of the path to take
        ///////////////////////////////////////////////////////////
        void execPath(Path const& p, unsigned int offset = 0) const
        {
            if (offset != p.size())
            {
                children[p[offset]].node();
                children[p[offset]].execPath(p, offset + 1);;
            }
        }

        /////////////////////////////////////////////////////////////
        /// \brief Computes the number of elements in the tree
        ///
        /// \return the number of elements in the tree
        /////////////////////////////////////////////////////////////
        std::size_t size() const
        {
            std::size_t size = 1;
            for (auto const& c : children)
                size += c.size();
            return size;
        }

        T node; ///< node of this tree
        std::vector<Tree<T>> children; ///< list of children
};

template<typename T>
std::ostream& print_helper(std::ostream& out, Tree<T> const& tree, std::size_t tab)
{
    for (auto i = 0u; i < tab; i++)
    {
        out << "-";
    }
    out << tree.node << std::endl;
    for (auto const& c : tree.children)
    {
        print_helper(out, c, tab + 2);
    }
    return out;
}

template<typename T>
std::ostream& operator<<(std::ostream& out, Tree<T> const& tree)
{
    return print_helper(out, tree, 0);
}



} // namespace geo

#endif // TREE_HPP