https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Revamp design of Neighborhood and Window. Add a new utility set whose behavior is transparent for the client (conversely to util::lazy_set_) and memory saving (conversely to internal::set_of_). * mln/util/set.hh: New. * tests/util/set.cc: New. Revamp design of Neighborhood and Window. * doc/tutorial/examples/image2d.cc: Use window2d. * mln/core/point.hh (dpsite): New associated type. * mln/core/window.hh: Update inheritance. (is_centered): Move here from dpoints_base_; such a method is not featured by neighborhoods so it cannot be factored in window_base. (fwd_qiter, bkd_qiter, insert): Move in impl super class. (operator<<): Split decl and def; update. (window): Now rely on... * mln/core/internal/basic_window_impl.hh: ...this new class. (set_of_): Replace inheritance by delegation to util::set. (fwd_qiter, bkd_qiter, insert): New factor defs; they were in window class. Now delegate code to insert_. (insert_): New default impl; such method can be overridden. * mln/core/internal/window_base.hh: New; for consistency purpose. * mln/core/dpoint.hh (psite, site): New. * mln/core/concept/neighborhood.hh: Layout. (Neighborhood): Change inheritance to Window. (dpoint, point): Remove cause not general. * mln/core/concept/window.hh (point, dpoint): Rename as... (psite, dpsite): ...these. (site): New associated type. (is_empty, is_centered, is_symmetric, sym): Remove; not general. * mln/core/concept/doc/window.hh: Update. doc/tutorial/examples/image2d.cc | 8 mln/core/concept/doc/window.hh | 25 -- mln/core/concept/neighborhood.hh | 11 - mln/core/concept/window.hh | 31 --- mln/core/dpoint.hh | 6 mln/core/internal/basic_window_impl.hh | 162 ++++++++++++---- mln/core/internal/window_base.hh | 83 ++++++++ mln/core/point.hh | 3 mln/core/window.hh | 102 ++-------- mln/util/set.hh | 316 +++++++++++++-------------------- tests/util/set.cc | 51 +++++ 11 files changed, 439 insertions(+), 359 deletions(-) Index: tests/util/set.cc --- tests/util/set.cc (revision 0) +++ tests/util/set.cc (revision 0) @@ -0,0 +1,51 @@ +// 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. + +/*! + * \file tests/util/set.cc + * + * \brief test of mln::util::set + * + */ + +#include <mln/util/set.hh> + +int main () +{ + using namespace mln; + util::set<int> s; + s.insert(1).insert(6).insert(6).insert(4); + mln_assertion(s.nelements() == 3); + s.remove(6); + mln_assertion(s.nelements() == 2); + mln_assertion(! s.has(6)); // not frozen + s.insert(6); + mln_assertion(s[2] == 6); + mln_assertion(s.has(6)); // frozen + s.clear(); + mln_assertion(s.is_empty()); +} Index: doc/tutorial/examples/image2d.cc --- doc/tutorial/examples/image2d.cc (revision 2012) +++ doc/tutorial/examples/image2d.cc (working copy) @@ -1,4 +1,5 @@ # include <mln/core/image2d.hh> +# include <mln/core/window2d.hh> int main() @@ -7,4 +8,11 @@ image2d<char> ima(2, 3); mln_invariant(ima.nsites() == 6); + + window2d win; + win + .insert(-1, 0) + .insert(0, -1) + .insert(-1,-1); + std::cout << win << std::endl; } Index: mln/core/point.hh --- mln/core/point.hh (revision 2012) +++ mln/core/point.hh (working copy) @@ -93,6 +93,9 @@ /// Dpoint associated type. typedef dpoint_<M,C> dpoint; + /// DPsite associated type. + typedef dpoint_<M,C> dpsite; + /// Coordinate associated type. typedef C coord; Index: mln/core/window.hh --- mln/core/window.hh (revision 2012) +++ mln/core/window.hh (working copy) @@ -36,9 +36,8 @@ * point_, neighb_, etc. */ -# include <mln/core/concept/window.hh> -# include <mln/core/concept/point_site.hh> -# include <mln/core/internal/dpoints_base.hh> +# include <mln/core/internal/window_base.hh> +# include <mln/core/internal/basic_window_impl.hh> # include <mln/core/dpoint.hh> # include <mln/core/box.hh> @@ -50,34 +49,17 @@ namespace mln { - // fwd decls - template <typename D> class dpoints_fwd_piter; - template <typename D> class dpoints_bkd_piter; - - /*! \brief Generic window class. * * This type of window is just like a set of delta-points. The * parameter is \c D, type of delta-point. */ template <typename D> - class window : public Window< window<D> >, - public internal::dpoints_base_<D, window<D> > + class window : public internal::window_base< D, window<D> >, + public internal::basic_window_impl< D, window<D> > { - typedef internal::dpoints_base_<D, window<D> > super_; public: - /*! \brief Site_Iterator type to browse the points of a generic window - * w.r.t. the ordering of delta-points. - */ - typedef dpoints_fwd_piter<D> fwd_qiter; - - /*! \brief Site_Iterator type to browse the points of a generic window - * w.r.t. the reverse ordering of delta-points. - */ - typedef dpoints_bkd_piter<D> bkd_qiter; - - /*! \brief Constructor without argument. * * The constructed window is empty. @@ -85,24 +67,16 @@ window(); + /*! \brief Test if the window is centered. + * + * \return True if the delta-point 0 belongs to the window. + */ + bool is_centered() const; + /*! \brief Test if the window is symmetric. */ bool is_symmetric() const; - /// Insert a delta-point \p dp. - window<D>& insert(const D& dp); - - /// \{ Insertion of a delta-point with different numbers of - /// arguments (coordinates) w.r.t. the dimension. - window<D>& insert(const mln_coord(D)& dind); // For 1D. - - window<D>& insert(const mln_coord(D)& drow, - const mln_coord(D)& dcol); // For 2D. - - window<D>& insert(const mln_coord(D)& dsli, - const mln_coord(D)& drow, - const mln_coord(D)& dcol); // For 3D. - /// \} /// Apply a central symmetry to the target window. window<D>& sym(); @@ -113,15 +87,9 @@ }; - // FIXME: Move code at EOF + doc. + // FIXME: Doc! template <typename D> - std::ostream& operator<<(std::ostream& ostr, const window<D>& win) - { - // FIXME - for (unsigned i = 0; i < win.ndpoints(); ++i) - ostr << win.dp(i); - return ostr; - } + std::ostream& operator<<(std::ostream& ostr, const window<D>& win); @@ -134,7 +102,7 @@ window<D>::window() { // FIXME HERE: Was: mln::metal::is_a<D, Dpoint>::check(); - mln::metal::is_a<D, Delta_Point_Site>::check(); + // mln::metal::is_a<D, Delta_Point_Site>::check(); } template <typename D> @@ -146,42 +114,10 @@ template <typename D> inline - window<D>& - window<D>::insert(const D& dp) + bool window<D>::is_centered() const { - mln_precondition(! has(dp)); - this->super_::insert(dp); - return *this; - } - - template <typename D> - inline - window<D>& - window<D>::insert(const mln_coord(D)& dind) - { - D dp(dind); - mln_precondition(! has(dp)); - return this->insert(dp); - } - - template <typename D> - inline - window<D>& - window<D>::insert(const mln_coord(D)& drow, const mln_coord(D)& dcol) - { - D dp(drow, dcol); - mln_precondition(! has(dp)); - return this->insert(dp); - } - - template <typename D> - inline - window<D>& - window<D>::insert(const mln_coord(D)& dsli, const mln_coord(D)& drow, const mln_coord(D)& dcol) - { - D dp(dsli, drow, dcol); - mln_precondition(! has(dp)); - return this->insert(dp); + static const D origin = all_to(0); + return this->dps_.has(origin); // FIXME: Use literal::origin. } template <typename D> @@ -197,6 +133,12 @@ return *this; } + template <typename D> + std::ostream& operator<<(std::ostream& ostr, const window<D>& win) + { + return ostr << win.dps_hook(); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/core/internal/basic_window_impl.hh --- mln/core/internal/basic_window_impl.hh (revision 2012) +++ mln/core/internal/basic_window_impl.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 @@ -25,15 +25,15 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_CORE_INTERNAL_DPOINTS_BASE_HH -# define MLN_CORE_INTERNAL_DPOINTS_BASE_HH +#ifndef MLN_CORE_INTERNAL_BASIC_WINDOW_IMPL_HH +# define MLN_CORE_INTERNAL_BASIC_WINDOW_IMPL_HH -/*! \file mln/core/internal/dpoints_base.hh +/*! \file mln/core/internal/basic_window_impl.hh * * \brief Definition of a base class for classes based on a set of dpoints. */ -# include <mln/core/internal/set_of.hh> +# include <mln/util/set.hh> # include <mln/fun/i2v/all_to.hh> # include <mln/norm/linfty.hh> @@ -41,6 +41,11 @@ namespace mln { + // Fwd decls. + template <typename D> class dpoints_fwd_piter; + template <typename D> class dpoints_bkd_piter; + + namespace internal { @@ -48,23 +53,27 @@ * */ template <typename D, typename E> - class dpoints_base_ : protected internal::set_of_<D> + class basic_window_impl { - typedef internal::set_of_<D> super_; - public: + util::set<D> dps_; - /// Point associated type. - typedef mln_point(D) point; + public: - /// Dpoint associated type. - typedef D dpoint; + /*! \brief Site_Iterator type to browse the points of a basic window + * whatever the ordering of delta-points. + */ + typedef dpoints_fwd_piter<D> qiter; + /*! \brief Site_Iterator type to browse the points of a basic window + * w.r.t. the ordering of delta-points. + */ + typedef dpoints_fwd_piter<D> fwd_qiter; - /*! \brief Test if the window is centered. - * - * \return True if the delta-point 0 belongs to the window. + /*! \brief Site_Iterator type to browse the points of a basic window + * w.r.t. the reverse ordering of delta-points. */ - bool is_centered() const; + typedef dpoints_bkd_piter<D> bkd_qiter; + /*! \brief Test if the window is empty (null size; no delta-point). */ @@ -84,11 +93,36 @@ // Give the \p i-th delta-point. const D& dp(unsigned i) const; + // Give the vector of delta-points. - const std::vector<D>& vect() const; + const std::vector<D>& std_vector() const; + + + /// Insert a delta-point \p dp. + E& insert(const D& dp); + + /// \{ Insertion of a delta-point with different numbers of + /// arguments (coordinates) w.r.t. the dimension. + E& insert(const mln_coord(D)& dind); // For 1D. + + E& insert(const mln_coord(D)& drow, + const mln_coord(D)& dcol); // For 2D. + + E& insert(const mln_coord(D)& dsli, + const mln_coord(D)& drow, + const mln_coord(D)& dcol); // For 3D. + /// \} + + + const util::set<D>& dps_hook() const; protected: - dpoints_base_(); + + basic_window_impl(); + + void insert_(const D& dp); // The only routine to effectively insert a dp. + // This is a default implementation. This routine can be + // overidden in sub-classes. }; @@ -97,29 +131,22 @@ template <typename D, typename E> inline - dpoints_base_<D,E>::dpoints_base_() + basic_window_impl<D,E>::basic_window_impl() { } template <typename D, typename E> inline - bool dpoints_base_<D,E>::is_centered() const + bool basic_window_impl<D,E>::is_empty() const { - static const D origin = all_to(0); - return this->super_::has(origin); + return dps_.is_empty(); } template <typename D, typename E> inline - bool dpoints_base_<D,E>::is_empty() const - { - return this->super_::is_empty(); - } - - template <typename D, typename E> - inline - unsigned dpoints_base_<D,E>::delta() const + unsigned basic_window_impl<D,E>::delta() const { + // FIXME: Is-it correct? unsigned d = 0; const unsigned n = ndpoints(); for (unsigned i = 0; i < n; ++i) @@ -134,34 +161,91 @@ template <typename D, typename E> inline unsigned - dpoints_base_<D,E>::ndpoints() const + basic_window_impl<D,E>::ndpoints() const { - return this->super_::nelements(); + return dps_.nelements(); } template <typename D, typename E> inline const D& - dpoints_base_<D,E>::dp(unsigned i) const + basic_window_impl<D,E>::dp(unsigned i) const { mln_precondition(i < ndpoints()); - return this->element(i); + return dps_[i]; } template <typename D, typename E> inline const std::vector<D>& - dpoints_base_<D,E>::vect() const + basic_window_impl<D,E>::vect() const { - return this->super_::vect(); + return dps_.vect(); } template <typename D, typename E> inline bool - dpoints_base_<D,E>::has(const D& dp) const + basic_window_impl<D,E>::has(const D& dp) const + { + return dps_.has(dp); + } + + template <typename D, typename E> + inline + E& + basic_window_impl<D,E>::insert(const D& dp) + { + E& self_ = internal::force_exact<E>(*this); + self_.insert_(dp); + return self_; + } + + template <typename D, typename E> + inline + E& + basic_window_impl<D,E>::insert(const mln_coord(D)& dind) + { + D dp(dind); + return insert(dp); + } + + template <typename D, typename E> + inline + E& + basic_window_impl<D,E>::insert(const mln_coord(D)& drow, + const mln_coord(D)& dcol) + { + D dp(drow, dcol); + return insert(dp); + } + + template <typename D, typename E> + inline + E& + basic_window_impl<D,E>::insert(const mln_coord(D)& dsli, + const mln_coord(D)& drow, + const mln_coord(D)& dcol) + { + D dp(dsli, drow, dcol); + return insert(dp); + } + + template <typename D, typename E> + inline + void + basic_window_impl<D,E>::insert_(const D& dp) + { + mln_precondition(! has(dp)); + dps_.insert(dp); + } + + template <typename D, typename E> + inline + const util::set<D>& + basic_window_impl<D,E>::dps_hook() const { - return this->super_::has(dp); + return dps_; } # endif // ! MLN_INCLUDE_ONLY @@ -171,4 +255,4 @@ } // end of namespace mln -#endif // ! MLN_CORE_INTERNAL_DPOINTS_BASE_HH +#endif // ! MLN_CORE_INTERNAL_BASIC_WINDOW_IMPLHH Index: mln/core/internal/window_base.hh --- mln/core/internal/window_base.hh (revision 0) +++ mln/core/internal/window_base.hh (revision 0) @@ -0,0 +1,83 @@ +// 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_WINDOW_BASE_HH +# define MLN_CORE_INTERNAL_WINDOW_BASE_HH + +/*! \file mln/core/internal/window_base.hh + * + * \brief Definition of a base class for site set classes. + */ + +# include <mln/core/concept/window.hh> + + +namespace mln +{ + + namespace internal + { + + + /*! \internal A base class for window classes. + * + * \p D is a dpsite type. + */ + template <typename D, typename E> + struct window_base : public Window<E> + { + + /// DPsite associated type. + typedef D dpsite; + + /// Psite associated type. + typedef mln_psite(D) psite; + + /// Site associated type. + typedef mln_site(D) site; + + protected: + window_base(); + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename S, typename E> + inline + window_base<S,E>::window_base() + { + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::internal + +} // end of namespace mln + + +#endif // ! MLN_CORE_INTERNAL_WINDOW_BASE_HH Index: mln/core/dpoint.hh --- mln/core/dpoint.hh (revision 2012) +++ mln/core/dpoint.hh (working copy) @@ -72,6 +72,12 @@ /// Point associated type. typedef point_<M,C> point; + /// Psite associated type. + typedef point_<M,C> psite; + + /// Site associated type. + typedef point_<M,C> site; + /// Coordinate associated type. typedef C coord; Index: mln/core/concept/neighborhood.hh --- mln/core/concept/neighborhood.hh (revision 2012) +++ mln/core/concept/neighborhood.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 @@ -32,7 +32,7 @@ * \brief Definition of the concept of mln::Neighborhood. */ -# include <mln/core/concept/object.hh> +# include <mln/core/concept/window.hh> namespace mln @@ -55,7 +55,7 @@ * class contents. */ template <typename E> - struct Neighborhood : public Object<E> + struct Neighborhood : public Window<E> { typedef Neighborhood<void> category; @@ -63,9 +63,6 @@ typedef niter; typedef fwd_niter; typedef bkd_niter; - - typedef dpoint; - typedef point; */ protected: @@ -82,8 +79,6 @@ typedef mln_niter(E) niter; typedef mln_fwd_niter(E) fwd_niter; typedef mln_bkd_niter(E) bkd_niter; - typedef mln_dpoint(E) dpoint; - typedef mln_point(E) point; } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/concept/window.hh --- mln/core/concept/window.hh (revision 2012) +++ mln/core/concept/window.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 @@ -61,20 +61,13 @@ typedef Window<void> category; /* - typedef point; - typedef dpoint; + typedef site; + typedef psite; + typedef dpsite; typedef qiter; typedef fwd_qiter; typedef bkd_qiter; - - bool is_empty() const; - bool is_centered() const; - bool is_symmetric() const; - - unsigned delta() const; - - E& sym(); */ protected: @@ -99,23 +92,13 @@ inline Window<E>::Window() { - typedef mln_point(E) point; - typedef mln_dpoint(E) dpoint; + 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; - - bool (E::*m1)() const = & E::is_empty; - m1 = 0; - bool (E::*m2)() const = & E::is_centered; - m2 = 0; - bool (E::*m3)() const = & E::is_symmetric; - m3 = 0; - unsigned (E::*m4)() const = & E::delta; - m4 = 0; - E& (E::*m5)() = & E::sym; - m5 = 0; } template <typename Wl, typename Wr> Index: mln/core/concept/doc/window.hh --- mln/core/concept/doc/window.hh (revision 2012) +++ mln/core/concept/doc/window.hh (working copy) @@ -59,31 +59,6 @@ * points in a backward way. */ typedef void bkd_qiter; - - /*! \brief Test if the window is empty. - * - * A window of null size is empty. - */ - bool is_empty() const; - - /*! \brief Test if the window is centered. - * - * A window is centered is the origin belongs to the window. - */ - bool is_centered() const; - - /*! \brief Test if the window is symmetric. - */ - bool is_symmetric() const; - - /*! \brief Give the maximum coordinate gap between the window - center and a window point. - */ - unsigned delta() const; - - /*! \brief Apply a central symmetry to the target window. - */ - E& sym(); }; } // end of namespace mln::doc Index: mln/util/set.hh --- mln/util/set.hh (revision 2012) +++ mln/util/set.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 @@ -25,20 +25,22 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_UTIL_LAZY_SET_HH -# define MLN_UTIL_LAZY_SET_HH +#ifndef MLN_UTIL_SET_HH +# define MLN_UTIL_SET_HH -/*! \file mln/util/lazy_set.hh +/*! \file mln/util/set.hh * - * \brief Definition of mln::lazy_set_ for internal use only. + * \brief Definition of mln::util::set. + * + * \todo Clean code and test! */ # include <vector> # include <set> # include <iterator> # include <algorithm> +# include <iostream> -# include <mln/core/internal/force_exact.hh> # include <mln/core/contract.hh> @@ -57,52 +59,72 @@ * * Elements are stored by copy. Implementation is lazy. * - * \invariant \a v_.size() == s_.size() + * The set has two states: frozen or not. There is an automatic + * switch of state when the user modifies its contents (insert, + * remove, or clear) or access to its contents (op[i]). * - * The parameter \c E is the element type, which shall not be + * The parameter \c T is the element type, which shall not be * const-qualified. * * \todo Add a remove method. */ - template <typename E> - class lazy_set_ + template <typename T> + class set { public: - /// Type of the stored value. - typedef E value; + /// Type of elements. + typedef T element; + /*! \brief Insert an element \p elt into the set. * * \param[in] elt The element to be inserted. * + * \pre The set is not frozen. + * * If \p elt is already in the set, this method is a no-op. * * \return The set itself after insertion. */ - lazy_set_<E>& insert(const E& elt); + set<T>& insert(const T& elt); /*! \brief Remove an element \p elt into the set. * * \param[in] elt The element to be inserted. * + * \pre The set is not frozen. + * * If \p elt is already in the set, this method is a no-op. * * \return The set itself after suppression. */ - lazy_set_<E>& remove(const E& elt); + set<T>& remove(const T& elt); - /*! \brief Return the i-th element of the set. + /*! \brief Empty the set. * - * \param[in] i Index of the element to retrieve. + * All elements contained in the set are destroyed so the set is + * emptied. * - * \pre i < nelements() + * \pre The set is not frozen. * - * The element is returned by reference and is constant. + * \post is_empty() == true */ - const E& element(unsigned i) const; + void clear(); + + + /*! \brief Return the number of elements of the set. + */ + unsigned nelements() const; + + + /*! \brief Test if the set is empty. + */ + bool is_empty() const; + + /*! \brief Return the i-th element of the set. * @@ -112,11 +134,7 @@ * * The element is returned by reference and is constant. */ - const E& operator[](unsigned i) const; - - /*! \brief Return the number of elements of the set. - */ - unsigned nelements() const; + const T& operator[](unsigned i) const; /*! \brief Test if the object \p elt belongs to the set. @@ -125,51 +143,23 @@ * * \return True is \p elt is in the set. */ - bool has(const E& elt) const; - - - /*! \brief Test if the set is empty. - */ - bool is_empty() const; - - - /*! \brief Make the set empty. - * - * All elements contained in the set are destroyed so the set is - * emptied. - * The lazy set can be cleared even if it is in const mode - * and then it is set in non-const mode. - * - * \post is_empty() == true - */ - void clear(); + bool has(const T& elt) const; /*! \brief Give access to the set elements. * * The complexity of this method is O(1). * + * \post The set is frozen. + * * \return An array (std::vector) of elements. */ - const std::vector<E>& vect() const; + const std::vector<T>& vect() const; - /// Constructor without arguments. - lazy_set_(); - /*! \brief Set the mode of the lazy_set - * - * The lazy set can have two modes : - * - const : The lazy set is as light as a vector but you cannot - * modify it - * - non-const : The lazy set use a std::set to have lazy manipulation - * - * \param[in] mode True for const mode, false for non-const. - * - */ - void set_const_mode(bool mode); + /// Constructor without arguments. + set(); - /// Get the mode of the lazy set. - bool get_mode() const; private: @@ -178,197 +168,157 @@ * This structure is only updated (if required) when elements * are accessed. */ - mutable std::vector<E> v_; + mutable std::vector<T> v_; /*! \brief Set of elements. * * This structure is always up-to-date w.r.t. the set contents. */ - std::set<E> s_; + mutable std::set<T> s_; - /*! \brief Update \a v_ from \a s_. - * - * Make the vector contains the same element than the sorted set.. + /*! \brief Freeze the contents of the set (update \a v_ from \a + * s_, then clear s_). */ - void update_() const; + void freeze_() const; - /// Tell if \a v_ needs to be updated. - mutable bool needs_update_; + /*! \brief Unfreeze the contents of the set. + */ + void unfreeze_() const; - /// Tell what the lazy set mode is. - bool mode_; + /// Tell if the set is frozen. + mutable bool frozen_; }; # ifndef MLN_INCLUDE_ONLY - template <typename E> + template <typename T> inline - lazy_set_<E>::lazy_set_() + set<T>::set() { - needs_update_ = false; - mode_ = false; + frozen_ = false; } - template <typename E> + template <typename T> inline - lazy_set_<E>& - lazy_set_<E>::insert(const E& elt) + set<T>& + set<T>::insert(const T& elt) { - mln_assertion(!mode_); + if (frozen_) unfreeze_(); s_.insert(elt); - if (needs_update_ == false) - needs_update_ = true; - return mln::internal::force_exact< lazy_set_<E> >(*this); + return *this; } - template <typename E> + template <typename T> inline - lazy_set_<E>& - lazy_set_<E>::remove(const E& elt) + set<T>& + set<T>::remove(const T& elt) { - mln_assertion(!mode_); - // FIXME : doesn't compile - std::remove(s_.begin(), s_.end(), elt); - if (needs_update_ == false) - needs_update_ = true; - return mln::internal::force_exact< lazy_set_<E> >(*this); + if (frozen_) unfreeze_(); + s_.erase(elt); + return *this; } - template <typename E> + template <typename T> inline - const E& - lazy_set_<E>::element(unsigned i) const + void + set<T>::clear() { - assert((!mode_ && i < s_.size()) - || i < v_.size()); - if (!mode_) - if (needs_update_) - update_(); - return v_[i]; + if (frozen_) + { + mln_invariant(s_.empty()); + v_.clear(); + frozen_ = false; } - - template <typename E> - inline - const E& - lazy_set_<E>::operator[](unsigned i) const + else { - return this->element(i); + mln_invariant(v_.empty()); + s_.clear(); + } + mln_postcondition(is_empty()); } - template <typename E> + template <typename T> inline unsigned - lazy_set_<E>::nelements() const + set<T>::nelements() const { - if (!mode_) - return s_.size(); - else - return v_.size(); + return frozen_ ? v_.size() : s_.size(); } - template <typename E> + template <typename T> inline - bool - lazy_set_<E>::has(const E& elt) const + const T& + set<T>::operator[](unsigned i) const { - if (!mode_) - return s_.find(elt) != s_.end(); - else - return v_.find(elt) != v_.end(); + mln_precondition(i < nelements()); + if (! frozen_) freeze_(); + return v_[i]; } - template <typename E> + template <typename T> inline bool - lazy_set_<E>::is_empty() const + set<T>::has(const T& elt) const { - return nelements() == 0; + return frozen_ + ? std::find(v_.begin(), v_.end(), elt) != v_.end() + : s_.find(elt) != s_.end(); } - template <typename E> + template <typename T> inline - void - lazy_set_<E>::clear() + bool + set<T>::is_empty() const { - v_.clear(); - s_.clear(); - needs_update_ = false; - mode_ = false; - mln_postcondition(is_empty()); + return nelements() == 0; } - template <typename E> + template <typename T> inline - const std::vector<E>& - lazy_set_<E>::vect() const + const std::vector<T>& + set<T>::vect() const { - if (!mode_) - if (needs_update_) - update_(); + if (! frozen_) freeze_(); return v_; } - template <typename E> + template <typename T> inline void - lazy_set_<E>::set_const_mode(bool mode) - { - if (mode != mode_) + set<T>::freeze_() const { - if (mode) - { - if (needs_update_) - update_(); + mln_precondition(frozen_ == false); + mln_invariant(v_.empty()); + std::copy(s_.begin(), s_.end(), std::back_inserter(v_)); s_.clear(); - } - else - { - mln_assertion(s_.size() == 0); - for (typename std::vector<E>::iterator it = v_.begin(); - it != v_.end(); it++) - s_.insert(*it); - needs_update_ = false; - } - mode_ = mode; - } + frozen_ = true; } - template <typename E> - inline - bool - lazy_set_<E>::get_mode() const - { - return mode_; - } - - template <typename E> + template <typename T> inline void - lazy_set_<E>::update_() const + set<T>::unfreeze_() const { - mln_precondition(needs_update_ && !mode_); + mln_precondition(frozen_ == true); + mln_invariant(s_.empty()); + s_.insert(v_.begin(), v_.end()); v_.clear(); - std::copy(s_.begin(), s_.end(), std::back_inserter(v_)); - // no s_.clear() here: - // - we want to keep information up-to-date in s_ - // - we want to save some execution time - needs_update_ = false; - } - - // FIXME : ambiguous with site_set operator << - // template <typename E> - // std::ostream& operator<<(std::ostream& ostr, - // const lazy_set_<E>& s) - // { - // ostr << '['; - // const unsigned n = s.nelements(); - // for (unsigned i = 0; i < n; ++i) - // ostr << s.element(i) - // << (i == s.nelements() - 1 ? ']' : ','); - // return ostr; - // } + frozen_ = false; + } + + template <typename T> + std::ostream& operator<<(std::ostream& ostr, + const mln::util::set<T>& s) + { + ostr << '['; + const unsigned n = s.nelements(); + for (unsigned i = 0; i < n; ++i) + ostr << s[i] + << (i == n - 1 ? ']' : ','); + return ostr; + } # endif // ! MLN_INCLUDE_ONLY @@ -377,4 +327,4 @@ } // end of namespace mln -#endif // ! MLN_UTIL_LAZY_SET_HH +#endif // ! MLN_UTIL_SET_HH