URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-25 Guillaume Duhamel <guillaume.duhamel@lrde.epita.fr> Add a structure of tree based on vector. * mln/util/tree_fast.hh: New structure of tree. * tests/tree_fast.cc: New test for fast_tree. --- mln/util/tree_fast.hh | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++ tests/tree_fast.cc | 63 ++++++++++++++++++++ 2 files changed, 219 insertions(+) Index: trunk/milena/tests/tree_fast.cc =================================================================== --- trunk/milena/tests/tree_fast.cc (revision 0) +++ trunk/milena/tests/tree_fast.cc (revision 1387) @@ -0,0 +1,63 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/*! + * \file tests/tree_fast.cc + * + * \brief test of mln::util::tree_fast + * + */ + +#include <mln/util/tree_fast.hh> +#include <mln/core/contract.hh> +#include <iostream> + +int main (void) +{ + using namespace mln; + + unsigned elt1 = 1; + unsigned elt2 = 2; + unsigned elt3 = 3; + unsigned elt4 = 4; + unsigned elt5 = 5; + unsigned elt6= 42; + + util::tree<unsigned> tree(elt1); + mln_assertion(tree.has (elt1)); + tree.add_child(tree.search(elt1), elt2); + mln_assertion(tree.has (elt2)); + tree.add_child(tree.search(elt1), elt3); + mln_assertion(tree.has (elt3)); + tree.add_child(tree.search(elt2), elt4); + mln_assertion(tree.has (elt4)); + tree.add_child(tree.search(elt2), elt5); + mln_assertion(tree.has (elt5)); + tree.add_parent(elt6); + mln_assertion(tree.has (elt6)); + mln_assertion(tree.search(elt6) == tree.root_); +} Index: trunk/milena/mln/util/tree_fast.hh =================================================================== --- trunk/milena/mln/util/tree_fast.hh (revision 0) +++ trunk/milena/mln/util/tree_fast.hh (revision 1387) @@ -0,0 +1,156 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_TREE_HH +# define MLN_UTIL_TREE_HH + +# include <vector> +# include <mln/core/contract.hh> + +/*! + * \file mln/util/tree_fast.hh + * + * \brief Definition of a fast generic general tree. + * + */ + +namespace mln +{ + + namespace util + { + + template <typename T> + struct tree + { + tree(); + tree(T& elt); + + const unsigned size() const; + bool has (T& elt) const; + unsigned search (T& elt) const; + bool is_root (unsigned i) const; + void add_child (unsigned i, T& elt); + void add_parent (T& elt); + + std::vector<T> data_; + std::vector<unsigned> parent_; + std::vector<std::vector<unsigned> > child_; + unsigned root_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename T> + tree<T>::tree() + { + } + + template <typename T> + tree<T>::tree(T& elt) + { + std::vector<unsigned> v; + data_.push_back(elt); + parent_.push_back(0); + child_.push_back(v); + root_ = 0; + } + + template <typename T> + const unsigned + tree<T>::size() const + { + return (data_.size ()); + } + + + template <typename T> + bool + tree<T>::has (T& elt) const + { + for (unsigned i = 0; i < data_.size (); ++i) + if (data_[i] == elt) + return true; + + return false; + } + + template <typename T> + unsigned + tree<T>::search (T& elt) const + { + for (unsigned i = 0; i < data_.size (); ++i) + if (data_[i] == elt) + return i; + + return (unsigned)(-1); + } + + template <typename T> + bool + tree<T>::is_root (unsigned i) const + { + return (root_ == i); + } + + template <typename T> + void + tree<T>::add_child (unsigned i, T& elt) + { + mln_assertion (i < data_.size ()); + std::vector<unsigned> v; + data_.push_back(elt); + parent_.push_back(i); + child_.push_back(v); + child_[i].push_back(data_.size () - 1); + } + + template <typename T> + void + tree<T>::add_parent (T& elt) + { + std::vector<unsigned> v; + data_.push_back(elt); + parent_.push_back(data_.size () - 1); + child_.push_back(v); + child_[data_.size () - 1].push_back(root_); + parent_[root_] = data_.size () - 1; + root_ = data_.size () - 1; + } + + + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util + + +} // end of namespace mln + + +#endif // !MLN_UTIL_TREE_HH