[Olena-patches] r3518: Clean and fix bugs on component trees propagation

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-03-12 Edwin Carlinet &lt;carlinet(a)lrde.epita.fr&gt; Clean and fix bugs on component trees propagation. * edwin/tree/accumulator/max.hh: Special max accumulator for iterator. * edwin/tree/accumulator: New. * edwin/tree/propagate.hh, * edwin/tree/propagate_leaf.hh, * edwin/tree/propagate_node.hh, * edwin/tree/propagate_value.hh: Improve propagation methods and make them cleaner. * edwin/tree/propagation.cc: Test file. * edwin/tree/routines.hh: Add methods for tree traversal. --- Makefile | 7 - accumulator/max.hh | 154 ++++++++++++++++++++++++++++++++ propagate.hh | 7 + propagate_leaf.hh | 63 +++++++++++++ propagate_node.hh | 253 +++++++++++++++++++++++++++++++++++++++++++++++++++++ propagate_value.hh | 231 ++++++++++++++++++++++++++++++++++++++++++++++++ propagation.cc | 118 ++++++++++++++++++++++++ routines.hh | 19 +++ 8 files changed, 847 insertions(+), 5 deletions(-) Index: trunk/milena/sandbox/edwin/tree/accumulator/max.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/accumulator/max.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/accumulator/max.hh (revision 3518) @@ -0,0 +1,154 @@ +// Copyright (C) 2007, 2008, 2009 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_ACCUMULATOR_MAX_HH_ +# define MLN_MORPHO_TREE_ACCUMULATOR_MAX_HH_ + +/// \file mln/morpho/tree/accumulator/max.hh +/// +/// Define an accumulator that returns iterator matching the max node value. + + +# include <mln/core/concept/image.hh> +# include <mln/accu/internal/base.hh> + +namespace mln { + namespace morpho { + namespace tree{ + namespace accumulator { + + template <typename T, typename I> + class max : public mln::accu::internal::base< mln_bkd_piter(T::nodes_t), max<T, I> > + { + typedef mln::accu::internal::base< unsigned, max<T, I> > super_; + + public: + typedef mln_bkd_piter(T::nodes_t) argument; + + /// Constructor + max(const Image<I>& f); + + /// Manipulators. + /// \{ + void init(); + + void take(const argument& it); + void take(const max<T, I>& other); + + void take_as_init(const argument& it); + /// \} + + /// Get the value of the accumulator. + mln_bkd_piter(T::nodes_t) to_result() const; + + /// Check whether the accumulator is able to give a result. + bool is_valid() const; + + private: + const I& f_; + mln_bkd_piter(T::nodes_t) max_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename T, typename I> + inline + max<T, I>::max(const Image<I>& f) : + f_ (exact(f)) + { + } + + template <typename T, typename I> + inline + void + max<T, I>::init() + { + } + + template <typename T, typename I> + inline + void + max<T, I>::take(const argument& it) + { + mln_invariant(it.is_valid()); + + if (!is_valid()) + { + take_as_init(it); + return; + } + + if (f_(it) > f_(max_)) + max_ = it; + } + + template <typename T, typename I> + inline + void + max<T, I>::take(const max<T, I>& other) + { + mln_invariant(other.is_valid()); + + if (f_(other.max_) > f_(max_)) + max_ = other.max_; + } + + template <typename T, typename I> + inline + void + max<T, I>::take_as_init(const argument& it) + { + mln_invariant(it.is_valid()); + max_ = it; + } + + template <typename T, typename I> + inline + mln_bkd_piter(T::nodes_t) + max<T, I>::to_result() const + { + return max_; + } + + template <typename T, typename I> + inline + bool + max<T, I>::is_valid() const + { + return max_.is_valid(); + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree::accumulator + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln + +#endif /* ! MLN_MORPHO_TREE_ACCUMULATOR_MAX_HH_ */ Index: trunk/milena/sandbox/edwin/tree/propagate.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate.hh (revision 3517) +++ trunk/milena/sandbox/edwin/tree/propagate.hh (revision 3518) @@ -1,4 +1,4 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 2009 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 @@ -55,8 +55,11 @@ } } - namespace binary { + + + + /// Dans le cas des images binaires... /// Propagate a tagged node's value to its subbranches. template <typename T, typename A> void Index: trunk/milena/sandbox/edwin/tree/propagate_node.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 3518) @@ -0,0 +1,253 @@ +// Copyright (C) 2007, 2008, 2009 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_PROPAGATE_NODE_HH_ +# define MLN_MORPHO_TREE_PROPAGATE_NODE_HH_ + +#include <mln/morpho/tree/data.hh> +#include <mln/core/site_set/p_array.hh> + +/// \file mln/morpho/tree/propagate_node.hh +/// +/// Functions to propagate node in the tree. + +namespace mln { + namespace morpho { + namespace tree { + + + /** + ** Propagate a value to a node and its descendants. + ** + ** @param n Forward iterator related to the node. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + ** @param v Value to propagate. Default is a_(n). + */ + template <typename T, typename A> + void + propagate_node_to_descendants(mln_bkd_piter(T::nodes_t)& n, + const T& t, + Image<A>& a_, + mln_value(A) v); + + /** + ** Propagate the value of a node to its descendants. + ** + ** @param n Forward iterator related to the node. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + */ + template <typename T, typename A> + void + propagate_node_to_descendants(mln_bkd_piter(T::nodes_t)& n, + const T& t, + Image<A>& a_); + + + /** + ** Propagate a value to a node and its descendants. + ** + ** @param n The root of subtree which value propagates in. + ** @param t The reference to components tree. + ** @param a_ The reference to image. + ** @param v The value to propagate. Default is a_(n). + */ + template <typename T, typename A> + void + propagate_node_to_descendants(mln_psite(A) n, + const T& t, + Image<A>& a_, + mln_value(A) v); + + /** + ** Propagate the node's value to its descendants. + ** + ** @param n The root of subtree which value propagates in. + ** @param t The reference to components tree. + ** @param a_ The reference to image. + */ + template <typename T, typename A> + void + propagate_node_to_descendants(mln_psite(A)& n, + const T& t, + Image<A>& a_); + + /** + ** Propagate a value from a node to its ancestors. + ** + ** @param n Forward iterator related to the node. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + ** @param v Value to propagate. + */ + template <typename T, typename A> + void + propagate_node_to_ancestors(mln_psite(A) n, + const T& t, + Image<A>& a_, + mln_value(A) v); + + /** + ** Propagate the node's value to its ancestors. + ** + ** @param n Forward iterator related to the node. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + */ + template <typename T, typename A> + void + propagate_node_to_ancestors(mln_psite(A) n, + const T& t, + Image<A>& a_); + + + + + + + /* Descendants propagation */ + + template <typename T, typename A> + void + propagate_node_to_descendants(mln_bkd_piter(T::nodes_t)& n, + const T& t, + Image<A>& a_, + mln_value(A) v) + { + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + mln_precondition(n.is_valid()); + mln_precondition(t.is_a_node(n)); + + mln_ch_value(A, bool) ancestors; + initialize(ancestors, a); + data::fill(ancestors, false); + ancestors(n) = true; + + mln_bkd_piter(T::nodes_t) it(n); + for (it.next(); it.is_valid(); it.next()) + { + if (ancestors(t.parent(it))) + { + ancestors(it) = true; + a(it) = v; + } + } + } + + template <typename T, typename A> + inline + void + propagate_node_to_descendants(mln_bkd_piter(T::nodes_t)& n, + const T& t, + Image<A>& a_) + { + A& a = exact(a_); + propagate_node_to_descendants(n, t, a, a(n)); + } + + template <typename T, typename A> + void + propagate_node_to_descendants(mln_psite(A) n, + const T& t, + Image<A>& a_, + mln_value(A) v) + { + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + mln_precondition(a.domain().has(n)); + + + if (!t.is_a_node(n)) // Get the representant. + n = t.parent(n); + + mln_bkd_piter(T::nodes_t) it = find_bkd(t.nodes(), n); + propagate_node_to_descendants(it, t, a, v); + } + + template <typename T, typename A> + inline + void + propagate_node_to_descendants(mln_psite(A) n, + const T& t, + Image<A>& a_) + + { + A& a = exact(a_); + propagate_node_to_descendants(n, t, a, a(n)); + } + + + /* Ancestors propagation */ + + template <typename T, typename A> + void + propagate_node_to_ancestors(mln_psite(A) n, + const T& t, + Image<A>& a_, + mln_value(A) v) + { + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + mln_precondition(a.domain().has(n)); + + if (!t.is_a_node(n)) + n = t.parent(n); + mln_assertion(t.is_a_node(n)); + + if (t.is_root(n)) + return; + + do { + n = t.parent(n); + a(n) = v; + } while (!t.is_root(n)); + + } + + template <typename T, typename A> + inline + void + propagate_node_to_ancestors(mln_psite(A) n, + const T& t, + Image<A>& a_) + { + A& a = exact(a_); + propagate_node_to_ancestors(n, t, a, a(n)); + } + + + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln + +#endif /* !MLN_MORPHO_TREE_PROPAGATE_NODE_HH_ */ Index: trunk/milena/sandbox/edwin/tree/routines.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/routines.hh (revision 3517) +++ trunk/milena/sandbox/edwin/tree/routines.hh (revision 3518) @@ -37,6 +37,22 @@ namespace morpho { namespace tree { + + template <typename T, + + + + + + + + + + + + + + // FIXME: it bugs; need a stack/queue template <typename I, typename T> util::array< mln_psite(I) > @@ -65,6 +81,9 @@ return fnodes; } + template <typename T, + + } } } Index: trunk/milena/sandbox/edwin/tree/propagate_leaf.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_leaf.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/propagate_leaf.hh (revision 3518) @@ -0,0 +1,63 @@ +// Copyright (C) 2007, 2008, 2009 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_PROPAGATE_LEAF_HH_ +# define MLN_MORPHO_TREE_PROPAGATE_LEAF_HH_ + + +/// \file mln/morpho/tree/propagate_leaf.hh +/// +/// Functions to propagate the leaf value in the tree. + +namespace mln { + namespace morpho { + namespace tree { + + template <typename T, typename A> + void + propagate_leaf_to_ancestors(mln_value(A) v, + const T& t, + Image<A>& a_) + { + A& a = exact(a_); + + mln_fwd_piter(T::leaves_t) l(t.leaves()); + for_all(l) + a(t.parent(l)) = 0; + + mln_fwd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + { + mln_assertion(t.is_a_node(t.parent(n))); + a(t.parent(n)) = a(t.parent(n)) || a(n); + } + } + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln +#endif /* !MLN_MORPHO_TREE_PROPAGATE_LEAF_HH_ */ Index: trunk/milena/sandbox/edwin/tree/propagation.cc =================================================================== --- trunk/milena/sandbox/edwin/tree/propagation.cc (revision 0) +++ trunk/milena/sandbox/edwin/tree/propagation.cc (revision 3518) @@ -0,0 +1,118 @@ +#include <iostream> + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/core/alias/point2d.hh> +#include <mln/core/routine/duplicate.hh> + +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> + + +#include <mln/level/sort_psites.hh> +#include <mln/morpho/tree/data.hh> + + +#include <../../theo/color/change_attributes.hh> +#include "propagate_node.hh" +#include "propagate_value.hh" +#include "run.hh" +#include "accumulator/max.hh" + +void usage(char** argv) +{ + std::cerr << "usage: " << argv[0] << " input" << std::endl; + abort(); +} + +void dsp(const char* str) +{ + std::cout << "*********************" << std::endl + << "** " << str << std::endl + << "*********************" << std::endl; +} + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc < 2) + usage(argv); + + + typedef image2d<int_u8> I; + I input, dup; + + + io::pgm::load(input, argv[1]); + + + typedef p_array< mln_site_(I) > S; + typedef morpho::tree::data<I,S> tree_t; + S sorted_sites = level::sort_psites_decreasing(input); + tree_t tree(input, sorted_sites, c4()); + + dsp("Input:"); + display_tree_attributes(tree, input); + + dup = duplicate(input); + morpho::tree::propagate_node_to_ancestors(point2d(1, 4), tree, dup, 0); + dsp("Propagate node to ancestors : (point2d(1, 4), tree, dup, 0)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_node_to_ancestors(point2d(1, 4), tree, dup); + dsp("Propagate node to ancestors : (point2d(1, 4), tree, dup)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_node_to_descendants(point2d(0, 2), tree, dup, 0); + dsp("Propagate node to descendants : (point2d(0, 2), tree, dup, 0)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_node_to_descendants(point2d(0, 2), tree, dup); + dsp("Propagate node to descendants : (point2d(0, 2), tree, dup)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_value_to_ancestors(117, tree, dup, 0); + dsp("Propagate value to ancestors : (117, tree, dup, 0)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_value_to_ancestors(117, tree, dup); + dsp("Propagate value to ancestors : (117, tree, dup)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_value_to_descendants(117, tree, dup, 0); + dsp("Propagate value to descendants : (117, tree, dup, 0)"); + display_tree_attributes(tree, dup); + + dup = duplicate(input); + morpho::tree::propagate_value_to_descendants(117, tree, dup); + dsp("Propagate value to descendants : (117, tree, dup)"); + display_tree_attributes(tree, dup); + + + + dup = duplicate(input); + + typedef morpho::tree::accumulator::max<tree_t, I> A; + A accu(dup); + morpho::tree::run_bkd(tree, accu); + + mln_bkd_piter_(tree_t::nodes_t) it_max = accu.to_result(); + morpho::tree::propagate_node_to_descendants(it_max, tree, dup, 69); + dsp("Propagate value to descendants : (it_max, tree, dup, 69)"); + display_tree_attributes(tree, dup); + + + + +} + + + Index: trunk/milena/sandbox/edwin/tree/propagate_value.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_value.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/propagate_value.hh (revision 3518) @@ -0,0 +1,231 @@ +// Copyright (C) 2007, 2008, 2009 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_PROPAGATE_VALUE_HH_ +# define MLN_MORPHO_TREE_PROPAGATE_VALUE_HH_ + + +/// \file mln/morpho/tree/propagate_value.hh +/// +/// Functions to propagate a value in the tree. + +namespace mln { + namespace morpho { + namespace tree { + + /** + ** Propagate the value \p v2 from node \p n having the value \p v + ** to its ancestors. + ** + ** @param v Value that node must have to be propagated. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + ** @param v2 Value to propagate (\p v by default). + */ + template <typename T, typename A> + void + propagate_value_to_ancestors(mln_value(A) v, + const T& t, + Image<A>& a_, + mln_value(A) v2); + + /** + ** Propagate the value \p v2 from node \p n having the value \p v + ** to its descendants. + ** + ** @param v Value that node must have to be propagated. + ** @param t Reference to components tree. + ** @param a_ Reference to image. + ** @param v2 Value to propagate (\p v by default). + */ + template <typename T, typename A> + void + propagate_value_to_descendants(mln_value(A) v, + const T& t, + Image<A>& a_, + mln_value(A) v2); + + + + + + + + + + namespace internal + { + template <typename T, typename A> + bool check_propagate_ancestors(const T& t, const A& a, mln_value(A) v) + { + mln_fwd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + if (a(n) == v && a(t.parent(n)) != v) + return false; + return true; + } + + template <typename T, typename A> + bool check_propagate_descendants(const T& t, const A& a, mln_value(A) v) + { + mln_fwd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + if (a(n) != v && a(t.parent(n)) == v) + return false; + return true; + } + + } // end of namespace mln::morpho::tree::internal + + template <typename T, typename A> + void + propagate_value_to_ancestors(mln_value(A) v, + const T& t, + Image<A>& a_, + mln_value(A) v2) + { + if (v == v2) + { + propagate_value_to_ancestors(v, t, a_); + return; + } + + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + + mln_ch_value(A, bool) deja_vu; + initialize(deja_vu, a); + data::fill(deja_vu, false); + + mln_fwd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + { + if (a(n) == v || deja_vu(n)) + { + mln_assertion(t.is_a_node(t.parent(n))); + a(t.parent(n)) = v2; + deja_vu(t.parent(n)) = true; + } + } + + mln_postcondition(internal::check_propagate_ancestors(t, a, v2)); + } + + + template <typename T, typename A> + void + propagate_value_to_ancestors(mln_value(A) v, + const T& t, + Image<A>& a_) + { + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + + mln_fwd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + { + if (a(n) == v) + { + mln_assertion(t.is_a_node(t.parent(n))); + a(t.parent(n)) = v; + } + } + + mln_postcondition(internal::check_propagate_ancestors(t, a, v)); + } + + + template <typename T, typename A> + void + propagate_value_to_descendants(mln_value(A) v, + const T& t, + Image<A>& a_, + mln_value(A) v2) + { + if (v == v2) + { + propagate_value_to_descendants(v, t, a_); + return; + } + + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + + mln_ch_value(A, bool) deja_vu; + initialize(deja_vu, a); + data::fill(deja_vu, false); + + mln_bkd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + { + if (a(n) == v) + { + mln_assertion(t.is_a_node(t.parent(n))); + deja_vu(n) = true; + } + else if (deja_vu(t.parent(n))) + { + mln_assertion(t.is_a_node(t.parent(n))); + a(n) = v2; + deja_vu(n) = true; + } + } + mln_postcondition(internal::check_propagate_descendants(t, a, v2)); + } + + template <typename T, typename A> + void + propagate_value_to_descendants(mln_value(A) v, + const T& t, + Image<A>& a_) + { + A& a = exact(a_); + mln_precondition(a.is_valid()); + mln_precondition(a.domain() == t.f().domain()); + + mln_bkd_piter(T::nodes_t) n(t.nodes()); + for_all(n) + { + if (a(t.parent(n)) == v) + { + mln_assertion(t.is_a_node(t.parent(n))); + a(n) = v; + } + } + mln_postcondition(internal::check_propagate_descendants(t, a, v)); + } + + + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln + +#endif /* !MLN_MORPHO_TREE_PROPAGATE_VALUE_HH_ */ Index: trunk/milena/sandbox/edwin/tree/Makefile =================================================================== --- trunk/milena/sandbox/edwin/tree/Makefile (revision 3517) +++ trunk/milena/sandbox/edwin/tree/Makefile (revision 3518) @@ -1,5 +1,5 @@ -TARGET=tree -SRC=tree.cc +TARGET=propagation +SRC=propagation.cc OBJS=${SRC:.cc=.o} OLENADIR=$(MLN_DIR)/.. @@ -7,7 +7,8 @@ CXXFLAGS=-I$(MILENADIR) -I./ -CXXFLAGS += -DNDEBUG -O1 +CXXFLAGS += -g -ggdb +#CXXFLAGS += -DNDEBUG -O1 CXX=g++ LD=g++