[Olena-patches] milena r1788: Commit of Sandbox

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-03-19 Michel Pellegrin <pellegrin@lrde.epita.fr> Commit of Sandbox. * mln/core/internal/point_set_base.hh: Header. * mln/core/line2d.hh: No append in line2d. * mln/core/p_graph.hh: Typos. * mln/util/lazy_set.hh: Disambiguization. * sandbox/pellegrin/cond_inheritance/Makefile: . * sandbox/pellegrin/cond_inheritance/concept/point_set.hh: . * sandbox/pellegrin/cond_inheritance/internal/multi_set.hh: . * sandbox/pellegrin/cond_inheritance/internal/point_set_base.hh: . * sandbox/pellegrin/cond_inheritance/internal/uni_set.hh: . * sandbox/pellegrin/cond_inheritance/p_array.hh: . * sandbox/pellegrin/cond_inheritance/p_set.hh: . * sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc: . * sandbox/pellegrin/first_test.cc: . * sandbox/pellegrin/set/Makefile: . * sandbox/pellegrin/set/core/concept/point_set.hh: New. * sandbox/pellegrin/set/core/concept: New. * sandbox/pellegrin/set/core/internal: New. * sandbox/pellegrin/set/core/line2d.hh: New. * sandbox/pellegrin/set/core/p_array.hh: New. * sandbox/pellegrin/set/core/p_bgraph.hh: New. * sandbox/pellegrin/set/core/p_graph.hh: New. * sandbox/pellegrin/set/core/p_line_graph.hh: New. * sandbox/pellegrin/set/core/p_priority_queue.hh: New. * sandbox/pellegrin/set/core/p_priority_queue_fast.hh: New. * sandbox/pellegrin/set/core/p_priority_queue_fast_with_array.hh: New. * sandbox/pellegrin/set/core/p_queue.hh: New. * sandbox/pellegrin/set/core/p_queue_fast.hh: New. * sandbox/pellegrin/set/core/p_set.hh: New. * sandbox/pellegrin/set/core/pset_if.hh: New. * sandbox/pellegrin/set/core/runs_psite.hh: New. * sandbox/pellegrin/set/core: New. * sandbox/pellegrin/set/multi_set.hh: . * sandbox/pellegrin/set/test_set.cc: . * sandbox/pellegrin/set/trait/point_set.hh: New. * sandbox/pellegrin/set/trait: New. * sandbox/pellegrin/set/types_de_points.txt: New. * sandbox/pellegrin/set/uni_set.hh: . --- mln/core/internal/point_set_base.hh | 1 mln/core/line2d.hh | 3 mln/core/p_graph.hh | 4 mln/util/lazy_set.hh | 4 sandbox/pellegrin/cond_inheritance/Makefile | 24 sandbox/pellegrin/cond_inheritance/concept/point_set.hh | 2 sandbox/pellegrin/cond_inheritance/internal/multi_set.hh | 2 sandbox/pellegrin/cond_inheritance/internal/point_set_base.hh | 2 sandbox/pellegrin/cond_inheritance/internal/uni_set.hh | 2 sandbox/pellegrin/cond_inheritance/p_array.hh | 5 sandbox/pellegrin/cond_inheritance/p_set.hh | 5 sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc | 4 sandbox/pellegrin/first_test.cc | 2 sandbox/pellegrin/set/Makefile | 26 sandbox/pellegrin/set/core/concept/point_set.hh | 252 ++++++ sandbox/pellegrin/set/core/line2d.hh | 208 +++++ sandbox/pellegrin/set/core/p_array.hh | 245 ++++++ sandbox/pellegrin/set/core/p_bgraph.hh | 232 ++++++ sandbox/pellegrin/set/core/p_graph.hh | 258 +++++++ sandbox/pellegrin/set/core/p_line_graph.hh | 176 ++++ sandbox/pellegrin/set/core/p_priority_queue.hh | 361 ++++++++++ sandbox/pellegrin/set/core/p_priority_queue_fast.hh | 361 ++++++++++ sandbox/pellegrin/set/core/p_priority_queue_fast_with_array.hh | 347 +++++++++ sandbox/pellegrin/set/core/p_queue.hh | 309 ++++++++ sandbox/pellegrin/set/core/p_queue_fast.hh | 316 ++++++++ sandbox/pellegrin/set/core/p_set.hh | 191 +++++ sandbox/pellegrin/set/core/pset_if.hh | 226 ++++++ sandbox/pellegrin/set/core/runs_psite.hh | 192 +++++ sandbox/pellegrin/set/multi_set.hh | 8 sandbox/pellegrin/set/test_set.cc | 4 sandbox/pellegrin/set/trait/point_set.hh | 110 +++ sandbox/pellegrin/set/types_de_points.txt | 14 sandbox/pellegrin/set/uni_set.hh | 8 33 files changed, 3824 insertions(+), 80 deletions(-) Index: trunk/milena/mln/core/internal/point_set_base.hh =================================================================== --- trunk/milena/mln/core/internal/point_set_base.hh (revision 1787) +++ trunk/milena/mln/core/internal/point_set_base.hh (revision 1788) @@ -45,7 +45,6 @@ /*! \internal A base class for point set classes. * \p P is a point site type. - * */ template <typename P, typename E> struct point_set_base_ : public Point_Set<E> Index: trunk/milena/mln/core/p_graph.hh =================================================================== --- trunk/milena/mln/core/p_graph.hh (revision 1787) +++ trunk/milena/mln/core/p_graph.hh (revision 1788) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_CORE_GRAPH_P_HH -# define MLN_CORE_GRAPH_P_HH +#ifndef MLN_CORE_P_GRAPH_HH +# define MLN_CORE_P_GRAPH_HH # include <mln/core/concept/point_site.hh> # include <mln/core/internal/point_set_base.hh> Index: trunk/milena/mln/core/line2d.hh =================================================================== --- trunk/milena/mln/core/line2d.hh (revision 1787) +++ trunk/milena/mln/core/line2d.hh (revision 1788) @@ -71,9 +71,6 @@ /// Give the exact bounding box. const box_<point2d>& bbox() const; - /// Append a point \p p. - line2d& append(const point2d& p); - /// Return the corresponding std::vector of points. const std::vector<point2d>& vect() const; Index: trunk/milena/mln/util/lazy_set.hh =================================================================== --- trunk/milena/mln/util/lazy_set.hh (revision 1787) +++ trunk/milena/mln/util/lazy_set.hh (revision 1788) @@ -220,7 +220,7 @@ s_.insert(elt); if (needs_update_ == false) needs_update_ = true; - return internal::force_exact< lazy_set_<E> >(*this); + return mln::internal::force_exact< lazy_set_<E> >(*this); } template <typename E> @@ -233,7 +233,7 @@ std::remove(s_.begin(), s_.end(), elt); if (needs_update_ == false) needs_update_ = true; - return internal::force_exact< lazy_set_<E> >(*this); + return mln::internal::force_exact< lazy_set_<E> >(*this); } template <typename E> Index: trunk/milena/sandbox/pellegrin/first_test.cc =================================================================== --- trunk/milena/sandbox/pellegrin/first_test.cc (revision 1787) +++ trunk/milena/sandbox/pellegrin/first_test.cc (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 Index: trunk/milena/sandbox/pellegrin/set/multi_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/multi_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/set/multi_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -26,8 +26,8 @@ // Public License. -#ifndef __MULTI_SET_HH__ -# define __MULTI_SET_HH__ +#ifndef MULTI_SET_HH +# define MULTI_SET_HH /*! \file sandbox/pellegrin/set/multi_set.hh * @@ -173,4 +173,4 @@ } // end of namespace mln -#endif // ! __MULTI_SET_HH__ +#endif // ! MULTI_SET_HH Index: trunk/milena/sandbox/pellegrin/set/trait/point_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/trait/point_set.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/trait/point_set.hh (revision 1788) @@ -0,0 +1,110 @@ +// 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_POINT_SET_HH +# define MLN_TRAIT_POINT_SET_HH + +/*! \file mln/trait/point_set.hh + * + * \brief Properties of point_set classes. + */ + +# include <string> +# include <mln/trait/undef.hh> + +# define mln_trait_point_set_arity(P) typename mln::trait::point_set< P >::arity +# define mln_trait_point_set_has_speed(P) typename mln::trait::point_set< P >::has_speed + +namespace mln +{ + + struct line2d; + template <typename P> struct p_array; + template <typename P> struct p_bgraph; + template <typename P> struct p_graph; + template <typename P> struct p_line_graph; + template <typename P, typename T> struct p_priority_queue; + template <typename P, typename T> struct p_priority_queue_fast; + template <typename P, typename T, typename S> struct p_priority_queue_fast_with_array; + template <typename P> struct p_queue; + template <typename P> struct p_queue_fast; + template <typename P> struct p_run; + template <typename P> struct p_runs_; + template <typename P> struct p_set; + template <typename S, typename F> struct pset_if; + + namespace trait + { + + namespace point_set + { + + struct arity + { + struct any {}; + struct unique : any + { std::string name() const { return "arity::unique"; } }; + struct multiple : any + { std::string name() const { return "arity::multiple"; } }; + }; + + struct has_speed + { + struct any {}; + struct slow : any + { std::string name() const { return "has_speed::slow"; } }; + struct fast : any + { std::string name() const { return "has_speed::fast"; } }; + }; + + } // end of namespace mln::trait::point_set + + template <typename P> + struct undefined_point_set_ + { + typedef undef arity; // unique or multiple + typedef undef has_speed; // slow or fast + }; + + template <typename P> + struct point_set_ : public undefined_point_set_<P> + { + }; + + template <typename P> + struct default_point_set_ : public undefined_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + }; + + } // end of namespace mln::trait + +} // end of namespace mln + + +#endif // ! MLN_TRAIT_POINT_SET_HH Index: trunk/milena/sandbox/pellegrin/set/uni_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/uni_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/set/uni_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -26,8 +26,8 @@ // Public License. -#ifndef __UNI_SET_HH__ -# define __UNI_SET_HH__ +#ifndef UNI_SET_HH +# define UNI_SET_HH /*! \file sandbox/pellegrin/set/uni_set.hh * @@ -173,4 +173,4 @@ } // end of namespace mln -#endif // ! __UNI_SET_HH__ +#endif // ! UNI_SET_HH Index: trunk/milena/sandbox/pellegrin/set/types_de_points.txt =================================================================== --- trunk/milena/sandbox/pellegrin/set/types_de_points.txt (revision 0) +++ trunk/milena/sandbox/pellegrin/set/types_de_points.txt (revision 1788) @@ -0,0 +1,14 @@ +mln::line2d: uni, fast +mln::p_array< P >: multi, fast +mln::p_bgraph< P >: uni, fast +mln::p_graph< P >: uni, fast +mln::p_line_graph< P >: uni, fast +mln::p_priority_queue< P, T >: uni, slow +mln::p_priority_queue_fast< P, T >: uni, fast +mln::p_priority_queue_fast_with_array< P, T, S >: multi, fast +mln::p_queue< P >: multi, slow +mln::p_queue_fast< P >: multi, fast +mln::p_run< P >: uni, fast +mln::p_runs_< P >: multi, fast +mln::p_set< P >: uni, fast +mln::pset_if< S, F >: uni, slow Index: trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast.hh (revision 1788) @@ -0,0 +1,361 @@ +// 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_PRIORITY_QUEUE_FAST_HH +# define MLN_CORE_P_PRIORITY_QUEUE_FAST_HH + +/*! \file mln/core/p_priority_queue_fast.hh + * + * \brief Definition of a point set class based on p_queue_fast with + * priority features. + */ + +# include <vector> +# include <deque> +# include <map> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/accu/bbox.hh> +# include <mln/core/p_queue_fast.hh> + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point fast queue class (based on std::map and p_queue_fast). + * + * This is a mathematical set of points (unique insertion). + * + * \todo Make it work with P being a Point_Site. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints() when this container is multiple. + */ + template <typename P, typename T> + class p_priority_queue_fast : public internal::point_set_base_< P, p_priority_queue_fast<P, T> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_priority_queue_fast(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if queue is empty or not. + bool is_empty() const; + + /// Give the number of points. + size_t npoints() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + /// Push force a point \p p in the queue. + p_priority_queue_fast<P, T>& push_force(const P& p, T prio = 0); + + /// Push a point \p p in the queue. + p_priority_queue_fast<P, T>& push(const P& p, T prio = 0); + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point. + void pop(); + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point. + const P& front() const; + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point and give the front point \p p of + /// the queue; \p p is the least recently inserted point. + const P& pop_front(); + + /// Clear the queue. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + protected: + + std::map<const T, p_queue_fast<P> > q_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_() const; + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_() const; + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T> + inline + p_priority_queue_fast<P, T>::p_priority_queue_fast() + { + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T> + inline + void + p_priority_queue_fast<P, T>::vect_update_() const + { + vect_.clear(); + vect_.reserve(npoints()); + + typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + std::copy((*it).second.vect().begin(), (*it).second.vect().end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P, typename T> + inline + void + p_priority_queue_fast<P, T>::bb_update_() const + { + bb_.init(); + + typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + for (unsigned i = 0; i < (*it).second.npoints (); ++i) + bb_.take((*it).second[i]); + bb_needs_update_ = false; + } + + + template <typename P, typename T> + inline + bool + p_priority_queue_fast<P, T>::has(const P& p) const + { + typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if ((*it).second.has (p)) + return true; + return false; + } + + template <typename P, typename T> + inline + bool + p_priority_queue_fast<P, T>::is_empty() const + { + typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!(*it).second.is_empty ()) + return false; + return true; + } + + template <typename P, typename T> + inline + size_t + p_priority_queue_fast<P, T>::npoints() const + { + unsigned res = 0; + + typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!(*it).second.is_empty ()) + res += (*it).second.npoints(); + return res; + } + + template <typename P, typename T> + inline + const box_<P>& + p_priority_queue_fast<P, T>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P, typename T> + inline + p_priority_queue_fast<P, T>& + p_priority_queue_fast<P, T>::push_force(const P& p, T prio) + { + q_[prio].push_force (p); + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + return *this; + } + + template <typename P, typename T> + inline + p_priority_queue_fast<P, T>& + p_priority_queue_fast<P, T>::push(const P& p, T prio) + { + if (! has(p)) + return this->push_force(p, prio); + else + return *this; + } + + template <typename P, typename T> + inline + void + p_priority_queue_fast<P, T>::pop() + { + typename std::map<T, p_queue_fast<P> >::reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!(*it).second.is_empty ()) + return (*it).second.pop (); + + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + } + + template <typename P, typename T> + inline + const P& + p_priority_queue_fast<P, T>::front() const + { + mln_precondition(! q_.empty()); + + typename std::map<T, p_queue_fast<P> >::const_reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!(*it).second.is_empty ()) + break; + return (*it).second.front (); + } + + template <typename P, typename T> + inline + const P& + p_priority_queue_fast<P, T>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P, typename T> + inline + void + p_priority_queue_fast<P, T>::clear() + { + typename std::map<T, p_queue_fast<P> >::iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + (*it).second.clear (); + q_.clear(); + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T> + inline + const std::vector<P>& + p_priority_queue_fast<P, T>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P, typename T> + inline + const P& + p_priority_queue_fast<P, T>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + + typename std::map<T, p_queue_fast<P> >::const_reverse_iterator it = q_.rbegin (); + unsigned cpt = 0; + + for (; it != q_.rend (); ++it) + { + if (!(*it).second.is_empty ()) + for (cpt = 0; cpt < (*it).second.npoints (); ++cpt) + { + if (i == 0) + return (*it).second[cpt]; + --i; + } + } + return (*it).second[cpt]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_PRIORITY_QUEUE_FAST_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_bgraph.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_bgraph.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_bgraph.hh (revision 1788) @@ -0,0 +1,232 @@ +// 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. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CORE_BGRAPH_P_HH +# define MLN_CORE_BGRAPH_P_HH + +# include <utility> + +# include <mln/core/concept/point_site.hh> +# include <mln/core/internal/point_set_base.hh> +# include <mln/accu/bbox.hh> +# include <mln/util/internal/boost_graph.hh> +# include <mln/core/bgraph_psite.hh> +# include <mln/core/p_bgraph_piter.hh> + + + +/// \file mln/core/p_bgraph.hh +/// \brief Definition of a point set based on a boost graph. + +namespace mln +{ + + template<typename P> class p_bgraph_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + template<typename P> + struct p_bgraph + : public internal::point_set_base_< graph_psite<P>, p_bgraph<P> > + { + typedef util::internal::boost_graph<P, util::empty> graph; + + /// Point_Site associated type. + typedef bgraph_psite<P> psite; + + /// Forward Point_Iterator associated type. + typedef p_bgraph_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_bgraph_piter_<P> bkd_piter; + + /// Graph vertex/edge identifier + typedef typename graph::vertex_descriptor node_id; + typedef typename graph::edge_descriptor edge_id; + + /// Graph vertex/edge iterator + typedef typename graph::vertex_iterator node_iterator; + typedef typename graph::edge_iterator edge_iterator; + typedef std::pair<node_iterator, node_iterator> node_iterators; + + + /// Construct a graph psite set from a graph of points. + /// \p gr is a pointer on a boost graph. + /// This boost graph must have been allocated dynamically. + p_bgraph (graph* gr); + + /// Return The number of points (i.e., nodes) in the graph. + std::size_t npoints() const; + + /// Return The number of lines (i.e., edges) in the graph. + std::size_t nlines() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + bool has(const psite& p) const; + + /// Return the graph point (FIXME site?) from an index + const P& point_from_id(const node_id& id) const; + P& point_from_id(const node_id& id); + + /// Return the point contained in the first node adjacent + // to the edge id \a e. + const P& node1(const edge_id& e) const; + /// Return the point contained in the second node adjacent + /// to the edge id \a e. + const P& node2(const edge_id& e) const; + + /// Return the graph associated to the p_bgraph domain: + const graph& to_graph() const; + graph& to_graph(); + + + private: + graph* gr_; + box_<P> bb_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template<typename P> + inline + p_bgraph<P>::p_bgraph (typename p_bgraph<P>::graph* gr) + : gr_ (gr) + { + mln_precondition(gr != 0); + // FIXME: Warning: if the underlying graph is updated later, this + // won't be taken into account by this p_bgraph! + accu::bbox<P> a; + + for (node_iterators iter = boost::vertices(*gr_); + iter.first != iter.second; + ++iter.first) + a.take((*gr_)[*iter.first]); + bb_ = a.to_result(); + } + + template<typename P> + inline + std::size_t + p_bgraph<P>::npoints() const + { + return boost::num_vertices(*gr_); + } + + template<typename P> + inline + std::size_t + p_bgraph<P>::nlines() const + { + return boost::num_edges(gr_->nedges()); + } + + template<typename P> + inline + const box_<P>& + p_bgraph<P>::bbox() const + { + return bb_; + } + + template<typename P> + inline + bool + p_bgraph<P>::has(const psite& p) const + { + return + // Check whether P is compatible with this psite set. + (&p.pg() == this) && + // Check that the node id of P belongs to the range of valid node ids. + (p.id() < this->npoints()); + } + + + template <typename P> + const P& + p_bgraph<P>::point_from_id(const typename p_bgraph<P>::node_id& id) const + { + return this->gr_->operator[](id); + } + + template <typename P> + P& + p_bgraph<P>::point_from_id(const typename p_bgraph<P>::node_id& id) + { + return this->gr_->operator[](id); + } + + + /// FIXME: Compare to p_bgraph, here we are loosing the vertex ordering + /// information. Is it bad?? + template <typename P> + const P& + p_bgraph<P>::node1(const typename p_bgraph<P>::edge_id& e) const + { + return this->point_from_id(source(e, *this->gr_)); + } + + /// FIXME: same as node1... + template <typename P> + const P& + p_bgraph<P>::node2(const typename p_bgraph<P>::edge_id& e) const + { + return this->point_from_id(target(e, *this->gr_)); + } + + template <typename P> + const typename p_bgraph<P>::graph& + p_bgraph<P>::to_graph() const + { + return *this->gr_; + } + + template <typename P> + typename p_bgraph<P>::graph& + p_bgraph<P>::to_graph() + { + return *this->gr_; + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of mln + + +#endif // MLN_CORE_BGRAPH_P_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_queue.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_queue.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_queue.hh (revision 1788) @@ -0,0 +1,309 @@ +// 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_QUEUE_HH +# define MLN_CORE_P_QUEUE_HH + +/*! \file mln/core/p_queue.hh + * + * \brief Definition of a point set class based on std::deque. + */ + +# include <vector> +# include <deque> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/accu/bbox.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point queue class (based on std::deque). + * + * This is a mathematical set of points (unique insertion). + * + * \todo Make it work with P being a Point_Site. + * \todo Add a parameter flag to choose another policy for "push" + * (i.e., no-op if multiple or allow multiple insertions). + * + * \warning We have some troubles with point set comparison based on + * a call to npoints() when this container is multiple. + */ + template <typename P> + class p_queue : public internal::point_set_base_< P, p_queue<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_queue(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if queue is empty or not. + bool is_empty() const; + + /// Give the number of points. + std::size_t npoints() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + /// Push force a point \p p in the queue. + p_queue<P>& push_force(const P& p); + + /// Push a point \p p in the queue. + p_queue<P>& push(const P& p); + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point. + void pop(); + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point. + const P& front() const; + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point and pop (remove) the front point \p p + /// from the queue; \p p is the least recently inserted point. + const P& pop_front(); + + /// Clear the queue. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + protected: + + std::deque<P> q_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_() const; + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_() const; + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_queue<P>::p_queue() + { + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P> + inline + void + p_queue<P>::vect_update_() const + { + vect_.clear(); + vect_.reserve(q_.size()); + std::copy(q_.begin(), q_.end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P> + inline + void + p_queue<P>::bb_update_() const + { + bb_.init(); + for (unsigned i = 0; i < q_.size(); ++i) + bb_.take(q_[i]); + bb_needs_update_ = false; + } + + template <typename P> + inline + bool + p_queue<P>::has(const P& p) const + { + for (unsigned i = 0; i < q_.size(); ++i) + if (q_[i] == p) + return true; + return false; + } + + template <typename P> + inline + bool + p_queue<P>::is_empty() const + { + return (q_.empty()); + } + + template <typename P> + inline + std::size_t + p_queue<P>::npoints() const + { + return q_.size(); + } + + template <typename P> + inline + const box_<P>& + p_queue<P>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P> + inline + p_queue<P>& + p_queue<P>::push_force(const P& p) + { + q_.push_back(p); + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + return *this; + } + + template <typename P> + inline + p_queue<P>& + p_queue<P>::push(const P& p) + { + mln_precondition(! has(p)); + // FIXME: Our choice is "error if multiple insertions" + return this->push_force(p); + } + + template <typename P> + inline + void + p_queue<P>::pop() + { + q_.pop_front(); + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + } + + template <typename P> + inline + const P& + p_queue<P>::front() const + { + mln_precondition(! q_.empty()); + return q_.front(); + } + + template <typename P> + inline + const P& + p_queue<P>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P> + inline + void + p_queue<P>::clear() + { + q_.clear(); + vect_.clear(); + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P> + inline + const std::vector<P>& + p_queue<P>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P> + inline + const P& + p_queue<P>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + return q_[i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_QUEUE_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_priority_queue.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_priority_queue.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_priority_queue.hh (revision 1788) @@ -0,0 +1,361 @@ +// 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_PRIORITY_QUEUE_HH +# define MLN_CORE_P_PRIORITY_QUEUE_HH + +/*! \file mln/core/p_priority_queue.hh + * + * \brief Definition of a point set class based on p_queue with + * priority features. + */ + +# include <vector> +# include <deque> +# include <map> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/accu/bbox.hh> +# include <mln/core/p_queue.hh> + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point priority queue class (based on p_queue and std::map). + * + * This is a mathematical set of points (unique insertion). + * + * \todo Make it work with P being a Point_Site. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints() when this container is multiple. + */ + template <typename P, typename T> + class p_priority_queue : public internal::point_set_base_< P, p_priority_queue<P, T> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_priority_queue(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if queue is empty or not. + bool is_empty() const; + + /// Give the number of points. + size_t npoints() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + /// Push force a point \p p in the queue. + p_priority_queue<P, T>& push_force(const P& p, T prio = 0); + + /// Push a point \p p in the queue. + p_priority_queue<P, T>& push(const P& p, T prio = 0); + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point. + void pop(); + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point. + const P& front() const; + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point and give the front point \p p of + /// the queue; \p p is the least recently inserted point. + const P& pop_front(); + + /// Clear the queue. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + protected: + + std::map<const T, p_queue<P> > q_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_() const; + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_() const; + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T> + inline + p_priority_queue<P, T>::p_priority_queue() + { + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T> + inline + void + p_priority_queue<P, T>::vect_update_() const + { + vect_.clear(); + vect_.reserve(npoints()); + + typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + std::copy((*it).second.vect().begin(), (*it).second.vect().end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P, typename T> + inline + void + p_priority_queue<P, T>::bb_update_() const + { + bb_.init(); + + typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + for (unsigned i = 0; i < (*it).second.npoints (); ++i) + bb_.take((*it).second[i]); + bb_needs_update_ = false; + } + + + template <typename P, typename T> + inline + bool + p_priority_queue<P, T>::has(const P& p) const + { + typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if ((*it).second.has (p)) + return true; + return false; + } + + template <typename P, typename T> + inline + bool + p_priority_queue<P, T>::is_empty() const + { + typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!(*it).second.is_empty ()) + return false; + return true; + } + + template <typename P, typename T> + inline + size_t + p_priority_queue<P, T>::npoints() const + { + unsigned res = 0; + + typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!(*it).second.is_empty ()) + res += (*it).second.npoints(); + return res; + } + + template <typename P, typename T> + inline + const box_<P>& + p_priority_queue<P, T>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P, typename T> + inline + p_priority_queue<P, T>& + p_priority_queue<P, T>::push_force(const P& p, T prio) + { + q_[prio].push_force (p); + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + return *this; + } + + template <typename P, typename T> + inline + p_priority_queue<P, T>& + p_priority_queue<P, T>::push(const P& p, T prio) + { + if (! has(p)) + return this->push_force(p, prio); + else + return *this; + } + + template <typename P, typename T> + inline + void + p_priority_queue<P, T>::pop() + { + typename std::map<T, p_queue<P> >::reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!(*it).second.is_empty ()) + return (*it).second.pop (); + + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + } + + template <typename P, typename T> + inline + const P& + p_priority_queue<P, T>::front() const + { + mln_precondition(! q_.empty()); + + typename std::map<T, p_queue<P> >::const_reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!(*it).second.is_empty ()) + break; + return (*it).second.front (); + } + + template <typename P, typename T> + inline + const P& + p_priority_queue<P, T>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P, typename T> + inline + void + p_priority_queue<P, T>::clear() + { + typename std::map<T, p_queue<P> >::iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + (*it).second.clear (); + q_.clear(); + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T> + inline + const std::vector<P>& + p_priority_queue<P, T>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P, typename T> + inline + const P& + p_priority_queue<P, T>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + + typename std::map<T, p_queue<P> >::const_reverse_iterator it = q_.rbegin (); + unsigned cpt = 0; + + for (; it != q_.rend (); ++it) + { + if (!(*it).second.is_empty ()) + for (cpt = 0; cpt < (*it).second.npoints (); ++cpt) + { + if (i == 0) + return (*it).second[cpt]; + --i; + } + } + return (*it).second[cpt]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_PRIORITY_QUEUE_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_line_graph.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_line_graph.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_line_graph.hh (revision 1788) @@ -0,0 +1,176 @@ +// 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. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CORE_LINE_GRAPH_P_HH +# define MLN_CORE_LINE_GRAPH_P_HH + +# include <mln/core/concept/point_site.hh> +# include <mln/core/internal/point_set_base.hh> +# include <mln/accu/bbox.hh> +# include <mln/util/graph.hh> +# include <mln/core/line_graph_psite.hh> +# include <mln/core/p_line_graph_piter.hh> +# include <mln/core/point_pair.hh> + +/* FIXME: This class shares a lot with p_graph. Factor as much as + possible. */ + + +/// \file mln/core/p_line_graph.hh +/// \brief Definition of a point set based on line graph. + +namespace mln +{ + + // FIXME: Dummy specialization, only to have this first version of + // our code compile. + template <typename P> + struct box_< point_pair<P> > : public Box< box_<P> > + { + // Nothing. + }; + + + template<typename P> class p_line_graph_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + template<typename P> + struct p_line_graph + : public internal::point_set_base_< line_graph_psite<P>, p_line_graph<P> > + { + typedef util::graph<P> graph; + + /// Construct a line graph psite set from a graph of points. + p_line_graph (graph& gr); + + /// Point_Site associated type. + typedef line_graph_psite<P> psite; + + /// Point associated type. + typedef point_pair<P> point; + + /// Forward Point_Iterator associated type. + typedef p_line_graph_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_line_graph_piter_<P> bkd_piter; + + /// Return The number of points (i.e., nodes) in the graph. + std::size_t npoints() const; + + /// Return The number of lines (i.e., edges) in the graph. + std::size_t nlines() const; + + /// Give the exact bounding box. + // FIXME: Dummy. + const box_<point>& bbox() const; + + bool has(const psite& p) const; + + // FIXME: Should be private. + graph gr_; + // FIXME: (Roland) Is it really useful/needed? + /* 2007-12-19: It seems so, since graph_image must implement a + method named bbox(). Now the question is: should each image + type have a bounding box? In particular, an image whose sites + are actually /pairs of points/! */ + // FIXME: Dummy. + box_<point> bb_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template<typename P> + inline + p_line_graph<P>::p_line_graph (util::graph<P>& gr) + : gr_ (gr) + { + // FIXME: Dummy initialization of bb_. +// // FIXME: Warning: if the underlying graph is updated later, this +// // won't be taken into account by this p_line_graph! +// accu::bbox<point> a; +// for (util::edge_id e = 0; e < nlines(); ++e) +// a.take(point(gr_.node_data(gr_.edge(e).n1()), +// gr_.node_data(gr_.edge(e).n2()))); +// bb_ = a.to_result(); + } + + // FIXME: Rename to npsites? In fact, this depends on the + // interface expected from models of Point_Sets. + template<typename P> + inline + std::size_t + p_line_graph<P>::npoints() const + { + return this->gr_.nnodes(); + } + + template<typename P> + inline + std::size_t + p_line_graph<P>::nlines() const + { + return this->gr_.nedges(); + } + + template<typename P> + inline + const box_< point_pair<P> >& + p_line_graph<P>::bbox() const + { + return bb_; + } + + template<typename P> + inline + bool + p_line_graph<P>::has(const psite& p) const + { + return + // Check whether P is compatible with this psite set. + (&p.plg() == this) && + // Check that the edge id of P belongs to the range of valid edge ids. + (p.id() < gr_.nedges()); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of mln + + +#endif // MLN_CORE_P_GRAPH_HH Index: trunk/milena/sandbox/pellegrin/set/core/pset_if.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/pset_if.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/pset_if.hh (revision 1788) @@ -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_PSET_IF_HH +# define MLN_CORE_PSET_IF_HH + +/*! \file mln/core/pset_if.hh + * + * \brief Definition of the restriction of a point set w.r.t. a predicate. + */ + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/concept/function.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename S, typename F> struct pset_if; + template <typename S, typename F> struct pset_if_fwd_piter_; + template <typename S, typename F> struct pset_if_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_< pset_if<> > : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Restrict a point set \p pset to points that verify \p f. + * + * \param[in] pset A point set. + * \param[in] f A function from point to Boolean. + * \return A subset of points. + */ + template <typename S, typename F> + pset_if<S, F> + operator | (const Point_Set<S>& pset, const Function_p2b<F>& f); + + + + /*! \brief Generic subset class. + * + * Parameter \c S is a point set type; parameter F is a function + * from point to Boolean. + */ + template <typename S, typename F> + class pset_if : public internal::point_set_base_< mln_psite(S), pset_if<S,F> > + { + typedef pset_if<S,F> self_; + typedef internal::point_set_base_<mln_psite(S), self_> super_; + public: + + typedef mln_psite(super_) psite; + + /// Forward Point_Iterator associated type. + typedef pset_if_fwd_piter_<S,F> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef mln::internal::fixme bkd_piter; + + + /// Constructor with a point set \p pset and a predicate \p f. + pset_if(const S& pset, const F& f); + + /// Constructor without argument. + pset_if(); + + + /// Test if \p p belongs to the subset. + bool has(const psite& p) const; + + /// Give a bounding box of the subset. + const box_<mln_point(S)>& bbox() const; + + /// Give the number of points of the subset. + std::size_t npoints() const; + + /// Give the primary overset. + const S& overset() const; + + /// Test predicate on point site \p p. + bool pred(const psite& p) const; + + /// Give the predicate function. + const F& predicate() const; + + protected: + + S pset_; + F f_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename S, typename F> + inline + pset_if<S, F> + operator | (const Point_Set<S>& pset, const Function_p2b<F>& f) + { + pset_if<S, F> tmp(exact(pset), exact(f)); + return tmp; + } + + + // pset_if<S,F> + + template <typename S, typename F> + inline + bool + pset_if<S,F>::has(const psite& p) const + { + return pset_.has(p) && f_(p); + } + + template <typename S, typename F> + inline + const box_<mln_point(S)>& + pset_if<S,F>::bbox() const + { + return pset_.bbox(); + } + + template <typename S, typename F> + inline + const S& + pset_if<S,F>::overset() const + { + return pset_; + } + + template <typename S, typename F> + inline + bool + pset_if<S,F>::pred(const psite& p) const + { + return f_(p); + } + + template <typename S, typename F> + inline + pset_if<S,F>::pset_if(const S& pset, const F& f) + : pset_(pset), + f_(f) + { + } + + template <typename S, typename F> + inline + pset_if<S,F>::pset_if() + { + } + + template <typename S, typename F> + inline + const F& + pset_if<S,F>::predicate() const + { + return f_; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + + +# include <mln/core/pset_if_piter.hh> + + + +namespace mln +{ + +# ifndef MLN_INCLUDE_ONLY + + template <typename S, typename F> + std::size_t + pset_if<S,F>::npoints() const + { + std::size_t n = 0; + fwd_piter p(*this); + for_all(p) + ++n; + return n; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_PSET_IF_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_set.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_set.hh (revision 1788) @@ -0,0 +1,191 @@ +// 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_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/internal/set_of.hh> +# include <mln/accu/bbox.hh> +# include <mln/core/p_array.hh> + + +namespace mln +{ + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point set class based on std::set. + * + * 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_set : public internal::point_set_base_< P, p_set<P> >, + private internal::set_of_<P> + { + typedef internal::set_of_<P> super_; + + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_set(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Return the corresponding std::vector of points. + using super_::vect; + + /// Give the number of points. + std::size_t npoints() const; + + /// Insert a point \p p. + p_set<P>& insert(const P& p); + + // FIXME : doesn't compile + // /// Remove a point \p p. + // p_set<P>& remove(P& p); + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + /// Clear this set. + void clear(); + + /// Give the exact bounding box. + const box_<mln_point(P)>& bbox() const; + + protected: + + accu::bbox<P> bb_; + // FIXME: Add invariant bb_.is_valid() <=> npoints() != 0 + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_set<P>::p_set() + { + } + + template <typename P> + inline + bool + p_set<P>::has(const P& p) const + { + return this->super_::has(p); + } + + template <typename P> + inline + std::size_t + p_set<P>::npoints() const + { + return this->super_::nelements(); + } + + template <typename P> + inline + p_set<P>& + p_set<P>::insert(const P& p) + { + this->super_::insert(p); + bb_.take(p); + return *this; + } + + + // FIXME : finish it. + // template <typename P> + // p_set<P>& + // p_set<P>::remove(P& p) + // { + // this->super_::remove(p); + // // FIXME: need to rebuild bb_ ? + // //bb_.untake(p); + // return *this; + // } + + template <typename P> + inline + const P& + p_set<P>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + return this->super_::element(i); + } + + template <typename P> + inline + void + p_set<P>::clear() + { + this->super_::clear(); + bb_.init(); + } + + template <typename P> + inline + const box_<mln_point(P)>& + p_set<P>::bbox() const + { + mln_precondition(npoints() != 0); + return bb_.to_result(); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_SET_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast_with_array.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast_with_array.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_priority_queue_fast_with_array.hh (revision 1788) @@ -0,0 +1,347 @@ +// 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_PRIORITY_QUEUE_FAST_WITH_ARRAY_HH +# define MLN_CORE_P_PRIORITY_QUEUE_FAST_WITH_ARRAY_HH + +/*! \file mln/core/p_priority_queue_fast_with_array.hh + * + * \brief Definition of a point set class based on p_queue with + * priority features. + */ + +# include <vector> +# include <deque> +# include <map> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/accu/bbox.hh> +# include <mln/core/p_queue_fast.hh> + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point queue class (based on std::vector and p_queue_fast). + * + * This is a mathematical set of points (unique insertion). + * + * \todo Make it work with P being a Point_Site. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints() when this container is multiple. + */ + template <typename P, typename T, unsigned S> + class p_priority_queue_fast_with_array : public internal::point_set_base_< P, p_priority_queue_fast_with_array<P, T, S> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_priority_queue_fast_with_array(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if queue is empty or not. + bool is_empty() const; + + /// Give the number of points. + unsigned npoints() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + /// Push force a point \p p in the queue. + p_priority_queue_fast_with_array<P, T, S>& push_force(const P& p, T prio = 0); + + /// Push a point \p p in the queue. + p_priority_queue_fast_with_array<P, T, S>& push(const P& p, T prio = 0); + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point. + void pop(); + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point. + const P& front() const; + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point and give the front point \p p of + /// the queue; \p p is the least recently inserted point. + const P& pop_front(); + + /// Clear the queue. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + protected: + + std::vector<p_queue_fast<P> > q_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_() const; + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_() const; + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T, unsigned S> + inline + p_priority_queue_fast_with_array<P, T, S>::p_priority_queue_fast_with_array() + { + vect_needs_update_ = false; + bb_needs_update_ = false; + q_.reserve(S); + std::copy(q_.begin(), q_.end(), + std::back_inserter(q_)); + for (unsigned i = 0; i < S; ++i) + q_[i].clear (); + } + + template <typename P, typename T, unsigned S> + inline + void + p_priority_queue_fast_with_array<P, T, S>::vect_update_() const + { + vect_.clear(); + vect_.reserve(npoints()); + + for (unsigned i = 0; i < S; ++i) + std::copy(q_[i].vect().begin(), q_[i].vect().end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P, typename T, unsigned S> + inline + void + p_priority_queue_fast_with_array<P, T, S>::bb_update_() const + { + bb_.init(); + + for (unsigned i = 0; i < S; ++i) + for (unsigned j = 0; j < q_[i].npoints (); ++j) + bb_.take(q_[i][j]); + bb_needs_update_ = false; + } + + + template <typename P, typename T, unsigned S> + inline + bool + p_priority_queue_fast_with_array<P, T, S>::has(const P& p) const + { + for (unsigned i = 0; i < S; ++i) + if (q_[i].has (p)) + return true; + return false; + } + + template <typename P, typename T, unsigned S> + inline + bool + p_priority_queue_fast_with_array<P, T, S>::is_empty() const + { + for (unsigned i = 0; i < S; ++i) + if (!q_[i].is_empty ()) + return false; + return true; + } + + template <typename P, typename T, unsigned S> + inline + unsigned + p_priority_queue_fast_with_array<P, T, S>::npoints() const + { + unsigned res = 0; + + for (unsigned i = 0; i < S; ++i) + if (!q_[i].is_empty ()) + res += q_[i].npoints(); + + return res; + } + + template <typename P, typename T, unsigned S> + inline + const box_<P>& + p_priority_queue_fast_with_array<P, T, S>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P, typename T, unsigned S> + inline + p_priority_queue_fast_with_array<P, T, S>& + p_priority_queue_fast_with_array<P, T, S>::push_force(const P& p, T prio) + { + q_[prio].push_force (p); + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + mln_assertion(!q_[prio].is_empty ()); + return *this; + } + + template <typename P, typename T, unsigned S> + inline + p_priority_queue_fast_with_array<P, T, S>& + p_priority_queue_fast_with_array<P, T, S>::push(const P& p, T prio) + { + if (! has(p)) + return this->push_force(p, prio); + else + return *this; + } + + template <typename P, typename T, unsigned S> + inline + void + p_priority_queue_fast_with_array<P, T, S>::pop() + { + for (unsigned i = S - 1; i != UINT_MAX; --i) + if (!q_[i].is_empty ()) + return q_[i].pop (); + + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + } + + template <typename P, typename T, unsigned S> + inline + const P& + p_priority_queue_fast_with_array<P, T, S>::front() const + { + mln_precondition(! is_empty()); + + for (unsigned i = S - 1; i != UINT_MAX; --i) + if (!q_[i].is_empty ()) + return q_[i].front (); + return q_[0].front (); + } + + template <typename P, typename T, unsigned S> + inline + const P& + p_priority_queue_fast_with_array<P, T, S>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P, typename T, unsigned S> + inline + void + p_priority_queue_fast_with_array<P, T, S>::clear() + { + for (unsigned i = 0; i < S; ++i) + q_[i].clear (); + q_.clear(); + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T, unsigned S> + inline + const std::vector<P>& + p_priority_queue_fast_with_array<P, T, S>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P, typename T, unsigned S> + inline + const P& + p_priority_queue_fast_with_array<P, T, S>::operator[](unsigned n) const + { + mln_precondition(n < npoints()); + unsigned i = S - 1; + unsigned cpt = 0; + + for (; i != UINT_MAX; --i) + if (!q_[i].is_empty ()) + for (cpt = 0; cpt < q_[i].npoints (); ++cpt, --n) + if (n == 0) + return q_[i][cpt]; + mln_assertion (false); + return q_[i][cpt]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_PRIORITY_QUEUE_FAST_WITH_ARRAY_HH Index: trunk/milena/sandbox/pellegrin/set/core/runs_psite.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/runs_psite.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/runs_psite.hh (revision 1788) @@ -0,0 +1,192 @@ +// 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_RUNS_PSITE_HH +# define MLN_CORE_RUNS_PSITE_HH + +/*! \file mln/core/runs_psite.hh + * + * \brief Definition of class mln::runs_psite_ for internal use only + */ + +# include <mln/core/concept/point_site.hh> + + +namespace mln +{ + // Fwd decl. + template <typename P> class p_runs_; + + /*! \brief Psite class used in run_image_. + * + * Parameter \c P is the type of the image point. + */ + template <typename P> + class runs_psite : public Point_Site< runs_psite<P> > + { + public: + + typedef mln_mesh(P) mesh; + enum { dim = P::dim }; + typedef P point; + typedef mln_dpoint(P) dpoint; + typedef mln_coord(P) coord; + + runs_psite(const p_runs_<P>& pr, unsigned in_run, unsigned of_run); + + operator P () const; + + /// Return the point at the start of the current run. + P& range_start_(); + + /// Return the point at the start of the current run. + const P& range_start_() const; + + /// Return the position of this psite in the point set. + unsigned p_of_run() const; + + /// Return the position of this psite in the point set. + unsigned& p_of_run(); + + /// Return the position of this psite in the current range. + unsigned p_in_run() const; + + /// Return the position of this psite in the current range. + unsigned& p_in_run(); + + /// Reference to the corresponding point. + const P& to_point() const; + + /// Give the i-th coordinate of the corresponding point. + mln_coord(P) operator[](unsigned i) const; + + protected: + + /// Start of the psite range. + const p_runs_<P>& pr_; + + /// Position in the psite range. + unsigned p_in_run_; + + /// Position of the psite in the point set. + unsigned p_of_run_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + runs_psite<P>::runs_psite(const p_runs_<P>& pr, unsigned in_run, unsigned of_run) + : pr_(pr), + p_in_run_(in_run), + p_of_run_(of_run) + { + mln_precondition(of_run < pr.nruns()); + mln_precondition(in_run < pr[of_run].length()); + } + + template <typename P> + inline + runs_psite<P>::operator P() const + { + return pr_[p_of_run_][p_in_run_]; + } + + template <typename P> + inline + const P& + runs_psite<P>::range_start_() const + { + return pr_[p_of_run_].first(); + } + + template <typename P> + inline + P& + runs_psite<P>::range_start_() + { + return pr_[p_of_run_].first(); + } + + template <typename P> + inline + unsigned + runs_psite<P>::p_of_run() const + { + return p_of_run_; + } + + template <typename P> + inline + unsigned& + runs_psite<P>::p_of_run() + { + return p_of_run_; + } + + template <typename P> + inline + unsigned + runs_psite<P>::p_in_run() const + { + return p_in_run_; + } + + template <typename P> + inline + unsigned& + runs_psite<P>::p_in_run() + { + return p_in_run_; + } + + template <typename P> + inline + const P& + runs_psite<P>::to_point() const + { + static P p = pr_[p_of_run_][p_in_run_]; + return p; + } + + template <typename P> + inline + mln_coord(P) + runs_psite<P>::operator[](unsigned i) const + { + mln_precondition(i < dim); + return pr_[p_of_run_][p_in_run_][i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +# include <mln/core/p_runs.hh> + +#endif // ! MLN_CORE_INTERNAL_RUNS_PSITE_HH Index: trunk/milena/sandbox/pellegrin/set/core/line2d.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/line2d.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/line2d.hh (revision 1788) @@ -0,0 +1,208 @@ +// 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_LINE2D_HH +# define MLN_CORE_LINE2D_HH + +/*! \file mln/core/line2d.hh + * + * \brief Definition of a point set class based on std::vector. + */ + +# include <vector> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/core/box2d.hh> +# include <mln/math/all.hh> + + +namespace mln +{ + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief 2D line point set class. + */ + class line2d : public internal::point_set_base_< point2d, line2d > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<point2d> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<point2d> bkd_piter; + + + /// Constructor from point \p beg to point \p end. + line2d(const point2d& beg, const point2d& end); + + + /// Test is \p p belongs to this point set. + bool has(const point2d& p) const; + + /// Give the number of points. + std::size_t npoints() const; + + /// Give the exact bounding box. + const box_<point2d>& bbox() const; + + /// Return the corresponding std::vector of points. + const std::vector<point2d>& vect() const; + + /// Return the \p i-th point. + const point2d& operator[](unsigned i) const; + + protected: + + point2d beg_, end_; + std::vector<point2d> vect_; + box2d bb_; + + void compute_(); + }; + + + +# ifndef MLN_INCLUDE_ONLY + + inline + line2d::line2d(const point2d& beg, const point2d& end) + : beg_(beg), + end_(end) + { + compute_(); + } + + inline + void + line2d::compute_() + { + // vect_ + dpoint2d dp = end_ - beg_; + int + srow = math::sign(dp.row()), drow = math::abs(dp.row()), ddrow = 2 * drow, + scol = math::sign(dp.col()), dcol = math::abs(dp.col()), ddcol = 2 * dcol, + row = beg_.row(), + col = beg_.col(); + if ( dcol > drow ) + { + int e = ddrow - dcol; + for (int i = 0; i < dcol; ++i) + { + vect_.push_back(make::point2d(row, col)); + while (e >= 0) + { + row += srow; + e -= ddcol; + } + col += scol; + e += ddrow; + } + } + else + { + int e = ddcol - drow; + for (int i = 0; i < drow; ++i) + { + vect_.push_back(make::point2d(row, col)); + while (e >= 0) + { + col += scol; + e -= ddrow; + } + row += srow; + e += ddcol; + } + } + vect_.push_back(make::point2d(row, col)); + // bb_ + bb_.pmin() = make::point2d(math::min(beg_.row(), end_.row()), + math::min(beg_.col(), end_.col())); + bb_.pmax() = make::point2d(math::max(beg_.row(), end_.row()), + math::max(beg_.col(), end_.col())); + } + + inline + bool + line2d::has(const point2d& p) const + { + if (! bb_.has(p)) + return false; + // FIXME: Optimize! + for (unsigned i = 0; i < vect_.size(); ++i) + if (vect_[i] == p) + return true; + return false; + } + + inline + std::size_t + line2d::npoints() const + { + return vect_.size(); + } + + inline + const box2d& + line2d::bbox() const + { + return bb_; + } + + inline + const std::vector<point2d>& + line2d::vect() const + { + return vect_; + } + + inline + const point2d& + line2d::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + return vect_[i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_LINE2D_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_array.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_array.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_array.hh (revision 1788) @@ -0,0 +1,245 @@ +// 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_ARRAY_HH +# define MLN_CORE_P_ARRAY_HH + +/*! \file mln/core/p_array.hh + * + * \brief Definition of a point set class based on std::vector. + */ + +# include <vector> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/accu/bbox.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_< p_array<P> > : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point set class based on std::vector. + * + * This is a multi-set of points. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints(). FIXME: Explain! + * + * \todo Make it work with P being a Point_Site. + */ + template <typename P> + class p_array : public internal::point_set_base_< P, p_array<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_array(); + + /// Constructor from a vector \p vect. + p_array(const std::vector<P>& vect); + + /// Reserve \p n cells. + void reserve(std::size_t n); + + /// 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 exact bounding box. + const box_<P>& bbox() const; + + /// Append a point \p p. + p_array<P>& append(const P& p); + + /// Clear this set. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + /// Hook to data. + std::vector<P>& hook_(); + + protected: + + std::vector<P> vect_; + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + + void update_bb_() const; + // FIXME: Add invariant bb_.is_valid() <=> npoints() != 0 + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_array<P>::p_array() + { + bb_needs_update_ = false; + } + + template <typename P> + inline + p_array<P>::p_array(const std::vector<P>& vect) + : vect_(vect) + { + bb_needs_update_ = true; + } + + template <typename P> + inline + void + p_array<P>::reserve(std::size_t n) + { + vect_.reserve(n); + } + + template <typename P> + inline + std::vector<P>& + p_array<P>::hook_() + { + return vect_; + } + + template <typename P> + inline + void + p_array<P>::update_bb_() const + { + bb_.init(); + for (unsigned i = 0; i < vect_.size(); ++i) + bb_.take(vect_[i]); + bb_needs_update_ = false; + } + + template <typename P> + inline + bool + p_array<P>::has(const P& p) const + { + for (unsigned i = 0; i < vect_.size(); ++i) + if (vect_[i] == p) + return true; + return false; + } + + template <typename P> + inline + std::size_t + p_array<P>::npoints() const + { + return vect_.size(); + } + + template <typename P> + inline + const box_<P>& + p_array<P>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + update_bb_(); + return bb_.to_result(); + } + + template <typename P> + inline + p_array<P>& + p_array<P>::append(const P& p) + { + vect_.push_back(p); + if (! bb_needs_update_) + bb_needs_update_ = true; + return *this; + } + + template <typename P> + inline + void + p_array<P>::clear() + { + vect_.clear(); + bb_needs_update_ = false; + } + + template <typename P> + inline + const std::vector<P>& + p_array<P>::vect() const + { + return vect_; + } + + template <typename P> + inline + const P& + p_array<P>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + return vect_[i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/p_array_piter.hh> + + +#endif // ! MLN_CORE_P_ARRAY_HH Index: trunk/milena/sandbox/pellegrin/set/core/concept/point_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/concept/point_set.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/concept/point_set.hh (revision 1788) @@ -0,0 +1,252 @@ +// 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_POINT_SET_HH +# define MLN_CORE_CONCEPT_POINT_SET_HH + +/*! \file mln/core/concept/point_set.hh + * + * \brief Definition of the concept of mln::Point_Set. + * + * \todo Think about adding an 'insert' method (not so easy because of + * pset_if...) + */ + +# include <mln/core/concept/point_site.hh> +# include <mln/core/concept/point_iterator.hh> +# include <mln/trait/point_set.hh> + + +namespace mln +{ + + // Fwd decl. + template <typename E> struct Point_Set; + + + /// Point_Set category flag type. + template <> + struct Point_Set<void> + { + typedef Object<void> super; + }; + + + /*! \brief Base class for implementation classes of point sets. + * + * \see mln::doc::Point_Set for a complete documentation of this + * class contents. + */ + template <typename E> + struct Point_Set : public Object<E> + { + typedef Point_Set<void> category; + + /* + typedef mesh; + + typedef point; + typedef psite; + + typedef fwd_piter; + typedef bkd_piter; + + bool has(const psite& p) const; + const box_<point>& bbox() const; + std::size_t npoints() const; + */ + + protected: + Point_Set(); + }; + + + /*! \brief Equality test between point sets \p lhs and \p rhs. + * + * \param[in] lhs A point set. + * \param[in] rhs Another point set. + * + * \relates mln::Point_Set + */ + template <typename Sl, typename Sr> + bool operator==(const Point_Set<Sl>& lhs, const Point_Set<Sr>& rhs); + + + + /*! \brief Inclusion test between point sets \p lhs and \p rhs. + * + * \param[in] lhs A point set (included?). + * \param[in] rhs Another point set (includer?). + * + * \relates mln::Point_Set + */ + template <typename Sl, typename Sr> + bool operator<=(const Point_Set<Sl>& lhs, const Point_Set<Sr>& rhs); + + + + /*! \brief Strict inclusion test between point sets \p lhs and \p + * rhs. + * + * \param[in] lhs A point set (strictly included?). + * \param[in] rhs Another point set (includer?). + * + * \relates mln::Point_Set + */ + template <typename Sl, typename Sr> + bool operator<(const Point_Set<Sl>& lhs, const Point_Set<Sr>& rhs); + + + + /*! \brief Print a point set \p pset into the output stream \p + * ostr. + * + * \param[in,out] ostr An output stream. + * \param[in] pset A point set. + * + * \return The modified output stream \p ostr. + * + * \relates mln::Point_Set + */ + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const Point_Set<S>& pset); + + + +# ifndef MLN_INCLUDE_ONLY + + // fwd decl + template <typename P> struct box_; + + template <typename E> + inline + Point_Set<E>::Point_Set() + { + typedef mln_mesh(E) mesh; + + typedef mln_point(E) point; + typedef mln_psite(E) psite; + + typedef mln_fwd_piter(E) fwd_piter; + typedef mln_bkd_piter(E) bkd_piter; + + typedef mln_trait_point_set_arity(P) arity; + typedef mln_trait_point_set_has_speed(P) has_speed; + + bool (E::*m1)(const psite& p) const = & E::has; + m1 = 0; + const box_<point>& (E::*m2)() const = & E::bbox; + m2 = 0; + std::size_t (E::*m3)() const = & E::npoints; + m3 = 0; + } + + + // operators + + + template <typename Sl, typename Sr> + inline + bool operator==(const Point_Set<Sl>& lhs_, const Point_Set<Sr>& rhs_) + { + // FIXME: Same grid! + const Sl& lhs = exact(lhs_); + const Sr& rhs = exact(rhs_); + + // easy test: + if (lhs.npoints() != rhs.npoints()) + return false; + + // exhaustive test: + mln_fwd_piter(Sl) pl(lhs); + mln_fwd_piter(Sr) pr(rhs); + for (pl.start(), pr.start(); + pl.is_valid() && pr.is_valid(); + pl.next(), pr.next()) + if (pl != pr) + return false; // difference found + + // both sets are equal only if both browsings are completed + // at the same time: + return ! pl.is_valid() && ! pr.is_valid(); + } + + + template <typename Sl, typename Sr> + inline + bool operator<=(const Point_Set<Sl>& lhs_, const Point_Set<Sr>& rhs_) + { + // FIXME: Same grid! + const Sl& lhs = exact(lhs_); + const Sr& rhs = exact(rhs_); + + // easy test: + if (lhs.npoints() > rhs.npoints()) + return false; + + // exhaustive test: + mln_piter(Sl) pl(lhs); + for_all(pl) + if (! rhs.has(pl)) + return false; + + return true; + } + + + template <typename Sl, typename Sr> + inline + bool operator<(const Point_Set<Sl>& lhs_, const Point_Set<Sr>& rhs_) + { + // FIXME: Same grid! + const Sl& lhs = exact(lhs_); + const Sr& rhs = exact(rhs_); + return lhs <= rhs && lhs.npoints() != rhs.npoints(); + } + + + template <typename S> + inline + std::ostream& operator<<(std::ostream& ostr, const Point_Set<S>& pset_) + { + const S& pset = exact(pset_); + ostr << '{'; + mln_piter(S) p(pset); + for_all(p) + ostr << p; + return ostr << '}'; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/ops.hh> + + +#endif // ! MLN_CORE_CONCEPT_POINT_SET_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_graph.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_graph.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_graph.hh (revision 1788) @@ -0,0 +1,258 @@ +// 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. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CORE_P_GRAPH_HH +# define MLN_CORE_P_GRAPH_HH + +# include <mln/core/concept/point_site.hh> +# include <mln/core/internal/point_set_base.hh> +# include <mln/accu/bbox.hh> +# include <mln/util/graph.hh> +# include <mln/core/graph_psite.hh> +# include <mln/core/p_graph_piter.hh> + +/// \file mln/core/p_graph.hh +/// \brief Definition of a point set based on graph. + +namespace mln +{ + + template<typename P> class p_graph_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + template<typename P> + struct p_graph + : public internal::point_set_base_< graph_psite<P>, p_graph<P> > + { + typedef util::graph<P> graph; + + /// Construct a graph psite set from a graph of points. + p_graph (graph& gr); + + /// Point_Site associated type. + typedef graph_psite<P> psite; + + /// Forward Point_Iterator associated type. + typedef p_graph_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_graph_piter_<P> bkd_piter; + + /// Return The number of points (i.e., nodes) in the graph. + std::size_t npoints() const; + + /// Return The number of lines (i.e., edges) in the graph. + std::size_t nlines() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + bool has(const psite& p) const; + + /// Return the graph point (FIXME site?) from an index + const P& point_from_id(const util::node_id& id) const; + P& point_from_id(const util::node_id& id); + + + /// Return the point contained in the first node adjacent + // to the edge id \a e. + const P& node1(const util::edge_id& e) const; + /// Return the point contained in the second node adjacent + /// to the edge id \a e. + const P& node2(const util::edge_id& e) const; + + /// Return true if the psites lhs and rhs are adjacent, or equal. + bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; + + /// Return true if the nodes lhs and rhs are adjacent, or equal + bool adjacent_or_equal(const util::node_id& lhs, + const util::node_id& rhs) const; + + /// Return the graph associated to the p_graph domain: + const graph& to_graph() const; + graph& to_graph(); + + + private: + graph gr_; + // FIXME: (Roland) Is it really useful/needed? + /* 2007-12-19: It seems so, since graph_image must implement a method + named bbox(). Now the question is: should each image type have a + bounding box? */ + box_<P> bb_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template<typename P> + inline + p_graph<P>::p_graph (util::graph<P>& gr) + : gr_ (gr) + { + // FIXME: Warning: if the underlying graph is updated later, this + // won't be taken into account by this p_graph! + accu::bbox<P> a; + for (unsigned i = 0; i < npoints(); ++i) + a.take(gr_.node_data(i)); + bb_ = a.to_result(); + } + + // FIXME: Rename to npsites? In fact, this depends on the + // interface expected from models of Point_Sets. + template<typename P> + inline + std::size_t + p_graph<P>::npoints() const + { + return this->gr_.nnodes(); + } + + template<typename P> + inline + std::size_t + p_graph<P>::nlines() const + { + return this->gr_.nedges(); + } + + template<typename P> + inline + const box_<P>& + p_graph<P>::bbox() const + { + return bb_; + } + + template<typename P> + inline + bool + p_graph<P>::has(const psite& p) const + { + return + // Check whether P is compatible with this psite set. + (&p.pg() == this) && + // Check that the node id of P belongs to the range of valid node ids. + (p.id() < gr_.nnodes()); + } + + template <typename P> + const P& + p_graph<P>::point_from_id(const util::node_id& id) const + { + return this->gr_.node_data(id); + } + + template <typename P> + P& + p_graph<P>::point_from_id(const util::node_id& id) + { + return this->gr_.node_data(id); + } + + template <typename P> + const P& + p_graph<P>::node1(const util::edge_id& e) const + { + util::node_id n1 = this->gr_.edge(e).n1(); + return this->point_from_id(n1); + } + + template <typename P> + const P& + p_graph<P>::node2(const util::edge_id& e) const + { + util::node_id n2 = this->gr_.edge(e).n2(); + return this->point_from_id(n2); + } + + template <typename P> + inline + bool + p_graph<P>::adjacent_or_equal(const psite& lhs, const psite& rhs) const + { + assert (&lhs.pg() == this && rhs.pg() == this); + return adjacent_or_equal(lhs.id(), rhs.id()); + } + + template <typename P> + inline + bool + p_graph<P>::adjacent_or_equal(const util::node_id& lhs, + const util::node_id& rhs) const + { + // FIXME: Likewise, this is inefficient. + + assert (lhs < this->npoints()); + assert (rhs < this->npoints()); + + if (rhs == lhs) + return true; + + // Check whether the iterator is among the neighbors of P_REF_. + typedef std::vector<util::node_id> adjacency_type; + const adjacency_type& lhs_neighbs = gr_.nodes()[lhs]->edges; + + adjacency_type::const_iterator j = + std::find (lhs_neighbs.begin(), lhs_neighbs.end(), rhs); + if (j != lhs_neighbs.end()) + return true; + + return false; + } + + template <typename P> + const typename p_graph<P>::graph& + p_graph<P>::to_graph() const + { + return this->gr_; + } + + template <typename P> + typename p_graph<P>::graph& + p_graph<P>::to_graph() + { + return this->gr_; + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of mln + + +#endif // MLN_CORE_P_GRAPH_HH Index: trunk/milena/sandbox/pellegrin/set/core/p_queue_fast.hh =================================================================== --- trunk/milena/sandbox/pellegrin/set/core/p_queue_fast.hh (revision 0) +++ trunk/milena/sandbox/pellegrin/set/core/p_queue_fast.hh (revision 1788) @@ -0,0 +1,316 @@ +// 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_QUEUE_FAST_HH +# define MLN_CORE_P_QUEUE_FAST_HH + +/*! \file mln/core/p_queue_fast.hh + * + * \brief Definition of a point set class faster but needs more memory + * space. + */ + +# include <vector> +# include <deque> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/p_array_piter.hh> +# include <mln/accu/bbox.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename P> struct p_array_fwd_piter_; + template <typename P> struct p_array_bkd_piter_; + + namespace trait + { + + template <typename P> + struct point_set_<line2d> : public default_point_set_<P> + { + typedef trait::point_set::arity::unique arity; + typedef trait::point_set::has_speed::fast has_speed; + } + + } + + /*! \brief Point queue class (based on std::deque). + * + * This is a mathematical set of points (unique insertion). + * + * \todo Make it work with P being a Point_Site. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints() when this container is multiple. + */ + template <typename P> + class p_queue_fast : public internal::point_set_base_< P, p_queue_fast<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef p_array_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef p_array_bkd_piter_<P> bkd_piter; + + /// Constructor. + p_queue_fast(); + + /// Test is \p p belongs to this point set. + bool has(const P& p) const; + + /// Test if queue is empty or not. + bool is_empty() const; + + /// Give the number of points. + std::size_t npoints() const; + + /// Give the exact bounding box. + const box_<P>& bbox() const; + + /// Push force a point \p p in the queue. + p_queue_fast<P>& push_force(const P& p); + + /// Push a point \p p in the queue. + p_queue_fast<P>& push(const P& p); + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point. + void pop(); + + /// Give the front point \p p of the queue; \p p is the least + /// recently inserted point. + const P& front() const; + + /// Pop (remove) the front point \p p from the queue; \p p is the + /// least recently inserted point and give the front point \p p of + /// the queue; \p p is the least recently inserted point. + const P& pop_front(); + + /// Clear the queue. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<P>& vect() const; + + /// Return the \p i-th point. + const P& operator[](unsigned i) const; + + protected: + + std::vector<P> q_; + std::size_t begin_; + std::size_t end_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_() const; + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_() const; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_queue_fast<P>::p_queue_fast() + { + // vect_needs_update_ = false; + bb_needs_update_ = false; + begin_ = 0; + end_ = 0; + } + + template <typename P> + inline + void + p_queue_fast<P>::vect_update_() const + { + vect_.clear(); + vect_.reserve(q_.size()); + std::copy(q_.begin(), q_.end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P> + inline + void + p_queue_fast<P>::bb_update_() const + { + bb_.init(); + for (std::size_t i = this->begin_; i < this->end_; ++i) + bb_.take(q_[i]); + bb_needs_update_ = false; + } + + template <typename P> + inline + bool + p_queue_fast<P>::has(const P& p) const + { + for (unsigned i = this->begin_; i < this->end_; ++i) + if (q_[i] == p) + return true; + return false; + } + + template <typename P> + inline + bool + p_queue_fast<P>::is_empty() const + { + return (this->begin_ == this->end_); + } + + template <typename P> + inline + std::size_t + p_queue_fast<P>::npoints() const + { + mln_precondition(this->end_ >= this->begin_); + return (this->end_ - this->begin_); + } + + template <typename P> + inline + const box_<P>& + p_queue_fast<P>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P> + inline + p_queue_fast<P>& + p_queue_fast<P>::push_force(const P& p) + { + q_.push_back(p); + ++this->end_; + if (! vect_needs_update_) + { + // vect_needs_update_ = true; + bb_needs_update_ = true; + } + return *this; + } + + template <typename P> + inline + p_queue_fast<P>& + p_queue_fast<P>::push(const P& p) + { + mln_precondition(! this->has(p)); + // FIXME: Our choice is "error if multiple insertions" + return this->push_force(p); + } + + template <typename P> + inline + void + p_queue_fast<P>::pop() + { + ++this->begin_; +// q_.pop_front(); +// if (! vect_needs_update_) +// { +// vect_needs_update_ = true; +// bb_needs_update_ = true; +// } + } + + template <typename P> + inline + const P& + p_queue_fast<P>::front() const + { + mln_precondition(! this->is_empty()); + return q_[begin_]; + } + + template <typename P> + inline + const P& + p_queue_fast<P>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + + template <typename P> + inline + void + p_queue_fast<P>::clear() + { + this->end_ = begin_; +// q_.clear(); +// vect_.clear(); +// vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P> + inline + const std::vector<P>& + p_queue_fast<P>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P> + inline + const P& + p_queue_fast<P>::operator[](unsigned i) const + { + mln_precondition(i < npoints()); + return q_[begin_ + i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_P_QUEUE_FAST_HH Index: trunk/milena/sandbox/pellegrin/set/Makefile =================================================================== --- trunk/milena/sandbox/pellegrin/set/Makefile (revision 1787) +++ trunk/milena/sandbox/pellegrin/set/Makefile (revision 1788) @@ -1,26 +1,2 @@ -All_warnings = -ansi -pedantic -Wabi -Wctor-dtor-privacy -Wnon-virtual-dtor \ - -Wreorder -Weffc++ -Wno-deprecated -Wstrict-null-sentinel \ - -Wno-non-template-friend -Wold-style-cast -Woverloaded-virtual \ - -Wno-pmf-conversions -Wsign-promo -fsyntax-only-pedantic-errors \ - -w -Wextra -Wall -Waddress -Waggregate-return -Wno-attributes \ - -Wcast-align -Wcast-qual -Wchar-subscripts -Wcomment -Wconversion \ - -Wno-deprecated-declarations -Wdisabled-optimization -Wno-div-by-zero \ - -Wno-endif-labels -Werror -Wfatal-errors -Wfloat-equal -Wformat \ - -Wformat=2 -Wno-format-extra-args -Wformat-nonliteral \ - -Wformat-security -Wformat-y2k -Wimplicit -Wimport -Wno-import \ - -Winit-self -Winline -Wno-invalid-offsetof -Winvalid-pch \ - -Wlarger-than-1 -Wunsafe-loop-optimizations -Wlong-long \ - -Wmissing-braces -Wmissing-field-initializers \ - -Wmissing-format-attribute -Wmissing-include-dirs -Wmissing-noreturn \ - -Wno-multichar -Wno-overflow -Woverlength-strings -Wpacked -Wpadded \ - -Wparentheses -Wpointer-arith -Wredundant-decls -Wreturn-type \ - -Wsequence-point -Wshadow -Wsign-compare -Wstack-protector \ - -Wstrict-aliasing -Wstrict-overflow -Wswitch -Wswitch-default \ - -Wswitch-enum -Wsystem-headers -Wtrigraphs -Wundef -Wuninitialized \ - -Wunknown-pragmas -Wno-pragmas -Wunreachable-code -Wunused \ - -Wunused-function -Wunused-label -Wunused-parameter -Wunused-value \ - -Wunused-variable -Wvariadic-macros -Wvolatile-register-var \ - -Wwrite-strings \ - all: - g++-4.2 -ansi -pedantic -I../.. first_test.cc -o first_test + g++-4.2 -ansi -pedantic -I../../.. test_has.cc -o test_has Index: trunk/milena/sandbox/pellegrin/set/test_set.cc =================================================================== --- trunk/milena/sandbox/pellegrin/set/test_set.cc (revision 1787) +++ trunk/milena/sandbox/pellegrin/set/test_set.cc (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -27,7 +27,7 @@ /*! \file sandbox/pellegrin/set/test_set.cc * - * \brief test my work on set. + * \brief Test my work on set. */ #include <mln/core/image2d.hh> Index: trunk/milena/sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -27,7 +27,7 @@ /*! \file sandbox/pellegrin/cond_inheritance/test_cond_inherit.cc * - * \brief test my work on conditional inheritance. + * \brief Test my work on conditional inheritance. */ #include <iostream> Index: trunk/milena/sandbox/pellegrin/cond_inheritance/p_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/p_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/p_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -43,9 +43,8 @@ /*! \brief Point set class. * * This is a mathematical uni-set of points. The - * parameter \p P shall be a Point type. + * parameter \p E shall be a Point type. * - * \todo All. */ template <typename E> class p_set: public internal::point_set_base<p_set<E>, E> Index: trunk/milena/sandbox/pellegrin/cond_inheritance/concept/point_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/concept/point_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/concept/point_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 Index: trunk/milena/sandbox/pellegrin/cond_inheritance/p_array.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/p_array.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/p_array.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -43,9 +43,8 @@ /*! \brief Point set class. * * This is a mathematical multi-set of points. The - * parameter \p P shall be a Point type. + * parameter \p E shall be a Point type. * - * \todo All. */ template <typename E> class p_array : public internal::point_set_base<p_array<E>, E> Index: trunk/milena/sandbox/pellegrin/cond_inheritance/internal/multi_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/internal/multi_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/internal/multi_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 Index: trunk/milena/sandbox/pellegrin/cond_inheritance/internal/uni_set.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/internal/uni_set.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/internal/uni_set.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 Index: trunk/milena/sandbox/pellegrin/cond_inheritance/internal/point_set_base.hh =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/internal/point_set_base.hh (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/internal/point_set_base.hh (revision 1788) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 Index: trunk/milena/sandbox/pellegrin/cond_inheritance/Makefile =================================================================== --- trunk/milena/sandbox/pellegrin/cond_inheritance/Makefile (revision 1787) +++ trunk/milena/sandbox/pellegrin/cond_inheritance/Makefile (revision 1788) @@ -1,26 +1,2 @@ -All_warnings = -ansi -pedantic -Wabi -Wctor-dtor-privacy -Wnon-virtual-dtor \ - -Wreorder -Weffc++ -Wno-deprecated -Wstrict-null-sentinel \ - -Wno-non-template-friend -Wold-style-cast -Woverloaded-virtual \ - -Wno-pmf-conversions -Wsign-promo -fsyntax-only-pedantic-errors \ - -w -Wextra -Wall -Waddress -Waggregate-return -Wno-attributes \ - -Wcast-align -Wcast-qual -Wchar-subscripts -Wcomment -Wconversion \ - -Wno-deprecated-declarations -Wdisabled-optimization -Wno-div-by-zero \ - -Wno-endif-labels -Werror -Wfatal-errors -Wfloat-equal -Wformat \ - -Wformat=2 -Wno-format-extra-args -Wformat-nonliteral \ - -Wformat-security -Wformat-y2k -Wimplicit -Wimport -Wno-import \ - -Winit-self -Winline -Wno-invalid-offsetof -Winvalid-pch \ - -Wlarger-than-1 -Wunsafe-loop-optimizations -Wlong-long \ - -Wmissing-braces -Wmissing-field-initializers \ - -Wmissing-format-attribute -Wmissing-include-dirs -Wmissing-noreturn \ - -Wno-multichar -Wno-overflow -Woverlength-strings -Wpacked -Wpadded \ - -Wparentheses -Wpointer-arith -Wredundant-decls -Wreturn-type \ - -Wsequence-point -Wshadow -Wsign-compare -Wstack-protector \ - -Wstrict-aliasing -Wstrict-overflow -Wswitch -Wswitch-default \ - -Wswitch-enum -Wsystem-headers -Wtrigraphs -Wundef -Wuninitialized \ - -Wunknown-pragmas -Wno-pragmas -Wunreachable-code -Wunused \ - -Wunused-function -Wunused-label -Wunused-parameter -Wunused-value \ - -Wunused-variable -Wvariadic-macros -Wvolatile-register-var \ - -Wwrite-strings \ - all: g++-4.2 -ansi -pedantic -I../../.. -I. test_cond_inherit.cc -o test -- Michel PELLEGRIN ÉPITA - CSI 2010