[Olena-patches] milena r1225: Add queue_p_fast

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-03 Guillaume Duhamel &lt;guillaume.duhamel(a)lrde.epita.fr&gt; Add queue_p_fast. * queue_p_fast.hh: New queue with vector. Update * labeling_algo.cc, * labeling_algo.hh: Update. --- labeling_algo.cc | 7 - labeling_algo.hh | 100 +++---------------- queue_p_fast.hh | 276 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 301 insertions(+), 82 deletions(-) Index: trunk/milena/sandbox/duhamel/labeling_algo.cc =================================================================== --- trunk/milena/sandbox/duhamel/labeling_algo.cc (revision 1224) +++ trunk/milena/sandbox/duhamel/labeling_algo.cc (revision 1225) @@ -42,6 +42,7 @@ # include <mln/labeling/foreground.hh> # include <mln/debug/println.hh> # include <mln/debug/println_with_border.hh> +# include <mln/draw/mesh.hh> # include "labeling_algo.hh" int main() @@ -69,14 +70,16 @@ image2d_b<int_u8> inte2(inte.domain()); + // level::fill(inte2, inte); + level::saturate(inte, 1, 255, inte2); io::pgm::save(inte2, "inte.pgm"); - debug::println_with_border(inte2); + // debug::println_with_border(inte2); mesh_p<point2d> m = make::graph_with_no_border(inte2, c4()); std::cout << "OK" << std::endl; draw::mesh (out, m, 255, 128); - debug::println(out); + // debug::println(out); io::pgm::save(out, "out.pgm"); } Index: trunk/milena/sandbox/duhamel/queue_p_fast.hh =================================================================== --- trunk/milena/sandbox/duhamel/queue_p_fast.hh (revision 0) +++ trunk/milena/sandbox/duhamel/queue_p_fast.hh (revision 1225) @@ -0,0 +1,276 @@ +// 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_FAST_HH +# define MLN_CORE_QUEUE_P_FAST_HH + +/*! \file mln/core/queue_p_fast.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/vec_p_piter.hh> +# include <mln/accu/bbox.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> + class queue_p_fast : public internal::point_set_base_< P, queue_p_fast<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_fast(); + + /// 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; + + /// 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. + queue_p_fast<P>& push_force(const P& p); + + /// Push a point \p p in the queue. + queue_p_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; + + /// 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> + queue_p_fast<P>::queue_p_fast() + { + // vect_needs_update_ = false; + bb_needs_update_ = false; + begin_ = 0; + end_ = 0; + } + + template <typename P> + void + queue_p_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> + void + queue_p_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> + bool + queue_p_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> + bool + queue_p_fast<P>::empty() const + { + return (this->begin_ == this->end_); + } + + template <typename P> + std::size_t + queue_p_fast<P>::npoints() const + { + mln_precondition(this->end_ >= this->begin_); + return (this->end_ - this->begin_); + } + + template <typename P> + const box_<P>& + queue_p_fast<P>::bbox() const + { + mln_precondition(npoints() != 0); + if (bb_needs_update_) + bb_update_(); + return bb_.to_result(); + } + + template <typename P> + queue_p_fast<P>& + queue_p_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> + queue_p_fast<P>& + queue_p_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> + void + queue_p_fast<P>::pop() + { + ++this->begin_; +// q_.pop_front(); +// if (! vect_needs_update_) +// { +// vect_needs_update_ = true; +// bb_needs_update_ = true; +// } + } + + template <typename P> + const P& + queue_p_fast<P>::front() const + { + mln_precondition(! this->empty()); + return q_[begin_]; + } + + template <typename P> + void + queue_p_fast<P>::clear() + { + this->end_ = begin_; +// q_.clear(); +// vect_.clear(); +// vect_needs_update_ = false; + bb_needs_update_ = false; + } + + template <typename P> + const std::vector<P>& + queue_p_fast<P>::vect() const + { + if (vect_needs_update_) + vect_update_(); + return vect_; + } + + template <typename P> + const P& + queue_p_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_QUEUE_P_FAST_HH Index: trunk/milena/sandbox/duhamel/labeling_algo.hh =================================================================== --- trunk/milena/sandbox/duhamel/labeling_algo.hh (revision 1224) +++ trunk/milena/sandbox/duhamel/labeling_algo.hh (revision 1225) @@ -1,4 +1,5 @@ # include <mln/core/queue_p.hh> +# include "queue_p_fast.hh" # include <mln/core/clone.hh> # include <mln/debug/println.hh> @@ -11,9 +12,6 @@ #include <mln/debug/println.hh> #include <mln/util/graph.hh> #include <mln/core/mesh_p.hh> -#include <mln/core/mesh_psite.hh> -#include <mln/draw/mesh.hh> -#include <mln/core/mesh_image.hh> #include <mln/accu/mean.hh> #include <mln/estim/min_max.hh> #include <algorithm> @@ -67,21 +65,16 @@ const Neighborhood<N>& nbh) { typedef metal::vec<2,float> X; - typedef mln_value(I) V; typedef mln_psite(I) P; I& ima = exact(ima_); util::graph<void> gr; - V min, max; estim::min_max (ima, min, max); unsigned nb = max - min + 1; std::vector<P> v(nb); - std::vector< accu::mean_< metal::vec<2,float> > > tab_mean (nb); - - std::cout << "nb = " << nb << std::endl; - + std::vector< accu::mean_< X > > tab_mean (nb); std::map<std::pair<V, V>, bool> m; mln_piter(I) p(ima.domain()); @@ -96,36 +89,16 @@ m[std::pair<V, V>(ima(p) - min, ima(n) - min)] = true; } - std::cout << "center[0] = " << tab_mean[0].to_result() << std::endl; - std::cout << "center[1] = " << tab_mean[1].to_result() << std::endl; - -// /// test -// v[0] = (make::point2d (0, 0)); -// v[1] = (make::point2d (5, 1)); -// v[2] = (make::point2d (9, 2)); -// v[3] = (make::point2d (0, 6)); -// v[4] = (make::point2d (6, 5)); -// v[5] = (make::point2d (8, 7)); - - for (unsigned i = min; i <= max; ++i) { gr.add_node (); -// std::cout << tab_mean[i].to_result ()[0] -// << std::endl; - v[i - min] = make::point2d ((unsigned)tab_mean[i].to_result ()[1], (unsigned)tab_mean[i].to_result ()[0]); + v[i - min] = make::point2d ((unsigned)tab_mean[i].to_result ()[0], + (unsigned)tab_mean[i].to_result ()[1]); } typename std::map<std::pair<V, V>, bool>::const_iterator it = m.begin (); for (; it != m.end (); ++it) - { -// gr.print_debug (); -// std::cout << "t1 = " << (*it).first.first << std::endl -// << "t2 = " << (*it).first.second << std::endl -// << std::endl; - gr.add_edge((*it).first.first, (*it).first.second); - } mesh_p<P> res(gr, v); return res; @@ -242,59 +215,26 @@ } } } - return out; - } - - template <typename I, typename N> - I - make_algo_debug2 (Image<I>& ima_, - const Neighborhood<N>& nbh) - { - I& ima = exact(ima_); - I out = clone(ima_); - queue_p<mln_psite(I)> q; - - // Init. - { - mln_piter(I) p(ima.domain()); - mln_niter(N) n(nbh, p); - - for_all(p) if (ima(p) == 0) - for_all(n) if (ima(n) != 0) - { - std::cout << "push : " << p << std::endl; - q.push(p); - break; - } - std::cout << "init => q has " << q.npoints() << " points" - << std::endl; - } +// // Body: alternative version. +// { +// while (! q.empty()) +// { +// mln_psite(I) p = q.front(); +// q.pop(); +// if (out(p) != 0) // p has already been processed so ignore +// continue; - // Body. - { - while (! q.empty()) - { - debug::println(out); - mln_psite(I) p = q.front(); - std::cout << "pop : " << p << std::endl; - q.pop(); - mln_invariant(ima(p) == 0); +// mln_niter(N) n(nbh, p); +// for_all(n) if (ima.has(n)) +// if (out(n) != 0) +// out(p) = out(n); +// else +// q.push_force(n); // n may already be in the queue, +// // yet we then queue again this psite +// } - mln_niter(N) n(nbh, p); - for_all(n) if (ima.has(n)) - if (out(n) != 0) - out(p) = out(n); - else - if (! q.has(n)) - { - std::cout << "push : " << n << std::endl; - q.push(n); - } - } - } return out; } - } // end of mln