[Olena-patches] 1814: Have piters on line graph windows and neighborhoods actually use them.

https://svn.lrde.epita.fr/svn/oln/trunk/milena All the duplicated code is the source of all those repetitive changes. My next patches will be about factoring all those guys. Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Have piters on line graph windows and neighborhoods actually use them. * mln/core/line_graph_window_piter.hh (mln::line_graph_window_fwd_piter<P, W>) (mln::line_graph_window_bkd_piter<P, W>): Have these class templates take a window type as second, additional parameter. (mln::line_graph_window_fwd_piter<P, W>::nbh_) (mln::line_graph_window_bkd_piter<P, W>::nbh_): New attributes. (line_graph_window_fwd_piter) (line_graph_window_bkd_piter): Adjust ctors. (mln::line_graph_window_fwd_piter<P, W>::first_) (mln::line_graph_window_fwd_piter<P, W>::step_) (mln::line_graph_window_bkd_piter<P, W>::first_) (mln::line_graph_window_bkd_piter<P, W>::step_): New methods. (mln::line_graph_window_fwd_piter<P, W>::start) (mln::line_graph_window_fwd_piter<P, W>::next_) (mln::line_graph_window_bkd_piter<P, W>::start) (mln::line_graph_window_bkd_piter<P, W>::next_): Delegate the body of the routine to the window. * mln/core/line_graph_elt_window.hh (mln::line_graph_elt_window<P>::fwd_qiter) (mln::line_graph_elt_window<P>::bkd_qiter): Adjust typedefs. (mln::line_graph_elt_window<P>::psite): New typedef. (mln::line_graph_elt_window<P>::start) (mln::line_graph_elt_window<P>::next_): New methods. * mln/core/line_graph_neighborhood_piter.hh (mln::line_graph_neighborhood_fwd_piter<P, N>) (mln::line_graph_neighborhood_bkd_piter<P, N>): Have these class templates take a neighborhood type as second, additional parameter. (mln::line_graph_neighborhood_fwd_piter<P, N>::nbh_) (mln::line_graph_neighborhood_bkd_piter<P, N>::nbh_): New attributes. (line_graph_neighborhood_fwd_piter) (line_graph_neighborhood_bkd_piter): Adjust ctors. (mln::line_graph_neighborhood_fwd_piter<P, N>::first_) (mln::line_graph_neighborhood_fwd_piter<P, N>::step_) (mln::line_graph_neighborhood_bkd_piter<P, N>::first_) (mln::line_graph_neighborhood_bkd_piter<P, N>::step_): New methods. (mln::line_graph_neighborhood_fwd_piter<P, N>::start) (mln::line_graph_neighborhood_fwd_piter<P, N>::next_) (mln::line_graph_neighborhood_bkd_piter<P, N>::start) (mln::line_graph_neighborhood_bkd_piter<P, N>::next_): Delegate the body of the routine to the neighborhood. * mln/core/line_graph_elt_neighborhood.hh (mln::line_graph_elt_neighborhood<P>::fwd_qiter) (mln::line_graph_elt_neighborhood<P>::bkd_qiter): Adjust typedefs. (mln::line_graph_elt_neighborhood<P>::psite): New typedef. (mln::line_graph_elt_neighborhood<P>::start) (mln::line_graph_elt_neighborhood<P>::next_): New methods. * tests/core/line_graph_elt_window.cc: Update test. * tests/core/line_graph_elt_neighborhood.cc: New test. mln/core/line_graph_elt_neighborhood.hh | 92 +++++++--- mln/core/line_graph_elt_window.hh | 90 ++++++---- mln/core/line_graph_neighborhood_piter.hh | 260 ++++++++++++++++------------- mln/core/line_graph_window_piter.hh | 263 ++++++++++++++++-------------- tests/core/line_graph_elt_neighborhood.cc | 43 +++- tests/core/line_graph_elt_window.cc | 29 +++ 6 files changed, 479 insertions(+), 298 deletions(-) Index: mln/core/line_graph_window_piter.hh --- mln/core/line_graph_window_piter.hh (revision 1813) +++ mln/core/line_graph_window_piter.hh (working copy) @@ -57,16 +57,16 @@ template <typename P> class line_graph_psite; - /*---------------------------------. - | line_graph_window_fwd_piter<P>. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_fwd_piter<P, W>. | + `------------------------------------*/ /// \brief Forward iterator on line graph window. - template <typename P> + template <typename P, typename W> class line_graph_window_fwd_piter : - public Point_Iterator< line_graph_window_fwd_piter<P> > // or Iterator<...>? + public Point_Iterator< line_graph_window_fwd_piter<P, W> > { - typedef line_graph_window_fwd_piter<P> self_; + typedef line_graph_window_fwd_piter<P, W> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,8 +83,9 @@ public: /// Construction. /// \{ - template <typename W, typename Pref> - line_graph_window_fwd_piter(const W& win, const Point_Site<Pref>& p_ref); + template <typename Pref> + line_graph_window_fwd_piter(const Window<W>& win, + const Point_Site<Pref>& p_ref); /// \} /// Manipulation. @@ -117,11 +118,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the window. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The window. + const W& win_; /// 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. @@ -134,22 +147,22 @@ 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> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P>& p); + operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P, W>& p); - /*---------------------------------. - | line_graph_window_bkd_piter<P>. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_bkd_piter<P, W>. | + `------------------------------------*/ /// \brief Backward iterator on line graph window. - template <typename P> + template <typename P, typename W> class line_graph_window_bkd_piter : - public Point_Iterator< line_graph_window_bkd_piter<P> > // or Iterator<...>? + public Point_Iterator< line_graph_window_bkd_piter<P, W> > { - typedef line_graph_window_bkd_piter<P> self_; + typedef line_graph_window_bkd_piter<P, W> self_; typedef Point_Iterator< self_ > super_; public: @@ -166,8 +179,9 @@ public: /// Construction. /// \{ - template <typename W, typename Pref> - line_graph_window_bkd_piter(const W& win, const Point_Site<Pref>& p_ref); + template <typename Pref> + line_graph_window_bkd_piter(const Window<W>& win, + const Point_Site<Pref>& p_ref); /// \} /// Manipulation. @@ -200,11 +214,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the window. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The window. + const W& win_; /// 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. @@ -217,26 +243,26 @@ 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> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P>& p); + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P, W>& p); # ifndef MLN_INCLUDE_ONLY - /*---------------------------------. - | line_graph_window_fwd_piter<P>. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_fwd_piter<P, W>. | + `------------------------------------*/ - // FIXME: Currently, argument win is ignored. - template <typename P> - template <typename W, typename Pref> + template <typename P, typename W> + template <typename Pref> inline - line_graph_window_fwd_piter<P>::line_graph_window_fwd_piter(const W& /* win */, + line_graph_window_fwd_piter<P, W>::line_graph_window_fwd_piter(const Window<W>& win, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : win_(exact(win)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -244,10 +270,10 @@ invalidate(); } - template <typename P> + template <typename P, typename W> inline bool - line_graph_window_fwd_piter<P>::is_valid() const + line_graph_window_fwd_piter<P, W>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -255,52 +281,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter<P>::invalidate() + line_graph_window_fwd_piter<P, W>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter<P>::start() + line_graph_window_fwd_piter<P, W>::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_(). */ + win_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter<P>::next_() + line_graph_window_fwd_piter<P, W>::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_()); + win_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> + inline + void + line_graph_window_fwd_piter<P, W>::first_() + { + id_ = 0; + } + + template <typename P, typename W> + inline + void + line_graph_window_fwd_piter<P, W>::step_() + { + ++id_; + } + + + template <typename P, typename W> inline bool - line_graph_window_fwd_piter<P>::adjacent_or_equal_to_p_ref_() const + line_graph_window_fwd_piter<P, W>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -330,68 +359,69 @@ return false; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_fwd_piter<P>::update_() + line_graph_window_fwd_piter<P, W>::update_() { // Update psite_. psite_ = line_graph_psite<P>(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename W> inline const P& - line_graph_window_fwd_piter<P>::to_point() const + line_graph_window_fwd_piter<P, W>::to_point() const { return p_; } - template <typename P> + template <typename P, typename W> inline const line_graph_psite<P>& - line_graph_window_fwd_piter<P>::to_psite() const + line_graph_window_fwd_piter<P, W>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename W> inline - line_graph_window_fwd_piter<P>::operator line_graph_psite<P> () const + line_graph_window_fwd_piter<P, W>::operator line_graph_psite<P> () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename W> inline mln_coord(P) - line_graph_window_fwd_piter<P>::operator[](unsigned i) const + line_graph_window_fwd_piter<P, W>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P>& p) + operator<<(std::ostream& ostr, const line_graph_window_fwd_piter<P, W>& p) { return ostr << p.to_psite(); } - /*---------------------------------. - | line_graph_window_bkd_piter<P>. | - `---------------------------------*/ + /*------------------------------------. + | line_graph_window_bkd_piter<P, W>. | + `------------------------------------*/ // FIXME: Currently, argument win is ignored. - template <typename P> - template <typename W, typename Pref> + template <typename P, typename W> + template <typename Pref> inline - line_graph_window_bkd_piter<P>::line_graph_window_bkd_piter(const W& /* win */, + line_graph_window_bkd_piter<P, W>::line_graph_window_bkd_piter(const Window<W>& win, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : win_(exact(win)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -399,10 +429,10 @@ invalidate(); } - template <typename P> + template <typename P, typename W> inline bool - line_graph_window_bkd_piter<P>::is_valid() const + line_graph_window_bkd_piter<P, W>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -410,52 +440,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter<P>::invalidate() + line_graph_window_bkd_piter<P, W>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter<P>::start() + line_graph_window_bkd_piter<P, W>::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_(). */ + win_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter<P>::next_() + line_graph_window_bkd_piter<P, W>::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_()); + win_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename W> + inline + void + line_graph_window_bkd_piter<P, W>::first_() + { + id_ = p_ref_.plg().gr_->nedges() - 1; + } + + template <typename P, typename W> + inline + void + line_graph_window_bkd_piter<P, W>::step_() + { + --id_; + } + + + template <typename P, typename W> inline bool - line_graph_window_bkd_piter<P>::adjacent_or_equal_to_p_ref_() const + line_graph_window_bkd_piter<P, W>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -485,52 +518,52 @@ return false; } - template <typename P> + template <typename P, typename W> inline void - line_graph_window_bkd_piter<P>::update_() + line_graph_window_bkd_piter<P, W>::update_() { // Update psite_. psite_ = line_graph_psite<P>(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename W> inline const P& - line_graph_window_bkd_piter<P>::to_point() const + line_graph_window_bkd_piter<P, W>::to_point() const { return p_; } - template <typename P> + template <typename P, typename W> inline const line_graph_psite<P>& - line_graph_window_bkd_piter<P>::to_psite() const + line_graph_window_bkd_piter<P, W>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename W> inline - line_graph_window_bkd_piter<P>::operator line_graph_psite<P> () const + line_graph_window_bkd_piter<P, W>::operator line_graph_psite<P> () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename W> inline mln_coord(P) - line_graph_window_bkd_piter<P>::operator[](unsigned i) const + line_graph_window_bkd_piter<P, W>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename W> inline std::ostream& - operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P>& p) + operator<<(std::ostream& ostr, const line_graph_window_bkd_piter<P, W>& p) { return ostr << p.to_psite(); } Index: mln/core/line_graph_elt_window.hh --- mln/core/line_graph_elt_window.hh (revision 1813) +++ mln/core/line_graph_elt_window.hh (working copy) @@ -28,13 +28,11 @@ #ifndef MLN_CORE_LINE_GRAPH_ELT_WINDOW_HH # define MLN_CORE_LINE_GRAPH_ELT_WINDOW_HH -/*! \file mln/core/line_graph_elt_window.hh - * - * \brief Definition of the elementary ``window'' on a line graph. - * - * \todo Make naming coherent: we have window (without '_') but - * point_, neighb_, etc. - */ +/// \file mln/core/line_graph_elt_window.hh +/// \brief Definition of the elementary ``window'' on a line graph. + +/* FIXME: Have a consistent naming: we have window (without '_') but + point_, neighb_, etc. */ /* FIXME: Factor those classes: - mln::graph_elt_window @@ -50,14 +48,11 @@ namespace mln { // Fwd decls. - template <typename P> class line_graph_window_fwd_piter; - template <typename P> class line_graph_window_bkd_piter; + template <typename P, typename W> class line_graph_window_fwd_piter; + template <typename P, typename W> class line_graph_window_bkd_piter; - /*! \brief Elementary window on line graph class. - * - * FIXME: Doc. - */ + /// \brief Elementary window on line graph class. template <typename P> class line_graph_elt_window : public Window< line_graph_elt_window<P> > { @@ -66,23 +61,21 @@ public: /// Associated types. /// \{ - /// The type of point stored into the window. - // FIXME: Is this right, if we consider that this window stores - // psites, not points? + /// The type of point corresponding to the window. typedef P point; + /// The type of psite corresponding to the window. + typedef line_graph_psite<P> psite; // FIXME: This is a dummy value. typedef void dpoint; - /*! \brief Point_Iterator type to browse the points of a generic window - * w.r.t. the ordering of delta-points. - */ - typedef line_graph_window_fwd_piter<P> fwd_qiter; - - /*! \brief Point_Iterator type to browse the points of a generic window - * w.r.t. the reverse ordering of delta-points. - */ - typedef line_graph_window_bkd_piter<P> bkd_qiter; + /// \brief Point_Iterator type to browse the psites of the window + /// w.r.t. the ordering of edges. + typedef line_graph_window_fwd_piter<P, self_> fwd_qiter; + + /// \brief Point_Iterator type to browse the psites of the window + /// w.r.t. the reverse ordering of edges. + typedef line_graph_window_bkd_piter<P, self_> bkd_qiter; /// The default qiter type. typedef fwd_qiter qiter; @@ -91,16 +84,25 @@ /// Construct an elementary line_graph window. line_graph_elt_window(); + /// Services for iterators. + /// \{ + /// Move \a piter to the beginning of the iteration on this window. + template <typename Piter> + void start(Point_Iterator<Piter>& piter) const; + /// Move \a piter to the next site on this window. + template <typename Piter> + void next_(Point_Iterator<Piter>& piter) const; + /// \} + + /// Interface of the concept Window. + /// \{ /// Is the window is empty? bool is_empty() const; - /// Is the window centered? bool is_centered() const; - /// Is the window symmetric? - // FIXME: We should defin this more precisely. + // FIXME: We should define this more precisely. bool is_symmetric() const; - /// Return the maximum coordinate gap between the window center /// and a window point. /* FIXME: This method returns a dummy value (0), since the delta @@ -114,9 +116,9 @@ It raises another question: should delta() be part of the concept ``Window''? */ unsigned delta() const; - /// Apply a central symmetry to the target window. self_& sym(); + /// \} }; @@ -129,6 +131,34 @@ } template <typename P> + template <typename Piter> + inline + void + line_graph_elt_window<P>::start(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + piter.first_(); + if (!piter.adjacent_or_equal_to_p_ref_()) + next_(piter); + } + + template <typename P> + template <typename Piter> + inline + void + line_graph_elt_window<P>::next_(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + /* 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. */ + do + piter.step_(); + while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); + } + + template <typename P> inline bool line_graph_elt_window<P>::is_empty() const Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1813) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -57,16 +57,16 @@ template <typename P> class line_graph_psite; - /*---------------------------------------. - | line_graph_neighborhood_fwd_piter<P>. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_fwd_piter<P, N>. | + `------------------------------------------*/ /// \brief Forward iterator on line graph neighborhood. - template <typename P> + template <typename P, typename N> class line_graph_neighborhood_fwd_piter : - public Point_Iterator< line_graph_neighborhood_fwd_piter<P> > // or Iterator<...>? + public Point_Iterator< line_graph_neighborhood_fwd_piter<P, N> > { - typedef line_graph_neighborhood_fwd_piter<P> self_; + typedef line_graph_neighborhood_fwd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,8 +83,8 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> - line_graph_neighborhood_fwd_piter(const N& nbh, + template <typename Pref> + line_graph_neighborhood_fwd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -119,11 +119,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the neighborhood. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The neighborhood. + const N& nbh_; /// 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. @@ -136,23 +148,23 @@ 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> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_fwd_piter<P>& p); + const line_graph_neighborhood_fwd_piter<P, N>& p); - /*---------------------------------------. - | line_graph_neighborhood_bkd_piter<P>. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_bkd_piter<P, N>. | + `------------------------------------------*/ /// \brief Backward iterator on line graph neighborhood. - template <typename P> + template <typename P, typename N> class line_graph_neighborhood_bkd_piter : - public Point_Iterator< line_graph_neighborhood_bkd_piter<P> > // or Iterator<...>? + public Point_Iterator< line_graph_neighborhood_bkd_piter<P, N> > { - typedef line_graph_neighborhood_bkd_piter<P> self_; + typedef line_graph_neighborhood_bkd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -169,8 +181,8 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> - line_graph_neighborhood_bkd_piter(const N& nbh, + template <typename Pref> + line_graph_neighborhood_bkd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -205,11 +217,23 @@ coord operator[](unsigned i) const; /// \} + /// Internals, used by the neighborhood. + /// \{ + public: + /// Set the iterator to the first site of the graph. + void first_(); + /// Advance the position of the iterator by one step. + void step_(); + + /// An internal iterator on the set of edges of the underlying graph. + util::edge_id id_; + /// \} + private: + /// The neighborhood. + const N& nbh_; /// 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. @@ -222,27 +246,28 @@ 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> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_bkd_piter<P>& p); + const line_graph_neighborhood_bkd_piter<P, N>& p); # ifndef MLN_INCLUDE_ONLY - /*---------------------------------------. - | line_graph_neighborhood_fwd_piter<P>. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_fwd_piter<P, N>. | + `------------------------------------------*/ // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + template <typename P, typename N> + template <typename Pref> inline - line_graph_neighborhood_fwd_piter<P>::line_graph_neighborhood_fwd_piter(const N& /* nbh */, + line_graph_neighborhood_fwd_piter<P, N>::line_graph_neighborhood_fwd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : nbh_(exact(nbh)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -250,10 +275,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - line_graph_neighborhood_fwd_piter<P>::is_valid() const + line_graph_neighborhood_fwd_piter<P, N>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -261,52 +286,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter<P>::invalidate() + line_graph_neighborhood_fwd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter<P>::start() + line_graph_neighborhood_fwd_piter<P, N>::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_(). */ + nbh_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter<P>::next_() + line_graph_neighborhood_fwd_piter<P, N>::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_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + line_graph_neighborhood_fwd_piter<P, N>::first_() + { + id_ = 0; + } + + template <typename P, typename N> + inline + void + line_graph_neighborhood_fwd_piter<P, N>::step_() + { + ++id_; + } + + + template <typename P, typename N> inline bool - line_graph_neighborhood_fwd_piter<P>::adjacent_or_equal_to_p_ref_() const + line_graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -336,69 +364,70 @@ return false; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter<P>::update_() + line_graph_neighborhood_fwd_piter<P, N>::update_() { // Update psite_. psite_ = line_graph_psite<P>(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename N> inline const P& - line_graph_neighborhood_fwd_piter<P>::to_point() const + line_graph_neighborhood_fwd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const line_graph_psite<P>& - line_graph_neighborhood_fwd_piter<P>::to_psite() const + line_graph_neighborhood_fwd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - line_graph_neighborhood_fwd_piter<P>::operator line_graph_psite<P> () const + line_graph_neighborhood_fwd_piter<P, N>::operator line_graph_psite<P> () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - line_graph_neighborhood_fwd_piter<P>::operator[](unsigned i) const + line_graph_neighborhood_fwd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_fwd_piter<P>& p) + const line_graph_neighborhood_fwd_piter<P, N>& p) { return ostr << p.to_psite(); } - /*---------------------------------------. - | line_graph_neighborhood_bkd_piter<P>. | - `---------------------------------------*/ + /*------------------------------------------. + | line_graph_neighborhood_bkd_piter<P, N>. | + `------------------------------------------*/ // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + template <typename P, typename N> + template <typename Pref> inline - line_graph_neighborhood_bkd_piter<P>::line_graph_neighborhood_bkd_piter(const N& /* nbh */, + line_graph_neighborhood_bkd_piter<P, N>::line_graph_neighborhood_bkd_piter(const Neighborhood<N>& nbh, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : nbh_(exact(nbh)), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_() { @@ -406,10 +435,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - line_graph_neighborhood_bkd_piter<P>::is_valid() const + line_graph_neighborhood_bkd_piter<P, N>::is_valid() const { // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract @@ -417,52 +446,55 @@ return p_ref_.is_valid() && id_ < p_ref_.plg().gr_->nedges(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter<P>::invalidate() + line_graph_neighborhood_bkd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter<P>::start() + line_graph_neighborhood_bkd_piter<P, N>::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_(). */ + nbh_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter<P>::next_() + line_graph_neighborhood_bkd_piter<P, N>::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_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + line_graph_neighborhood_bkd_piter<P, N>::first_() + { + id_ = p_ref_.plg().gr_->nedges() - 1; + } + + template <typename P, typename N> + inline + void + line_graph_neighborhood_bkd_piter<P, N>::step_() + { + --id_; + } + + + template <typename P, typename N> inline bool - line_graph_neighborhood_bkd_piter<P>::adjacent_or_equal_to_p_ref_() const + line_graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { // Check wether the iterator points to P_REF_. if (id_ == p_ref_.id()) @@ -492,53 +524,53 @@ return false; } - template <typename P> + template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter<P>::update_() + line_graph_neighborhood_bkd_piter<P, N>::update_() { // Update psite_. psite_ = line_graph_psite<P>(p_ref_.plg(), id_); } - template <typename P> + template <typename P, typename N> inline const P& - line_graph_neighborhood_bkd_piter<P>::to_point() const + line_graph_neighborhood_bkd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const line_graph_psite<P>& - line_graph_neighborhood_bkd_piter<P>::to_psite() const + line_graph_neighborhood_bkd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - line_graph_neighborhood_bkd_piter<P>::operator line_graph_psite<P> () const + line_graph_neighborhood_bkd_piter<P, N>::operator line_graph_psite<P> () const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - line_graph_neighborhood_bkd_piter<P>::operator[](unsigned i) const + line_graph_neighborhood_bkd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; } - template <typename P> + template <typename P, typename N> inline std::ostream& operator<<(std::ostream& ostr, - const line_graph_neighborhood_bkd_piter<P>& p) + const line_graph_neighborhood_bkd_piter<P, N>& p) { return ostr << p.to_psite(); } Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1813) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -28,17 +28,11 @@ #ifndef MLN_CORE_LINE_GRAPH_ELT_NEIGHBORHOOD_HH # define MLN_CORE_LINE_GRAPH_ELT_NEIGHBORHOOD_HH -/*! \file mln/core/line_graph_elt_neighborhood.hh - * - * \brief Definition of the elementary ``window'' on a line graph. - * - * \todo Make naming coherent: we have window (without '_') but - * point_, neighb_, etc. - */ +/// \file mln/core/line_graph_elt_neighborhood.hh +/// \brief Definition of the elementary ``window'' on a line graph. -# include <mln/core/concept/neighborhood.hh> -# include <mln/core/line_graph_psite.hh> -# include <mln/core/line_graph_neighborhood_piter.hh> +/* FIXME: Have a consistent naming: we have window (without '_') but + point_, neighb_, etc. */ /* FIXME: Factor those classes: - mln::graph_elt_window @@ -46,17 +40,19 @@ - mln::line_graph_elt_window - mln::line_graph_elt_neighborhood. */ +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/line_graph_psite.hh> +# include <mln/core/line_graph_neighborhood_piter.hh> + + namespace mln { // Fwd decls. - template <typename P> class line_graph_neighborhood_fwd_piter; - template <typename P> class line_graph_neighborhood_bkd_piter; + template <typename P, typename N> class line_graph_neighborhood_fwd_piter; + template <typename P, typename N> class line_graph_neighborhood_bkd_piter; - /*! \brief Elementary neighborhood on line graph class. - * - * FIXME: Doc. - */ + /// \brief Elementary neighborhood on line graph class. template <typename P> class line_graph_elt_neighborhood : public Neighborhood< line_graph_elt_neighborhood<P> > @@ -66,29 +62,69 @@ public: /// Associated types. /// \{ - /// The type of point stored into the neighborhood. - // FIXME: Is this right, if we consider that this neighborhood stores - // psites, not points? + /// The type of point corresponding to the neighborhood. typedef P point; + /// The type of psite corresponding to the neighborhood. + typedef line_graph_psite<P> psite; // FIXME: This is a dummy value. typedef void dpoint; - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the ordering of delta-points. - */ - typedef line_graph_neighborhood_fwd_piter<P> fwd_niter; - - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the reverse ordering of delta-points. - */ - typedef line_graph_neighborhood_bkd_piter<P> bkd_niter; + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of edges. + typedef line_graph_neighborhood_fwd_piter<P, self_> fwd_niter; + + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the reverse ordering of edges. + typedef line_graph_neighborhood_bkd_piter<P, self_> bkd_niter; /// The default qiter type. typedef fwd_niter niter; /// \} + + /// Services for iterators. + /// \{ + /// Move \a piter to the beginning of the iteration on this neighborhood. + template <typename Piter> + void start(Point_Iterator<Piter>& piter) const; + /// Move \a piter to the next site on this neighborhood. + template <typename Piter> + void next_(Point_Iterator<Piter>& piter) const; + /// \} }; +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + template <typename Piter> + inline + void + line_graph_elt_neighborhood<P>::start(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + piter.first_(); + if (!piter.adjacent_or_equal_to_p_ref_()) + next_(piter); + } + + template <typename P> + template <typename Piter> + inline + void + line_graph_elt_neighborhood<P>::next_(Point_Iterator<Piter>& piter_) const + { + Piter& piter = exact(piter_); + /* 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. */ + do + piter.step_(); + while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); + } + +# endif // ! MLN_INCLUDE_ONLY + } // end of namespace mln Index: tests/core/line_graph_elt_window.cc --- tests/core/line_graph_elt_window.cc (revision 1813) +++ tests/core/line_graph_elt_window.cc (working copy) @@ -49,6 +49,20 @@ | Graph. | `--------*/ + /* The graph is as follows and its corresponding line graph are as + follows: + + 0 1 2 3 4 0 1 2 3 4 + .----------- .----------- + | | + 0 | 0 2 0 | * * + 1 | \ / | 1 | 0 1 | + 2 | 1 | 2 | * 4 + 3 | \ | 3 | 2 | + 4 | 3-4 4 | *3* + + */ + // Points associated to nodes. std::vector<p_t> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -76,7 +90,18 @@ // Line graph psite set. p_line_graph<p_t> plg(g); // Line graph point site. - line_graph_psite<p_t> psite(plg, 0); + line_graph_psite<p_t> p(plg, 1); // ``Sliding'' window of a psite of PLG. - line_graph_elt_window<p_t> win; + typedef line_graph_elt_window<p_t> win_t; + win_t win; + + mln_fwd_qiter_(win_t) fq(win, p); + for_all(fq) + std::cout << fq << " "; + std::cout << std::endl; + + mln_bkd_qiter_(win_t) bq(win, p); + for_all(bq) + std::cout << bq << " "; + std::cout << std::endl; } Index: tests/core/line_graph_elt_neighborhood.cc --- tests/core/line_graph_elt_neighborhood.cc (revision 1813) +++ tests/core/line_graph_elt_neighborhood.cc (working copy) @@ -25,15 +25,15 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/line_graph_elt_window.cc +/*! \file tests/core/line_graph_elt_neighborhood.cc * - * \brief Tests on mln::line_graph_elt_window. + * \brief Tests on mln::line_graph_elt_neighborhood. */ #include <vector> #include <mln/core/point2d.hh> -#include <mln/core/line_graph_elt_window.hh> +#include <mln/core/line_graph_elt_neighborhood.hh> #include <mln/debug/iota.hh> #include <mln/debug/println.hh> @@ -49,6 +49,20 @@ | Graph. | `--------*/ + /* The graph is as follows and its corresponding line graph are as + follows: + + 0 1 2 3 4 0 1 2 3 4 + .----------- .----------- + | | + 0 | 0 2 0 | * * + 1 | \ / | 1 | 0 1 | + 2 | 1 | 2 | * 4 + 3 | \ | 3 | 2 | + 4 | 3-4 4 | *3* + + */ + // Points associated to nodes. std::vector<p_t> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -69,14 +83,25 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*------------------. - | Graph and window. | - `------------------*/ + /*-------------------------. + | Graph and neighborhood. | + `-------------------------*/ // Line graph psite set. p_line_graph<p_t> plg(g); // Line graph point site. - line_graph_psite<p_t> psite(plg, 0); - // ``Sliding'' window of a psite of PLG. - line_graph_elt_window<p_t> win; + line_graph_psite<p_t> p(plg, 1); + // ``Sliding'' neighborhood of a psite of PLG. + typedef line_graph_elt_neighborhood<p_t> nbh_t; + nbh_t nbh; + + mln_fwd_niter_(nbh_t) fq(nbh, p); + for_all(fq) + std::cout << fq << " "; + std::cout << std::endl; + + mln_bkd_niter_(nbh_t) bq(nbh, p); + for_all(bq) + std::cout << bq << " "; + std::cout << std::endl; }