March 2008 - Olena-patches

1780: Add backward iterators for graph-related neighborhoods and windows; document forward iterators.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Add more documentation to forward iterators on graph neighborhoods and windows, and add backward iterators. * mln/core/graph_neighborhood_piter.hh: More documentation. (graph_neighborhood_fwd_piter(const N&, const Point_Site<Pref>&): Adopt the uniform initialization scheme used in other iterators on graph-related structures. (mln::graph_neighborhood_fwd_piter::operator point): Remove. (mln::graph_neighborhood_fwd_piter::invalidate): Initialize member id_ to -1. (mln::graph_neighborhood_bkd_piter): New class. * mln/core/graph_window_piter.hh: More documentation. (mln::graph_window_fwd_piter::operator point): Remove. (mln::graph_window_fwd_piter::invalidate): Initialize member id_ to -1. (mln::graph_window_bkd_piter): New class. * mln/core/line_graph_window_piter.hh, * mln/core/line_graph_neighborhood_piter.hh: Remove spurious comments. graph_neighborhood_piter.hh | 256 +++++++++++++++++++++++++++++++++++---- graph_window_piter.hh | 239 ++++++++++++++++++++++++++++++++---- line_graph_neighborhood_piter.hh | 10 - line_graph_window_piter.hh | 2 4 files changed, 453 insertions(+), 54 deletions(-) Index: mln/core/line_graph_window_piter.hh --- mln/core/line_graph_window_piter.hh (revision 1779) +++ mln/core/line_graph_window_piter.hh (working copy) @@ -70,7 +70,6 @@ typedef Point_Iterator< self_ > super_; public: - // Make definitions from super class available. enum { dim = P::dim }; typedef line_graph_psite psite; @@ -154,7 +153,6 @@ typedef Point_Iterator< self_ > super_; public: - // Make definitions from super class available. enum { dim = P::dim }; typedef line_graph_psite psite; Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1779) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -61,7 +61,7 @@ | line_graph_neighborhood_fwd_piter. | `---------------------------------------*/ - /// \brief Backward iterator on line graph neighborhood. + /// \brief Forward iterator on line graph neighborhood. template <typename P> class line_graph_neighborhood_fwd_piter : public Point_Iterator< line_graph_neighborhood_fwd_piter > // or Iterator<...>? @@ -70,7 +70,6 @@ typedef Point_Iterator< self_ > super_; public: - // Make definitions from super class available. enum { dim = P::dim }; typedef line_graph_psite psite; @@ -157,7 +156,6 @@ typedef Point_Iterator< self_ > super_; public: - // Make definitions from super class available. enum { dim = P::dim }; typedef line_graph_psite psite; @@ -244,9 +242,6 @@ inline line_graph_neighborhood_fwd_piter::line_graph_neighborhood_fwd_piter(const N& /* nbh */, const Point_Site<Pref>& p_ref) - /* FIXME: We should use a routine actually checking the - conversion, since to_psite() checks nothing (as of - 2008-03-05). */ : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() @@ -402,9 +397,6 @@ inline line_graph_neighborhood_bkd_piter::line_graph_neighborhood_bkd_piter(const N& /* nbh */, const Point_Site<Pref>& p_ref) - /* FIXME: We should use a routine actually checking the - conversion, since to_psite() checks nothing (as of - 2008-03-05). */ : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() Index: mln/core/graph_window_piter.hh --- mln/core/graph_window_piter.hh (revision 1779) +++ mln/core/graph_window_piter.hh (working copy) @@ -37,9 +37,6 @@ - mln::graph_neighborhood_fwd_piter - mln::line_graph_window_fwd_piter - mln::line_graph_neighborhood_fwd_piter. - - and later (when they get implemented): - - mln::graph_window_bkd_piter - mln::graph_neighborhood_bkd_piter - mln::line_graph_window_bkd_piter @@ -49,8 +46,6 @@ # include <mln/core/p_graph.hh> # include <mln/core/graph_psite.hh> -/* FIXME: Doc. */ - /* FIXME: Due to the poor interface of mln::p_graph and mln::util::graph, we show to much implementation details here. Enrich their interfaces to avoid that. */ @@ -66,6 +61,7 @@ | graph_window_fwd_piter. | `----------------------------*/ + /// \brief Forward iterator on graph window. template <typename P> class graph_window_fwd_piter : public Point_Iterator< graph_window_fwd_piter > // or Iterator<...>? @@ -74,41 +70,52 @@ typedef Point_Iterator< self_ > super_; public: - typedef graph_psite psite; - enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; + typedef graph_psite psite; typedef P point; + typedef mln_coord(P) coord; // FIXME: Dummy typedef. typedef void dpoint; - typedef mln_coord(P) coord; + // FIXME: Dummy value. + typedef void mesh; public: + /// Construction. + /// \{ template <typename W, typename Pref> graph_window_fwd_piter(const W& win, const Point_Site<Pref>& p_ref); + /// \} + /// Manipulation. + /// \{ + /// Test if the iterator is valid. bool is_valid() const; + /// Invalidate the iterator. void invalidate(); + /// Start an iteration. void start(); + /// Go to the next point. void next_(); - + /// Is the piter adjacent or equal to the reference point? bool adjacent_or_equal_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); + /// \} + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. const point& to_point() const; - + /// Reference to the corresponding point site. const psite& to_psite() const; - - operator point() const; - + /// Convert the iterator into a line graph psite. operator psite() const; - /// Return the \a i th coordinate of the (iterated) point. + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; + /// \} private: /// The ``central'' psite of the window. @@ -121,13 +128,86 @@ point p_; }; + /*----------------------------. | graph_window_bkd_piter. | `----------------------------*/ + /// \brief Backward iterator on graph window. + template <typename P> + class graph_window_bkd_piter : + public Point_Iterator< graph_window_bkd_piter > // or Iterator<...>? + { + typedef graph_window_bkd_piter self_; + typedef Point_Iterator< self_ > super_; + + public: + enum { dim = P::dim }; + + typedef graph_psite psite; + typedef P point; + typedef mln_coord(P) coord; + // FIXME: Dummy typedef. + typedef void dpoint; + // FIXME: Dummy value. + typedef void mesh; + + public: + /// Construction. + /// \{ + template <typename W, typename Pref> + graph_window_bkd_piter(const W& win, const Point_Site<Pref>& p_ref); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + /// Is the piter adjacent or equal to the reference point? + bool adjacent_or_equal_to_p_ref_() const; + /// Update the internal data of the iterator. + void update_(); + /// \} + + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. + const point& to_point() const; + /// Reference to the corresponding point site. + const psite& to_psite() const; + /// Convert the iterator into a line graph psite. + operator psite() const; + + /// Read-only access to the \a i-th coordinate. + coord operator[](unsigned i) const; + /// \} + + private: + /// The ``central'' psite of the window. + const psite& p_ref_; + /// An internal iterator on the set of nodes of the underlying graph. + util::node_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + point p_; + }; + + # ifndef MLN_INCLUDE_ONLY + /*----------------------------. + | graph_window_fwd_piter. | + `----------------------------*/ + // FIXME: Currently, argument win is ignored. template <typename P> template <typename W, typename Pref> @@ -136,7 +216,7 @@ const Point_Site<Pref>& p_ref) : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. - psite_(p_ref_.pg(), p_ref_.pg().npoints()), + psite_(), p_() { // Invalidate id_. @@ -156,7 +236,7 @@ void graph_window_fwd_piter::invalidate() { - id_ = p_ref_.pg().npoints(); + id_ = -1; } template <typename P> @@ -187,9 +267,7 @@ window, which is not the case now! (Currently, next_() behaves as win was always an elementary window.) */ do - { ++id_; - } while (is_valid() && !adjacent_or_equal_to_p_ref_()); if (is_valid()) update_(); @@ -233,15 +311,130 @@ template <typename P> inline - graph_window_fwd_piter::operator P() const + graph_window_fwd_piter::operator graph_psite() const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + graph_window_fwd_piter::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + + /*----------------------------. + | graph_window_bkd_piter. | + `----------------------------*/ + + // FIXME: Currently, argument win is ignored. + template <typename P> + template <typename W, typename Pref> + inline + graph_window_bkd_piter::graph_window_bkd_piter(const W& /* win */, + const Point_Site<Pref>& p_ref) + : p_ref_(exact(p_ref).to_psite()), + // Initialize psite_ to a dummy value. + psite_(), + p_() + { + // Invalidate id_. + invalidate(); + } + + template <typename P> + inline + bool + graph_window_bkd_piter::is_valid() const + { + return id_ < p_ref_.pg().npoints(); + } + + template <typename P> + inline + void + graph_window_bkd_piter::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + graph_window_bkd_piter::start() + { + id_ = p_ref_.plg().gr_.nnodes() - 1; + if (!adjacent_or_equal_to_p_ref_()) + next_(); + /* FIXME: This is redundant with the end of next_(), but we might + change the implementation of start_() when we'll fix it later, + and no longer use next_(). */ + if (is_valid()) + update_(); + } + + template <typename P> + inline + void + graph_window_bkd_piter::next_() + { + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent nodes fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + /* FIXME: Moreover, the behavior of next shall depend on the + window, which is not the case now! (Currently, next_() behaves + as win was always an elementary window.) */ + do + --id_; + while (is_valid() && !adjacent_or_equal_to_p_ref_()); + if (is_valid()) + update_(); + } + + + template <typename P> + inline + bool + graph_window_bkd_piter::adjacent_or_equal_to_p_ref_() const + { + return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + } + + template <typename P> + inline + void + graph_window_bkd_piter::update_() + { + // Update psite_. + psite_ = graph_psite(p_ref_.pg(), id_); + // Update p_. + p_ = p_ref_.pg().point_from_id(id_); + } + + template <typename P> + inline + const P& + graph_window_bkd_piter::to_point() const + { return p_; } template <typename P> inline - graph_window_fwd_piter::operator graph_psite() const + const graph_psite& + graph_window_bkd_piter::to_psite() const + { + return psite_; + } + + template <typename P> + inline + graph_window_bkd_piter::operator graph_psite() const { mln_precondition(is_valid()); return psite_; @@ -250,7 +443,7 @@ template <typename P> inline mln_coord(P) - graph_window_fwd_piter::operator[](unsigned i) const + graph_window_bkd_piter::operator[](unsigned i) const { assert(i < dim); return p_[i]; Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1779) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -37,9 +37,6 @@ - mln::graph_neighborhood_fwd_piter - mln::line_graph_window_fwd_piter - mln::line_graph_neighborhood_fwd_piter. - - and later (when they get implemented): - - mln::graph_window_bkd_piter - mln::graph_neighborhood_bkd_piter - mln::line_graph_window_bkd_piter @@ -49,8 +46,6 @@ # include <mln/core/p_graph.hh> # include <mln/core/graph_psite.hh> -/* FIXME: Doc. */ - /* FIXME: Due to the poor interface of mln::p_graph and mln::util::graph, we show to much implementation details here. Enrich their interfaces to avoid that. */ @@ -66,6 +61,7 @@ | graph_neighborhood_fwd_piter. | `----------------------------------*/ + /// \brief Forward iterator on graph neighborhood. template <typename P> class graph_neighborhood_fwd_piter : public Point_Iterator< graph_neighborhood_fwd_piter > // or Iterator<...>? @@ -74,39 +70,49 @@ typedef Point_Iterator< self_ > super_; public: - typedef graph_psite psite; - enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; + typedef graph_psite psite; typedef P point; + typedef mln_coord(P) coord; // FIXME: Dummy typedef. typedef void dpoint; - typedef mln_coord(P) coord; + // FIXME: Dummy value. + typedef void mesh; public: + /// Construction. + /// \{ template <typename N, typename Pref> graph_neighborhood_fwd_piter(const N& nbh, const Point_Site<Pref>& p_ref); + /// \} + /// Manipulation. + /// \{ + /// Test if the iterator is valid. bool is_valid() const; + /// Invalidate the iterator. void invalidate(); + /// Start an iteration. void start(); + /// Go to the next point. void next_(); + /// Is the piter adjacent or equal to the reference point? bool adjacent_or_equal_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); + /// \} + /// Conversion and accessors. + /// Reference to the corresponding point. const point& to_point() const; - + /// Reference to the corresponding point site. const psite& to_psite() const; - - operator point() const; - + /// Convert the iterator into a line graph psite. operator psite() const; - /// Return the \a i th coordinate of the (iterated) point. + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; private: @@ -120,13 +126,84 @@ point p_; }; + /*----------------------------------. | graph_neighborhood_bkd_piter. | `----------------------------------*/ + /// \brief Backward iterator on graph neighborhood. + template <typename P> + class graph_neighborhood_bkd_piter : + public Point_Iterator< graph_neighborhood_bkd_piter > // or Iterator<...>? + { + typedef graph_neighborhood_bkd_piter self_; + typedef Point_Iterator< self_ > super_; + + public: + enum { dim = P::dim }; + + typedef graph_psite psite; + typedef P point; + typedef mln_coord(P) coord; + // FIXME: Dummy typedef. + typedef void dpoint; + // FIXME: Dummy value. + typedef void mesh; + + public: + /// Construction. + /// \{ + template <typename N, typename Pref> + graph_neighborhood_bkd_piter(const N& nbh, const Point_Site<Pref>& p_ref); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + /// Is the piter adjacent or equal to the reference point? + bool adjacent_or_equal_to_p_ref_() const; + /// Update the internal data of the iterator. + void update_(); + /// \} + + /// Conversion and accessors. + /// Reference to the corresponding point. + const point& to_point() const; + /// Reference to the corresponding point site. + const psite& to_psite() const; + /// Convert the iterator into a line graph psite. + operator psite() const; + + /// Read-only access to the \a i-th coordinate. + coord operator[](unsigned i) const; + + private: + /// The ``central'' psite of the neighborhood. + const psite& p_ref_; + /// An internal iterator on the set of nodes of the underlying graph. + util::node_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + point p_; + }; + + # ifndef MLN_INCLUDE_ONLY + /*----------------------------------. + | graph_neighborhood_fwd_piter. | + `----------------------------------*/ + // FIXME: Currently, argument nbh is ignored. template <typename P> template <typename N, typename Pref> @@ -135,7 +212,7 @@ const Point_Site<Pref>& p_ref) : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. - psite_(p_ref_.pg(), p_ref_.pg().npoints()), + psite_(), p_() { // Invalidate id_. @@ -158,7 +235,7 @@ void graph_neighborhood_fwd_piter::invalidate() { - id_ = p_ref_.pg().gr_.nnodes(); + id_ = -1 } template <typename P> @@ -254,15 +331,154 @@ template <typename P> inline - graph_neighborhood_fwd_piter::operator P() const + graph_neighborhood_fwd_piter::operator graph_psite() const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + graph_neighborhood_fwd_piter::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + + /*----------------------------------. + | graph_neighborhood_bkd_piter. | + `----------------------------------*/ + + // FIXME: Currently, argument nbh is ignored. + template <typename P> + template <typename N, typename Pref> + inline + graph_neighborhood_bkd_piter::graph_neighborhood_bkd_piter(const N& /* nbh */, + const Point_Site<Pref>& p_ref) + : p_ref_(exact(p_ref).to_psite()), + // Initialize psite_ to a dummy value. + psite_(), + p_() + { + // Invalidate id_. + invalidate(); + } + + template <typename P> + inline + bool + graph_neighborhood_bkd_piter::is_valid() const + { + // FIXME: We depend too much on the implementation of util::graph + // here. The util::graph should provide the service to abstract + // these manipulations. + return id_ < p_ref_.pg().gr_.nnodes(); + } + + template <typename P> + inline + void + graph_neighborhood_bkd_piter::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + graph_neighborhood_bkd_piter::start() + { + id_ = p_ref_.plg().gr_.nnodes() - 1; + if (!adjacent_or_equal_to_p_ref_()) + next_(); + /* FIXME: This is redundant with the end of next_(), but we might + change the implementation of start_() when we'll fix it later, + and no longer use next_(). */ + if (is_valid()) + update_(); + } + + template <typename P> + inline + void + graph_neighborhood_bkd_piter::next_() + { + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent nodes fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + /* FIXME: Moreover, the behavior of next shall depend on the + neighborhood, which is not the case now! (Currently, next_() behaves + as nbh was always an elementary neighborhood.) */ + do + --id_; + while (is_valid() && !adjacent_or_equal_to_p_ref_()); + if (is_valid()) + update_(); + } + + template <typename P> + inline + bool + graph_neighborhood_bkd_piter::adjacent_or_equal_to_p_ref_() const + { + // FIXME: Likewise, this is inefficient. + + // Check wether the iterator points to P_REF_. + if (id_ == p_ref_.id()) + return true; + + // Check whether the iterator is among the neighbors of P_REF_. + { + // Paranoid assertion. + assert (p_ref_.id() < p_ref_.pg().gr_.nnodes()); + // FIXME: This is too low-level. Yet another service the graph + // should provide. + typedef std::vector<util::node_id> adjacency_type; + const adjacency_type& p_ref_neighbs = + p_ref_.pg().gr_.nodes()[p_ref_.id()]->edges; + adjacency_type::const_iterator j = + std::find (p_ref_neighbs.begin(), p_ref_neighbs.end(), id_); + if (j != p_ref_neighbs.end()) + return true; + } + + // Otherwise, the iterator is not adjacent to P_REF_. + return false; + } + + template <typename P> + inline + void + graph_neighborhood_bkd_piter::update_() + { + // Update psite_. + psite_ = graph_psite(p_ref_.pg(), id_); + // Update p_. + p_ = p_ref_.pg().gr_.node_data(id_); + } + + template <typename P> + inline + const P& + graph_neighborhood_bkd_piter::to_point() const + { return p_; } template <typename P> inline - graph_neighborhood_fwd_piter::operator graph_psite() const + const graph_psite& + graph_neighborhood_bkd_piter::to_psite() const + { + return psite_; + } + + template <typename P> + inline + graph_neighborhood_bkd_piter::operator graph_psite() const { mln_precondition(is_valid()); return psite_; @@ -271,7 +487,7 @@ template <typename P> inline mln_coord(P) - graph_neighborhood_fwd_piter::operator[](unsigned i) const + graph_neighborhood_bkd_piter::operator[](unsigned i) const { assert(i < dim); return p_[i];

1 0

1779: Finish the conversion of level::sort_points to level::sort_psites.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Finish the conversion of level::sort_points to level::sort_psites. * mln/level/sort_points.hh: Remove. * mln/level/all.hh: s/sort_point.hh/sort_psite.hh/. * mln/labeling/regional_minima.hh: s/point/psite/. * mln/labeling/regional_minima.hh (impl::regional_minima_functor<I_, N_, L_>::regional_minima_functor): Remove outdated FIXME. * tests/level/sort_points.cc, tests/level/sort_points_full.cc: Rename as... * tests/level/sort_psites.cc, tests/level/sort_psites_full.cc: ...these. s/sort_points/sort_psites/. * tests/level/Makefile.am (check_PROGRAMS): s/sort_points/sort_psites/. Add sort_psites_full. (sort_points_SOURCES): Likewise. Rename as... (sort_psites_SOURCES): ...this. (sort_psites_full_SOURCES): New. mln/labeling/regional_maxima.hh | 5 ++--- mln/labeling/regional_minima.hh | 6 ++---- mln/level/all.hh | 2 +- tests/level/Makefile.am | 8 ++++++-- tests/level/sort_psites.cc | 12 ++++++------ tests/level/sort_psites_full.cc | 10 +++++----- 6 files changed, 22 insertions(+), 21 deletions(-) Index: mln/level/all.hh --- mln/level/all.hh (revision 1778) +++ mln/level/all.hh (working copy) @@ -68,7 +68,7 @@ # include <mln/level/naive/all.hh> # include <mln/level/paste.hh> # include <mln/level/saturate.hh> -# include <mln/level/sort_points.hh> +# include <mln/level/sort_psites.hh> # include <mln/level/stretch.hh> # include <mln/level/take.hh> # include <mln/level/to_enc.hh> Index: mln/labeling/regional_minima.hh --- mln/labeling/regional_minima.hh (revision 1778) +++ mln/labeling/regional_minima.hh (working copy) @@ -107,8 +107,7 @@ regional_minima_functor(const I_& input, const N_& nbh) : input(input), nbh(nbh), - s(level::sort_psites_increasing(input)), // FIXME: - // sort_psites_increasing + s(level::sort_psites_increasing(input)), attr(input.domain()) { } @@ -122,8 +121,7 @@ template <typename I, typename N, typename L> mln_ch_value(I, L) - regional_minima_(const I& input, const N& nbh, - L& nlabels) + regional_minima_(const I& input, const N& nbh, L& nlabels) { trace::entering("labeling::impl::generic::regional_minima_"); Index: mln/labeling/regional_maxima.hh --- mln/labeling/regional_maxima.hh (revision 1778) +++ mln/labeling/regional_maxima.hh (working copy) @@ -38,7 +38,7 @@ # include <mln/core/concept/neighborhood.hh> # include <mln/canvas/labeling.hh> # include <mln/level/fill.hh> -# include <mln/level/sort_points.hh> +# include <mln/level/sort_psites.hh> namespace mln @@ -108,8 +108,7 @@ regional_maxima_functor(const I_& input, const N_& nbh) : input(input), nbh(nbh), - s(level::sort_points_decreasing(input)), // FIXME: - // sort_psites_decreasing + s(level::sort_psites_decreasing(input)), attr(input.domain()) { } Index: tests/level/sort_psites.cc --- tests/level/sort_psites.cc (revision 1777) +++ tests/level/sort_psites.cc (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 @@ -25,14 +25,14 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/level/sort_points.cc +/*! \file tests/level/sort_psites.cc * - * \brief Tests on mln::level::sort_points. + * \brief Tests on mln::level::sort_psites. */ #include <mln/core/image2d.hh> #include <mln/debug/iota.hh> -#include <mln/level/sort_points.hh> +#include <mln/level/sort_psites.hh> #include <mln/core/p_array.hh> @@ -42,8 +42,8 @@ image2d<int> ima(3, 3); debug::iota (ima); - p_array<point2d> array_inc = level::sort_points_increasing(ima); - p_array<point2d> array_dec = level::sort_points_decreasing(ima); + p_array<point2d> array_inc = level::sort_psites_increasing(ima); + p_array<point2d> array_dec = level::sort_psites_decreasing(ima); p_array<point2d> array_inc_ref; p_array<point2d> array_dec_ref; Index: tests/level/sort_psites_full.cc --- tests/level/sort_psites_full.cc (revision 1777) +++ tests/level/sort_psites_full.cc (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 @@ -51,7 +51,7 @@ #include <mln/level/saturate.hh> #include <mln/level/paste.hh> -#include <mln/level/sort_points.hh> +#include <mln/level/sort_psites.hh> @@ -104,8 +104,8 @@ { I& input = exact(input_); - p_array<J> array_inc = level::sort_points_increasing(input); - p_array<J> array_dec = level::sort_points_decreasing(input); + p_array<J> array_inc = level::sort_psites_increasing(input); + p_array<J> array_dec = level::sort_psites_decreasing(input); mln_assertion(array_inc == array_inc_ref); mln_assertion(array_dec == array_dec_ref); @@ -306,7 +306,7 @@ int rows = 8; int cols = 8; - std::cerr << "Tests level::sort_points:" << std::endl; + std::cerr << "Tests level::sort_psites:" << std::endl; std::cerr << "in int:" << std::endl; chk<int>(slis, rows, cols); std::cerr << "in unsigned:" << std::endl; Index: tests/level/Makefile.am --- tests/level/Makefile.am (revision 1778) +++ tests/level/Makefile.am (working copy) @@ -20,7 +20,8 @@ memset_ \ paste \ saturate \ - sort_points \ + sort_psites \ + sort_psites_full \ stretch \ take \ transform @@ -40,9 +41,12 @@ memset__SOURCES = memset_.cc paste_SOURCES = paste.cc saturate_SOURCES = saturate.cc -sort_points_SOURCES = sort_points.cc +sort_psites_SOURCES = sort_psites.cc stretch_SOURCES = stretch.cc take_SOURCES = take.cc transform_SOURCES = transform.cc +# Lengthy tests. +sort_psites_full_SOURCES = sort_psites_full.cc + TESTS = $(check_PROGRAMS)

1 0

milena r1778: Add to sanbox an image type maped on the hard disk
by Matthieu Garrigues 12 Mar '08

12 Mar '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-03-12 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Add to sanbox an image type maped on the hard disk. * milena/sandbox/garrigues/tiled_image2d: New. * milena/sandbox/garrigues/tiled_image2d/tiled_image2d.cc: New. * milena/sandbox/garrigues/tiled_image2d/tiled_image2d.hh: New. * milena/sandbox/garrigues/tiled_image2d/backend/file.hh: New. * milena/sandbox/garrigues/tiled_image2d/backend/ios.hh: New. * milena/sandbox/garrigues/tiled_image2d/backend/mmap.hh: New. * milena/sandbox/garrigues/tiled_image2d/backend: New. * milena/sandbox/garrigues/tiled_image2d/block.hh: New. * milena/sandbox/garrigues/tiled_image2d/context.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/all.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/image2d/all.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/image2d/lrtb.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/image2d/tblr.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/image2d: New. * milena/sandbox/garrigues/tiled_image2d/layout/layout2d.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/page2d/all.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/page2d/lrtb.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/page2d/tblr.hh: New. * milena/sandbox/garrigues/tiled_image2d/layout/page2d: New. * milena/sandbox/garrigues/tiled_image2d/layout: New. * milena/sandbox/garrigues/tiled_image2d/page.hh: New. * milena/sandbox/garrigues/tiled_image2d/paged_image.hh: New. * milena/sandbox/garrigues/tiled_image2d/support/lru.hh: New. * milena/sandbox/garrigues/tiled_image2d/support/simple.hh: New. * milena/sandbox/garrigues/tiled_image2d/support: New. --- backend/file.hh | 76 ++++++++++ backend/ios.hh | 79 ++++++++++ backend/mmap.hh | 125 +++++++++++++++++ block.hh | 63 ++++++++ context.hh | 38 +++++ layout/all.hh | 8 + layout/image2d/all.hh | 7 layout/image2d/lrtb.hh | 65 ++++++++ layout/image2d/tblr.hh | 33 ++++ layout/layout2d.hh | 56 +++++++ layout/page2d/all.hh | 7 layout/page2d/lrtb.hh | 52 +++++++ layout/page2d/tblr.hh | 21 ++ page.hh | 91 ++++++++++++ paged_image.hh | 56 +++++++ support/lru.hh | 198 +++++++++++++++++++++++++++ support/simple.hh | 35 ++++ tiled_image2d.cc | 45 ++++++ tiled_image2d.hh | 357 +++++++++++++++++++++++++++++++++++++++++++++++++ 19 files changed, 1412 insertions(+) Index: trunk/milena/sandbox/garrigues/tiled_image2d/paged_image.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/paged_image.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/paged_image.hh (revision 1778) @@ -0,0 +1,56 @@ +#ifndef paged_image_hh +#define paged_image_hh + +#include "page.hh" + +template<typename T, typename Domain, typename Layout, typename Support> +struct paged_image { + typedef Domain domain_type; + typedef Support support_type; + typedef Layout layout_type; + + typedef page<T, typename Layout::page_layout> page_type; + + paged_image(const Domain& d, Support& s) + : domain_(d), support_(s) + {} + + + const domain_type& domain() const { return domain_; } + + template<typename Point> + page_type page_at(const Point& p) { + unsigned page_n = Layout::image_layout::page_at(*this, p); + return page_type(support_.get_block(page_n)); + } + + template<typename Point> + void prepare(const Point& p) { + unsigned page_n = Layout::image_layout::page_at(*this, p); + support_.prepare(page_n); + } + + template<typename Point> + T& operator()(const Point& p) { + unsigned page_n = Layout::image_layout::page_at(*this, p); + // note: although the page instance goes + // out of scope, the reference stays valid + // because the block is ultimately held by support. + return page_type(support_.get_block(page_n))(Layout::image_layout::changeref(p)); + } + + template<typename Point> + const T& operator()(const Point& p) const { + unsigned page_n = Layout::page_at(*this, p); + // note: although the page instance goes + // out of scope, the reference stays valid + // because the block is ultimately held by support. + return page_type(const_cast<support_type&>(support_).get_block(page_n))(Layout::image_layout::changeref(p)); + } + + + domain_type domain_; + support_type& support_; +}; + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/context.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/context.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/context.hh (revision 1778) @@ -0,0 +1,38 @@ +#ifndef context_hh +#define context_hh + +#include "ersatz/domain.hh" +#include "page.hh" +#include "paged_image.hh" + +template<typename T, typename Layout, + template<typename Block> class Backend, + template<typename Backend> class Support, + typename Domain = domain<Layout::dim, unsigned> > +struct context { + + typedef typename Layout::template block_<T> block_type; + + typedef T value_type; + + enum { dim = Layout::dim }; + + typedef Backend<block_type> backend_type; + + typedef Support<backend_type> support_type; + + typedef Layout layout_type; + typedef typename layout_type::page_layout page_layout; + typedef typename layout_type::image_layout image_layout; + + typedef page<T, page_layout> page_type; + + typedef Domain domain_type; + + typedef paged_image<value_type, domain_type, layout_type, support_type> image_type; + +}; + + + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/backend/ios.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/backend/ios.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/backend/ios.hh (revision 1778) @@ -0,0 +1,79 @@ +#ifndef ios_backend_hh +#define ios_backend_hh + +#include <iostream> +#include <cassert> + +template<typename Block> +struct ios_backend { + typedef Block block_type; + + ios_backend(std::iostream& ios, unsigned n_blocks) + : ios_(ios), size_(n_blocks) { + assert(ios_.good()); + loaded_ = new Block*[n_blocks]; + for (Block **p = loaded_; p < loaded_ + n_blocks; ++p) + *p = 0; + } + + ~ios_backend() { + for (unsigned n = 0; n < size_; ++n) + if (loaded_[n]) { + commit(n); + delete loaded_[n]; + } + delete[] loaded_; + } + + unsigned size() { return size_; } + + + Block& get(unsigned n) { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + const Block& get(unsigned n) const { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + void commit() { + for (unsigned n = 0; n < size_; ++n) + if(loaded_[n]) + commit(n); + } + + void commit(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + ios_.seekp(n * Block::nbytes); + ios_.write(b->bytes, Block::nbytes); + ios_.flush(); + } + + void forget(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + commit(n); + loaded_[n] = 0; + delete b; + } + + void load(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + if (!b) b = new Block; + ios_.seekp(n * Block::nbytes); + ios_.read(b->bytes, Block::nbytes); + loaded_[n] = b; + } + + Block** loaded_; + std::iostream &ios_; + unsigned size_; +}; + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/backend/mmap.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/backend/mmap.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/backend/mmap.hh (revision 1778) @@ -0,0 +1,125 @@ +// Copyright (C) 2007, 2008 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 mmap_backend_hh +#define mmap_backend_hh + +#include <sys/mman.h> +#include <unistd.h> +#include <cassert> +#include <cstdio> + + +namespace mln +{ + + template<typename Block> + struct mmap_backend : public Object< mmap_backend<Block> >{ + typedef Block block_type; + + mmap_backend(int fd, unsigned n_blocks) + : fd_(fd), size_(n_blocks) { + + assert(Block::nbytes % getpagesize() == 0); + if (fd == -1) { perror("open"); exit(1); } + assert(fd_ != -1); + +#ifndef NDEBUG + // FIXME: should be performed as static check + Block *bl = 0; + assert((void*)bl == (void*)bl->bytes); +#endif + + loaded_ = new Block*[n_blocks]; + for (Block **p = loaded_; p < loaded_ + n_blocks; ++p) + *p = 0; + } + + ~mmap_backend() { + for (unsigned n = 0; n < size_; ++n) + if (loaded_[n]) + munmap(loaded_[n]->bytes, Block::nbytes); + delete[] loaded_; + } + + unsigned size() { return size_; } + + Block& get(unsigned n) { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + const Block& get(unsigned n) const { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + void commit() { + for (unsigned n = 0; n < size_; ++n) + if(loaded_[n]) + commit(n); + } + + void commit(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + if (msync(b->bytes, Block::nbytes, MS_SYNC) == -1) + perror("msync"); + } + + void forget(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + loaded_[n] = 0; + if (munmap(b->bytes, Block::nbytes) == -1) + perror("munmap"); + } + + void load(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + if (!b) { + b = (Block*) mmap(0, Block::nbytes, PROT_READ|PROT_WRITE, MAP_FILE|MAP_SHARED, fd_, n * Block::nbytes); + if (b == (void*)-1) + perror("mmap"); + assert(b != 0); + loaded_[n] = b; + + } + } + + Block** loaded_; + int fd_; + unsigned size_; + }; + + +} // end of namespace mln + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/backend/file.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/backend/file.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/backend/file.hh (revision 1778) @@ -0,0 +1,76 @@ +#ifndef file_backend_hh +#define file_backend_hh + +#include <unistd.h> +#include <cassert> + +template<typename Block> +struct file_backend { + typedef Block block_type; + + file_backend(int fd, unsigned n_blocks) + : fd_(fd), size_(n_blocks) { + loaded_ = new Block*[n_blocks]; + for (Block **p = loaded_; p < loaded_ + n_blocks; ++p) + *p = 0; + } + + ~file_backend() { + for (unsigned n = 0; n < size_; ++n) + if (loaded_[n]) { + commit(n); + delete loaded_[n]; + } + delete[] loaded_; + } + + unsigned size() const { return size_; } + + Block& get(unsigned n) { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + const Block& get(unsigned n) const { + assert(n < size_); + assert(loaded_[n]); + return *loaded_[n]; + } + + void commit() { + for (unsigned n = 0; n < size_; ++n) + if(loaded_[n]) + commit(n); + } + + void commit(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + lseek(fd_, n * Block::nbytes, SEEK_SET); + write(fd_, b->bytes, Block::nbytes); + } + + void forget(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + commit(n); + loaded_[n] = 0; + delete b; + } + + void load(unsigned n) { + assert(n < size_); + Block *b = loaded_[n]; + if (!b) b = new Block; + lseek(fd_, n * Block::nbytes, SEEK_SET); + read(fd_, b->bytes, Block::nbytes); + loaded_[n] = b; + } + + Block** loaded_; + int fd_; + unsigned size_; +}; + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.hh (revision 1778) @@ -0,0 +1,357 @@ +// Copyright (C) 2007, 2008 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_TILED_IMAGE2D_HH +# define MLN_CORE_TILED_IMAGE2D_HH + +/*! \file mln/core/tiled_image2d.hh + * + * \brief Definition of the basic mln::tiled_image2d class. + */ + +# include <mln/core/internal/image_primary.hh> +# include <mln/core/internal/fixme.hh> +# include <mln/core/box2d.hh> +# include <mln/core/inplace.hh> +# include <mln/core/init.hh> + +# include <mln/border/thickness.hh> +# include <mln/value/set.hh> +# include <mln/fun/i2v/all_to.hh> +# include <mln/core/line_piter.hh> +# include <fcntl.h> + +# include "support/lru.hh" +# include "backend/mmap.hh" +# include "layout/layout2d.hh" +# include "block.hh" +# include "page.hh" + +// FIXME : give the side's side of the square of the block. +# define SIDE 128 + +namespace mln +{ + + // Fwd decl. + template <typename T> struct tiled_image2d; + + + namespace internal + { + + /// \internal Data structure for \c mln::tiled_image2d<T>. + template <typename T> + struct data_< tiled_image2d<T> > + { + typedef block<T, SIDE * SIDE> block; + typedef mmap_backend<block> backend; + typedef lru_support<backend> support; + typedef layout2d<SIDE, SIDE> layout; + + data_(const box2d& b); + ~data_(); + + void prepare(const point2d& p) { + unsigned page_n = layout::image_layout::page_at(*this, p); + support_.prepare(page_n); + } + + support& support_; + + box2d b_; // theoretical box + unsigned bdr_; + }; + + } // end of namespace mln::internal + + + namespace trait + { + + template <typename T> + struct image_< tiled_image2d<T> > : default_image_< T, tiled_image2d<T> > + { + typedef trait::image::category::primary category; + + typedef trait::image::access::random access; + typedef trait::image::space::two_d space; + typedef trait::image::size::regular size; + typedef trait::image::support::aligned support; + + typedef trait::image::border::stored border; + typedef trait::image::data::linear data; + typedef trait::image::io::read_write io; + typedef trait::image::speed::fast speed; + }; + + } // end of namespace mln::trait + + + + /*! \brief FIXME. + * + * FIXME + */ + template <typename T> + struct tiled_image2d : public internal::image_primary_< box2d, tiled_image2d<T> > + { + // Warning: just to make effective types appear in Doxygen: + typedef box2d pset; + typedef point2d psite; + typedef point2d point; + typedef dpoint2d dpoint; + typedef mln_fwd_piter(box2d) fwd_piter; + typedef mln_bkd_piter(box2d) bkd_piter; + typedef line_piter_<point> line_piter; + // End of warning. + + + /// Value associated type. + typedef T value; + + /// Return type of read-only access. + typedef const T& rvalue; + + /// Return type of read-write access. + typedef T& lvalue; + + + /// Skeleton. + typedef tiled_image2d< tag::value_<T> > skeleton; + + + /// Value_Set associated type. + typedef mln::value::set<T> vset; + + /// Block type. + typedef block<T, SIDE * SIDE> block; + + /// Support type. + typedef lru_support<mmap_backend<block> > support; + /// Layout type + typedef layout2d<SIDE, SIDE> layout; + /// Page type + typedef page<T, layout> page; + + /// Constructor without argument. + tiled_image2d(); + + /// Constructor with the numbers of rows and columns + tiled_image2d(int nrows, int ncols); + + /// Constructor with a box (default is + /// 3). + tiled_image2d(const box2d& b); + + + /// Initialize an empty image. + void init_(const box2d& b); + + + /// Test if \p p is valid. + bool owns_(const point2d& p) const; + + /// Give the set of values of the image. + const vset& values() const; + + /// Give the definition domain. + const box2d& domain() const; + + /// Give the number of cells (points including border ones). + std::size_t ncells() const; + + /// Read-only access to the image value located at point \p p. + const T& operator()(const point2d& p) const; + + /// Read-write access to the image value located at point \p p. + T& operator()(const point2d& p); + + /// Read-only access to the image value located at offset \p o. + const T& operator[](unsigned o) const; + + /// Read-write access to the image value located at offset \p o. + T& operator[](unsigned o); + + /// Read-only access to the image value located at (\p row, \p col). + const T& at(int row, int col) const; + + /// Read-write access to the image value located at (\p row, \p col). + T& at(int row, int col); + + }; + + + + // Fwd decl. + + template <typename T, typename J> + void init_(tag::image_t, mln::tiled_image2d<T>& target, const J& model); + + + +# ifndef MLN_INCLUDE_ONLY + + // init_ + + template <typename T, typename J> + inline + void init_(tag::image_t, tiled_image2d<T>& target, const J& model) + { + box2d b; + init_(tag::bbox, b, model); + unsigned bdr; + target.init_(b); + } + + + // internal::data_< tiled_image2d<T> > + + namespace internal + { + template <typename T> + inline + data_< tiled_image2d<T> >::data_(const box2d& b) + : b_ (b), + // FIXME : hard coded path. + support_(*new support(*new backend( open("/tmp/milena_tiled.image", O_RDWR | O_CREAT | O_TRUNC, 0664), b.npoints()) )) + { + std::cout << b.npoints() * sizeof(T) << std::endl; + char a = 0; + lseek(support_.backend_.fd_, b.npoints() * sizeof(T) - 1, SEEK_SET); + write(support_.backend_.fd_, &a, 1); + } + + template <typename T> + inline + data_< tiled_image2d<T> >::~data_() + { + close(support_.backend_.fd_); + } + + } // end of namespace mln::internal + + + // tiled_image2d<T> + + template <typename T> + inline + tiled_image2d<T>::tiled_image2d() + { + } + + template <typename T> + inline + tiled_image2d<T>::tiled_image2d(int nrows, int ncols) + { + init_(make::box2d(nrows, ncols)); + } + + template <typename T> + inline + tiled_image2d<T>::tiled_image2d(const box2d& b) + { + init_(b); + } + + template <typename T> + inline + void + tiled_image2d<T>::init_(const box2d& b) + { + mln_precondition(! this->has_data()); + this->data_ = new internal::data_< tiled_image2d<T> >(b); + } + + template <typename T> + inline + const typename tiled_image2d<T>::vset& + tiled_image2d<T>::values() const + { + return vset::the(); + } + + template <typename T> + inline + const box2d& + tiled_image2d<T>::domain() const + { + mln_precondition(this->has_data()); + return this->data_->b_; + } + + template <typename T> + inline + std::size_t + tiled_image2d<T>::ncells() const + { + mln_precondition(this->has_data()); + return this->data_->b_.npoints(); + } + + template <typename T> + inline + bool + tiled_image2d<T>::owns_(const point2d& p) const + { + mln_precondition(this->has_data()); + return this->data_->b_.has(p); + } + + template <typename T> + inline + const T& + tiled_image2d<T>::operator()(const point2d& p) const + { + mln_precondition(this->owns_(p)); + unsigned page_n = layout::image_layout::page_at(*this, p); + // note: although the page instance goes + // out of scope, the reference stays valid + // because the block is ultimately held by support. + return page(const_cast<support&>(this->data_->support_).get_block(page_n)) + (layout::image_layout::changeref(p)); + } + + template <typename T> + inline + T& + tiled_image2d<T>::operator()(const point2d& p) + { + mln_precondition(this->owns_(p)); + unsigned page_n = layout::image_layout::page_at(*this, p); + // note: although the page instance goes + // out of scope, the reference stays valid + // because the block is ultimately held by support. + return page(this->data_->support_.get_block(page_n)) + (layout::image_layout::changeref(p)); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // ! MLN_CORE_TILED_IMAGE2D_HH Index: trunk/milena/sandbox/garrigues/tiled_image2d/block.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/block.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/block.hh (revision 1778) @@ -0,0 +1,63 @@ +// Copyright (C) 2007, 2008 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 block_hh +#define block_hh + +#include <cassert> + +namespace mln +{ + + template<typename T, unsigned size> + struct block : public Object< block<T, size> > { + typedef T value_type; + enum { nitems = size, nbytes = size * sizeof(T) }; + union { + char bytes[nbytes]; + T array[nitems]; + }; + + T& operator[](unsigned p) + { + assert(p < nitems); + return array[p]; + } + + const T& operator[](unsigned p) const + { + assert(p < nbytes); + return array[p]; + } + }; + + +} // end of namespace mln + + + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/page.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/page.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/page.hh (revision 1778) @@ -0,0 +1,91 @@ +// Copyright (C) 2007, 2008 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 page_hh +#define page_hh + +#include "block.hh" + +namespace mln +{ + + template <unsigned Dim, typename Layout> + struct page_domain {}; + + template<typename Layout> + struct page_domain<1, Layout> + { + enum {dim = 1}; + static unsigned len(unsigned) { return Layout::width; } + }; + template<typename Layout> + struct page_domain<2, Layout> + { + enum {dim = 2}; + static unsigned len(unsigned i) { return i ? Layout::height : Layout::width; } + }; + template<typename Layout> + struct page_domain<3, Layout> + { + enum {dim = 3}; + static unsigned len(unsigned i) { + return (i == 2) ? Layout::depth : (i ? Layout::height : Layout::depth); + } + }; + + template<typename T, typename Layout> + struct page : public Object< page<T, Layout> > + { + typedef Layout layout_type; + typedef block<T, Layout::w * Layout::h> block_type; + typedef T value_type; + typedef page_domain<Layout::dim, Layout> domain_type; + + static domain_type domain() + { return domain_type(); } + + page() {} + page(const page& p) : data_(p.data_) {} + page(block_type& p) : data_(&p) {} + + template<typename Point> + value_type& operator()(const Point& p) { + return (*data_)[layout_type::page_layout::pixel_at(p)]; + } + + template<typename Point> + const value_type& operator()(const Point& p) const { + return (*data_)[Layout::page_layout::pixel_at(p)]; + } + + block_type *data_; + }; + + +} // end of namespace mln + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/support/lru.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/support/lru.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/support/lru.hh (revision 1778) @@ -0,0 +1,198 @@ +// Copyright (C) 2007, 2008 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 lru_support_hh +#define lru_support_hh + +namespace mln +{ + + template<typename Block> + struct item { + item(unsigned n, item<Block>* first) + : block_number(n), prev(0), next(first) + { + if (first) + first->prev = this; + } + + + unsigned block_number; + item<Block> *prev; + item<Block> *next; + }; + +#ifdef LRU_DEBUG +#include <iostream> + + template<typename Item> + struct inspect_ { + inspect_(const Item *first, const Item *last) : first_(first), last_(last) {} + const Item * first_; + const Item * last_; + }; + template<typename Item> + std::ostream& operator<<(std::ostream& o, const inspect_<Item>& i) { + const Item *p = i.first_; + const Item *prev = 0; + while (p) { + assert(p->prev == prev); + o <prev << ',' << p->next << ':' << p->block_number << ')' << ' '; + prev = p; + p = p->next; + } + o << i.last_; + return o; + } + template<typename Item> + inspect_<Item> inspect(const Item *first, const Item* last) { return inspect_<Item>(first, last); } +#endif + + /* + LRU: least recently used gets evicted first + */ + template<typename Backend> + struct lru_support : public Object< lru_support<Backend> > { + + typedef typename Backend::block_type block_type; + typedef item<block_type> node_type; + + lru_support(Backend& b, unsigned buffer_size = 5) + : backend_(b), maxitems_(buffer_size), counter_(0), first_(0), last_(0) + { + assert(buffer_size > 1); + unsigned sz = b.size(); + map_ = new node_type* [sz]; + for (node_type **p = map_; p < map_ + sz; ++p) + *p = 0; + } + + ~lru_support() { + delete[] map_; + } + + void hit(node_type* node, unsigned n) { + assert(node->block_number == n); + if (first_ != node) { +#ifdef LRU_DEBUG + std::cerr << "lru: pull " << n << '<' << node << '>' << ' ' << inspect(first_,last_) << std::endl; +#endif + // move to head of queue + + if (node->next) // is last? + // no: patch up next node + node->next->prev = node->prev; + else + // yes + last_ = node->prev; + + // patch up previous node + node->prev->next = node->next; + + // insert in front + first_->prev = node; + node->next = first_; + node->prev = 0; + first_ = node; + +#ifdef LRU_DEBUG + std::cerr << "lru: end pull " << n << ' ' << inspect(first_,last_) << std::endl; +#endif + } + + } + + void evict_last() { + node_type *prev = last_->prev; + +#ifdef LRU_DEBUG + std::cerr << "lru: evict " << last_->block_number << ' ' << inspect(first_, last_) << std::endl; +#endif + backend_.forget(last_->block_number); + + map_[last_->block_number] = 0; + delete last_; + + prev->next = 0; + last_ = prev; + --counter_; + } + + node_type* miss(unsigned n) { +#ifdef LRU_DEBUG + std::cerr << "lru: miss " << n << ' ' << inspect(first_, last_) << std::endl; +#endif + + if (counter_ >= maxitems_) + evict_last(); + +#ifdef LRU_DEBUG + std::cerr << "lru: load " << n << ' ' << inspect(first_, last_) << std::endl; +#endif + + backend_.load(n); + + node_type *node = new node_type(n, first_); + map_[n] = node; + first_ = node; + + if (!last_) + // first item ever, becomes new last + last_ = node; + +#ifdef LRU_DEBUG + std::cerr << "lru: end miss " << n << ' ' << inspect(first_, last_) << std::endl; +#endif + + ++counter_; + return node; + } + + block_type& get_block(unsigned n) { + prepare(n); + return backend_.get(n); + } + + void prepare(unsigned n) { + if (node_type *node = map_[n]) + hit(node, n); + else + miss(n); + } + + Backend& backend_; + unsigned maxitems_; + unsigned counter_; + node_type **map_; + node_type *first_; + node_type *last_; + }; + + +} // end of namespace mln + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/support/simple.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/support/simple.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/support/simple.hh (revision 1778) @@ -0,0 +1,35 @@ +#ifndef simple_support_hh +#define simple_support_hh + +/* +Simple support: only one page in memory at a time. + */ +template<typename Backend> +struct simple_support { + + typedef typename Backend::block_type block_type; + + simple_support(Backend& b) + : backend_(b), current_(0) + { + backend_.load(0); + } + + void prepare(unsigned n) { + // no-op here + } + + block_type& get_block(unsigned n) { + if (n != current_) { + backend_.forget(current_); + backend_.load(n); + current_ = n; + } + return backend_.get(n); + } + + Backend& backend_; + unsigned current_; +}; + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.cc =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.cc (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/tiled_image2d.cc (revision 1778) @@ -0,0 +1,45 @@ +// 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/tiled_image2d.cc + * + * \brief Tests on mln::tiled_image2d. + */ + +#include "tiled_image2d.hh" + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> + +int main() +{ + using namespace mln; + + tiled_image2d<int> ima(10700, 10700); + + level::fill(ima, 6); +} Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/layout2d.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/layout2d.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/layout2d.hh (revision 1778) @@ -0,0 +1,56 @@ +// Copyright (C) 2007, 2008 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 layout2d_hh +#define layout2d_hh + +#include "block.hh" +#include "layout/image2d/lrtb.hh" +#include "layout/page2d/lrtb.hh" + +namespace mln +{ + + template<unsigned width, unsigned height, + template<unsigned,unsigned> class ImageLayout = layout::image2d_lrtb, + template<unsigned,unsigned> class PageLayout = layout::page2d_lrtb > + struct layout2d : public Object< layout2d<width, height> > { + enum { dim = 2 , w = width, h = height }; + + typedef ImageLayout<width, height> image_layout; + typedef PageLayout<width, height> page_layout; + + template<typename T> + struct block_ : block<T, width * height> {}; + + }; + + +} // end of namespace mln + + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/tblr.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/tblr.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/tblr.hh (revision 1778) @@ -0,0 +1,21 @@ +#ifndef layout_page2d_tblr_hh +#define layout_page2d_tblr_hh + +#include "ersatz/point.hh" + +namespace layout { + +template<unsigned W, unsigned H> +struct page2d_tblr { + enum { dim = 2, width = W, height = H, nitems = W * H }; + + template<typename C> + static unsigned pixel_at(const point2d_<C>& p) + { + return p[0] * height + p[1]; + } +}; + +} + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/lrtb.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/lrtb.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/lrtb.hh (revision 1778) @@ -0,0 +1,52 @@ +// Copyright (C) 2007, 2008 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 layout_page2d_lrtb_hh +#define layout_page2d_lrtb_hh + +#include <mln/core/point2d.hh> + +namespace mln +{ + + namespace layout { + + template<unsigned W, unsigned H> + struct page2d_lrtb { + enum { dim = 2, width = W, height = H, nitems = W * H }; + + static unsigned pixel_at(const point2d& p) + { + return p[1] * width + p[0]; + } + }; + + } + +} // end of namespace mln + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/all.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/all.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/page2d/all.hh (revision 1778) @@ -0,0 +1,7 @@ +#ifndef layout_page2d_all_hh +#define layout_page2d_all_hh + +#include "layout/page2d/lrtb.hh" +#include "layout/page2d/tblr.hh" + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/all.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/all.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/all.hh (revision 1778) @@ -0,0 +1,8 @@ +#ifndef layout_all_hh +#define layout_all_hh + +#include "layout/layout2d.hh" +#include "layout/page2d/all.hh" +#include "layout/image2d/all.hh" + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/tblr.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/tblr.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/tblr.hh (revision 1778) @@ -0,0 +1,33 @@ +#ifndef layout_image2d_tblr_hh +#define layout_image2d_tblr_hh + +#include "ersatz/point.hh" + +namespace layout { + +template<unsigned W, unsigned H> +struct image2d_tblr { + enum { dim = 2, page_width = W, page_height = H }; + + template<typename Image> + static unsigned size(const Image& im) { + const typename Image::domain_type& d = im.domain(); + return (d.len(0) / page_width ) * (d.len(1) / page_height); + } + + template<typename Image, typename C> + static unsigned page_at(const Image& im, const point2d_<C>& p) + { + return (p[0] / page_width) * (im.domain().len(1) / page_height) + p[1] / page_height; + }; + + template<typename C> + static point2d_<C> changeref(const point2d_<C>& p) + { + return point2d_<C(p[0] % page_width, p[1] % page_height); + } +}; + +} + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/lrtb.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/lrtb.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/lrtb.hh (revision 1778) @@ -0,0 +1,65 @@ +// Copyright (C) 2007, 2008 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 layout_image2d_lrtb_hh +#define layout_image2d_lrtb_hh + +#include <mln/core/point2d.hh> + +namespace mln +{ + + namespace layout { + + template<unsigned W, unsigned H> + struct image2d_lrtb : public Object<image2d_lrtb<W, H> > { + enum { dim = 2, page_width = W, page_height = H }; + + template<typename Image> + static unsigned size(const Image& im) { + const typename Image::domain_type& d = im.domain(); + return (d.len(0) / page_width ) * (d.len(1) / page_height); + } + + template<typename Image> + static unsigned page_at(const Image& im, const point2d& p) + { + return (p[1] / page_height) * (im.domain().len(0) / page_width) + p[0] / page_width; + }; + + static point2d changeref(const point2d& p) + { + return point2d(p[0] % page_width, p[1] % page_height); + } + }; + + } + + +} // end of namespace mln + +#endif Index: trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/all.hh =================================================================== --- trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/all.hh (revision 0) +++ trunk/milena/sandbox/garrigues/tiled_image2d/layout/image2d/all.hh (revision 1778) @@ -0,0 +1,7 @@ +#ifndef layout_image2d_all_hh +#define layout_image2d_all_hh + +#include "layout/image2d/lrtb.hh" +#include "layout/image2d/tblr.hh" + +#endif

1 0

1777: Miscellaneous fixes on morphological tests.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Miscellaneous fixes on morphological tests. * mln/morpho/dilation.hh (mln::morpho::dilation(const Image&, Image<O>&)) (mln::morpho::dilation(const Image&, const Window<W>&, Image<O>&)): Disable these routines. (mln::morpho::dilation(const Image&, const Window<W>&)): Add preconditions. * mln/win/rectangle2d.hh (mln::win::rectangle2d::psite): New typedef. * tests/morpho/Makefile.am (CXXFLAGS_SPEED): Append -DNDEBUG to speed up lengthy tests. * tests/morpho/dilation.cc: No longer use the dilation facades taking the output image as argument; instead, use the facades returning the output images as return value. * tests/morpho/lena_line_graph_image_wst1.cc: Use the psite associated to a point iterator on a line_graph_image, not the point. mln/morpho/dilation.hh | 43 ++++++++++++++++------------- mln/win/rectangle2d.hh | 3 ++ tests/morpho/Makefile.am | 2 - tests/morpho/dilation.cc | 12 ++------ tests/morpho/lena_line_graph_image_wst1.cc | 2 - 5 files changed, 33 insertions(+), 29 deletions(-) Index: mln/morpho/dilation.hh --- mln/morpho/dilation.hh (revision 1776) +++ mln/morpho/dilation.hh (working copy) @@ -28,11 +28,8 @@ #ifndef MLN_MORPHO_DILATION_HH # define MLN_MORPHO_DILATION_HH -/*! \file mln/morpho/dilation.hh - * - * \brief Morphological dilation. - * - */ +/// \file mln/morpho/dilation.hh +/// \brief Morphological dilation. # include <mln/morpho/includes.hh> @@ -47,14 +44,19 @@ /// /// \{ - /// Perform a morphological dilation of \a input using its - /// neighborhood and store the result into \a output. - /// - /// \pre \a input must be an image with a neighborhood. - /* FIXME: Do we want to keep this version? */ - template <typename I, typename O> - void - dilation(const Image& input, Image<O>& output); + /* FIXME: We'll probably get rid of the neighborhood-based + versions for Olena 1.0, and try to re-introduce them for + Olena 1.1. */ + + /* FIXME: Unless there's a good reason, we should get rid of this + version. */ +// /// Perform a morphological dilation of \a input using its +// /// neighborhood and store the result into \a output. +// /// +// /// \pre \a input must be an image with a neighborhood. +// template <typename I, typename O> +// void +// dilation(const Image& input, Image<O>& output); /// Perform a morphological dilation of \a input using its /// neighborhood and return the result. @@ -71,12 +73,13 @@ /// images. /// /// \{ - /// Perform a morphological dilation of \a input using \a win and - /// store the result into \a output. - /* FIXME: Do we want to keep this version? */ - template <typename I, typename W, typename O> - void - dilation(const Image& input, const Window<W>& win, Image<O>& output); + /* FIXME: Unless there's a good reason, we should get rid of this + version. */ +// /// Perform a morphological dilation of \a input using \a win and +// /// store the result into \a output. +// template <typename I, typename W, typename O> +// void +// dilation(const Image& input, const Window<W>& win, Image<O>& output); /// Perform a morphological dilation of \a input using \a win and /// return the result. @@ -334,6 +337,8 @@ dilation(const Image& input, const Window<W>& win) { trace::entering("morpho::dilation"); + mln_precondition(exact(input).has_data()); + mln_precondition(! exact(win).is_empty()); mln_concrete(I) output; initialize(output, input); Index: mln/win/rectangle2d.hh --- mln/win/rectangle2d.hh (revision 1776) +++ mln/win/rectangle2d.hh (working copy) @@ -59,6 +59,9 @@ struct rectangle2d : public Window< rectangle2d >, public internal::dpoints_base_< dpoint2d, rectangle2d > { + /// Point Site associated type. + typedef point2d psite; + /// Point associated type. typedef point2d point; Index: tests/morpho/Makefile.am --- tests/morpho/Makefile.am (revision 1776) +++ tests/morpho/Makefile.am (working copy) @@ -38,7 +38,7 @@ # FIXME: We should isolate those tests, as they take a long time to # execute. -CXXFLAGS_SPEED = -O3 -ggdb +CXXFLAGS_SPEED = -O3 -ggdb -DNDEBUG lena_line_graph_image_wst1_SOURCES = lena_line_graph_image_wst1.cc lena_line_graph_image_wst1_CXXFLAGS = $(CXXFLAGS_SPEED) lena_line_graph_image_wst2_SOURCES = lena_line_graph_image_wst2.cc Index: tests/morpho/dilation.cc --- tests/morpho/dilation.cc (revision 1776) +++ tests/morpho/dilation.cc (working copy) @@ -74,27 +74,23 @@ { win::rectangle2d rec(5, 3); - image2d<int_u8> out(lena.domain()); - morpho::dilation(lena, rec, out); + image2d<int_u8> out = morpho::dilation(lena, rec); io::pgm::save(out, "out1.pgm"); } { win::octagon2d oct(7); - image2d<int_u8> out(lena.domain()); - morpho::dilation(lena, oct, out); + image2d<int_u8> out = morpho::dilation(lena, oct); io::pgm::save(out, "out2.pgm"); } { - image2d<int_u8> out(lena.domain()); - morpho::dilation(lena + c4(), out); + image2d<int_u8> out = morpho::dilation(lena + c4()); io::pgm::save(out, "out3.pgm"); } { - image2d<int_u8> out(lena.domain()); - morpho::dilation(lena + c8(), out); + image2d<int_u8> out = morpho::dilation(lena + c8()); io::pgm::save(out, "out4.pgm"); } Index: tests/morpho/lena_line_graph_image_wst1.cc --- tests/morpho/lena_line_graph_image_wst1.cc (revision 1776) +++ tests/morpho/lena_line_graph_image_wst1.cc (working copy) @@ -221,7 +221,7 @@ { if (wshed(pw) == 0) { - mln_point_(wst_ima_t) pp(pw); + mln_psite_(wst_ima_t) pp(pw); // Equivalent of the line (edge) PP in OUTPUT. int row1 = pp.first()[0] * 2; int col1 = pp.first()[1] * 2;

1 0

1776: Fix mln::neighb::image initializations.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix mln::neighb::image initializations. * mln/neighb/image.hh (mln::neighb::image::image): New ctor. (mln::neighb::image::ima, mln::neighb::image::nbh): New accessors. (init_(tag::image_t, neighb::image<I, N>&, const neighb::image<J, N>&)): New. (mln::neighb::image::init_): New. Use this method... (mln::neighb::image<I, N>::image(Image&, const Neighborhood<N>&)): ...here. (mln::neighb::image<I, N>::has_data): Ensure the delegatee is not null. image.hh | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 71 insertions(+), 5 deletions(-) Index: mln/neighb/image.hh --- mln/neighb/image.hh (revision 1775) +++ mln/neighb/image.hh (working copy) @@ -34,6 +34,7 @@ # include <mln/core/internal/image_identity.hh> # include <mln/core/concept/neighborhood.hh> +// FIXME: Handle the constness of the underlying image. namespace mln { @@ -106,21 +107,55 @@ /// Skeleton. typedef image< tag::image_, tag::neighb_<N> > skeleton; - /// Constructor. + /// Constructors. + /// \{ + image(); image(Image& ima, const Neighborhood<N>& nbh); + /// \} /// Test if this image has been initialized. bool has_data() const; + /// Accessors. + /// \{ + /// Return the underlying image, read-only. + const I& ima() const; + /// Return the underlying image, read-write. + I& ima(); + // FIXME: Rename to nbh(). /// Return the neighborhood associated to this image. const neighb& neighborhood() const; + /// \} + + /// Initialize an empty image. + void init_(Image& ima, const Neighborhood<N>& nbh); }; } // end of namespace mln::neighb + // Fwd decl. + template <typename I, typename J, typename N> + void init_(tag::image_t, + neighb::image<I, N>& target, const neighb::image<J, N>& model); + + + # ifndef MLN_INCLUDE_ONLY + /*-----------------. + | Initialization. | + `-----------------*/ + + template <typename I, typename J, typename N> + void init_(tag::image_t, + neighb::image<I, N>& target, const neighb::image<J, N>& model) + { + I ima; + initialize(ima, model.ima()); + target.init_(ima, model.neighborhood()); + } + /*------------. | operator+. | `------------*/ @@ -133,9 +168,9 @@ return tmp; } - /*--------------------------------------. - | internal::data_< cast_image_<T,I> >. | - `--------------------------------------*/ + /*-----------------------------------------. + | internal::data_< neighb::image_<T,I> >. | + `-----------------------------------------*/ namespace internal { @@ -157,8 +192,23 @@ template <typename I, typename N> inline + image<I, N>::image() + { + } + + template <typename I, typename N> + inline image<I, N>::image(Image& ima, const Neighborhood<N>& nbh) { + init_(ima, nbh); + } + + template <typename I, typename N> + inline + void + image<I, N>::init_(Image& ima, const Neighborhood<N>& nbh) + { + mln_precondition(! this->has_data()); this->data_ = new mln::internal::data_< mln::neighb::image<I, N> >(exact(ima), exact(nbh)); @@ -169,7 +219,23 @@ bool image<I, N>::has_data() const { - return this->delegatee_()->has_data(); + return this->delegatee_() && this->delegatee_()->has_data(); + } + + template <typename I, typename N> + inline + I& + image<I, N>::ima() + { + return this->data_->ima_; + } + + template <typename I, typename N> + inline + const I& + image<I, N>::ima() const + { + return this->data_->ima_; } template <typename I, typename N>

1 0

1775: Have area closing and opening work on line graph images.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have area closing and opening work on line graph images. * mln/core/concept/point_set.hh (mln::Point_Set<E>::Point_Set): No longer require the presence of a bounding box. * mln/core/concept/point_site.hh: Add a FIXME. * mln/level/sort_points.hh: Wrap long lines. (sort_points_increasing_(trait::image::quant::low, const I&)) (sort_points_decreasing_(trait::image::quant::low, const I&)): Fix the initialization of the return value. * mln/level/sort_psites.hh: New. Use it... * mln/morpho/closing_attribute.hh, * mln/morpho/opening_attribute.hh: ...here. s/point/psite/ * mln/canvas/morpho/algebraic_union_find.hh, * mln/labeling/regional_minima.hh, * mln/convert/to_p_array.hh: Likewise. * mln/core/p_array.hh (mln::p_array::psite, mln::p_array::point): New typedefs. (mln::p_array::has): Tale a psite as argument, not a point. s/box_/box_<point>/. * mln/core/p_array_piter.hh (mln::p_array_fwd_piter_::psite) (mln::p_array_fwd_piter_::point): (mln::p_array_bkd_piter_::psite) (mln::p_array_bkd_piter_::point): New typedefs. (mln::p_array_fwd_piter_::to_psite) (mln::p_array_fwd_piter_::operator psite): (mln::p_array_bkd_piter_::to_psite) (mln::p_array_bkd_piter_::operator psite): New. (mln::p_array_fwd_piter_::operator P): (mln::p_array_bkd_piter_::operator P): Remove. (mln::p_array_fwd_piter_::p_) (mln::p_array_bkd_piter_::p_): Change the type of this member from P to psite. (mln::p_array_fwd_piter_::to_point) (mln::p_array_fwd_piter_::operator[](unsigned)): (mln::p_array_bkd_piter_::to_point) (mln::p_array_bkd_piter_::operator[](unsigned)): Fix return types. * tests/morpho/lena_line_graph_image_wst2.cc: Simplify the line graph image using an area closing, instead of simplifying the initial (image2d) image. mln/canvas/morpho/algebraic_union_find.hh | 19 +- mln/convert/to_p_array.hh | 16 - mln/core/concept/point_set.hh | 9 - mln/core/concept/point_site.hh | 2 mln/core/p_array.hh | 13 + mln/core/p_array_piter.hh | 105 ++++++++---- mln/labeling/regional_minima.hh | 4 mln/level/sort_points.hh | 14 - mln/level/sort_psites.hh | 244 +++++++++++++++++++++++++++++ mln/morpho/closing_attribute.hh | 6 mln/morpho/opening_attribute.hh | 6 tests/morpho/lena_line_graph_image_wst2.cc | 39 ++-- 12 files changed, 383 insertions(+), 94 deletions(-) Index: mln/core/concept/point_set.hh --- mln/core/concept/point_set.hh (revision 1774) +++ mln/core/concept/point_set.hh (working copy) @@ -77,8 +77,10 @@ typedef bkd_piter; bool has(const psite& p) const; - const box_<point>& bbox() const; std::size_t npoints() const; + + // FIXME: No longer required (at least, not this way). + const box_<point>& bbox() const; */ protected: @@ -157,8 +159,9 @@ bool (E::*m1)(const psite& p) const = & E::has; m1 = 0; - const box_<point>& (E::*m2)() const = & E::bbox; - m2 = 0; + // FIXME: No longer required (at least, not this way). +// const box_<point>& (E::*m2)() const = & E::bbox; +// m2 = 0; std::size_t (E::*m3)() const = & E::npoints; m3 = 0; } Index: mln/core/concept/point_site.hh --- mln/core/concept/point_site.hh (revision 1774) +++ mln/core/concept/point_site.hh (working copy) @@ -338,6 +338,8 @@ return tmp; } + // FIXME: We shall not rely on a point object associted to the point + // site! (Such an object does not always exist.) template <typename P> inline std::ostream& operator<<(std::ostream& ostr, const Point_Site& p_) Index: mln/level/sort_points.hh --- mln/level/sort_points.hh (revision 1774) +++ mln/level/sort_points.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 @@ -156,8 +156,7 @@ for_all(p) vec[loc[vset.index_of(input(p))]++] = p; - p_array<mln_point(I)> v; - v.hook_() = vec; + p_array<mln_point(I)> v(vec); return v; } @@ -201,8 +200,7 @@ for_all(p) vec[loc[vset.index_of(input(p))]++] = p; - p_array<mln_point(I)> v; - v.hook_() = vec; + p_array<mln_point(I)> v(vec); return v; } @@ -218,7 +216,8 @@ sort_points_increasing(const Image& input) { mln_precondition(exact(input).has_data()); - return impl::sort_points_increasing_(mln_trait_image_quant(I)(), exact(input)); + return impl::sort_points_increasing_(mln_trait_image_quant(I)(), + exact(input)); } template <typename I> @@ -227,7 +226,8 @@ sort_points_decreasing(const Image& input) { mln_precondition(exact(input).has_data()); - return impl::sort_points_decreasing_(mln_trait_image_quant(I)(), exact(input)); + return impl::sort_points_decreasing_(mln_trait_image_quant(I)(), + exact(input)); } # endif // ! MLN_INCLUDE_ONLY Index: mln/level/sort_psites.hh --- mln/level/sort_psites.hh (revision 0) +++ mln/level/sort_psites.hh (revision 0) @@ -0,0 +1,244 @@ +// 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 +// 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_LEVEL_SORT_PSITES_HH +# define MLN_LEVEL_SORT_PSITES_HH + +/*! \file mln/level/sort_psites.hh + * + * \brief Sort_Psites the contents of an image into another one. + * + * \todo Factor code + optimize. + */ + +/* FIXME: Factor with mln/level/sort_points.hh, if needed (maybe wait + for the upcoming big changes regarding types associated to images + (point -> site, etc.). */ + +# include <algorithm> + +# include <mln/core/concept/image.hh> +# include <mln/convert/to_p_array.hh> +# include <mln/histo/compute.hh> + + +namespace mln +{ + + namespace level + { + + /*! Sort psites the image \p input through a function \p f to set + * the \p output image in increasing way. + * + * \param[in] input The input image. + * + * \pre \p input.has_data + */ + template <typename I> + p_array<mln_psite(I)> sort_psites_increasing(const Image& input); + + /*! Sort psites the image \p input through a function \p f to set + * the \p output image in decreasing way. + * + * \param[in] input The input image. + * + * \pre \p input.has_data + */ + template <typename I> + p_array<mln_psite(I)> sort_psites_decreasing(const Image& input); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // utility + + template <typename I> + struct value_psite_less_ + { + const I& ima_; + + inline + value_psite_less_(const I& ima) + : ima_(ima) + { + } + + inline + bool operator()(const mln_psite(I)& lhs, + const mln_psite(I)& rhs) const + { + return ima_(lhs) < ima_(rhs) || (ima_(lhs) == ima_(rhs) + && lhs < rhs); + } + }; + + template <typename I> + struct value_psite_greater_ + { + const I& ima_; + + inline + value_psite_greater_(const I& ima) + : ima_(ima) + { + } + + inline + bool operator()(const mln_psite(I)& lhs, + const mln_psite(I)& rhs) const + { + return ima_(lhs) > ima_(rhs) || (ima_(lhs) == ima_(rhs) + && lhs > rhs); + } + }; + + + // increasing + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_increasing_(trait::image::quant::any, // general case + const I& input) + { + p_array<mln_psite(I)> v = convert::to_p_array(input.domain()); + std::sort(v.hook_().begin(), v.hook_().end(), + value_psite_less_(input)); + return v; + } + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_increasing_(trait::image::quant::low, // low quantization + const I& input) + { + typedef mln_vset(I) S; + const S& vset = input.values(); + const unsigned n = vset.nvalues(); + + // h + histo::data<S> h = histo::compute(input); + + // preparing output data + std::vector<unsigned> loc(vset.nvalues()); + loc[0] = 0; + for (unsigned i = 1; i != n; ++i) + loc[i] = loc[i-1] + h[i-1]; + + // computing output data + std::vector<mln_psite(I)> vec(input.npoints()); + mln_fwd_piter(I) p(input.domain()); + for_all(p) + vec[loc[vset.index_of(input(p))]++] = p; + + p_array<mln_psite(I)> v(vec); + return v; + } + + + // decreasing + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_decreasing_(trait::image::quant::any, // general case + const I& input) + { + p_array<mln_psite(I)> v = convert::to_p_array(input.domain()); + std::sort(v.hook_().begin(), v.hook_().end(), + value_psite_greater_(input)); + return v; + } + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_decreasing_(trait::image::quant::low, // low quantization + const I& input) + { + typedef mln_vset(I) S; + const S& vset = input.values(); + const unsigned n = vset.nvalues(); + + // h + histo::data<S> h = histo::compute(input); + + // preparing output data + std::vector<unsigned> loc(vset.nvalues()); + loc[n-1] = 0; + for (int i = n - 2; i >= 0; --i) + loc[i] = loc[i+1] + h[i+1]; + + // computing output data + std::vector<mln_psite(I)> vec(input.npoints()); + mln_fwd_piter(I) p(input.domain()); + for_all(p) + vec[loc[vset.index_of(input(p))]++] = p; + + p_array<mln_psite(I)> v(vec); + return v; + } + + + } // end of namespace mln::level::impl + + + // Facades. + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_increasing(const Image& input) + { + mln_precondition(exact(input).has_data()); + return impl::sort_psites_increasing_(mln_trait_image_quant(I)(), + exact(input)); + } + + template <typename I> + inline + p_array<mln_psite(I)> + sort_psites_decreasing(const Image& input) + { + mln_precondition(exact(input).has_data()); + return impl::sort_psites_decreasing_(mln_trait_image_quant(I)(), + exact(input)); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::level + +} // end of namespace mln + + +#endif // ! MLN_LEVEL_SORT_PSITES_HH Index: mln/morpho/closing_attribute.hh --- mln/morpho/closing_attribute.hh (revision 1774) +++ mln/morpho/closing_attribute.hh (working copy) @@ -35,7 +35,7 @@ # include <mln/morpho/includes.hh> # include <mln/canvas/morpho/algebraic_union_find.hh> -# include <mln/level/sort_points.hh> +# include <mln/level/sort_psites.hh> # include <mln/util/pix.hh> @@ -66,7 +66,7 @@ typename I_, typename N_, typename O_> struct closing_attribute_t { - typedef mln_point(I_) P; + typedef mln_psite(I_) P; // requirements from mln::canvas::morpho::algebraic_union_find @@ -108,7 +108,7 @@ closing_attribute_t(const I_& input, const N_& nbh, mln_result(A) lambda, O_& output) : input(input), nbh(nbh), lambda(lambda), output(output), - s(level::sort_points_increasing(input)) + s(level::sort_psites_increasing(input)) { } Index: mln/morpho/opening_attribute.hh --- mln/morpho/opening_attribute.hh (revision 1774) +++ mln/morpho/opening_attribute.hh (working copy) @@ -35,7 +35,7 @@ # include <mln/morpho/includes.hh> # include <mln/canvas/morpho/algebraic_union_find.hh> -# include <mln/level/sort_points.hh> +# include <mln/level/sort_psites.hh> # include <mln/util/pix.hh> @@ -66,7 +66,7 @@ typename I_, typename N_, typename O_> struct opening_attribute_t { - typedef mln_point(I_) P; + typedef mln_psite(I_) P; // requirements from mln::canvas::morpho::algebraic_union_find @@ -108,7 +108,7 @@ opening_attribute_t(const I_& input, const N_& nbh, mln_result(A) lambda, O_& output) : input(input), nbh(nbh), lambda(lambda), output(output), - s(level::sort_points_decreasing(input)) + s(level::sort_psites_decreasing(input)) { } Index: mln/canvas/morpho/algebraic_union_find.hh --- mln/canvas/morpho/algebraic_union_find.hh (revision 1774) +++ mln/canvas/morpho/algebraic_union_find.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 @@ -60,11 +60,11 @@ typedef typename F::O O; typedef typename F::S S; typedef typename F::A A; - typedef mln_point(I) point; + typedef mln_psite(I) psite; // aux: mln_ch_value(O, bool) deja_vu; - mln_ch_value(O, point) parent; + mln_ch_value(O, psite) parent; mln_ch_value(O, A) data; algebraic_union_find(F& f) @@ -83,6 +83,7 @@ initialize(data, f.input); f.init(); } + // first pass { mln_fwd_piter(S) p(f.s); @@ -116,18 +117,18 @@ } // end of run() - void make_set(const point& p) + void make_set(const psite& p) { parent(p) = p; data(p).take_as_init(make::pix(f.input, p)); // FIXME: algebraic so p! } - bool is_root(const point& p) const + bool is_root(const psite& p) const { return parent(p) == p; } - point find_root(const point& x) + psite find_root(const psite& x) { if (parent(x) == x) return x; @@ -135,15 +136,15 @@ return parent(x) = find_root(parent(x)); } - bool equiv(const point2d& r, const point2d& p) + 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)); } - void do_union(const point& n, const point& p) + void do_union(const psite& n, const psite& p) { - point r = find_root(n); + psite r = find_root(n); if (r != p) { if (equiv(r, p)) Index: mln/labeling/regional_minima.hh --- mln/labeling/regional_minima.hh (revision 1774) +++ mln/labeling/regional_minima.hh (working copy) @@ -38,7 +38,7 @@ # include <mln/core/concept/neighborhood.hh> # include <mln/canvas/labeling.hh> # include <mln/level/fill.hh> -# include <mln/level/sort_points.hh> +# include <mln/level/sort_psites.hh> namespace mln @@ -107,7 +107,7 @@ regional_minima_functor(const I_& input, const N_& nbh) : input(input), nbh(nbh), - s(level::sort_points_increasing(input)), // FIXME: + s(level::sort_psites_increasing(input)), // FIXME: // sort_psites_increasing attr(input.domain()) { Index: mln/convert/to_p_array.hh --- mln/convert/to_p_array.hh (revision 1774) +++ mln/convert/to_p_array.hh (working copy) @@ -45,14 +45,14 @@ /// Convert a point set \p pset into a p_array (point set vector). template <typename S> - p_array<mln_point(S)> to_p_array(const Point_Set<S>& pset); + p_array<mln_psite(S)> to_p_array(const Point_Set<S>& pset); /// Convert a window \p win centered at point \p p into a p_array /// (point set vector). template <typename W> - p_array<mln_point(W)> to_p_array(const Window<W>& win, - const mln_point(W)& p); + p_array<mln_psite(W)> to_p_array(const Window<W>& win, + const mln_psite(W)& p); @@ -60,10 +60,10 @@ template <typename S> inline - p_array<mln_point(S)> to_p_array(const Point_Set<S>& pset_) + p_array<mln_psite(S)> to_p_array(const Point_Set<S>& pset_) { const S& pset = exact(pset_); - p_array<mln_point(S)> v; + p_array<mln_psite(S)> v; v.reserve(pset.npoints()); mln_fwd_piter(S) p(pset); for_all(p) @@ -73,10 +73,10 @@ template <typename W> inline - p_array<mln_point(W)> to_p_array(const Window<W>& win, - const mln_point(W)& p) + p_array<mln_psite(W)> to_p_array(const Window<W>& win, + const mln_psite(W)& p) { - p_array<mln_point(W)> v; + p_array<mln_psite(W)> v; v.reserve(exact(win).ndpoints()); mln_qiter(W) q(win, p); for_all(q) Index: mln/core/p_array.hh --- mln/core/p_array.hh (revision 1774) +++ mln/core/p_array.hh (working copy) @@ -60,6 +60,11 @@ class p_array : public internal::point_set_base_< P, p_array > { public: + /// The associated psite type. + typedef P psite; + + /// The associated point type. + typedef mln_point(P) point; /// Forward Point_Iterator associated type. typedef p_array_fwd_piter_ fwd_piter; @@ -77,13 +82,13 @@ void reserve(std::size_t n); /// Test is \p p belongs to this point set. - bool has(const P& p) const; + bool has(const psite& p) const; /// Give the number of points. std::size_t npoints() const; /// Give the exact bounding box. - const box_& bbox() const; + const box_<point>& bbox() const; /// Append a point \p p. p_array& append(const P& p); @@ -103,7 +108,7 @@ protected: std::vector vect_; - mutable accu::bbox bb_; + mutable accu::bbox<point> bb_; mutable bool bb_needs_update_; void update_bb_() const; @@ -177,7 +182,7 @@ template <typename P> inline - const box_& + const box_<mln_point(P)>& p_array::bbox() const { mln_precondition(npoints() != 0); Index: mln/core/p_array_piter.hh --- mln/core/p_array_piter.hh (revision 1774) +++ mln/core/p_array_piter.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,10 +28,8 @@ #ifndef MLN_CORE_P_ARRAY_PITER_HH # define MLN_CORE_P_ARRAY_PITER_HH -/*! \file mln/core/p_array_piter.hh - * - * \brief Definition of point iterators on mln::p_array. - */ +/// \file mln/core/p_array_piter.hh +/// \brief Definition of point iterators on mln::p_array. # include <mln/core/p_array.hh> @@ -39,28 +37,34 @@ namespace mln { - /*! \brief Forward iterator on points of a p_array. - * - */ + /// \brief Forward iterator on points of a p_array. template <typename P> - struct p_array_fwd_piter_ : public internal::point_iterator_base_< P, p_array_fwd_piter_ > + struct p_array_fwd_piter_ + : public internal::point_iterator_base_< P, p_array_fwd_piter_ > { typedef p_array_fwd_piter_ self_; typedef internal::point_iterator_base_< P, self_ > super_; public: + /// The associated psite type. + typedef P psite; + + /// The associated point type. + typedef mln_point(P) point; - // Make definitions from super class available. enum { dim = super_::dim }; /// Coordinate associated type. template <typename S> p_array_fwd_piter_(const Point_Set<S>& s); + /// Reference of the corresponding psite. + const psite& to_psite() const; + /// Reference of the corresponding point. - const P& to_point() const; + const point& to_point() const; /// Read-only access to the \p i-th coordinate. - mln_coord(P) operator[](unsigned i) const; + mln_coord(point) operator[](unsigned i) const; /// Test if the iterator is valid. bool is_valid() const; @@ -74,39 +78,46 @@ /// Go to the next point. void next_(); - /// Convert the iterator into a point. - operator P() const; + /// Convert the iterator into a psite. + operator psite() const; protected: const std::vector& vect_; - unsigned i_; // FIXME: Why it's unsigned in fwd iterator and signed in the bkd one ? - P p_; + // FIXME: Why it's unsigned in fwd iterator and signed in the bkd one ? + unsigned i_; + psite p_; }; - /*! \brief Backward iterator on points of a p_array. - * - */ + /// \brief Backward iterator on points of a p_array. template <typename P> - struct p_array_bkd_piter_ : public internal::point_iterator_base_< P, p_array_bkd_piter_ > + struct p_array_bkd_piter_ + : public internal::point_iterator_base_< P, p_array_bkd_piter_ > { typedef p_array_bkd_piter_ self_; typedef internal::point_iterator_base_< P, self_ > super_; public: + /// The associated psite type. + typedef P psite; + + /// The associated point type. + typedef mln_point(P) point; - // Make definitions from super class available. enum { dim = super_::dim }; /// Coordinate associated type. template <typename S> p_array_bkd_piter_(const Point_Set<S>& s); + /// Reference of the corresponding psite. + const psite& to_psite() const; + /// Reference of the corresponding point. - const P& to_point() const; + const point& to_point() const; /// Read-only access to the \p i-th coordinate. - mln_coord(P) operator[](unsigned i) const; + mln_coord(point) operator[](unsigned i) const; /// Test if the iterator is valid. bool is_valid() const; @@ -120,20 +131,28 @@ /// Go to the next point. void next_(); - /// Convert the iterator into a point. - operator P() const; + /// Convert the iterator into a psite. + operator psite() const; protected: const std::vector& vect_; + /* FIXME: See the comment on p_array_fwd_piter_::i_ above. We + could turn this `int' into an `unsigned'. Then, + - setting the value of i_ to -1 (== UINT_MAX) in invalidate(), + - and having valid() test whether i_ is strictly smaller than + vect_.size() + should work in both iterators (fwd and bkd). */ int i_; - P p_; + psite p_; }; # ifndef MLN_INCLUDE_ONLY - // p_array_fwd_piter_ + /*------------------------. + | p_array_fwd_piter_. | + `------------------------*/ template <typename P> template <typename S> @@ -147,19 +166,27 @@ template <typename P> inline const P& - p_array_fwd_piter_::to_point() const + p_array_fwd_piter_::to_psite() const { return p_; } template <typename P> inline - mln_coord(P) + const mln_point(P)& + p_array_fwd_piter_::to_point() const + { + return p_.to_point(); + } + + template <typename P> + inline + mln_coord(mln_point_(P)) p_array_fwd_piter_::operator[](unsigned i) const { mln_precondition(i < dim); mln_precondition(is_valid()); - return p_[i]; + return p_.to_point()[i]; } template <typename P> @@ -207,7 +234,9 @@ } - // p_array_bkd_piter_ + /*------------------------. + | p_array_bkd_piter_. | + `------------------------*/ template <typename P> template <typename S> @@ -221,19 +250,27 @@ template <typename P> inline const P& - p_array_bkd_piter_::to_point() const + p_array_bkd_piter_::to_psite() const { return p_; } template <typename P> inline - mln_coord(P) + const mln_point(P)& + p_array_bkd_piter_::to_point() const + { + return p_.to_point(); + } + + template <typename P> + inline + mln_coord(mln_point_(P)) p_array_bkd_piter_::operator[](unsigned i) const { mln_precondition(i < dim); mln_precondition(is_valid()); - return p_[i]; + return p_.to_point()[i]; } template <typename P> Index: tests/morpho/lena_line_graph_image_wst2.cc --- tests/morpho/lena_line_graph_image_wst2.cc (revision 1774) +++ tests/morpho/lena_line_graph_image_wst2.cc (working copy) @@ -34,7 +34,6 @@ \brief More tests on the Watershed Transform (WST) on a mln::line_graph_image. - The scenario is as follows: \li load a 2-D, gray-level image from a PGM file; \li simplify the image to reduce the number of local minima; @@ -99,14 +98,6 @@ image2d<input_val_t> input; io::pgm::load(input, MLN_IMG_DIR "/small.pgm"); - /* FIXME: In fact, we'd probably want to compute the gradient - /before/ simplfying the image, but as the area closing doesn't - work (yet) on graph images, hence we cannot do this yet. */ - - // Simplify the input image. - image2d<input_val_t> work(input.domain()); - morpho::closing_area(input, c8(), 500, work); - /*-------------. | Line graph. | `-------------*/ @@ -118,18 +109,18 @@ // Points. /* FIXME: The need for such a structure during the conversion exhibits the lack of a service from util::graph (or a another, - missing tool) regarding the retrieval of node ids from + missing tool) regarding the retrieval of nodes' ids from points. */ std::map<point2d, util::node_id> points; util::node_id id = 0; // Nodes. std::vector<input_val_t> node_values; - mln_fwd_piter_(image2d<input_val_t>) p(work.domain()); + mln_fwd_piter_(image2d<input_val_t>) p(input.domain()); for_all (p) { g.add_node (p); - node_values.push_back (work(p)); + node_values.push_back (input(p)); /* FIXME: ``Guessing'' the id of the point just being inserted is bad. utill:graph<N,E>::add_node should return this id. */ @@ -144,12 +135,12 @@ mln_fwd_qiter_(window2d) q(next_c4_win, p); for_all (p) for_all (q) - if (work.has(q)) + if (input.has(q)) { g.add_edge(points[p], points[q]); // The computed value is a kind of norm of the gradient // bewteen P and Q. - edge_values.push_back(math::abs(work(p) - work(q))); + edge_values.push_back(math::abs(input(p) - input(q))); } // Line graph point set. @@ -163,21 +154,27 @@ | Simplification. | `-----------------*/ - // FIXME: Adjust the area closing filter, so that we can apply it on - // graph images. + typedef line_graph_elt_neighborhood<point2d> nbh_t; + nbh_t nbh; + + ima_t closed_lg_ima (lg_ima.domain()); + /* FIXME: We should change the attribute closing performed here; + instead of computing the area using the data on the lines + (edges), whe should use the data on the pixels (vertices). + + The best way is probably to create another attribute-functor and + use the algebraic_union_find canvas. */ + morpho::closing_area(lg_ima, nbh, 20, closed_lg_ima); /*------. | WST. | `------*/ - typedef line_graph_elt_neighborhood<point2d> nbh_t; - nbh_t nbh; - // Perform a Watershed Transform. typedef int_u16 wst_full_val_t; wst_full_val_t nbasins; typedef line_graph_image<point2d, wst_full_val_t> wst_full_ima_t; - wst_full_ima_t wshed_full = morpho::meyer_wst(lg_ima, nbh, nbasins); + wst_full_ima_t wshed_full = morpho::meyer_wst(closed_lg_ima, nbh, nbasins); std::cout << "nbasins = " << nbasins << std::endl; // Reduce the value set to 8-bit. @@ -243,7 +240,7 @@ { if (wshed(pw) == 0) { - mln_point_(wst_ima_t) pp(pw); + mln_psite_(wst_ima_t) pp(pw); // Equivalent of the line (edge) PP in OUTPUT. int row1 = pp.first()[0] * 2; int col1 = pp.first()[1] * 2;

1 0

1774: Fix morphological erosion implementation based on pixters.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix morphological erosion implementation based on pixters. * mln/core/dpoints_pixter.hh (dpoints_fwd_pixter::next_): Don't update member value_ptr_ when the pixter is invalid. * mln/morpho/erosion.hh, mln/morpho/erosion.spe.hh: Fix indentation. Aesthetic chnanges. core/dpoints_pixter.hh | 1 + morpho/erosion.hh | 8 +++----- morpho/erosion.spe.hh | 2 ++ 3 files changed, 6 insertions(+), 5 deletions(-) Index: mln/core/dpoints_pixter.hh --- mln/core/dpoints_pixter.hh (revision 1773) +++ mln/core/dpoints_pixter.hh (working copy) @@ -211,6 +211,7 @@ dpoints_fwd_pixter::next_() { ++i_; + if (is_valid()) this->value_ptr_ += offset_[i_]; } Index: mln/morpho/erosion.hh --- mln/morpho/erosion.hh (revision 1773) +++ mln/morpho/erosion.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 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 @@ -28,10 +28,8 @@ #ifndef MLN_MORPHO_EROSION_HH # define MLN_MORPHO_EROSION_HH -/*! \file mln/morpho/erosion.hh - * - * \brief Morphological erosion. - */ +/// \file mln/morpho/erosion.hh +/// \brief Morphological erosion. # include <mln/morpho/includes.hh> Index: mln/morpho/erosion.spe.hh --- mln/morpho/erosion.spe.hh (revision 1773) +++ mln/morpho/erosion.spe.hh (working copy) @@ -88,11 +88,13 @@ namespace generic { // Fwd decl. + // Implementation is in mln/morpho/erosion.hh. template <typename I, typename W> mln_concrete(I) erosion_on_function_(const I& input, const W& win); // Fwd decl. + // Implementation is in mln/morpho/erosion.hh. template <typename I, typename W> mln_concrete(I) erosion_on_set_(const I& input, const W& win);

1 0

1773: Partially check point sets compatibility.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Partially check point sets compatibility. * tests/core/point_set_compatibility.cc: New test. * tests/core/Makefile.am (check_PROGRAMS): Add point_set_compatibility. (point_set_compatibility_SOURCES): New. Makefile.am | 2 + point_set_compatibility.cc | 89 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 91 insertions(+) Index: tests/core/point_set_compatibility.cc --- tests/core/point_set_compatibility.cc (revision 0) +++ tests/core/point_set_compatibility.cc (revision 0) @@ -0,0 +1,89 @@ +// Copyright (C) 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 +// 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/core/point_set_compatibility.cc +/// \brief Tests on the compatibility of some point sites with some +/// point sets (and their iterators). + +#include <mln/core/point2d.hh> + +#include <mln/core/p_array.hh> +#include <mln/core/graph_psite.hh> +#include <mln/core/p_graph_piter.hh> + + +int main() +{ + using namespace mln; + + /*--------------------------------------------------------. + | Compatibility of mln::graph_psite with mln::p_array and | + | mln::p_array_piter. | + `--------------------------------------------------------*/ + + // Graph. + + // Points associated to nodes. + std::vector<point2d> points; + points.push_back(make::point2d(0,0)); // Point associated to node 0. + points.push_back(make::point2d(2,2)); // Point associated to node 1. + points.push_back(make::point2d(0,4)); // Point associated to node 2. + points.push_back(make::point2d(4,3)); // Point associated to node 3. + points.push_back(make::point2d(4,4)); // Point associated to node 4. + + // Edges. + util::graph<point2d> g; + // Populate the graph with nodes. + for (unsigned i = 0; i < points.size(); ++i) + g.add_node (points[i]); + // Populate the graph with edges. + g.add_edge(0, 1); + g.add_edge(1, 2); + g.add_edge(1, 3); + g.add_edge(3, 4); + g.add_edge(4, 2); + + + // Graph point set. + p_graph<point2d> pg(g); + + + // Array of graph point sites. + typedef graph_psite<point2d> gpsite_t; + p_array<gpsite_t> pa; + + + // Tests: copying all psites from PG to PA. + p_graph_fwd_piter_<point2d> p(pg); + for_all (p) + pa.append (p); + + // Test: create and use an iterator over PA. + p_array_fwd_piter_<gpsite_t> p2(pa); + for_all (p2) + std::cout << p2 << std::endl; +} Index: tests/core/Makefile.am --- tests/core/Makefile.am (revision 1772) +++ tests/core/Makefile.am (working copy) @@ -22,6 +22,7 @@ p_queue \ p_queue_fast \ p_runs \ + point_set_compatibility \ rle_image \ sparse_image \ t_image \ @@ -46,6 +47,7 @@ p_queue_SOURCES = p_priority_queue_fast.cc p_queue_fast_SOURCES = p_priority_queue_fast.cc p_runs_SOURCES = p_runs.cc +point_set_compatibility_SOURCES = point_set_compatibility.cc rle_image_SOURCES = rle_image.cc sparse_image_SOURCES = sparse_image.cc t_image_SOURCES = t_image.cc

1 0

1772: Add backward iterators on line graph windows and neighborhoods.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Add backward iterators on line graph windows and neighborhoods. * mln/core/line_graph_window_piter.hh: Add more documentation. (mln::line_graph_window_fwd_piter::point): Set typedef to P. (mln::line_graph_window_fwd_piter::to_point) (mln::line_graph_window_fwd_piter::operator[](unsigned)): Adjust return types. (mln::line_graph_window_fwd_piter::operator point): Remove. (line_graph_window_fwd_piter(const W&, const Point_Site<Pref>&)) (line_graph_window_fwd_piter::invalidate) Adjust to the new interface of mln::p_line_graph. (line_graph_window_fwd_piter::update_): Don't update member p_. (operator<<(std::ostream&, const line_graph_window_fwd_piter&)): Print the associated psite, not the associated point. (mln::line_graph_window_bkd_piter) (operator<<(std::ostream&, const line_graph_window_bkd_piter&)): New. * mln/core/line_graph_neighborhood_piter.hh Add more documentation. (mln::line_graph_neighborhood_fwd_piter::point): Set typedef to P. (mln::line_graph_neighborhood_fwd_piter::to_point) (mln::line_graph_neighborhood_fwd_piter::operator[](unsigned)): Adjust return types. (mln::line_graph_neighborhood_fwd_piter::operator point): Remove. (line_graph_neighborhood_fwd_piter(const N&, const Point_Site<Pref>&): (mln::line_graph_neighborhood_fwd_piter::invalidate) Adjust to the new interface of mln::p_line_graph. (mln::line_graph_neighborhood_fwd_piter::update_): Don't update member p_. (operator<<(std::ostream&,const line_graph_neighborhood_fwd_piter&)): Print the associated psite, not the associated point. (mln::line_graph_neighborhood_bkd_piter) (operator<<(std::ostream&,const line_graph_neighborhood_bkd_piter&)): New. line_graph_neighborhood_piter.hh | 310 ++++++++++++++++++++++++++++++++++----- line_graph_window_piter.hh | 296 +++++++++++++++++++++++++++++++++---- 2 files changed, 543 insertions(+), 63 deletions(-) Index: mln/core/line_graph_window_piter.hh --- mln/core/line_graph_window_piter.hh (revision 1771) +++ mln/core/line_graph_window_piter.hh (working copy) @@ -37,9 +37,6 @@ - mln::graph_neighborhood_fwd_piter - mln::line_graph_window_fwd_piter - mln::line_graph_neighborhood_fwd_piter. - - and later (when they get implemented): - - mln::graph_window_bkd_piter - mln::graph_neighborhood_bkd_piter - mln::line_graph_window_bkd_piter @@ -48,9 +45,6 @@ # include <mln/core/concept/point_iterator.hh> # include <mln/core/p_line_graph.hh> # include <mln/core/line_graph_psite.hh> -# include <mln/core/point_pair.hh> - -/* FIXME: Doc. */ /* FIXME: Due to the poor interface of mln::p_line_graph and mln::util::graph, we show to much implementation details here. @@ -67,6 +61,7 @@ | line_graph_window_fwd_piter. | `---------------------------------*/ + /// \brief Forward iterator on line graph window. template <typename P> class line_graph_window_fwd_piter : public Point_Iterator< line_graph_window_fwd_piter > // or Iterator<...>? @@ -75,38 +70,53 @@ typedef Point_Iterator< self_ > super_; public: - typedef line_graph_psite psite; - + // Make definitions from super class available. enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; - typedef point_pair point; + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; // FIXME: Dummy typedef. typedef void dpoint; - typedef mln_coord(point) coord; + // FIXME: Dummy typedef. + typedef void mesh; public: + /// Construction. + /// \{ template <typename W, typename Pref> line_graph_window_fwd_piter(const W& win, const Point_Site<Pref>& p_ref); + /// \} + /// Manipulation. + /// \{ + /// Test if the iterator is valid. bool is_valid() const; + /// Invalidate the iterator. void invalidate(); + /// Start an iteration. void start(); + /// Go to the next point. void next_(); + /// Is the piter adjacent or equal to the reference point? bool adjacent_or_equal_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); + /// \} + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. const point& to_point() const; + /// Reference to the corresponding point site. const psite& to_psite() const; - - operator point() const; + /// Convert the iterator into a line graph psite. operator psite() const; - /// Return the \a i th coordinate of the (iterated) point. + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; + /// \} private: /// The ``central'' psite of the window. @@ -116,6 +126,8 @@ /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ point p_; }; @@ -133,11 +145,93 @@ | line_graph_window_bkd_piter. | `---------------------------------*/ - // FIXME: Implement line_graph_window_bkd_piter. + /// \brief Backward iterator on line graph window. + template <typename P> + class line_graph_window_bkd_piter : + public Point_Iterator< line_graph_window_bkd_piter > // or Iterator<...>? + { + typedef line_graph_window_bkd_piter self_; + typedef Point_Iterator< self_ > super_; + + public: + // Make definitions from super class available. + enum { dim = P::dim }; + + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; + // FIXME: Dummy typedef. + typedef void dpoint; + // FIXME: Dummy typedef. + typedef void mesh; + + public: + /// Construction. + /// \{ + template <typename W, typename Pref> + line_graph_window_bkd_piter(const W& win, const Point_Site<Pref>& p_ref); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + /// Is the piter adjacent or equal to the reference point? + bool adjacent_or_equal_to_p_ref_() const; + /// Update the internal data of the iterator. + void update_(); + /// \} + + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. + const point& to_point() const; + /// Reference to the corresponding point site. + const psite& to_psite() const; + /// Convert the iterator into a line graph psite. + operator psite() const; + + /// Read-only access to the \a i-th coordinate. + coord operator[](unsigned i) const; + /// \} + + private: + /// The ``central'' psite of the window. + const psite& p_ref_; + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ + point p_; + }; + + /* FIXME: This hand-made delegation is painful. We should rely on + the general mechanism provided by Point_Site. But then again, we + need to refine/adjust the interface of Point_Site w.r.t. the + mandatory conversions to points. */ + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter& p); + # ifndef MLN_INCLUDE_ONLY + /*---------------------------------. + | line_graph_window_fwd_piter. | + `---------------------------------*/ + // FIXME: Currently, argument win is ignored. template <typename P> template <typename W, typename Pref> @@ -146,8 +240,7 @@ const Point_Site<Pref>& p_ref) : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. - psite_(p_ref_.plg(), p_ref_.plg().nlines()), - p_() + psite_() { // Invalidate id_. invalidate(); @@ -169,7 +262,7 @@ void line_graph_window_fwd_piter::invalidate() { - id_ = p_ref_.plg().gr_.nedges(); + id_ = -1; } template <typename P> @@ -245,16 +338,11 @@ { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); - // Update p_. - // FIXME: These repeated assignments might be very costly. - /* FIXME: Likewise, it's hard to read. Simplify accesses to the graph. */ - p_ = point(p_ref_.plg().gr_.node_data(p_ref_.plg().gr_.edge(id_).n1()), - p_ref_.plg().gr_.node_data(p_ref_.plg().gr_.edge(id_).n2())); } template <typename P> inline - const point_pair& + const P& line_graph_window_fwd_piter::to_point() const { return p_; @@ -270,15 +358,161 @@ template <typename P> inline - line_graph_window_fwd_piter::operator point_pair() const + line_graph_window_fwd_piter::operator line_graph_psite () const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + line_graph_window_fwd_piter::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const line_graph_window_fwd_piter& p) + { + return ostr << p.to_psite(); + } + + + /*---------------------------------. + | line_graph_window_bkd_piter. | + `---------------------------------*/ + + // FIXME: Currently, argument win is ignored. + template <typename P> + template <typename W, typename Pref> + inline + line_graph_window_bkd_piter::line_graph_window_bkd_piter(const W& /* win */, + const Point_Site<Pref>& p_ref) + : p_ref_(exact(p_ref).to_psite()), + // Initialize psite_ to a dummy value. + psite_() + { + // Invalidate id_. + invalidate(); + } + + template <typename P> + inline + bool + line_graph_window_bkd_piter::is_valid() const + { + // FIXME: We depend too much on the implementation of util::graph + // here. The util::graph should provide the service to abstract + // these manipulations. + return id_ < p_ref_.plg().gr_.nedges(); + } + + template <typename P> + inline + void + line_graph_window_bkd_piter::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + line_graph_window_bkd_piter::start() + { + id_ = p_ref_.plg().gr_.nedges() - 1; + if (!adjacent_or_equal_to_p_ref_()) + next_(); + /* FIXME: This is redundant with the end of next_(), but we might + change the implementation of start_() when we'll fix it later, + and no longer use next_(). */ + if (is_valid()) + update_(); + } + + template <typename P> + inline + void + line_graph_window_bkd_piter::next_() + { + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent edges fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + /* FIXME: Moreover, the behavior of next shall depend on the + window, which is not the case now! (Currently, next_() behaves + as win was always an elementary window.) */ + do + --id_; + while (is_valid() && !adjacent_or_equal_to_p_ref_()); + if (is_valid()) + update_(); + } + + template <typename P> + inline + bool + line_graph_window_bkd_piter::adjacent_or_equal_to_p_ref_() const + { + // Check wether the iterator points to P_REF_. + if (id_ == p_ref_.id()) + return true; + + // Check whether the iterator is among the neighbors of P_REF_. + { + // Paranoid assertion. + assert (p_ref_.id() < p_ref_.plg().gr_.nedges()); + /* FIXME: We should have a convenient shortcut for these + repetitive accesses to p_ref_.plg().gr_ (e.g., a method gr() + or g() in this class. */ + const typename p_line_graph::graph& gr = p_ref_.plg().gr_; + // Check whether the edge this iterator points to is adjacent to + // the one p_ref points to, by comparing their ajacent nodes. + /* FIXME: This is too low-level. Yet another service the graph + // should provide. */ + if (gr.edge(id_).n1() == gr.edge(p_ref_.id()).n1() || + gr.edge(id_).n1() == gr.edge(p_ref_.id()).n2() || + gr.edge(id_).n2() == gr.edge(p_ref_.id()).n1() || + gr.edge(id_).n2() == gr.edge(p_ref_.id()).n2()) + return true; + } + + // Otherwise, the iterator is not adjacent to P_REF_. + return false; + } + + template <typename P> + inline + void + line_graph_window_bkd_piter::update_() + { + // Update psite_. + psite_ = line_graph_psite(p_ref_.plg(), id_); + } + + template <typename P> + inline + const P& + line_graph_window_bkd_piter::to_point() const + { return p_; } template <typename P> inline - line_graph_window_fwd_piter::operator line_graph_psite () const + const line_graph_psite& + line_graph_window_bkd_piter::to_psite() const + { + return psite_; + } + + template <typename P> + inline + line_graph_window_bkd_piter::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; @@ -286,8 +520,8 @@ template <typename P> inline - mln_coord(point_pair) - line_graph_window_fwd_piter::operator[](unsigned i) const + mln_coord(P) + line_graph_window_bkd_piter::operator[](unsigned i) const { assert(i < dim); return p_[i]; @@ -296,9 +530,9 @@ template <typename P> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_fwd_piter& p) + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter& p) { - return ostr << p.to_point(); + return ostr << p.to_psite(); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1771) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -29,7 +29,7 @@ # define MLN_CORE_LINE_GRAPH_NEIGHBORHOOD_PITER_HH /// \file mln/core/line_graph_neighborhood_piter.hh -/// \brief Definition of a point iterator on a line_graph neighborhood. +/// \brief Definition of a point iterator on a line graph neighborhood. /* FIXME: Factor those classes: @@ -37,9 +37,6 @@ - mln::graph_neighborhood_fwd_piter - mln::line_graph_window_fwd_piter - mln::line_graph_neighborhood_fwd_piter. - - and later (when they get implemented): - - mln::graph_window_bkd_piter - mln::graph_neighborhood_bkd_piter - mln::line_graph_window_bkd_piter @@ -48,9 +45,6 @@ # include <mln/core/concept/point_iterator.hh> # include <mln/core/p_line_graph.hh> # include <mln/core/line_graph_psite.hh> -# include <mln/core/point_pair.hh> - -/* FIXME: Doc. */ /* FIXME: Due to the poor interface of mln::p_line_graph and mln::util::graph, we show to much implementation details here. @@ -67,6 +61,7 @@ | line_graph_neighborhood_fwd_piter. | `---------------------------------------*/ + /// \brief Backward iterator on line graph neighborhood. template <typename P> class line_graph_neighborhood_fwd_piter : public Point_Iterator< line_graph_neighborhood_fwd_piter > // or Iterator<...>? @@ -75,39 +70,55 @@ typedef Point_Iterator< self_ > super_; public: - typedef line_graph_psite psite; - + // Make definitions from super class available. enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; - typedef point_pair point; + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; // FIXME: Dummy typedef. typedef void dpoint; - typedef mln_coord(point) coord; + // FIXME: Dummy typedef. + typedef void mesh; public: + /// Construction. + /// \{ template <typename N, typename Pref> line_graph_neighborhood_fwd_piter(const N& nbh, const Point_Site<Pref>& p_ref); + /// \} + /// Manipulation. + /// \{ + /// Test if the iterator is valid. bool is_valid() const; + /// Invalidate the iterator. void invalidate(); + /// Start an iteration. void start(); + /// Go to the next point. void next_(); + /// Is the piter adjacent or equal to the reference point? bool adjacent_or_equal_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); + /// \} + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. const point& to_point() const; + /// Reference to the corresponding point site. const psite& to_psite() const; - - operator point() const; + /// Convert the iterator into a line graph psite. operator psite() const; - /// Return the \a i th coordinate of the (iterated) point. + /// Read-only access to the \a i-th coordinate. + // FIXME: Dummy. coord operator[](unsigned i) const; + /// \} private: /// The ``central'' psite of the neighborhood. @@ -117,6 +128,8 @@ /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ point p_; }; @@ -135,21 +148,108 @@ | line_graph_neighborhood_bkd_piter. | `---------------------------------------*/ - // FIXME: Implement line_graph_neighborhood_bkd_piter. + /// \brief Backward iterator on line graph neighborhood. + template <typename P> + class line_graph_neighborhood_bkd_piter : + public Point_Iterator< line_graph_neighborhood_bkd_piter > // or Iterator<...>? + { + typedef line_graph_neighborhood_bkd_piter self_; + typedef Point_Iterator< self_ > super_; + + public: + // Make definitions from super class available. + enum { dim = P::dim }; + + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; + // FIXME: Dummy typedef. + typedef void dpoint; + // FIXME: Dummy typedef. + typedef void mesh; + + public: + /// Construction. + /// \{ + template <typename N, typename Pref> + line_graph_neighborhood_bkd_piter(const N& nbh, + const Point_Site<Pref>& p_ref); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + /// Is the piter adjacent or equal to the reference point? + bool adjacent_or_equal_to_p_ref_() const; + /// Update the internal data of the iterator. + void update_(); + /// \} + + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. + const point& to_point() const; + /// Reference to the corresponding point site. + const psite& to_psite() const; + /// Convert the iterator into a line graph psite. + operator psite() const; + + /// Read-only access to the \a i-th coordinate. + // FIXME: Dummy. + coord operator[](unsigned i) const; + /// \} + + private: + /// The ``central'' psite of the neighborhood. + const psite& p_ref_; + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ + point p_; + }; + + /* FIXME: This hand-made delegation is painful. We should rely on + the general mechanism provided by Point_Site. But then again, we + need to refine/adjust the interface of Point_Site w.r.t. the + mandatory conversions to points. */ + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, + const line_graph_neighborhood_bkd_piter& p); + # ifndef MLN_INCLUDE_ONLY + /*---------------------------------------. + | line_graph_neighborhood_fwd_piter. | + `---------------------------------------*/ + // FIXME: Currently, argument nbh is ignored. template <typename P> template <typename N, typename Pref> inline line_graph_neighborhood_fwd_piter::line_graph_neighborhood_fwd_piter(const N& /* nbh */, const Point_Site<Pref>& p_ref) + /* FIXME: We should use a routine actually checking the + conversion, since to_psite() checks nothing (as of + 2008-03-05). */ : p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. - psite_(p_ref_.plg(), p_ref_.plg().nlines()), - p_() + psite_() { // Invalidate id_. invalidate(); @@ -171,7 +271,7 @@ void line_graph_neighborhood_fwd_piter::invalidate() { - id_ = p_ref_.plg().gr_.nedges(); + id_ = -1; } template <typename P> @@ -247,16 +347,11 @@ { // Update psite_. psite_ = line_graph_psite(p_ref_.plg(), id_); - // Update p_. - // FIXME: These repeated assignments might be very costly. - /* FIXME: Likewise, it's hard to read. Simplify accesses to the graph. */ - p_ = point(p_ref_.plg().gr_.node_data(p_ref_.plg().gr_.edge(id_).n1()), - p_ref_.plg().gr_.node_data(p_ref_.plg().gr_.edge(id_).n2())); } template <typename P> inline - const point_pair& + const P& line_graph_neighborhood_fwd_piter::to_point() const { return p_; @@ -272,15 +367,165 @@ template <typename P> inline - line_graph_neighborhood_fwd_piter::operator point_pair() const + line_graph_neighborhood_fwd_piter::operator line_graph_psite () const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + line_graph_neighborhood_fwd_piter::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, + const line_graph_neighborhood_fwd_piter& p) + { + return ostr << p.to_psite(); + } + + + /*---------------------------------------. + | line_graph_neighborhood_bkd_piter. | + `---------------------------------------*/ + + // FIXME: Currently, argument nbh is ignored. + template <typename P> + template <typename N, typename Pref> + inline + line_graph_neighborhood_bkd_piter::line_graph_neighborhood_bkd_piter(const N& /* nbh */, + const Point_Site<Pref>& p_ref) + /* FIXME: We should use a routine actually checking the + conversion, since to_psite() checks nothing (as of + 2008-03-05). */ + : p_ref_(exact(p_ref).to_psite()), + // Initialize psite_ to a dummy value. + psite_() + { + // Invalidate id_. + invalidate(); + } + + template <typename P> + inline + bool + line_graph_neighborhood_bkd_piter::is_valid() const + { + // FIXME: We depend too much on the implementation of util::graph + // here. The util::graph should provide the service to abstract + // these manipulations. + return id_ < p_ref_.plg().gr_.nedges(); + } + + template <typename P> + inline + void + line_graph_neighborhood_bkd_piter::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + line_graph_neighborhood_bkd_piter::start() + { + id_ = p_ref_.plg().gr_.nedges() - 1; + if (!adjacent_or_equal_to_p_ref_()) + next_(); + /* FIXME: This is redundant with the end of next_(), but we might + change the implementation of start_() when we'll fix it later, + and no longer use next_(). */ + if (is_valid()) + update_(); + } + + template <typename P> + inline + void + line_graph_neighborhood_bkd_piter::next_() + { + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent edges fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + /* FIXME: Moreover, the behavior of next shall depend on the + neighborhood, which is not the case now! (Currently, next_() + behaves as nbh was always an elementary neighborhood.) */ + do + --id_; + while (is_valid() && !adjacent_or_equal_to_p_ref_()); + if (is_valid()) + update_(); + } + + template <typename P> + inline + bool + line_graph_neighborhood_bkd_piter::adjacent_or_equal_to_p_ref_() const + { + // Check wether the iterator points to P_REF_. + if (id_ == p_ref_.id()) + return true; + + // Check whether the iterator is among the neighbors of P_REF_. + { + // Paranoid assertion. + assert (p_ref_.id() < p_ref_.plg().gr_.nedges()); + /* FIXME: We should have a convenient shortcut for these + repetitive accesses to p_ref_.plg().gr_ (e.g., a method gr() + or g() in this class. */ + const typename p_line_graph::graph& gr = p_ref_.plg().gr_; + // Check whether the edge this iterator points to is adjacent to + // the one p_ref points to, by comparing their ajacent nodes. + /* FIXME: This is too low-level. Yet another service the graph + // should provide. */ + if (gr.edge(id_).n1() == gr.edge(p_ref_.id()).n1() || + gr.edge(id_).n1() == gr.edge(p_ref_.id()).n2() || + gr.edge(id_).n2() == gr.edge(p_ref_.id()).n1() || + gr.edge(id_).n2() == gr.edge(p_ref_.id()).n2()) + return true; + } + + // Otherwise, the iterator is not adjacent to P_REF_. + return false; + } + + template <typename P> + inline + void + line_graph_neighborhood_bkd_piter::update_() + { + // Update psite_. + psite_ = line_graph_psite(p_ref_.plg(), id_); + } + + template <typename P> + inline + const P& + line_graph_neighborhood_bkd_piter::to_point() const + { return p_; } template <typename P> inline - line_graph_neighborhood_fwd_piter::operator line_graph_psite () const + const line_graph_psite& + line_graph_neighborhood_bkd_piter::to_psite() const + { + return psite_; + } + + template <typename P> + inline + line_graph_neighborhood_bkd_piter::operator line_graph_psite () const { mln_precondition(is_valid()); return psite_; @@ -288,8 +533,8 @@ template <typename P> inline - mln_coord(point_pair) - line_graph_neighborhood_fwd_piter::operator[](unsigned i) const + mln_coord(P) + line_graph_neighborhood_bkd_piter::operator[](unsigned i) const { assert(i < dim); return p_[i]; @@ -299,13 +544,14 @@ inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_fwd_piter& p) + const line_graph_neighborhood_bkd_piter& p) { - return ostr << p.to_point(); + return ostr << p.to_psite(); } # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln + #endif // ! MLN_CORE_LINE_GRAPH_NEIGHBORHOOD_PITER_HH

1 0

1771: Add a backward iterator on p_line_graph.
by Roland Levillain 12 Mar '08

12 Mar '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Add a backward iterator on p_line_graph. * mln/core/p_line_graph_piter.hh (p_line_graph_piter_): Rename as... (p_line_graph_fwd_piter_): ...this. (p_line_graph_fwd_piter_::self_): Adjust. (p_line_graph_fwd_piter_::point): Set typedef to P. (p_line_graph_fwd_piter_::coord): Set typedef to mln_coord(point). (p_line_graph_fwd_piter_(const p_line_graph_fwd_piter_&)) (operator= (const p_line_graph_fwd_piter_&)): New. (p_line_graph_fwd_piter_::operator point): Remove. (p_line_graph_fwd_piter_::operator psite): New. (p_line_graph_fwd_piter_::plg_): Change the type of this member from const p_line_graph& to const p_line_graph*. (p_line_graph_fwd_piter_(const p_line_graph&)) (p_line_graph_fwd_piter_::is_valid) (p_line_graph_fwd_piter_::invalidate): Adjust. (p_line_graph_fwd_piter_::update_): Don't update member p_. (p_line_graph_bkd_piter_): New. (operator<<(std::ostream&, const p_line_graph_fwd_piter_&)) (operator<<(std::ostream&, const p_line_graph_bkd_piter_&)) * mln/core/p_line_graph.hh (mln::box_< point_pair >): Remove this specialization. (mln::p_line_graph::point): Remove typedef. (mln::p_line_graph::fwd_piter): Adjust to the new name of mln::p_line_graph_fwd_piter_. (mln::p_line_graph::bkd_piter): New typedef. (mln::p_line_graph::nlines): Rename as... (mln::p_line_graph::nedges): ..this. (mln::p_line_graph::npoints): Rename as... (mln::p_line_graph::nnodes): ...this. (mln::p_line_graph::npoints): New. s/box_<point>/box_/. (mln::p_line_graph::p_line_graph (util::graph&)): Fix the initialization of bb_. (operator==(const p_line_graph&, const p_line_graph&)): New. p_line_graph.hh | 87 ++++++------ p_line_graph_piter.hh | 351 +++++++++++++++++++++++++++++++++++++++++--------- 2 files changed, 340 insertions(+), 98 deletions(-) Index: mln/core/p_line_graph_piter.hh --- mln/core/p_line_graph_piter.hh (revision 1770) +++ mln/core/p_line_graph_piter.hh (working copy) @@ -31,12 +31,9 @@ # include <mln/core/internal/point_iterator_base.hh> # include <mln/core/p_line_graph.hh> # include <mln/core/line_graph_psite.hh> -# include <mln/core/point_pair.hh> -/*! \file mln/core/p_line_graph_piter.hh - * - * \brief Definition of point iterator on graph-based point set. - */ +/// \file mln/core/p_line_graph_piter.hh +/// \brief Definition of point iterator on line graph-based point set. namespace mln { @@ -45,67 +42,156 @@ template<typename P> class line_graph_psite; - // FIXME: Why `p_line_graph_piter_' and not `p_line_graph_piter' - // (without `_')? + /*-----------------------------. + | p_line_graph_fwd_piter_. | + `-----------------------------*/ + /// \brief Forward iterator on point sites of a mln::p_line_graph. template<typename P> - class p_line_graph_piter_ - : public internal::point_iterator_base_< P, p_line_graph_piter_ > + class p_line_graph_fwd_piter_ + : public internal::point_iterator_base_< P, p_line_graph_fwd_piter_ > { - typedef p_line_graph_piter_ self_; + typedef p_line_graph_fwd_piter_ self_; typedef internal::point_iterator_base_< P, self_ > super_; public: - // Make definitions from super class available. enum { dim = super_::dim }; - typedef line_graph_psite psite; - typedef point_pair point; - typedef mln_coord(point_pair) coord; - p_line_graph_piter_(const p_line_graph& plg); + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; - /// Read-only access to the \p i-th coordinate. - mln_coord(point) operator[](unsigned i) const; + /// Construction and assignment. + /// \{ + p_line_graph_fwd_piter_(const p_line_graph& plg); + p_line_graph_fwd_piter_(const self_& rhs); + self_& operator= (const self_& rhs); + /// \} + /// Manipulation. + /// \{ /// Test if the iterator is valid. bool is_valid() const; - /// Invalidate the iterator. void invalidate(); - /// Start an iteration. void start(); /// Go to the next point. void next_(); - /// Update the internal data of the iterator. void update_(); + /// \} + /// Conversion and accessors. + /// \{ /// Reference to the corresponding point. + // FIXME: Dummy. const point& to_point () const; - /// Reference to the corresponding point site. const psite& to_psite () const; + /// Convert the iterator into a line graph psite. + operator psite() const; + + /// Read-only access to the \a i-th coordinate. + coord operator[](unsigned i) const; + /// \} + + private: + /// The p_line_graph this point site belongs to. + const p_line_graph* plg_; + /// The id of the edge this psite is pointing towards. + util::edge_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ + point p_; + }; + + + /* FIXME: This hand-made delegation is painful. We should rely on + the general mechanism provided by Point_Site. But then again, we + need to refine/adjust the interface of Point_Site w.r.t. the + mandatory conversions to points. */ + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const p_line_graph_fwd_piter_& p); - /// Convert the iterator into a point. - operator point() const; - /// Convert the iterator into a graph psite. + /*-----------------------------. + | p_line_graph_bkd_piter_. | + `-----------------------------*/ + + /// \brief Backward iterator on point sites of a mln::p_line_graph. + template<typename P> + class p_line_graph_bkd_piter_ + : public internal::point_iterator_base_< P, p_line_graph_bkd_piter_ > + { + typedef p_line_graph_bkd_piter_ self_; + typedef internal::point_iterator_base_< P, self_ > super_; + + public: + // Make definitions from super class available. + enum { dim = super_::dim }; + + typedef line_graph_psite psite; + typedef P point; + typedef mln_coord(point) coord; + + /// Construction and assignment. + /// \{ + p_line_graph_bkd_piter_(const p_line_graph& plg); + p_line_graph_bkd_piter_(const self_& rhs); + self_& operator= (const self_& rhs); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + /// Update the internal data of the iterator. + void update_(); + /// \} + + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding point. + // FIXME: Dummy. + const point& to_point () const; + /// Reference to the corresponding point site. + const psite& to_psite () const; + /// Convert the iterator into a line graph psite. operator psite() const; + /// Read-only access to the \a i-th coordinate. + mln_coord(point) operator[](unsigned i) const; + /// \} + protected: /// The p_line_graph this point site belongs to. - const p_line_graph& plg_; + const p_line_graph* plg_; /// The id of the edge this psite is pointing towards. util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; - /// The psite corresponding to this iterator. + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ point p_; }; + /* FIXME: This hand-made delegation is painful. We should rely on the general mechanism provided by Point_Site. But then again, we need to refine/adjust the interface of Point_Site w.r.t. the @@ -113,18 +199,21 @@ template <typename P> inline std::ostream& - operator<<(std::ostream& ostr, const p_line_graph_piter_& p); + operator<<(std::ostream& ostr, const p_line_graph_bkd_piter_& p); # ifndef MLN_INCLUDE_ONLY + /*-----------------------------. + | p_line_graph_fwd_piter_. | + `-----------------------------*/ + template<typename P> inline - p_line_graph_piter_::p_line_graph_piter_(const p_line_graph& plg) - : plg_(plg), + p_line_graph_fwd_piter_::p_line_graph_fwd_piter_(const p_line_graph& plg) + : plg_(&plg), // Initialize psite_ to a dummy value. - psite_(plg, plg_.nlines()), - p_() + psite_(plg, -1) { // Invalidate id_. invalidate(); @@ -132,32 +221,55 @@ template<typename P> inline - mln_coord(point_pair) - p_line_graph_piter_::operator[](unsigned i) const + p_line_graph_fwd_piter_::p_line_graph_fwd_piter_(const p_line_graph_fwd_piter_& rhs) + : plg_(rhs.plg_), + id_(rhs.id_), + psite_(rhs.psite_) { + } + + template<typename P> + inline + p_line_graph_fwd_piter_& + p_line_graph_fwd_piter_::operator=(const p_line_graph_fwd_piter_& rhs) + { + if (&rhs == this) + return *this; + plg_ = rhs.plg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + return *this; + } + + template<typename P> + inline + mln_coord(P) + p_line_graph_fwd_piter_::operator[](unsigned i) const + { + // Dummy value. return p_[i]; } template<typename P> inline bool - p_line_graph_piter_::is_valid() const + p_line_graph_fwd_piter_::is_valid() const { - return id_ < plg_.nlines(); + return plg_ && id_ < plg_->nedges(); } template<typename P> inline void - p_line_graph_piter_::invalidate() + p_line_graph_fwd_piter_::invalidate() { - id_ = plg_.nlines(); + id_ = -1; } template<typename P> inline void - p_line_graph_piter_::start() + p_line_graph_fwd_piter_::start() { id_ = 0; if (is_valid()) @@ -167,7 +279,7 @@ template<typename P> inline void - p_line_graph_piter_::next_() + p_line_graph_fwd_piter_::next_() { ++id_; if (is_valid()) @@ -177,20 +289,25 @@ template<typename P> inline void - p_line_graph_piter_::update_() + p_line_graph_fwd_piter_::update_() { // Update psite_. - psite_ = line_graph_psite(plg_, id_); - // Update p_. - // FIXME: These repeated assignments might be very costly. - p_ = point(plg_.gr_.node_data(plg_.gr_.edge(id_).n1()), - plg_.gr_.node_data(plg_.gr_.edge(id_).n2())); + psite_ = line_graph_psite(*plg_, id_); + } + + template<typename P> + inline + const P& + p_line_graph_fwd_piter_::to_point() const + { + // Dummy value. + return p_; } template<typename P> inline - const point_pair& - p_line_graph_piter_::to_point() const + const line_graph_psite& + p_line_graph_fwd_piter_::to_psite() const { /* We don't check whether the iterator is valid before returning the value using @@ -203,13 +320,135 @@ on window or neighborhood (say, Q); most of the time, for_all() is responsible for the initialization of P, but it takes place *after* the creation of Q. */ + return psite_; + } + + template<typename P> + inline + p_line_graph_fwd_piter_::operator line_graph_psite() const + { + mln_precondition(is_valid()); + return psite_; + } + + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const p_line_graph_fwd_piter_& p) + { + // FIXME: We should use p.to_psite() here, but as it lacks the + // precondition the conversion operator has, we use the latter. + return ostr << static_cast< line_graph_psite >(p); + } + + + /*-----------------------------. + | p_line_graph_bkd_piter_. | + `-----------------------------*/ + + template<typename P> + inline + p_line_graph_bkd_piter_::p_line_graph_bkd_piter_(const p_line_graph& plg) + : plg_(&plg), + // Initialize psite_ to a dummy value. + psite_(plg, -1) + { + // Invalidate id_. + invalidate(); + } + + template<typename P> + inline + p_line_graph_bkd_piter_::p_line_graph_bkd_piter_(const p_line_graph_bkd_piter_& rhs) + : plg_(rhs.plg_), + id_(rhs.id_), + psite_(rhs.psite_) + { + } + + template<typename P> + inline + p_line_graph_bkd_piter_& + p_line_graph_bkd_piter_::operator=(const p_line_graph_bkd_piter_& rhs) + { + if (&rhs == this) + return *this; + plg_ = rhs.plg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + // FIXME: Probably superfluous. +// update_(); + return *this; + } + + template<typename P> + inline + mln_coord(P) + p_line_graph_bkd_piter_::operator[](unsigned i) const + { + // Dummy value. + return p_[i]; + } + + template<typename P> + inline + bool + p_line_graph_bkd_piter_::is_valid() const + { + return plg_ && id_ < plg_->nedges(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_::invalidate() + { + id_ = -1; + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_::start() + { + id_ = plg_->nedges() - 1; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_::next_() + { + --id_; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_::update_() + { + // Update psite_. + psite_ = line_graph_psite(*plg_, id_); + } + + template<typename P> + inline + const P& + p_line_graph_bkd_piter_::to_point() const + { + // Dummy value. return p_; } template<typename P> inline const line_graph_psite& - p_line_graph_piter_::to_psite() const + p_line_graph_bkd_piter_::to_psite() const { /* We don't check whether the iterator is valid before returning the value using @@ -227,15 +466,7 @@ template<typename P> inline - p_line_graph_piter_::operator point_pair() const - { - mln_precondition(is_valid()); - return p_; - } - - template<typename P> - inline - p_line_graph_piter_::operator line_graph_psite() const + p_line_graph_bkd_piter_::operator line_graph_psite() const { mln_precondition(is_valid()); return psite_; @@ -245,9 +476,9 @@ template <typename P> inline std::ostream& - operator<<(std::ostream& ostr, const p_line_graph_piter_& p) + operator<<(std::ostream& ostr, const p_line_graph_bkd_piter_& p) { - return ostr << p.to_point(); + return ostr << static_cast< line_graph_psite >(p); } # endif // ! MLN_INCLUDE_ONLY @@ -255,4 +486,4 @@ } // end of mln -#endif // MLN_P_LINE_GRAPH_PITER_HH +#endif // ! MLN_CORE_P_LINE_GRAPH_PITER_HH Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1770) +++ mln/core/p_line_graph.hh (working copy) @@ -34,7 +34,6 @@ # include <mln/util/graph.hh> # include <mln/core/line_graph_psite.hh> # include <mln/core/p_line_graph_piter.hh> -# include <mln/core/point_pair.hh> /* FIXME: This class shares a lot with p_graph. Factor as much as possible. */ @@ -45,17 +44,9 @@ namespace mln { - - // FIXME: Dummy specialization, only to have this first version of - // our code compile. - template <typename P> - struct box_< point_pair > : public Box< box_ > - { - // Nothing. - }; - - - template<typename P> class p_line_graph_piter_; + /* FIXME: Contray to, e.g., p_array, the sole parameter P of + p_line_graph is expected to be a point, not a psite!! We should + have a uniform scheme for point site sets. */ template<typename P> struct p_line_graph @@ -69,24 +60,24 @@ /// Point_Site associated type. typedef line_graph_psite psite; - /// Point associated type. - typedef point_pair point; - /// Forward Point_Iterator associated type. - typedef p_line_graph_piter_ fwd_piter; + typedef p_line_graph_fwd_piter_ fwd_piter; /// Backward Point_Iterator associated type. - typedef p_line_graph_piter_ bkd_piter; + typedef p_line_graph_bkd_piter_ bkd_piter; - /// Return The number of points (i.e., nodes) in the graph. + /// Return The number of points (sites) of the set, i.e., the + /// number of \em edges, since this is a point set based on a line + /// graph. std::size_t npoints() const; - /// Return The number of lines (i.e., edges) in the graph. - std::size_t nlines() const; + /// Return The number of nodes (vertices) in the graph. + std::size_t nnodes() const; + /// Return The number of edges in the graph. + std::size_t nedges() const; /// Give the exact bounding box. - // FIXME: Dummy. - const box_<point>& bbox() const; + const box_& bbox() const; bool has(const psite& p) const; @@ -95,12 +86,20 @@ // FIXME: (Roland) Is it really useful/needed? /* 2007-12-19: It seems so, since graph_image must implement a method named bbox(). Now the question is: should each image - type have a bounding box? In particular, an image whose sites - are actually /pairs of points/! */ - // FIXME: Dummy. - box_<point> bb_; + type have a bounding box? */ + box_ bb_; }; + + /// \brief Comparison between two mln::p_line_graph's. + /// + /// Two mln::p_line_graph's are considered equal if they have the + /// same address. + template <typename P> + bool + operator==(const p_line_graph& lhs, const p_line_graph& rhs); + + # ifndef MLN_INCLUDE_ONLY template<typename P> @@ -108,37 +107,41 @@ p_line_graph::p_line_graph (util::graph& gr) : gr_ (gr) { - // FIXME: Dummy initialization of bb_. -// // FIXME: Warning: if the underlying graph is updated later, this -// // won't be taken into account by this p_line_graph! -// accu::bbox<point> a; -// for (util::edge_id e = 0; e < nlines(); ++e) -// a.take(point(gr_.node_data(gr_.edge(e).n1()), -// gr_.node_data(gr_.edge(e).n2()))); -// bb_ = a.to_result(); + // FIXME: Warning: if the underlying graph is updated later, this + // won't be taken into account by this p_line_graph! + accu::bbox a; + for (unsigned i = 0; i < nnodes(); ++i) + a.take(gr_.node_data(i)); + bb_ = a.to_result(); } - // FIXME: Rename to npsites? In fact, this depends on the - // interface expected from models of Point_Sets. template<typename P> inline std::size_t p_line_graph::npoints() const { + return nedges(); + } + + template<typename P> + inline + std::size_t + p_line_graph::nnodes() const + { return this->gr_.nnodes(); } template<typename P> inline std::size_t - p_line_graph::nlines() const + p_line_graph::nedges() const { return this->gr_.nedges(); } template<typename P> inline - const box_< point_pair >& + const box_& p_line_graph::bbox() const { return bb_; @@ -156,6 +159,14 @@ (p.id() < gr_.nedges()); } + + template <typename P> + bool + operator==(const p_line_graph& lhs, const p_line_graph& rhs) + { + return &lhs == &rhs; + } + # endif // ! MLN_INCLUDE_ONLY } // end of mln

1 0