URL:
https://svn.lrde.epita.fr/svn/oln/trunk/milena
ChangeLog:
2007-10-26 Matthieu Garrigues <garrigues(a)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