September 2008 - Olena-patches

2449: Add edge_impl_ and vertex_impl_.
by Guillaume Lazzara 30 Sep '08

30 Sep '08

--- milena/mln/util/internal/graph_edge.hh | 4 +- milena/mln/util/internal/graph_edge_impl.hh | 89 +++++++++++++++++++++++++ milena/mln/util/internal/graph_vertex.hh | 4 +- milena/mln/util/internal/graph_vertex_impl.hh | 89 +++++++++++++++++++++++++ 4 files changed, 184 insertions(+), 2 deletions(-) create mode 100644 milena/mln/util/internal/graph_edge_impl.hh create mode 100644 milena/mln/util/internal/graph_vertex_impl.hh diff --git a/milena/mln/util/internal/graph_edge.hh b/milena/mln/util/internal/graph_edge.hh index 78a00c2..24bb716 100644 --- a/milena/mln/util/internal/graph_edge.hh +++ b/milena/mln/util/internal/graph_edge.hh @@ -28,6 +28,8 @@ #ifndef MLN_UTIL_INTERNAL_GRAPH_EDGE_HH # define MLN_UTIL_INTERNAL_GRAPH_EDGE_HH +# include <mln/util/internal/graph_edge_impl.hh> + /*! \file mln/util/internal/graph_edge.hh * \brief Definition of a graph edge. */ @@ -44,7 +46,7 @@ namespace mln /// \brief Edge of a graph \p G. template <typename G> - class edge + class edge : public internal::edge_impl_<G> { typedef mlc_const(G) graph_t; diff --git a/milena/mln/util/internal/graph_edge_impl.hh b/milena/mln/util/internal/graph_edge_impl.hh new file mode 100644 index 0000000..2ed90c5 --- /dev/null +++ b/milena/mln/util/internal/graph_edge_impl.hh @@ -0,0 +1,89 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_CORE_INTERNAL_EDGE_IMPL_HH +# define MLN_CORE_INTERNAL_EDGE_IMPL_HH + +/*! \file mln/core/internal/edge_impl.hh + * + * \brief Define a couple of implementation classes to provide methods + * to classes of generalized edges. + */ + +# include <mln/core/internal/force_exact.hh> + + +namespace mln +{ + + namespace util + { + + namespace internal + { + + /// Implementation class to equip generalized edge classes. + template <typename G> + class edge_impl_ + { + protected: + edge_impl_(); + }; + + } // end of namespace internal + + } // end of namespace util + +} // end of namespace mln + +#ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace util + { + + namespace internal + { + + template <typename G> + inline + edge_impl_<G>::edge_impl_() + { + } + + } // end of namespace internal + + } // end of namespace util + +} // end of namespace mln + +#endif // ! MLN_INCLUDE_ONLY + + +#endif // ! MLN_CORE_INTERNAL_EDGE_IMPL_HH diff --git a/milena/mln/util/internal/graph_vertex.hh b/milena/mln/util/internal/graph_vertex.hh index c40bf0f..fc4ff2b 100644 --- a/milena/mln/util/internal/graph_vertex.hh +++ b/milena/mln/util/internal/graph_vertex.hh @@ -28,6 +28,8 @@ #ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH # define MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH +# include <mln/util/internal/graph_vertex_impl.hh> + /// \file mln/util/internal/graph_vertex.hh /// \brief Implementation of a graph vertex. @@ -39,7 +41,7 @@ namespace mln /// \brief Vertex of a graph \p G. template<typename G> - class vertex + class vertex : public internal::vertex_impl_<G> { typedef mlc_const(G) graph_t; diff --git a/milena/mln/util/internal/graph_vertex_impl.hh b/milena/mln/util/internal/graph_vertex_impl.hh new file mode 100644 index 0000000..863cf25 --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_impl.hh @@ -0,0 +1,89 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_CORE_INTERNAL_VERTEX_IMPL_HH +# define MLN_CORE_INTERNAL_VERTEX_IMPL_HH + +/*! \file mln/core/internal/vertex_impl.hh + * + * \brief Define a couple of implementation classes to provide methods + * to classes of generalized vertexs. + */ + +# include <mln/core/internal/force_exact.hh> + + +namespace mln +{ + + namespace util + { + + namespace internal + { + + /// Implementation class to equip generalized vertex classes. + template <typename G> + class vertex_impl_ + { + protected: + vertex_impl_(); + }; + + } // end of namespace internal + + } // end of namespace util + +} // end of namespace mln + +#ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace util + { + + namespace internal + { + + template <typename G> + inline + vertex_impl_<G>::vertex_impl_() + { + } + + } // end of namespace internal + + } // end of namespace util + +} // end of namespace mln + +#endif // ! MLN_INCLUDE_ONLY + + +#endif // ! MLN_CORE_INTERNAL_VERTEX_IMPL_HH -- 1.5.6.5

1 0

2448: Add a new util::graph implementation. The graph does not store data anymore.
by Guillaume Lazzara 30 Sep '08

30 Sep '08

