July 2008 - Olena-patches

2093: Improve classical points typedefs.
by Roland Levillain 22 Jul '08

22 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Improve classical points typedefs. * milena/mln/core/point1d.hh, * milena/mln/core/point2d.hh, * milena/mln/core/point2d_h.hh, * milena/mln/core/point3d.hh: Include mln/core/grids.hh. Use fully qualified type names to help swig wrap these typedefs. point1d.hh | 18 ++++++++---------- point2d.hh | 18 ++++++++---------- point2d_h.hh | 17 ++++++++--------- point3d.hh | 16 +++++++--------- 4 files changed, 31 insertions(+), 38 deletions(-) Index: milena/mln/core/point1d.hh --- milena/mln/core/point1d.hh (revision 2093) +++ milena/mln/core/point1d.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,22 +28,20 @@ #ifndef MLN_CORE_POINT1D_HH # define MLN_CORE_POINT1D_HH -/*! \file mln/core/point1d.hh - * - * \brief Definition of the mln::point1d alias and of its construction - * routine. - */ +/// \file mln/core/point1d.hh +/// \brief Definition of the mln::point1d alias and of its construction +/// routine. # include <mln/core/point.hh> +# include <mln/core/grids.hh> namespace mln { - /*! \brief Type alias for a point defined on the 1D square grid with - * integer coordinates. - */ - typedef point_<grid::tick, int> point1d; + /// \brief Type alias for a point defined on the 1D square grid with + /// integer coordinates. + typedef point_<mln::grid::tick, int> point1d; } // end of namespace mln Index: milena/mln/core/point3d.hh --- milena/mln/core/point3d.hh (revision 2093) +++ milena/mln/core/point3d.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,21 +28,19 @@ #ifndef MLN_CORE_POINT3D_HH # define MLN_CORE_POINT3D_HH -/*! \file mln/core/point3d.hh - * - * \brief Definition of the mln::point3d alias and of its construction - * routine. - */ +/// \file mln/core/point3d.hh +/// \brief Definition of the mln::point3d alias and of its construction +/// routine. # include <mln/core/point.hh> +# include <mln/core/grids.hh> namespace mln { - /*! \brief Type alias for a point defined on the 3D square grid with - * integer coordinates. - */ + /// \brief Type alias for a point defined on the 3D square grid with + /// integer coordinates. typedef point_<grid::cube, int> point3d; Index: milena/mln/core/point2d.hh --- milena/mln/core/point2d.hh (revision 2093) +++ milena/mln/core/point2d.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,22 +28,20 @@ #ifndef MLN_CORE_POINT2D_HH # define MLN_CORE_POINT2D_HH -/*! \file mln/core/point2d.hh - * - * \brief Definition of the mln::point2d alias and of its construction - * routine. - */ +/// \file mln/core/point2d.hh +/// \brief Definition of the mln::point2d alias and of its construction +/// routine. # include <mln/core/point.hh> +# include <mln/core/grids.hh> namespace mln { - /*! \brief Type alias for a point defined on the 2D square grid with - * integer coordinates. - */ - typedef point_<grid::square, int> point2d; + /// \brief Type alias for a point defined on the 2D square grid with + /// integer coordinates. + typedef point_<mln::grid::square, int> point2d; } // end of namespace mln Index: milena/mln/core/point2d_h.hh --- milena/mln/core/point2d_h.hh (revision 2093) +++ milena/mln/core/point2d_h.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,21 +28,20 @@ #ifndef MLN_CORE_POINT2D_H_HH # define MLN_CORE_POINT2D_H_HH -/*! \file mln/core/point2d_h.hh - * - * \brief Definition of the mln::point2d_h alias and of its construction - * routine. - */ +/// \file mln/core/point2d_h.hh +/// \brief Definition of the mln::point2d_h alias and of its construction +/// routine. + # include <mln/core/point.hh> +# include <mln/core/grids.hh> namespace mln { - /*! \brief Type alias for a point defined on the 2D square grid with - * integer coordinates. - */ + /// \brief Type alias for a point defined on the 2D hexagonal grid + /// with integer coordinates. typedef point_<grid::hexa, int> point2d_h;

