URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-11-28 Simon Nivault <simon.nivault@lrde.epita.fr> Add run-based utilities. * mln/core/internal/run_pset.hh: Point set based on many runs. * mln/core/p_array_piter.hh: Add FIXME. * mln/core/p_run.hh: New, Point set based on a run. * mln/core/p_run_piter.hh: New. * mln/util/lazy_set.hh: New, lazy vector of sorted elements. * tests/run_pset.cc: Update. --- mln/core/internal/run_pset.hh | 58 +++++-- mln/core/p_array_piter.hh | 2 mln/core/p_run.hh | 226 +++++++++++++++++++++++++++++ mln/core/p_run_piter.hh | 266 ++++++++++++++++++++++++++++++++++ mln/util/lazy_set.hh | 320 ++++++++++++++++++++++++++++++++++++++++++ tests/run_pset.cc | 7 6 files changed, 858 insertions(+), 21 deletions(-) Index: trunk/milena/tests/run_pset.cc =================================================================== --- trunk/milena/tests/run_pset.cc (revision 1562) +++ trunk/milena/tests/run_pset.cc (revision 1563) @@ -63,17 +63,18 @@ // Pset test internal::run_pset_<point2d> ps; - ps.insert(p, 7); + ps.insert(p_run<point2d>(p, 7)); mln_assertion(ps.npoints() == 7); - ps.insert(q, 42); + ps.insert(p_run<point2d>(q, 42)); mln_assertion(ps.npoints() == 49); mln_assertion(ps.has(site)); mln_assertion(!ps.has(site2)); - ps.insert(r, 14); + ps.insert(p_run<point2d>(r, 14)); mln_assertion(!ps.has(site2)); + ps.insert(p_run<point2d>(make::point2d(17,40), 6)); // parc(ps); } Index: trunk/milena/mln/core/internal/run_pset.hh =================================================================== --- trunk/milena/mln/core/internal/run_pset.hh (revision 1562) +++ trunk/milena/mln/core/internal/run_pset.hh (revision 1563) @@ -37,9 +37,10 @@ # include <mln/core/internal/point_set_base.hh> # include <mln/core/internal/point_iterator_base.hh> # include <mln/core/internal/run_psite.hh> +# include <mln/core/p_run.hh> # include <mln/accu/bbox.hh> +# include <mln/util/lazy_set.hh> -# include <vector> # include <utility> @@ -63,7 +64,7 @@ { public: - typedef std::vector<std::pair<P, unsigned> > std_container; + typedef util::lazy_set_<p_run<P> > container; typedef run_fwd_piter_<P> fwd_piter; typedef run_bkd_piter_<P> bkd_piter; @@ -80,13 +81,13 @@ typename std::size_t npoints() const; /// Insert a range, start at point \p p wit len \p len. - void insert(const P& p, unsigned len); + void insert(const p_run<P>& pr); /// Return the len of the range starting at point \p p. unsigned range_len_(const P& p) const; /// Return the container of the pset (internal use only). - const std_container& con() const; + const container& con() const; protected: @@ -94,7 +95,7 @@ typename std::size_t npoints_; /// Points container - std_container con_; + container con_; /// Exact bounding box. accu::bbox<P> fb_; @@ -112,9 +113,9 @@ bool run_pset_<P>::has(const run_psite<P>& p) const { - for (unsigned i = 0; i < con_.size(); ++i) + for (unsigned i = 0; i < con_.nelements(); ++i) { - if (con_[i].first == p.range_start_() && con_[i].second > p.index_()) + if (con_[i].first() == p.range_start_() && con_[i].length() > p.index_()) return true; } return false; @@ -136,19 +137,42 @@ template <typename P> void - run_pset_<P>::insert(const P& p, unsigned len) + run_pset_<P>::insert(const p_run<P>& pr) { - P run_pend; - typename std_container::value_type elt (p, len); - con_.push_back(elt); + typename std::vector<p_run<P> >::const_iterator iter = con_.vect().begin(); + while (iter != con_.vect().end() && iter->first() < pr.first()) + ++iter; + + if (iter != con_.vect().begin()) + { + typename std::vector<p_run<P> >::const_iterator prec = iter; + --prec; + bool equal = true; + for (int i = P::dim - 2; i >= 0; --i) + if (!(equal = equal && (prec->first()[i] == pr.first()[i]))) + break; + if (equal) + mln_assertion(prec->first()[P::dim - 1] + (signed)prec->length() + < pr.first()[P::dim - 1]); + } + + if (iter != con_.vect().end()) + { + bool equal = true; + for (int i = P::dim - 2; i >= 0; --i) + if (!(equal = equal && ((*iter).first()[i] == pr.first()[i]))) + break; + if (equal) + mln_assertion(pr.first()[P::dim - 1] + (signed)pr.length() + < iter->first()[P::dim - 1]); + } + con_.insert(pr); // update box - fb_.take(p); - run_pend = p; - run_pend[0] += len - 1; - fb_.take(run_pend); + fb_.take(pr.bbox().pmin()); + fb_.take(pr.bbox().pmax()); // update size - npoints_ += len; + npoints_ += pr.npoints(); } template <typename P> @@ -168,7 +192,7 @@ } template <typename P> - const typename run_pset_<P>::std_container& + const typename run_pset_<P>::container& run_pset_<P>::con() const { return con_; Index: trunk/milena/mln/core/p_run.hh =================================================================== --- trunk/milena/mln/core/p_run.hh (revision 0) +++ trunk/milena/mln/core/p_run.hh (revision 1563) @@ -0,0 +1,226 @@ +// 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. + +#ifndef MLN_CORE_P_RUN_HH +# define MLN_CORE_P_RUN_HH + +/*! \file mln/core/p_run.hh + * + * \brief Definition of a point set class based on std::set. + */ + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/internal/set_of.hh> +# include <mln/accu/bbox.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_run_fwd_piter_; + template <typename P> struct p_run_bkd_piter_; + + /*! \brief Point set class in run. + * + * This is a mathematical set of points (not a multi-set). The + * parameter \p P shall be a Point type. + * + * \todo Test if \p P being a Point_Site is ok. + */ + template <typename P> + class p_run : public internal::point_set_base_< P, p_run<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_run_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_run_bkd_piter_<P> bkd_piter; + + /// Constructor without argument. + p_run(); + + /// Constructor. + p_run(const P& start, std::size_t len); + + /// Set the starting point. + void set_run(const P& start, std::size_t len); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Give the number of points. + std::size_t npoints() const; + + /// Give the length of the run. + std::size_t length() const; + + /// Return the \p i-th point. + P operator[](unsigned i) const; + + /// Return the first point. + const P& first() const; + + /// Give the exact bounding box. + const box_<mln_point(P)>& bbox() const; + + /// Set a relation order to p_run. + bool operator<(const p_run<P>& rhs) const; + + protected: + + accu::bbox<P> bb_; + // FIXME: Add invariant bb_.is_valid() <=> npoints() != 0 + + /// The first point of the run. + P p_; + + /// The length of the run. + std::size_t len_; + + /// For internal use. + bool is_valid_; + }; + + template <typename P> + std::ostream& operator<<(std::ostream& out, const p_run<P>& pr) + { + out << "Run: (" << pr.first() << ", " << pr.length() << ")"; + return out; + } + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + p_run<P>::p_run() + { + is_valid_ = false; + } + + template <typename P> + p_run<P>::p_run(const P& start, std::size_t len) + : p_(start), + len_(len) + { + mln_precondition(len != 0); + P p = start; + bb_.init(); + bb_.take(p); + p[P::dim - 1] += len - 1; + bb_.take(p); + is_valid_ = true; + } + + template <typename P> + void + p_run<P>::set_run(const P& start, std::size_t len) + { + mln_precondition(len != 0); + p_ = start; + len_ = len; + P p = start; + bb_.init(); + bb_.take(p); + p[P::dim - 1] += len - 1; + bb_.take(p); + is_valid_ = true; + } + + template <typename P> + bool + p_run<P>::has(const P& p) const + { + mln_precondition(is_valid_); + bool res = true; + for (int i = P::dim - 2; i >= 0; --i) + if (!(res = (res && p[i] == p_[i]))) + return false; + return (p[P::dim - 1] >= p_[P::dim - 1] + && p[P::dim - 1] < p_[P::dim - 1] + (signed)len_); + } + + template <typename P> + std::size_t + p_run<P>::npoints() const + { + mln_precondition(is_valid_); + return len_; + } + + template <typename P> + std::size_t + p_run<P>::length() const + { + mln_precondition(is_valid_); + return len_; + } + + template <typename P> + P + p_run<P>::operator[](unsigned i) const + { + mln_precondition(is_valid_); + mln_precondition(i < npoints()); + P p = p_; + p[P::dim - 1] += i; + return p; + } + + template <typename P> + const P& + p_run<P>::first() const + { + return p_; + } + + template <typename P> + const box_<mln_point(P)>& + p_run<P>::bbox() const + { + mln_precondition(is_valid_); + mln_precondition(npoints() != 0); + return bb_.to_result(); + } + + template <typename P> + bool + p_run<P>::operator<(const p_run<P>& rhs) const + { + return (this->p_ < rhs.p_) + || (this->p_ == rhs.p_ && this->len_ < rhs.len_); + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +# include <mln/core/p_run_piter.hh> + +#endif // ! MLN_CORE_P_RUN_HH Index: trunk/milena/mln/core/p_run_piter.hh =================================================================== --- trunk/milena/mln/core/p_run_piter.hh (revision 0) +++ trunk/milena/mln/core/p_run_piter.hh (revision 1563) @@ -0,0 +1,266 @@ +// 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. + +#ifndef MLN_CORE_P_RUN_PITER_HH +# define MLN_CORE_P_RUN_PITER_HH + +/*! \file mln/core/p_run_piter.hh + * + * \brief Definition of point iterators on mln::p_run. + */ + +# include <mln/core/p_run.hh> + + +namespace mln +{ + + /*! \brief Forward iterator on points of a p_run<P>. + * + */ + template <typename P> + struct p_run_fwd_piter_ : public internal::point_iterator_base_< P, p_run_fwd_piter_<P> > + { + typedef p_run_fwd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; + public: + + // Make definitions from super class available. + enum { dim = super_::dim }; + + /// Coordinate associated type. + p_run_fwd_piter_(const p_run<P>& pr); + + /// Reference of the corresponding point. + const P& to_point() const; + + /// Read-only access to the \p i-th coordinate. + mln_coord(P) 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 point. + operator P() const; + + protected: + const p_run<P>& run_; + bool is_valid_; + P p_; + }; + + + + /*! \brief Backward iterator on points of a p_run<P>. + * + */ + template <typename P> + struct p_run_bkd_piter_ : public internal::point_iterator_base_< P, p_run_bkd_piter_<P> > + { + typedef p_run_bkd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; + public: + + // Make definitions from super class available. + enum { dim = super_::dim }; + + /// Coordinate associated type. + p_run_bkd_piter_(const p_run<P>& pr); + + /// Reference of the corresponding point. + const P& to_point() const; + + /// Read-only access to the \p i-th coordinate. + mln_coord(P) 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 point. + operator P() const; + + protected: + const p_run<P>& run_; + bool is_valid_; + P p_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + // p_run_fwd_piter_<P> + + template <typename P> + p_run_fwd_piter_<P>::p_run_fwd_piter_(const p_run<P>& pr) + : run_(pr) + { + invalidate(); + } + + template <typename P> + const P& + p_run_fwd_piter_<P>::to_point() const + { + mln_precondition(is_valid()); + return p_; + } + + template <typename P> + mln_coord(P) + p_run_fwd_piter_<P>::operator[](unsigned i) const + { + mln_precondition(i < dim); + mln_precondition(is_valid()); + return p_[i]; + } + + template <typename P> + bool + p_run_fwd_piter_<P>::is_valid() const + { + return is_valid_; + } + + template <typename P> + void + p_run_fwd_piter_<P>::invalidate() + { + is_valid_ = false; + } + + template <typename P> + void + p_run_fwd_piter_<P>::start() + { + p_ = run_.first(); + is_valid_ = true; + } + + template <typename P> + void + p_run_fwd_piter_<P>::next_() + { + p_[dim - 1]++; + is_valid_ = p_[dim - 1] - run_.first()[dim - 1] < (signed)run_.length(); + } + + template <typename P> + p_run_fwd_piter_<P>::operator P() const + { + mln_precondition(is_valid()); + return p_; + } + + + // p_run_bkd_piter_<P> + + template <typename P> + p_run_bkd_piter_<P>::p_run_bkd_piter_(const p_run<P>& pr) + : run_(pr) + { + invalidate(); + } + + template <typename P> + const P& + p_run_bkd_piter_<P>::to_point() const + { + mln_precondition(is_valid()); + return p_; + } + + template <typename P> + mln_coord(P) + p_run_bkd_piter_<P>::operator[](unsigned i) const + { + mln_precondition(i < dim); + mln_precondition(is_valid()); + return p_[i]; + } + + template <typename P> + bool + p_run_bkd_piter_<P>::is_valid() const + { + return is_valid; + } + + template <typename P> + void + p_run_bkd_piter_<P>::invalidate() + { + is_valid_ = false; + } + + template <typename P> + void + p_run_bkd_piter_<P>::start() + { + p_ = run_[run_.length() - 1]; + is_valid_ = true; +} + + template <typename P> + void + p_run_bkd_piter_<P>::next_() + { + p_[dim - 1]++; + is_valid_ = p_[dim - 1] - run_.first()[dim - 1] >= 0; + } + + template <typename P> + p_run_bkd_piter_<P>::operator P() const + { + mln_precondition(is_valid()); + return p_; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_RUN_PITER_HH Index: trunk/milena/mln/core/p_array_piter.hh =================================================================== --- trunk/milena/mln/core/p_array_piter.hh (revision 1562) +++ trunk/milena/mln/core/p_array_piter.hh (revision 1563) @@ -79,7 +79,7 @@ protected: const std::vector<P>& vect_; - unsigned i_; + unsigned i_; // FIXME: Why it's unsigned in fwd iterator and signed in the bkd one ? P p_; }; Index: trunk/milena/mln/util/lazy_set.hh =================================================================== --- trunk/milena/mln/util/lazy_set.hh (revision 0) +++ trunk/milena/mln/util/lazy_set.hh (revision 1563) @@ -0,0 +1,320 @@ +// 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. + +#ifndef MLN_UTIL_LAZY_SET_HH +# define MLN_UTIL_LAZY_SET_HH + +/*! \file mln/core/internal/lazy_set.hh + * + * \brief Definition of mln::lazy_set_ for internal use only. + */ + +# include <vector> +# include <set> +# include <iterator> +# include <algorithm> + +# include <mln/core/internal/force_exact.hh> + + +namespace mln +{ + + namespace util + { + + /*! \brief An "efficient" mathematical set class. + * + * \internal + * + * This set class is designed to store a mathematical set and to + * present it to the user as a linear array (std::vector). + * + * Elements are stored by copy. Implementation is lazy. + * + * \invariant \a v_.size() == s_.size() + * + * The parameter \c E is the element type, which shall not be + * const-qualified. + * + * \todo Add a remove method. + */ + template <typename E> + class lazy_set_ + { + public: + + /// Type of the stored value. + typedef E value; + + /*! \brief Insert an element \p elt into the set. + * + * \param[in] elt The element to be inserted. + * + * 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); + + + /*! \brief Remove an element \p elt into the set. + * + * \param[in] elt The element to be inserted. + * + * 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); + + + /*! \brief Return the i-th element of the set. + * + * \param[in] i Index of the element to retrieve. + * + * \pre i < nelements() + * + * The element is returned by reference and is constant. + */ + const E& element(unsigned i) const; + + /*! \brief Return the i-th element of the set. + * + * \param[in] i Index of the element to retrieve. + * + * \pre i < nelements() + * + * 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; + + + /*! \brief Test if the object \p elt belongs to the set. + * + * \param[in] elt A possible element of the set. + * + * \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. + * + * \post is_empty() == true + */ + void clear(); + + + /*! \brief Give access to the set elements. + * + * The complexity of this method is O(1). + * + * \return An array (std::vector) of elements. + */ + const std::vector<E>& vect() const; + + /// Constructor without arguments. + lazy_set_(); + + private: + + /*! \brief Array of elements. + * + * This structure is only updated (if required) when elements + * are accessed. + */ + mutable std::vector<E> v_; + + /*! \brief Set of elements. + * + * This structure is always up-to-date w.r.t. the set contents. + */ + std::set<E> s_; + + + /*! \brief Update \a v_ from \a s_. + * + * FIXME: explain. + */ + void update_() const; + + /// Tell if \a v_ needs to be updated. + mutable bool needs_update_; + }; + + + /*! \brief Print a set \p s into the output stream \p + * ostr. + * + * \param[in,out] ostr An output stream. + * \param[in] s A set. + * + * \return The modified output stream \p ostr. + * + * \relates mln::internal::lazy_set_ + */ + // FIXME : ambiguous with point_set operator << + // template <typename E> + // std::ostream& operator<<(std::ostream& ostr, const lazy_set_<E>& s); + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + lazy_set_<E>::lazy_set_() + { + needs_update_ = false; + } + + template <typename E> + lazy_set_<E>& + lazy_set_<E>::insert(const E& elt) + { + s_.insert(elt); + if (needs_update_ == false) + needs_update_ = true; + return internal::force_exact< lazy_set_<E> >(*this); + } + + template <typename E> + lazy_set_<E>& + lazy_set_<E>::remove(const E& elt) + { + // FIXME : doesn't compile + std::remove(s_.begin(), s_.end(), elt); + if (needs_update_ == false) + needs_update_ = true; + return internal::force_exact< lazy_set_<E> >(*this); + } + + template <typename E> + const E& + lazy_set_<E>::element(unsigned i) const + { + assert(i < v_.size()); + if (needs_update_) + update_(); + return v_[i]; + } + + template <typename E> + const E& + lazy_set_<E>::operator[](unsigned i) const + { + return this->element(i); + } + + template <typename E> + unsigned + lazy_set_<E>::nelements() const + { + if (needs_update_) + update_(); + return v_.size(); + } + + template <typename E> + bool + lazy_set_<E>::has(const E& elt) const + { + return s_.find(elt) != s_.end(); + } + + template <typename E> + bool + lazy_set_<E>::is_empty() const + { + return nelements() == 0; + } + + template <typename E> + void + lazy_set_<E>::clear() + { + v_.clear(); + s_.clear(); + needs_update_ = false; + mln_postcondition(is_empty()); + } + + template <typename E> + const std::vector<E>& + lazy_set_<E>::vect() const + { + if (needs_update_) + update_(); + return v_; + } + + template <typename E> + void + lazy_set_<E>::update_() const + { + mln_precondition(needs_update_); + 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 point_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; + // } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util + +} // end of namespace mln + + +#endif // ! MLN_UTIL_LAZY_SET_HH