156 lines
5.2 KiB
C++
156 lines
5.2 KiB
C++
////////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// 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
|