--- milena/mln/core/concept/graph.hh | 150 ++++ milena/mln/core/internal/graph_iter_base.hh | 135 ++++ milena/mln/core/macros.hh | 53 ++ milena/mln/util/graph.hh | 284 ++------ milena/mln/util/internal/graph_base.hh | 742 +++++++------------- milena/mln/util/internal/graph_edge.hh | 378 ++++++++++ milena/mln/util/internal/graph_edge_iter.hh | 273 +++++++ .../mln/util/internal/graph_edge_nbh_edge_iter.hh | 335 +++++++++ milena/mln/util/internal/graph_vertex.hh | 361 ++++++++++ milena/mln/util/internal/graph_vertex_iter.hh | 266 +++++++ .../util/internal/graph_vertex_nbh_edge_iter.hh | 323 +++++++++ .../util/internal/graph_vertex_nbh_vertex_iter.hh | 320 +++++++++ milena/tests/util/graph.cc | 107 +++- 13 files changed, 3013 insertions(+), 714 deletions(-) create mode 100644 milena/mln/core/concept/graph.hh create mode 100644 milena/mln/core/internal/graph_iter_base.hh create mode 100644 milena/mln/util/internal/graph_edge.hh create mode 100644 milena/mln/util/internal/graph_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_edge_nbh_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex.hh create mode 100644 milena/mln/util/internal/graph_vertex_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh diff --git a/milena/mln/core/concept/graph.hh b/milena/mln/core/concept/graph.hh new file mode 100644 index 0000000..36d94c9 --- /dev/null +++ b/milena/mln/core/concept/graph.hh @@ -0,0 +1,150 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_CORE_CONCEPT_GRAPH_HH +# define MLN_CORE_CONCEPT_GRAPH_HH + +/*! \file mln/core/concept/graph.hh + * \brief Definition of the concept of mln::Graph. + */ + +namespace mln +{ + + + // Fwd decl. + template <typename E> struct Graph; + + // Graph category flag type. + template <> + struct Graph<void> + { + typedef Object<void> super; + }; + + /*! \brief Base class for implementation of graph classes. + * + * \see mln::doc::Graph for a complete documentation of this class + * contents. + */ + template <typename E> + struct Graph : public Object<E> + { + typedef Graph<void> category; + + /* + // provided by internal::image_base: + + typedef pset; + typedef site; + typedef psite; + + typedef fwd_piter; + typedef bkd_piter; + + // Misc. + void *graph_id() const; + template<typename G2> + bool is_subgraph_of(const G2& gr) const; + + // Vertex and edges oriented. + unsigned v_other(unsigned id_e, unsigned id_v) const; + + // Vertex oriented. + size_t v_nmax() const; + bool has_v(unsigned id_v) const; + size_t v_nmax_nbh_edges(unsigned id_v) const; + unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; + + // Edge oriented. + size_t e_nmax() const; + bool has_e(unsigned id_e) const; + unsigned v1(unsigned id_e) const; + unsigned v2(unsigned id_e) const; + size_t e_nmax_nbh_edges(unsigned id_e) const; + unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; + + */ + + protected: + Graph(); + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Graph<E>::Graph() + { + // provided by internal::graph_base: + + //typedef mln_psite(E) psite; + + //typedef mln_fwd_piter(E) fwd_piter; + //typedef mln_bkd_piter(E) bkd_piter; + + // Check methods + const void * const(E::*m1)() const = & E::graph_id; + m1 = 0; + unsigned (E::*m2)(unsigned id_e, unsigned id_v) const = & E::v_other; + m2 = 0; + unsigned (E::*m3)() = & E::add_vertex; + m3 = 0; + size_t (E::*m4)() const = & E::v_nmax; + m4 = 0; + bool (E::*m5)(unsigned id_v) const = & E::has_v; + m5 = 0; + size_t (E::*m6)(unsigned id_v) const = & E::v_nmax_nbh_edges; + m6 = 0; + unsigned (E::*m7)(unsigned id_v, unsigned i) const = & E::v_ith_nbh_edge; + m7 = 0; + size_t (E::*m8)() const = & E::e_nmax; + m8 = 0; + bool (E::*m9)(unsigned id_e) const = & E::has_e; + m9 = 0; + unsigned (E::*m10)(unsigned id_e) const = & E::v1; + m10 = 0; + unsigned (E::*m11)(unsigned id_e) const = & E::v2; + m11 = 0; + size_t (E::*m12)(unsigned id_e) const = & E::e_nmax_nbh_edges; + m12 = 0; + unsigned (E::*m13)(unsigned id_e, unsigned i) const = & E::e_ith_nbh_edge; + m13 = 0; + + //FIXME: enable this test. Currently does not work because this is + // a templated method. + //bool (E::*m14)(...) = & E::is_subgraph_of; + //m14 = 0; +} + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // ! MLN_CORE_CONCEPT_GRAPH_HH + diff --git a/milena/mln/core/internal/graph_iter_base.hh b/milena/mln/core/internal/graph_iter_base.hh new file mode 100644 index 0000000..2d7297c --- /dev/null +++ b/milena/mln/core/internal/graph_iter_base.hh @@ -0,0 +1,135 @@ +// 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. + +#ifndef MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH +# define MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH + +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> + +/// \file mln/core/internal/graph_iter_base.hh +/// \brief Base class for graph iterators. + +namespace mln +{ + + namespace internal + { + + /// Base class for graph iterators + /// \p G graph type. + /// \p S the type of the data pointed by the iterator. + /// For instance : edge, vertex.... + template<typename G, typename S> + class graph_iterator_base + : public Iterator< graph_iterator_base<G> >, + public internal::proxy_impl< const S&, graph_iterator_base<G> > + { + public: + /// Constructors. + /// \{ + graph_iterator_base(); + graph_iterator_base(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next_(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const S& subj_(); + /// \} + + protected: + const G *g_; + unsigned i_; + }; + + + template<typename G, typename S> + class graph_fwd_iterator_base + : public Iterator< graph_fwd_iterator_base<G> >, + public internal::proxy_impl< const S&, graph_fwd_iterator_base<G> > + { + public: + /// Construction and assignment. + /// \{ + graph_fwd_iterator_base(); + graph_fwd_iterator_base(const G& g); + /// \} + + /// 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 value. + void next_(); + + /// Return current index + unsigned index() const; + + /// Proxy. + /// \{ + /// Proxy Subject type + typedef const mln_vertex(G)& q_subject; + + /// Proxy subject + q_subject subj_(); + /// \} + + protected: + const G *g_; + unsigned i_; + }; + + } // End of namespace mln::internal. + +} // End of namespace mln. + +#endif // !MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH diff --git a/milena/mln/core/macros.hh b/milena/mln/core/macros.hh index 3b0b88c..3dc9036 100644 --- a/milena/mln/core/macros.hh +++ b/milena/mln/core/macros.hh @@ -418,5 +418,58 @@ # define mln_nixter(I, N) mln_fwd_nixter(I, N) # define mln_nixter_(I, N) mln_fwd_nixter_(I, N) +/// Shortcuts to access the vertex iterator type associated to a graph G. +/// \{ +# define mln_vertex_iter(G) typename G::vertex_iter +# define mln_vertex_iter_(G) G::vertex_iter +# define mln_vertex_fwd_iter(G) typename G::vertex_fwd_iter +# define mln_vertex_fwd_iter_(G) G::vertex_fwd_iter +# define mln_vertex_bkd_iter(G) typename G::vertex_bkd_iter +# define mln_vertex_bkd_iter_(G) G::vertex_bkd_iter +/// \} + +/// Shortcuts to access the edge iterator type associated to a graph G. +/// \{ +# define mln_edge_iter(G) typename G::edge_iter +# define mln_edge_iter_(G) G::edge_iter +# define mln_edge_fwd_iter(G) typename G::edge_fwd_iter +# define mln_edge_fwd_iter_(G) G::edge_fwd_iter +# define mln_edge_bkd_iter(G) typename G::edge_bkd_iter +# define mln_edge_bkd_iter_(G) G::edge_bkd_iter +/// \} + +/// Shortcuts to access the vertex centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_vertex_nbh_vertex_iter(G) typename G::vertex_nbh_vertex_iter +# define mln_vertex_nbh_vertex_iter_(G) G::vertex_nbh_vertex_iter +# define mln_vertex_nbh_vertex_fwd_iter(G) typename G::vertex_nbh_vertex_fwd_iter +# define mln_vertex_nbh_vertex_fwd_iter_(G) G::vertex_nbh_vertex_fwd_iter +# define mln_vertex_nbh_vertex_bkd_iter(G) typename G::vertex_nbh_vertex_bkd_iter +# define mln_vertex_nbh_vertex_bkd_iter_(G) G::vertex_nbh_vertex_bkd_iter +/// \} + +/// Shortcuts to access the vertex centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_vertex_nbh_edge_iter(G) typename G::vertex_nbh_edge_iter +# define mln_vertex_nbh_edge_iter_(G) G::vertex_nbh_edge_iter +# define mln_vertex_nbh_edge_fwd_iter(G) typename G::vertex_nbh_edge_fwd_iter +# define mln_vertex_nbh_edge_fwd_iter_(G) G::vertex_nbh_edge_fwd_iter +# define mln_vertex_nbh_edge_bkd_iter(G) typename G::vertex_nbh_edge_bkd_iter +# define mln_vertex_nbh_edge_bkd_iter_(G) G::vertex_nbh_edge_bkd_iter +/// \} + +/// Shortcuts to access the edge centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_edge_nbh_edge_iter(G) typename G::edge_nbh_edge_iter +# define mln_edge_nbh_edge_iter_(G) G::edge_nbh_edge_iter +# define mln_edge_nbh_edge_fwd_iter(G) typename G::edge_nbh_edge_fwd_iter +# define mln_edge_nbh_edge_fwd_iter_(G) G::edge_nbh_edge_fwd_iter +# define mln_edge_nbh_edge_bkd_iter(G) typename G::edge_nbh_edge_bkd_iter +# define mln_edge_nbh_edge_bkd_iter_(G) G::edge_nbh_edge_bkd_iter +/// \} #endif // ! MLN_CORE_MACROS_HH + diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index 0273bd8..ba148d3 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -32,281 +32,97 @@ /// \brief Definitions of undirected graphs. # include <mln/util/internal/graph_base.hh> +# include <mln/util/internal/graph_vertex_iter.hh> +# include <mln/util/internal/graph_edge_iter.hh> +# include <mln/util/internal/graph_vertex_nbh_vertex_iter.hh> +# include <mln/util/internal/graph_vertex_nbh_edge_iter.hh> +# include <mln/util/internal/graph_edge_nbh_edge_iter.hh> namespace mln { namespace util { - /*-----------. - | Fwd decl. | - `-----------*/ /// \brief Undirected graph. - template<typename V = void, typename E = void> - class graph; - - /*--------------------. - | graph<void, void>. | - `--------------------*/ - - /// Specialization for undirected graphs with no data on vertices nor - /// on edges. - template <> - class graph<void, void> : public internal::graph_base<void, void> + class graph : public internal::graph_base<graph> { public: /// The super class. - typedef internal::graph_base<void, void> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2); - }; - - /*-----------------. - | graph<V, void>. | - `-----------------*/ + typedef internal::graph_base<graph> super; - /// Specialization for undirected graphs with data on vertices. - template <typename V> - class graph<V, void> : public internal::graph_base<V, void> - { - public: - /// The super class. - typedef internal::graph_base<V, void> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(const V& data); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2); + /// Iterator types + /// \{ - /// Return the data associated to vertex with id \a v. + /// Vertex iterators /// \{ - V& vertex_data(vertex_id v); - const V& vertex_data(vertex_id v) const; + typedef mln::internal::vertex_fwd_iterator<graph> vertex_fwd_iter; + typedef mln::internal::vertex_bkd_iterator<graph> vertex_bkd_iter; + typedef vertex_fwd_iter vertex_iter; /// \} - }; - /*--------------. - | graph<V, E>. | - `--------------*/ - - /// Specialization for undirected graphs with data on vertices and - /// edges. - template <typename V, typename E> - class graph : public internal::graph_base<V, E> - { - public: - /// The super class. - typedef internal::graph_base<V, E> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(const V& data); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2, const E& data); - - /// Return the data associated to vertex with id \a v. + /// Vertex centered edge iterators /// \{ - V& vertex_data(vertex_id v); - const V& vertex_data(vertex_id v) const; + typedef mln::internal::vertex_nbh_edge_fwd_iterator<graph> vertex_nbh_edge_fwd_iter; + typedef mln::internal::vertex_nbh_edge_bkd_iterator<graph> vertex_nbh_edge_bkd_iter; + typedef vertex_nbh_edge_fwd_iter vertex_nbh_edge_iter; /// \} - /// Return the data associated to the edge with id \a e. + /// Vertex centered vertex iterators /// \{ - E& edge_data(edge_id e); - const E& edge_data(edge_id e) const; + typedef mln::internal::vertex_nbh_vertex_fwd_iterator<graph> vertex_nbh_vertex_fwd_iter; + typedef mln::internal::vertex_nbh_vertex_bkd_iterator<graph> vertex_nbh_vertex_bkd_iter; + typedef vertex_nbh_vertex_fwd_iter vertex_nbh_vertex_iter; /// \} - /// Return the data associated to the edge between vertices with - /// ids \a v1 and \a v2. + /// Edge iterators /// \{ - E& edge_data(vertex_id v1, vertex_id v2); - const E& edge_data(vertex_id v1, vertex_id v2) const; + typedef mln::internal::edge_fwd_iterator<graph> edge_fwd_iter; + typedef mln::internal::edge_bkd_iterator<graph> edge_bkd_iter; + typedef edge_fwd_iter edge_iter; /// \} - }; - - - -# ifndef MLN_INCLUDE_ONLY - - /*--------------------. - | graph<void, void>. | - `--------------------*/ - - /* Note that definition of members from fully specialized - template classes are not preceded by `template<>'. */ - inline - vertex_id - graph<void, void>::add_vertex() - { - return super::add_vertex_(new util::vertex<void>); - } - - /* Note that ddefinition of members from fully specialized - template classes are not preceded by `template<>'. */ - inline - edge_id - graph<void, void>::add_edge(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<void>(v1, v2)); - } - - /*-----------------. - | graph<V, void>. | - `-----------------*/ - template<typename V> - inline - vertex_id - graph<V, void>::add_vertex(const V& data) - { - return super::add_vertex_(new util::vertex<V>(data)); - } - - template<typename V> - inline - edge_id - graph<V, void>::add_edge(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<void>(v1, v2)); - } - - template <class V> - inline - V& - graph<V, void>::vertex_data(vertex_id v) - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } + /// Edge centered edge iterators. + /// \{ + typedef mln::internal::edge_nbh_edge_fwd_iterator<graph> edge_nbh_edge_fwd_iter; + typedef mln::internal::edge_nbh_edge_bkd_iterator<graph> edge_nbh_edge_bkd_iter; + typedef edge_nbh_edge_fwd_iter edge_nbh_edge_iter; + /// \} - template<typename V> - inline - const V& - graph<V, void>::vertex_data(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } + /// \} + /// Return whether this graph is a subgraph + /// Return always false here. + template <typename G2> + bool is_subgraph_of(const G2& g); + }; - /*--------------. - | graph<V, E>. | - `--------------*/ + } // end of namespace mln::util - template<typename V, typename E> - inline - vertex_id - graph<V, E>::add_vertex(const V& data) - { - return super::add_vertex_(new util::vertex<V>(data)); - } +} // end of namespace mln - template<typename V, typename E> - inline - edge_id - graph<V, E>::add_edge(vertex_id v1, vertex_id v2, const E& data) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<E>(v1, v2, data)); - } - template<typename V, typename E> - inline - V& - graph<V, E>::vertex_data(vertex_id v) - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } +# ifndef MLN_INCLUDE_ONLY - template<typename V, typename E> - inline - const V& - graph<V, E>::vertex_data(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } +namespace mln +{ - template<typename V, typename E> - inline - E& - graph<V, E>::edge_data(edge_id e) - { - mln_assertion(e < this->nedges()); - return this->edges_[e]->data; - } + namespace util + { - template<typename V, typename E> + template <typename G2> inline - const E& - graph<V, E>::edge_data(edge_id e) const + bool + graph::is_subgraph_of(const G2& g) { - mln_assertion(e < this->nedges()); - return this->edges_[e]->data; + return false; } - template<typename V, typename E> - inline - E& - graph<V, E>::edge_data(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - ord_pair<vertex_id> vertex_pair (v1, v2); - std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; - for (std::vector<edge_id>::iterator e = edges_ids.begin(); - e != edges_ids.end(); ++e) - if (this->edges_[*e] == vertex_pair) - return this->edges_[*e]->data; - // If no edge between V1 and V2 was found, abort. - abort(); - } + } // end of namespace mln::util - template<typename V, typename E> - inline - const E& - graph<V, E>::edge_data(vertex_id v1, vertex_id v2) const - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - ord_pair<vertex_id> vertex_pair (v1, v2); - const std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; - for (std::vector<edge_id>::const_iterator e = edges_ids.begin(); - e != edges_ids.end(); ++e) - if (this->edges_[*e] == vertex_pair) - return this->edges_[*e]->data; - // If no edge between V1 and V2 was found, abort. - abort(); - } +} // end of namespace mln # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::util - -} // end of namespace mln #endif // ! MLN_UTIL_GRAPH_HH diff --git a/milena/mln/util/internal/graph_base.hh b/milena/mln/util/internal/graph_base.hh index d6fb437..17143c5 100644 --- a/milena/mln/util/internal/graph_base.hh +++ b/milena/mln/util/internal/graph_base.hh @@ -39,14 +39,15 @@ # include <set> # include <ostream> -// For gen_id. -# include <mln/value/builtin/all.hh> - # include <mln/core/concept/object.hh> +# include <mln/core/concept/graph.hh> +# include <mln/core/concept/proxy.hh> # include <mln/util/ord_pair.hh> # include <mln/value/builtin/integers.hh> +# include <mln/util/internal/graph_edge.hh> +# include <mln/util/internal/graph_vertex.hh> namespace mln { @@ -54,391 +55,151 @@ namespace mln namespace util { - /*--------------. - | Identifiers. | - `--------------*/ - - /// \brief Generic identifier/handler. - /// - /// Inspired by Vaucansons's handlers for automata. - /// - /// https://svn.lrde.epita.fr/svn/vaucanson/trunk/include/vaucanson/automata/co… - /// https://svn.lrde.epita.fr/svn/vaucanson/trunk/include/vaucanson/automata/co… - /// - /// \todo We /might/ want to integrate this into Milena's value system. - /// - /// \todo Move this class elsewhere? - - template <typename Tag, typename Equiv> - class gen_id : public Object< gen_id < Tag, Equiv > > - { - typedef gen_id<Tag, Equiv> self_t; - - public: - typedef Equiv equiv; - - gen_id(); - gen_id(const Equiv& e); - self_t& operator=(const Equiv& e); - - const equiv& to_equiv() const; - equiv& to_equiv(); - operator const equiv() const; - operator equiv(); - - private: - equiv e_; - }; - - - /// Compare two identifiers. - /// \{ - template <typename Tag, typename Equiv> - bool - operator==(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - operator==(const Equiv& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - operator==(const gen_id<Tag, Equiv>& i, const Equiv j); - - - template <typename Tag, typename Equiv> - bool - ord_strict(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - ord_weak(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - /// \} - - - /// Tags. - /// \{ - struct vertex_tag; - struct edge_tag; - /// \} - - - /// \brief The type used to identify vertices. - /// - /// Used internally as a key to manipulate vertices. - typedef gen_id<vertex_tag, unsigned> vertex_id; - - /// \brief The type used to identify edges. - /// - /// Used internally as a key to manipulate edges. - typedef gen_id<edge_tag, unsigned> edge_id; - - - /*---------. - | Vertex. | - `---------*/ - - /// \brief Vertex of a graph, holding a value of type \p T. - template<typename T> - struct vertex - { - vertex(T data) - : data(data) - {} - - T data; - std::vector<edge_id> edges; - }; - - /// \brief Specialization of mln::util::vertex for vertices with no - /// associated value. - template <> - struct vertex<void> - { - std::vector<edge_id> edges; - }; - - - /*-------. - | Edge. | - `-------*/ - - /// \brief Edge of a graph, holding a value of type \p T. - template<typename T> - struct edge - { - edge(vertex_id v1, vertex_id v2) - : pair_vertex_(v1, v2) - {} - - /// Return the lowest vertex id adjacent to this edge. - vertex_id v1() const { return pair_vertex_.first(); } - /// Return the highest vertex id adjacent to this edge. - vertex_id v2() const { return pair_vertex_.second(); } - - T data; - ord_pair<vertex_id> pair_vertex_; - }; - - /// \brief Specialization of mln::util::vertex for edges with no - /// associated value. - template <> - struct edge<void> - { - edge(vertex_id v1, vertex_id v2) - : pair_vertex_(v1, v2) - {} - - /// Return the lowest vertex id adjacent to this edge. - vertex_id v1() const { return pair_vertex_.first(); } - /// Return the highest vertex id adjacent to this edge. - vertex_id v2() const { return pair_vertex_.second(); } - - ord_pair<vertex_id> pair_vertex_; - }; - - // FIXME: Document this. In particular, we should state that edges are - // only compared w.r.t. their adjacent vertices, not the data they - // possibly hold! - template <typename E> - bool - operator==(const edge<E>& lhs, const edge<E>& rhs); - - template <typename E> - bool - operator< (const edge<E>& lhs, const edge<E>& rhs); - - /*-------------. | Graph base. | `-------------*/ namespace internal { - // FIXME: This should be no longer useful once vertices and edges - // are handled without pointers and dynamic allocation. - template <typename T> - struct less_ptr - { - bool - operator()(const T& a, const T& b) - { - mln_assertion(a); - mln_assertion(b); - return (*a < *b); - } - }; - - /// \brief Base class for undirected graphs. - template<typename V, typename E> - class graph_base + template<typename E> + class graph_base : public Graph<E> { - typedef graph_base<V, E> self_t; - - public: - /* FIXME: Do we really want handle vertices and edges through - pointers? In my (Roland) opinion, this is just a drawback, - here. */ + /// The type of a vertex. + typedef util::vertex<E> vertex_t; + /// Internal vertex data type + typedef std::vector<unsigned> vertex_data_t; /// The type of the set of vertices. - typedef std::vector< util::vertex<V>* > vertices_t; + typedef std::vector<vertex_data_t> vertices_t; + + /// The type of an edge. + typedef util::edge<E> edge_t; + /// Internal edge data type. + typedef ord_pair<unsigned> edge_data_t; /// The type of the set of edges. - typedef std::vector< util::edge<E>* > edges_t; + typedef std::vector<edge_data_t> edges_t; /// A set to test the presence of a given edge. - typedef std::set< util::edge<E>*, - less_ptr< util::edge<E>* > > edges_set_t; + typedef std::set<edge_data_t> edges_set_t; - /// Construction, assignments and destruction. + public: + /// Misc. methods /// \{ - graph_base(); - graph_base(const self_t& rhs); - self_t& operator=(const self_t& rhs); - ~graph_base(); + /// Returns the graph id, the "this" pointer. + const void * const graph_id() const; /// \} - /// Return the vertex whose id is \a v. + /// Vertex and edge oriented methods. /// \{ - util::vertex<V>& vertex(vertex_id v); - const util::vertex<V>& vertex(vertex_id v) const; + /// Returns the other adjacent vertex id of a given edge id \p id_e. + unsigned v_other(unsigned id_e, unsigned id_v) const; /// \} - /// Return the edge whose id is \a e. - /// \{ - util::edge<E>& edge(edge_id e); - const util::edge<E>& edge(edge_id e) const; - /// \} - /// Return the whole vertices of the graph. + /// Vertex oriented. + /// \{ + + /// Shortcuts factoring the insertion of vertices and edges. /// \{ - vertices_t& vertices(); - const vertices_t& vertices() const; - /// \} + /// \brief Add a vertex. + /// + /// \return The id of the new vertex. + unsigned add_vertex(); - /// Return the whole edges of the graph. + /// Return the vertex whose id is \a v. /// \{ - edges_t& edges(); - const edges_t& edges() const; + vertex_t vertex(unsigned id_v) const; /// \} /// \brief Return the number of vertices in the graph. - size_t nvertices() const; - /// \brief Return the number of edges in the graph. - size_t nedges() const; + size_t v_nmax() const; - // FIXME: We might want to externalize this in routine of - // namespace mln::debug. - /** \brief Print on \p ostr the graph. + /// Check whether a vertex id \p id_v is valid in the graph. + bool has_v(unsigned id_v) const; - \param[in] ostr The output stream. */ - void print_debug(std::ostream& ostr) const; + /// Return the number of adjacent edges of vertex \p id_v. + size_t v_nmax_nbh_edges(unsigned id_v) const; - protected: - /// Shortcuts factoring the insertion of vertices and edges. + /// Returns the \p i th edge adjacent to the vertex \p id_v. + unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; + + /// Return the number of adjacent vertices of vertex \p id_v. + size_t v_nmax_nbh_vertices(unsigned id_v) const; + + /// Returns the \p i th vertex adjacent to the vertex \p id_v. + unsigned v_ith_nbh_vertex(unsigned id_v, unsigned i) const; + + /// \} + + + /// Edge oriented. /// \{ - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex_(util::vertex<V>* vertex); /// \brief Add an edge. /// /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge_(util::edge<E>* edge); + /// otherwise, return <tt>mln_max(unsigned)</tt>. + unsigned add_edge(unsigned id_v1, unsigned id_v2); /// \} - protected: - /// The vertices. - vertices_t vertices_; - /// The edges. - edges_t edges_; - /// An index of the set of edges, for fast-access purpose. - edges_set_t edges_set_; - }; - - } // end of namespace mln::util::internal - - - -# ifndef MLN_INCLUDE_ONLY + /// Return the edge whose id is \a e. + /// \{ + const edge_t& edge(unsigned e) const; + /// \} - /*--------------. - | Identifiers. | - `--------------*/ + /// \brief Return the number of edges in the graph. + size_t e_nmax() const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::gen_id() - { - } + /// Return whether \p id_e is in the graph. + bool has_e(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::gen_id(const Equiv& e) - : e_ (e) - { - } + /// Return the first vertex associated to the edge \p id_e. + unsigned v1(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>& - gen_id<Tag, Equiv>::operator=(const Equiv& e) - { - e_ = e; - return *this; - } - - template <typename Tag, typename Equiv> - inline - const Equiv& - gen_id<Tag, Equiv>::to_equiv() const - { - return e_; - } + /// Return the second vertex associated to edge \p id_e + unsigned v2(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - Equiv& - gen_id<Tag, Equiv>::to_equiv() - { - return e_; - } + /// Return the number max of adjacent edge, given an edge \p id_e. + size_t e_nmax_nbh_edges(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::operator const Equiv() const - { - return to_equiv(); - } + /// Return the \p i th edge adjacent to the edge \p id_e. + unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::operator Equiv() - { - return to_equiv(); - } + /// \} + // FIXME: We might want to externalize this in routine of + // namespace mln::debug. + /** \brief Print on \p ostr the graph. - template <typename Tag, typename Equiv> - inline - bool - operator==(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() == j.to_equiv(); - } + \param[in] ostr The output stream. */ + void print_debug(std::ostream& ostr) const; - template <typename Tag, typename Equiv> - inline - bool - operator==(const Equiv& i, const gen_id<Tag, Equiv>& j) - { - return i == j.to_equiv(); - } - template <typename Tag, typename Equiv> - inline - bool - operator==(const gen_id<Tag, Equiv>& i, const Equiv j) - { - return i.to_equiv() == j; - } + protected: - template <typename Tag, typename Equiv> - inline - bool - ord_strict (const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() < j.to_equiv(); - } + /// The vertices. + vertices_t vertices_; + /// The edges. + edges_t edges_; + /// An index of the set of edges, for fast-access purpose. + edges_set_t edges_set_; - template <typename Tag, typename Equiv> - inline - bool - ord_weak (const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() <= j.to_equiv(); - } + /// Construction, assignments and destruction. + /// \{ + graph_base<E>(); + //graph_base<E>(const self_t& rhs); + //self_t& operator=(const self_t& rhs); + //~graph_base<E>(); + /// \} + }; - /*---------------------. - | Operators on edges. | - `---------------------*/ + } // end of namespace mln::util::internal + } // End of namespace mln::util - template <typename E> - inline - bool - operator==(const edge<E>& lhs, const edge<E>& rhs) - { - return lhs.pair_vertex_ == rhs.pair_vertex_; - } +# ifndef MLN_INCLUDE_ONLY - template <typename E> - inline - bool - operator< (const edge<E>& lhs, const edge<E>& rhs) - { - return lhs.pair_vertex_ < rhs.pair_vertex_; - } + namespace util + { namespace internal { @@ -447,194 +208,145 @@ namespace mln | Construction, assignments and destruction. | `--------------------------------------------*/ - template<typename V, typename E> + template<typename E> inline - graph_base<V, E>::graph_base() + graph_base<E>::graph_base() : vertices_(), edges_(), edges_set_() { } - template<typename V, typename E> - inline - graph_base<V, E>::graph_base(const graph_base<V, E>& rhs) - : vertices_(), edges_(), edges_set_() - { - vertices_.reserve(rhs.vertices_.size()); - edges_.reserve(rhs.edges_.size()); - for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); - v != rhs.vertices_.end(); ++v) - vertices_.push_back(new util::vertex<V>(**v)); - for (typename edges_t::const_iterator e = rhs.edges_.begin(); - e != rhs.edges_.end(); ++e) - edges_.push_back(new util::edge<E>(**e)); - std::copy(edges_.begin(), edges_.end(), - std::insert_iterator<edges_set_t>(edges_set_, - edges_set_.begin())); - } + /*-------------. + | Misc methods | + `-------------*/ - template<typename V, typename E> + template<typename E> inline - graph_base<V, E>& - graph_base<V, E>::operator=(const graph_base<V, E>& rhs) + const void * const + graph_base<E>::graph_id() const { - if (this != &rhs) - { - /// Free previous vertices and edges. - for (typename vertices_t::iterator v = vertices_.begin(); - v != vertices_.end(); ++v) - delete *v; - for (typename edges_t::iterator e = edges_.begin(); - e != edges_.end(); ++e) - delete *e; - edges_set_.clear(); - /// Assign values from RHS. - vertices_.reserve(rhs.vertices_.size()); - edges_.reserve(rhs.edges_.size()); - for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); - v != rhs.vertices_.end(); ++v) - vertices_.push_back(new util::vertex<V>(**v)); - for (typename edges_t::const_iterator e = rhs.edges_.begin(); - e != rhs.edges_.end(); ++e) - edges_.push_back(new util::edge<E>(**e)); - std::copy(edges_.begin(), edges_.end(), - std::insert_iterator<edges_set_t>(edges_set_, - edges_set_.begin())); - } - return *this; + return this; } - template<typename V, typename E> + /*-------------------------. + | Vertex and edges related | + `-------------------------*/ + + template<typename E> inline - graph_base<V, E>::~graph_base() + unsigned + graph_base<E>::v_other(unsigned id_e, unsigned id_v) const { - for (typename vertices_t::iterator v = vertices_.begin(); - v != vertices_.end(); ++v) - delete *v; - for (typename edges_t::iterator e = edges_.begin(); e != edges_.end(); - ++e) - delete *e; - edges_set_.clear(); + mln_precondition(has_e(id_e)); + mln_precondition(has_v(id_v)); + mln_precondition(edges_[id_e].first() == id_v + || edges_[id_e].second() == id_v); + + const edge_data_t& e = edges_[id_e]; + if (e.first() == id_v) + return e.second(); + return e.first(); } - /*------------. - | Accessors. | - `------------*/ + /*---------------. + | Vertex related | + `---------------*/ - template<typename V, typename E> + template<typename E> inline - util::vertex<V>& - graph_base<V, E>::vertex(vertex_id v) + unsigned + graph_base<E>::add_vertex() { - mln_assertion(v < this->nvertices()); - return *vertices_[v]; - } + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + vertices_.resize(vertices_.size() + 1); - template<typename V, typename E> - inline - const util::vertex<V>& - graph_base<V, E>::vertex(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return *vertices_[v]; + return vertices_.size() - 1; } - template<typename V, typename E> + template<typename E> inline - util::edge<E>& - graph_base<V, E>::edge(edge_id e) + typename graph_base<E>::vertex_t + graph_base<E>::vertex(unsigned id_v) const { - mln_assertion(e < this->nedges()); - return *edges_[e]; - } + mln_assertion(has_v(id_v)); - template<typename V, typename E> - inline - const util::edge<E>& - graph_base<V, E>::edge(edge_id e) const - { - mln_assertion(e < this->nedges()); - return *edges_[e]; + return vertex_t(this, id_v); } - template<typename V, typename E> + template<typename E> inline - typename graph_base<V, E>::vertices_t& - graph_base<V, E>::vertices() + size_t + graph_base<E>::v_nmax() const { - return vertices_; + return vertices_.size(); } - template<typename V, typename E> + template<typename E> inline - const typename graph_base<V, E>::vertices_t& - graph_base<V, E>::vertices() const + bool + graph_base<E>::has_v(unsigned id_v) const { - return vertices_; + return id_v < vertices_.size(); } - template<typename V, typename E> + template<typename E> inline - typename graph_base<V, E>::edges_t& - graph_base<V, E>::edges() + size_t + graph_base<E>::v_nmax_nbh_edges(unsigned id_v) const { - return edges_; + mln_precondition(has_v(id_v)); + + return vertices_[id_v].size(); } - template<typename V, typename E> + template<typename E> inline - const typename graph_base<V, E>::edges_t& - graph_base<V, E>::edges() const + unsigned + graph_base<E>::v_ith_nbh_edge(unsigned id_v, unsigned i) const { - return edges_; + mln_precondition(has_v(id_v)); + if (i >= v_nmax_nbh_edges(id_v)) + return v_nmax(); + + return vertices_[id_v][i]; } - template<typename V, typename E> + template<typename E> inline size_t - graph_base<V, E>::nvertices() const + graph_base<E>::v_nmax_nbh_vertices(unsigned id_v) const { - return vertices_.size(); + mln_precondition(has_v(id_v)); + return v_nmax_nbh_edges(id_v); } - template<typename V, typename E> + template<typename E> inline - size_t - graph_base<V, E>::nedges() const + unsigned + graph_base<E>::v_ith_nbh_vertex(unsigned id_v, unsigned i) const { - return edges_.size(); + mln_precondition(has_v(id_v)); + + unsigned id_e = v_ith_nbh_edge(id_v, i); + return v_other(id_e, id_v); } - /*---------------. - | Manipulators. | - `---------------*/ - template<typename V, typename E> - inline - vertex_id - graph_base<V, E>::add_vertex_(util::vertex<V>* vertex) - { - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - vertices_.push_back (vertex); - return vertices_.size() - 1; - } + /*--------------. + | Edges related | + `---------------*/ - template<typename V, typename E> + template<typename E> inline - edge_id - graph_base<V, E>::add_edge_(util::edge<E>* edge) + unsigned + graph_base<E>::add_edge(unsigned id_v1, unsigned id_v2) { // Does this edge already exist in the graph? + edge_data_t edge(id_v1, id_v2); if (edges_set_.find(edge) != edges_set_.end ()) { - // Remove the previously allocated data for EDGE. - delete edge; - edge = 0; // Return the erroneous value. - /* FIXME: We have to explicitly extract the numerical - equivalent type here, because mln::util::gen_id<T, E> - is not compatible with Milena's value system (yet). */ - return mln_max(edge_id::equiv); + return mln_max(unsigned); } else { @@ -642,49 +354,121 @@ namespace mln /* FIXME: This is not thread-proof (these two lines should form an atomic section). */ edges_.push_back(edge); - edge_id id = edges_.size() - 1; + unsigned id = edges_.size() - 1; // Update the set of edges. edges_set_.insert(edge); - vertices_[edge->v1()]->edges.push_back(id); - vertices_[edge->v2()]->edges.push_back(id); + vertices_[edge.first()].push_back(id); + vertices_[edge.second()].push_back(id); return id; } } + template<typename E> + inline + const typename graph_base<E>::edge_t& + graph_base<E>::edge(unsigned e) const + { + mln_assertion(e < this->nedges()); + return edge_t(this, edges_[e].first(), edges_[e].second()); + } + + template<typename E> + inline + size_t + graph_base<E>::e_nmax() const + { + return edges_.size(); + } + + template<typename E> + inline + bool + graph_base<E>::has_e(unsigned id_e) const + { + return id_e < edges_.size(); + } + + template<typename E> + inline + unsigned + graph_base<E>::v1(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return edges_[id_e].first(); + } + + template<typename E> + inline + unsigned + graph_base<E>::v2(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return edges_[id_e].second(); + } + + template<typename E> + inline + size_t + graph_base<E>::e_nmax_nbh_edges(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e)); + } + + template<typename E> + inline + unsigned + graph_base<E>::e_ith_nbh_edge(unsigned id_e, unsigned i) const + { + mln_precondition(has_e(id_e)); + if (i >= e_nmax_nbh_edges(id_e)) + return e_nmax(); + + unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e)); + if (i < v1_nmax) + return v_ith_nbh_edge(v1(id_e), i); + return v_ith_nbh_edge(v2(id_e), i - v1_nmax); + } + /*--------. | Debug. | `--------*/ - template<typename V, typename E> + template<typename E> inline void - graph_base<V, E>::print_debug (std::ostream& ostr) const + graph_base<E>::print_debug (std::ostream& ostr) const { ostr << "graph: " << std::endl; for (unsigned v = 0; v < vertices_.size(); ++v) { ostr << "vertex: " << v << std::endl << " -- adjacent vertices: "; - /* FIXME: We shouldn't manipulate std::vector<edge_id> - directly, but use a typedef instead. */ - for (typename std::vector<util::edge_id>::const_iterator e = - vertices_[v]->edges.begin(); e != vertices_[v]->edges.end(); + for (vertex_data_t::const_iterator e = + vertices_[v].begin(); e != vertices_[v].end(); ++e) - if (v == edges_[*e]->v1()) - ostr << edges_[*e]->v2() << " "; + if (v == edges_[*e].first()) + ostr << edges_[*e].second() << " "; else - ostr << edges_[*e]->v1() << " "; + ostr << edges_[*e].first() << " "; ostr << std::endl; } ostr << std::endl; + + ostr << "edges:" << std::endl; + unsigned ei = 0; + for (edges_t::const_iterator e = edges_.begin(); e != edges_.end(); + ++e, ++ei) + ostr << "edge " << ei << ": (" << e->first() << ", " << e->second() << " )" << std::endl; } } // end of namespace mln::util::internal + } // end of namespace mln::util + # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::util } // end of namespace mln diff --git a/milena/mln/util/internal/graph_edge.hh b/milena/mln/util/internal/graph_edge.hh new file mode 100644 index 0000000..78a00c2 --- /dev/null +++ b/milena/mln/util/internal/graph_edge.hh @@ -0,0 +1,378 @@ +// 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_UTIL_INTERNAL_GRAPH_EDGE_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_HH + +/*! \file mln/util/internal/graph_edge.hh + * \brief Definition of a graph edge. + */ + +namespace mln +{ + + namespace util + { + + /*-------. + | Edge. | + `-------*/ + + /// \brief Edge of a graph \p G. + template <typename G> + class edge + { + typedef mlc_const(G) graph_t; + + public: + /// Constructors + /// \{ + edge(); + explicit edge(graph_t *g); + edge(graph_t *g, unsigned id); + /// \} + + + + /// Misc. + /// \{ + /// Return the edge id. + unsigned id() const; + + /// Set \att id_ with \p id; + void update_id(unsigned id); + + /// Return pointer of the graph holding this edge. + const graph_t * const g() const; + /// \} + + + + /// Vertex and edges oriented. + /// \{ + /// Return the vertex id of this edge which is different from \p id_v. + unsigned v_other(unsigned id_v) const; + /// \} + + + /// Edge oriented. + /// \{ + bool is_valid() const; + + /// Return the lowest vertex id adjacent to this edge. + unsigned v1() const; + + /// Return the highest vertex id adjacent to this edge. + unsigned v2() const; + + /// Return the number max of adjacent edges. + size_t nmax_nbh_edges() const; + + /// Return the \p i th adjacent edge. + unsigned ith_nbh_edge(unsigned i) const; + /// \} + + private: + graph_t * const g_; + unsigned id_; + }; + + template <typename G> + bool + operator==(const util::edge<G>& lhs, const util::edge<G>& rhs); + + template <typename G> + bool + operator< (const util::edge<G>& lhs, const util::edge<G>& rhs); + + } // End of namespace mln::util + + + /// subject_impl specialization (Proxy) + /// \{ + namespace internal + { + + template <typename G, typename E> + struct subject_impl< const util::edge<G>, E > + { + unsigned id() const; + const mlc_const(G) * const g() const; + unsigned v_other(unsigned id_v) const; + bool is_valid() const; + unsigned v1() const; + unsigned v2() const; + size_t nmax_nbh_edges() const; + unsigned ith_nbh_edge(unsigned i) const; + + + private: + const E& exact_() const; + }; + + template <typename G, typename E> + struct subject_impl< util::edge<G>, E > : + subject_impl< const util::edge<G>, E > + { + void update_id(unsigned id); + + private: + E& exact_(); + }; + + } // end of namespace mln::internal + /// \} + + +# ifndef MLN_INCLUDE_ONLY + + /*---------------------. + | Operators on edges. | + `---------------------*/ + + namespace util + { + + template <typename G> + inline + edge<G>::edge() + : g_(0), id_(0) + { + } + + template <typename G> + inline + edge<G>::edge(graph_t *g) + : g_(g), id_(g->e_nmax()) + { + } + + template <typename G> + inline + edge<G>::edge(graph_t *g, unsigned id) + : g_(g), id_(id) + { + mln_precondition(g->has_e(id)); + } + + template <typename G> + inline + unsigned + edge<G>::id() const + { + return id_; + } + + template <typename G> + inline + void + edge<G>::update_id(unsigned id) + { + id_ = id; + } + + template <typename G> + inline + const typename edge<G>::graph_t * const + edge<G>::g() const + { + return g_; + } + + template <typename G> + inline + unsigned + edge<G>::v_other(unsigned id_v) const + { + mln_precondition(v1() == id_v || v2() == id_v); + return g_->v_other(id_, id_v); + } + + template <typename G> + inline + bool + edge<G>::is_valid() const + { + return g_ != 0 && g_->has_e(id_); + } + + template <typename G> + inline + unsigned + edge<G>::v1() const + { + mln_precondition(g_->has_e(id_)); + return g_->v1(id_); + } + + template <typename G> + inline + unsigned + edge<G>::v2() const + { + mln_precondition(g_->has_e(id_)); + return g_->v2(id_); + } + + template <typename G> + inline + size_t + edge<G>::nmax_nbh_edges() const + { + mln_precondition(g_->has_e(id_)); + return g_->e_nmax_nbh_edges(id_); + } + + template <typename G> + inline + unsigned + edge<G>::ith_nbh_edge(unsigned i) const + { + mln_precondition(g_->has_e(id_)); + return g_->e_ith_nbh_edge(id_, i); + } + + + + template <typename G> + inline + bool + operator==(const util::edge<G>& lhs, const util::edge<G>& rhs) + { + return lhs.pair_vertex_ == rhs.pair_vertex_; + } + + template <typename G> + inline + bool + operator< (const util::edge<G>& lhs, const util::edge<G>& rhs) + { + return lhs.pair_vertex_ < rhs.pair_vertex_; + } + + } // end of namespace mln::util + + namespace internal + { + + /*----------------------------------` + | subject_impl< const util::edge<G> | + \----------------------------------*/ + + template <typename G, typename E> + inline + const E& + subject_impl< const util::edge<G>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::id() const + { + return exact_().get_subject().id(); + } + + template <typename G, typename E> + inline + const mlc_const(G) * const + subject_impl< const util::edge<G>, E >::g() const + { + return exact_().get_subject().g(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v_other(unsigned id_v) const + { + return exact_().get_subject().v_other(id_v); + } + + template <typename G, typename E> + inline + bool + subject_impl< const util::edge<G>, E >::is_valid() const + { + return exact_().get_subject().is_valid(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v1() const + { + return exact_().get_subject().v1(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v2() const + { + return exact_().get_subject().v2(); + } + + template <typename G, typename E> + inline + size_t + subject_impl< const util::edge<G>, E >::nmax_nbh_edges() const + { + return exact_().get_subject().nmax_nbh_edges(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::ith_nbh_edge(unsigned i) const + { + return exact_().get_subject().ith_nbh_edge(i); + } + + + /*----------------------------------` + | subject_impl< util::edge<G> | + \----------------------------------*/ + + template <typename G, typename E> + inline + void + subject_impl< util::edge<G>, E >::update_id(unsigned id) + { + return exact_().get_subject().update_id(id); + } + + } // End of namespace mln::internal + +# endif // !MLN_INCLUDE_ONLY + +} // End of namespace mln + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_HH + diff --git a/milena/mln/util/internal/graph_edge_iter.hh b/milena/mln/util/internal/graph_edge_iter.hh new file mode 100644 index 0000000..9bcf9ff --- /dev/null +++ b/milena/mln/util/internal/graph_edge_iter.hh @@ -0,0 +1,273 @@ +// 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. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH + +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/util/internal/graph_edge.hh> + +/// \file mln/util/internal/graph_edge_iter.hh +/// \brief Implementation for graph edge iterators. + +namespace mln +{ + + namespace internal + { + + /// Forward edge iterator. + template <typename G> + class edge_fwd_iterator + : public Proxy< edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, edge_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + edge_fwd_iterator(); + edge_fwd_iterator(const G& g); + /// \} + + /// Iterator interface + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + util::edge<G> e_; + }; + + template <typename G> + class edge_bkd_iterator + : public Proxy< edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, edge_bkd_iterator<G> > + { + public: + /// Constructors. + /// \{ + edge_bkd_iterator(); + edge_bkd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + util::edge<G> e_; + }; + + } // End of namespace mln::internal + +} // End of namespace mln + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace internal + { + + template <typename G> + inline + edge_fwd_iterator<G>::edge_fwd_iterator() + { + } + + template <typename G> + inline + edge_fwd_iterator<G>::edge_fwd_iterator(const G& g) + : e_(util::edge<G>(&g)) + { + invalidate(); + } + + template <typename G> + inline + bool + edge_fwd_iterator<G>::is_valid() const + { + return e_.is_valid(); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::start() + { + e_.update_id(0); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::next() + { + e_.update_id(e_.id() + 1); + } + + template <typename G> + inline + unsigned + edge_fwd_iterator<G>::index() const + { + return e_.id(); + } + + template <typename G> + inline + const util::edge<G>& + edge_fwd_iterator<G>::subj_() + { + return e_; + } + + + + /*------------------` + | edge_bkd_iterator | + \------------------*/ + + template <typename G> + inline + edge_bkd_iterator<G>::edge_bkd_iterator() + { + } + + template <typename G> + inline + edge_bkd_iterator<G>::edge_bkd_iterator(const G& g) + : e_(util::edge<G>(&g)) + { + invalidate(); + } + + template <typename G> + inline + bool + edge_bkd_iterator<G>::is_valid() const + { + return e_.is_valid(); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::start() + { + e_.update_id(e_.g()->e_nmax() - 1); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::next() + { + e_.update_id(e_.id() - 1); + } + + template <typename G> + inline + unsigned + edge_bkd_iterator<G>::index() const + { + return e_.id(); + } + + template <typename G> + inline + const util::edge<G>& + edge_bkd_iterator<G>::subj_() + { + return e_; + } + + } // End of namespace mln::internal + +} // End of namespace mln + +# endif // !MLN_INCLUDE_ONLY + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh new file mode 100644 index 0000000..084ad23 --- /dev/null +++ b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh @@ -0,0 +1,335 @@ +// 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. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_edge_nbh_edge_iter.hh +/// \brief Implementation for graph edge iterators centered to an edge. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class edge_nbh_edge_fwd_iterator + : public Proxy< edge_nbh_edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, edge_nbh_edge_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + edge_nbh_edge_fwd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + + const util::edge<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + template <typename G> + class edge_nbh_edge_bkd_iterator + : public Proxy< edge_nbh_edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, edge_nbh_edge_bkd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + edge_nbh_edge_bkd_iterator(const C& e); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::edge<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename G> + template <typename C> + inline + edge_nbh_edge_fwd_iterator<G>::edge_nbh_edge_fwd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(e.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + edge_nbh_edge_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + edge_nbh_edge_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + edge_nbh_edge_fwd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + + // We shall encounter vertices which are part of the + // current edge. + // We do not want them to be part of the edge neighbors. + unsigned e_id = c_->ith_nbh_edge(i_); + while (e_id == c_->id()) + e_id = c_->ith_nbh_edge(++i_); + + e_.update_id(e_id); + } + + template <typename G> + template <typename E> + inline + void + edge_nbh_edge_fwd_iterator<G>::center_at(const E& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + + /*---------------------------` + | edge_nbh_edge_bkd_iterator | + \---------------------------*/ + + template <typename G> + template <typename C> + inline + edge_nbh_edge_bkd_iterator<G>::edge_nbh_edge_bkd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(e.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + edge_nbh_edge_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + edge_nbh_edge_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + edge_nbh_edge_bkd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + + // We shall encounter vertices which are part of the + // current edge. + // We do not want them to be part of the edge neighbors. + unsigned e_id = c_->ith_nbh_edge(i_); + while (e_id == c_->id()) + e_id = c_->ith_nbh_edge(--i_); + + e_.update_id(e_id); + } + + template <typename G> + template <typename E> + inline + void + edge_nbh_edge_bkd_iterator<G>::center_at(const E& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex.hh b/milena/mln/util/internal/graph_vertex.hh new file mode 100644 index 0000000..c40bf0f --- /dev/null +++ b/milena/mln/util/internal/graph_vertex.hh @@ -0,0 +1,361 @@ +// 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_UTIL_INTERNAL_GRAPH_VERTEX_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH + +/// \file mln/util/internal/graph_vertex.hh +/// \brief Implementation of a graph vertex. + +namespace mln +{ + + namespace util + { + + /// \brief Vertex of a graph \p G. + template<typename G> + class vertex + { + typedef mlc_const(G) graph_t; + + public: + + /// Constructors. + /// \{ + vertex(); + explicit vertex(graph_t *g); + vertex(graph_t *g, unsigned id); + /// \} + + /// Check whether the vertex is still part of the graph. + bool is_valid() const; + + unsigned other(unsigned id_e) const; + + /// Returns the ith edge starting from this vertex. + unsigned ith_nbh_edge(unsigned i) const; + + /// Returns the number max of edges starting from this vertex. + /// If g_ is a sub graph of another graph, nmax will be retrived from + /// the initial graph. + unsigned nmax_nbh_edges() const; + + /// Returns the ith vertex adjacent to this vertex. + unsigned ith_nbh_vertex(unsigned i) const; + + /// Returns the number max of vertices adjacent to this vertex. + unsigned nmax_nbh_vertices() const; + + /// Change the parent graph of that vertex. + void change_graph(const G& g); + + /// Update vertex id. + void update_id(unsigned id); + + /// Returns the graph pointer this vertex belongs to. + const graph_t * const g() const; + + /// Returns vertex id. + unsigned id() const; + + private: + graph_t * const g_; + unsigned id_; + }; + + } // End of namespace mln::util + + +/// subject_impl specialization (Proxy) +/// \{ + namespace internal + { + template <typename G, typename E> + struct subject_impl< const util::vertex<G>, E > + { + bool is_valid() const; + const mlc_const(G) * const g() const; + unsigned id() const; + + unsigned other(unsigned id_e) const; + unsigned ith_nbh_edge(unsigned i) const; + unsigned nmax_nbh_edges() const; + unsigned ith_nbh_vertex(unsigned i) const; + unsigned nmax_nbh_vertices() const; + + private: + const E& exact_() const; + }; + + template <typename G, typename E> + struct subject_impl< util::vertex<G>, E > : + subject_impl< const util::vertex<G>, E > + { + void change_graph(const G& g); + void update_id(unsigned id); + + private: + E& exact_(); + }; + + } // end of namespace mln::internal + +} // End of namespace mln +/// \} + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace util + { + + template <typename G> + inline + vertex<G>::vertex() + : g_(0), id_(0) + { + } + + template <typename G> + inline + vertex<G>::vertex(graph_t *g) + : g_(g), id_(g_->v_nmax()) + { + } + + template<typename G> + inline + vertex<G>::vertex(graph_t *g, unsigned id) + : g_(g), id_(id) + { + mln_precondition(g_->has_v(id)); + } + + template<typename G> + inline + bool + vertex<G>::is_valid() const + { + return g_ != 0 && g_->has_v(id_); + } + + template<typename G> + inline + unsigned + vertex<G>::other(unsigned id_e) const + { + mln_precondition(g_->has_v(id_)); + mln_precondition(g_->has_e(id_e)); + mln_precondition(g_->v1(id_e) == id_ || g_->v2(id_e) == id_); + return g_->v_other(id_e, id_); + } + + template<typename G> + inline + unsigned + vertex<G>::ith_nbh_edge(unsigned i) const + { + mln_precondition(g_->has_v(id_)); + return g_->v_ith_nbh_edge(id_, i); + } + + template<typename G> + inline + unsigned + vertex<G>::nmax_nbh_edges() const + { + mln_precondition(g_->has_v(id_)); + return g_->v_nmax_nbh_edges(id_); + } + + template<typename G> + inline + unsigned + vertex<G>::ith_nbh_vertex(unsigned i) const + { + mln_precondition(g_->has_v(id_)); + return g_->v_ith_nbh_vertex(id_, i); + } + + template<typename G> + inline + unsigned + vertex<G>::nmax_nbh_vertices() const + { + mln_precondition(g_->has_v(id_)); + return g_->v_nmax_nbh_vertices(id_); + } + + template<typename G> + inline + void + vertex<G>::change_graph(const G& g) + { + mln_precondition(g_->has_v(id_)); + g_ = &g; + } + + template<typename G> + inline + void + vertex<G>::update_id(unsigned id) + { + id_ = id; + } + + template<typename G> + inline + const typename vertex<G>::graph_t * const + vertex<G>::g() const + { + return g_; + } + + template<typename G> + inline + unsigned + vertex<G>::id() const + { + return id_; + } + + } // end of namespace mln::util + + namespace internal + { + + template <typename G, typename E> + inline + const E& + subject_impl< const util::vertex<G>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename G, typename E> + inline + bool + subject_impl< const util::vertex<G>, E >::is_valid() const + { + return exact_().get_subject().is_valid(); + } + + template <typename G, typename E> + inline + const mlc_const(G)* const + subject_impl< const util::vertex<G>, E >::g() const + { + return exact_().get_subject().g(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::id() const + { + return exact_().get_subject().id(); + }; + + + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::other(unsigned id_e) const + { + return exact_().get_subject().other(id_e); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::ith_nbh_edge(unsigned i) const + { + return exact_().get_subject().ith_nbh_edge(i); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::nmax_nbh_edges() const + { + return exact_().get_subject().nmax_nbh_edges(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::ith_nbh_vertex(unsigned i) const + { + return exact_().get_subject().ith_nbh_vertex(i); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::nmax_nbh_vertices() const + { + return exact_().get_subject().nmax_nbh_vertices(); + } + + template <typename G, typename E> + inline + E& + subject_impl< util::vertex<G>, E >::exact_() + { + return internal::force_exact<E>(*this); + } + + template <typename G, typename E> + inline + void + subject_impl< util::vertex<G>, E >::change_graph(const G& g) + { + exact_().get_subject().change_graph(g); + } + + template <typename G, typename E> + inline + void + subject_impl< util::vertex<G>, E >::update_id(unsigned id) + { + exact_().get_subject().update_id(id); + }; + + } // end of namespace mln::internal + +} // End of namespace mln + +# endif // !MLN_INCLUDE_ONLY + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH + diff --git a/milena/mln/util/internal/graph_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_iter.hh new file mode 100644 index 0000000..9d2f3df --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_iter.hh @@ -0,0 +1,266 @@ +// 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. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH + +# include <mln/metal/const.hh> +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/util/internal/graph_base.hh> + +/// \file mln/util/internal/graph_vertex_iter.hh +/// \brief Implementation for graph vertex iterators. + +namespace mln +{ + + namespace internal + { + + template<typename G> + class vertex_fwd_iterator + : public Proxy< vertex_fwd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + vertex_fwd_iterator(); + vertex_fwd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + util::vertex<G> v_; + }; + + template<typename G> + class vertex_bkd_iterator + : public Proxy< vertex_bkd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + vertex_bkd_iterator(); + vertex_bkd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + util::vertex<G> v_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + /*--------------------` + | vertex_fwd_iterator | + \--------------------*/ + + template<typename G> + inline + vertex_fwd_iterator<G>::vertex_fwd_iterator() + { + } + + template<typename G> + inline + vertex_fwd_iterator<G>::vertex_fwd_iterator(const G& g) + : v_(util::vertex<G>(&g)) + { + invalidate(); + } + + template<typename G> + inline + bool + vertex_fwd_iterator<G>::is_valid() const + { + return v_.is_valid(); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->v_nmax()); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::start() + { + v_.update_id(0); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::next() + { + v_.update_id(v_.id() + 1); + } + + template<typename G> + inline + unsigned + vertex_fwd_iterator<G>::index() const + { + return v_.id(); + } + + template<typename G> + inline + const util::vertex<G>& + vertex_fwd_iterator<G>::subj_() + { + return v_; + } + + + /*--------------------` + | vertex_bkd_iterator | + \--------------------*/ + + template<typename G> + inline + vertex_bkd_iterator<G>::vertex_bkd_iterator() + { + } + + template<typename G> + inline + vertex_bkd_iterator<G>::vertex_bkd_iterator(const G& g) + : v_(util::vertex<G>(&g)) + { + invalidate(); + } + + template<typename G> + inline + bool + vertex_bkd_iterator<G>::is_valid() const + { + return v_.is_valid(); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->v_nmax()); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::start() + { + v_.update_id(v_.g()->v_nmax() - 1); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::next() + { + v_.update_id(v_.id() - 1); + } + + template<typename G> + inline + unsigned + vertex_bkd_iterator<G>::index() const + { + return v_.id(); + } + + template<typename G> + inline + const util::vertex<G>& + vertex_bkd_iterator<G>::subj_() + { + return v_; + } +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh new file mode 100644 index 0000000..4edc652 --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh @@ -0,0 +1,323 @@ +// 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. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_EDGE_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_vertex_nbh_edge_iter.hh +/// \brief Implementation for graph edge iterators centered to a vertex. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class vertex_nbh_edge_fwd_iterator + : public Proxy< vertex_nbh_edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, vertex_nbh_edge_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + vertex_nbh_edge_fwd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; // Center + util::edge<G> e_; + unsigned i_; + }; + + template <typename G> + class vertex_nbh_edge_bkd_iterator + : public Proxy< vertex_nbh_edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, vertex_nbh_edge_bkd_iterator<G> > + { + public: + /// Constructors. + /// \{ + template <typename C> + vertex_nbh_edge_bkd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename G> + template <typename C> + inline + vertex_nbh_edge_fwd_iterator<G>::vertex_nbh_edge_fwd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_edge_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_edge_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + vertex_nbh_edge_fwd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + e_.update_id(c_->ith_nbh_edge(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_edge_fwd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + + + /*-----------------------------` + | vertex_nbh_edge_bkd_iterator | + \-----------------------------*/ + + + template <typename G> + template <typename C> + inline + vertex_nbh_edge_bkd_iterator<G>::vertex_nbh_edge_bkd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_edge_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_edge_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + vertex_nbh_edge_bkd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + e_.update_id(c_->ith_nbh_edge(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_edge_bkd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_NBH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh new file mode 100644 index 0000000..d51bc29 --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh @@ -0,0 +1,320 @@ +// 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. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_vertex_nbh_vertex_iter.hh +/// \brief Implementation for graph vertex iterators centered to a vertex. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class vertex_nbh_vertex_fwd_iterator + : public Proxy< vertex_nbh_vertex_fwd_iterator<G> >, + public internal::proxy_impl< const util::vertex<G>&, vertex_nbh_vertex_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + vertex_nbh_vertex_fwd_iterator(const C& c); + /// \} + + /// 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 value. + void next(); + + /// Return current index + unsigned index() const; + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; + util::vertex<G> v_; + unsigned i_; + }; + + template <typename G> + class vertex_nbh_vertex_bkd_iterator + : public Proxy< vertex_nbh_vertex_bkd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_nbh_vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + template <typename C> + vertex_nbh_vertex_bkd_iterator(const C& v); + /// \} + + /// 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 value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; //Center + util::vertex<G> v_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename G> + template <typename C> + inline + vertex_nbh_vertex_fwd_iterator<G>::vertex_nbh_vertex_fwd_iterator(const C& c) + : v_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_vertex_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_vertices(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::invalidate() + { + i_ = v_.g()->v_nmax(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_vertex_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::vertex<G>& + vertex_nbh_vertex_fwd_iterator<G>::subj_() + { + return v_; + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + v_.update_id(c_->ith_nbh_vertex(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + /*-------------------------------` + | vertex_nbh_vertex_bkd_iterator | + \-------------------------------*/ + + + template <typename G> + template <typename C> + inline + vertex_nbh_vertex_bkd_iterator<G>::vertex_nbh_vertex_bkd_iterator(const C& c) + : v_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_vertex_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_vertices(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->e_nmax()); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_vertex_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::vertex<G>& + vertex_nbh_vertex_bkd_iterator<G>::subj_() + { + return v_; + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + v_.update_id(c_->ith_nbh_vertex(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH + diff --git a/milena/tests/util/graph.cc b/milena/tests/util/graph.cc index d20b02d..60a609a 100644 --- a/milena/tests/util/graph.cc +++ b/milena/tests/util/graph.cc @@ -35,7 +35,7 @@ int main () { using namespace mln; - util::graph<void> g; + util::graph g; g.add_vertex (); // 0 g.add_vertex (); // 1 @@ -51,4 +51,109 @@ int main () g.add_edge (1, 0); g.add_edge (5, 3); g.add_edge (2, 1); + + + // Vertex iter and edge iter + { + unsigned i = 0; + mln_vertex_fwd_iter_(util::graph) v(g); + for_all(v) + mln_assertion(i++ == v.index()); + mln_assertion(i != 0); + + i = 0; + mln_edge_fwd_iter_(util::graph) e(g); + for_all(e) + mln_assertion(i++ == e.index()); + mln_assertion(i != 0); + } + { + unsigned i = g.v_nmax() - 1; + mln_vertex_bkd_iter_(util::graph) v(g); + for_all(v) + mln_assertion(i-- == v.index()); + mln_assertion(i != g.v_nmax() - 1); + + i = g.e_nmax() - 1; + mln_edge_bkd_iter_(util::graph) e(g); + for_all(e) + mln_assertion(i-- == e.index()); + mln_assertion(i != g.e_nmax() - 1); + } + + // vertex iter + Edge nbh iter + { + mln_vertex_fwd_iter_(util::graph) v(g); + mln_vertex_nbh_edge_fwd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = 0; + for_all(n) + mln_assertion(i++ == n.index()); + mln_assertion(i != 0); + } + } + { + mln_vertex_bkd_iter_(util::graph) v(g); + mln_vertex_nbh_edge_bkd_iter_(util::graph) e(v); + for_all(v) + { + unsigned i = v.nmax_nbh_edges(); + for_all(e) + mln_assertion(--i == e.index()); + mln_assertion((v.nmax_nbh_edges() == 0 && i == 0) || i != v.nmax_nbh_edges()); + } + } + + { + mln_edge_fwd_iter_(util::graph) e(g); + mln_edge_nbh_edge_fwd_iter_(util::graph) n(e); + for_all(e) + { + unsigned i = 0; + for_all(n) + ++i; + // we check i == e.nmax_nbh_edges() - 2 since e is it's own neighboor and the + // iterator skip it. + mln_assertion((i == 0 && e.nmax_nbh_edges() < 2) || i == e.nmax_nbh_edges() - 2); + } + } + { + mln_edge_bkd_iter_(util::graph) e(g); + mln_edge_nbh_edge_bkd_iter_(util::graph) n(e); + for_all(e) + { + //std::cout << "== e.id() = " << e.id() << std::endl; + unsigned i = e.nmax_nbh_edges(); + for_all(n) + --i; + // we check i == e.nmax_nbh_edges() - 2 since e is it's own neighboor and the + // iterator skip it. + mln_assertion((i == e.nmax_nbh_edges() && e.nmax_nbh_edges() < 2) || i == 2); + + } + } + + { + mln_vertex_fwd_iter_(util::graph) v(g); + mln_vertex_nbh_vertex_fwd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = 0; + for_all(n) + ++i; + mln_assertion(i == v.nmax_nbh_vertices()); + } + } + { + mln_vertex_bkd_iter_(util::graph) v(g); + mln_vertex_nbh_vertex_bkd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = v.nmax_nbh_vertices(); + for_all(n) + --i; + mln_assertion(i == 0); + } + } } -- 1.5.6.5

