[Olena-patches] 1771: Add a backward iterator on p_line_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_line_graph. * mln/core/p_line_graph_piter.hh (p_line_graph_piter_<P>): Rename as... (p_line_graph_fwd_piter_<P>): ...this. (p_line_graph_fwd_piter_<P>::self_): Adjust. (p_line_graph_fwd_piter_<P>::point): Set typedef to P. (p_line_graph_fwd_piter_<P>::coord): Set typedef to mln_coord(point). (p_line_graph_fwd_piter_(const p_line_graph_fwd_piter_&)) (operator= (const p_line_graph_fwd_piter_&)): New. (p_line_graph_fwd_piter_<P>::operator point): Remove. (p_line_graph_fwd_piter_<P>::operator psite): New. (p_line_graph_fwd_piter_<P>::plg_): Change the type of this member from const p_line_graph<P>& to const p_line_graph<P>*. (p_line_graph_fwd_piter_(const p_line_graph<P>&)) (p_line_graph_fwd_piter_<P>::is_valid) (p_line_graph_fwd_piter_<P>::invalidate): Adjust. (p_line_graph_fwd_piter_<P>::update_): Don't update member p_. (p_line_graph_bkd_piter_<P>): New. (operator<<(std::ostream&, const p_line_graph_fwd_piter_<P>&)) (operator<<(std::ostream&, const p_line_graph_bkd_piter_<P>&)) * mln/core/p_line_graph.hh (mln::box_< point_pair<P> >): Remove this specialization. (mln::p_line_graph<P>::point): Remove typedef. (mln::p_line_graph<P>::fwd_piter): Adjust to the new name of mln::p_line_graph_fwd_piter_<P>. (mln::p_line_graph<P>::bkd_piter): New typedef. (mln::p_line_graph<P>::nlines): Rename as... (mln::p_line_graph<P>::nedges): ..this. (mln::p_line_graph<P>::npoints): Rename as... (mln::p_line_graph<P>::nnodes): ...this. (mln::p_line_graph<P>::npoints): New. s/box_<point>/box_<P>/. (mln::p_line_graph<P>::p_line_graph (util::graph<P>&)): Fix the initialization of bb_. (operator==(const p_line_graph<P>&, const p_line_graph<P>&)): New. p_line_graph.hh | 87 ++++++------ p_line_graph_piter.hh | 351 +++++++++++++++++++++++++++++++++++++++++--------- 2 files changed, 340 insertions(+), 98 deletions(-) Index: mln/core/p_line_graph_piter.hh --- mln/core/p_line_graph_piter.hh (revision 1770) +++ mln/core/p_line_graph_piter.hh (working copy) @@ -31,12 +31,9 @@ # include <mln/core/internal/point_iterator_base.hh> # include <mln/core/p_line_graph.hh> # include <mln/core/line_graph_psite.hh> -# include <mln/core/point_pair.hh> -/*! \file mln/core/p_line_graph_piter.hh - * - * \brief Definition of point iterator on graph-based point set. - */ +/// \file mln/core/p_line_graph_piter.hh +/// \brief Definition of point iterator on line graph-based point set. namespace mln { @@ -45,67 +42,156 @@ template<typename P> class line_graph_psite; - // FIXME: Why `p_line_graph_piter_' and not `p_line_graph_piter' - // (without `_')? + /*-----------------------------. + | p_line_graph_fwd_piter_<P>. | + `-----------------------------*/ + /// \brief Forward iterator on point sites of a mln::p_line_graph<P>. template<typename P> - class p_line_graph_piter_ - : public internal::point_iterator_base_< P, p_line_graph_piter_<P> > + class p_line_graph_fwd_piter_ + : public internal::point_iterator_base_< P, p_line_graph_fwd_piter_<P> > { - typedef p_line_graph_piter_<P> self_; + typedef p_line_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 line_graph_psite<P> psite; - typedef point_pair<P> point; - typedef mln_coord(point_pair<P>) coord; - p_line_graph_piter_(const p_line_graph<P>& plg); + typedef line_graph_psite<P> psite; + typedef P point; + typedef mln_coord(point) coord; - /// Read-only access to the \p i-th coordinate. - mln_coord(point) operator[](unsigned i) const; + /// Construction and assignment. + /// \{ + p_line_graph_fwd_piter_(const p_line_graph<P>& plg); + p_line_graph_fwd_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. + // FIXME: Dummy. 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 p_line_graph this point site belongs to. + const p_line_graph<P>* plg_; + /// The id of the edge this psite is pointing towards. + util::edge_id id_; + /// The psite corresponding to this iterator. + psite psite_; + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ + 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_line_graph_fwd_piter_<P>& p); - /// Convert the iterator into a point. - operator point() const; - /// Convert the iterator into a graph psite. + /*-----------------------------. + | p_line_graph_bkd_piter_<P>. | + `-----------------------------*/ + + /// \brief Backward iterator on point sites of a mln::p_line_graph<P>. + template<typename P> + class p_line_graph_bkd_piter_ + : public internal::point_iterator_base_< P, p_line_graph_bkd_piter_<P> > + { + typedef p_line_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 line_graph_psite<P> psite; + typedef P point; + typedef mln_coord(point) coord; + + /// Construction and assignment. + /// \{ + p_line_graph_bkd_piter_(const p_line_graph<P>& plg); + p_line_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. + // FIXME: Dummy. + 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. + mln_coord(point) operator[](unsigned i) const; + /// \} + protected: /// The p_line_graph this point site belongs to. - const p_line_graph<P>& plg_; + const p_line_graph<P>* plg_; /// The id of the edge this psite is pointing towards. util::edge_id id_; /// The psite corresponding to this iterator. psite psite_; - /// The psite corresponding to this iterator. + /// The point corresponding to this iterator. + /* FIXME: Dummy value. To be removed as soon as the conversion + from psite to point is no longer mandatory. */ 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 @@ -113,18 +199,21 @@ template <typename P> inline std::ostream& - operator<<(std::ostream& ostr, const p_line_graph_piter_<P>& p); + operator<<(std::ostream& ostr, const p_line_graph_bkd_piter_<P>& p); # ifndef MLN_INCLUDE_ONLY + /*-----------------------------. + | p_line_graph_fwd_piter_<P>. | + `-----------------------------*/ + template<typename P> inline - p_line_graph_piter_<P>::p_line_graph_piter_(const p_line_graph<P>& plg) - : plg_(plg), + p_line_graph_fwd_piter_<P>::p_line_graph_fwd_piter_(const p_line_graph<P>& plg) + : plg_(&plg), // Initialize psite_ to a dummy value. - psite_(plg, plg_.nlines()), - p_() + psite_(plg, -1) { // Invalidate id_. invalidate(); @@ -132,32 +221,55 @@ template<typename P> inline - mln_coord(point_pair<P>) - p_line_graph_piter_<P>::operator[](unsigned i) const + p_line_graph_fwd_piter_<P>::p_line_graph_fwd_piter_(const p_line_graph_fwd_piter_<P>& rhs) + : plg_(rhs.plg_), + id_(rhs.id_), + psite_(rhs.psite_) { + } + + template<typename P> + inline + p_line_graph_fwd_piter_<P>& + p_line_graph_fwd_piter_<P>::operator=(const p_line_graph_fwd_piter_<P>& rhs) + { + if (&rhs == this) + return *this; + plg_ = rhs.plg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + return *this; + } + + template<typename P> + inline + mln_coord(P) + p_line_graph_fwd_piter_<P>::operator[](unsigned i) const + { + // Dummy value. return p_[i]; } template<typename P> inline bool - p_line_graph_piter_<P>::is_valid() const + p_line_graph_fwd_piter_<P>::is_valid() const { - return id_ < plg_.nlines(); + return plg_ && id_ < plg_->nedges(); } template<typename P> inline void - p_line_graph_piter_<P>::invalidate() + p_line_graph_fwd_piter_<P>::invalidate() { - id_ = plg_.nlines(); + id_ = -1; } template<typename P> inline void - p_line_graph_piter_<P>::start() + p_line_graph_fwd_piter_<P>::start() { id_ = 0; if (is_valid()) @@ -167,7 +279,7 @@ template<typename P> inline void - p_line_graph_piter_<P>::next_() + p_line_graph_fwd_piter_<P>::next_() { ++id_; if (is_valid()) @@ -177,20 +289,25 @@ template<typename P> inline void - p_line_graph_piter_<P>::update_() + p_line_graph_fwd_piter_<P>::update_() { // Update psite_. - psite_ = line_graph_psite<P>(plg_, id_); - // Update p_. - // FIXME: These repeated assignments might be very costly. - p_ = point(plg_.gr_.node_data(plg_.gr_.edge(id_).n1()), - plg_.gr_.node_data(plg_.gr_.edge(id_).n2())); + psite_ = line_graph_psite<P>(*plg_, id_); + } + + template<typename P> + inline + const P& + p_line_graph_fwd_piter_<P>::to_point() const + { + // Dummy value. + return p_; } template<typename P> inline - const point_pair<P>& - p_line_graph_piter_<P>::to_point() const + const line_graph_psite<P>& + p_line_graph_fwd_piter_<P>::to_psite() const { /* We don't check whether the iterator is valid before returning the value using @@ -203,13 +320,135 @@ 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_line_graph_fwd_piter_<P>::operator line_graph_psite<P>() const + { + mln_precondition(is_valid()); + return psite_; + } + + + template <typename P> + inline + std::ostream& + operator<<(std::ostream& ostr, const p_line_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< line_graph_psite<P> >(p); + } + + + /*-----------------------------. + | p_line_graph_bkd_piter_<P>. | + `-----------------------------*/ + + template<typename P> + inline + p_line_graph_bkd_piter_<P>::p_line_graph_bkd_piter_(const p_line_graph<P>& plg) + : plg_(&plg), + // Initialize psite_ to a dummy value. + psite_(plg, -1) + { + // Invalidate id_. + invalidate(); + } + + template<typename P> + inline + p_line_graph_bkd_piter_<P>::p_line_graph_bkd_piter_(const p_line_graph_bkd_piter_<P>& rhs) + : plg_(rhs.plg_), + id_(rhs.id_), + psite_(rhs.psite_) + { + } + + template<typename P> + inline + p_line_graph_bkd_piter_<P>& + p_line_graph_bkd_piter_<P>::operator=(const p_line_graph_bkd_piter_<P>& rhs) + { + if (&rhs == this) + return *this; + plg_ = rhs.plg_; + id_ = rhs.id_; + psite_ = rhs.psite_; + // FIXME: Probably superfluous. +// update_(); + return *this; + } + + template<typename P> + inline + mln_coord(P) + p_line_graph_bkd_piter_<P>::operator[](unsigned i) const + { + // Dummy value. + return p_[i]; + } + + template<typename P> + inline + bool + p_line_graph_bkd_piter_<P>::is_valid() const + { + return plg_ && id_ < plg_->nedges(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_<P>::invalidate() + { + id_ = -1; + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_<P>::start() + { + id_ = plg_->nedges() - 1; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_<P>::next_() + { + --id_; + if (is_valid()) + update_(); + } + + template<typename P> + inline + void + p_line_graph_bkd_piter_<P>::update_() + { + // Update psite_. + psite_ = line_graph_psite<P>(*plg_, id_); + } + + template<typename P> + inline + const P& + p_line_graph_bkd_piter_<P>::to_point() const + { + // Dummy value. return p_; } template<typename P> inline const line_graph_psite<P>& - p_line_graph_piter_<P>::to_psite() const + p_line_graph_bkd_piter_<P>::to_psite() const { /* We don't check whether the iterator is valid before returning the value using @@ -227,15 +466,7 @@ template<typename P> inline - p_line_graph_piter_<P>::operator point_pair<P>() const - { - mln_precondition(is_valid()); - return p_; - } - - template<typename P> - inline - p_line_graph_piter_<P>::operator line_graph_psite<P>() const + p_line_graph_bkd_piter_<P>::operator line_graph_psite<P>() const { mln_precondition(is_valid()); return psite_; @@ -245,9 +476,9 @@ template <typename P> inline std::ostream& - operator<<(std::ostream& ostr, const p_line_graph_piter_<P>& p) + operator<<(std::ostream& ostr, const p_line_graph_bkd_piter_<P>& p) { - return ostr << p.to_point(); + return ostr << static_cast< line_graph_psite<P> >(p); } # endif // ! MLN_INCLUDE_ONLY @@ -255,4 +486,4 @@ } // end of mln -#endif // MLN_P_LINE_GRAPH_PITER_HH +#endif // ! MLN_CORE_P_LINE_GRAPH_PITER_HH Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1770) +++ mln/core/p_line_graph.hh (working copy) @@ -34,7 +34,6 @@ # include <mln/util/graph.hh> # include <mln/core/line_graph_psite.hh> # include <mln/core/p_line_graph_piter.hh> -# include <mln/core/point_pair.hh> /* FIXME: This class shares a lot with p_graph. Factor as much as possible. */ @@ -45,17 +44,9 @@ namespace mln { - - // FIXME: Dummy specialization, only to have this first version of - // our code compile. - template <typename P> - struct box_< point_pair<P> > : public Box< box_<P> > - { - // Nothing. - }; - - - template<typename P> class p_line_graph_piter_; + /* FIXME: Contray to, e.g., p_array, the sole parameter P of + p_line_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_line_graph @@ -69,24 +60,24 @@ /// Point_Site associated type. typedef line_graph_psite<P> psite; - /// Point associated type. - typedef point_pair<P> point; - /// Forward Point_Iterator associated type. - typedef p_line_graph_piter_<P> fwd_piter; + typedef p_line_graph_fwd_piter_<P> fwd_piter; /// Backward Point_Iterator associated type. - typedef p_line_graph_piter_<P> bkd_piter; + typedef p_line_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 edges, since this is a point set based on a line + /// graph. 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. - // FIXME: Dummy. - const box_<point>& bbox() const; + const box_<P>& bbox() const; bool has(const psite& p) const; @@ -95,12 +86,20 @@ // 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? In particular, an image whose sites - are actually /pairs of points/! */ - // FIXME: Dummy. - box_<point> bb_; + type have a bounding box? */ + box_<P> bb_; }; + + /// \brief Comparison between two mln::p_line_graph's. + /// + /// Two mln::p_line_graph's are considered equal if they have the + /// same address. + template <typename P> + bool + operator==(const p_line_graph<P>& lhs, const p_line_graph<P>& rhs); + + # ifndef MLN_INCLUDE_ONLY template<typename P> @@ -108,37 +107,41 @@ p_line_graph<P>::p_line_graph (util::graph<P>& gr) : gr_ (gr) { - // FIXME: Dummy initialization of bb_. -// // FIXME: Warning: if the underlying graph is updated later, this -// // won't be taken into account by this p_line_graph! -// accu::bbox<point> a; -// for (util::edge_id e = 0; e < nlines(); ++e) -// a.take(point(gr_.node_data(gr_.edge(e).n1()), -// gr_.node_data(gr_.edge(e).n2()))); -// bb_ = a.to_result(); + // FIXME: Warning: if the underlying graph is updated later, this + // won't be taken into account by this p_line_graph! + accu::bbox<P> a; + for (unsigned i = 0; i < nnodes(); ++i) + a.take(gr_.node_data(i)); + 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_line_graph<P>::npoints() const { + return nedges(); + } + + template<typename P> + inline + std::size_t + p_line_graph<P>::nnodes() const + { return this->gr_.nnodes(); } template<typename P> inline std::size_t - p_line_graph<P>::nlines() const + p_line_graph<P>::nedges() const { return this->gr_.nedges(); } template<typename P> inline - const box_< point_pair<P> >& + const box_<P>& p_line_graph<P>::bbox() const { return bb_; @@ -156,6 +159,14 @@ (p.id() < gr_.nedges()); } + + template <typename P> + bool + operator==(const p_line_graph<P>& lhs, const p_line_graph<P>& rhs) + { + return &lhs == &rhs; + } + # endif // ! MLN_INCLUDE_ONLY } // end of mln