[Olena-patches] 2113: Add a first implementation of general complexes.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Complex-based images will follow... soon. Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Add a first implementation of general complexes. * mln/core/complex.hh, mln/core/face.hh: New. * tests/core/complex.cc: New test. * tests/core/Makefile.am (check_PROGRAMS): Add complex. (complex_SOURCES): New. Set to complex.cc. mln/core/complex.hh | 347 +++++++++++++++++++++++++++++++++++++++++++++++++ mln/core/face.hh | 287 ++++++++++++++++++++++++++++++++++++++++ tests/core/Makefile.am | 2 tests/core/complex.cc | 75 ++++++++++ 4 files changed, 711 insertions(+) Index: mln/core/complex.hh --- mln/core/complex.hh (revision 0) +++ mln/core/complex.hh (revision 0) @@ -0,0 +1,347 @@ +// 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_CORE_COMPLEX_HH +# define MLN_CORE_COMPLEX_HH + +/// \file mln/core/complex.hh +/// \brief Structures for general complexes. +/// +/// A complexes defines a topological space which can be used as a +/// support for an image (i.e., as site sets). +/// +/// FIXME: More. + +# include <iosfwd> + +# include <mln/metal/bool.hh> + +# include <mln/core/face.hh> + + +namespace mln +{ + + // Forward declaration. + namespace internal + { + template <unsigned N, unsigned D> + struct faces_set_mixin; + } + + + /*----------. + | Complex. | + `----------*/ + + /// \brief General complex of dimension \p D. + template <unsigned D> + class complex : private internal::faces_set_mixin<D, D> + { + public: + /// Complex construction. + /// \{ + + /// \brief Add a 0-face to the complex. + face_handle<0u, D> add_face(); + + /// \brief Add a \p (N+1)-face to the complex (with \p N >= 0). + /// + /// \param adjacent_faces The (\p N-1)-faces adjacent to the new + /// \p N-face. + template <unsigned N> + face_handle<N + 1, D> add_face(const faces_set<N, D>& adjacent_faces); + /// \} + + /// Pretty-printing. + /// \{ + /// Print the complex. + void print(std::ostream& ostr) const; + /// Print the faces of dimension \p N. + template <unsigned N> + void print_faces(std::ostream& ostr) const; + /// \} + + private: + /// Accessors. + /// \{ + template <unsigned N, unsigned D_> friend class face_handle; + + template <unsigned N> + face<N, D>& face_(unsigned face_id); + + template <unsigned N> + const face<N, D>& face_(unsigned face_id) const; + /// \} + + /// \brief connect two faces. + /// + /// \param f1 A face of dimension \p N + /// \param f2 A face of dimension \p N + 1 + /// + /// \pre \p N must be lower or equal to \p D. + template <unsigned N> + void connect_(const face_handle<N, D>& f1, + const face_handle<N + 1, D>& f2); + }; + + + // FIXME: Move and renamed as mln::debug::println? + /// Pretty print a complex. + template <unsigned D> + std::ostream& + operator<<(std::ostream& ostr, const complex<D>& c); + + + /*---------------------. + | Faces of a complex. | + `---------------------*/ + + // FIXME: Move these declarations after � Complex �. + + /// The sets of n-faces of a complex are recursively aggregated as + /// mixins. + namespace internal + { + + // FIXME: Factor common things here. + + /// \brief Recursive mixins of set of faces. + /// \{ + template <unsigned N, unsigned D> + struct faces_set_mixin : faces_set_mixin<N - 1, D> + { + std::vector< face<N, D> > faces_; + + /// Pretty-printing. + /// \{ + /// Print the faces of dimension \p N. + void print(std::ostream& ostr) const; + /// Recursively print the faces of dimensions 0 to \p N + /// (in ascending dimension). + void print_rec_asc(std::ostream& ostr) const; + /// \} + }; + + template <unsigned D> + struct faces_set_mixin<0u, D> + { + std::vector< face<0u, D> > faces_; + + /// Pretty-printing. + /// \{ + /// Print the faces of dimension 0. + void print(std::ostream& ostr) const; + void print_rec_asc(std::ostream& ostr) const; + /// \} + }; + /// \} + + } // end of namespace mln::internal + + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D> + face_handle<0u, D> + complex<D>::add_face() + { + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + internal::faces_set_mixin<0u, D>::faces_.push_back(face<0u, D>()); + unsigned id = internal::faces_set_mixin<0u, D>::faces_.size() - 1; + + return face_handle<0u, D>(*this, id); + } + + template <unsigned D> + template <unsigned N> + face_handle<N + 1, D> + complex<D>::add_face(const faces_set<N, D>& adjacent_faces) + { + // FIXME: Ensure ADJACENT_FACES are already part of the complex. + + face<N + 1, D> f; + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + internal::faces_set_mixin<N + 1, D>::faces_.push_back(f); + unsigned id = internal::faces_set_mixin<N + 1, D>::faces_.size() - 1; + + face_handle<N + 1, D> fh(*this, id); + // Connect F and its ADJACENT_FACES. + /* FIXME: Use <fonctional> or Milena's functors. */ + for (typename std::vector< face_handle<N, D> >::const_iterator a = + adjacent_faces.faces().begin(); + a != adjacent_faces.faces().end(); ++a) + connect_(*a, fh); + + return fh; + } + + template <unsigned D> + template <unsigned N> + face<N, D>& + complex<D>::face_(unsigned face_id) + { + return internal::faces_set_mixin<N, D>::faces_[face_id]; + } + + template <unsigned D> + template <unsigned N> + const face<N, D>& + complex<D>::face_(unsigned face_id) const + { + return internal::faces_set_mixin<N, D>::faces_[face_id]; + } + + template <unsigned D> + template <unsigned N> + void + complex<D>::connect_(const face_handle<N, D>& f1, + const face_handle<N + 1, D>& f2) + { + // Ensure N is compatible with D. + metal::bool_< N <= D >::check(); + + f1.get().connect_higher_dim_face(f2); + f2.get().connect_lower_dim_face(f1); + } + + + /*------------------. + | Pretty-printing. | + `------------------*/ + + template <unsigned D> + std::ostream& + operator<<(std::ostream& ostr, const complex<D>& c) + { + c.print(ostr); + return ostr; + } + + template <unsigned D> + void + complex<D>::print(std::ostream& ostr) const + { + internal::faces_set_mixin<D, D>::print_rec_asc(ostr); + } + + template <unsigned D> + template <unsigned N> + void + complex<D>::print_faces(std::ostream& ostr) const + { + // Ensure N is compatible with D. + metal::bool_< N <= D >::check(); + + internal::faces_set_mixin<N, D>::print(ostr); + } + + + namespace internal + { + + // FIXME: Factor common things here. + + template <unsigned N, unsigned D> + void + faces_set_mixin<N, D>::print_rec_asc(std::ostream& ostr) const + { + faces_set_mixin<N - 1, D>::print_rec_asc(ostr); + print(ostr); + } + + template <unsigned D> + void + faces_set_mixin<0, D>::print_rec_asc(std::ostream& ostr) const + { + print(ostr); + } + + template <unsigned N, unsigned D> + void + faces_set_mixin<N, D>::print(std::ostream& ostr) const + { + ostr << "Faces of dimension " << N + << " and their ajacent faces of dimension " + << N - 1 << " and " + << N + 1 << std::endl; + for (unsigned f = 0; f < faces_.size(); ++f) + { + ostr << " " << f << ": dim " << N - 1 << ": { "; + for (typename std::vector< face_handle<N - 1, D> >::const_iterator l = + faces_[f].lower_dim_faces_.begin(); + l != faces_[f].lower_dim_faces_.end(); + ++l) + ostr << l->face_id_ << " "; + ostr << "}, dim " << N + 1 << ": { "; + for (typename std::vector< face_handle<N + 1, D> >::const_iterator h = + faces_[f].higher_dim_faces_.begin(); + h != faces_[f].higher_dim_faces_.end(); + ++h) + ostr << h->face_id_ << " "; + ostr << "}"; + ostr << std::endl; + } + } + + template <unsigned D> + void + faces_set_mixin<0u, D>::print(std::ostream& ostr) const + { + // FIXME: Much could be factored with the previous routine. + const unsigned N = 0; + ostr << "Faces of dimension " << N + << " and their ajacent faces of dimension " + << N + 1 << std::endl; + for (unsigned f = 0; f < faces_.size(); ++f) + { + ostr << " " << f << " dim " << N + 1 << ": { "; + for (typename std::vector< face_handle<N + 1, D> >::const_iterator h = + faces_[f].higher_dim_faces_.begin(); + h != faces_[f].higher_dim_faces_.end(); + ++h) + ostr << h->face_id_ << " "; + ostr << "}"; + ostr << std::endl; + } + } + + + // FIXME: Handle faces_set_mixin<D, D>::print. + + + } // end of namespace mln::internal + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_COMPLEX_HH Index: mln/core/face.hh --- mln/core/face.hh (revision 0) +++ mln/core/face.hh (revision 0) @@ -0,0 +1,287 @@ +// 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_CORE_FACE_HH +# define MLN_CORE_FACE_HH + +/// \file mln/core/face.hh +/// \brief Face of a complex. +/// +/// FIXME: More. + +#include <vector> + +#include <mln/core/contract.hh> + + +namespace mln +{ + + // Forward declarations. + template <unsigned D> class complex; + template <unsigned N, unsigned D> class face_handle; + namespace internal + { + template <unsigned N, unsigned D> + struct faces_set_mixin; + } + + + /*-------. + | Face. | + `-------*/ + + /* FIXME: we might want to factor connect_{higher,lower}_dim_cell + and {higher,lower_dim_faces_} as member of super classes. */ + + template <unsigned N, unsigned D> + class face + { + public: + void connect_higher_dim_face(const face_handle<N + 1, D>& f); + void connect_lower_dim_face (const face_handle<N - 1, D>& f); + + private: + friend class mln::internal::faces_set_mixin<N, D>; + + // FIXME: Provide accessors instead of using `friend' if there are + // clients other than mln::internal::faces_set_mixin<N, D>. + std::vector< face_handle<N + 1, D> > higher_dim_faces_; + std::vector< face_handle<N - 1, D> > lower_dim_faces_; + }; + + template <unsigned D> + class face<0u, D> + { + public: + void connect_higher_dim_face(const face_handle<1u, D>& f); + + private: + friend class mln::internal::faces_set_mixin<0, D>; + + // FIXME: Provide accessors instead of using `friend; if there are + // clients other than mln::internal::faces_set_mixin<0, D>. + std::vector< face_handle<1u, D> > higher_dim_faces_; + }; + + // FIXME: Handle face<0u, 0u>. + + + /*--------------. + | Face handle. | + `--------------*/ + + // Face handle in a complex. + template <unsigned N, unsigned D> + struct face_handle + { + face_handle(complex<D>& complex, unsigned face_id); + + /// Copy and assignment. + /// \{ + face_handle(const face_handle<N, D>& rhs); + face_handle<N, D>& operator=(const face_handle<N, D>& rhs); + /// \} + + /// Accessors. + /// \{ + /// Return the mln::face pointed by this handle. + face<N, D>& get() const; + /// \} + + /* FIXME: Hide data. */ + // A const face_handle can be used to modify a complex. + mutable complex<D>& c_; + unsigned face_id_; + }; + + template <unsigned N, unsigned D> + face_handle<N, D> + make_face_handle(const complex<D>& c, unsigned face_id); + + + /*----------------------. + | Set of face handles. | + `----------------------*/ + + /// \brief Set of face handles of dimension \p N. + template <unsigned N, unsigned D> + class faces_set + { + public: + void add(const face_handle<N, D>& f); + + /// \brief Accessors. + /// + /// Return the set of handles. + /// \{ + const std::vector< face_handle<N, D> >& faces() const; + /// \} + + private: + friend class mln::complex<D>; + + // FIXME: Rename this as `handles_'? + std::vector< face_handle<N, D> > faces_; + }; + + + /// Construction helpers for mln::faces_set. + /// \{ + template <unsigned N, unsigned D> + faces_set<N, D> + operator+(const face_handle<N, D>& f1, const face_handle<N, D>& f2); + + template <unsigned N, unsigned D> + faces_set<N, D> + operator+(const faces_set<N, D>& fs, const face_handle<N, D>& f); + /// \} + + + +# ifndef MLN_INCLUDE_ONLY + + /*--------------. + | Face handle. | + `--------------*/ + + template <unsigned N, unsigned D> + face_handle<N, D>::face_handle(complex<D>& c, unsigned face_id) + : c_(c), face_id_(face_id) + { + } + + template <unsigned N, unsigned D> + face_handle<N, D>::face_handle(const face_handle<N, D>& rhs) + : c_(rhs.c_), face_id_(rhs.face_id_) + { + } + + template <unsigned N, unsigned D> + face_handle<N, D>& + face_handle<N, D>::operator=(const face_handle<N, D>& rhs) + { + if (&rhs != this) + { + c_ = rhs.c_; + face_id_ = rhs.face_id_; + } + return *this; + } + + template <unsigned N, unsigned D> + face<N, D>& + face_handle<N, D>::get() const + { + return c_.template face_<N>(face_id_); + } + + + template <unsigned N, unsigned D> + face_handle<N, D> + make_face_handle(const complex<D>& c, unsigned face_id) + { + return face_handle<N, D>(c, face_id); + } + + + /*--------. + | Faces. | + `--------*/ + + template <unsigned N, unsigned D> + void + face<N, D>::connect_higher_dim_face(const face_handle<N + 1, D>& f) + { + higher_dim_faces_.push_back(f); + } + + template <unsigned N, unsigned D> + void + face<N, D>::connect_lower_dim_face(const face_handle<N - 1, D>& f) + { + lower_dim_faces_.push_back(f); + } + + template <unsigned D> + void + face<0u, D>::connect_higher_dim_face(const face_handle<1u, D>& f) + { + higher_dim_faces_.push_back(f); + } + + + /*---------------. + | Set of faces. | + `---------------*/ + + template <unsigned N, unsigned D> + void + faces_set<N, D>::add(const face_handle<N, D>& f) + { + // Check consistency. + if (!faces_.empty()) + mln_assertion(&faces_.front().c_ == &f.c_); + + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + faces_.push_back (f); + } + + template <unsigned N, unsigned D> + const std::vector< face_handle<N, D> >& + faces_set<N, D>::faces() const + { + return faces_; + } + + + template <unsigned N, unsigned D> + faces_set<N, D> + operator+(const face_handle<N, D>& f1, const face_handle<N, D>& f2) + { + faces_set<N, D> fs; + fs.add(f1); + fs.add(f2); + return fs; + } + + template <unsigned N, unsigned D> + faces_set<N, D> + operator+(const faces_set<N, D>& fs, const face_handle<N, D>& f) + { + faces_set<N, D> fs2(fs); + fs2.add(f); + return fs2; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_FACE_HH Index: tests/core/complex.cc --- tests/core/complex.cc (revision 0) +++ tests/core/complex.cc (revision 0) @@ -0,0 +1,75 @@ +// 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file tests/core/complex.cc +/// \brief Test of mln::complex. + +#include <iostream> + +#include <mln/core/complex.hh> + + +int main() +{ + using namespace mln; + + /* A 2-d (simplicial) complex. + + v0 e3 v3 + o-----------o + / \ / + / \ t2 / + e0 / \ / e4 + / t1 \e1 / + / \ / + o-----------o + v1 e2 v2 + + */ + + + complex<2> c; + + // 0-faces (points). + face_handle<0, 2> v0 = c.add_face(); + face_handle<0, 2> v1 = c.add_face(); + face_handle<0, 2> v2 = c.add_face(); + face_handle<0, 2> v3 = c.add_face(); + + // 1-faces (segments). + face_handle<1, 2> e0 = c.add_face(v0 + v1); + face_handle<1, 2> e1 = c.add_face(v0 + v2); + face_handle<1, 2> e2 = c.add_face(v1 + v2); + face_handle<1, 2> e3 = c.add_face(v0 + v3); + face_handle<1, 2> e4 = c.add_face(v2 + v3); + + // 2-faces (triangles). + face_handle<2, 2> t0 = c.add_face(e0 + e1 + e2); + face_handle<2, 2> t1 = c.add_face(e1 + e3 + e4); + + std::cout << c << std::endl; +} Index: tests/core/Makefile.am --- tests/core/Makefile.am (revision 2113) +++ tests/core/Makefile.am (working copy) @@ -12,6 +12,7 @@ clock_neighb2d \ clock_test \ clone \ + complex \ \ decorated_image \ dpoint1d \ @@ -98,6 +99,7 @@ clock_neighb2d_SOURCES = clock_neighb2d.cc clock_test_SOURCES = clock_test.cc clone_SOURCES = clone.cc +complex_SOURCES = complex.cc decorated_image_SOURCES = decorated_image.cc dpoint1d_SOURCES = dpoint1d.cc