1 1

2095: Fix ChangeLogs
by Roland Levillain 22 Jul '08

22 Jul '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk Index: milena/ChangeLog =================================================================== --- milena/ChangeLog (revision 2094) +++ milena/ChangeLog (revision 2095) @@ -1,3 +1,14 @@ +2008-07-22 Roland Levillain <roland(a)lrde.epita.fr> + + Improve classical points typedefs. + + * mln/core/point1d.hh, + * mln/core/point2d.hh, + * mln/core/point2d_h.hh, + * mln/core/point3d.hh: + Include mln/core/grids.hh. + Use fully qualified type names to help swig wrap these typedefs. + 2008-07-21 Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Add lazy_image type. Index: ChangeLog =================================================================== --- ChangeLog (revision 2094) +++ ChangeLog (revision 2095) @@ -1,37 +1,3 @@ -2008-07-22 Roland Levillain <roland(a)lrde.epita.fr> - - Improve classical points typedefs. - - * milena/mln/core/point1d.hh, - * milena/mln/core/point2d.hh, - * milena/mln/core/point2d_h.hh, - * milena/mln/core/point3d.hh: - Include mln/core/grids.hh. - Use fully qualified type names to help swig wrap these typedefs. - -2008-07-22 Roland Levillain <roland(a)lrde.epita.fr> - -A build-aux/pypath.m4 -A build-aux/swig.m4 -A build-aux/with-swilena.m4 -A swilena -A swilena/Makefile.am -A swilena/image2d.i -A swilena/python -A swilena/python/Makefile.am -A swilena/python/ltihooks.py -A swilena/python/test.py -A swilena/run.in -A swilena/run.mk -M Makefile.am -M configure.ac - -M milena/mln/core/point1d.hh -M milena/mln/core/point2d.hh -M milena/mln/core/point2d_h.hh -M milena/mln/core/point3d.hh - - 2008-06-23 Roland Levillain <roland(a)lrde.epita.fr> Update external/README.

1 0

2092: Add lazy_image type.
by Ugo Jardonnet 21 Jul '08

