[Olena-patches] 2946: Add a morpho tree data structure based on parenthood.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add a morpho tree data structure based on parenthood. * mln/morpho/tree/data.hh: New. * mln/morpho/tree/all.hh: Update. * tests/morpho/tree/data.cc: New. * tests/morpho/tree/Makefile.am: Update. * mln/morpho/tree/utils.hh (todo): New. * mln/core/image/safe.hh (init_): New precondition. Upgrade doc style. mln/core/image/safe.hh | 17 ++- mln/morpho/tree/all.hh | 1 mln/morpho/tree/data.hh | 187 ++++++++++++++++++++++++++++++++++++++++++ mln/morpho/tree/utils.hh | 2 tests/morpho/tree/Makefile.am | 6 - tests/morpho/tree/data.cc | 86 +++++++++++++++++++ 6 files changed, 289 insertions(+), 10 deletions(-) Index: tests/morpho/tree/Makefile.am --- tests/morpho/tree/Makefile.am (revision 2945) +++ tests/morpho/tree/Makefile.am (working copy) @@ -4,9 +4,11 @@ check_PROGRAMS = \ compute_tree \ + data \ max -compute_tree_SOURCES = compute_tree_.cc -max_SOURCES = max_.cc +compute_tree_SOURCES = compute_tree.cc +data_SOURCES = data.cc +max_SOURCES = max.cc TESTS = $(check_PROGRAMS) Index: tests/morpho/tree/data.cc --- tests/morpho/tree/data.cc (revision 0) +++ tests/morpho/tree/data.cc (revision 0) @@ -0,0 +1,86 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// 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/morpho/tree/parent.cc +/// +/// Tests on mln::morpho::tree::parent. + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/pw/image.hh> + +#include <mln/debug/println.hh> +#include <mln/debug/iota.hh> +#include <mln/morpho/elementary/dilation.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> + +#include <mln/morpho/tree/data.hh> + + +int main() +{ + using namespace mln; + + typedef image2d<unsigned> I; + I ima(3, 3); + debug::iota(ima); + + ima = morpho::elementary::dilation(ima, c8()); + debug::println("ima = ", ima); + + typedef p_array<point2d> S; + S s = level::sort_psites_increasing(ima); + + typedef morpho::tree::data<I,S> tree_t; + tree_t t(ima, s, c4()); + + debug::println( "parent = ", t.parent_image() | t.domain() ); + debug::println( "on node = ", t.parent_image() | t.nodes() ); + + { + std::cout << "nodes = "; + tree_t::nodes_t::piter p(t.nodes()); + for_all(p) + std::cout << p << ' '; + std::cout << std::endl + << std::endl; + } + + + { + image2d<unsigned> area(ima.domain()); + level::fill(area, 1); + tree_t::piter p(t.domain()); + for_all(p) + if (! t.is_root(p)) + area(t.parent(p)) += area(p); + debug::println("area = ", area | t.nodes()); + } + +} Index: mln/core/image/safe.hh --- mln/core/image/safe.hh (revision 2945) +++ mln/core/image/safe.hh (working copy) @@ -1,4 +1,5 @@ // Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,14 +29,13 @@ #ifndef MLN_CORE_IMAGE_SAFE_HH # define MLN_CORE_IMAGE_SAFE_HH -/*! - * \file mln/core/image/safe.hh - * - * \brief Definition of a morpher that makes image become accessible - * at undefined location. - * - * \todo Use 'instant' as the routine safe returns. - */ +/// +/// \file mln/core/image/safe.hh +/// +/// \brief Definition of a morpher that makes image become accessible +/// at undefined location. +/// +/// \todo Use 'instant' as the routine safe returns. # include <mln/core/internal/image_identity.hh> @@ -162,6 +162,7 @@ void safe_image<I>::init_(I& ima, const mln_value(I)& default_value) { + mln_precondition(! this->has_data()); mln_precondition(ima.has_data()); this->data_ = new internal::data< safe_image<I> >(ima, default_value); } Index: mln/morpho/tree/all.hh --- mln/morpho/tree/all.hh (revision 2945) +++ mln/morpho/tree/all.hh (working copy) @@ -47,6 +47,7 @@ # include <mln/morpho/tree/compute_parent.hh> +# include <mln/morpho/tree/data.hh> # include <mln/morpho/tree/max.hh> # include <mln/morpho/tree/utils.hh> Index: mln/morpho/tree/data.hh --- mln/morpho/tree/data.hh (revision 0) +++ mln/morpho/tree/data.hh (revision 0) @@ -0,0 +1,187 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// 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_MORPHO_TREE_DATA_HH +# define MLN_MORPHO_TREE_DATA_HH + +/// \file mln/morpho/tree/data.hh +/// +/// FIXME: First Attempt. + +# include <mln/morpho/tree/compute_parent.hh> +# include <mln/core/image/sub_image.hh> + + + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + // FIXME: Doc! + + template <typename I, typename S> + class data + { + public: + + + /// Ctor. + template <typename N> + data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh); + + + + /// \{ Parent-related materials. + + typedef mln_ch_value(I, mln_psite(I)) parent_t; + + const mln_psite(I)& parent(const mln_psite(I)& p) const + { + mln_precondition(is_valid()); + mln_precondition(parent_.domain().has(p)); + return parent_(p); + } + + const parent_t& parent_image() const + { + mln_precondition(is_valid()); + return parent_; + } + + /// \} + + + /// \{ Tests. + + bool is_valid() const + { + return parent_.has_data(); // FIXME: and... (?) + } + + bool is_root(const mln_psite(I)& p) const + { + mln_precondition(is_valid()); + mln_precondition(parent_.domain().has(p)); + return parent_(p) == p; + } + + bool is_a_node(const mln_psite(I)& p) const + { + mln_precondition(is_valid()); + mln_precondition(parent_.domain().has(p)); + return parent_(p) == p || f_(parent_(p)) != f_(p); + } + + /// \} + + + /// \{ Nodes-related materials. + + typedef p_array<mln_psite(I)> nodes_t; + + const p_array<mln_psite(I)>& nodes() const + { + mln_precondition(is_valid()); + return nodes_; + } + + /// \} + + + /// \{ How-to iterate on all sites. + + typedef mln_bkd_piter(S) piter; + typedef mln_bkd_piter(S) fwd_piter; + typedef mln_fwd_piter(S) bkd_piter; + + const S& domain() const + { + return s_; + } + + /// \} + + unsigned nroots() const + { + return nroots_; + } + + protected: + + const I& f_; + const S& s_; + mln_ch_value(I, mln_psite(I)) parent_; + p_array<mln_psite(I)> nodes_; + unsigned nroots_; + }; + + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename S> + template <typename N> + inline + data<I,S>::data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh) + : f_(exact(f)), + s_(exact(s)) + { + const N& nbh_ = exact(nbh); + + // Compute parent image. + parent_ = morpho::tree::compute_parent(f_, nbh_, s_); + + // Store tree nodes. + nroots_ = 0; + mln_bkd_piter(S) p(s_); + for_all(p) + if (f_(parent_(p)) != f_(p)) + nodes_.insert(p); + else + if (parent_(p) == p) + { + nodes_.insert(p); + ++nroots_; + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_TREE_DATA_HH Index: mln/morpho/tree/utils.hh --- mln/morpho/tree/utils.hh (revision 2945) +++ mln/morpho/tree/utils.hh (working copy) @@ -31,6 +31,8 @@ /// \file mln/morpho/tree/utils.hh /// /// Utilities. +/// +/// \todo Remove this file after ./data.hh is completed! # include <mln/core/concept/image.hh> # include <mln/core/site_set/p_array.hh>