* mln/topo/adj_lower_dim_connected_n_face_iter.hh, * mln/topo/adj_higher_dim_connected_n_face_iter.hh: New. Include these headers... * mln/topo/complex.hh: ...here. * tests/topo/complex.cc: Exercise these iterators. --- milena/ChangeLog | 11 + .../topo/adj_higher_dim_connected_n_face_iter.hh | 270 ++++++++++++++++++++ .../topo/adj_lower_dim_connected_n_face_iter.hh | 270 ++++++++++++++++++++ milena/mln/topo/complex.hh | 2 + milena/tests/topo/complex.cc | 66 +++-- 5 files changed, 595 insertions(+), 24 deletions(-) create mode 100644 milena/mln/topo/adj_higher_dim_connected_n_face_iter.hh create mode 100644 milena/mln/topo/adj_lower_dim_connected_n_face_iter.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index 583c73e..ee844c1 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,16 @@ 2008-10-05 Roland Levillain <roland@lrde.epita.fr> + Add relative iterators on faces sharing lower/higher-dimension faces. + + * mln/topo/adj_lower_dim_connected_n_face_iter.hh, + * mln/topo/adj_higher_dim_connected_n_face_iter.hh: + New. + Include these headers... + * mln/topo/complex.hh: ...here. + * tests/topo/complex.cc: Exercise these iterators. + +2008-10-05 Roland Levillain <roland@lrde.epita.fr> + Add operator!= on face handles. * mln/topo/face.hh diff --git a/milena/mln/topo/adj_higher_dim_connected_n_face_iter.hh b/milena/mln/topo/adj_higher_dim_connected_n_face_iter.hh new file mode 100644 index 0000000..ad6dbe9 --- /dev/null +++ b/milena/mln/topo/adj_higher_dim_connected_n_face_iter.hh @@ -0,0 +1,270 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_TOPO_ADJ_HIGHER_DIM_CONNECTED_N_FACE_ITER_HH +# define MLN_TOPO_ADJ_HIGHER_DIM_CONNECTED_N_FACE_ITER_HH + +/// \file mln/topo/adj_higher_dim_connected_n_face_iter.hh + +/// \brief Definition of forward and backward iterators on all the +/// n-faces sharing an adjacent (n+1)-face with a (reference) n-face +/// in a complex. + +# include <set> + +# include <mln/topo/internal/complex_relative_iterator_base.hh> +# include <mln/topo/face.hh> + + +namespace mln +{ + + namespace topo + { + + // Forward declarations. + template <unsigned D> class complex; + namespace internal + { + template <unsigned D> class adj_higher_dim_connected_n_face_iterator; + } + + + /*---------------------------------------------------. + | topo::adj_higher_dim_connected_n_face_fwd_iter<D>. | + `---------------------------------------------------*/ + + /// \brief Forward iterator on all the n-faces sharing an adjacent + /// (n+1)-face with a (reference) n-face of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_higher_dim_connected_n_face_fwd_iter + : public internal::forward_complex_relative_iterator_base< face<D>, + adj_higher_dim_connected_n_face_fwd_iter<D> >, + private internal::adj_higher_dim_connected_n_face_iterator<D> + { + private: + typedef adj_higher_dim_connected_n_face_fwd_iter<D> self_; + typedef internal::forward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + /// Construction. + /// \{ + adj_higher_dim_connected_n_face_fwd_iter(); + template <typename Fref> + adj_higher_dim_connected_n_face_fwd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + /*---------------------------------------------------. + | topo::adj_higher_dim_connected_n_face_bkd_iter<D>. | + `---------------------------------------------------*/ + + /// \brief Backward iterator on all the n-faces sharing an adjacent + /// (n+1)-face with a (reference) n-face of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_higher_dim_connected_n_face_bkd_iter + : public internal::backward_complex_relative_iterator_base< face<D>, + adj_higher_dim_connected_n_face_bkd_iter<D> >, + private internal::adj_higher_dim_connected_n_face_iterator<D> + { + private: + typedef adj_higher_dim_connected_n_face_bkd_iter<D> self_; + typedef internal::backward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + /// Construction. + /// \{ + adj_higher_dim_connected_n_face_bkd_iter(); + template <typename Fref> + adj_higher_dim_connected_n_face_bkd_iter(const Fref& f_ref); + /// \} + + /// \brief Compute the set of faces adjacent to the reference face. + /// + /// The computation is delegated to + /// mln::topo::internal::adj_higher_dim_connected_n_face_iterator. + void update_adj_faces_(); + }; + + + /*-------------------------------------------------------------. + | topo::internal::adj_higher_dim_connected_n_face_iterator<D>. | + `-------------------------------------------------------------*/ + + namespace internal + { + + template <unsigned D> + class adj_higher_dim_connected_n_face_iterator + { + protected: + /// The actual implementation of the computation of the set of + /// faces adjacent to the reference face. + void update_adj_faces__(const face<D>& center, + std::vector< face<D> >& adj_faces); + }; + + } // end of namespace mln::topo::internal + + + +# ifndef MLN_INCLUDE_ONLY + + /*---------------------------------------------------. + | topo::adj_higher_dim_connected_n_face_fwd_iter<D>. | + `---------------------------------------------------*/ + + template <unsigned D> + inline + adj_higher_dim_connected_n_face_fwd_iter<D>::adj_higher_dim_connected_n_face_fwd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_higher_dim_connected_n_face_fwd_iter<D>::adj_higher_dim_connected_n_face_fwd_iter(const Fref& f_ref) + : super_(f_ref) + { + } + + /* FIXME: Most of this code is shared by + adj_higher_dim_connected_n_face_{fwd,bkd}_iter<D> and + adj_higher_dim_connected_n_face_{fwd,bkd}_iter<D>). Find a way + to factor this, maybe through a common (implementation) base + class. */ + template <unsigned D> + inline + void + adj_higher_dim_connected_n_face_fwd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + // Delegate computation to base class. + this->update_adj_faces__(*this->c_, this->adj_faces_); + } + + + /*---------------------------------------------------. + | topo::adj_higher_dim_connected_n_face_bkd_iter<D>. | + `---------------------------------------------------*/ + + template <unsigned D> + inline + adj_higher_dim_connected_n_face_bkd_iter<D>::adj_higher_dim_connected_n_face_bkd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_higher_dim_connected_n_face_bkd_iter<D>::adj_higher_dim_connected_n_face_bkd_iter(const Fref& f_ref) + : super_(f_ref) + { + } + + template <unsigned D> + inline + void + adj_higher_dim_connected_n_face_bkd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + // Delegate computation to base class. + this->update_adj_faces__(*this->c_, this->adj_faces_); + } + + + /*-------------------------------------------------------------. + | topo::internal::adj_higher_dim_connected_n_face_iterator<D>. | + `-------------------------------------------------------------*/ + + namespace internal + { + + /* FIXME: Factor + topo::internal::adj_lower_dim_connected_n_face_iterator<D> and + topo::internal::adj_higher_dim_connected_n_face_iterator<D>. */ + + template <unsigned D> + inline + void + adj_higher_dim_connected_n_face_iterator<D>::update_adj_faces__(const face<D>& center, + std::vector< face<D> >& adj_faces) + { + // Reset the result container. + adj_faces.clear(); + + /* A set of faces containing the same values as ADJ_FACES, used + to quickly check whether a candidate face has already been + added to the pool of adjacent faces. We use an std::set + because the lookup is cheaper (O(log(n)) vs O(n) for a + vector, where n is the size of the containers. */ + std::set< face<D> > faces_set; + typedef std::vector< face<D> > faces_t; + + // The set of (n+1)-faces adjacent to CENTER. + faces_t shared_higher_faces = center.higher_dim_adj_faces(); + for (typename faces_t::const_iterator slf = shared_higher_faces.begin(); + slf != shared_higher_faces.end(); ++slf) + { + /* The n-faces sharing an adjacent (n+1)-face with CENTER. + Note that this set contains CENTER itself. */ + faces_t adj_n_faces = slf->lower_dim_adj_faces(); + for (typename faces_t::const_iterator af = adj_n_faces.begin(); + af != adj_n_faces.end(); ++af) + { + /* Ensure that 1. we are not adding CENTER to the result; + and 2. that we are not adding an already added + processed face. */ + if (*af != center && + faces_set.find(*af) == faces_set.end()) + { + adj_faces.push_back(*af); + faces_set.insert(*af); + } + } + } + } + + } // end of namespace mln::topo::internal + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_ADJ_HIGHER_DIM_CONNECTED_N_FACE_ITER_HH diff --git a/milena/mln/topo/adj_lower_dim_connected_n_face_iter.hh b/milena/mln/topo/adj_lower_dim_connected_n_face_iter.hh new file mode 100644 index 0000000..7a11009 --- /dev/null +++ b/milena/mln/topo/adj_lower_dim_connected_n_face_iter.hh @@ -0,0 +1,270 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_TOPO_ADJ_LOWER_DIM_CONNECTED_N_FACE_ITER_HH +# define MLN_TOPO_ADJ_LOWER_DIM_CONNECTED_N_FACE_ITER_HH + +/// \file mln/topo/adj_lower_dim_connected_n_face_iter.hh + +/// \brief Definition of forward and backward iterators on all the +/// n-faces sharing an adjacent (n-1)-face with a (reference) n-face +/// in a complex. + +# include <set> + +# include <mln/topo/internal/complex_relative_iterator_base.hh> +# include <mln/topo/face.hh> + + +namespace mln +{ + + namespace topo + { + + // Forward declarations. + template <unsigned D> class complex; + namespace internal + { + template <unsigned D> class adj_lower_dim_connected_n_face_iterator; + } + + + /*---------------------------------------------------. + | topo::adj_lower_dim_connected_n_face_fwd_iter<D>. | + `---------------------------------------------------*/ + + /// \brief Forward iterator on all the n-faces sharing an adjacent + /// (n-1)-face with a (reference) n-face of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_lower_dim_connected_n_face_fwd_iter + : public internal::forward_complex_relative_iterator_base< face<D>, + adj_lower_dim_connected_n_face_fwd_iter<D> >, + private internal::adj_lower_dim_connected_n_face_iterator<D> + { + private: + typedef adj_lower_dim_connected_n_face_fwd_iter<D> self_; + typedef internal::forward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + /// Construction. + /// \{ + adj_lower_dim_connected_n_face_fwd_iter(); + template <typename Fref> + adj_lower_dim_connected_n_face_fwd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + /*---------------------------------------------------. + | topo::adj_lower_dim_connected_n_face_bkd_iter<D>. | + `---------------------------------------------------*/ + + /// \brief Backward iterator on all the n-faces sharing an adjacent + /// (n-1)-face with a (reference) n-face of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_lower_dim_connected_n_face_bkd_iter + : public internal::backward_complex_relative_iterator_base< face<D>, + adj_lower_dim_connected_n_face_bkd_iter<D> >, + private internal::adj_lower_dim_connected_n_face_iterator<D> + { + private: + typedef adj_lower_dim_connected_n_face_bkd_iter<D> self_; + typedef internal::backward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + /// Construction. + /// \{ + adj_lower_dim_connected_n_face_bkd_iter(); + template <typename Fref> + adj_lower_dim_connected_n_face_bkd_iter(const Fref& f_ref); + /// \} + + /// \brief Compute the set of faces adjacent to the reference face. + /// + /// The computation is delegated to + /// mln::topo::internal::adj_lower_dim_connected_n_face_iterator. + void update_adj_faces_(); + }; + + + /*-------------------------------------------------------------. + | topo::internal::adj_lower_dim_connected_n_face_iterator<D>. | + `-------------------------------------------------------------*/ + + namespace internal + { + + template <unsigned D> + class adj_lower_dim_connected_n_face_iterator + { + protected: + /// The actual implementation of the computation of the set of + /// faces adjacent to the reference face. + void update_adj_faces__(const face<D>& center, + std::vector< face<D> >& adj_faces); + }; + + } // end of namespace mln::topo::internal + + + +# ifndef MLN_INCLUDE_ONLY + + /*---------------------------------------------------. + | topo::adj_lower_dim_connected_n_face_fwd_iter<D>. | + `---------------------------------------------------*/ + + template <unsigned D> + inline + adj_lower_dim_connected_n_face_fwd_iter<D>::adj_lower_dim_connected_n_face_fwd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_lower_dim_connected_n_face_fwd_iter<D>::adj_lower_dim_connected_n_face_fwd_iter(const Fref& f_ref) + : super_(f_ref) + { + } + + /* FIXME: Most of this code is shared by + adj_lower_dim_connected_n_face_{fwd,bkd}_iter<D> and + adj_higher_dim_connected_n_face_{fwd,bkd}_iter<D>). Find a way + to factor this, maybe through a common (implementation) base + class. */ + template <unsigned D> + inline + void + adj_lower_dim_connected_n_face_fwd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + // Delegate computation to base class. + this->update_adj_faces__(*this->c_, this->adj_faces_); + } + + + /*---------------------------------------------------. + | topo::adj_lower_dim_connected_n_face_bkd_iter<D>. | + `---------------------------------------------------*/ + + template <unsigned D> + inline + adj_lower_dim_connected_n_face_bkd_iter<D>::adj_lower_dim_connected_n_face_bkd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_lower_dim_connected_n_face_bkd_iter<D>::adj_lower_dim_connected_n_face_bkd_iter(const Fref& f_ref) + : super_(f_ref) + { + } + + template <unsigned D> + inline + void + adj_lower_dim_connected_n_face_bkd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + // Delegate computation to base class. + this->update_adj_faces__(*this->c_, this->adj_faces_); + } + + + /*-------------------------------------------------------------. + | topo::internal::adj_lower_dim_connected_n_face_iterator<D>. | + `-------------------------------------------------------------*/ + + namespace internal + { + + /* FIXME: Factor + topo::internal::adj_lower_dim_connected_n_face_iterator<D> and + topo::internal::adj_higher_dim_connected_n_face_iterator<D>. */ + + template <unsigned D> + inline + void + adj_lower_dim_connected_n_face_iterator<D>::update_adj_faces__(const face<D>& center, + std::vector< face<D> >& adj_faces) + { + // Reset the result container. + adj_faces.clear(); + + /* A set of faces containing the same values as ADJ_FACES, used + to quickly check whether a candidate face has already been + added to the pool of adjacent faces. We use an std::set + because the lookup is cheaper (O(log(n)) vs O(n) for a + vector, where n is the size of the containers. */ + std::set< face<D> > faces_set; + typedef std::vector< face<D> > faces_t; + + // The set of (n-1)-faces adjacent to CENTER. + faces_t shared_lower_faces = center.lower_dim_adj_faces(); + for (typename faces_t::const_iterator slf = shared_lower_faces.begin(); + slf != shared_lower_faces.end(); ++slf) + { + /* The n-faces sharing an adjacent (n-1)-face with CENTER. + Note that this set contains CENTER itself. */ + faces_t adj_n_faces = slf->higher_dim_adj_faces(); + for (typename faces_t::const_iterator af = adj_n_faces.begin(); + af != adj_n_faces.end(); ++af) + { + /* Ensure that 1. we are not adding CENTER to the result; + and 2. that we are not adding an already added + processed face. */ + if (*af != center && + faces_set.find(*af) == faces_set.end()) + { + adj_faces.push_back(*af); + faces_set.insert(*af); + } + } + } + } + + } // end of namespace mln::topo::internal + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_ADJ_LOWER_DIM_CONNECTED_N_FACE_ITER_HH diff --git a/milena/mln/topo/complex.hh b/milena/mln/topo/complex.hh index 1291ca7..06c714e 100644 --- a/milena/mln/topo/complex.hh +++ b/milena/mln/topo/complex.hh @@ -59,6 +59,8 @@ # include <mln/topo/adj_lower_face_iter.hh> # include <mln/topo/adj_higher_face_iter.hh> # include <mln/topo/adj_lower_higher_face_iter.hh> +# include <mln/topo/adj_lower_dim_connected_n_face_iter.hh> +# include <mln/topo/adj_higher_dim_connected_n_face_iter.hh> namespace mln diff --git a/milena/tests/topo/complex.cc b/milena/tests/topo/complex.cc index 92d0398..249b743 100644 --- a/milena/tests/topo/complex.cc +++ b/milena/tests/topo/complex.cc @@ -211,10 +211,12 @@ int main() milena/tests/core/complex_image.cc) and ticket #162 (https://trac.lrde.org/olena/ticket/162) */ - /* Iterate on the the set of (n-1)- and/or (n+1)-faces adjacent to - the faces of C. + // ------------------------------------------------------------ // + // Iterate on the the set of (n-1)- and/or (n+1)-faces adjacent // + // to the faces of C. // + // ------------------------------------------------------------ // - Note: this can be solved with iterators where the dimension can + /* Note: this can be solved with iterators where the dimension can be either static or dynamic. For the moment, our iterators are dynamic w.r.t. the dimensions of the faces (both the reference face and the iterated ones). @@ -259,31 +261,44 @@ int main() } std::cout << std::endl; - /* But first, we need to clarify (existing) names. The one listed - in https://trac.lrde.org/olena/wiki/Olena/ComplexBasedImages - are OK. - Next, write these: + // ------------------------------------------------------- // + // Iterators on the the set of n-faces sharing an adjacent // + // (n-1)-face or (n+1)-face with f, n being dynamic. // + // ------------------------------------------------------- // + + // For each face F of C, iterate on the the set of n-faces sharing + // adjacent (n-1)-faces with F. + topo::adj_lower_dim_connected_n_face_fwd_iter<D> fwd_aldcf(fwd_f); + topo::adj_lower_dim_connected_n_face_bkd_iter<D> bkd_aldcf(fwd_f); + for_all(fwd_f) + { + std::cout << "Lower-dim-connected faces adjacent to " << fwd_f + << ": " << std::endl; + for_all_2(fwd_aldcf, bkd_aldcf) + std::cout << " " << fwd_aldcf << '\t' << bkd_aldcf << std::endl; + } + std::cout << std::endl; + + // For each face F of C, iterate on the the set of n-faces sharing + // adjacent (n+1)-faces with F. + topo::adj_higher_dim_connected_n_face_fwd_iter<D> fwd_ahdcf(fwd_f); + topo::adj_higher_dim_connected_n_face_bkd_iter<D> bkd_ahdcf(fwd_f); + for_all(fwd_f) + { + std::cout << "Higher-dim-connected faces adjacent to " << fwd_f + << ": " << std::endl; + for_all_2(fwd_ahdcf, bkd_ahdcf) + std::cout << " " << fwd_ahdcf << '\t' << bkd_ahdcf << std::endl; + } + std::cout << std::endl; + + + /* Next, write these: ----------------------------------------------------------------- Name Definition ----------------------------------------------------------------- - adj_lower_dim_connected_n_face_fwd_iter<D>(c, f) - adj_lower_dim_connected_n_face_bkd_iter<D>(c, f) - (FIXME: These names are admittedly too long.) - | Iterators on the the set of - | n-faces sharing an adjacent - | (n-1)-face with f, n being - | dynamic - - adj_higher_dim_connected_n_face_fwd_iter<D>(c, f) - adj_higher_dim_connected_n_face_bkd_iter<D>(c, f) - (FIXME: These names are admittedly too long.) - | Iterators on the the set of - | n-faces sharing an adjacent - | (n+1)-face with f, n being - | dynamic - cell_fwd_iter<D>(c, f) | Iterators on the set of the cell_bkd_iter<D>(c, f) | faces in the « cell » | including p, i.e. the set of @@ -324,7 +339,9 @@ int main() faces_fwd_iter_<N, D> static, acting as proxies of face<D>'s. ----------------------------------------------------------------- - */ + + See also https://trac.lrde.org/olena/wiki/Olena/ComplexBasedImages */ + /*------------------. | Other iterators. | @@ -333,6 +350,7 @@ int main() // For each face, iterate on itself. (This iterator is not // interesting as-is, but is useful when combined with others, // e.g. in topo::centered_iter_adapter). + std::cout << "Center-only iterator:" << std::endl; topo::center_only_iter<D> center(fwd_f); for_all(fwd_f) for_all(center) -- 1.6.0.1