URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-11-13 Guillaume Duhamel <guillaume.duhamel@lrde.epita.fr> Fix queue : rename empty in is_empty and add method pop_front. Rename empty in is_empty and add method pop_front, which return the front element and pop the queue. * mln/core/p_priority_queue.hh, * mln/core/p_priority_queue_fast.hh, * mln/core/p_queue.hh, * mln/core/p_queue_fast.hh: Update this modification. Update with these modifications. * mln/geom/seeds2tiling.hh, * mln/geom/seeds2tiling_with_chamfer.hh, * tests/core_p_priority_queue.cc, * tests/core_p_priority_queue_fast.cc: Update. --- mln/core/p_priority_queue.hh | 69 ++++++++++++++++++++-------------- mln/core/p_priority_queue_fast.hh | 29 ++++++++++---- mln/core/p_queue.hh | 19 ++++++++- mln/core/p_queue_fast.hh | 22 +++++++++- mln/geom/seeds2tiling.hh | 4 - mln/geom/seeds2tiling_with_chamfer.hh | 2 tests/core_p_priority_queue.cc | 10 ++-- tests/core_p_priority_queue_fast.cc | 8 +-- 8 files changed, 112 insertions(+), 51 deletions(-) Index: trunk/milena/tests/core_p_priority_queue.cc =================================================================== --- trunk/milena/tests/core_p_priority_queue.cc (revision 1469) +++ trunk/milena/tests/core_p_priority_queue.cc (revision 1470) @@ -37,12 +37,12 @@ { using namespace mln; - mln::p_priority_queue<point2d, unsigned> q; + p_priority_queue<point2d, unsigned> q; point2d p1 (6, 9); point2d p2 (5, 1); point2d p3 (4, 2); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); mln_assertion (q.npoints () == 0); @@ -53,7 +53,7 @@ std::cout << q.bbox () << std::endl; std::cout << q << std::endl; - mln_assertion (!q.empty ()); + mln_assertion (!q.is_empty ()); mln_assertion (q.has (p1)); mln_assertion (q.has (p2)); @@ -84,7 +84,7 @@ mln_assertion (!q.has (p3)); mln_assertion (q.npoints () == 0); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); q.push_force (p3); q.push_force (p2, 5); @@ -94,5 +94,5 @@ mln_assertion (q[1] == p1); mln_assertion (q[0] == p2); q.clear (); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); } Index: trunk/milena/tests/core_p_priority_queue_fast.cc =================================================================== --- trunk/milena/tests/core_p_priority_queue_fast.cc (revision 1469) +++ trunk/milena/tests/core_p_priority_queue_fast.cc (revision 1470) @@ -42,7 +42,7 @@ point2d p2 (5, 1); point2d p3 (4, 2); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); mln_assertion (q.npoints () == 0); @@ -53,7 +53,7 @@ std::cout << q.bbox () << std::endl; std::cout << q << std::endl; - mln_assertion (!q.empty ()); + mln_assertion (!q.is_empty ()); mln_assertion (q.has (p1)); mln_assertion (q.has (p2)); @@ -84,7 +84,7 @@ mln_assertion (!q.has (p3)); mln_assertion (q.npoints () == 0); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); q.push_force (p3); q.push_force (p2, 5); @@ -94,5 +94,5 @@ mln_assertion (q[1] == p1); mln_assertion (q[0] == p2); q.clear (); - mln_assertion (q.empty ()); + mln_assertion (q.is_empty ()); } Index: trunk/milena/mln/core/p_queue.hh =================================================================== --- trunk/milena/mln/core/p_queue.hh (revision 1469) +++ trunk/milena/mln/core/p_queue.hh (revision 1470) @@ -80,7 +80,7 @@ bool has(const P& p) const; /// Test if queue is empty or not. - bool empty() const; + bool is_empty() const; /// Give the number of points. std::size_t npoints() const; @@ -102,6 +102,11 @@ /// 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(); @@ -169,7 +174,7 @@ template <typename P> bool - p_queue<P>::empty() const + p_queue<P>::is_empty() const { return (q_.empty()); } @@ -234,6 +239,16 @@ } template <typename P> + const P& + p_queue<P>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P> void p_queue<P>::clear() { Index: trunk/milena/mln/core/p_priority_queue_fast.hh =================================================================== --- trunk/milena/mln/core/p_priority_queue_fast.hh (revision 1469) +++ trunk/milena/mln/core/p_priority_queue_fast.hh (revision 1470) @@ -82,7 +82,7 @@ bool has(const P& p) const; /// Test if queue is empty or not. - bool empty() const; + bool is_empty() const; /// Give the number of points. unsigned npoints() const; @@ -104,6 +104,11 @@ /// 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(); @@ -182,12 +187,12 @@ template <typename P, typename T> bool - p_priority_queue_fast<P, T>::empty() const + 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.empty ()) + if (!(*it).second.is_empty ()) return false; return true; } @@ -201,7 +206,7 @@ typename std::map<T, p_queue_fast<P> >::const_iterator it = q_.begin (); for (; it != q_.end (); ++it) - if (!(*it).second.empty ()) + if (!(*it).second.is_empty ()) res += (*it).second.npoints(); return res; } @@ -246,7 +251,7 @@ typename std::map<T, p_queue_fast<P> >::reverse_iterator it = q_.rbegin (); for (; it != q_.rend (); ++it) - if (!(*it).second.empty ()) + if (!(*it).second.is_empty ()) return (*it).second.pop (); if (! vect_needs_update_) @@ -265,12 +270,22 @@ typename std::map<T, p_queue_fast<P> >::const_reverse_iterator it = q_.rbegin (); for (; it != q_.rend (); ++it) - if (!(*it).second.empty ()) + if (!(*it).second.is_empty ()) break; return (*it).second.front (); } template <typename P, typename T> + const P& + p_priority_queue_fast<P, T>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P, typename T> void p_priority_queue_fast<P, T>::clear() { @@ -303,7 +318,7 @@ for (; it != q_.rend (); ++it) { - if (!(*it).second.empty ()) + if (!(*it).second.is_empty ()) for (cpt = 0; cpt < (*it).second.npoints (); ++cpt) { if (i == 0) Index: trunk/milena/mln/core/p_priority_queue.hh =================================================================== --- trunk/milena/mln/core/p_priority_queue.hh (revision 1469) +++ trunk/milena/mln/core/p_priority_queue.hh (revision 1470) @@ -28,7 +28,7 @@ #ifndef MLN_CORE_QUEUE_P_PRIORITY_HH # define MLN_CORE_QUEUE_P_PRIORITY_HH -/*! \file mln/core/p_queue_priority.hh +/*! \file mln/core/p_priority_queue.hh * * \brief Definition of a point set class based on p_queue with * priority features. @@ -65,7 +65,7 @@ * a call to npoints() when this container is multiple. */ template <typename P, typename T> - class p_queue_priority : public internal::point_set_base_< P, p_queue_priority<P, T> > + class p_priority_queue : public internal::point_set_base_< P, p_priority_queue<P, T> > { public: @@ -76,13 +76,13 @@ typedef p_array_bkd_piter_<P> bkd_piter; /// Constructor. - p_queue_priority(); + 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 empty() const; + bool is_empty() const; /// Give the number of points. unsigned npoints() const; @@ -91,10 +91,10 @@ const box_<P>& bbox() const; /// Push force a point \p p in the queue. - p_queue_priority<P, T>& push_force(const P& p, T prio = 0); + p_priority_queue<P, T>& push_force(const P& p, T prio = 0); /// Push a point \p p in the queue. - p_queue_priority<P, T>& push(const P& p, T prio = 0); + 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. @@ -104,6 +104,11 @@ /// 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(); @@ -132,7 +137,7 @@ # ifndef MLN_INCLUDE_ONLY template <typename P, typename T> - p_queue_priority<P, T>::p_queue_priority() + p_priority_queue<P, T>::p_priority_queue() { vect_needs_update_ = false; bb_needs_update_ = false; @@ -140,7 +145,7 @@ template <typename P, typename T> void - p_queue_priority<P, T>::vect_update_() const + p_priority_queue<P, T>::vect_update_() const { vect_.clear(); vect_.reserve(npoints()); @@ -155,7 +160,7 @@ template <typename P, typename T> void - p_queue_priority<P, T>::bb_update_() const + p_priority_queue<P, T>::bb_update_() const { bb_.init(); @@ -170,7 +175,7 @@ template <typename P, typename T> bool - p_queue_priority<P, T>::has(const P& p) const + p_priority_queue<P, T>::has(const P& p) const { typename std::map<T, p_queue<P> >::const_iterator it = q_.begin (); @@ -182,33 +187,33 @@ template <typename P, typename T> bool - p_queue_priority<P, T>::empty() const + 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.empty ()) + if (!(*it).second.is_empty ()) return false; return true; } template <typename P, typename T> unsigned - p_queue_priority<P, T>::npoints() const + 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.empty ()) + if (!(*it).second.is_empty ()) res += (*it).second.npoints(); return res; } template <typename P, typename T> const box_<P>& - p_queue_priority<P, T>::bbox() const + p_priority_queue<P, T>::bbox() const { mln_precondition(npoints() != 0); if (bb_needs_update_) @@ -217,8 +222,8 @@ } template <typename P, typename T> - p_queue_priority<P, T>& - p_queue_priority<P, T>::push_force(const P& p, T prio) + 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_) @@ -230,8 +235,8 @@ } template <typename P, typename T> - p_queue_priority<P, T>& - p_queue_priority<P, T>::push(const P& p, T prio) + 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); @@ -241,12 +246,12 @@ template <typename P, typename T> void - p_queue_priority<P, T>::pop() + 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.empty ()) + if (!(*it).second.is_empty ()) return (*it).second.pop (); if (! vect_needs_update_) @@ -258,21 +263,31 @@ template <typename P, typename T> const P& - p_queue_priority<P, T>::front() const + 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.empty ()) + if (!(*it).second.is_empty ()) break; return (*it).second.front (); } template <typename P, typename T> + const P& + p_priority_queue<P, T>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + template <typename P, typename T> void - p_queue_priority<P, T>::clear() + p_priority_queue<P, T>::clear() { typename std::map<T, p_queue<P> >::iterator it = q_.begin (); @@ -285,7 +300,7 @@ template <typename P, typename T> const std::vector<P>& - p_queue_priority<P, T>::vect() const + p_priority_queue<P, T>::vect() const { if (vect_needs_update_) vect_update_(); @@ -294,7 +309,7 @@ template <typename P, typename T> const P& - p_queue_priority<P, T>::operator[](unsigned i) const + p_priority_queue<P, T>::operator[](unsigned i) const { mln_precondition(i < npoints()); @@ -303,7 +318,7 @@ for (; it != q_.rend (); ++it) { - if (!(*it).second.empty ()) + if (!(*it).second.is_empty ()) for (cpt = 0; cpt < (*it).second.npoints (); ++cpt) { if (i == 0) Index: trunk/milena/mln/core/p_queue_fast.hh =================================================================== --- trunk/milena/mln/core/p_queue_fast.hh (revision 1469) +++ trunk/milena/mln/core/p_queue_fast.hh (revision 1470) @@ -81,7 +81,7 @@ bool has(const P& p) const; /// Test if queue is empty or not. - bool empty() const; + bool is_empty() const; /// Give the number of points. std::size_t npoints() const; @@ -103,6 +103,11 @@ /// 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(); @@ -173,7 +178,7 @@ template <typename P> bool - p_queue_fast<P>::empty() const + p_queue_fast<P>::is_empty() const { return (this->begin_ == this->end_); } @@ -236,11 +241,22 @@ const P& p_queue_fast<P>::front() const { - mln_precondition(! this->empty()); + mln_precondition(! this->is_empty()); return q_[begin_]; } template <typename P> + const P& + p_queue_fast<P>::pop_front() + { + const P& res = this->front(); + + this->pop(); + return res; + } + + + template <typename P> void p_queue_fast<P>::clear() { Index: trunk/milena/mln/geom/seeds2tiling.hh =================================================================== --- trunk/milena/mln/geom/seeds2tiling.hh (revision 1469) +++ trunk/milena/mln/geom/seeds2tiling.hh (revision 1470) @@ -78,7 +78,7 @@ // // Body. // { -// while (! q.empty()) +// while (! q.is_empty()) // { // mln_psite(I) p = q.front(); // q.pop(); @@ -96,7 +96,7 @@ // Body: alternative version. { - while (! q.empty()) + while (! q.is_empty()) { mln_psite(I) p = q.front(); q.pop(); Index: trunk/milena/mln/geom/seeds2tiling_with_chamfer.hh =================================================================== --- trunk/milena/mln/geom/seeds2tiling_with_chamfer.hh (revision 1469) +++ trunk/milena/mln/geom/seeds2tiling_with_chamfer.hh (revision 1470) @@ -80,7 +80,7 @@ // Body: alternative version. { - while (! q.empty()) + while (! q.is_empty()) { mln_psite(I) p = q.front(); q.pop();