[Olena-patches] 1770: Add a backward iterator on p_graph.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Add a backward iterator on p_graph. * mln/core/p_graph_piter.hh (p_graph_piter_<P>): Rename as... (p_graph_fwd_piter_<P>): ...this. (p_graph_fwd_piter_<P>::operator point): Remove. (p_graph_fwd_piter_<P>::pg_): Change the type of this member from const p_graph<P>& to const p_graph<P>*. (p_graph_fwd_piter_<P>::p_graph_fwd_piter_(const p_graph<P>&)) (p_graph_fwd_piter_<P>::is_valid) (p_graph_fwd_piter_<P>::invalidate) (p_graph_fwd_piter_<P>::update_): Adjust. (p_graph_fwd_piter_<P>::coord): New typedef. (p_graph_fwd_piter_(const p_graph_fwd_piter_<P>&)): New ctor. (p_graph_fwd_piter_<P>::operator= (const p_graph_fwd_piter_<P>&)): New operator. (p_graph_piter_<P>::operator P): Remove. (p_graph_bkd_piter_<P>): New. (operator<<(std::ostream&, const p_graph_fwd_piter_<P>&)) (operator<<(std::ostream&, const p_graph_bkd_piter_<P>&)): New. * mln/core/p_graph.hh (mln::p_graph<P>::fwd_piter): Adjust to the new name of mln::p_graph_fwd_piter_<P>. (mln::p_graph<P>::bkd_piter): New typedef. (mln::p_graph<P>::nlines): Rename as... (mln::p_graph<P>::nedges): ..this. (mln::p_graph<P>::npoints): Rename as... (mln::p_graph<P>::nnodes): ...this. (mln::p_graph<P>::npoints): New. (operator==(const p_graph<P>&, const p_graph<P>&)): New. * mln/draw/graph.hh (graph(Image<I>&, const graph_image<P, V>&, mln_value(I))): Adjust. core/p_graph.hh | 51 +++++-- core/p_graph_piter.hh | 350 ++++++++++++++++++++++++++++++++++++++++++++------ draw/graph.hh | 4 3 files changed, 353 insertions(+), 52 deletions(-) Index: mln/core/p_graph_piter.hh --- mln/core/p_graph_piter.hh (revision 1769) +++ mln/core/p_graph_piter.hh (working copy) @@ -32,10 +32,8 @@ # include <mln/core/p_graph.hh> # include <mln/core/graph_psite.hh> -/*! \file mln/core/p_graph_piter.hh - * - * \brief Definition of point iterator on graph-based point set. - */ +/// \file mln/core/p_graph_piter.hh +/// \brief Definition of point iterator on graph-based point set. namespace mln { @@ -44,57 +42,140 @@ template<typename P> class graph_psite; - // FIXME: Why `p_graph_piter_' and not `p_graph_piter' (without `_')? + /*------------------------. + | p_graph_fwd_piter_<P>. | + `------------------------*/ + /// \brief Forward iterator on point sites of a mln::p_graph<P>. template<typename P> - class p_graph_piter_ - : public internal::point_iterator_base_< P, p_graph_piter_<P> > + class p_graph_fwd_piter_ + : public internal::point_iterator_base_< P, p_graph_fwd_piter_<P> > { - typedef p_graph_piter_<P> self_; + typedef p_graph_fwd_piter_<P> self_; typedef internal::point_iterator_base_< P, self_ > super_; public: - // Make definitions from super class available. enum { dim = super_::dim }; + typedef graph_psite<P> psite; typedef P point; + typedef mln_coord(point) coord; + + /// Construction and assignment. + /// \{ + p_graph_fwd_piter_(const p_graph<P>& pg); + p_graph_fwd_piter_(const self_& rhs); + self_& operator= (const self_& rhs); + /// \} - p_graph_piter_(const p_graph<P>& pg); + /// 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. + const point& to_point () const; + /// Reference to the corresponding point site. + const psite& to_psite () const; + /// Convert the iterator into a graph psite. + operator psite() const; /// Read-only access to the \p i-th coordinate. mln_coord(P) operator[](unsigned i) 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. + unsigned id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + 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_graph_fwd_piter_<P>& p); + + + /*------------------------. + | p_graph_bkd_piter_<P>. | + `------------------------*/ + + /// \brief Backward iterator on point sites of a mln::p_graph<P>. + template<typename P> + class p_graph_bkd_piter_ + : public internal::point_iterator_base_< P, p_graph_bkd_piter_<P> > + { + typedef p_graph_bkd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; + + public: + // Make definitions from super class available. + enum { dim = super_::dim }; + + typedef graph_psite<P> psite; + typedef P point; + typedef mln_coord(point) coord; + + /// Construction and assignment. + /// \{ + p_graph_bkd_piter_(const p_graph<P>& pg); + p_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. const point& to_point () const; - /// Reference to the corresponding point site. const psite& to_psite () const; - - /// Convert the iterator into a point. - operator point() const; - /// Convert the iterator into a graph psite. operator psite() const; - protected: + /// Read-only access to the \p i-th coordinate. + coord operator[](unsigned i) const; + /// \} + + private: /// The p_graph this point site belongs to. - const p_graph<P>& pg_; + const p_graph<P>* pg_; /// The id of the node this psite is pointing towards. unsigned id_; /// The psite corresponding to this iterator. @@ -104,16 +185,28 @@ }; + /* 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_graph_bkd_piter_<P>& p); + # ifndef MLN_INCLUDE_ONLY + /*------------------------. + | p_graph_fwd_piter_<P>. | + `------------------------*/ + template<typename P> inline - p_graph_piter_<P>::p_graph_piter_(const p_graph<P>& pg) - : pg_(pg), + p_graph_fwd_piter_<P>::p_graph_fwd_piter_(const p_graph<P>& pg) + : pg_(&pg), // Initialize psite_ to a dummy value. - psite_(pg, pg_.npoints()), - p_() + psite_(pg, -1) { // Invalidate id_. invalidate(); @@ -121,8 +214,32 @@ template<typename P> inline + p_graph_fwd_piter_<P>::p_graph_fwd_piter_(const p_graph_fwd_piter_<P>& rhs) + : pg_(rhs.pg_), + id_(rhs.id_), + psite_(rhs.psite_), + p_(rhs.p_) + { + } + + template<typename P> + inline + p_graph_fwd_piter_<P>& + p_graph_fwd_piter_<P>::operator=(const p_graph_fwd_piter_<P>& rhs) + { + if (&rhs == this) + return *this; + pg_ = rhs.pg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + p_ = rhs.p_; + return *this; + } + + template<typename P> + inline mln_coord(P) - p_graph_piter_<P>::operator[](unsigned i) const + p_graph_fwd_piter_<P>::operator[](unsigned i) const { return p_[i]; } @@ -130,23 +247,23 @@ template<typename P> inline bool - p_graph_piter_<P>::is_valid() const + p_graph_fwd_piter_<P>::is_valid() const { - return id_ < pg_.npoints(); + return pg_ && id_ < pg_->nnodes(); } template<typename P> inline void - p_graph_piter_<P>::invalidate() + p_graph_fwd_piter_<P>::invalidate() { - id_ = pg_.npoints(); + id_ = -1; } template<typename P> inline void - p_graph_piter_<P>::start() + p_graph_fwd_piter_<P>::start() { id_ = 0; if (is_valid()) @@ -156,7 +273,7 @@ template<typename P> inline void - p_graph_piter_<P>::next_() + p_graph_fwd_piter_<P>::next_() { ++id_; if (is_valid()) @@ -166,18 +283,18 @@ template<typename P> inline void - p_graph_piter_<P>::update_() + p_graph_fwd_piter_<P>::update_() { // Update psite_. - psite_ = graph_psite<P>(pg_, id_); + psite_ = graph_psite<P>(*pg_, id_); // Update p_. - p_ = pg_.point_from_id(id_); + p_ = pg_->point_from_id(id_); } template<typename P> inline const P& - p_graph_piter_<P>::to_point() const + p_graph_fwd_piter_<P>::to_point() const { /* We don't check whether the iterator is valid before returning the value using @@ -196,7 +313,7 @@ template<typename P> inline const graph_psite<P>& - p_graph_piter_<P>::to_psite() const + p_graph_fwd_piter_<P>::to_psite() const { /* We don't check whether the iterator is valid before returning the value using @@ -214,23 +331,178 @@ template<typename P> inline - p_graph_piter_<P>::operator P() const + p_graph_fwd_piter_<P>::operator graph_psite<P>() const + { + mln_precondition(is_valid()); + return psite_; + } + + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const p_graph_fwd_piter_<P>& 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< graph_psite<P> >(p); + } + + + /*------------------------. + | p_graph_bkd_piter_<P>. | + `------------------------*/ + + template<typename P> + inline + p_graph_bkd_piter_<P>::p_graph_bkd_piter_(const p_graph<P>& pg) + : pg_(&pg), + // Initialize psite_ to a dummy value. + psite_(pg, -1) + { + // Invalidate id_. + invalidate(); + } + + template<typename P> + inline + p_graph_bkd_piter_<P>::p_graph_bkd_piter_(const p_graph_bkd_piter_<P>& rhs) + : pg_(rhs.pg_), + id_(rhs.id_), + psite_(rhs.psite_), + p_(rhs.p_) + { + } + + template<typename P> + inline + p_graph_bkd_piter_<P>& + p_graph_bkd_piter_<P>::operator=(const p_graph_bkd_piter_<P>& rhs) + { + if (&rhs == this) + return *this; + pg_ = rhs.pg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + p_ = rhs.p_; + return *this; + } + + template<typename P> + inline + mln_coord(P) + p_graph_bkd_piter_<P>::operator[](unsigned i) const + { + return p_[i]; + } + + template<typename P> + inline + bool + p_graph_bkd_piter_<P>::is_valid() const + { + return pg_ && id_ < pg_->nnodes(); + } + + template<typename P> + inline + void + p_graph_bkd_piter_<P>::invalidate() + { + id_ = -1; + } + + template<typename P> + inline + void + p_graph_bkd_piter_<P>::start() + { + id_ = pg_->nnodes() - 1; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_graph_bkd_piter_<P>::next_() + { + --id_; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_graph_bkd_piter_<P>::update_() + { + // Update psite_. + psite_ = graph_psite<P>(*pg_, id_); + // Update p_. + p_ = pg_->point_from_id(id_); + } + + template<typename P> + inline + const P& + p_graph_bkd_piter_<P>::to_point() const { + /* We don't check whether the iterator is valid before returning + the value using + mln_precondition(is_valid()); + + since this method may be called *before* the iterator is + actually initialized. This is the case for instance when this + point iterator (say, P) is used to initialize another iterator + 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 p_; } template<typename P> inline - p_graph_piter_<P>::operator graph_psite<P>() const + const graph_psite<P>& + p_graph_bkd_piter_<P>::to_psite() const + { + /* We don't check whether the iterator is valid before returning + the value using + + mln_precondition(is_valid()); + + since this method may be called *before* the iterator is + actually initialized. This is the case for instance when this + point iterator (say, P) is used to initialize another iterator + 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_graph_bkd_piter_<P>::operator graph_psite<P>() const { mln_precondition(is_valid()); return psite_; } + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const p_graph_bkd_piter_<P>& 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< graph_psite<P> >(p); + } + # endif // ! MLN_INCLUDE_ONLY } // end of mln -#endif // MLN_P_GRAPH_PITER_HH +#endif // ! MLN_CORE_P_GRAPH_PITER_HH Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1769) +++ mln/core/p_graph.hh (working copy) @@ -40,8 +40,9 @@ namespace mln { - - template<typename P> class p_graph_piter_; + /* FIXME: Contray to, e.g., p_array, the sole parameter P of p_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_graph @@ -56,16 +57,19 @@ typedef graph_psite<P> psite; /// Forward Point_Iterator associated type. - typedef p_graph_piter_<P> fwd_piter; + typedef p_graph_fwd_piter_<P> fwd_piter; /// Backward Point_Iterator associated type. - typedef p_graph_piter_<P> bkd_piter; + typedef p_graph_bkd_piter_<P> 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 vertices. 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. const box_<P>& bbox() const; @@ -96,15 +100,27 @@ graph& to_graph(); - private: + // FIXME: Should be private. + public: graph gr_; // 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? */ + private: box_<P> bb_; }; + + /// \brief Comparison between two mln::p_graph's. + /// + /// Two mln::p_graph's are considered equal if they have the + /// same address. + template <typename P> + bool + operator==(const p_graph<P>& lhs, const p_graph<P>& rhs); + + # ifndef MLN_INCLUDE_ONLY template<typename P> @@ -120,20 +136,26 @@ 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_graph<P>::npoints() const { + return nnodes(); + } + + template<typename P> + inline + std::size_t + p_graph<P>::nnodes() const + { return this->gr_.nnodes(); } template<typename P> inline std::size_t - p_graph<P>::nlines() const + p_graph<P>::nedges() const { return this->gr_.nedges(); } @@ -238,6 +260,13 @@ } + template <typename P> + bool + operator==(const p_graph<P>& lhs, const p_graph<P>& rhs) + { + return &lhs == &rhs; + } + # endif // ! MLN_INCLUDE_ONLY } // end of mln Index: mln/draw/graph.hh --- mln/draw/graph.hh (revision 1769) +++ mln/draw/graph.hh (working copy) @@ -116,10 +116,10 @@ // Draw the background. level::fill(ima, 0); // Draw the lines (edges). - for (size_t l = 0; l < gi.domain().nlines(); ++l) + for (size_t l = 0; l < gi.domain().nedges(); ++l) line (exact(ima), gi.node1(l), gi.node2(l), link_v); // Draw the points (nodes). - for (size_t p = 0; p < gi.domain().npoints(); ++p) + for (size_t p = 0; p < gi.domain().nnodes(); ++p) exact(ima)(gi.domain().point_from_id(p)) = gi.node_values()[p]; }