[Olena-patches] milena r1836: A fast point2d set : p_image2d

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-03 Matthieu Garrigues &lt;garrigues(a)lrde.epita.fr&gt; A fast point2d set : p_image2d. * mln/core/p_image2d.hh: The new set. * mln/core/p_image2d_piter.hh: To iter on it. * tests/core/p_image2d.cc: some small tests. --- mln/core/p_image2d.hh | 209 +++++++++++++++++++++++++++++ mln/core/p_image2d_piter.hh | 316 ++++++++++++++++++++++++++++++++++++++++++++ tests/core/p_image2d.cc | 56 +++++++ 3 files changed, 581 insertions(+) Index: trunk/milena/tests/core/p_image2d.cc =================================================================== --- trunk/milena/tests/core/p_image2d.cc (revision 0) +++ trunk/milena/tests/core/p_image2d.cc (revision 1836) @@ -0,0 +1,56 @@ +// Copyright (C) 2007 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/core/p_image2d.cc + * + * \brief Tests on mln::p_image2d. + */ + +#include <mln/core/p_image2d.hh> + +int main() +{ + using namespace mln; + + p_image2d<point2d> ps(20,20); + ps + .insert(make::point2d(6, 9)) + .insert(make::point2d(4, 2)) + .insert(make::point2d(4, 2)) + .insert(make::point2d(5, 1)); + mln_assertion(ps.npoints() == 3); + + ps.remove(make::point2d(5, 1)); + ps.remove(make::point2d(5, 1)); + + ps.remove(make::point2d(6, 9)); + ps.remove(make::point2d(4, 2)); + + mln_assertion(ps.npoints() == 0); + mln_assertion(ps.is_empty()); + +} Index: trunk/milena/mln/core/p_image2d.hh =================================================================== --- trunk/milena/mln/core/p_image2d.hh (revision 0) +++ trunk/milena/mln/core/p_image2d.hh (revision 1836) @@ -0,0 +1,209 @@ +// 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 +// 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_P_SET_HH +# define MLN_CORE_P_SET_HH + + +/*! \file mln/core/p_set.hh + * + * \brief Definition of a point set class based on std::set. + */ + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/box2d.hh> +# include <mln/core/image2d.hh> +# include <mln/accu/bbox.hh> +# include <mln/level/fill.hh> +# include <mln/core/p_array.hh> + + +namespace mln +{ + + + // Fwd decls. + template <typename P> struct p_image2d_fwd_piter_; + template <typename P> struct p_image2d_bkd_piter_; + + template <typename P> + class p_image2d : public internal::point_set_base_<P, p_image2d<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_image2d_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_image2d_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_image2d(int nrows, int ncols); + p_image2d(const box2d& b); + + /// Insert a point \p p. + p_image2d<P>& insert(const P p); + p_image2d<P>& insert(const p_image2d& set); + + /// Remove a point \p p. + p_image2d<P>& remove(const P p); + p_image2d<P>& remove(const p_image2d& set); + + /// Give the number of points. + unsigned npoints() const; + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if the set is empty. + bool is_empty() const; + + /// Clear this set. + void clear(); + + /// Hook to the image2d + const image2d<bool>& image() const; + private: + image2d<bool> points_; + unsigned npoints_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + p_image2d<P>::p_image2d(int nrows, int ncols) + : points_(nrows, ncols), + npoints_(0) + { + + level::fill(points_, false); + } + + template <typename P> + p_image2d<P>::p_image2d(const box2d& b) + : points_(b), + npoints_(0) + { + level::fill(points_, false); + } + + + template <typename P> + p_image2d<P>& + p_image2d<P>::insert(const P p) + { + if (points_(p) == false) + { + points_(p) = true; + npoints_++; + } + return *this; + } + + template <typename P> + p_image2d<P>& + p_image2d<P>::insert(const p_image2d& set) + { + if (set->is_empty()) + return *this; + mln_fwd_piter(image2d<bool>) p(set.points_ | true); + for_all(p) + if (this->points_.has(p)) + this->insert(p); + return *this; + } + + template <typename P> + p_image2d<P>& + p_image2d<P>::remove(const P p) + { + if (points_(p) == true) + { + points_(p) = false; + npoints_--; + } + return *this; + } + + template <typename P> + p_image2d<P>& + p_image2d<P>::remove(const p_image2d& set) + { + if (this->is_empty() || set->is_empty()) + return *this; + mln_fwd_piter(image2d<bool>) p(set.points_ | true); + for_all(p) + if (this->points_.has(p)) + this->remove(p); + return *this; + } + + template <typename P> + unsigned + p_image2d<P>::npoints() const + { + return npoints_; + } + + template <typename P> + bool + p_image2d<P>::has(const P& p) const + { + return points_(p); + } + + template <typename P> + bool + p_image2d<P>::is_empty() const + { + return npoints_ == 0; + } + + template <typename P> + void + p_image2d<P>::clear() + { + level::fill(points_, false); + } + + template <typename P> + const image2d<bool>& + p_image2d<P>::image() const + { + return points_; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/p_image2d_piter.hh> + + +#endif // ! MLN_CORE_P_SET_HH Index: trunk/milena/mln/core/p_image2d_piter.hh =================================================================== --- trunk/milena/mln/core/p_image2d_piter.hh (revision 0) +++ trunk/milena/mln/core/p_image2d_piter.hh (revision 1836) @@ -0,0 +1,316 @@ +// 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. + +#ifndef MLN_CORE_P_IMAGE2D_PITER_HH +# define MLN_CORE_P_IMAGE2D_PITER_HH + +/// \file mln/core/p_image2d_piter.hh +/// \brief Definition of point iterators on mln::p_array. + +# include <mln/core/p_image2d.hh> +# include <mln/core/box_piter.hh> + + +namespace mln +{ + + /// \brief Forward iterator on points of a p_array<P>. + template <typename P> + struct p_image2d_fwd_piter_ + : public internal::point_iterator_base_< P, p_image2d_fwd_piter_<P> > + { + typedef p_image2d_fwd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; + public: + /// The associated psite type. + typedef P psite; + + /// The associated point type. + typedef mln_point(P) point; + + enum { dim = super_::dim }; + + /// Coordinate associated type. + template <typename S> + p_image2d_fwd_piter_(const p_image2d<S>& s); + + /// Reference of the corresponding psite. + const psite& to_psite() const; + + /// Reference of the corresponding point. + const point& to_point() const; + + /// Read-only access to the \p i-th coordinate. + mln_coord(point) operator[](unsigned i) const; + + /// Test if the iterator is valid. + bool is_valid() const; + + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + + /// Convert the iterator into a psite. + operator psite() const; + + protected: + box_fwd_piter_<P> piter_; + const image2d<bool> ima_; + }; + + + + /// \brief Backward iterator on points of a p_array<P>. + template <typename P> + struct p_image2d_bkd_piter_ + : public internal::point_iterator_base_< P, p_image2d_bkd_piter_<P> > + { + typedef p_image2d_bkd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; + public: + /// The associated psite type. + typedef P psite; + + /// The associated point type. + typedef mln_point(P) point; + + enum { dim = super_::dim }; + + /// Coordinate associated type. + template <typename S> + p_image2d_bkd_piter_(const p_image2d<S>& s); + + /// Reference of the corresponding psite. + const psite& to_psite() const; + + /// Reference of the corresponding point. + const point& to_point() const; + + /// Read-only access to the \p i-th coordinate. + mln_coord(point) operator[](unsigned i) const; + + /// Test if the iterator is valid. + bool is_valid() const; + + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + + /// Convert the iterator into a psite. + operator psite() const; + + protected: + box_bkd_piter_<P> piter_; + image2d<bool> ima_; + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + /*------------------------. + | p_image2d_fwd_piter_<P>. | + `------------------------*/ + + template <typename P> + template <typename S> + inline + p_image2d_fwd_piter_<P>::p_image2d_fwd_piter_(const p_image2d<S>& s) + : piter_(exact(s).image().domain()), + ima_(exact(s).image()) + { + invalidate(); + } + + template <typename P> + inline + const P& + p_image2d_fwd_piter_<P>::to_psite() const + { + return piter_.to_psite(); + } + + template <typename P> + inline + const mln_point(P)& + p_image2d_fwd_piter_<P>::to_point() const + { + return piter_.to_point(); + } + + template <typename P> + inline + mln_coord(mln_point_(P)) + p_image2d_fwd_piter_<P>::operator[](unsigned i) const + { + return piter_[i]; + } + + template <typename P> + inline + bool + p_image2d_fwd_piter_<P>::is_valid() const + { + return piter_.is_valid(); + } + + template <typename P> + inline + void + p_image2d_fwd_piter_<P>::invalidate() + { + return piter_.invalidate(); + } + + template <typename P> + inline + void + p_image2d_fwd_piter_<P>::start() + { + piter_.start(); + while(is_valid() && !ima_(piter_)) + piter_.next(); + } + + template <typename P> + inline + void + p_image2d_fwd_piter_<P>::next_() + { + piter_.next(); + while(is_valid() && !ima_(piter_)) + piter_.next(); + } + + template <typename P> + inline + p_image2d_fwd_piter_<P>::operator P() const + { + return P(piter_); + } + + + /*------------------------. + | p_image2d_bkd_piter_<P>. | + `------------------------*/ + + template <typename P> + template <typename S> + inline + p_image2d_bkd_piter_<P>::p_image2d_bkd_piter_(const p_image2d<S>& s) + : piter_(exact(s).image().domain()), + ima_(exact(s).image()) + { + invalidate(); + } + + template <typename P> + inline + const P& + p_image2d_bkd_piter_<P>::to_psite() const + { + return piter_.to_psite(); + } + + template <typename P> + inline + const mln_point(P)& + p_image2d_bkd_piter_<P>::to_point() const + { + return piter_.to_point(); + } + + template <typename P> + inline + mln_coord(mln_point_(P)) + p_image2d_bkd_piter_<P>::operator[](unsigned i) const + { + mln_precondition(is_valid()); + return piter_[i]; + } + + template <typename P> + inline + bool + p_image2d_bkd_piter_<P>::is_valid() const + { + return piter_.is_valid(); + } + + template <typename P> + inline + void + p_image2d_bkd_piter_<P>::invalidate() + { + return piter_.invalidate(); + } + + template <typename P> + inline + void + p_image2d_bkd_piter_<P>::start() + { + piter_.start(); + while(is_valid() && !ima_(piter_)) + piter_.next(); + } + + template <typename P> + inline + void + p_image2d_bkd_piter_<P>::next_() + { + piter_.next(); + while(is_valid() && !ima_(piter_)) + piter_.next(); + } + + template <typename P> + inline + p_image2d_bkd_piter_<P>::operator P() const + { + mln_precondition(is_valid()); + return P(piter_); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_IMAGE2D_PITER_HH