URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-03-16 Edwin Carlinet &lt;carlinet(a)lrde.epita.fr&gt; Fix component tree test to work with new iterators. * mln/morpho/tree/compute_attribute_image.hh: Modify code to make it work with new tree implementation. * mln/morpho/tree/data.hh: Fix bug in preorder iterator (last element was ignored). * sandbox/edwin/tree/propagate_node.hh, * sandbox/edwin/tree/propagation.cc: Optimize propagation for new component tree implementation. * tests/morpho/tree/data.cc: Add some tests. --- mln/morpho/tree/compute_attribute_image.hh | 3 - mln/morpho/tree/data.hh | 61 +++++++++++++++------ sandbox/edwin/tree/propagate_node.hh | 84 +++-------------------------- sandbox/edwin/tree/propagation.cc | 44 +++++++-------- tests/morpho/tree/data.cc | 41 ++++++++++---- 5 files changed, 110 insertions(+), 123 deletions(-) Index: trunk/milena/tests/morpho/tree/data.cc =================================================================== --- trunk/milena/tests/morpho/tree/data.cc (revision 3536) +++ trunk/milena/tests/morpho/tree/data.cc (revision 3537) @@ -62,18 +62,39 @@ debug::println( "on node = ", t.parent_image() | t.nodes() ); { - std::cout << "nodes = "; - tree_t::nodes_t::fwd_piter p(t.nodes()); - for_all(p) - std::cout << p << ' '; - std::cout << std::endl; + /* Check site and node up order */ + tree_t::up_node_piter n(t); + tree_t::up_site_piter s(t); + n.start(); + for_all(s) + if (t.is_a_node(s)) + { + mln_assertion(s == n); + n.next(); + } + mln_assertion(!n.is_valid()); + } + + { + /* Check site and node up order */ + tree_t::dn_node_piter n(t); + tree_t::dn_site_piter s(t); + n.start(); + for_all(s) + if (t.is_a_node(s)) + { + mln_assertion(s == n); + n.next(); + } + mln_assertion(!n.is_valid()); } + + { std::cout << "nodes = "; - tree_t::fwd_piter p(t.domain()); - for_all(p) - if (t.is_a_node(p)) - std::cout << p << ' '; + tree_t::up_node_piter n(t); + for_all(n) + std::cout << n << ' '; std::cout << std::endl << std::endl; } @@ -82,7 +103,7 @@ { image2d<unsigned> area(ima.domain()); data::fill(area, 1); - tree_t::fwd_piter p(t.domain()); + tree_t::up_site_piter p(t); for_all(p) if (! t.is_root(p)) area(t.parent(p)) += area(p); Index: trunk/milena/mln/morpho/tree/compute_attribute_image.hh =================================================================== --- trunk/milena/mln/morpho/tree/compute_attribute_image.hh (revision 3536) +++ trunk/milena/mln/morpho/tree/compute_attribute_image.hh (revision 3537) @@ -36,6 +36,7 @@ /// \todo Specialize for low quant (and try fastest). # include <mln/core/concept/image.hh> +# include <mln/morpho/tree/data.hh> # include <mln/trait/accumulators.hh> # include <mln/util/pix.hh> # include <mln/data/fill.hh> @@ -143,7 +144,7 @@ take_as_init(acc(p), t.f(), p); } { - mln_fwd_piter(T) p(t.domain()); + mln_up_site_piter(T) p(t); // Propagate attribute from a site to its parent. for_all(p) if (! t.is_root(p)) Index: trunk/milena/mln/morpho/tree/data.hh =================================================================== --- trunk/milena/mln/morpho/tree/data.hh (revision 3536) +++ trunk/milena/mln/morpho/tree/data.hh (revision 3537) @@ -38,7 +38,6 @@ /// learn why we want the 1st pass to be in forward scan of s). # include <mln/morpho/tree/compute_parent.hh> -//# include <mln/core/image/sub_image.hh> # include <mln/core/site_set/p_array.hh> # include <mln/core/internal/site_set_iterator_base.hh> # include <mln/core/internal/piter_identity.hh> @@ -56,10 +55,6 @@ # define mln_dn_node_piter_(T) T::dn_node_piter # define mln_preorder_piter_(T) T::preorder_piter -// FIXME: rename these iterators. -//# define mln_up_leaf_piter(T) typename T::up_leaf_piter; -//# define mln_dn_leaf_piter(T) typename T::dn_leaf_piter; - namespace mln { @@ -139,15 +134,8 @@ /// \} - const p_array<mln_psite(I)>& children(const mln_psite(I)& p) const - { - return children_(p); - } - - const mln_ch_value(I, nodes_t)& children_image() const - { - return children_; - } + const p_array<mln_psite(I)>& children(const mln_psite(I)& p) const; + const mln_ch_value(I, nodes_t)& children_image() const; /// \{ Tests. @@ -290,6 +278,10 @@ /// Constructor. preorder_piter(const T& t); + + preorder_piter(const T& t, + const mln_psite(T::function)& p); + /// Test if the iterator is valid. bool is_valid_() const; @@ -305,7 +297,8 @@ protected: using super_::p_; using super_::s_; - std::deque<mln_psite(T)> stack_; // FIXME: implement p_stack. + std::deque<mln_psite(T::function)> stack_; // FIXME: implement p_stack. + const mln_psite(T::function)* root_; }; @@ -455,6 +448,22 @@ return f_(p); } + template <typename I, typename S> + inline + const p_array<mln_psite(I)>& + data<I,S>::children(const mln_psite(I)& p) const + { + return children_(p); + } + + template <typename I, typename S> + inline + const mln_ch_value(I, p_array<mln_psite(I)>)& + data<I,S>::children_image() const + { + return children_; + } + // Iterators. @@ -463,12 +472,23 @@ template <typename T> inline preorder_piter<T>::preorder_piter() + : root_ (0) { } template <typename T> inline preorder_piter<T>::preorder_piter(const T& t) + : root_ (0) + { + this->change_target(t); + } + + template <typename T> + inline + preorder_piter<T>::preorder_piter(const T& t, + const mln_psite(T::function)& p) + : root_ (&p) { this->change_target(t); } @@ -495,7 +515,13 @@ preorder_piter<T>::start_() { this->invalidate(); - mln_dn_node_piter(T) n(s_->nodes()); + stack_.push_back(mln_psite(T::function)()); // needed for last element. + + if (root_) + stack_.push_back(*root_); + else + { + mln_dn_node_piter(T) n(*s_); int roots = 0; for (n.start(); n.is_valid() && roots < s_->nroots(); n.next()) if (s_->is_root(n)) @@ -503,6 +529,7 @@ stack_.push_back(n); roots++; } + } this->next(); } @@ -514,6 +541,8 @@ { p_ = stack_.back(); stack_.pop_back(); + if (!exact(this)->is_valid()) + return; mln_fwd_piter(T::nodes_t) child(s_->children(p_)); for_all(child) stack_.push_back(child); Index: trunk/milena/sandbox/edwin/tree/propagate_node.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 3536) +++ trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 3537) @@ -31,6 +31,7 @@ #include <mln/morpho/tree/data.hh> #include <mln/core/site_set/p_array.hh> +#include <stack> /// \file mln/morpho/tree/propagate_node.hh /// @@ -44,35 +45,6 @@ /** ** 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_dn_node_piter(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_dn_node_piter(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. @@ -127,51 +99,10 @@ Image<A>& a_); - - - +# ifndef MLN_INCLUDE_ONLY /* Descendants propagation */ - template <typename T, typename A> - void - propagate_node_to_descendants(mln_dn_node_piter(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_dn_node_piter(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 @@ -188,9 +119,13 @@ if (!t.is_a_node(n)) // Get the representant. n = t.parent(n); + mln_assertion(t.is_a_node(n)); + + typename T::preorder_piter pp(t, n); - mln_dn_node_piter(T) it(find_bkd(t.nodes(), n)); - propagate_node_to_descendants(it, t, a, v); + pp.start(); // We don't set n to v. + for (pp.next(); pp.is_valid(); pp.next()) + a(pp) = v; } template <typename T, typename A> @@ -220,7 +155,7 @@ mln_precondition(a.domain() == t.f().domain()); mln_precondition(a.domain().has(n)); - if (!t.is_a_node(n)) + if (!t.is_a_node(n)) // Get the representant. n = t.parent(n); mln_assertion(t.is_a_node(n)); @@ -245,6 +180,7 @@ propagate_node_to_ancestors(n, t, a, a(n)); } +# endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho::tree } // end of namespace mln::morpho Index: trunk/milena/sandbox/edwin/tree/propagation.cc =================================================================== --- trunk/milena/sandbox/edwin/tree/propagation.cc (revision 3536) +++ trunk/milena/sandbox/edwin/tree/propagation.cc (revision 3537) @@ -90,25 +90,25 @@ 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); +// 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); @@ -123,9 +123,9 @@ dsp("Propagate value to descendants : (it_max, tree, dup, 69)"); display_tree_attributes(tree, dup); - mln_dn_node_piter_(tree_t) n(tree); - n.start(); - print(tree.children_image(), n); +// mln_dn_node_piter_(tree_t) n(tree); +// n.start(); +// print(tree.children_image(), n); std::cout << "\n"; mln_preorder_piter_(tree_t) pit(tree);