1 0

cleanup-2008 2447: Add traits for windows and factor code.
by Thierry Geraud 30 Sep '08

30 Sep '08

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add traits for windows and factor code. * mln/trait/windows.hh: New. * mln/trait/window: New. * mln/trait/window/props.hh: New. * mln/trait/window/print.hh: New. * mln/core/macros.hh (mln_regular): New. * mln/core/neighb.hh (operator<<): New. * mln/core/concept/weighted_window.hh (include): Update. * mln/core/concept/neighborhood.hh: Likewise. * mln/core/concept/window.hh: Likewise. (window_size_check, window_support_check): New. (window_definition_check): New. (operator<<): New. * mln/core/concept/object.hh: New metal include. * mln/core/internal/dpsites_impl.hh: Rename as... * mln/core/internal/classical_window_base.hh: ...this. (is_centered, is_symmetric, sym): New. (delta): Rely on... (delta_): ...this new method. (print, print_): New. * mln/geom/shift.hh: Revamp. * mln/core/window.hh, * mln/win/cube3d.hh, * mln/win/line.hh, * mln/win/rectangle2d.hh, * mln/win/diag2d.hh, * mln/win/backdiag2d.hh, * mln/win/multiple.hh, * mln/win/cuboid3d.hh, * mln/win/octagon2d.hh, * mln/win/disk2d.hh: Update and factor code. core/concept/neighborhood.hh | 1 core/concept/object.hh | 1 core/concept/weighted_window.hh | 1 core/concept/window.hh | 154 ++++++++++++++++++++++++++++++++- core/internal/classical_window_base.hh | 136 +++++++++++++++++++++-------- core/macros.hh | 6 + core/neighb.hh | 7 + core/window.hh | 43 ++++++--- geom/shift.hh | 53 +++++++++-- trait/window/print.hh | 119 +++++++++++++++++++++++++ trait/window/props.hh | 136 +++++++++++++++++++++++++++++ trait/windows.hh | 113 ++++++++++++++++++++++++ win/backdiag2d.hh | 64 ++----------- win/cube3d.hh | 64 ++----------- win/cuboid3d.hh | 69 ++------------ win/diag2d.hh | 64 ++----------- win/disk2d.hh | 66 ++------------ win/line.hh | 87 ++++++------------ win/multiple.hh | 96 +++++++++++++++----- win/octagon2d.hh | 64 ++----------- win/rectangle2d.hh | 68 ++------------ 21 files changed, 893 insertions(+), 519 deletions(-) Index: mln/trait/windows.hh --- mln/trait/windows.hh (revision 0) +++ mln/trait/windows.hh (revision 0) @@ -0,0 +1,113 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_TRAIT_WINDOWS_HH +# define MLN_TRAIT_WINDOWS_HH + +/*! \file mln/trait/windows.hh + * + * \brief Some base trait types for windows. + */ + +# include <mln/trait/undef.hh> +# include <mln/trait/window/props.hh> + + +/// Shortcut to the window property about the 'size' method presence. +# define mln_trait_window_size(W) typename mln::trait::window_< W >::size + +/// Shortcut to the window property about the 'support' it is designed for. +# define mln_trait_window_support(W) typename mln::trait::window_< W >::support + +/// Shortcut to the window property about its definition. +# define mln_trait_window_definition(W) typename mln::trait::window_< W >::definition + + +# define mln_internal_add_classical_window_trait(W) \ + \ + namespace win { struct W; } \ + \ + namespace trait \ + { \ + \ + template <> \ + struct window_< win::W > : classical_window_ \ + { \ + }; \ + \ + } \ + \ + struct e_n_d__w_i_t_h__s_e_m_i_c_o_l_u_m_n + + +namespace mln +{ + + namespace trait + { + + /// Pack of 'undefined' type values for properties of windows. + template <typename W> + struct undefined_window_ + { + typedef undef size; // Fixed or unknown. + typedef undef support; // Regular or irregular. + typedef undef definition; // Unique, n_ary, or varying. + }; + + + /*! \brief The trait pack structure for properties of windows. + * + * This structure is specialized for every concrete class of site + * set so that properties are properly defined. + * + * \see mln::doc::Window for the documentation of the "window" + * concept. + */ + template <typename W> + struct window_ : undefined_window_<W> + { + }; + + + // \internal Trait for classical windows. + struct classical_window_ + { + typedef mln::trait::window::size::fixed size; + typedef mln::trait::window::support::regular support; + typedef mln::trait::window::definition::unique definition; + }; + + } // end of namespace mln::trait + +} // end of namespace mln + + +# include <mln/trait/window/print.hh> + + +#endif // ! MLN_TRAIT_WINDOWS_HH Index: mln/trait/window/props.hh --- mln/trait/window/props.hh (revision 0) +++ mln/trait/window/props.hh (revision 0) @@ -0,0 +1,136 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_TRAIT_WINDOW_PROPS_HH +# define MLN_TRAIT_WINDOW_PROPS_HH + +/*! \file mln/trait/window/props.hh + * + * \brief Properties of window classes. + * + * \todo Precise the differences (?) between dynamic, growing, and + * free... + */ + +# include <string> +# include <mln/trait/undef.hh> + + + +// Properties of windows. +// ======================== + +// size: /any/ +// | +// + -- fixed +// | +// + -- unknown + +// support: /any/ +// | +// + -- regular +// | +// + -- irregular + +// definition: /any/ +// | +// + -- unique +// | +// + -- /multiple/ +// | +// + -- n_ary +// | +// + -- varying + + +namespace mln +{ + + namespace trait + { + + namespace window + { + + + /// Window property about the 'size' method presence. + struct size + { + /// Base class for the window 'size' property. + struct any { protected: any() {} }; + + /// Property that states that the size is fixed. + struct fixed : any { std::string name() const { return "size::fixed"; } }; + + /// Property that states that the size is not fixed so unknown. + struct unknown : any { std::string name() const { return "size::unknown"; } }; + }; + + + /// Window property about the 'support' it is designed for. + struct support + { + /// Base class for the window 'support' property. + struct any { protected: any() {} }; + + /// Property that states that the window is designed for a regular support. + struct regular : any { std::string name() const { return "support::regular"; } }; + + /// Property that states that the window is not designed for a regular support. + struct irregular : any { std::string name() const { return "support::irregular"; } }; + }; + + + /// Window property about how the window is defined. + struct definition + { + /// Base class for the window 'definition' property. + struct any { protected: any() {} }; + + /// Property that states that the definition is unique. + struct unique : any { std::string name() const { return "definition::unique"; } }; + + /// Abstract property that states that the definition is multiple. + struct multiple : any { protected: multiple() {} }; + + /// Property that states that this window has n definitions. + struct n_ary : multiple { std::string name() const { return "definition::n_ary"; } }; + + /// Property that states that this window has a varying definition. + struct varying : multiple { std::string name() const { return "definition::varying"; } }; + }; + + + } // end of namespace mln::trait::window + + } // end of namespace mln::trait + + +} // end of namespace mln + + +#endif // ! MLN_TRAIT_WINDOW_PROPS_HH Index: mln/trait/window/print.hh --- mln/trait/window/print.hh (revision 0) +++ mln/trait/window/print.hh (revision 0) @@ -0,0 +1,119 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// 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. + +#ifndef MLN_TRAIT_WINDOW_PRINT_HH +# define MLN_TRAIT_WINDOW_PRINT_HH + +/*! \file mln/trait/window/print.hh + * + * \brief Print the collection of traits for a window type. + */ + +# include <iostream> + +# include <mln/trait/windows.hh> +# include <mln/metal/is_a.hh> +# include <mln/metal/bexpr.hh> + + + +namespace mln +{ + + // Forward declaration. + template <typename E> struct Window; + template <typename E> struct Weighted_Window; + template <typename E> struct Neighborhood; + + + namespace trait + { + + namespace window + { + + template <typename T> + void print(std::ostream& ostr = std::cout); + + template <typename T> + void print(const Neighborhood<T>& nbh, std::ostream& ostr = std::cout); + + template <typename T> + void print(const Window<T>& win, std::ostream& ostr = std::cout); + + template <typename T> + void print(const Weighted_Window<T>& w_win, std::ostream& ostr = std::cout); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T> + inline + void print(std::ostream& ostr) + { + metal::or_< mlc_is_a(T, Neighborhood), + metal::or_< mlc_is_a(T, Window), + mlc_is_a(T, Weighted_Window) > + >::check(); + typedef mln::trait::window_<T> the; + ostr << "{ " + << typename the::size() .name() << ", " + << typename the::support() .name() << ", " + << typename the::definition() .name() << " }" << std::endl; + } + + template <typename T> + inline + void print(const Neighborhood<T>&, std::ostream& ostr) + { + print<T>(ostr); + } + + template <typename T> + inline + void print(const Window<T>&, std::ostream& ostr) + { + print<T>(ostr); + } + + template <typename T> + inline + void print(const Weighted_Window<T>&, std::ostream& ostr) + { + print<T>(ostr); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::trait::window + + } // end of namespace mln::trait + +} // end of namespace mln + + +#endif // ! MLN_TRAIT_WINDOW_PRINT_HH Index: mln/core/macros.hh --- mln/core/macros.hh (revision 2446) +++ mln/core/macros.hh (working copy) @@ -299,6 +299,12 @@ # define mln_r_element_(T) T::r_element /// \} +/// Shortcuts to access the regular type associated to T. +/// \{ +# define mln_regular(T) typename T::regular +# define mln_regular_(T) T::regular +/// \} + /// Shortcuts to access the result type associated to T. /// \{ # define mln_result(T) typename T::result Index: mln/core/neighb.hh --- mln/core/neighb.hh (revision 2446) +++ mln/core/neighb.hh (working copy) @@ -105,6 +105,13 @@ }; + template <typename W> + inline + std::ostream& operator<<(std::ostream&ostr, const neighb<W>& nbh) + { + return ostr << nbh.win(); + } + namespace convert { Index: mln/core/concept/weighted_window.hh --- mln/core/concept/weighted_window.hh (revision 2446) +++ mln/core/concept/weighted_window.hh (working copy) @@ -35,6 +35,7 @@ # include <mln/core/concept/object.hh> # include <mln/core/concept/iterator.hh> +# include <mln/trait/windows.hh> namespace mln Index: mln/core/concept/object.hh --- mln/core/concept/object.hh (revision 2446) +++ mln/core/concept/object.hh (working copy) @@ -43,6 +43,7 @@ # include <mln/trace/all.hh> # include <mln/metal/is_a.hh> # include <mln/metal/is.hh> +# include <mln/metal/is_not.hh> # include <mln/metal/ret.hh> Index: mln/core/concept/neighborhood.hh --- mln/core/concept/neighborhood.hh (revision 2446) +++ mln/core/concept/neighborhood.hh (working copy) @@ -33,6 +33,7 @@ */ # include <mln/core/concept/object.hh> +# include <mln/trait/windows.hh> namespace mln Index: mln/core/concept/window.hh --- mln/core/concept/window.hh (revision 2446) +++ mln/core/concept/window.hh (working copy) @@ -32,10 +32,13 @@ * \brief Definition of the concept of mln::Window. * * \todo Operator== should test if the cmp is possible. + * + * \todo Activate run_extra() below. */ # include <mln/core/concept/object.hh> # include <mln/core/concept/iterator.hh> +# include <mln/trait/windows.hh> # include <mln/core/site_set/p_array.hh> @@ -82,20 +85,124 @@ bool operator==(const Window<Wl>& lhs, const Window<Wr>& rhs); + template <typename W> + std::ostream& operator<<(std::ostream& ostr, const Window<W>& win); + + # ifndef MLN_INCLUDE_ONLY + namespace internal + { + + // size: fixed or unknown. + + template <typename trait_size, typename E> + struct window_size_check + { + static void run() { /* No requirement. */ } + }; + + template <typename E> + struct window_size_check< mln::trait::window::size::fixed, E > + { + static void run() + { + unsigned (E::*m)() const = & E::size; + m = 0; + } + }; + + // support: regular or irregular. + + template <typename trait_support, typename E> + struct window_support_check + { + static void run() { /* No requirement. */ } + }; + + template <typename E> + struct window_support_check< mln::trait::window::support::regular, E > + { + static void run_extra() + { + bool (E::*m1)() const = &E::is_centered; + m1 = 0; + bool (E::*m2)() const = &E::is_symmetric; + m2 = 0; + void (E::*m3)() = &E::sym; + m3 = 0; + unsigned (E::*m4)() const = &E::delta; + m4 = 0; + } + static void run(mln::trait::window::definition::unique) + { + typedef mln_dpsite(E) D; + const D& (E::*m)(unsigned) const = &E::dp; + m = 0; + run_extra(); + } + static void run(mln::trait::window::definition::n_ary) + { + // run_extra(); + } + static void run(mln::trait::window::definition::varying) + { + /* No requirement. */ + } + static void run() + { + run(mln_trait_window_definition(E)()); + } + }; + + // definition: unique, n_ary, or varying. + + template <typename trait_definition, typename E> + struct window_definition_check + { + static void run() { /* No requirement. */ } + }; + + template <typename E> + struct window_definition_check< mln::trait::window::definition::multiple, E > + { + static void run() + { + typedef mln_element(E) W; + void (E::*m1)(unsigned, const W&) = &E::set_window; + m1 = 0; + const W& (E::*m2)(unsigned) const = &E::window; + m2 = 0; + unsigned (E::*m3)() const = &E::nwindows; + m3 = 0; + } + }; + + } // end of namespace mln::internal + + template <typename E> inline Window<E>::Window() { + // Check properties. + mlc_not_equal( mln_trait_window_size(E), mln::trait::undef )::check(); + mlc_not_equal( mln_trait_window_support(E), mln::trait::undef )::check(); + mlc_not_equal( mln_trait_window_definition(E), mln::trait::undef )::check(); + + // Check associated types. typedef mln_site(E) site; typedef mln_psite(E) psite; typedef mln_dpsite(E) dpsite; - typedef mln_qiter(E) qiter; typedef mln_fwd_qiter(E) fwd_qiter; typedef mln_bkd_qiter(E) bkd_qiter; + + // Check methods depending upon properties. + internal::window_size_check < mln_trait_window_size(E), E >::run(); + internal::window_support_check < mln_trait_window_support(E), E >::run(); + internal::window_definition_check< mln_trait_window_definition(E), E >::run(); } template <typename Wl, typename Wr> @@ -105,6 +212,51 @@ return exact(lhs).std_vector() == exact(rhs).std_vector(); } + + // Operator <<. + + namespace internal + { + + template <typename W> + inline + void print(trait::window::definition::unique, + std::ostream& ostr, const W& win) // FIXME: Add Window<W> to win? + { + win.print(ostr); + } + + template <typename W> + inline + void print(trait::window::definition::multiple, + std::ostream& ostr, const W& win) // FIXME: Add Window<W> to win? + { + ostr << "["; + const unsigned nw = win.nwindows(); + for (unsigned w = 0; w < nw; ++w) + { + ostr << " #" << w << ':'; + win.window(w).print(ostr); + } + ostr << " ]"; + } + + } // end of namespace mln + + template <typename W> + inline + std::ostream& operator<<(std::ostream& ostr, const Window<W>& win) + { + mlc_is(mln_trait_window_support(W), + trait::window::support::regular)::check(); + mlc_is_not(mln_trait_window_definition(W), + trait::window::definition::varying)::check(); + // FIXME: test on is_empty? + internal::print(mln_trait_window_definition(W)(), + ostr, exact(win)); + return ostr; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/core/window.hh --- mln/core/window.hh (revision 2446) +++ mln/core/window.hh (working copy) @@ -53,11 +53,28 @@ namespace mln { - // Fwd decls. + // Forward declarations. + template <typename D> class window; template <typename V> class dpsites_fwd_piter; template <typename V> class dpsites_bkd_piter; + + namespace trait + { + + template <typename D> + struct window_< mln::window<D> > + { + typedef trait::window::size::fixed size; + typedef trait::window::support::regular support; + typedef trait::window::definition::unique definition; + }; + + } // end of namespace trait + + + /*! \brief Generic window class. * * This type of window is just like a set of delta-points. The @@ -68,6 +85,10 @@ { public: + /// Regular window associated type. + typedef window<D> regular; + + /*! \brief Constructor without argument. * * The constructed window is empty. @@ -154,17 +175,15 @@ /// Hook to the set of D. const util::set<D>& dps_hook_() const; + /// Print the window definition into \p ostr. + void print(std::ostream& ostr) const; + private: util::set<D> dps_; }; - // FIXME: Doc! - template <typename D> - std::ostream& operator<<(std::ostream& ostr, const window<D>& win); - - /*! \brief Equality comparison between windows \p lhs and \p rhs. * @@ -347,15 +366,17 @@ return dps_; } - // Operators. - template <typename D> - std::ostream& - operator<<(std::ostream& ostr, const window<D>& win) + inline + void + window<D>::print(std::ostream& ostr) const { - return ostr << win.dps_hook_(); + ostr << dps_; } + + // Operators. + template <typename D> bool operator==(const window<D>& lhs, const window<D>& rhs) Index: mln/core/internal/classical_window_base.hh --- mln/core/internal/classical_window_base.hh (revision 2440) +++ mln/core/internal/classical_window_base.hh (working copy) @@ -25,16 +25,17 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_CORE_INTERNAL_DPSITES_IMPL_HH -# define MLN_CORE_INTERNAL_DPSITES_IMPL_HH +#ifndef MLN_CORE_INTERNAL_CLASSICAL_WINDOW_BASE_HH +# define MLN_CORE_INTERNAL_CLASSICAL_WINDOW_BASE_HH -/*! \file mln/core/internal/dpsites_impl.hh +/*! \file mln/core/internal/classical_window_base.hh * * \brief Definition of a base class for classes based on a set of dpoints. * - * \todo Rename as dpsites_impl. - * * \todo Remove the .vect() method. + * + * \todo Add a test that overridden delta_() and win.delta() give the + * same result. */ # include <mln/core/window.hh> @@ -52,10 +53,15 @@ * */ template <typename D, typename E> - class dpsites_impl + class classical_window_base : public window_base<D, E> { public: + + /// Regular window associated type. + typedef window<D> regular; + + /// Forward site iterator associated type. typedef dpsites_fwd_piter<E> fwd_qiter; @@ -66,41 +72,50 @@ typedef fwd_qiter qiter; - /*! \brief Test if the window is centered. - * - * \return True if the delta-point 0 belongs to the window. - */ - bool is_centered() const; + /// Give the number of delta-points. + unsigned size() const; - /*! \brief Test if the window is empty (null size; no delta-point). - */ + /// Test if the window is empty (null size; no delta-point). bool is_empty() const; - /*! \brief Give the maximum coordinate gap between the window - center and a window point. - */ + + /// Test if the window is centered; return true. + bool is_centered() const; + + /// Test if the window is symmetric; return true. + bool is_symmetric() const; + + /// Apply a central symmetry to the target window; a no-op here. + void sym(); + + + /// Give the maximum coordinate gap between the window center + /// and a window point. unsigned delta() const; - /// Give the number of delta-points. - unsigned size() const; /// Test if the delta-point \p dp belongs to the window. bool has(const D& dp) const; - // Give the \p i-th delta-point. + /// Give the \p i-th delta-point. const D& dp(unsigned i) const; - // Give the vector of delta-points. + /// Give the vector of delta-points. const std::vector<D>& vect() const; - // Give the vector of delta-points. + /// Give the vector of delta-points. const std::vector<D>& std_vector() const; + /// Print into \p ostr the window definition. + void print(std::ostream& ostr) const; + protected: - dpsites_impl(); + classical_window_base(); void insert(const D& d); + unsigned delta_() const; // Default implementation based on win_. + void print_(std::ostream& ostr) const; // Default implementation based on win_. mln::window<D> win_; }; @@ -111,43 +126,76 @@ template <typename D, typename E> inline - dpsites_impl<D,E>::dpsites_impl() + classical_window_base<D,E>::classical_window_base() { } template <typename D, typename E> inline - bool dpsites_impl<D,E>::is_centered() const + unsigned + classical_window_base<D,E>::size() const { - return win_.is_centered(); + return win_.size(); } template <typename D, typename E> inline - bool dpsites_impl<D,E>::is_empty() const + bool + classical_window_base<D,E>::is_empty() const { return win_.is_empty(); } template <typename D, typename E> inline - unsigned dpsites_impl<D,E>::delta() const + bool + classical_window_base<D,E>::is_centered() const { - return win_.delta(); + mln_invariant(win_.is_centered()); + return true; + } + + template <typename D, typename E> + inline + bool + classical_window_base<D,E>::is_symmetric() const + { + mln_invariant(win_.is_symmetric()); + return true; + } + + template <typename D, typename E> + inline + void + classical_window_base<D,E>::sym() + { + mln_invariant(win_.is_symmetric()); + // No-op. } template <typename D, typename E> inline unsigned - dpsites_impl<D,E>::size() const + classical_window_base<D,E>::delta() const { - return win_.size(); + // void *v = (void*)(& classical_window_base<D,E>::delta_); + // void *w = (void*)(& E::delta_); + // std::cout << v << ' ' << w << std::endl; + return exact(this)->delta_(); + } + + template <typename D, typename E> + inline + unsigned + classical_window_base<D,E>::delta_() const + { + return win_.delta(); } template <typename D, typename E> inline const D& - dpsites_impl<D,E>::dp(unsigned i) const + classical_window_base<D,E>::dp(unsigned i) const { mln_precondition(i < size()); return win_.dp(i); @@ -156,7 +204,7 @@ template <typename D, typename E> inline const std::vector<D>& - dpsites_impl<D,E>::std_vector() const + classical_window_base<D,E>::std_vector() const { return win_.std_vector(); } @@ -164,7 +212,7 @@ template <typename D, typename E> inline const std::vector<D>& - dpsites_impl<D,E>::vect() const + classical_window_base<D,E>::vect() const { return std_vector(); } @@ -172,7 +220,7 @@ template <typename D, typename E> inline bool - dpsites_impl<D,E>::has(const D& dp) const + classical_window_base<D,E>::has(const D& dp) const { return win_.has(dp); } @@ -180,11 +228,27 @@ template <typename D, typename E> inline void - dpsites_impl<D,E>::insert(const D& d) + classical_window_base<D,E>::insert(const D& d) { win_.insert(d); } + template <typename D, typename E> + inline + void + classical_window_base<D,E>::print(std::ostream& ostr) const + { + exact(this)->print_(ostr); + } + + template <typename D, typename E> + inline + void + classical_window_base<D,E>::print_(std::ostream& ostr) const + { + ostr << win_; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace internal @@ -192,4 +256,4 @@ } // end of namespace mln -#endif // ! MLN_CORE_INTERNAL_DPSITES_IMPL_HH +#endif // ! MLN_CORE_INTERNAL_CLASSICAL_WINDOW_BASE_HH Index: mln/geom/shift.hh --- mln/geom/shift.hh (revision 2446) +++ mln/geom/shift.hh (working copy) @@ -45,27 +45,66 @@ /// Shift a window \p win with a delta-point \p dp. template <typename W> - window<mln_dpsite(W)> + mln_regular(W) shift(const Window<W>& win, const mln_dpsite(W)& dp); # ifndef MLN_INCLUDE_ONLY + namespace impl + { + template <typename W> inline - window<mln_dpsite(W)> - shift(const Window<W>& win_, const mln_dpsite(W)& dp) + mln_regular(W) + shift_(trait::window::definition::unique, + const W& win, const mln_dpsite(W)& dp) { - mlc_is_a(mln_site(W), Gpoint)::check(); - const W& win = exact(win_); - - window<mln_dpsite(W)> tmp; + mlc_is(mln_trait_window_size(W), + trait::window::size::fixed)::check(); + mln_regular(W) tmp; unsigned n = win.size(); for (unsigned i = 0; i < n; ++i) tmp.insert(win.dp(i) + dp); return tmp; } + template <typename W> + inline + mln_regular(W) + shift_(trait::window::definition::multiple, + const W& win, const mln_dpsite(W)& dp) + { + mln_regular(W) tmp(win.function()); + const unsigned nw = win.nwindows(); + for (unsigned w = 0; w < nw; ++w) + tmp.set_window(w, geom::shift(win.window(w), dp)); + return tmp; + } + + } // end of namespace mln::geom::impl + + + // Facade. + template <typename W> + inline + mln_regular(W) + shift(const Window<W>& win, const mln_dpsite(W)& dp) + { + trace::entering("geom::shift"); + + mlc_is(mln_trait_window_support(W), + trait::window::support::regular)::check(); + mlc_is_not(mln_trait_window_definition(W), + trait::window::definition::varying)::check(); + + mln_regular(W) tmp = impl::shift_(mln_trait_window_definition(W)(), + exact(win), dp); + + trace::exiting("geom::shift"); + return tmp; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::geom Index: mln/win/cube3d.hh --- mln/win/cube3d.hh (revision 2446) +++ mln/win/cube3d.hh (working copy) @@ -33,14 +33,16 @@ * \brief Definition of the mln::win::cube3d window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint3d.hh> namespace mln { + mln_internal_add_classical_window_trait(cube3d); + + namespace win { @@ -63,8 +65,7 @@ * o o o \n * is defined with length = 3. */ - struct cube3d : public internal::window_base< dpoint3d, cube3d >, - public internal::dpsites_impl< dpoint3d, cube3d > + struct cube3d : public internal::classical_window_base< dpoint3d, cube3d > { /*! \brief Constructor. * @@ -74,18 +75,6 @@ */ cube3d(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - /*! \brief Give the cube length, that is, its height. */ unsigned length() const; @@ -93,29 +82,15 @@ /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - cube3d& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print a cube3d window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win A cube3d window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::cube3d - */ - std::ostream& operator<<(std::ostream& ostr, const cube3d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -132,40 +107,21 @@ } inline - bool cube3d::is_centered() const - { - return true; - } - - inline - bool cube3d::is_symmetric() const - { - return true; - } - - inline unsigned cube3d::length() const { return length_; } inline - unsigned cube3d::delta() const + unsigned cube3d::delta_() const { return length_ / 2; } inline - cube3d& cube3d::sym() - { - return *this; - } - - inline - std::ostream& operator<<(std::ostream& ostr, const cube3d& win) + void cube3d::print_(std::ostream& ostr) const { - ostr << "[cube3d: length=" << win.length() << ']'; - return ostr; + ostr << "[cube3d: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/line.hh --- mln/win/line.hh (revision 2446) +++ mln/win/line.hh (working copy) @@ -33,14 +33,29 @@ * \brief Definition of the mln::win::line window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/dpoint.hh> namespace mln { + // Forward declaration. + namespace win { template <typename M, unsigned i, typename C> struct line; } + + + namespace trait + { + + template <typename M, unsigned i, typename C> + struct window_< mln::win::line<M,i,C> > : classical_window_ + { + }; + + } // end of namespace trait + + + namespace win { @@ -56,8 +71,7 @@ * \see mln::win::hline2d for an exemple of his use. */ template <typename M, unsigned i, typename C> - struct line : public internal::window_base< dpoint<M, C>, line<M,i,C> >, - public internal::dpsites_impl< dpoint<M, C>, line<M,i,C> > + struct line : public internal::classical_window_base< dpoint<M, C>, line<M,i,C> > { /*! \brief Constructor. * @@ -67,49 +81,24 @@ */ line(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - - /*! \brief Give the hline length, that is, its width. - */ + /// Give the line length. unsigned length() const; + /// Give the line size, that is, its length. + unsigned size() const; + /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - line<M,i,C>& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print an line window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win An line window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::line - */ - template <typename M, unsigned i, typename C> - std::ostream& operator<<(std::ostream& ostr, const line<M,i,C>& win); - - # ifndef MLN_INCLUDE_ONLY @@ -133,20 +122,6 @@ template <typename M, unsigned i, typename C> inline - bool line<M,i,C>::is_centered() const - { - return true; - } - - template <typename M, unsigned i, typename C> - inline - bool line<M,i,C>::is_symmetric() const - { - return true; - } - - template <typename M, unsigned i, typename C> - inline unsigned line<M,i,C>::length() const { return length_; @@ -154,24 +129,24 @@ template <typename M, unsigned i, typename C> inline - unsigned line<M,i,C>::delta() const + unsigned line<M,i,C>::size() const { - return length_ / 2; + return length_; } template <typename M, unsigned i, typename C> inline - line<M,i,C>& line<M,i,C>::sym() + unsigned line<M,i,C>::delta_() const { - return *this; + return length_ / 2; } template <typename M, unsigned i, typename C> inline - std::ostream& operator<<(std::ostream& ostr, const line<M,i,C>& win) + void + line<M,i,C>::print_(std::ostream& ostr) const { - ostr << "[line: length=" << win.length() << ']'; - return ostr; + ostr << "[line: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/rectangle2d.hh --- mln/win/rectangle2d.hh (revision 2446) +++ mln/win/rectangle2d.hh (working copy) @@ -35,8 +35,7 @@ * \todo Reactivate includes at EOF. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint2d.hh> # include <mln/core/def/coord.hh> @@ -44,6 +43,9 @@ namespace mln { + mln_internal_add_classical_window_trait(rectangle2d); + + namespace win { @@ -58,8 +60,7 @@ * o o o o o \n * is defined with height = 3 and width = 5. */ - struct rectangle2d : public internal::window_base< dpoint2d, rectangle2d >, - public internal::dpsites_impl< dpoint2d, rectangle2d > + struct rectangle2d : public internal::classical_window_base< dpoint2d, rectangle2d > { /*! \brief Constructor. * @@ -71,18 +72,6 @@ rectangle2d(unsigned height, unsigned width); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - /// Give the rectangle height. unsigned height() const; @@ -95,34 +84,20 @@ /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; - - /// Apply a central symmetry to the target window; a no-op here. - void sym(); + unsigned delta_() const; /// Give the std vector of delta-points. const std::vector<dpoint2d>& std_vector() const; + void print_(std::ostream& ostr) const; + protected: unsigned height_, width_; }; - /*! \brief Print a rectangle window \p win into the output stream \p - * ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win A rectangle window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::rectangle2d - */ - std::ostream& operator<<(std::ostream& ostr, const rectangle2d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -141,18 +116,6 @@ } inline - bool rectangle2d::is_centered() const - { - return true; - } - - inline - bool rectangle2d::is_symmetric() const - { - return true; - } - - inline unsigned rectangle2d::height() const { return height_; @@ -171,19 +134,12 @@ } inline - unsigned rectangle2d::delta() const + unsigned rectangle2d::delta_() const { return width_ > height_ ? width_ / 2 : height_ / 2; } inline - void - rectangle2d::sym() - { - // No-op. - } - - inline const std::vector<dpoint2d>& rectangle2d::std_vector() const { @@ -191,10 +147,10 @@ } inline - std::ostream& operator<<(std::ostream& ostr, const rectangle2d& win) + void + rectangle2d::print_(std::ostream& ostr) const { - ostr << "[rectangle2d: width=" << win.width() << ", height=" << win.height() << ']'; - return ostr; + ostr << "[rectangle2d: width=" << width_ << ", height=" << height_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/diag2d.hh --- mln/win/diag2d.hh (revision 2446) +++ mln/win/diag2d.hh (working copy) @@ -33,14 +33,16 @@ * \brief Definition of the mln::win::diag2d window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint2d.hh> namespace mln { + mln_internal_add_classical_window_trait(diag2d); + + namespace win { @@ -57,8 +59,7 @@ * o \n * is defined with length = 5. */ - struct diag2d : public internal::window_base< dpoint2d, diag2d >, - public internal::dpsites_impl< dpoint2d, diag2d > + struct diag2d : public internal::classical_window_base< dpoint2d, diag2d > { /*! \brief Constructor. * @@ -68,18 +69,6 @@ */ diag2d(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - /*! \brief Give the diagonal length, that is, its width. */ unsigned length() const; @@ -87,29 +76,15 @@ /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - diag2d& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print an diagonal line window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win A diagonal line window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::diag2d - */ - std::ostream& operator<<(std::ostream& ostr, const diag2d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -124,40 +99,21 @@ } inline - bool diag2d::is_centered() const - { - return true; - } - - inline - bool diag2d::is_symmetric() const - { - return true; - } - - inline unsigned diag2d::length() const { return length_; } inline - unsigned diag2d::delta() const + unsigned diag2d::delta_() const { return length_ / 2; } inline - diag2d& diag2d::sym() - { - return *this; - } - - inline - std::ostream& operator<<(std::ostream& ostr, const diag2d& win) + void diag2d::print_(std::ostream& ostr) const { - ostr << "[diag 2d: length=" << win.length() << ']'; - return ostr; + ostr << "[diag 2d: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/backdiag2d.hh --- mln/win/backdiag2d.hh (revision 2446) +++ mln/win/backdiag2d.hh (working copy) @@ -33,14 +33,16 @@ * \brief Definition of the mln::win::backdiag2d window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint2d.hh> namespace mln { + mln_internal_add_classical_window_trait(backdiag2d); + + namespace win { @@ -57,8 +59,7 @@ * o \n * is defined with length = 5. */ - struct backdiag2d : public internal::window_base< dpoint2d, backdiag2d >, - public internal::dpsites_impl< dpoint2d, backdiag2d > + struct backdiag2d : public internal::classical_window_base< dpoint2d, backdiag2d > { /*! \brief Constructor. * @@ -68,18 +69,6 @@ */ backdiag2d(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - /*! \brief Give the diagonal length, that is, its width. */ unsigned length() const; @@ -87,29 +76,15 @@ /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - backdiag2d& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print an diagonal line window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win A diagonal line window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::backdiag2d - */ - std::ostream& operator<<(std::ostream& ostr, const backdiag2d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -124,40 +99,21 @@ } inline - bool backdiag2d::is_centered() const - { - return true; - } - - inline - bool backdiag2d::is_symmetric() const - { - return true; - } - - inline unsigned backdiag2d::length() const { return length_; } inline - unsigned backdiag2d::delta() const + unsigned backdiag2d::delta_() const { return length_ / 2; } inline - backdiag2d& backdiag2d::sym() - { - return *this; - } - - inline - std::ostream& operator<<(std::ostream& ostr, const backdiag2d& win) + void backdiag2d::print_(std::ostream& ostr) const { - ostr << "[diag 2d: length=" << win.length() << ']'; - return ostr; + ostr << "[backdiag 2d: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/multiple.hh --- mln/win/multiple.hh (revision 2446) +++ mln/win/multiple.hh (working copy) @@ -42,13 +42,33 @@ namespace mln { + // Forward declarations. namespace win { - - // Forward declaration. + template <typename W, typename F> class multiple; template <typename W, typename F> class multiple_qiter; + } + + namespace trait + { + + template <typename W, typename F> + struct window_< win::multiple<W,F> > + { + typedef trait::window::size::fixed size; + typedef trait::window::support::regular support; + typedef trait::window::definition::n_ary definition; + }; + + } // end of namespace trait + + + + namespace win + { + template <typename W, typename F> class multiple : public internal::window_base< mln_dpsite(W), multiple<W,F> > { @@ -58,10 +78,14 @@ typedef mln_psite(W) psite; typedef mln_site(W) site; + typedef multiple< window<dpsite>, F > regular; + typedef multiple_qiter<W,F> fwd_qiter; typedef multiple_qiter<W,F> bkd_qiter; typedef multiple_qiter<W,F> qiter; + typedef W element; + multiple(); multiple(const F& f); @@ -72,9 +96,13 @@ const W& window(unsigned i) const; + unsigned nwindows() const; + + const F& function() const; + unsigned size() const; - unsigned size_around(const mln_psite(W)& p) const; +// unsigned size_around(const mln_psite(W)& p) const; const mln_dpsite(W)& ith_dp_around(unsigned i, const mln_psite(W)& p) const; @@ -86,11 +114,9 @@ util::array<W> win_; F f_; - unsigned size_; }; - template <typename W, typename F> class multiple_qiter : public internal::site_relative_iterator_base< multiple<W,F>, @@ -120,7 +146,8 @@ private: unsigned i_; - unsigned n_() const; + unsigned size_; +// unsigned n_() const; }; @@ -148,7 +175,7 @@ bool multiple<W,F>::is_empty() const { - return size_ == 0; + return win_.is_empty(); } template <typename W, typename F> @@ -157,6 +184,8 @@ multiple<W,F>::set_window(unsigned i, const W& win) { mln_precondition(i == win_.nelements()); + if (i >= 1) + mln_precondition(win.size() == win_[0].size()); win_.append(win); } @@ -172,9 +201,25 @@ template <typename W, typename F> inline unsigned + multiple<W,F>::nwindows() const + { + return win_.nelements(); + } + + template <typename W, typename F> + inline + const F& + multiple<W,F>::function() const + { + return f_; + } + + template <typename W, typename F> + inline + unsigned multiple<W,F>::size() const { - mln_precondition(win_.nelements() >= 1); + mln_precondition(win_.nelements() >= 2); // Multiple cannot be just 1 element. unsigned s = win_[0].size(); for (unsigned i = 1; i < win_.nelements(); ++i) mln_precondition(win_[i].size() == s); @@ -205,14 +250,14 @@ return true; } - template <typename W, typename F> - inline - unsigned - multiple<W,F>::size_around(const mln_psite(W)& p) const - { - mln_precondition(f_(p) < win_.nelements()); - return win_[f_(p)].size(); - } +// template <typename W, typename F> +// inline +// unsigned +// multiple<W,F>::size_around(const mln_psite(W)& p) const +// { +// mln_precondition(f_(p) < win_.nelements()); +// return win_[f_(p)].size(); +// } template <typename W, typename F> inline @@ -242,6 +287,7 @@ // We have to first change the center so that 'invalidate' can // work when changing the target. this->change_target(w); + size_ = w.size(); // FIXME: In a local change_target! } template <typename W, typename F> @@ -249,7 +295,7 @@ bool multiple_qiter<W,F>::is_valid_() const { - return i_ < n_(); + return i_ < size_; } template <typename W, typename F> @@ -257,7 +303,7 @@ void multiple_qiter<W,F>::invalidate_() { - i_ = n_(); + i_ = size_; } template <typename W, typename F> @@ -284,13 +330,13 @@ return *this->c_ + this->s_->ith_dp_around(i_, *this->c_); } - template <typename W, typename F> - inline - unsigned - multiple_qiter<W,F>::n_() const - { - return this->s_->size_around(*this->c_); - } +// template <typename W, typename F> +// inline +// unsigned +// multiple_qiter<W,F>::size_() const +// { +// return this->s_->size_around(*this->c_); +// } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/cuboid3d.hh --- mln/win/cuboid3d.hh (revision 2446) +++ mln/win/cuboid3d.hh (working copy) @@ -31,14 +31,16 @@ /// \file mln/win/cuboid3d.hh /// \brief Definition of the mln::win::cuboid3d window. -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint3d.hh> namespace mln { + mln_internal_add_classical_window_trait(cuboid3d); + + namespace win { @@ -73,8 +75,7 @@ Reference: http://en.wikipedia.org/wiki/Cuboid */ - struct cuboid3d : public internal::window_base< dpoint3d, cuboid3d >, - public internal::dpsites_impl< dpoint3d, cuboid3d > + struct cuboid3d : public internal::classical_window_base< dpoint3d, cuboid3d > { /// \brief Constructor. /// @@ -86,16 +87,6 @@ cuboid3d(unsigned depth, unsigned height, unsigned width); - /// Properties of the window. - /// \{ - /// \brief Test if the window is centered. - /// \return \c true (always). - bool is_centered() const; - /// \brief Test if the window is symmetric. - /// \return \c true (always). - bool is_symmetric() const; - /// \} - /// Accessors. /// \{ /// \brief Return the depth of the cuboid. @@ -111,10 +102,9 @@ /// \brief Give the maximum coordinate gap between the center of /// the window and a point of the window. - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - cuboid3d& sym(); + void print_(std::ostream& ostr) const; protected: /// The depth of the cuboid (expressed as a number of slices). @@ -126,17 +116,6 @@ }; - /// \brief Print a cuboid window \a win into the output stream \a ostr. - /// - /// \param[in,out] ostr An output stream. - /// \param[in] win A cuboid window. - /// - /// \return The modified output stream \a ostr. - /// - /// \relates mln::win::cuboid3d - std::ostream& operator<<(std::ostream& ostr, const cuboid3d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -157,20 +136,6 @@ } inline - bool - cuboid3d::is_centered() const - { - return true; - } - - inline - bool - cuboid3d::is_symmetric() const - { - return true; - } - - inline unsigned cuboid3d::depth() const { @@ -200,7 +165,7 @@ inline unsigned - cuboid3d::delta() const + cuboid3d::delta_() const { if (depth_ > height_) if (depth_ > width_) @@ -219,20 +184,12 @@ } inline - cuboid3d& - cuboid3d::sym() - { - return *this; - } - - inline - std::ostream& - operator<<(std::ostream& ostr, const cuboid3d& win) + void + cuboid3d::print_(std::ostream& ostr) const { - ostr << "[cuboid3d: width=" << win.depth() - << ", depth=" << win.width() - << ", height=" << win.height() << ']'; - return ostr; + ostr << "[cuboid3d: width=" << depth_ + << ", depth=" << width_ + << ", height=" << height_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/octagon2d.hh --- mln/win/octagon2d.hh (revision 2446) +++ mln/win/octagon2d.hh (working copy) @@ -33,14 +33,16 @@ * \brief Definition of the mln::win::octagon2d window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint2d.hh> namespace mln { + mln_internal_add_classical_window_trait(octagon2d); + + namespace win { @@ -61,8 +63,7 @@ * o o o \n * is defined with L = 7 (l = 1). */ - struct octagon2d : public internal::window_base< dpoint2d, octagon2d >, - public internal::dpsites_impl< dpoint2d, octagon2d > + struct octagon2d : public internal::classical_window_base< dpoint2d, octagon2d > { /*! \brief Constructor. * @@ -72,18 +73,6 @@ */ octagon2d(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - /*! \brief Give the octagon length, that is, its width. */ unsigned length() const; @@ -91,33 +80,19 @@ /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; /*! \brief Give the area. */ unsigned area() const; - /// Apply a central symmetry to the target window. - octagon2d& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print an octagon window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win An octagon window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::octagon2d - */ - std::ostream& operator<<(std::ostream& ostr, const octagon2d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -153,25 +128,13 @@ } inline - bool octagon2d::is_centered() const - { - return true; - } - - inline - bool octagon2d::is_symmetric() const - { - return true; - } - - inline unsigned octagon2d::length() const { return length_; } inline - unsigned octagon2d::delta() const + unsigned octagon2d::delta_() const { return length_ / 2; } @@ -184,16 +147,9 @@ } inline - octagon2d& octagon2d::sym() - { - return *this; - } - - inline - std::ostream& operator<<(std::ostream& ostr, const octagon2d& win) + void octagon2d::print_(std::ostream& ostr) const { - ostr << "[octagon2d: length=" << win.length() << ']'; - return ostr; + ostr << "[octagon2d: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY Index: mln/win/disk2d.hh --- mln/win/disk2d.hh (revision 2446) +++ mln/win/disk2d.hh (working copy) @@ -33,14 +33,16 @@ * \brief Definition of the mln::win::disk2d window. */ -# include <mln/core/internal/window_base.hh> -# include <mln/core/internal/dpsites_impl.hh> +# include <mln/core/internal/classical_window_base.hh> # include <mln/core/alias/dpoint2d.hh> namespace mln { + mln_internal_add_classical_window_trait(disk2d); + + namespace win { @@ -49,8 +51,7 @@ * An disk2d is centered and symmetric. * */ - struct disk2d : public internal::window_base< dpoint2d, disk2d >, - public internal::dpsites_impl< dpoint2d, disk2d > + struct disk2d : public internal::classical_window_base< dpoint2d, disk2d > { /*! \brief Constructor. * @@ -59,48 +60,22 @@ */ disk2d(unsigned length); - /*! \brief Test if the window is centered. - * - * \return True. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - * - * \return true. - */ - bool is_symmetric() const; - - /*! \brief Give the disk length, that is, its width. + /*! \brief Give the disk diameter. */ unsigned length() const; /*! \brief Give the maximum coordinate gap between the window * center and a window point. */ - unsigned delta() const; + unsigned delta_() const; - /// Apply a central symmetry to the target window. - disk2d& sym(); + void print_(std::ostream& ostr) const; protected: unsigned length_; }; - /*! \brief Print an disk window \p win into the output - * stream \p ostr. - * - * \param[in,out] ostr An output stream. - * \param[in] win A disk window. - * - * \return The modified output stream \p ostr. - * - * \relates mln::win::disk2d - */ - std::ostream& operator<<(std::ostream& ostr, const disk2d& win); - - # ifndef MLN_INCLUDE_ONLY @@ -118,40 +93,21 @@ } inline - bool disk2d::is_centered() const - { - return true; - } - - inline - bool disk2d::is_symmetric() const - { - return true; - } - - inline unsigned disk2d::length() const { return length_; } inline - unsigned disk2d::delta() const + unsigned disk2d::delta_() const { return length_ / 2; } inline - disk2d& disk2d::sym() - { - return *this; - } - - inline - std::ostream& operator<<(std::ostream& ostr, const disk2d& win) + void disk2d::print_(std::ostream& ostr) const { - ostr << "[disk2d: length=" << win.length() << ']'; - return ostr; + ostr << "[disk2d: length=" << length_ << ']'; } # endif // ! MLN_INCLUDE_ONLY

