[Olena-patches] 1780: Add backward iterators for graph-related neighborhoods and windows; document forward iterators.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; 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<P>::operator point): Remove. (mln::graph_neighborhood_fwd_piter<P>::invalidate): Initialize member id_ to -1. (mln::graph_neighborhood_bkd_piter<P>): New class. * mln/core/graph_window_piter.hh: More documentation. (mln::graph_window_fwd_piter<P>::operator point): Remove. (mln::graph_window_fwd_piter<P>::invalidate): Initialize member id_ to -1. (mln::graph_window_bkd_piter<P>): 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<P> 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<P> 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<P>. | `---------------------------------------*/ - /// \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<P> > // 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<P> 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<P> psite; @@ -244,9 +242,6 @@ inline line_graph_neighborhood_fwd_piter<P>::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<P>::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<P>. | `----------------------------*/ + /// \brief Forward iterator on graph window. template <typename P> class graph_window_fwd_piter : public Point_Iterator< graph_window_fwd_piter<P> > // or Iterator<...>? @@ -74,41 +70,52 @@ typedef Point_Iterator< self_ > super_; public: - typedef graph_psite<P> psite; - enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; + typedef graph_psite<P> 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<P>. | `----------------------------*/ + /// \brief Backward iterator on graph window. + template <typename P> + class graph_window_bkd_piter : + public Point_Iterator< graph_window_bkd_piter<P> > // or Iterator<...>? + { + typedef graph_window_bkd_piter<P> self_; + typedef Point_Iterator< self_ > super_; + + public: + enum { dim = P::dim }; + + typedef graph_psite<P> 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<P>. | + `----------------------------*/ + // 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<P>::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<P>::operator P() const + graph_window_fwd_piter<P>::operator graph_psite<P>() const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + graph_window_fwd_piter<P>::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + + /*----------------------------. + | graph_window_bkd_piter<P>. | + `----------------------------*/ + + // FIXME: Currently, argument win is ignored. + template <typename P> + template <typename W, typename Pref> + inline + graph_window_bkd_piter<P>::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<P>::is_valid() const + { + return id_ < p_ref_.pg().npoints(); + } + + template <typename P> + inline + void + graph_window_bkd_piter<P>::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + graph_window_bkd_piter<P>::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<P>::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<P>::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<P>::update_() + { + // Update psite_. + psite_ = graph_psite<P>(p_ref_.pg(), id_); + // Update p_. + p_ = p_ref_.pg().point_from_id(id_); + } + + template <typename P> + inline + const P& + graph_window_bkd_piter<P>::to_point() const + { return p_; } template <typename P> inline - graph_window_fwd_piter<P>::operator graph_psite<P>() const + const graph_psite<P>& + graph_window_bkd_piter<P>::to_psite() const + { + return psite_; + } + + template <typename P> + inline + graph_window_bkd_piter<P>::operator graph_psite<P>() const { mln_precondition(is_valid()); return psite_; @@ -250,7 +443,7 @@ template <typename P> inline mln_coord(P) - graph_window_fwd_piter<P>::operator[](unsigned i) const + graph_window_bkd_piter<P>::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<P>. | `----------------------------------*/ + /// \brief Forward iterator on graph neighborhood. template <typename P> class graph_neighborhood_fwd_piter : public Point_Iterator< graph_neighborhood_fwd_piter<P> > // or Iterator<...>? @@ -74,39 +70,49 @@ typedef Point_Iterator< self_ > super_; public: - typedef graph_psite<P> psite; - enum { dim = P::dim }; - // FIXME: Dummy value. - typedef void mesh; + typedef graph_psite<P> 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<P>. | `----------------------------------*/ + /// \brief Backward iterator on graph neighborhood. + template <typename P> + class graph_neighborhood_bkd_piter : + public Point_Iterator< graph_neighborhood_bkd_piter<P> > // or Iterator<...>? + { + typedef graph_neighborhood_bkd_piter<P> self_; + typedef Point_Iterator< self_ > super_; + + public: + enum { dim = P::dim }; + + typedef graph_psite<P> 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<P>. | + `----------------------------------*/ + // 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<P>::invalidate() { - id_ = p_ref_.pg().gr_.nnodes(); + id_ = -1 } template <typename P> @@ -254,15 +331,154 @@ template <typename P> inline - graph_neighborhood_fwd_piter<P>::operator P() const + graph_neighborhood_fwd_piter<P>::operator graph_psite<P>() const { mln_precondition(is_valid()); + return psite_; + } + + template <typename P> + inline + mln_coord(P) + graph_neighborhood_fwd_piter<P>::operator[](unsigned i) const + { + assert(i < dim); + return p_[i]; + } + + + /*----------------------------------. + | graph_neighborhood_bkd_piter<P>. | + `----------------------------------*/ + + // FIXME: Currently, argument nbh is ignored. + template <typename P> + template <typename N, typename Pref> + inline + graph_neighborhood_bkd_piter<P>::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<P>::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<P>::invalidate() + { + id_ = -1; + } + + template <typename P> + inline + void + graph_neighborhood_bkd_piter<P>::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<P>::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<P>::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<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_neighborhood_bkd_piter<P>::to_point() const + { return p_; } template <typename P> inline - graph_neighborhood_fwd_piter<P>::operator graph_psite<P>() const + const graph_psite<P>& + graph_neighborhood_bkd_piter<P>::to_psite() const + { + return psite_; + } + + template <typename P> + inline + graph_neighborhood_bkd_piter<P>::operator graph_psite<P>() const { mln_precondition(is_valid()); return psite_; @@ -271,7 +487,7 @@ template <typename P> inline mln_coord(P) - graph_neighborhood_fwd_piter<P>::operator[](unsigned i) const + graph_neighborhood_bkd_piter<P>::operator[](unsigned i) const { assert(i < dim); return p_[i];