URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-26 Matthieu Garrigues <garrigues@lrde.epita.fr> Add iterator for branches. * mln/util/branch_iter.hh: To iterate on branch. * mln/util/tree.hh: Add branch class, fix tree. * mln/util/tree_to_image.hh: Fix. * mln/value/concept/built_in.hh: Add a forward declaration. * sandbox/garrigues/fllt.hh: Update. * tests/branch_iter.cc: Test for branch_iter. --- mln/util/branch_iter.hh | 161 ++++++++++++++++++++++++++++++++++++++++++ mln/util/tree.hh | 98 ++++++++++++++++++++++--- mln/util/tree_to_image.hh | 3 mln/value/concept/built_in.hh | 1 sandbox/garrigues/fllt.hh | 43 +++++++++-- tests/branch_iter.cc | 68 +++++++++++++++++ 6 files changed, 354 insertions(+), 20 deletions(-) Index: trunk/milena/tests/branch_iter.cc =================================================================== --- trunk/milena/tests/branch_iter.cc (revision 0) +++ trunk/milena/tests/branch_iter.cc (revision 1393) @@ -0,0 +1,68 @@ +// 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/branch_iter.cc + * + * \brief test of mln::util::branch_iter + * + */ + +#include <mln/core/image2d.hh> +#include <mln/util/tree.hh> +#include <mln/util/branch_iter.hh> + +int main() +{ + using namespace mln; + + util::node<int> n(11); + + util::tree<int> t(&n); + + util::node<int>* f = n.add_child(42); + + util::node<int>* g = f->add_child(421); + util::node<int>* h = f->add_child(422); + + g->add_child(4211)->add_child(51)->add_child(52)->add_child(53)->add_child(54)->add_child(55); + g->add_child(4212); + + f->add_child(4221); + f->add_child(4222); + + n.add_child(43); + + util::branch<int> b(t, n); + + std::vector< util::node<int>* >::iterator it; + util::branch_iter<int> p(b); + for_all(p) + { + std::cout << "parcour : " << util::node<int>(p).elt() << std::endl; + } +} Index: trunk/milena/mln/value/concept/built_in.hh =================================================================== --- trunk/milena/mln/value/concept/built_in.hh (revision 1392) +++ trunk/milena/mln/value/concept/built_in.hh (revision 1393) @@ -42,6 +42,7 @@ namespace value { + template <typename B> struct Built_In; // Category flag type. template <> struct Built_In<void> // No inheritance here since this category is special (on the side). Index: trunk/milena/mln/util/tree_to_image.hh =================================================================== --- trunk/milena/mln/util/tree_to_image.hh (revision 1392) +++ trunk/milena/mln/util/tree_to_image.hh (revision 1393) @@ -65,9 +65,8 @@ mln_piter(set_p<point2d>) p(node->elt_.points); for_all(p) - { output(p) = node->elt_.value; - } + typename std::vector< util::node<T>* >::const_iterator it = node->child_.begin(); for (int i = 0; Index: trunk/milena/mln/util/tree.hh =================================================================== --- trunk/milena/mln/util/tree.hh (revision 1392) +++ trunk/milena/mln/util/tree.hh (revision 1393) @@ -45,15 +45,34 @@ namespace util { + /// Fwd declarations. + template <typename T> class node; + template <typename T> class tree; + template <typename T> class branch; + template <typename T> - struct node + class node { + public: + + /// \{ Constructors node(); - node(T& elt); + node(T elt); + /// \} + + /// \{ Acccess to the element. + T& elt(); + const T& elt() const; + /// \} + + /// Access to the children + const std::vector< node<T>* >& children() const; + std::vector< node<T>* >& children(); - T& content(); - const T& content() const; - node<T>* add_child(T& elt); + /// Access to the parent node. + const node<T>* parent() const; + + node<T>* add_child(T elt); void set_parent(node<T>* parent); node<T>* get_parent(); void print_rec(int n) const; @@ -61,14 +80,17 @@ int search_rec(node<T>** res, T& elt); node<T>* search(T& elt); + private: + //FIXME tree<T>& tree_; T elt_; node<T>* parent_; std::vector< node<T>* > child_; }; template <typename T> - struct tree + class tree { + public: typedef node<T> node_t; tree(); tree(node<T>* root); @@ -77,9 +99,26 @@ void add_tree_up (T& elt); void add_tree_down (T& elt); + private: node<T>* root_; }; + + template <typename T> + class branch + { + public: + branch(tree<T>& tree, node<T>& apex); + + node<T>& apex(); + tree<T>& tree(); + + private: + node<T>& apex_; + util::tree<T>& tree_; + }; + + # ifndef MLN_INCLUDE_ONLY template <typename T> @@ -131,7 +170,7 @@ } template <typename T> - node<T>::node(T& elt) + node<T>::node(T elt) : elt_ (elt), parent_ (0) { @@ -139,21 +178,36 @@ template <typename T> const T& - node<T>::content() const + node<T>::elt() const { return elt_; } template <typename T> T& - node<T>::content() + node<T>::elt() { return elt_; } + + template <typename T> + std::vector< node<T>* >& + node<T>::children() + { + return child_; + } + + template <typename T> + const std::vector< node<T>* >& + node<T>::children() const + { + return child_; + } + template <typename T> node<T>* - node<T>::add_child(T& elt) + node<T>::add_child(T elt) { node<T>* s = new node<T>(elt); @@ -211,6 +265,30 @@ return 0; } + // Branch methods + template <typename T> + branch<T>::branch(util::tree<T>& tree, + util::node<T>& apex) + : tree_(tree), + apex_(apex) + { + } + + + template <typename T> + util::node<T>& + branch<T>::apex() + { + return apex_; + } + + template <typename T> + util::tree<T>& + branch<T>::tree() + { + return tree_; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::util Index: trunk/milena/mln/util/branch_iter.hh =================================================================== --- trunk/milena/mln/util/branch_iter.hh (revision 0) +++ trunk/milena/mln/util/branch_iter.hh (revision 1393) @@ -0,0 +1,161 @@ +// 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_BRANCH_ITER_HH +# define MLN_UTIL_BRANCH_ITER_HH + +# include <stack> +# include <mln/util/tree.hh> +/*! + * \file mln/util/branch.hh + * + * \brief Definition of a iterator on branch. + * + */ + +namespace mln +{ + + namespace util + { + template <typename T> + class branch_iter + { + public: + branch_iter(branch<T> branch); + + /// Convertion to node. + operator node<T>&() const; + + /// Test the iterator validity. + bool is_valid() const; + + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next point. + void next(); + + + private: + util::branch<T> branch_; + + typedef typename std::vector< util::node<T>* >::iterator child_iter; + typedef std::pair<child_iter, child_iter> iter_pair; + /// Store child().begin() and child().end(). + std::stack< iter_pair > s_; + + util::node<T>* n_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename T> + branch_iter<T>::branch_iter(branch<T> branch) + : branch_(branch) + { + invalidate(); + } + + template <typename T> + branch_iter<T>::operator node<T>&() const + { + mln_assertion(n_); + return *n_; + } + + template <typename T> + bool + branch_iter<T>::is_valid() const + { + return n_ != 0; + } + + template <typename T> + void + branch_iter<T>::invalidate() + { + n_ = 0; + } + + + template <typename T> + void + branch_iter<T>::start() + { + s_.push(iter_pair(branch_.apex().children().begin(), + branch_.apex().children().end())); + n_ = &branch_.apex(); + + //n_ = *(s_.top().first); + //s_.top().first++; + } + + template <typename T> + void + branch_iter<T>::next() + { + if (s_.size() == 0) + invalidate(); + else + { + if (s_.top().first == s_.top().second) + //if (*(s_.top().first) == 0) + { + mln_assertion(n_); + s_.pop(); + next(); + return; + } + else + { + n_ = *(s_.top().first); + s_.top().first++; + + mln_assertion(n_); + if (n_->children().size() > 0) + s_.push(iter_pair(n_->children().begin(), + n_->children().end())); + return; + } + } + } + +# endif // ! MLN_INCLUDE_ONLY + + + } + +} // end of namespace mln + + +#endif // !MLN_UTIL_BRANCH_HH Index: trunk/milena/sandbox/garrigues/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt.hh (revision 1392) +++ trunk/milena/sandbox/garrigues/fllt.hh (revision 1393) @@ -246,10 +246,10 @@ // FIXME : we can make it faster. mln_piter(set_p<P>) p(R); current_region = new fllt_node(P, V)(); - current_region->content().value = g; + current_region->elt().value = g; for_all(p) { - current_region->content().points.insert(p); + current_region->elt().points.insert(p); if (regions(p) == 0) regions(p) = current_region; else @@ -281,7 +281,7 @@ // and which are the holes. Keep one pixel of each holes. // WARNING : We trust labeling::level to label the exterior border with 1. - current_region->content().holes.insert(a_point_of(tmp | pw::value(tmp) == pw::cst(n))); + current_region->elt().holes.insert(a_point_of(tmp | pw::value(tmp) == pw::cst(n))); // FIXME : [optimisation] Remove from N border of holes???. // Recompute gn <- min u(x) x belongs to A @@ -469,7 +469,7 @@ // debug::println(regions); - //debug::println(ima | regions(make:defined reference to `mln::fllt::lower<mln::value::int_u<8u> >::inc':point2d(-4,-1))->content().points); + //debug::println(ima | regions(make:defined reference to `mln::fllt::lower<mln::value::int_u<8u> >::inc':point2d(-4,-1))->elt().points); return (&tree); @@ -530,10 +530,38 @@ static const neighb2d& reg_nbh() { return c8(); } }; + +// template <> +// void find_shape_of_holes(fllt_node(P, V)* lower, +// fllt_node(P, V)* upper) +// { +// } + template <typename P, typename V> - void find_shapes_of_holes(fllt_node(P, V)* lower, + void merge_trees(fllt_node(P, V)* lower, fllt_node(P, V)* upper) { + + // In order to merge the trees, we only have to find for each shape S + // with a hole H in it whether one of its children has a hole HŽ + // containing H. If it is the case, we do nothing. Otherwise, we + // put the shape of the hole H (and all its descendants) as child of + // the shape . + + fllt_node(P, V)* it = lower; + + if (lower->elt().holes.size() > 0) + { + + } + // FIXME : add an method to tree to get the childen. + // FIXME : add an iterator to browse a tree. + + mln_piter(set_p<P>) p(lower->child_); + for_all(p) + { + merge_trees(lower, upper); + } } template <typename V> @@ -546,10 +574,9 @@ fllt_tree(P, V)* lower_tree; lower_tree = compute_level_set<V, lower<V> >(ima); + upper_tree = compute_level_set<V, upper<V> >(ima); - // upper_tree = compute_level_set<V, upper<V> >(ima); - - //find_shapes_of_holes(lower_tree, upper_tree); + merge_trees(lower_tree, upper_tree); } } // end of namespace mln::fllt