21 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Add lazy_image type. * mln/core/lazy_image.hh: New Image type. Compute values on the fly. lazy_image.hh | 209 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+) Index: mln/core/lazy_image.hh --- mln/core/lazy_image.hh (revision 0) +++ mln/core/lazy_image.hh (revision 0) @@ -0,0 +1,209 @@ +// 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_CORE_LAZY_IMAGE_HH +# define MLN_CORE_LAZY_IMAGE_HH + +/*! \file mln/core/lazy_image.hh + * + * \brief Definition of a lazy image. Values are computed on the fly + */ + +# include <cmath> + +# include <mln/core/internal/image_identity.hh> +# include <mln/core/box2d.hh> +# include <mln/core/line_piter.hh> + + +namespace mln +{ + + // Fwd decl. + template <typename I, typename F, typename B> struct lazy_image; + + namespace internal + { + + /// \internal Data structure for \c mln::lazy_image. + template <typename I, typename F, typename B> + struct data_< lazy_image<I,F,B> > + { + data_(const F& fun_, const B& box); + + mutable mln_ch_value(I,mln_result(F)) ima_; + mutable mln_ch_value(I,bool) is_known; + const F& fun; + const B& bb_; + }; + + } // end of namespace mln::internal + + + + namespace trait + { + + template <typename I, typename F, typename B> + struct image_< lazy_image<I,F,B> > : default_image_morpher_< I, mln_value(I), + lazy_image<I,F,B> > + { + typedef trait::image::category::domain_morpher category; + + typedef mln_trait_image_access(I) access; + typedef mln_trait_image_space(I) space; + typedef mln_trait_image_size(I) size; + typedef mln_trait_image_support(I) support; + typedef mln_trait_image_border(I) border; + typedef mln_trait_image_io_from_(I) io; + typedef mln_trait_image_data_from_(I) data; + + }; + + } // end of namespace mln::trait + + + + /*! \brief Lazy image class. + * + * The parameter \c I is the type of image. + * The parameter \c F is the type of function. + * The parameter \c B is the type of box. + * + * This image class tage a functor \p fun and a box \p box. + * Access to ima(p) where \p p include \p box return fun(b) lazily. + * + */ + template <typename I, typename F, typename B> + struct lazy_image : public mln::internal::image_identity_< mln_ch_value(I, mln_result(F)), + mln_pset(I), lazy_image<I, F,B> > + { + typedef mln::internal::image_morpher_< mln_ch_value(I, mln_result(F)), + mln_pset(I), lazy_image<I,F,B> > super_; + typedef line_piter_<mln_psite(I)> line_piter; + + /// Return type of read access. + typedef mln_result(F) rvalue; + + /// Return type of read-write access. + typedef mln_result(F)& lvalue; + + /// Skeleton. + typedef lazy_image< tag::image_, F, B > skeleton; + + /// Test if a pixel value is accessible at \p p. + using super_::has_data; + + /// Constructors. + lazy_image(const F& fun, const B& box); + + /// Return domain of lazyd_image. + const box2d& domain() const; + + /// Test if a pixel value is accessible at \p p. + bool owns_(const mln_psite(I)&) const; + + /// Read-only access of pixel value at point site \p p. + mln_result(F) operator()(const mln_psite(I)& p) const; + + /// Read and "write if possible" access of pixel value at point site \p p. + lvalue operator()(const mln_psite(I)& p); + }; + + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + // internal::data_< lazy_image<I,S> > + + template <typename I, typename F, typename B> + inline + data_< lazy_image<I,F,B> >::data_(const F& fun, const B& box) + : ima_(box), is_known(box), fun(fun), bb_(box) + { + } + + } // end of namespace mln::internal + + template <typename I, typename F, typename B> + inline + lazy_image<I,F,B>::lazy_image(const F& fun, const B& box) + { + this->data_ = new internal::data_< lazy_image<I,F,B> >(fun, box); + } + + template <typename I, typename F, typename B> + inline + bool lazy_image<I,F,B>::owns_(const mln_psite(I)& p) const + { + return this->data_->ima_.owns_(p); + } + + template <typename I, typename F, typename B> + inline + mln_result(F) + lazy_image<I,F,B>::operator()(const mln_psite(I)& p) const + { + mln_assertion(this->owns_(p)); + if (this->data_->is_known(p)) + return this->data_->ima_(p); + this->data_->ima_(p) = this->data_->fun(p); + this->data_->is_known(p) = true; + return this->data_->ima_(p); + } + + + template <typename I, typename F, typename B> + inline + typename lazy_image<I,F,B>::lvalue + lazy_image<I,F,B>::operator()(const mln_psite(I)& p) + { + mln_assertion(this->owns_(p)); + if (this->data_->is_known(p)) + return this->data_->ima_(p); + this->data_->ima_(p) = this->data_->fun(p); + this->data_->is_known(p) = true; + return this->data_->ima_(p); + } + + template <typename I, typename F, typename B> + inline + const box2d& + lazy_image<I,F,B>::domain() const + { + return this->data_->bb_; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_LAZY_IMAGE_HH

1 0

2091: Add image conversion to p_array.
by Ugo Jardonnet 21 Jul '08

21 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Add image conversion to p_array. * mln/convert/to_p_array.hh (to_p_array): Add. to_p_array.hh | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) Index: mln/convert/to_p_array.hh --- mln/convert/to_p_array.hh (revision 2091) +++ mln/convert/to_p_array.hh (working copy) @@ -52,6 +52,11 @@ p_array<mln_psite(W)> to_p_array(const Window<W>& win, const mln_psite(W)& p); + /// Convert an image \p img into a p_array. + template <typename I> + p_array<mln_point(I)> + to_p_array(const Image& img); + # ifndef MLN_INCLUDE_ONLY @@ -83,6 +88,23 @@ return v; } + template <typename I> + inline + p_array<mln_point(I)> + to_p_array(const Image& img_) + { + const I& img = exact(img_); + + p_array<mln_point(I)> a; + + mln_piter(I) p(img.domain()); + for_all(p) + if (img(p)) + a.append(p); + + return a; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::convert

