[Olena-patches] 3226: Prepare to fastest the morpho canvas of algebraic union find.

29 Jan 2009

https://svn.lrde.epita.fr/svn/oln/trunk/milena


Index: ChangeLog
from  Thierry Geraud  <thierry.geraud@lrde.epita.fr>

	Prepare to fastest the morpho canvas of algebraic union find.

	* mln/canvas/morpho/algebraic_union_find.hh
	(opening_attribute_functor_base): Remove; useless.
	(impl): New sub-namespace.
	(find_root, algebraic_union_find): Move into impl.
	(dispatch): New sub-namespace.
	(algebraic_union_find_dispatch): New.
	(algebraic_union_find): New facade.
	* mln/morpho/closing_attribute.hh
	(closing_attribute_t_f, closing_attribute_f): Remove dead code.
	(closing_attribute): Update.
	* mln/morpho/opening_attribute.hh
	(opening_attribute_t_f, opening_attribute_f): Remove dead code.
	(opening_attribute): Update.
	* tests/convert/impl/Makefile.am: New.
	* tests/convert/Makefile.am: Update.

 mln/canvas/morpho/algebraic_union_find.hh |  199 +++++-------------------------
 mln/morpho/closing_attribute.hh           |   94 --------------
 mln/morpho/opening_attribute.hh           |   91 -------------
 tests/convert/Makefile.am                 |    2 
 tests/convert/impl/Makefile.am            |   10 +
 5 files changed, 58 insertions(+), 338 deletions(-)

Index: mln/morpho/closing_attribute.hh

--- mln/morpho/closing_attribute.hh	(revision 3225)
+++ mln/morpho/closing_attribute.hh	(working copy)
@@ -100,6 +100,9 @@
     } // end of namespace mln::morpho::impl
 
 
+
+    // Facade.
+
     template <typename A, typename I, typename N>
     inline
     mln_concrete(I)
@@ -110,12 +113,9 @@
 
       mln_precondition(exact(input).is_valid());
 
-      mln_concrete(I) output;
-      initialize(output, input);
-
       typedef impl::closing_attribute_t<I, A> F;
       F f(input, lambda);
-      canvas::morpho::algebraic_union_find(input, nbh, f, output);
+      mln_concrete(I) output = canvas::morpho::algebraic_union_find(input, nbh, f);
 
       mln_postcondition(output >= input);
 
@@ -124,92 +124,6 @@
     }
 
 
-    /* -----------------------------------------------------------
-
-       Old code below.
-
-    namespace impl
-    {
-
-      template <typename A_,
-		typename I_, typename N_, typename O_>
-      struct closing_attribute_t_f
-      {
-	typedef mln_psite(I_) P;
-
-	// requirements from mln::canvas::morpho::algebraic_union_find
-
-	typedef A_ A;
-	typedef I_ I;
-	typedef N_ N;
-	typedef O_ O;
-	typedef p_array<P> S;
-	typedef util::pix<I> pix_t;
-
-	const I& input;
-	const N& nbh;
-	mln_result(A) lambda;
-	O& output;
-
-	const S s;
-
-	inline
-	void init()
-	{
-	  // FIXME: border::fill(input, mln_max(mln_value(I)));
-	  // FIXME: Shouldn't it be
-	  //   border::fill(input, mln_max(mln_value(I)))
-	  //   instead?
-	}
-
-	inline
-	bool is_active(const A& attr) const
-	{
-	  return attr.to_result() < lambda;
-	}
-
-	inline
-	void inactivate(A& attr)
-	{
-	  attr.set_value(lambda);
-	}
-
-	// end of requirements
-
-	inline
-	closing_attribute_t_f(const I_& input, const N_& nbh,
-			      mln_result(A) lambda, O_& output)
-	  : input(input), nbh(nbh), lambda(lambda), output(output),
-	    s(level::sort_psites_increasing(input))
-	{
-	}
-
-      };
-
-    } // end of namespace mln::morpho::impl
-
-
-    template <typename A,
-	      typename I, typename N, typename O>
-    inline
-    void closing_attribute_f(const Image<I>& input_,
-			     const Neighborhood<N>& nbh_, mln_result(A) lambda,
-			     Image<O>& output_)
-    {
-      const I& input = exact(input_);
-      const N& nbh = exact(nbh_);
-      O& output = exact(output_);
-      mln_precondition(output.domain() == input.domain());
-
-      typedef impl::closing_attribute_t_f<A,I,N,O> F;
-      F f(input, nbh, lambda, output);
-      canvas::morpho::algebraic_union_find_f<F> run(f);
-
-      mln_postcondition(output >= input);
-    }
-
-    */
-
 # endif // ! MLN_INCLUDE_ONLY
 
   } // end of namespace mln::morpho