1 0

cleanup-2008 2446: Update documentation about image properties.
by Nicolas Ballas 30 Sep '08

30 Sep '08

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Update documentation about image properties. * tests/level/median_.cc: Update. * tests/level/Makefile.am: Add the tests in the Makefile.am. * doc/technical/designs/properties/values.txt: Update. * mln/accu/histo.hh: Fix a compile mistake. doc/technical/designs/properties/values.txt | 86 +++++++++++++++++++++++++--- mln/accu/histo.hh | 2 tests/level/Makefile.am | 2 tests/level/median_.cc | 1 4 files changed, 81 insertions(+), 10 deletions(-) Index: tests/level/median_.cc --- tests/level/median_.cc (revision 2445) +++ tests/level/median_.cc (working copy) @@ -44,4 +44,5 @@ level::impl::median_(lena, rect, out); io::pgm::save(out, "out.pgm"); } + } Index: tests/level/Makefile.am --- tests/level/Makefile.am (revision 2445) +++ tests/level/Makefile.am (working copy) @@ -14,6 +14,7 @@ fill \ fill_with_value \ median \ + median_ \ median_dir \ median_fast \ median_hline2d \ @@ -36,6 +37,7 @@ fill_SOURCES = fill.cc fill_with_value_SOURCES = fill_with_value.cc median_SOURCES = median.cc +median__SOURCES = median_.cc median_dir_SOURCES = median_dir.cc median_fast_SOURCES = median_fast.cc median_hline2d_SOURCES = median_hline2d.cc Index: doc/technical/designs/properties/values.txt --- doc/technical/designs/properties/values.txt (revision 2445) +++ doc/technical/designs/properties/values.txt (working copy) @@ -14,8 +14,21 @@ | + -- direct | + + -- semi_direct + | + -- computed +=> Definition: This property indicates if the image value are stored in memory. + +- direct: Images store all their values in memory, we can take a reference +of the values. + +- semi-direct: Images store partially their value in memory, we can't take +a reference on them. For instance, images that compute a value at the first +access and store it in a buffer to speed up the next access, are semi-direct. + +- computed: All the image values are computed on the fly, at each access. + ** value_storage:/any/ | @@ -27,9 +40,54 @@ | | | + -- piecewise | - + -- disrupted + + -- none -=> Methods related: + +*** Definition: + Indicate how the value are stored in memory + +- singleton: The image has only one values, this values is store in memory. + 01 + -- +0 |ee| values in memory +1 |ee| ==========> [e] + -- + + + +- one_block: All the image values are stored in a buffer in memory. + + 01 + -- +0 |ef| values in memory +1 |ge| ==========> [e, f, g, e] + -- + +- piece_wise: The values are stored in several memory locations. + +example 1) RLE Image + + 013456 + ------ +0 |ee | values in memory +1 | fff | ==========> [e], [f], [g] +3 | ggg| +4 | | + ------ + +example 2) Sparse Image + + 013456 + ------ +0 |ef | values in memory +1 | faaff| ==========> [e, f], [f, a, a, f, f], [l, l, o, g, g] +3 | llogg| +4 | | + ------ + +- none: We don't have any information about the value storage. + +*** Methods related: value_storage == singleton => ima.value() -> return the image value @@ -67,6 +125,23 @@ method of value_wise property value + cell_wise property value +** site_wise_io:/any/ + | + + -- read_only + | + + -- read_write + +=> Definition: + Indicates the io permission for the site access. + It replaces the property value_access. + +- read_only: We can only read the image values. +- read_write: We can read and write the image values. + + **Note**: RLE images are read only for the access sites. + +FIXME: Do we need a value_wise_io + * Impact on the fill and paste algorithms @@ -158,10 +233,3 @@ r : (5,2), (4, 2), (6, 2) g : (5,4), (4, 4), (6, 3) b : (2,2), (1, 2), (3, 2) - --differentiate the localization of an image and its storage method. - -** Image related with 'special' values access - -*** Run Images (sparse, value_encoded) -*** Pkey Images Index: mln/accu/histo.hh --- mln/accu/histo.hh (revision 2445) +++ mln/accu/histo.hh (working copy) @@ -199,7 +199,7 @@ inline std::ostream& operator<<(std::ostream& ostr, const histo<V>& h) { - mln_viter(V) v(h.vset()); + mln_viter(value::set<V>) v(h.vset()); for_all(v) if (h(v) != 0) ostr << v << ':' << h(v) << ' ';

1 0

milena r2445: Fixes on median
by Matthieu Garrigues 30 Sep '08

30 Sep '08

URL: https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena ChangeLog: 2008-09-30 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Fixes on median. * mln/level/median.hh: Add initialisation of p : p = input.domain().pmin() + up; * tests/level/median_.cc: Some tests. --- mln/level/median.hh | 1 tests/level/median_.cc | 54 +++++++++++++++++++------------------------------ 2 files changed, 22 insertions(+), 33 deletions(-) Index: branches/cleanup-2008/milena/tests/level/median_.cc =================================================================== --- branches/cleanup-2008/milena/tests/level/median_.cc (revision 2444) +++ branches/cleanup-2008/milena/tests/level/median_.cc (revision 2445) @@ -1,37 +1,6 @@ -// Copyright (C) 2007, 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/level/median.cc - * - * \brief Test on mln::level::median. - */ - #include <mln/core/image/image2d.hh> #include <mln/win/rectangle2d.hh> +#include <mln/make/box2d.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> @@ -41,13 +10,31 @@ #include "tests/data.hh" +#include <mln/debug/iota.hh> +#include <mln/debug/println.hh> + int main() { using namespace mln; using value::int_u8; - win::rectangle2d rect(5, 5); + { + border::thickness = 5; + box2d bb = make::box2d(0, 0, 3, 3); + image2d<int_u8> ima(bb); + debug::iota(ima); + debug::println(ima); + + win::rectangle2d rect(3, 3); + image2d<int_u8> out(ima.domain()); + + level::impl::median_(ima, rect, out); + } + + + { + win::rectangle2d rect(20, 20); border::thickness = 6; image2d<int_u8> lena; @@ -57,3 +44,4 @@ level::impl::median_(lena, rect, out); io::pgm::save(out, "out.pgm"); } +} Index: branches/cleanup-2008/milena/mln/level/median.hh =================================================================== --- branches/cleanup-2008/milena/mln/level/median.hh (revision 2444) +++ branches/cleanup-2008/milena/mln/level/median.hh (revision 2445) @@ -143,6 +143,7 @@ void init() { med.init(); + p = input.domain().pmin() + up; mln_qiter(W) q(win, p); for_all(q) if (input.has(q)) med.take(input(q));

1 0

2444: Add iterators on lower- and higher-dimension adjacent faces.
by Roland Levillain 30 Sep '08

30 Sep '08

* mln/topo/internal/complex_relative_iterator_base.hh: New file. * mln/topo/adj_lower_face_iter.hh, * mln/topo/adj_higher_face_iter.hh: New files. Include them... * mln/topo/complex.hh: ...here. * tests/topo/complex.cc (main): Exercise these iterators. --- milena/ChangeLog | 13 + milena/mln/topo/adj_higher_face_iter.hh | 185 +++++++++ milena/mln/topo/adj_lower_face_iter.hh | 185 +++++++++ milena/mln/topo/complex.hh | 4 + .../internal/complex_relative_iterator_base.hh | 436 ++++++++++++++++++++ milena/tests/topo/complex.cc | 49 ++- 6 files changed, 852 insertions(+), 20 deletions(-) create mode 100644 milena/mln/topo/adj_higher_face_iter.hh create mode 100644 milena/mln/topo/adj_lower_face_iter.hh create mode 100644 milena/mln/topo/internal/complex_relative_iterator_base.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index 0f28467..040d817 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,18 @@ 2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Add iterators on lower- and higher-dimension adjacent faces. + + * mln/topo/internal/complex_relative_iterator_base.hh: + New file. + * mln/topo/adj_lower_face_iter.hh, + * mln/topo/adj_higher_face_iter.hh: + New files. + Include them... + * mln/topo/complex.hh: ...here. + * tests/topo/complex.cc (main): Exercise these iterators. + +2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Print the address of complexes with their face handles. * mln/topo/face.hh (operator<<(std::ostream&, const face<D>&)) diff --git a/milena/mln/topo/adj_higher_face_iter.hh b/milena/mln/topo/adj_higher_face_iter.hh new file mode 100644 index 0000000..5301c05 --- /dev/null +++ b/milena/mln/topo/adj_higher_face_iter.hh @@ -0,0 +1,185 @@ +// 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_FACE_ITER_HH +# define MLN_TOPO_ADJ_HIGHER_FACE_ITER_HH + +/// \file mln/topo/adj_higher_face_iter.hh +/// \brief Definition of forward and backward iterators on the +/// adjacent (n+1)-faces of a (reference) n-face in a complex. + +# include <mln/topo/internal/complex_relative_iterator_base.hh> +# include <mln/topo/face.hh> + + +namespace mln +{ + + namespace topo + { + + // Forward declaration. + template <unsigned D> class complex; + + + /*------------------------------------. + | topo::adj_higher_face_fwd_iter<D>. | + `------------------------------------*/ + + /// \brief Forward iterator on all the faces of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_higher_face_fwd_iter + : public internal::forward_complex_relative_iterator_base< face<D>, + adj_higher_face_fwd_iter<D> > + { + private: + typedef adj_higher_face_fwd_iter<D> self_; + typedef internal::forward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + using super_::is_valid; + using super_::invalidate; + + public: + /// Construction and assignment. + /// \{ + adj_higher_face_fwd_iter(); + template <typename Fref> + adj_higher_face_fwd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + /*------------------------------------. + | topo::adj_higher_face_bkd_iter<D>. | + `------------------------------------*/ + + /// \brief Backward iterator on all the faces of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_higher_face_bkd_iter + : public internal::backward_complex_relative_iterator_base< face<D>, + adj_higher_face_bkd_iter<D> > + { + private: + typedef adj_higher_face_bkd_iter<D> self_; + typedef internal::backward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + using super_::is_valid; + using super_::invalidate; + + public: + /// Construction and assignment. + /// \{ + adj_higher_face_bkd_iter(); + template <typename Fref> + adj_higher_face_bkd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + +# ifndef MLN_INCLUDE_ONLY + + /*------------------------------------. + | topo::adj_higher_face_fwd_iter<D>. | + `------------------------------------*/ + + template <unsigned D> + inline + adj_higher_face_fwd_iter<D>::adj_higher_face_fwd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_higher_face_fwd_iter<D>::adj_higher_face_fwd_iter(const Fref& f_ref) + { + center_at(f_ref); + // FIXME: Move this to the super class? + invalidate(); + } + + template <unsigned D> + inline + void + adj_higher_face_fwd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + this->adj_faces_ = this->c_->higher_dim_adj_faces(); + } + + + /*------------------------------------. + | topo::adj_higher_face_bkd_iter<D>. | + `------------------------------------*/ + + template <unsigned D> + inline + adj_higher_face_bkd_iter<D>::adj_higher_face_bkd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_higher_face_bkd_iter<D>::adj_higher_face_bkd_iter(const Fref& f_ref) + { + center_at(f_ref); + // FIXME: Move this to the super class? + invalidate(); + } + + template <unsigned D> + inline + void + adj_higher_face_bkd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + this->adj_faces_ = this->c_->higher_dim_adj_faces(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_ADJ_HIGHER_FACE_ITER_HH diff --git a/milena/mln/topo/adj_lower_face_iter.hh b/milena/mln/topo/adj_lower_face_iter.hh new file mode 100644 index 0000000..498357b --- /dev/null +++ b/milena/mln/topo/adj_lower_face_iter.hh @@ -0,0 +1,185 @@ +// 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_FACE_ITER_HH +# define MLN_TOPO_ADJ_LOWER_FACE_ITER_HH + +/// \file mln/topo/adj_lower_face_iter.hh +/// \brief Definition of forward and backward iterators on the +/// adjacent (n-1)-faces of a (reference) n-face in a complex. + +# include <mln/topo/internal/complex_relative_iterator_base.hh> +# include <mln/topo/face.hh> + + +namespace mln +{ + + namespace topo + { + + // Forward declaration. + template <unsigned D> class complex; + + + /*-----------------------------------. + | topo::adj_lower_face_fwd_iter<D>. | + `-----------------------------------*/ + + /// \brief Forward iterator on all the faces of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_lower_face_fwd_iter + : public internal::forward_complex_relative_iterator_base< face<D>, + adj_lower_face_fwd_iter<D> > + { + private: + typedef adj_lower_face_fwd_iter<D> self_; + typedef internal::forward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + using super_::is_valid; + using super_::invalidate; + + public: + /// Construction and assignment. + /// \{ + adj_lower_face_fwd_iter(); + template <typename Fref> + adj_lower_face_fwd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + /*-----------------------------------. + | topo::adj_lower_face_bkd_iter<D>. | + `-----------------------------------*/ + + /// \brief Backward iterator on all the faces of an mln::complex<D>. + /// + /// \arg \p D The dimension of the complex this iterator belongs to. + template <unsigned D> + class adj_lower_face_bkd_iter + : public internal::backward_complex_relative_iterator_base< face<D>, + adj_lower_face_bkd_iter<D> > + { + private: + typedef adj_lower_face_bkd_iter<D> self_; + typedef internal::backward_complex_relative_iterator_base< face<D>, + self_ > super_; + + public: + using super_::is_valid; + using super_::invalidate; + + public: + /// Construction and assignment. + /// \{ + adj_lower_face_bkd_iter(); + template <typename Fref> + adj_lower_face_bkd_iter(const Fref& f_ref); + /// \} + + /// Compute the set of faces adjacent to the reference face. + void update_adj_faces_(); + }; + + + +# ifndef MLN_INCLUDE_ONLY + + /*-----------------------------------. + | topo::adj_lower_face_fwd_iter<D>. | + `-----------------------------------*/ + + template <unsigned D> + inline + adj_lower_face_fwd_iter<D>::adj_lower_face_fwd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_lower_face_fwd_iter<D>::adj_lower_face_fwd_iter(const Fref& f_ref) + { + center_at(f_ref); + // FIXME: Move this to the super class? + invalidate(); + } + + template <unsigned D> + inline + void + adj_lower_face_fwd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + this->adj_faces_ = this->c_->lower_dim_adj_faces(); + } + + + /*-----------------------------------. + | topo::adj_lower_face_bkd_iter<D>. | + `-----------------------------------*/ + + template <unsigned D> + inline + adj_lower_face_bkd_iter<D>::adj_lower_face_bkd_iter() + { + } + + template <unsigned D> + template <typename Fref> + inline + adj_lower_face_bkd_iter<D>::adj_lower_face_bkd_iter(const Fref& f_ref) + { + center_at(f_ref); + // FIXME: Move this to the super class? + invalidate(); + } + + template <unsigned D> + inline + void + adj_lower_face_bkd_iter<D>::update_adj_faces_() + { + mln_precondition(this->c_); + this->adj_faces_ = this->c_->lower_dim_adj_faces(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_ADJ_LOWER_FACE_ITER_HH diff --git a/milena/mln/topo/complex.hh b/milena/mln/topo/complex.hh index 643285c..c053879 100644 --- a/milena/mln/topo/complex.hh +++ b/milena/mln/topo/complex.hh @@ -56,6 +56,10 @@ # include <mln/topo/faces_iter.hh> # endif +# include <mln/topo/adj_lower_face_iter.hh> +# include <mln/topo/adj_higher_face_iter.hh> + + namespace mln { diff --git a/milena/mln/topo/internal/complex_relative_iterator_base.hh b/milena/mln/topo/internal/complex_relative_iterator_base.hh new file mode 100644 index 0000000..599727a --- /dev/null +++ b/milena/mln/topo/internal/complex_relative_iterator_base.hh @@ -0,0 +1,436 @@ +// 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_INTERNAL_COMPLEX_RELATIVE_ITERATOR_BASE_HH +# define MLN_TOPO_INTERNAL_COMPLEX_RELATIVE_ITERATOR_BASE_HH + +/** \file mln/topo/internal/complex_relative_iterator_base.hh + \brief Definition of an implementation (factoring) class for + iterators on mln::complex. + + The hierarchy of classes in this file is as follows + + \verbatim + + complex_relative_iterator_base<F, E> + ^ + | + ,--------------+--------------. + | | + forward_complex_relative_iterator_base<F, E> | + | + backward_complex_relative_iterator_base<F, E> + + \endverbatim +*/ + +# include <limits> + +# include <mln/metal/equal.hh> + +# include <mln/core/concept/iterator.hh> +# include <mln/topo/complex.hh> + +/* FIXME: By moving iterator `i_' into + internal::complex_relative_iterator_base, we'll be able to factor + more methods (do_next_, update_f); this requires the type of this + iterator be passed as an extra parameter to + internal::complex_relative_iterator_base. */ + + +namespace mln +{ + + namespace topo + { + + namespace internal + { + + /*-------------------------------------------------------. + | topo::internal::complex_relative_iterator_base<F, E>. | + `-------------------------------------------------------*/ + + /// \brief Factoring class for relative iterators on mln::complex. + /// + /// \arg \p F The type of the face handle. + /// \arg \p E The type exact type of the iterator. + template <typename F, typename E> + class complex_relative_iterator_base : public Iterator<E> + { + typedef complex_relative_iterator_base<F, E> self_; + + public: + typedef F face; + // FIXME: Maybe we could just get the dimension D of the face's + // complex, an define complex_type as mln::complex<D>? + typedef typename F::complex_type complex_type; + + /// Construction and assignment. + /// \{ + /* FIXME: Keep this non-const? See a (big) comment about this in + milena/tests/complex_image.cc. */ + complex_relative_iterator_base(); + /// \} + + /// Manipulation. + /// \{ + /// Change the center face. + void center_at(const F& c); + + /// Start an iteration. + void start(); + /// Go to the next point. + void next_(); + /// \} + + /// Conversion and accessors. + /// \{ + /// Reference to the corresponding face handle. + const face& to_face () const; + /// Convert the iterator into an face handle. + operator face() const; + /// \} + + protected: + /// A pointer to the center face around which this iterator + /// moves. + const face* c_; + + // The type of the set of vicinity sites (adjacent face handles). + typedef std::vector<face> adj_faces_t; + /// The set of faces adjacent to the reference face. + adj_faces_t adj_faces_; + + /// The face handle this iterator is pointing to. + face f_; + }; + + + /* 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 F, typename E> + inline + std::ostream& + operator<<(std::ostream& ostr, const complex_relative_iterator_base<F, E>& p); + + + /*---------------------------------------------------------------. + | topo::internal::forward_complex_relative_iterator_base<F, E>. | + `---------------------------------------------------------------*/ + + /// \brief Factoring class for forward relative iterators on + /// mln::complex. + /// + /// \arg \p F The type of the face handle. + /// \arg \p E The type exact type of the iterator. + template <typename F, typename E> + class forward_complex_relative_iterator_base + : public complex_relative_iterator_base<F, E> + { + typedef forward_complex_relative_iterator_base<F, E> self_; + typedef complex_relative_iterator_base<F, E> super_; + + public: + typedef F face; + // FIXME: Maybe we could just get the dimension D of the face's + // complex, an define complex_type as mln::complex<D>? + typedef typename F::complex_type complex_type; + + public: + /// Construction and assignment. + /// \{ + /* FIXME: Keep this non-const? See a (big) comment about this in + milena/tests/complex_image.cc. */ + forward_complex_relative_iterator_base(); + /// \} + + public: + /// Manipulation + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void do_start_(); + /// Go to the next point. + void do_next_(); + + /// Update the target face. + void update_f_(); + /// \} + + protected: + /// An iterator on the set of adjacent edges. + typename super_::adj_faces_t::const_iterator i_; + }; + + + /*----------------------------------------------------------------. + | topo::internal::backward_complex_relative_iterator_base<F, E>. | + `----------------------------------------------------------------*/ + + /// \brief Factoring class for backward relative iterators on + /// mln::complex. + /// + /// \arg \p F The type of the face handle. + /// \arg \p E The type exact type of the iterator. + template <typename F, typename E> + class backward_complex_relative_iterator_base + : public complex_relative_iterator_base<F, E> + { + typedef backward_complex_relative_iterator_base<F, E> self_; + typedef complex_relative_iterator_base<F, E> super_; + + public: + typedef F face; + // FIXME: Maybe we could just get the dimension D of the face's + // complex, an define complex_type as mln::complex<D>? + typedef typename F::complex_type complex_type; + + public: + /// Construction and assignment. + /// \{ + /* FIXME: Keep this non-const? See a (big) comment about this in + milena/tests/complex_image.cc. */ + backward_complex_relative_iterator_base(); + /// \} + + public: + /// Manipulation + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void do_start_(); + /// Go to the next point. + void do_next_(); + + /// Update the target face. + void update_f_(); + /// \} + + protected: + /// An iterator on the set of adjacent edges. + typename super_::adj_faces_t::const_reverse_iterator i_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + /*-------------------------------------------------------. + | topo::internal::complex_relative_iterator_base<F, E>. | + `-------------------------------------------------------*/ + + template <typename F, typename E> + inline + complex_relative_iterator_base<F, E>::complex_relative_iterator_base() + : c_(0) + { + // Ensure F and E are compatible. + mlc_equal(F, typename E::face)::check(); + // Check for required methods in E. + void (E::*m)() = & E::update_adj_faces_; + m = 0; + } + + template <typename F, typename E> + inline + void + complex_relative_iterator_base<F, E>::center_at(const F& c) + { + c_ = &c; + exact(this)->invalidate(); + } + + template <typename F, typename E> + inline + void + complex_relative_iterator_base<F, E>::start() + { + exact(this)->do_start_(); + if (exact(this)->is_valid()) + exact(this)->update_f_(); + } + + template <typename F, typename E> + inline + void + complex_relative_iterator_base<F, E>::next_() + { + exact(this)->do_next_(); + if (exact(this)->is_valid()) + exact(this)->update_f_(); + } + + template <typename F, typename E> + inline + const F& + complex_relative_iterator_base<F, E>::to_face() const + { + return f_; + } + + template <typename F, typename E> + inline + complex_relative_iterator_base<F, E>::operator F() const + { + mln_precondition(exact(this)->is_valid()); + return f_; + } + + + template <typename F, typename E> + inline + std::ostream& + operator<<(std::ostream& ostr, + const complex_relative_iterator_base<F, E>& p) + { + return ostr << F(p); + } + + + /*---------------------------------------------------------------. + | topo::internal::forward_complex_relative_iterator_base<F, E>. | + `---------------------------------------------------------------*/ + + template <typename F, typename E> + inline + forward_complex_relative_iterator_base<F, E>::forward_complex_relative_iterator_base() + { + } + + template <typename F, typename E> + inline + bool + forward_complex_relative_iterator_base<F, E>::is_valid() const + { + return i_ != this->adj_faces_.end(); + } + + template <typename F, typename E> + inline + void + forward_complex_relative_iterator_base<F, E>::invalidate() + { + i_ = this->adj_faces_.end(); + } + + template <typename F, typename E> + inline + void + forward_complex_relative_iterator_base<F, E>::do_start_() + { + exact(this)->update_adj_faces_(); + i_ = this->adj_faces_.begin(); + } + + template <typename F, typename E> + inline + void + forward_complex_relative_iterator_base<F, E>::do_next_() + { + ++i_; + } + + template <typename F, typename E> + inline + void + forward_complex_relative_iterator_base<F, E>::update_f_() + { + this->f_ = *i_; + } + + + /*----------------------------------------------------------------. + | topo::internal::backward_complex_relative_iterator_base<F, E>. | + `----------------------------------------------------------------*/ + + template <typename F, typename E> + inline + backward_complex_relative_iterator_base<F, E>::backward_complex_relative_iterator_base() + { + } + + template <typename F, typename E> + inline + bool + backward_complex_relative_iterator_base<F, E>::is_valid() const + { + return i_ != this->adj_faces_.rend(); + } + + template <typename F, typename E> + inline + void + backward_complex_relative_iterator_base<F, E>::invalidate() + { + i_ = this->adj_faces_.rend(); + } + + template <typename F, typename E> + inline + void + backward_complex_relative_iterator_base<F, E>::do_start_() + { + exact(this)->update_adj_faces_(); + i_ = this->adj_faces_.rbegin(); + } + + template <typename F, typename E> + inline + void + backward_complex_relative_iterator_base<F, E>::do_next_() + { + ++i_; + } + + template <typename F, typename E> + inline + void + backward_complex_relative_iterator_base<F, E>::update_f_() + { + this->f_ = *i_; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::topo::internal + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_INTERNAL_COMPLEX_RELATIVE_ITERATOR_BASE_HH diff --git a/milena/tests/topo/complex.cc b/milena/tests/topo/complex.cc index 349921c..f079734 100644 --- a/milena/tests/topo/complex.cc +++ b/milena/tests/topo/complex.cc @@ -207,7 +207,8 @@ 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)-faces adjacent to AF. + /* Iterate on the the set of (n-1)- and (n+1)-faces adjacent to the + faces of C. Note: this can be solved with iterators where the dimension can be either static or dynamic. @@ -224,13 +225,31 @@ int main() (Note: we might want to get rid of the name `citer', and use `fiter' everywhere.). - A static version might be useful (and more efficient) too. + A static version might be useful (and more efficient) too. */ + + topo::adj_lower_face_fwd_iter<D> fwd_alf(fwd_f); + topo::adj_lower_face_bkd_iter<D> bkd_alf(fwd_f); + for_all(fwd_f) + { + std::cout << "Lower-dimension faces adjacent to " << fwd_f << ": " + << std::endl; + for_all_2(fwd_alf, bkd_alf) + std::cout << " " << fwd_alf << '\t' << bkd_alf << std::endl; + } + std::cout << std::endl; - Likewise, our iterators on n-faces (both faces_piter and - complex_faces_piter) use a static `n'. We should also have - n-faces iterators where n could be dynamic. + topo::adj_higher_face_fwd_iter<D> fwd_ahf(fwd_f); + topo::adj_higher_face_bkd_iter<D> bkd_ahf(fwd_f); + for_all(fwd_f) + { + std::cout << "Higher-dimension faces adjacent to " << fwd_f << ": " + << std::endl; + for_all_2(fwd_ahf, bkd_ahf) + std::cout << " " << fwd_ahf << '\t' << bkd_ahf << std::endl; + } + std::cout << std::endl; - But first, we need to clarify (existing) names. The one listed + /* But first, we need to clarify (existing) names. The one listed in https://trac.lrde.org/olena/wiki/Olena/ComplexBasedImages are OK. @@ -239,26 +258,16 @@ int main() ----------------------------------------------------------------- Name Definition ----------------------------------------------------------------- - adj_lower_faces_fwd_iter<D>(c, f) | Iterators on the adjacent - adj_lower_faces_bkd_iter<D>(c, f) | (lower) (n-1)-faces of the - | n-face f of the complex c, - | n being dynamic - - adj_higher_faces_fwd_iter<D>(c, f) | Iterators on the adjacent - adj_higher_faces_bkd_iter<D>(c, f) | (higher) (n+1)-faces of the - | n-face f of the complex c, - | n being dynamic - - adj_lower_dim_connected_n_faces_fwd_iter<D>(c, f) - adj_lower_dim_connected_n_faces_bkd_iter<D>(c, f) + 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_faces_fwd_iter<D>(c, f) - adj_higher_dim_connected_n_faces_bkd_iter<D>(c, f) + 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 -- 1.6.0.1

1 0

2443: Print the address of complexes with their face handles.
by Roland Levillain 30 Sep '08

30 Sep '08

* mln/topo/face.hh (operator<<(std::ostream&, const face<D>&)) * mln/topo/n_face.hh (operator<<(std::ostream&, const n_face<N, D>&)): Do it. --- milena/ChangeLog | 8 ++++++++ milena/mln/topo/face.hh | 3 ++- milena/mln/topo/n_face.hh | 3 ++- 3 files changed, 12 insertions(+), 2 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index a9e0511..0f28467 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,13 @@ 2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Print the address of complexes with their face handles. + + * mln/topo/face.hh (operator<<(std::ostream&, const face<D>&)) + * mln/topo/n_face.hh (operator<<(std::ostream&, const n_face<N, D>&)): + Do it. + +2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Overhaul mln::topo::internal::complex_iter_base. * mln/topo/internal/complex_iter_base.hh diff --git a/milena/mln/topo/face.hh b/milena/mln/topo/face.hh index 1ff81e5..00d6049 100644 --- a/milena/mln/topo/face.hh +++ b/milena/mln/topo/face.hh @@ -404,7 +404,8 @@ namespace mln std::ostream& operator<<(std::ostream& ostr, const face<D>& f) { - return ostr << "(dim = " << f.n() << ", id = " << f.face_id() << ')'; + return ostr << "(cplx = " << &f.cplx() << ", dim = " << f.n() + << ", id = " << f.face_id() << ')'; } # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/topo/n_face.hh b/milena/mln/topo/n_face.hh index bb4e926..fddf568 100644 --- a/milena/mln/topo/n_face.hh +++ b/milena/mln/topo/n_face.hh @@ -259,7 +259,8 @@ namespace mln std::ostream& operator<<(std::ostream& ostr, const n_face<N, D>& f) { - return ostr << "(dim = " << f.n() << ", id = " << f.face_id() << ')'; + return ostr << "(cplx = " << &f.cplx() << ", dim = " << f.n() + << ", id = " << f.face_id() << ')'; } # endif // ! MLN_INCLUDE_ONLY -- 1.6.0.1

1 0

2442: Overhaul mln::topo::internal::complex_iter_base.
by Roland Levillain 30 Sep '08

30 Sep '08

* mln/topo/internal/complex_iter_base.hh (mln::topo::internal::complex_iter_base<F, E>::to_face): Remove. (operator<<(std::ostream&, const complex_iter_base<F, E>&)): Remove outdated FIXME. (mln::topo::internal::complex_iter_base<F, E>::face_): Rename as... (mln::topo::internal::complex_iter_base<F, E>::f_): ...this. Adjust. * mln/topo/face_iter.hh, * mln/topo/n_face_iter.hh, * mln/topo/static_n_face_iter.hh: Adjust as well. --- milena/ChangeLog | 16 +++++++ milena/mln/topo/face_iter.hh | 38 ++++++++-------- milena/mln/topo/internal/complex_iter_base.hh | 56 ++++++++----------------- milena/mln/topo/n_face_iter.hh | 32 +++++++------- milena/mln/topo/static_n_face_iter.hh | 30 +++++++------- 5 files changed, 84 insertions(+), 88 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 6ce4fb0..a9e0511 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,21 @@ 2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Overhaul mln::topo::internal::complex_iter_base. + + * mln/topo/internal/complex_iter_base.hh + (mln::topo::internal::complex_iter_base<F, E>::to_face): Remove. + (operator<<(std::ostream&, const complex_iter_base<F, E>&)): + Remove outdated FIXME. + (mln::topo::internal::complex_iter_base<F, E>::face_): Rename as... + (mln::topo::internal::complex_iter_base<F, E>::f_): ...this. + Adjust. + * mln/topo/face_iter.hh, + * mln/topo/n_face_iter.hh, + * mln/topo/static_n_face_iter.hh: + Adjust as well. + +2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Improve accesses to adjacent faces to mln::topo::face<D>. * mln/topo/face.hh diff --git a/milena/mln/topo/face_iter.hh b/milena/mln/topo/face_iter.hh index 4de87cc..a564831 100644 --- a/milena/mln/topo/face_iter.hh +++ b/milena/mln/topo/face_iter.hh @@ -84,7 +84,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -124,7 +124,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -156,8 +156,8 @@ namespace mln void face_fwd_iter<D>::start() { - face_.set_n(0u); - face_.set_face_id(0u); + f_.set_n(0u); + f_.set_face_id(0u); } template <unsigned D> @@ -167,27 +167,27 @@ namespace mln { if (is_valid()) { - unsigned n = face_.n(); - unsigned face_id = face_.face_id(); + unsigned n = f_.n(); + unsigned face_id = f_.face_id(); - if (face_id + 1 < face_.cplx().nfaces(n)) + if (face_id + 1 < f_.cplx().nfaces(n)) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id + 1); + f_.set_face_id(face_id + 1); else // Start to iterate on the faces of the next dimension if // possible. if (n <= D) { // FIXME: Same remark as above. - face_.set_n(n + 1); - face_.set_face_id(0u); + f_.set_n(n + 1); + f_.set_face_id(0u); } else invalidate(); @@ -220,8 +220,8 @@ namespace mln void face_bkd_iter<D>::start() { - face_.set_n(D); - face_.set_face_id(face_.cplx().template nfaces<D>() - 1); + f_.set_n(D); + f_.set_face_id(f_.cplx().template nfaces<D>() - 1); } template <unsigned D> @@ -231,27 +231,27 @@ namespace mln { if (is_valid()) { - unsigned n = face_.n(); - unsigned face_id = face_.face_id(); + unsigned n = f_.n(); + unsigned face_id = f_.face_id(); if (face_id > 0) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id - 1); + f_.set_face_id(face_id - 1); else // Start to iterate on the faces of the previous dimension // if it exists. if (n > 0) { // FIXME: Same remark as above. - face_.set_n(n - 1); - face_.set_face_id(face_.cplx().nfaces(n - 1) - 1); + f_.set_n(n - 1); + f_.set_face_id(f_.cplx().nfaces(n - 1) - 1); } else invalidate(); diff --git a/milena/mln/topo/internal/complex_iter_base.hh b/milena/mln/topo/internal/complex_iter_base.hh index dc479e2..06ffca2 100644 --- a/milena/mln/topo/internal/complex_iter_base.hh +++ b/milena/mln/topo/internal/complex_iter_base.hh @@ -39,6 +39,11 @@ # include <mln/core/concept/iterator.hh> # include <mln/topo/complex.hh> +// FIXME: Rename as something else? +// - complex_iterator_base? +// - complex_set_iterator_base? +// - faces_set_iterator_base? + namespace mln { @@ -83,17 +88,15 @@ namespace mln void invalidate(); /// \} - /// Conversion and accessors. + /// Conversion. /// \{ - /// Reference to the corresponding face handle. - const face& to_face () const; - /// Convert the iterator into an face handle. - operator face() const; + /// Return a reference to the corresponding face handle. + operator const face&() const; /// \} protected: /// The face handle this iterator is pointing to. - face face_; + face f_; }; @@ -124,8 +127,8 @@ namespace mln // Ensure F and E are compatible. mlc_equal(F, typename E::face)::check(); - face_.set_cplx(c); - // Invalidate face_. + f_.set_cplx(c); + // Invalidate f_. invalidate(); } @@ -134,8 +137,8 @@ namespace mln void complex_iter_base<F, E>::set_cplx(complex_type& c) { - face_.set_cplx(c); - // Invalidate face_. + f_.set_cplx(c); + // Invalidate f_. invalidate(); } @@ -144,7 +147,7 @@ namespace mln bool complex_iter_base<F, E>::is_valid() const { - return face_.is_valid(); + return f_.is_valid(); } template <typename F, typename E> @@ -152,23 +155,14 @@ namespace mln void complex_iter_base<F, E>::invalidate() { - face_.invalidate(); - } - - template <typename F, typename E> - inline - const F& - complex_iter_base<F, E>::to_face() const - { - return face_; + f_.invalidate(); } template <typename F, typename E> inline - complex_iter_base<F, E>::operator F() const + complex_iter_base<F, E>::operator const F&() const { - mln_precondition(is_valid()); - return face_; + return f_; } @@ -177,21 +171,7 @@ namespace mln std::ostream& operator<<(std::ostream& ostr, const complex_iter_base<F, E>& p) { - /* FIXME: We should use p.to_face() here, but as it lacks the - precondition the conversion operator has, so we use the latter. - - We should - - rename `to_face' as `to_face_'; - - write a new `to_face' routine checking the validity of the - iterator; - - have the conversion operator to face use this new `to_face' - routine; - - adjust former clients of `to_face' - - This is a general remark that applies to all iterators of - Milena. */ - F f = p; - return ostr << f; + return ostr << F(p); } # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/topo/n_face_iter.hh b/milena/mln/topo/n_face_iter.hh index c4291e2..2a499c2 100644 --- a/milena/mln/topo/n_face_iter.hh +++ b/milena/mln/topo/n_face_iter.hh @@ -95,7 +95,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -143,7 +143,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -177,7 +177,7 @@ namespace mln void n_face_fwd_iter<D>::start() { - face_.set_face_id(0u); + f_.set_face_id(0u); } template <unsigned D> @@ -187,19 +187,19 @@ namespace mln { if (is_valid()) { - unsigned face_id = face_.face_id(); + unsigned face_id = f_.face_id(); // The number of faces of dimension N in cplx_. - unsigned nn_faces = face_.cplx().nfaces(n()); + unsigned nn_faces = f_.cplx().nfaces(n()); if (face_id + 1 < nn_faces) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id + 1); + f_.set_face_id(face_id + 1); else invalidate(); } @@ -210,7 +210,7 @@ namespace mln unsigned n_face_fwd_iter<D>::n() const { - return face_.n(); + return f_.n(); } template <unsigned D> @@ -219,7 +219,7 @@ namespace mln n_face_fwd_iter<D>::set_n(unsigned n) { mln_precondition(n <= D); - face_.set_n(n); + f_.set_n(n); } @@ -250,8 +250,8 @@ namespace mln void n_face_bkd_iter<D>::start() { - face_.set_n(n()); - face_.set_face_id(face_.cplx().nfaces(n()) - 1); + f_.set_n(n()); + f_.set_face_id(f_.cplx().nfaces(n()) - 1); } template <unsigned D> @@ -261,17 +261,17 @@ namespace mln { if (is_valid()) { - unsigned face_id = face_.face_id(); + unsigned face_id = f_.face_id(); if (face_id > 0) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id - 1); + f_.set_face_id(face_id - 1); else invalidate(); } @@ -282,7 +282,7 @@ namespace mln unsigned n_face_bkd_iter<D>::n() const { - return face_.n(); + return f_.n(); } template <unsigned D> @@ -291,7 +291,7 @@ namespace mln n_face_bkd_iter<D>::set_n(unsigned n) { mln_precondition(n <= D); - face_.set_n(n); + f_.set_n(n); } # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/topo/static_n_face_iter.hh b/milena/mln/topo/static_n_face_iter.hh index 291b699..f29c4e4 100644 --- a/milena/mln/topo/static_n_face_iter.hh +++ b/milena/mln/topo/static_n_face_iter.hh @@ -81,7 +81,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -124,7 +124,7 @@ namespace mln /// \} private: - using super_::face_; + using super_::f_; }; @@ -142,7 +142,7 @@ namespace mln { // Ensure N is compatible with D. metal::bool_< N <= D >::check(); - face_.set_n(N); + f_.set_n(N); mln_postcondition(!is_valid()); } @@ -153,7 +153,7 @@ namespace mln { // Ensure N is compatible with D. metal::bool_< N <= D >::check(); - face_.set_n(N); + f_.set_n(N); mln_postcondition(!is_valid()); } @@ -162,7 +162,7 @@ namespace mln void static_n_face_fwd_iter<N, D>::start() { - face_.set_face_id(0u); + f_.set_face_id(0u); } template <unsigned N, unsigned D> @@ -172,20 +172,20 @@ namespace mln { if (is_valid()) { - unsigned face_id = face_.face_id(); + unsigned face_id = f_.face_id(); // The number of faces of dimension N in cplx_. - unsigned nn_faces = face_.cplx().template nfaces<N>(); + unsigned nn_faces = f_.cplx().template nfaces<N>(); if (face_id + 1 < nn_faces) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id + 1); + f_.set_face_id(face_id + 1); else invalidate(); } @@ -203,7 +203,7 @@ namespace mln { // Ensure N is compatible with D. metal::bool_< N <= D >::check(); - face_.set_n(N); + f_.set_n(N); mln_postcondition(!is_valid()); } @@ -214,7 +214,7 @@ namespace mln { // Ensure N is compatible with D. metal::bool_< N <= D >::check(); - face_.set_n(N); + f_.set_n(N); mln_postcondition(!is_valid()); } @@ -223,7 +223,7 @@ namespace mln void static_n_face_bkd_iter<N, D>::start() { - face_.set_face_id(face_.cplx().template nfaces<N>() - 1); + f_.set_face_id(f_.cplx().template nfaces<N>() - 1); } template <unsigned N, unsigned D> @@ -233,18 +233,18 @@ namespace mln { if (is_valid()) { - unsigned face_id = face_.face_id(); + unsigned face_id = f_.face_id(); if (face_id > 0) /* FIXME: Provide accessor face::face_id() returning a mutable reference? This way, we could just write - ++face_.face_id(); + ++f_.face_id(); instead of the following. Or add {inc,add}_face_id() services. */ - face_.set_face_id(face_id - 1); + f_.set_face_id(face_id - 1); else invalidate(); } -- 1.6.0.1

1 0

2441: Improve accesses to adjacent faces to mln::topo::face<D>.
by Roland Levillain 30 Sep '08

30 Sep '08

* mln/topo/face.hh (mln::topo::face<D>::lower_dim_adj_faces): Return an empty vector if `this' is a 0-face. (mln::topo::face<D>::higher_dim_adj_faces): Return an empty vector if `this' is a D-face. (mln::topo::face<D>::lower_dim_adj_faces) (mln::topo::face<D>::higher_dim_adj_faces): Make it const. (mln::topo::internal::lower_dim_adj_faces_if_dim_matches_<N, D>) (mln::topo::internal::higher_dim_adj_faces_if_dim_matches_<N, D>): Adjust. --- milena/ChangeLog | 16 ++++++++++++++++ milena/mln/topo/face.hh | 26 ++++++++++++++------------ 2 files changed, 30 insertions(+), 12 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index d820e59..6ce4fb0 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,21 @@ 2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Improve accesses to adjacent faces to mln::topo::face<D>. + + * mln/topo/face.hh + (mln::topo::face<D>::lower_dim_adj_faces): + Return an empty vector if `this' is a 0-face. + (mln::topo::face<D>::higher_dim_adj_faces): + Return an empty vector if `this' is a D-face. + (mln::topo::face<D>::lower_dim_adj_faces) + (mln::topo::face<D>::higher_dim_adj_faces): + Make it const. + (mln::topo::internal::lower_dim_adj_faces_if_dim_matches_<N, D>) + (mln::topo::internal::higher_dim_adj_faces_if_dim_matches_<N, D>): + Adjust. + +2008-09-30 Roland Levillain <roland(a)lrde.epita.fr> + Delegate pretty-printing of iterators on faces to mln::topo::face. * mln/topo/internal/complex_iter_base.hh (operator<<): Here. diff --git a/milena/mln/topo/face.hh b/milena/mln/topo/face.hh index c485697..1ff81e5 100644 --- a/milena/mln/topo/face.hh +++ b/milena/mln/topo/face.hh @@ -100,9 +100,9 @@ namespace mln // FIXME: To be overhauled. // FIXME: Why no `const' here? /// Return an array of face handles pointing to adjacent (n-1)-faces. - std::vector< face<D> > lower_dim_adj_faces(); + std::vector< face<D> > lower_dim_adj_faces() const; /// Return an array of face handles pointing to adjacent (n+1)-faces. - std::vector< face<D> > higher_dim_adj_faces(); + std::vector< face<D> > higher_dim_adj_faces() const; /// \} private: @@ -264,7 +264,7 @@ namespace mln template <unsigned N, unsigned D> struct lower_dim_adj_faces_if_dim_matches_ { - std::vector< face<D> > operator()(face<D>& face) + std::vector< face<D> > operator()(const face<D>& face) { metal::bool_< (N <= D) >::check(); metal::bool_< (N > 1) >::check(); @@ -288,7 +288,7 @@ namespace mln template <unsigned D> struct lower_dim_adj_faces_if_dim_matches_<1, D> { - std::vector< face<D> > operator()(face<D>& face) + std::vector< face<D> > operator()(const face<D>& face) { /// If we reached this function, then the dimension of FACE /// has to be 1. @@ -306,7 +306,7 @@ namespace mln template <unsigned N, unsigned D> struct higher_dim_adj_faces_if_dim_matches_ { - std::vector< face<D> > operator()(face<D>& face) + std::vector< face<D> > operator()(const face<D>& face) { metal::bool_< (N < D) >::check(); @@ -330,7 +330,7 @@ namespace mln template <unsigned D> struct higher_dim_adj_faces_if_dim_matches_<0, D> { - std::vector< face<D> > operator()(face<D>& face) + std::vector< face<D> > operator()(const face<D>& face) { /// If we reached this function, then the dimension of face /// has to be D - 1. @@ -350,25 +350,27 @@ namespace mln template <unsigned D> inline std::vector< face<D> > - face<D>::lower_dim_adj_faces() + face<D>::lower_dim_adj_faces() const { // FIXME: Warning: might prevent any attempt to build a complex<0>. metal::bool_< D != 0 >::check(); - mln_precondition(n_ > 0); - return internal::lower_dim_adj_faces_if_dim_matches_<D, D>()(*this); + return n_ > 0 ? + internal::lower_dim_adj_faces_if_dim_matches_<D, D>()(*this) : + std::vector< face<D> >(); } template <unsigned D> inline std::vector< face<D> > - face<D>::higher_dim_adj_faces() + face<D>::higher_dim_adj_faces() const { // FIXME: Warning: might prevent any attempt to build a complex<0>. metal::bool_< D != 0 >::check(); - mln_precondition(n_ < D); - return internal::higher_dim_adj_faces_if_dim_matches_<D - 1, D>()(*this); + return n_ < D ? + internal::higher_dim_adj_faces_if_dim_matches_<D - 1, D>()(*this) : + std::vector< face<D> >(); } -- 1.6.0.1

1 0

cleanup-2008 2440: Update reconstruction algorithms in theo's sandbox.
by Thierry Geraud 30 Sep '08

30 Sep '08

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008 Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Update reconstruction algorithms in theo's sandbox. * milena/mln/level/paste.hh: Fix warning. * milena/sandbox/geraud/Rd/hybrid.hh, * milena/sandbox/geraud/Rd/queue_based.hh, * milena/sandbox/geraud/Rd/parallel.cc, * milena/sandbox/geraud/Rd/union_find.hh, * milena/sandbox/geraud/Rd/parallel.hh, * milena/sandbox/geraud/Rd/sequential.cc, * milena/sandbox/geraud/Rd/utils.hh, * milena/sandbox/geraud/Rd/hybrid.cc, * milena/sandbox/geraud/Rd/queue_based.cc, * milena/sandbox/geraud/Rd/min.cc, * milena/sandbox/geraud/Rd/sequential.hh, * milena/sandbox/geraud/Rd/union_find.cc: Update. mln/level/paste.hh | 2 + sandbox/geraud/Rd/hybrid.cc | 20 ++++++++------- sandbox/geraud/Rd/hybrid.hh | 24 +++++++------------ sandbox/geraud/Rd/min.cc | 4 +-- sandbox/geraud/Rd/parallel.cc | 23 ++++++++++-------- sandbox/geraud/Rd/parallel.hh | 20 ++++----------- sandbox/geraud/Rd/queue_based.cc | 22 +++++++++-------- sandbox/geraud/Rd/queue_based.hh | 19 +++++---------- sandbox/geraud/Rd/sequential.cc | 23 ++++++++---------- sandbox/geraud/Rd/sequential.hh | 13 +--------- sandbox/geraud/Rd/union_find.cc | 22 +++++++++-------- sandbox/geraud/Rd/union_find.hh | 30 ++++++++--------------- sandbox/geraud/Rd/utils.hh | 49 +++++++++++++++++++-------------------- 13 files changed, 123 insertions(+), 148 deletions(-) Index: milena/mln/level/paste.hh --- milena/mln/level/paste.hh (revision 2439) +++ milena/mln/level/paste.hh (working copy) @@ -84,6 +84,8 @@ mlc_converts_to(mln_value(I), mln_value(J))::check(); mln_precondition(exact(data).has_data()); mln_precondition(exact(data).domain() <= exact(destination).domain()); + (void)data; + (void)destination; } } // end of namespace mln::level::internal Index: milena/sandbox/geraud/Rd/hybrid.hh --- milena/sandbox/geraud/Rd/hybrid.hh (revision 2439) +++ milena/sandbox/geraud/Rd/hybrid.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -46,17 +46,11 @@ I hybrid(const I& f, const I& g, const N& nbh, bool echo = false) { - typedef mln_point(I) point; + typedef mln_site(I) point; std::queue<point> q; - f.name_it("f"); - g.name_it("g"); - // initialisation - I o(f.domain()); - o.name_it("o"); - level::paste(f, o); - // WAS: I o = clone(f); + I o = clone(f); unsigned n_init_pushs = 0, n_body_pushs = 0, n_pops = 0; @@ -72,8 +66,10 @@ for_all(p) { o(p) = min( max_Nplus(o, p,nbh), g(p) ); - for_all(n) if (f.has(n) and n < p) // N+ - if (o(n) < o(p) and o(n) < g(n)) + for_all(n) + if (f.has(n) && + util::ord_strict(n.to_site(), p.to_site())) // N+ + if (o(n) < o(p) && o(n) < g(n)) { q.push(p); ++n_init_pushs; @@ -92,7 +88,7 @@ q.pop(); ++n_pops; for_all(n) if (f.has(n)) - if (o(n) < o(p) and o(n) != g(n)) + if (o(n) < o(p) && o(n) != g(n)) { o(n) = min(o(p), g(n)); if (echo) std::cout << " push " << n; @@ -103,13 +99,11 @@ if (echo) std::cout << std::endl; } - + if (echo) std::cout << "n_init_pushs = " << n_init_pushs << std::endl << "n_body_pushs = " << n_body_pushs << std::endl << "n_pops = " << n_pops << std::endl; - print_counts(); - return o; } Index: milena/sandbox/geraud/Rd/queue_based.hh --- milena/sandbox/geraud/Rd/queue_based.hh (revision 2439) +++ milena/sandbox/geraud/Rd/queue_based.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research && Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -18,7 +18,7 @@ // 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 +// file, or you compile this file && 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 @@ -52,13 +52,9 @@ if (echo) std::cout << std::endl; - f.name_it("f"); - g.name_it("g"); - - typedef mln_point(I) point; + typedef mln_site(I) point; std::queue<point> q; I o; - o.name_it("o"); unsigned n_init_pushs = 0, n_body_pushs = 0, n_pops = 0; @@ -71,8 +67,8 @@ mln_piter(I) p(f.domain()); mln_niter(N) n(nbh, p); - for_all(p) if (o(p) != 0) // p in M - for_all(n) if (f.has(n) and o(n) == 0) // n not in M + for_all(p) if (o(p) != 0u) // p in M + for_all(n) if (f.has(n) && o(n) == 0u) // n not in M { q.push(p); que(p) = true; @@ -94,7 +90,7 @@ ++n_pops; for_all(n) if (f.has(n)) { - if (o(n) < o(p) and o(n) != g(n)) + if (o(n) < o(p) && o(n) != g(n)) { o(n) = min(o(p), g(n)); if (echo) std::cout << " push " << n; @@ -110,12 +106,11 @@ if (echo) std::cout << std::endl; } + if (echo) std::cout << "n_init_pushs = " << n_init_pushs << std::endl << "n_body_pushs = " << n_body_pushs << std::endl << "n_pops = " << n_pops << std::endl; - print_counts(); - return o; } Index: milena/sandbox/geraud/Rd/parallel.cc --- milena/sandbox/geraud/Rd/parallel.cc (revision 2439) +++ milena/sandbox/geraud/Rd/parallel.cc (working copy) @@ -1,7 +1,7 @@ #include <iostream> -#include <mln/core/image2d.hh> -#include <mln/core/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> #include <mln/debug/println.hh> @@ -14,7 +14,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " f.pgm g.pgm c output.pgm" << std::endl - << "reconstruction by dilation (parallel version; may 2007)" << std::endl + << "reconstruction by dilation (parallel version; sep 2008)" << std::endl << "f = marker (to be dilated)" << std::endl << "g = mask (constraint >= f)" << std::endl << "c: 4 or 8" << std::endl; @@ -30,22 +30,25 @@ using namespace mln; using value::int_u8; + border::thickness = 0; // Safety. + typedef image2d<int_u8> I; int c = atoi(argv[3]); if (c != 4 and c != 8) usage(argv); - I f = io::pgm::load<int_u8>(argv[1]); - I g = io::pgm::load<int_u8>(argv[2]); + I f, g; + io::pgm::load(f, argv[1]); + io::pgm::load(g, argv[2]); - if (not (f <= g)) + if (! (f <= g)) { - std::cerr << "pb" << std::endl; + std::cerr << "error: the precondition 'f <= g' is not true" << std::endl; return 1; } - io::pgm::save(morpho::Rd::parallel(f, g, - (c == 4 ? c4() : c8())), - argv[4]); + I o = morpho::Rd::parallel(f, g, + (c == 4 ? c4() : c8())); + io::pgm::save(o, argv[4]); } Index: milena/sandbox/geraud/Rd/union_find.hh --- milena/sandbox/geraud/Rd/union_find.hh (revision 2439) +++ milena/sandbox/geraud/Rd/union_find.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -44,7 +44,7 @@ template <typename I, typename N> struct union_find_t { - typedef mln_point(I) point; + typedef mln_site(I) point; typedef mln_value(I) value; // in: @@ -56,28 +56,21 @@ // aux: std::vector<point> S; - // was: I data; - mln_ch_value(I, bool) isproc; + mln_ch_value(I, bool) deja_vu; mln_ch_value(I, point) parent; union_find_t(const I& f, const I& g, const N& nbh) : f(f), g(g), nbh(nbh) { - f.name_it("f"); - g.name_it("g"); initialize(o, f); - o.name_it("o"); initialize(parent, f); - parent.name_it("parent"); - initialize(isproc, f); - isproc.name_it("isproc"); - // was: initialize(data, f); + initialize(deja_vu, f); // init - level::fill(isproc, false); + level::fill(deja_vu, false); S = histo_reverse_sort(g); - level::paste(f, o); // new: replace make_set(p) { data(p) = f(p) } + level::paste(f, o); // Replace: for all p, make_set(p) { data(p) = f(p) } // first pass @@ -90,11 +83,11 @@ for_all(n) { if (f.has(n)) - mln_invariant(isproc(n) == is_proc(n, p)); - if (f.has(n) and isproc(n)) + mln_invariant(deja_vu(n) == is_proc(n, p)); + if (f.has(n) && deja_vu(n)) do_union(n, p); } - isproc(p) = true; + deja_vu(p) = true; } // second pass @@ -109,13 +102,12 @@ o(p) = o(parent(p)); } - print_counts(); - } bool is_proc(const point& n, const point& p) const { - return g(n) > g(p) or (g(n) == g(p) and n < p); + return g(n) > g(p) or (g(n) == g(p) && + util::ord_strict(n, p)); } void make_set(const point& p) Index: milena/sandbox/geraud/Rd/parallel.hh --- milena/sandbox/geraud/Rd/parallel.hh (revision 2439) +++ milena/sandbox/geraud/Rd/parallel.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -45,21 +45,14 @@ I parallel(const I& f, const I& g, const N& nbh, bool test = true) { -// if (test) -// mln_precondition(f <= g); - - f.name_it("f"); - g.name_it("g"); + if (test) + mln_precondition(f <= g); I o_(f.domain()); - o_.name_it("o_"); mln_piter(I) p(f.domain()); // initialisation - I o(f.domain()); - o.name_it("o"); - level::paste(f, o); - // WAS: I o = clone(f); + I o = clone(f); bool stability; do @@ -77,9 +70,8 @@ } while (not stability); - print_counts(); - - // mln_postcondition(o <= g); + if (test) + mln_postcondition(o <= g); return o; } Index: milena/sandbox/geraud/Rd/sequential.cc --- milena/sandbox/geraud/Rd/sequential.cc (revision 2439) +++ milena/sandbox/geraud/Rd/sequential.cc (working copy) @@ -1,5 +1,5 @@ -#include <mln/core/image2d.hh> -#include <mln/core/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> #include <mln/debug/println.hh> #include <mln/io/pgm/load.hh> @@ -11,7 +11,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " f.pgm g.pgm c output.pgm" << std::endl - << "reconstruction by dilation (sequential version; may 2007)" << std::endl + << "reconstruction by dilation (sequential version; sep 2008)" << std::endl << "f = marker (to be dilated)" << std::endl << "g = mask (constraint >= f)" << std::endl << "c: 4 or 8" << std::endl; @@ -27,25 +27,24 @@ using namespace mln; using value::int_u8; + border::thickness = 0; // Safety. + typedef image2d<int_u8> I; int c = atoi(argv[3]); if (c != 4 and c != 8) usage(argv); - I f = io::pgm::load<int_u8>(argv[1]); - f.name_it("main.f"); - - I g = io::pgm::load<int_u8>(argv[2]); - g.name_it("main.g"); + I f, g; + io::pgm::load(f, argv[1]); + io::pgm::load(g, argv[2]); if (not (f <= g)) { - std::cerr << "pb" << std::endl; + std::cerr << "error: the precondition 'f <= g' is not true" << std::endl; return 1; } - io::pgm::save(morpho::Rd::sequential(f, g, - (c == 4 ? c4() : c8())), - argv[4]); + I o = morpho::Rd::sequential(f, g, (c == 4 ? c4() : c8())); + io::pgm::save(o, argv[4]); } Index: milena/sandbox/geraud/Rd/utils.hh --- milena/sandbox/geraud/Rd/utils.hh (revision 2439) +++ milena/sandbox/geraud/Rd/utils.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -31,9 +31,11 @@ # include <vector> # include <mln/core/concept/image.hh> -# include <mln/core/clone.hh> +# include <mln/core/routine/clone.hh> -# include <mln/level/fill.hh> +# include <mln/util/ord.hh> + +# include <mln/level/fill_with_value.hh> # include <mln/level/paste.hh> # include <mln/level/compare.hh> @@ -59,7 +61,7 @@ template <typename I> I minimun(const I& ima1, const I& ima2) { - mln_precondition(ima1.has_data() and ima2.has_data()); + mln_precondition(ima1.has_data() && ima2.has_data()); mln_precondition(ima1.domain() == ima2.domain()); I out(ima1.domain()); mln_piter(I) p(ima1.domain()); @@ -75,7 +77,7 @@ mln_value(I) v = ima(p); mln_niter(N) n(nbh, p); for_all(n) - if (ima.has(n) and ima(n) > v) + if (ima.has(n) && ima(n) > v) v = ima(n); return v; } @@ -87,7 +89,9 @@ mln_value(I) v = ima(p); mln_niter(N) n(nbh, p); for_all(n) - if (ima.has(n) and n > p and ima(n) > v) + if (ima.has(n) && + util::ord_strict(p.to_site(), n.to_site()) && + ima(n) > v) v = ima(n); return v; } @@ -98,7 +102,9 @@ mln_value(I) v = ima(p); mln_niter(N) n(nbh, p); for_all(n) - if (ima.has(n) and n < p and ima(n) > v) + if (ima.has(n) && + util::ord_strict(n.to_site(), p.to_site()) && + ima(n) > v) v = ima(n); return v; } @@ -116,7 +122,7 @@ // template <typename I> -// std::vector<mln_point(I)> histo_sort(const I& ima) +// std::vector<mln_site(I)> histo_sort(const I& ima) // { // std::vector<unsigned> h = compute_histo(ima); // // preparing output data @@ -124,9 +130,9 @@ // loc[0] = 0; // for (int l = 1; l < 256; ++l) // loc[l] = loc[l-1] + h[l-1]; -// std::vector<mln_point(I)> vec(ima.points().npoints()); +// std::vector<mln_site(I)> vec(ima.nsites()); // // storing output data -// mln_piter(I) p(ima.points()); +// mln_piter(I) p(ima.domain()); // for_all(p) // vec[loc[ima(p)]++] = p; // return vec; @@ -134,7 +140,7 @@ template <typename I> - std::vector<mln_point(I)> histo_reverse_sort(const I& ima) + std::vector<mln_site(I)> histo_reverse_sort(const I& ima) { std::vector<unsigned> h = compute_histo(ima); // preparing output data @@ -142,7 +148,7 @@ loc[255] = 0; for (int l = 254; l >= 0; --l) loc[l] = loc[l+1] + h[l+1]; - std::vector<mln_point(I)> vec(ima.domain().npoints()); + std::vector<mln_site(I)> vec(ima.nsites()); // storing output data mln_piter(I) p(ima.domain()); for_all(p) @@ -155,7 +161,7 @@ template <typename I, typename N> struct regional_maxima_t { - typedef mln_point(I) point; + typedef mln_site(I) point; typedef mln_ch_value(I, bool) image_bool; typedef mln_ch_value(I, point) image_point; @@ -168,26 +174,21 @@ // aux: std::vector<point> S; - image_bool is_proc; + image_bool deja_vu; image_bool attr; image_point parent; regional_maxima_t(const I& f, const N& nbh) : f(f), nbh(nbh) { - f.name_it("rm.f"); initialize(o, f); - o.name_it("rm.o"); initialize(parent, f); - parent.name_it("rm.parent"); initialize(attr, f); - attr.name_it("rm.attr"); - initialize(is_proc, f); - is_proc.name_it("rm.is_proc"); + initialize(deja_vu, f); // init - level::fill(is_proc, false); + level::fill_with_value(deja_vu, false); S = histo_reverse_sort(f); // first pass @@ -199,14 +200,14 @@ make_set(p); mln_niter(N) n(nbh, p); for_all(n) - if (f.has(n) and is_proc(n)) + if (f.has(n) && deja_vu(n)) { if (f(n) == f(p)) do_union(n, p); else // f(n) > f(p) attr(p) = false; } - is_proc(p) = true; + deja_vu(p) = true; } // second pass @@ -242,7 +243,7 @@ if (r != p) { parent(r) = p; - attr(p) = attr(p) and attr(r); + attr(p) = attr(p) && attr(r); } } Index: milena/sandbox/geraud/Rd/hybrid.cc --- milena/sandbox/geraud/Rd/hybrid.cc (revision 2439) +++ milena/sandbox/geraud/Rd/hybrid.cc (working copy) @@ -1,7 +1,7 @@ #include <iostream> -#include <mln/core/image2d.hh> -#include <mln/core/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> #include <mln/debug/println.hh> @@ -14,7 +14,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " f.pgm g.pgm c output.pgm" << std::endl - << "reconstruction by dilation (hybrid version; may 2007)" << std::endl + << "reconstruction by dilation (hybrid version; sep 2008)" << std::endl << "f = marker (to be dilated)" << std::endl << "g = mask (constraint >= f)" << std::endl << "c: 4 or 8" << std::endl; @@ -30,22 +30,24 @@ using namespace mln; using value::int_u8; + border::thickness = 0; // Safety. + typedef image2d<int_u8> I; int c = atoi(argv[3]); if (c != 4 and c != 8) usage(argv); - I f = io::pgm::load<int_u8>(argv[1]); - I g = io::pgm::load<int_u8>(argv[2]); + I f, g; + io::pgm::load(f, argv[1]); + io::pgm::load(g, argv[2]); if (not (f <= g)) { - std::cerr << "pb" << std::endl; + std::cerr << "error: the precondition 'f <= g' is not true" << std::endl; return 1; } - io::pgm::save(morpho::Rd::hybrid(f, g, - (c == 4 ? c4() : c8())), - argv[4]); + I o = morpho::Rd::hybrid(f, g, (c == 4 ? c4() : c8())); + io::pgm::save(o, argv[4]); } Index: milena/sandbox/geraud/Rd/queue_based.cc --- milena/sandbox/geraud/Rd/queue_based.cc (revision 2439) +++ milena/sandbox/geraud/Rd/queue_based.cc (working copy) @@ -1,5 +1,5 @@ -#include <mln/core/image2d.hh> -#include <mln/core/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> #include <mln/debug/println.hh> @@ -12,7 +12,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " f.pgm g.pgm c output.pgm" << std::endl - << "reconstruction by dilation (queue_based version; may 2007)" << std::endl + << "reconstruction by dilation (queue_based version; sep 2008)" << std::endl << "f = marker (to be dilated)" << std::endl << "g = mask (constraint >= f)" << std::endl << "c: 4 or 8" << std::endl; @@ -28,22 +28,24 @@ using namespace mln; using value::int_u8; + border::thickness = 0; // Safety. + typedef image2d<int_u8> I; int c = atoi(argv[3]); if (c != 4 and c != 8) usage(argv); - I f = io::pgm::load<int_u8>(argv[1]); - I g = io::pgm::load<int_u8>(argv[2]); + I f, g; + io::pgm::load(f, argv[1]); + io::pgm::load(g, argv[2]); - if (not (f <= g)) + if (! (f <= g)) { - std::cerr << "pb" << std::endl; + std::cerr << "error: the precondition 'f <= g' is not true" << std::endl; return 1; } - io::pgm::save(morpho::Rd::queue_based(f, g, - (c == 4 ? c4() : c8())), - argv[4]); + I o = morpho::Rd::queue_based(f, g, (c == 4 ? c4() : c8())); + io::pgm::save(o, argv[4]); } Index: milena/sandbox/geraud/Rd/min.cc --- milena/sandbox/geraud/Rd/min.cc (revision 2439) +++ milena/sandbox/geraud/Rd/min.cc (working copy) @@ -1,4 +1,4 @@ -#include <mln/core/image2d.hh> +#include <mln/core/image/image2d.hh> #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> @@ -7,7 +7,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " 1.pgm 2.pgm out.pgm" << std::endl - << "(2008 Feb)" << std::endl; + << "(sep 2008)" << std::endl; exit(1); } Index: milena/sandbox/geraud/Rd/sequential.hh --- milena/sandbox/geraud/Rd/sequential.hh (revision 2439) +++ milena/sandbox/geraud/Rd/sequential.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -45,17 +45,10 @@ { mln_precondition(f <= g); - f.name_it("f"); - g.name_it("g"); - I o_(f.domain()); - o_.name_it("o_"); // initialisation - I o(f.domain()); - o.name_it("o"); - level::paste(f, o); - // WAS: I o = clone(f); + I o = clone(f); bool stability; do @@ -80,8 +73,6 @@ } while (not stability); - print_counts(); - mln_postcondition(o <= g); return o; } Index: milena/sandbox/geraud/Rd/union_find.cc --- milena/sandbox/geraud/Rd/union_find.cc (revision 2439) +++ milena/sandbox/geraud/Rd/union_find.cc (working copy) @@ -1,5 +1,5 @@ -#include <mln/core/image2d.hh> -#include <mln/core/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> #include <mln/debug/println.hh> @@ -13,7 +13,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " f.pgm g.pgm c output.pgm" << std::endl - << "reconstruction by dilation (union_find version; may 2007)" << std::endl + << "reconstruction by dilation (union_find version; sep 2008)" << std::endl << "f = marker (to be dilated)" << std::endl << "g = mask (constraint >= f)" << std::endl << "c: 4 or 8" << std::endl; @@ -29,22 +29,24 @@ using namespace mln; using value::int_u8; + border::thickness = 0; // Safety. + typedef image2d<int_u8> I; int c = atoi(argv[3]); if (c != 4 and c != 8) usage(argv); - I f = io::pgm::load<int_u8>(argv[1]); - I g = io::pgm::load<int_u8>(argv[2]); + I f, g; + io::pgm::load(f, argv[1]); + io::pgm::load(g, argv[2]); - if (not (f <= g)) + if (! (f <= g)) { - std::cerr << "pb" << std::endl; + std::cerr << "error: the precondition 'f <= g' is not true" << std::endl; return 1; } - io::pgm::save(morpho::Rd::union_find(f, g, - (c == 4 ? c4() : c8())), - argv[4]); + I o = morpho::Rd::union_find(f, g, (c == 4 ? c4() : c8())); + io::pgm::save(o, argv[4]); }

1 0