1 0

2091: Fix conflict in point.hh.
by Ugo Jardonnet 21 Jul '08

21 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Fix conflict in point.hh. * mln/core/point.hh (operator algebra::vec<M,float>: Fail if point coordinate type is already float. point.hh | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) Index: mln/core/point.hh --- mln/core/point.hh (revision 2090) +++ mln/core/point.hh (working copy) @@ -38,6 +38,7 @@ # include <mln/fun/i2v/all_to.hh> # include <mln/metal/bool.hh> +# include <mln/metal/is_not.hh> # include <mln/algebra/vec.hh> # include <mln/metal/converts_to.hh> # include <mln/core/h_vec.hh> @@ -62,7 +63,7 @@ template <typename M, typename C> struct point_to_ { - typedef algebra::vec<M::dim, C> metal_vec; + typedef algebra::vec<M::dim, C> algebra_vec; typedef mln::h_vec<M::dim, C> h_vec; }; @@ -146,7 +147,7 @@ typedef algebra::vec<M::dim, C> vec_t; /// Hook to coordinates. - operator typename internal::point_to_<M, C>::metal_vec () const; + operator typename internal::point_to_<M, C>::algebra_vec () const; operator algebra::vec<M::dim, float> () const; /// Transform to point in homogene coordinate system. @@ -303,19 +304,22 @@ return *this; } + template <typename M, typename C> inline - point_<M,C>::operator typename internal::point_to_<M, C>::metal_vec () const + point_<M,C>::operator typename internal::point_to_<M, C>::algebra_vec () const { return coord_; // FIXME: Is-it OK? } + template <typename M, typename C> inline point_<M,C>::operator algebra::vec<M::dim, float> () const { + mlc_is_not(C,float)::check(); algebra::vec<dim, float> tmp; - for (unsigned i = 0; i < dim; ++i) + for (unsigned int i = 0; i < dim; ++i) tmp[i] = coord_[i]; return tmp; }

1 0

2090: Add matrix trace and transposition.
by Ugo Jardonnet 21 Jul '08

21 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Add matrix trace and transposition. * mln/algebra/mat.hh (transpose,trace): Add. mat.hh | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) Index: mln/algebra/mat.hh --- mln/algebra/mat.hh (revision 2089) +++ mln/algebra/mat.hh (working copy) @@ -256,6 +256,16 @@ std::ostream& operator<<(std::ostream& ostr, const mat<n,m,T>& v); + // transpose + + template<unsigned n, unsigned m, typename T> + mat<m,n,T> + trans(const mat<n,m,T>& matrix); + + // trace + + template<unsigned n, typename T> inline + float tr(const mat<n,n,T>& m); # ifndef MLN_INCLUDE_ONLY @@ -489,6 +499,27 @@ return ostr; } + + template<unsigned n, unsigned m, typename T> + mat<m,n,T> + trans(const mat<n,m,T>& matrix) + { + mat<m,n,T> tmp; + for (unsigned i = 0; i < n; ++i) + for (unsigned j = 0; j < m; ++j) + tmp(j,i) = matrix(i,j); + return tmp; + } + + template<unsigned n, typename T> inline + float tr(const mat<n,n,T>& m) + { + float f = 0.f; + for (unsigned i = 0; i < n; ++i) + f += m(i,i); + return f; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::algebra

1 0

2089: Fix a first bug in the watershed.
by Alexandre Abraham 02 Jul '08