Index: mln/morpho/opening_attribute.hh
--- mln/morpho/opening_attribute.hh	(revision 3225)
+++ mln/morpho/opening_attribute.hh	(working copy)
@@ -102,6 +102,8 @@
     } // end of namespace mln::morpho::impl
 
 
+    // Facade.
+
     template <typename A, typename I, typename N>
     inline
     mln_concrete(I)
@@ -112,101 +114,16 @@
 
       mln_precondition(exact(input).is_valid());
 
-      mln_concrete(I) output;
-      initialize(output, input);
-
       typedef impl::opening_attribute_t<I, A> F;
       F f(input, lambda);
-      canvas::morpho::algebraic_union_find(input, nbh, f, output);
+      mln_concrete(I) output = canvas::morpho::algebraic_union_find(input, nbh, f);
 
       mln_postcondition(output <= input);
+
       trace::exiting("morpho::opening_attribute");
       return output;
     }
 
-
-    // -----------------------------------------------------------
-    // Old code below.
-
-
-    namespace impl
-    {
-
-      template <typename A_,
-		typename I_, typename N_, typename O_>
-      struct opening_attribute_t_f
-      {
-	typedef mln_psite(I_) P;
-
-	// requirements from mln::canvas::morpho::algebraic_union_find
-
-	typedef A_ A;
-	typedef I_ I;
-	typedef N_ N;
-	typedef O_ O;
-	typedef p_array<P> S;
-	typedef util::pix<I> pix_t;
-
-	const I& input;
-	const N& nbh;
-	mln_result(A) lambda;
-	O& output;
-
-	const S s;
-
-	inline
-	void init()
-	{
-	  // FIXME: border::fill(input, mln_max(mln_value(I)));
-	}
-
-	inline
-	bool is_active(const A& attr) const
-	{
-	  return attr.to_result() < lambda;
-	}
-
-	inline
-	void inactivate(A& attr)
-	{
-	  attr.set_value(lambda);
-	}
-
-	// end of requirements
-
-	inline
-	opening_attribute_t_f(const I_& input, const N_& nbh,
-			    mln_result(A) lambda, O_& output)
-	  : input(input), nbh(nbh), lambda(lambda), output(output),
-	    s(level::sort_psites_decreasing(input))
-	{
-	}
-
-      };
-
-    } // end of namespace mln::morpho::impl
-
-
-    template <typename A,
-	      typename I, typename N, typename O>
-    inline
-    void opening_attribute_f(const Image<I>& input_,
-			     const Neighborhood<N>& nbh_, mln_result(A) lambda,
-			     Image<O>& output_)
-    {
-      const I& input = exact(input_);
-      const N& nbh = exact(nbh_);
-      O& output = exact(output_);
-      mln_precondition(output.domain() == input.domain());
-
-      typedef impl::opening_attribute_t_f<A,I,N,O> F;
-      F f(input, nbh, lambda, output);
-      canvas::morpho::algebraic_union_find_f<F> run(f);
-
-      mln_postcondition(output <= input);
-    }
-
-
 # endif // ! MLN_INCLUDE_ONLY
 
   } // end of namespace mln::morpho
