Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Implementations for each canvas propositions. * oln/morpho/cc_tarjan.hh: Rename union_find_procedure. * oln/morpho/union_find.hh: Update. * oln/morpho/union_find_v2.hh: New. * oln/morpho/union_find_procedure.hh: New. * oln/morpho/union_find_v3.hh: New. * oln/morpho/union_find_v4.hh: New. * oln/canvas/two_pass.hh: update. canvas/two_pass.hh | 57 ++++++++++++++++-- morpho/union_find.hh | 6 - morpho/union_find_v2.hh | 145 +++++++++++++++++++++++++++++++++++++++++++++++ morpho/union_find_v3.hh | 147 ++++++++++++++++++++++++++++++++++++++++++++++++ morpho/union_find_v4.hh | 147 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 493 insertions(+), 9 deletions(-) Index: oln/morpho/union_find.hh --- oln/morpho/union_find.hh (revision 962) +++ oln/morpho/union_find.hh (working copy) @@ -90,7 +90,7 @@ void init() { - level::fill(is_processed, false); + level::fill(inplace(is_processed), false); } void first_pass_body(const oln_point(I)& p) @@ -98,7 +98,7 @@ parent(p) = p; if ( input(p) ) { - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) { if ( input(n) == true and is_processed(n) ) @@ -133,7 +133,7 @@ union_find(const Image_with_Nbh<I>& input) { impl::union_find_<I> f(exact(input)); - canvas::two_pass(f, input); + canvas::v1::two_pass(f); return f.output; } Index: oln/morpho/union_find_v2.hh --- oln/morpho/union_find_v2.hh (revision 0) +++ oln/morpho/union_find_v2.hh (revision 0) @@ -0,0 +1,145 @@ +// 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 receiv 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 OLN_MORPHO_UNION_FIND_HH +# define OLN_MORPHO_UNION_FIND_HH + +# include <oln/core/concept/image.hh> + +# include <oln/canvas/two_pass.hh> +# include <oln/level/fill.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I> + struct union_find_ + { + oln_plain_value(I, unsigned) output; + + oln_plain(I) is_processed; + oln_plain_value(I, oln_point(I)) parent; + + union_find_(I in) + { + prepare(is_processed, with, in); + prepare(output, with, in); + prepare(parent, with, in); + } + + oln_point(I) + find_root(const I& ima, + const oln_point(I)& x, + oln_plain_value(I, oln_point(I))& parent) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x), parent); + return parent(x); + } + return x; + } + + void + do_union(const I& ima, + const oln_point(I)& n, + const oln_point(I)& p, + oln_plain_value(I, oln_point(I))& parent) + { + oln_point(I) r = find_root(ima, n, parent); + if (r != p) + parent(r) = p; + } + + void init() + { + level::fill(inplace(is_processed), false); + } + + void first_pass_body(const oln_point(I)& p, I input) + { + parent(p) = p; + if ( input(p) ) + { + oln_niter(I) n(input, p); + for_all(n) + { + if ( input(n) == true and is_processed(n) ) + do_union(input, n, p, parent); + } + is_processed(p) = true; + } + + } + + void second_pass_body(const oln_point(I)& p, I input) + { + unsigned current_label = 0; + if ( input(p) == true and parent(p) == p ) + output(p) = ++current_label; + else + output(p) = output(parent(p)); + } + + void final() + { + + }; + + } // end of namespace oln::morpho::impl + +// Facades. + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input) + { + impl::union_find_<I> f(exact(input)); + canvas::v2::two_pass(f, input); + return f.output; + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_UNION_FIND_HH Index: oln/morpho/union_find_v3.hh --- oln/morpho/union_find_v3.hh (revision 0) +++ oln/morpho/union_find_v3.hh (revision 0) @@ -0,0 +1,147 @@ +// 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 receiv 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 OLN_MORPHO_UNION_FIND_HH +# define OLN_MORPHO_UNION_FIND_HH + +# include <oln/core/concept/image.hh> + +# include <oln/canvas/two_pass.hh> +# include <oln/level/fill.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + template <typename I> + struct union_find_ + { + const I& input; + oln_plain_value(I, unsigned) output; + + oln_plain(I) is_processed; + oln_plain_value(I, oln_point(I)) parent; + + union_find_(const I& in) + : input(in) + { + prepare(is_processed, with, in); + prepare(output, with, in); + prepare(parent, with, in); + } + + oln_point(I) + find_root(const I& ima, + const oln_point(I)& x, + oln_plain_value(I, oln_point(I))& parent) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x), parent); + return parent(x); + } + return x; + } + + void + do_union(const I& ima, + const oln_point(I)& n, + const oln_point(I)& p, + oln_plain_value(I, oln_point(I))& parent) + { + oln_point(I) r = find_root(ima, n, parent); + if (r != p) + parent(r) = p; + } + + void init() + { + level::fill(inplace(is_processed), false); + } + + void first_pass_body(const oln_point(I)& p) + { + parent(p) = p; + if ( input(p) ) + { + oln_niter(I) n(input, p); + for_all(n) + { + if ( input(n) == true and is_processed(n) ) + do_union(input, n, p, parent); + } + is_processed(p) = true; + } + + } + + void second_pass_body(const oln_point(I)& p) + { + unsigned current_label = 0; + if ( input(p) == true and parent(p) == p ) + output(p) = ++current_label; + else + output(p) = output(parent(p)); + } + + void final() + { + } + + }; + + } // end of namespace oln::morpho::impl + +// Facades. + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input) + { + impl::union_find_<I> f(exact(input)); + canvas::v1::two_pass(f); + return f.output; + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_UNION_FIND_HH Index: oln/morpho/union_find_v4.hh --- oln/morpho/union_find_v4.hh (revision 0) +++ oln/morpho/union_find_v4.hh (revision 0) @@ -0,0 +1,147 @@ +// 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 receiv 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 OLN_MORPHO_UNION_FIND_HH +# define OLN_MORPHO_UNION_FIND_HH + +# include <oln/core/concept/image.hh> + +# include <oln/canvas/two_pass.hh> +# include <oln/level/fill.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + template <typename I> + struct union_find_ + { + const I& input; + oln_plain_value(I, unsigned) output; + + oln_plain(I) is_processed; + oln_plain_value(I, oln_point(I)) parent; + + union_find_(const I& in) + : input(in) + { + prepare(is_processed, with, in); + prepare(output, with, in); + prepare(parent, with, in); + } + + oln_point(I) + find_root(const I& ima, + const oln_point(I)& x, + oln_plain_value(I, oln_point(I))& parent) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x), parent); + return parent(x); + } + return x; + } + + void + do_union(const I& ima, + const oln_point(I)& n, + const oln_point(I)& p, + oln_plain_value(I, oln_point(I))& parent) + { + oln_point(I) r = find_root(ima, n, parent); + if (r != p) + parent(r) = p; + } + + void init() + { + level::fill(inplace(is_processed), false); + } + + void first_pass_body(const oln_point(I)& p) + { + parent(p) = p; + if ( input(p) ) + { + oln_niter(I) n(input, p); + for_all(n) + { + if ( input(n) == true and is_processed(n) ) + do_union(input, n, p, parent); + } + is_processed(p) = true; + } + + } + + void second_pass_body(const oln_point(I)& p) + { + unsigned current_label = 0; + if ( input(p) == true and parent(p) == p ) + output(p) = ++current_label; + else + output(p) = output(parent(p)); + } + + void final() + { + } + + }; + + } // end of namespace oln::morpho::impl + +// Facades. + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Image_with_Nbh<I>& input) + { + impl::union_find_<I> f(exact(input)); + canvas::v1::two_pass(f); + return f.output; + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_UNION_FIND_HH Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 962) +++ oln/canvas/two_pass.hh (working copy) @@ -25,6 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. +# include <oln/core/concept/image.hh> + #ifndef OLN_CANVAS_TWO_PASS_HH # define OLN_CANVAS_TWO_PASS_HH @@ -34,10 +36,10 @@ namespace v1 { template <template <class> class F, - typename I> + typename I> // Data owned by f. void two_pass(F<I> f) { - mlc::assert_< mlc_is_a(I, Image) >::check(); +// mlc::assert_< mlc_is_a(I, Image) >::check(); f.init(); @@ -55,12 +57,12 @@ } } - namespace v2 + namespace v2 // Data owned by f but not input { template <typename F, typename I> void two_pass(F f, I input) { - mlc::assert_< mlc_is_a(I, Image) >::check(); +// mlc::assert_< mlc_is_a(I, Image) >::check(); f.init(input); @@ -78,12 +80,12 @@ } } - namespace v3 + namespace v3 // Auxiliar data given as argument. { template <typename F, typename I, typename A> void two_pass(F f, I input, A aux) { - mlc::assert_< mlc_is_a(I, Image) >::check(); +// mlc::assert_< mlc_is_a(I, Image) >::check(); f.init(input, aux); @@ -101,6 +103,49 @@ } } + + namespace v4 // Via Inheritens. + { + + template <typename I> + class two_pass + { + + void init(I input) { } + + void final(I input) { } + + void first_pass_body(const oln_point(I)& p) + { + assert (0 && "two_pass canvas : procedure 'void first_pass_body(const oln_point(I)& p)' must be defined"); + } + + void second_pass_body(const oln_point(I)& p) + { + assert (0 && "two_pass canvas : procedure 'void second_pass_body(const oln_point(I)& p)' must be defined"); + } + + void run(I input) + { + init(input); + + // first pass + oln_fwd_piter(I) p1(input.points()); + for_all(p1) + first_pass_body(p1, input); + + // second pass + oln_bkd_piter(I) p2(input.points()); + for_all(p2) + second_pass_body(p2, input); + + final(input); + } + + }; + + } + } #endif // ! OLN_CANVAS_TWO_PASS_HH