[Olena-patches] 1715: Revamp iterators on windows on graphs.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Revamp iterators on windows on graphs. * mln/core/graph_window_piter.hh: Add missing inline `keywords' on methods. (graph_window_fwd_piter<P>::psite_) (graph_window_fwd_piter<P>::p_): New attributes. (graph_window_fwd_piter<P>::graph_window_fwd_piter): Adjust ctor. (graph_window_fwd_piter<P>::update_): New method. Use it... (graph_window_fwd_piter<P>::start) (graph_window_fwd_piter<P>::next_) ...here (graph_window_fwd_piter<P>::to_psite) (graph_window_fwd_piter<P>::operator point): New methods. (graph_window_fwd_piter<P>::to_psite) (graph_window_fwd_piter<P>::operator psite) (graph_window_fwd_piter<P>::operator[]): Adjust. * mln/core/p_graph.hh (p_graph<P>::has): Rewrite this method using a much simpler and faster approach. * mln/core/p_graph_piter.hh (p_graph_piter_<P>::i_): Rename as... (p_graph_piter_<P>::id_): ...this. (p_graph_piter_<P>::p_graph_piter_): Adjust ctor. (p_graph_piter_<P>::is_valid) (p_graph_piter_<P>::invalidate) (p_graph_piter_<P>::start) (p_graph_piter_<P>::next_) (p_graph_piter_<P>::update_): Adjust. * mln/core/graph_psite.hh: More doc. * mln/core/graph_elt_window.hh: Fix header guards. * mln/core/graph_image.hh: Aesthetic changes. * mln/util/internal/graph_base.hh: More FIXME. core/graph_elt_window.hh | 6 +-- core/graph_image.hh | 6 +-- core/graph_psite.hh | 4 +- core/graph_window_piter.hh | 74 ++++++++++++++++++++++++++++++++++++++------ core/p_graph.hh | 13 ++----- core/p_graph_piter.hh | 28 +++++++++------- util/internal/graph_base.hh | 6 +++ 7 files changed, 100 insertions(+), 37 deletions(-) Index: mln/core/graph_elt_window.hh --- mln/core/graph_elt_window.hh (revision 1714) +++ mln/core/graph_elt_window.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_WIN_GRAPH_ELT_WINDOW_HH -# define MLN_WIN_GRAPH_ELT_WINDOW_HH +#ifndef MLN_CORE_GRAPH_ELT_WINDOW_HH +# define MLN_CORE_GRAPH_ELT_WINDOW_HH /*! \file mln/core/graph_elt_window.hh * @@ -168,4 +168,4 @@ } // end of namespace mln -#endif // ! MLN_WIN_GRAPH_ELT_WINDOW_HH +#endif // ! MLN_CORE_GRAPH_ELT_WINDOW_HH Index: mln/core/graph_image.hh --- mln/core/graph_image.hh (revision 1714) +++ mln/core/graph_image.hh (working copy) @@ -28,10 +28,8 @@ #ifndef MLN_CORE_GRAPH_IMAGE_HH # define MLN_CORE_GRAPH_IMAGE_HH -/*! \file mln/core/graph_image.hh - * - * \brief Definition of a graph-based image. - */ +/// \file mln/core/graph_image.hh +/// \brief Definition of a graph-based image. # include <mln/trait/images.hh> Index: mln/core/graph_psite.hh --- mln/core/graph_psite.hh (revision 1714) +++ mln/core/graph_psite.hh (working copy) @@ -68,13 +68,15 @@ coord operator[](unsigned id) const; /// \} - /// Return the mln::p_graph this point site belongs to. + /// Return the p_graph this point site belongs to. const p_graph<P>& pg() const; /// Return the node id of this point site. util::node_id id() const; private: + // The p_graph this point site belongs to. const p_graph<P>& pg_; + // The id of the node this psite is pointing towards. util::node_id id_; }; Index: mln/core/graph_window_piter.hh --- mln/core/graph_window_piter.hh (revision 1714) +++ mln/core/graph_window_piter.hh (working copy) @@ -77,20 +77,29 @@ void next_(); bool adjacent_or_equal_to_p_ref_() const; + /// Update the internal data of the iterator. + void update_(); - // FIXME: In fact, this method should be named `to_psite', since - // it returns a mln::graph_psite<P> object, not a P object. const point& to_point() const; + + const psite& to_psite() const; + + operator point() const; + operator psite () const; + /// Return the \a i th coordinate of the (iterated) point. coord operator[](unsigned i) const; private: - /// The ``central'' point of the window. + /// 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_; }; // FIXME: Implement graph_window_bkd_piter. @@ -101,15 +110,20 @@ // FIXME: Currently, argument win is ignored. template <typename P> template <typename W, typename Pref> + inline graph_window_fwd_piter<P>::graph_window_fwd_piter(const W& /* win */, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()) + : p_ref_(exact(p_ref).to_psite()), + // Initialize psite_ to a dummy value. + psite_(p_ref_.pg(), p_ref_.pg().npoints()), + p_() { // Invalidate id_. invalidate(); } template <typename P> + inline bool graph_window_fwd_piter<P>::is_valid() const { @@ -120,6 +134,7 @@ } template <typename P> + inline void graph_window_fwd_piter<P>::invalidate() { @@ -127,15 +142,22 @@ } template <typename P> + inline void graph_window_fwd_piter<P>::start() { id_ = 0; 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_fwd_piter<P>::next_() { @@ -144,13 +166,17 @@ 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! */ + 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_fwd_piter<P>::adjacent_or_equal_to_p_ref_() const { @@ -180,16 +206,46 @@ } template <typename P> + inline + void + graph_window_fwd_piter<P>::update_() + { + // Update psite_. + psite_ = graph_psite<P>(p_ref_.pg(), id_); + // Update p_. + p_ = p_ref_.pg().gr_.node_data(id_); + } + + template <typename P> + inline const P& graph_window_fwd_piter<P>::to_point() const { - return p_ref_.pg().gr_.node_data(id_); + return p_; + } + + template <typename P> + inline + const graph_psite<P>& + graph_window_fwd_piter<P>::to_psite() const + { + return psite_; } template <typename P> + inline + graph_window_fwd_piter<P>::operator P() const + { + mln_precondition(is_valid()); + return p_; + } + + template <typename P> + inline graph_window_fwd_piter<P>::operator graph_psite<P> () const { - return graph_psite<P>(p_ref_.pg(), id_); + mln_precondition(is_valid()); + return psite_; } template <typename P> @@ -198,7 +254,7 @@ graph_window_fwd_piter<P>::operator[](unsigned i) const { assert(i < dim); - return to_point()[i]; + return p_[i]; } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1714) +++ mln/core/p_graph.hh (working copy) @@ -127,14 +127,11 @@ bool p_graph<P>::has(const psite& p) const { - // FIXME: util::graph (or util::internal::graph_base) should - // provide the iteration facility (iterators, find, etc.) - const typename graph::nodes_t& nodes = gr_.nodes(); - for (typename graph::nodes_t::const_iterator n = nodes.begin(); - n != nodes.end(); ++n) - if ((*n)->data == p) - return true; - return false; + return + // Check whether P is compatible with this psite set. + (&p.pg() == this) && + // Check that the node id of P belongs to the range of valid node ids. + (p.id() < gr_.nnodes()); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/p_graph_piter.hh --- mln/core/p_graph_piter.hh (revision 1714) +++ mln/core/p_graph_piter.hh (working copy) @@ -93,10 +93,14 @@ operator psite() const; protected: + // The p_graph this point site belongs to. const p_graph<P>& pg_; - unsigned i_; - P p_; + // The id of the node this psite is pointing towards. + unsigned id_; + // The psite corresponding to this iterator. psite psite_; + // The point corresponding to this iterator. + point p_; }; @@ -107,11 +111,11 @@ inline p_graph_piter_<P>::p_graph_piter_(const p_graph<P>& pg) : pg_(pg), - p_(), // Initialize psite_ to a dummy value. - psite_(pg, pg_.npoints()) + psite_(pg, pg_.npoints()), + p_() { - // Invalidate i_. + // Invalidate id_. invalidate(); } @@ -128,7 +132,7 @@ bool p_graph_piter_<P>::is_valid() const { - return i_ < pg_.npoints(); + return id_ < pg_.npoints(); } template<typename P> @@ -136,7 +140,7 @@ void p_graph_piter_<P>::invalidate() { - i_ = pg_.npoints(); + id_ = pg_.npoints(); } template<typename P> @@ -144,7 +148,7 @@ void p_graph_piter_<P>::start() { - i_ = 0; + id_ = 0; if (is_valid()) update_(); } @@ -154,7 +158,7 @@ void p_graph_piter_<P>::next_() { - ++i_; + ++id_; if (is_valid()) update_(); } @@ -164,10 +168,10 @@ void p_graph_piter_<P>::update_() { - // Update p_. - p_ = pg_.gr_.node_data(i_); // Update psite_. - psite_ = graph_psite<P>(pg_, i_); + psite_ = graph_psite<P>(pg_, id_); + // Update p_. + p_ = pg_.gr_.node_data(id_); } template<typename P> Index: mln/util/internal/graph_base.hh --- mln/util/internal/graph_base.hh (revision 1714) +++ mln/util/internal/graph_base.hh (working copy) @@ -44,6 +44,12 @@ namespace util { + /* FIXME: We should create actual types for node_id and edge_id, + (not just typedefs), at least to prevent the user from using a + node_id where an edge_id is expected (and vice versa). + Conversion to and from unsigned would still be useful, but it + might be safer to turn them into explicit ones. */ + /// \bref The type used to identify nodes. /// /// Used internally as a key to manipulate nodes.