Index: mln/canvas/morpho/algebraic_union_find.hh
--- mln/canvas/morpho/algebraic_union_find.hh	(revision 3225)
+++ mln/canvas/morpho/algebraic_union_find.hh	(working copy)
@@ -48,24 +48,13 @@
     namespace morpho
     {
 
-      // FIXME: Is it really needed?
-      struct opening_attribute_functor_base
+      namespace impl
       {
-	inline void init()			{}
-
-	template <typename A>
-	inline bool is_active(const A&) const	{ return false; }
-
-	template <typename A>
-	inline void inactivate(A&)		{}
-      };
-
 
       template <typename I>
-      static inline
+	inline
       mln_psite(I)
-      find_root(I& parent,
-		const mln_psite(I)& x)
+	find_root(I& parent, const mln_psite(I)& x)
       {
 	if (parent(x) == x)
 	  return x;
@@ -73,12 +62,12 @@
 	  return parent(x) = find_root(parent, parent(x));
       }
 
-      template <typename I, typename N, typename F, typename O>
-      void
+	template <typename I, typename N, typename F>
+	inline
+	mln_concrete(I)
       algebraic_union_find(const Image<I>& input_,
 			   const Neighborhood<N>& nbh_,
-			   F& f,
-			   Image<O>& output_)
+			     F& f)
       {
 	trace::entering("canvas::morpho::algebraic_union_find");
 
@@ -89,20 +78,20 @@
 
 	const I& input = exact(input_);
 	const N& nbh = exact(nbh_);
-	O& output = exact(output_);
 
-	mln_precondition(output.domain() == input.domain());
+	  mln_concrete(I) output;
+	  initialize(output, input);
 
 	// Local type.
 	typedef mln_psite(I) P;
 
 	// Auxiliary data.
-	mln_ch_value(O, bool)  deja_vu;
+	  mln_ch_value(I, bool)  deja_vu;
  	mln_ch_value(I, bool)  activity;
-	mln_ch_value(O, P)     parent;
-	mln_ch_value(O, A)     data;
+	  mln_ch_value(I, P)     parent;
+	  mln_ch_value(I, A)     data;
 
-	// init
+	  // Initialization.
 	{
 	  initialize(deja_vu, input);
 	  mln::data::fill(deja_vu, false);
@@ -113,7 +102,7 @@
 	  f.init(); // init required.
 	}
 
-	// first pass
+	  // First pass.
 	{
 	  mln_fwd_piter(S) p(f.s); // s required.
 	  mln_niter(N) n(nbh, p);
@@ -185,7 +174,7 @@
 	  }
 	}
 
-	// second pass
+	  // Second pass.
 	{
 	  mln_bkd_piter(S) p(f.s);
 	  for_all(p)
@@ -202,159 +191,47 @@
 	  mln::data::fill(output, input);
 	*/
 	trace::exiting("canvas::morpho::algebraic_union_find");
-      }
-
-
-      // -----------------------------------------------------------
-      // Old code below.
-
-      // General version.
-
-      template <typename F>
-      struct algebraic_union_find_f
-      {
-      	F& f;
-
-      	typedef typename F::I I;
-      	typedef typename F::N N;
-      	typedef typename F::O O;
-      	typedef typename F::S S;
-      	typedef typename F::A A;
-      	typedef mln_psite(I) psite;
 
-      	// aux:
-      	mln_ch_value(O, bool)  deja_vu;
-      	mln_ch_value(O, psite) parent;
-      	mln_ch_value(O, A)     data;
-
-      	algebraic_union_find_f(F& f)
-      	  : f(f)
-      	{
-      	  run();
+	  return output;
       	}
 
-      	void run()
-      	{
-      	  // init
-      	  {
-      	    initialize(deja_vu, f.input);
-      	    mln::data::fill(deja_vu, false);
-      	    initialize(parent, f.input);
-      	    initialize(data, f.input);
-      	    f.init();
-      	  }
-
-      	  // first pass
-      	  {
-      	    mln_fwd_piter(S) p(f.s);
-      	    mln_niter(N) n(f.nbh, p);
-      	    for_all(p)
-	    {
-	      make_set(p);
-	      for_all(n)
-		if (f.input.domain().has(n) && deja_vu(n))
-		  do_union(n, p);
-	      deja_vu(p) = true;
-	    }
-      	  }
-
-      	  // second pass
-      	  {
-      	    mln_bkd_piter(S) p(f.s);
-      	    for_all(p)
-      	      if (is_root(p))
-      		f.output(p) = f.input(p);
-      	      else
-      		f.output(p) = f.output(parent(p));
-      	  }
-
-      	  /*
-      	    Change 2nd pass into:
-	    for_all(p) if (not is_root(p)) f.output(p) = f.output(parent(p));
-      	    and add in init:
-	    mln::data::fill(f.output, f.input);
-	  */
-
-      	} // end of run()
-
-      	void make_set(const psite& p)
-      	{
-      	  parent(p) = p;
-      	  /* FIXME: What if the value_type of DATA (i.e., A) were not
-      	     based on a accu::count<mln::pix>?  Currently, nothing
-      	     enforces this, but the code below expects this line to be
-      	     valid:
-
-	     data(p).take_as_init(make::pix(f.input, p))
-
-      	     which probably restricts the kind of input images.
+      } // end of namespace mln::canvas::morpho::impl
 
-      	     If we want to be more generic, the initialization should
-      	     read something like:
 
-	     init_data(p);
 
-      	     i.e., the functor for the initialization of data should
-      	     be passed as an argument to the canvas' ctor.
+      // Dispatch.
 
-      	     Of course, we might want to restrict attributes to the
-      	     accumulator accu::count<mln::pix> (which is perfectly
-      	     acceptable), but then this class should statically check
-      	     the conformance of the template parameter A to this
-      	     constraint.  */
-      	  data(p).take_as_init(make::pix(f.input, p)); // FIXME: algebraic so p!
-      	}
-
-      	bool is_root(const psite& p) const
+      namespace internal
       	{
-      	  return parent(p) == p;
-      	}
 
-      	psite find_root(const psite& x)
+	template <typename I, typename N, typename F>
+	inline
+	mln_concrete(I)
+	algebraic_union_find_dispatch(trait::image::speed::any,
+				      const Image<I>& input,
+				      const Neighborhood<N>& nbh,
+				      F& f)
       	{
-      	  if (parent(x) == x)
-      	    return x;
-      	  else
-      	    return parent(x) = find_root(parent(x));
+	  return impl::algebraic_union_find(input, nbh, f);
       	}
 
-      	bool equiv(const psite& r, const psite& p)
-      	{
-      	  // Either a flat zone or the component of r is still growing.
-      	  return f.input(r) == f.input(p) || f.is_active(data(r));
-      	}
+      } // end of namespace mln::canvas::morpho::internal
 