02 Jul '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Alexandre Abraham <abraham(a)lrde.epita.fr> Fix a first bug in the watershed. * abraham/tests/morpho/test_watershed.cc: . * abraham/tests/morpho/Makefile: remove Werror. * abraham/mln/morpho/basic_najman.hh: fix bug. mln/morpho/basic_najman.hh | 123 +++++++++++++++++++++++++++++------------ tests/morpho/Makefile | 2 tests/morpho/test_watershed.cc | 4 - 3 files changed, 92 insertions(+), 37 deletions(-) Index: abraham/tests/morpho/test_watershed.cc --- abraham/tests/morpho/test_watershed.cc (revision 2088) +++ abraham/tests/morpho/test_watershed.cc (working copy) @@ -22,9 +22,9 @@ // #define TEST - // io::pgm::load(input, "./images/test_watershed.pgm"); + io::pgm::load(input, "./images/test_watershed.pgm"); // io::pgm::load(input, "./images/little_test.pgm"); - io::pgm::load(input, "./images/test_2.pgm"); + // io::pgm::load(input, "./images/test_2.pgm"); // io::pgm::load(input, "./images/lena_light.pgm"); // io::pgm::load(mverif, "./images/result_m_watershed.pgm"); Index: abraham/tests/morpho/Makefile --- abraham/tests/morpho/Makefile (revision 2088) +++ abraham/tests/morpho/Makefile (working copy) @@ -2,7 +2,7 @@ OBJ=$(SRC:.cc=.o) EXEC=$(SRC:.cc=) CC=g++ -CXXFLAGS=-Wall -W -Werror -I ../../ -I ../../../../ -g +CXXFLAGS=-Wall -W -I ../../ -I ../../../../ -g all: $(EXEC) Index: abraham/mln/morpho/basic_najman.hh --- abraham/mln/morpho/basic_najman.hh (revision 2088) +++ abraham/mln/morpho/basic_najman.hh (working copy) @@ -113,14 +113,14 @@ // Priority function for the second wateshed template <typename I> - class lesser_psite + class lower_psite { public: typedef mln_psite(I) psite; - lesser_psite(const Image& ima); + lower_psite(const Image& ima); - /// Is \a x lesser than \a y? + /// Is \a x lower than \a y? bool operator()(const psite& x, const psite& y); private: @@ -128,31 +128,31 @@ }; template <typename I> - lesser_psite - make_lesser_psite(const Image& ima); + lower_psite + make_lower_psite(const Image& ima); # ifndef MLN_INCLUDE_ONLY template <typename I> - lesser_psite::lesser_psite(const Image& ima) + lower_psite::lower_psite(const Image& ima) : ima_ (exact(ima)) { } template <typename I> bool - lesser_psite::operator()(const mln_psite(I)& x, const mln_psite(I)& y) + lower_psite::operator()(const mln_psite(I)& x, const mln_psite(I)& y) { return ima_(x) < ima_(y); } template <typename I> - lesser_psite - make_lesser_psite(const Image& ima) + lower_psite + make_lower_psite(const Image& ima) { - return lesser_psite(ima); + return lower_psite(ima); } # endif // ! MLN_INCLUDE_ONLY @@ -160,16 +160,16 @@ template <typename I, typename N, typename B> - class my_lesser_psite + class my_lower_psite { public: typedef mln_psite(I) psite; - my_lesser_psite(const Image& ima, + my_lower_psite(const Image& ima, const Neighborhood<N>& nbh, const Image& enqueued); - /// Is \a x lesser than \a y? + /// Is \a x lower than \a y? bool operator()(const psite& x, const psite& y); private: @@ -180,8 +180,8 @@ template <typename I, typename N, typename B> - my_lesser_psite<I, N, B> - make_my_lesser_psite(const Image& ima, + my_lower_psite<I, N, B> + make_my_lower_psite(const Image& ima, const Neighborhood<N>& nbh, const Image& enqueued); @@ -189,7 +189,7 @@ # ifndef MLN_INCLUDE_ONLY template <typename I, typename N, typename B> - my_lesser_psite<I, N, B>::my_lesser_psite(const Image& ima, + my_lower_psite<I, N, B>::my_lower_psite(const Image& ima, const Neighborhood<N>& nbh, const Image& enqueued) : ima_ (exact(ima)), nbh_(exact(nbh)), enqueued_(exact(enqueued)) @@ -198,7 +198,7 @@ template <typename I, typename N, typename B> bool - my_lesser_psite<I, N, B>::operator()(const mln_psite(I)& x, const mln_psite(I)& y) + my_lower_psite<I, N, B>::operator()(const mln_psite(I)& x, const mln_psite(I)& y) { #if 0 @@ -269,12 +269,12 @@ template <typename I, typename N, typename B> - my_lesser_psite<I, N, B> - make_my_lesser_psite(const Image& ima, + my_lower_psite<I, N, B> + make_my_lower_psite(const Image& ima, const Neighborhood<N>& nbh, const Image& enqueued) { - return my_lesser_psite<I, N, B>(ima, nbh, enqueued); + return my_lower_psite<I, N, B>(ima, nbh, enqueued); } # endif // ! MLN_INCLUDE_ONLY @@ -576,6 +576,7 @@ psite adjCanonicalElt = Find_tree(q); psite adjNode = Find_node(subtreeRoot(adjCanonicalElt)); if (curNode != adjNode) + { if (nodes(curNode).level == nodes(adjNode).level) curNode = MergeNode(adjNode, curNode); else @@ -584,6 +585,7 @@ nodes(curNode).area += nodes(adjNode).area; nodes(curNode).highest += nodes(adjNode).highest; } + } curCanonicalElt = Link_tree(adjCanonicalElt, curCanonicalElt); subtreeRoot(curCanonicalElt) = curNode; @@ -884,7 +886,11 @@ return psite(-1, -1); if (v.npoints() == 1) + { + if (nodes(v[0]).children.npoints() == 1) + std::cout << "SINGL QUI MERDE" << std::endl; return v[0]; + } psite c = max(v), @@ -905,6 +911,47 @@ if (nodes(c).level <= pima(p)) return psite(-1, -1); + if (nodes(c).children.npoints() == 1) + std::cout << "LCA QUI MERDE" << std::endl; + + return c; + } + + + psite w_constructible_slow(psite p) + { + mln_niter(N) q(nbh, p); + p_set<psite> v; + + for_all(q) + if (pima.has(q) && pima(q) > pima(p)) + v.insert(Par_node(q)); + + if (v.npoints() == 0) + return psite(-1, -1); + + if (v.npoints() == 1) + return v[0]; + + psite + c = max(v), + cmax = c; + + typename p_set<psite>::fwd_piter it(v); + for_all(it) + { + // Can't remove the point from the set + if (it.to_point() == cmax) + continue; + + psite c1 = lca(c, it.to_point()); + if (c1 != it.to_point()) + c = c1; + } + + if (nodes(c).level <= pima(p)) + return psite(-1, -1); + return c; } @@ -1154,6 +1201,10 @@ enqueued(x) = false; psite c = w_constructible(x); + // psite d = w_constructible_slow(x); + + //if (c != d) + // std::cerr << "COUILLE AVEC LE LCA : " << x << " donne " << c << " au lieu de " << d << std::endl; if (c != psite(-1, -1)) @@ -1169,7 +1220,10 @@ { } else + { std::cerr << "ERREUR COMPOSANTE BRANCHE " << nodes(c).children.npoints() << std::endl; + } + mln_niter(N) q(nbh, x); for_all(q) @@ -1216,7 +1270,7 @@ repr[position] = p; depth[position] = d; euler[position] = pos[p]; - position++; + ++position; node& n = nodes(p); typename p_array<mln_psite(I)>::fwd_piter it(n.children); @@ -1225,7 +1279,8 @@ build_euler_tour_rec(it.to_point(), position, d+1); depth[position] = d; // Not optimized euler[position] = pos[p]; - position++; + repr[position] = p; // Pas necessaire? + ++position; } } @@ -1265,7 +1320,7 @@ Minim[0][i] = i+1; } - Minim[0][size - 1] = size - 1; + // Minim[0][size - 1] = size - 1; int k; for (int j = 1; j < logn; j++) { @@ -1273,7 +1328,7 @@ Minim[j] = &minim[j * size]; for (int i = 0; i < size; i++) { if ((i + (k << 1)) >= size) { - Minim[j][i] = size - 1; + //Minim[j][i] = size - 1; } else { if (depth[euler[Minim[j - 1][i]]] <= depth[euler[Minim[j - 1][i + k]]])

1 0