[Olena-patches] milena r1318: Add queue with priority in sandbox

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-11 Guillaume Duhamel &lt;guillaume.duhamel(a)lrde.epita.fr&gt; Add queue with priority in sandbox. * queue_p_priority.cc: New test for queue with priority. * queue_p_priority.hh: New queue with priority. * queue_p_fast.hh, * translate_image.cc, * translate_image.hh, * log.txt: Update. --- log.txt | 9 + queue_p_fast.hh | 1 queue_p_priority.cc | 64 ++++++++++ queue_p_priority.hh | 314 ++++++++++++++++++++++++++++++++++++++++++++++++++++ translate_image.cc | 19 +-- translate_image.hh | 24 +++ 6 files changed, 419 insertions(+), 12 deletions(-) Index: trunk/milena/sandbox/duhamel/queue_p_priority.cc =================================================================== --- trunk/milena/sandbox/duhamel/queue_p_priority.cc (revision 0) +++ trunk/milena/sandbox/duhamel/queue_p_priority.cc (revision 1318) @@ -0,0 +1,64 @@ +#include "queue_p_priority.hh" +#include <mln/core/image2d.hh> + +int main () +{ + using namespace mln; + + mln::queue_p_priority<point2d, unsigned> q; + point2d p1 (1,1); + point2d p2 (1,5); + point2d p3 (2,7); + + mln_assertion (q.empty ()); + + mln_assertion (q.npoints () == 0); + + q.push_force (p3); + q.push_force (p1, 3); + q.push_force (p2, 5); + + + mln_assertion (!q.empty ()); + + mln_assertion (q.has (p1)); + mln_assertion (q.has (p2)); + mln_assertion (q.has (p3)); + + mln_assertion (q.npoints () == 3); + mln_assertion (q.front () == p2); + q.pop (); + + mln_assertion (q.has (p1)); + mln_assertion (!q.has (p2)); + mln_assertion (q.has (p3)); + + mln_assertion (q.npoints () == 2); + mln_assertion (q.front () == p1); + q.pop (); + + mln_assertion (!q.has (p1)); + mln_assertion (!q.has (p2)); + mln_assertion (q.has (p3)); + + mln_assertion (q.npoints () == 1); + mln_assertion (q.front () == p3); + q.pop (); + + mln_assertion (!q.has (p1)); + mln_assertion (!q.has (p2)); + mln_assertion (!q.has (p3)); + mln_assertion (q.npoints () == 0); + + mln_assertion (q.empty ()); + + q.push_force (p3); + q.push_force (p2, 5); + q.push_force (p1, 3); + + mln_assertion (q[0] == p3); + mln_assertion (q[1] == p1); + mln_assertion (q[2] == p2); + q.clear (); + mln_assertion (q.empty ()); +} Index: trunk/milena/sandbox/duhamel/translate_image.hh =================================================================== --- trunk/milena/sandbox/duhamel/translate_image.hh (revision 1317) +++ trunk/milena/sandbox/duhamel/translate_image.hh (revision 1318) @@ -61,6 +61,27 @@ } // end of namespace mln::internal + + namespace trait + { + + template <typename I> + struct image_< translate_image<I> > : default_image_morpher_< I, mln_value(I), + translate_image<I> > + { + + typedef trait::image::category::domain_morpher category; + + typedef mln_trait_image_io_from_(I) io; + + typedef mln_trait_image_data_from_(I) data; + + }; + + } // end of namespace mln::trait + + + /*! \brief FIXME * */ @@ -73,7 +94,6 @@ /// Return type of read-write access. typedef typename internal::morpher_lvalue_<I>::ret lvalue; - /// Skeleton. typedef translate_image< tag::image_<I> > skeleton; @@ -84,7 +104,7 @@ translate_image(I& ima, const mln_dpoint(I) dp); translate_image(); - /// FIXME: Doc! + /// Return domain of translated_image. const box2d& domain() const; /// Test if a pixel value is accessible at \p p. Index: trunk/milena/sandbox/duhamel/queue_p_fast.hh =================================================================== --- trunk/milena/sandbox/duhamel/queue_p_fast.hh (revision 1317) +++ trunk/milena/sandbox/duhamel/queue_p_fast.hh (revision 1318) @@ -124,7 +124,6 @@ mutable accu::bbox<P> bb_; mutable bool bb_needs_update_; void bb_update_() const; - }; Index: trunk/milena/sandbox/duhamel/queue_p_priority.hh =================================================================== --- trunk/milena/sandbox/duhamel/queue_p_priority.hh (revision 0) +++ trunk/milena/sandbox/duhamel/queue_p_priority.hh (revision 1318) @@ -0,0 +1,314 @@ +// 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_QUEUE_P_PRIORITY_HH +# define MLN_CORE_QUEUE_P_PRIORITY_HH + +/*! \file mln/core/queue_p_priority.hh + * + * \brief Definition of a point set class based on std::deque. + */ + +# include <vector> +# include <deque> +# include <map> +# include <algorithm> +# include <iterator> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/core/vec_p_piter.hh> +# include <mln/accu/bbox.hh> +# include <mln/core/queue_p.hh> + +namespace mln +{ + + // Fwd decls. + template <typename P> struct vec_p_fwd_piter_; + template <typename P> struct vec_p_bkd_piter_; + + + /*! \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, typename T> + class queue_p_priority// : public internal::point_set_base_< P, queue_p_priority<P> > + { + public: + + /// Forward Point_Iterator associated type. + typedef vec_p_fwd_piter_<P> fwd_piter; + + /// Backward Point_Iterator associated type. + typedef vec_p_bkd_piter_<P> bkd_piter; + + /// Constructor. + queue_p_priority(); + + /// Test is \p p belongs to this point set. + bool has(const P& p); + + /// Test if queue is empty or not. + bool empty(); + + /// Give the number of points. + unsigned npoints(); + + /// Give the exact bounding box. + const box_<P>& bbox(); + + /// Push force a point \p p in the queue. + queue_p_priority<P, T>& push_force(const P& p, T prio = 0); + + /// Push a point \p p in the queue. + queue_p_priority<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(); + + /// 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); + + protected: + + std::map<const T, queue_p<P> > q_; + + mutable std::vector<P> vect_; + mutable bool vect_needs_update_; + void vect_update_(); + + mutable accu::bbox<P> bb_; + mutable bool bb_needs_update_; + void bb_update_(); + + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T> + queue_p_priority<P, T>::queue_p_priority() + { + } + + template <typename P, typename T> + void + queue_p_priority<P, T>::vect_update_() + { + vect_.clear(); + vect_.reserve(npoints()); + + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + std::copy(q_[(*it).first].begin(), q_[(*it).first].end(), + std::back_inserter(vect_)); + vect_needs_update_ = false; + } + + template <typename P, typename T> + void + queue_p_priority<P, T>::bb_update_() + { + bb_.init(); + + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + for (unsigned i = 0; i < q_[(*it).first].npoints (); ++i) + bb_.take(q_[(*it).first][i]); + } + + + template <typename P, typename T> + bool + queue_p_priority<P, T>::has(const P& p) + { + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (q_[(*it).first].has (p)) + return true; + return false; + } + + template <typename P, typename T> + bool + queue_p_priority<P, T>::empty() + { + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!q_[(*it).first].empty ()) + return false; + return true; + } + + template <typename P, typename T> + unsigned + queue_p_priority<P, T>::npoints() + { + unsigned res = 0; + + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + if (!q_[(*it).first].empty ()) + res += q_[(*it).first].npoints(); + return res; + } + + template <typename P, typename T> + const box_<P>& + queue_p_priority<P, T>::bbox() + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P, typename T> + queue_p_priority<P, T>& + queue_p_priority<P, T>::push_force(const P& p, T prio) + { + q_[prio].push_force (p); + + return *this; + } + + template <typename P, typename T> + queue_p_priority<P, T>& + queue_p_priority<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> + void + queue_p_priority<P, T>::pop() + { + typename std::map<T, queue_p<P> >::const_reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!q_[(*it).first].empty ()) + return q_[(*it).first].pop (); + + if (! vect_needs_update_) + { + vect_needs_update_ = true; + bb_needs_update_ = true; + } + } + + template <typename P, typename T> + const P& + queue_p_priority<P, T>::front() + { + mln_precondition(! q_.empty()); + + typename std::map<T, queue_p<P> >::const_reverse_iterator it = q_.rbegin (); + + for (; it != q_.rend (); ++it) + if (!q_[(*it).first].empty ()) + break; + return q_[(*it).first].front (); + } + + template <typename P, typename T> + void + queue_p_priority<P, T>::clear() + { + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + + for (; it != q_.end (); ++it) + q_[(*it).first].clear (); + q_.clear(); + vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P, typename T> + const std::vector<P>& + queue_p_priority<P, T>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P, typename T> + const P& + queue_p_priority<P, T>::operator[](unsigned i) + { + mln_precondition(i < npoints()); + + typename std::map<T, queue_p<P> >::const_iterator it = q_.begin (); + unsigned cpt = 0; + + for (; it != q_.end (); ++it) + { + if (!q_[(*it).first].empty ()) + for (cpt = 0; cpt < q_[(*it).first].npoints (); ++cpt) + { + if (i == 0) + return q_[(*it).first][cpt]; + --i; + } + } + return q_[(*it).first][cpt]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_QUEUE_P_PRIORITY_HH Index: trunk/milena/sandbox/duhamel/translate_image.cc =================================================================== --- trunk/milena/sandbox/duhamel/translate_image.cc (revision 1317) +++ trunk/milena/sandbox/duhamel/translate_image.cc (revision 1318) @@ -6,7 +6,7 @@ #include <mln/border/fill.hh> #include <mln/debug/println_with_border.hh> #include <mln/debug/println.hh> -#include "translate_image.hh" +#include <mln/core/translate_image.hh> int main () { @@ -31,12 +31,13 @@ std::cout << "translated image :" << std::endl; debug::println (tmp); -// std::cout << std::endl; -// I out (4,4); -// level::paste(ima, out); -// level::paste(tmp, out); -// std::cout << "pasted image :" -// << std::endl; -// debug::println (out); -// std::cout << std::endl; + + std::cout << std::endl; + I out (4,4); + level::paste(ima, out); + level::paste(tmp, out); + std::cout << "pasted image :" + << std::endl; + debug::println (out); + std::cout << std::endl; } Index: trunk/milena/sandbox/duhamel/log.txt =================================================================== --- trunk/milena/sandbox/duhamel/log.txt (revision 1317) +++ trunk/milena/sandbox/duhamel/log.txt (revision 1318) @@ -13,3 +13,12 @@ - mesh_p / mesh_image - draw mesh - graph_labeling + +- show/display. + +- Add translate image class. +- Add convert/to_tiles. + +- border/resize. + +- queue with priority.