https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Have piters on graph neighborhoods actually use the neighborhood. * mln/core/graph_neighborhood_piter.hh (mln::graph_neighborhood_fwd_piter<P, W>) (mln::graph_neighborhood_bkd_piter<P, W>): Have these class templates take a neighborhood type as second, additional parameter. (mln::graph_neighborhood_fwd_piter<P, W>::nbh_) (mln::graph_neighborhood_bkd_piter<P, W>::nbh_): New attributes. (mln::graph_neighborhood_fwd_piter<P, W>::graph_neighborhood_fwd_piter) (mln::graph_neighborhood_bkd_piter<P, W>::graph_neighborhood_bkd_piter): Adjust ctors. (mln::graph_neighborhood_fwd_piter<P, W>::first_) (mln::graph_neighborhood_fwd_piter<P, W>::step_) (mln::graph_neighborhood_bkd_piter<P, W>::first_) (mln::graph_neighborhood_bkd_piter<P, W>::step_): New methods. (mln::graph_neighborhood_fwd_piter<P, W>::start) (mln::graph_neighborhood_fwd_piter<P, W>::next_) (mln::graph_neighborhood_bkd_piter<P, W>::start) (mln::graph_neighborhood_bkd_piter<P, W>::next_): Delegate the body of the routine to the neighborhood. * mln/core/graph_elt_neighborhood.hh (mln::graph_elt_neighborhood<P>::fwd_qiter) (mln::graph_elt_neighborhood<P>::bkd_qiter): Adjust typedefs. (mln::graph_elt_neighborhood<P>::psite): New typedef. (mln::graph_elt_neighborhood<P>::start) (mln::graph_elt_neighborhood<P>::next_): New methods. * tests/core/graph_elt_neighborhood.cc: New test. mln/core/graph_elt_neighborhood.hh | 70 +++++++-- mln/core/graph_neighborhood_piter.hh | 250 +++++++++++++++++++---------------- tests/core/graph_elt_neighborhood.cc | 22 +-- 3 files changed, 205 insertions(+), 137 deletions(-) Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1807) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -57,16 +57,15 @@ template <typename P> class graph_psite; - /*----------------------------------. - | graph_neighborhood_fwd_piter<P>. | - `----------------------------------*/ + /*-------------------------------------. + | graph_neighborhood_fwd_piter<P, N>. | + `-------------------------------------*/ - /// \brief Forward iterator on graph neighborhood. - template <typename P> + template <typename P, typename N> class graph_neighborhood_fwd_piter : - public Point_Iterator< graph_neighborhood_fwd_piter<P> > // or Iterator<...>? + public Point_Iterator< graph_neighborhood_fwd_piter<P, N> > { - typedef graph_neighborhood_fwd_piter<P> self_; + typedef graph_neighborhood_fwd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -83,7 +82,7 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> + template <typename Pref> graph_neighborhood_fwd_piter(const N& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -115,11 +114,23 @@ /// Read-only access to the \a i-th coordinate. 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 nodes of the underlying graph. + util::node_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 nodes of the underlying graph. - util::node_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -127,16 +138,15 @@ }; - /*----------------------------------. - | graph_neighborhood_bkd_piter<P>. | - `----------------------------------*/ + /*-------------------------------------. + | graph_neighborhood_bkd_piter<P, N>. | + `-------------------------------------*/ - /// \brief Backward iterator on graph neighborhood. - template <typename P> + template <typename P, typename N> class graph_neighborhood_bkd_piter : - public Point_Iterator< graph_neighborhood_bkd_piter<P> > // or Iterator<...>? + public Point_Iterator< graph_neighborhood_bkd_piter<P, N> > { - typedef graph_neighborhood_bkd_piter<P> self_; + typedef graph_neighborhood_bkd_piter<P, N> self_; typedef Point_Iterator< self_ > super_; public: @@ -153,7 +163,7 @@ public: /// Construction. /// \{ - template <typename N, typename Pref> + template <typename Pref> graph_neighborhood_bkd_piter(const N& nbh, const Point_Site<Pref>& p_ref); /// \} @@ -185,11 +195,23 @@ /// Read-only access to the \a i-th coordinate. 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 nodes of the underlying graph. + util::node_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 nodes of the underlying graph. - util::node_id id_; /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -200,17 +222,17 @@ # ifndef MLN_INCLUDE_ONLY - /*----------------------------------. - | graph_neighborhood_fwd_piter<P>. | - `----------------------------------*/ - - // FIXME: Currently, argument nbh is ignored. - template <typename P> - template <typename N, typename Pref> + /*-------------------------------------. + | graph_neighborhood_fwd_piter<P, N>. | + `-------------------------------------*/ + + template <typename P, typename N> + template <typename Pref> inline - graph_neighborhood_fwd_piter<P>::graph_neighborhood_fwd_piter(const N& /* nbh */, + graph_neighborhood_fwd_piter<P, N>::graph_neighborhood_fwd_piter(const 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_(), p_() @@ -219,10 +241,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter<P>::is_valid() const + 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 @@ -230,60 +252,63 @@ return p_ref_.is_valid() && id_ < p_ref_.pg().gr_->nnodes(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P>::invalidate() + graph_neighborhood_fwd_piter<P, N>::invalidate() { - id_ = -1 + id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P>::start() + 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 - graph_neighborhood_fwd_piter<P>::next_() + graph_neighborhood_fwd_piter<P, N>::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_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + graph_neighborhood_fwd_piter<P, N>::first_() + { + id_ = 0; + } + + template <typename P, typename N> + inline + void + graph_neighborhood_fwd_piter<P, N>::step_() + { + ++id_; + } + + + template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter<P>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P>::update_() + graph_neighborhood_fwd_piter<P, N>::update_() { // Update psite_. psite_ = graph_psite<P>(p_ref_.pg(), id_); @@ -291,51 +316,51 @@ p_ = p_ref_.pg().gr_->node_data(id_); } - template <typename P> + template <typename P, typename N> inline const P& - graph_neighborhood_fwd_piter<P>::to_point() const + graph_neighborhood_fwd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const graph_psite<P>& - graph_neighborhood_fwd_piter<P>::to_psite() const + graph_neighborhood_fwd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - graph_neighborhood_fwd_piter<P>::operator graph_psite<P>() const + graph_neighborhood_fwd_piter<P, N>::operator graph_psite<P>() const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - graph_neighborhood_fwd_piter<P>::operator[](unsigned i) const + graph_neighborhood_fwd_piter<P, N>::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> + /*-------------------------------------. + | graph_neighborhood_bkd_piter<P, N>. | + `-------------------------------------*/ + + template <typename P, typename N> + template <typename Pref> inline - graph_neighborhood_bkd_piter<P>::graph_neighborhood_bkd_piter(const N& /* nbh */, + graph_neighborhood_bkd_piter<P, N>::graph_neighborhood_bkd_piter(const N& nbh, const Point_Site<Pref>& p_ref) - : p_ref_(exact(p_ref).to_psite()), + : nbh_(nbh), + p_ref_(exact(p_ref).to_psite()), // Initialize psite_ to a dummy value. psite_(), p_() @@ -344,10 +369,10 @@ invalidate(); } - template <typename P> + template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter<P>::is_valid() const + 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 @@ -355,60 +380,63 @@ return p_ref_.is_valid() && id_ < p_ref_.pg().gr_->nnodes(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P>::invalidate() + graph_neighborhood_bkd_piter<P, N>::invalidate() { id_ = -1; } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P>::start() + graph_neighborhood_bkd_piter<P, N>::start() { - id_ = p_ref_.pg().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_(). */ + nbh_.start(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P>::next_() + graph_neighborhood_bkd_piter<P, N>::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_()); + nbh_.next_(*this); if (is_valid()) update_(); } - template <typename P> + template <typename P, typename N> + inline + void + graph_neighborhood_bkd_piter<P, N>::first_() + { + id_ = p_ref_.pg().gr_->nnodes() - 1; + } + + template <typename P, typename N> + inline + void + graph_neighborhood_bkd_piter<P, N>::step_() + { + --id_; + } + + + template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter<P>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const { return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); } - template <typename P> + template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P>::update_() + graph_neighborhood_bkd_piter<P, N>::update_() { // Update psite_. psite_ = graph_psite<P>(p_ref_.pg(), id_); @@ -416,34 +444,34 @@ p_ = p_ref_.pg().gr_->node_data(id_); } - template <typename P> + template <typename P, typename N> inline const P& - graph_neighborhood_bkd_piter<P>::to_point() const + graph_neighborhood_bkd_piter<P, N>::to_point() const { return p_; } - template <typename P> + template <typename P, typename N> inline const graph_psite<P>& - graph_neighborhood_bkd_piter<P>::to_psite() const + graph_neighborhood_bkd_piter<P, N>::to_psite() const { return psite_; } - template <typename P> + template <typename P, typename N> inline - graph_neighborhood_bkd_piter<P>::operator graph_psite<P>() const + graph_neighborhood_bkd_piter<P, N>::operator graph_psite<P>() const { mln_precondition(is_valid()); return psite_; } - template <typename P> + template <typename P, typename N> inline mln_coord(P) - graph_neighborhood_bkd_piter<P>::operator[](unsigned i) const + graph_neighborhood_bkd_piter<P, N>::operator[](unsigned i) const { assert(i < dim); return p_[i]; Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1807) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -50,8 +50,8 @@ namespace mln { // Fwd decls. - template <typename P> class graph_neighborhood_fwd_piter; - template <typename P> class graph_neighborhood_bkd_piter; + template <typename P, typename W> class graph_neighborhood_fwd_piter; + template <typename P, typename W> class graph_neighborhood_bkd_piter; /*! \brief Elementary neighborhood on graph class. @@ -67,29 +67,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 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 graph_neighborhood_fwd_piter<P> fwd_qiter; + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of vertices. + typedef graph_neighborhood_fwd_piter<P, self_> fwd_niter; + + /// \brief Point_Iterator type to browse the psites of the + /// neighborhood w.r.t. the ordering of vertices. + typedef graph_neighborhood_bkd_piter<P, self_> bkd_niter; - /*! \brief Point_Iterator type to browse the points of a generic - * neighborhood w.r.t. the reverse ordering of delta-points. - */ - typedef graph_neighborhood_bkd_piter<P> bkd_qiter; + /// The default niter type. + typedef fwd_niter niter; + /// \} - /// The default qiter type. - typedef fwd_qiter qiter; + /// 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 + 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 + 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/graph_elt_neighborhood.cc --- tests/core/graph_elt_neighborhood.cc (revision 1806) +++ tests/core/graph_elt_neighborhood.cc (working copy) @@ -25,9 +25,9 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/graph_elt_window.cc +/*! \file tests/core/graph_elt_neighborhood.cc * - * \brief Tests on mln::graph_elt_window. + * \brief Tests on mln::graph_elt_neighborhood. */ #include <iostream> @@ -35,7 +35,7 @@ #include <vector> #include <mln/core/point2d.hh> -#include <mln/core/graph_elt_window.hh> +#include <mln/core/graph_elt_neighborhood.hh> #include <mln/debug/iota.hh> #include <mln/debug/println.hh> @@ -84,24 +84,24 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*------------------. - | Graph and window. | - `------------------*/ + /*-------------------------. + | Graph and neighborhood. | + `-------------------------*/ // Graph psite set. p_graph<p_t> pg(g); // Graph point site. graph_psite<p_t> p(pg, 1); - // ``Sliding'' window of a psite of PG. - typedef graph_elt_window<p_t> win_t; - win_t win; + // ``Sliding'' neighborhood of a psite of PG. + typedef graph_elt_neighborhood<p_t> nbh_t; + nbh_t nbh; - mln_fwd_qiter_(win_t) fq(win, p); + mln_fwd_niter_(nbh_t) fq(nbh, p); for_all(fq) std::cout << fq << " "; std::cout << std::endl; - mln_bkd_qiter_(win_t) bq(win, p); + mln_bkd_niter_(nbh_t) bq(nbh, p); for_all(bq) std::cout << bq << " "; std::cout << std::endl;