-      	void do_union(const psite& n, const psite& p)
-      	{
-      	  psite r = find_root(n);
-      	  if (r != p)
-	  {
-	    if (equiv(r, p))
-	    {
-	      /* FIXME: Same remark as above concerning the
-		 initialization of data(p); instead of
 
-		 data(p).take(data(r));
 
-		 we should (or could) have
+      // Facade.
 
-		 unite_data(p, r);
-
-		 so as to keep the generic aspect of this canvas
-		 (as long as the set of acceptable types for the
-		 template parameter A is not bound).  */
-	      data(p).take(data(r));
-	      parent(r) = p;
-	    }
-	    else
-	      f.inactivate(data(p));
-	  }
+      template <typename I, typename N, typename F>
+      inline
+      mln_concrete(I)
+      algebraic_union_find(const Image<I>& input,
+			   const Neighborhood<N>& nbh,
+			   F& f)
+      {
+	return internal::algebraic_union_find_dispatch(mln_trait_image_speed(I)(),
+						       input, nbh, f);
       	}
 
-      };
-
-      // FIXME: Fast version.
-
 
     } // end of namespace mln::canvas::morpho
 
Index: tests/convert/impl/Makefile.am
--- tests/convert/impl/Makefile.am	(revision 0)
+++ tests/convert/impl/Makefile.am	(revision 0)
@@ -0,0 +1,10 @@
+## Process this file through Automake to create Makefile.in -*- Makefile -*-
+
+include $(top_srcdir)/milena/tests/tests.mk
+
+check_PROGRAMS =					\
+  from_site_set_to_image
+
+from_site_set_to_image_SOURCES = from_site_set_to_image.cc
+
+TESTS = $(check_PROGRAMS)
Index: tests/convert/Makefile.am
--- tests/convert/Makefile.am	(revision 3225)
+++ tests/convert/Makefile.am	(working copy)
@@ -2,6 +2,8 @@
 
 include $(top_srcdir)/milena/tests/tests.mk
 
+SUBDIRS = impl
+
 ##FIXME: re-enable all tests
 check_PROGRAMS =				\
   to_hsl 					\

    