[Olena-patches] olena-2.0-163-gc328f24 Improve hqueue used in compute_tree_of_shapes.

* mln/util/hqueue.hh: Remove. * mln/world/kn/internal/hqueue.hh, * mln/world/kn/internal/queue.hh: New. * mln/world/kn/compute_tree_of_shapes.hh: Update use of hqueue. Set l_inf. --- milena/ChangeLog | 12 ++ milena/mln/util/hqueue.hh | 163 ------------------- milena/mln/world/kn/compute_tree_of_shapes.hh | 53 ++++--- milena/mln/world/kn/internal/hqueue.hh | 165 ++++++++++++++++++++ .../kn/internal/{domain_from_k0.hh => queue.hh} | 113 +++++++++----- 5 files changed, 277 insertions(+), 229 deletions(-) delete mode 100644 milena/mln/util/hqueue.hh create mode 100644 milena/mln/world/kn/internal/hqueue.hh copy milena/mln/world/kn/internal/{domain_from_k0.hh => queue.hh} (53%) diff --git a/milena/ChangeLog b/milena/ChangeLog index e1d6e5f..39b1c71 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,17 @@ 2012-10-29 Guillaume Lazzara <z@lrde.epita.fr> + Improve hqueue used in compute_tree_of_shapes. + + * mln/util/hqueue.hh: Remove. + + * mln/world/kn/internal/hqueue.hh, + * mln/world/kn/internal/queue.hh: New. + + * mln/world/kn/compute_tree_of_shapes.hh: Update use of + hqueue. Set l_inf. + +2012-10-29 Guillaume Lazzara <z@lrde.epita.fr> + * mln/world/kn/compute_tree_of_shapes.hh: Make p_inf an argument to this routine. diff --git a/milena/mln/util/hqueue.hh b/milena/mln/util/hqueue.hh deleted file mode 100644 index 9485827..0000000 --- a/milena/mln/util/hqueue.hh +++ /dev/null @@ -1,163 +0,0 @@ -// Copyright (C) 2012 EPITA Research and Development Laboratory (LRDE) -// -// This file is part of Olena. -// -// Olena is free software: you can redistribute it and/or modify it under -// the terms of the GNU General Public License as published by the Free -// Software Foundation, version 2 of the License. -// -// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. -// -// As a special exception, you may use this file as part of a free -// software project without restriction. Specifically, if other files -// instantiate templates or use macros or inline functions from this -// file, or you compile this file and link it with other files to produce -// an executable, this file does not by itself cause the resulting -// executable to be covered by the GNU General Public License. This -// exception does not however invalidate any other reasons why the -// executable file might be covered by the GNU General Public License. - -#ifndef MLN_UTIL_HQUEUE_HH -# define MLN_UTIL_HQUEUE_HH - -/// \file -/// \brief Class for hierarchical queues. - - -# include <cstdlib> -# include <iostream> -# include <vector> -# include <queue> - - -namespace mln -{ - - namespace util - { - - /// \brief Class for hierarchical queues. - template <typename T, typename P> - class hqueue - { - public: - hqueue(); - hqueue(const value::interval<P>& inter); - hqueue(const P& first, const P& last); - - unsigned size() const; - - bool is_empty_at(const P& bucket) const; - bool is_not_empty_at(const P& bucket) const; - -// const std::queue<T>& operator[](const P& bucket) const; - - void push(const T& t, const P& bucket); - T pop(const P& bucket); - - private: - std::vector<std::queue<T> > v_; - unsigned head_; - value::interval<P> inter_; - }; - - -# ifndef MLN_INCLUDE_ONLY - - - template <typename T, typename P> - hqueue<T,P>::hqueue() - { - head_ = 0; - } - - template <typename T, typename P> - hqueue<T,P>::hqueue(const value::interval<P>& inter) - { - inter_ = inter; - v_.resize(inter.nelements()); - head_ = 0; - } - - template <typename T, typename P> - hqueue<T,P>::hqueue(const P& first, const P& last) - { - inter_ = value::interval<P>(first, last); - v_.resize(inter_.nelements()); - head_ = 0; - } - - template <typename T, typename P> - unsigned - hqueue<T,P>::size() const - { - mln_precondition(head_ <= v_.size()); - return v_.size() - head_; - } - - template <typename T, typename P> - bool - hqueue<T,P>::is_empty_at(const P& bucket) const - { - return v_[inter_.index_of(bucket)].empty() == 0; - } - - template <typename T, typename P> - bool - hqueue<T,P>::is_not_empty_at(const P& bucket) const - { - return ! is_empty_at(bucket); - } - - // template <typename T, typename P> - // const std::queue<T>& - // hqueue<T,P>::operator[](const P& i) const - // { - // mln_precondition(i < this->size()); - // return v_[head_ + i]; - // } - - template <typename T, typename P> - void - hqueue<T,P>::push(const T& t, const P& bucket) - { - v_[inter_.index_of(bucket)].push(t); - } - - template <typename T, typename P> - T - hqueue<T,P>::pop(const P& bucket) - { - mln_precondition(!is_empty_at(bucket)); - mln_precondition(bucket < v_.size()); - T front = v_[bucket].front(); - v_[bucket].pop(); - return front; - } - - - template <typename T, typename P> - std::ostream& - operator<<(std::ostream& ostr, const hqueue<T,P>& q) - { - unsigned n = q.size(); - ostr << '('; - for (unsigned i = 0; i < n; ++i) - ostr << q.v_[i] << (i + 1 == n ? "" : ", "); - return ostr << ')'; - } - - -# endif // ! MLN_INCLUDE_ONLY - - } // end of namespace mln::util - -} // end of namespace mln - -#endif // ! MLN_UTIL_HQUEUE_HH diff --git a/milena/mln/world/kn/compute_tree_of_shapes.hh b/milena/mln/world/kn/compute_tree_of_shapes.hh index 795eceb..d6a5984 100644 --- a/milena/mln/world/kn/compute_tree_of_shapes.hh +++ b/milena/mln/world/kn/compute_tree_of_shapes.hh @@ -41,7 +41,7 @@ # include <mln/value/interval.hh> # include <mln/value/is_degenerated.hh> -# include <mln/util/hqueue.hh> +# include <mln/world/kn/internal/hqueue.hh> # include <mln/util/tree_of_shapes.hh> # include <mln/world/kn/is_2_face.hh> @@ -70,13 +70,13 @@ namespace mln template <typename I, typename IV> util::tree_of_shapes<I> compute_tree_of_shapes(const Image<I>& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf); + const mln_site(I)& p_infty); /// \overload template <typename I, typename IV, typename U> util::tree_of_shapes<I> compute_tree_of_shapes(const Image<I>& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, const U& value); + const mln_site(I)& p_infty, const U& value); # ifndef MLN_INCLUDE_ONLY @@ -95,18 +95,18 @@ namespace mln typedef mln_ch_value(I,P) T; typedef mln_ch_value(I,unsigned) U; typedef std::vector<P> Array_P; - typedef util::hqueue<P,EV> q_type; + typedef world::kn::internal::hqueue<P,EV> q_type; compute_tree_of_shapes_t(); util::tree_of_shapes<I> operator()(const I& F_, const value::interval<IV>& inter, - const mln_site(I)& p_inf); + const mln_site(I)& p_infty); template <typename L> util::tree_of_shapes<I> operator()(const I& F_, const value::interval<IV>& inter, - const mln_site(I)& p_inf, + const mln_site(I)& p_infty, const L& l_inf); void do_union(P p_, P r_, T& zpar, U& rank, U& last); @@ -134,7 +134,7 @@ namespace mln mln_equiv(V) lcur; P undef; - P p_inf_; + P p_infty_; unsigned N; box2d D; @@ -254,7 +254,7 @@ namespace mln for (; l_ < inter_.last(); value::inc(l_)) { - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -263,7 +263,7 @@ namespace mln // Avoid overflow on last element. if (l_ == inter_.last()) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -280,7 +280,7 @@ namespace mln EV l_ = lcur; for (; l_ > inter_.first(); value::dec(l_)) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -288,7 +288,7 @@ namespace mln // Avoid overflow on first element. if (l_ == inter_.first()) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -382,9 +382,8 @@ namespace mln // p is in queue if p is 'deja_vu' but not 'done' } unsigned i = 0; - lcur = safe_cast_to<EV>(F(p_inf_)); // the start level is the one of root - priority_push(q, p_inf_, F); // realize push(q[lcur], p_inf_) - deja_vu(p_inf_) = true; + priority_push(q, p_infty_, F); // realize push(q[lcur], p_infty_) + deja_vu(p_infty_) = true; do { P p = priority_pop(q); @@ -479,15 +478,16 @@ namespace mln util::tree_of_shapes<I> compute_tree_of_shapes_t<I,IV>::operator()(const I& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf) + const mln_site(I)& p_infty) { mln_precondition(F.is_valid()); - mln_precondition(value::is_degenerated(F(p_inf))); + mln_precondition(value::is_degenerated(F(p_infty))); N = F.nsites(); D = F.domain(); inter_ = inter; - p_inf_ = p_inf; + p_infty_ = p_infty; + lcur = safe_cast_to<EV>(F(p_infty_)); // the start level is the one of root util::tree_of_shapes<I> t; @@ -506,16 +506,17 @@ namespace mln util::tree_of_shapes<I> compute_tree_of_shapes_t<I,IV>::operator()(const I& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, + const mln_site(I)& p_infty, const L& l_inf) { mln_precondition(F.is_valid()); - mln_precondition(F(p_inf).has(l_inf)); + mln_precondition(F(p_infty).has(l_inf)); N = F.nsites(); D = F.domain(); inter_ = inter; - p_inf_ = p_inf; + p_infty_ = p_infty; + lcur = safe_cast_to<EV>(l_inf); // the start level is the one of root util::tree_of_shapes<I> t; @@ -535,16 +536,16 @@ namespace mln template <typename I, typename IV> util::tree_of_shapes<I> compute_tree_of_shapes(const Image<I>& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf) + const mln_site(I)& p_infty) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(exact(F).is_valid()); typedef mln_value(I) V; mlc_is_a(V, value::interval)::check(); - mln_precondition(value::is_degenerated(exact(F)(p_inf))); + mln_precondition(value::is_degenerated(exact(F)(p_infty))); util::tree_of_shapes<I> - t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf); + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_infty); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; @@ -553,16 +554,16 @@ namespace mln template <typename I, typename IV, typename U> util::tree_of_shapes<I> compute_tree_of_shapes(const Image<I>& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, const U& l_inf) + const mln_site(I)& p_infty, const U& l_inf) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(exact(F).is_valid()); typedef mln_value(I) V; mlc_is_a(V, value::interval)::check(); - mln_precondition(F(p_inf).has(l_inf)); + mln_precondition(F(p_infty).has(l_inf)); util::tree_of_shapes<I> - t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf, l_inf); + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_infty, l_inf); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; diff --git a/milena/mln/world/kn/internal/hqueue.hh b/milena/mln/world/kn/internal/hqueue.hh new file mode 100644 index 0000000..fe29376 --- /dev/null +++ b/milena/mln/world/kn/internal/hqueue.hh @@ -0,0 +1,165 @@ +// Copyright (C) 2012 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_WORLD_KN_INTERNAL_HQUEUE_HH +# define MLN_WORLD_KN_INTERNAL_HQUEUE_HH + +/// \file +/// \brief Class for hierarchical queues. + + +# include <iostream> +# include <vector> +# include <mln/world/kn/internal/queue.hh> + +namespace mln +{ + + namespace world + { + + namespace kn + { + + namespace internal + { + + /// \internal + /// \brief Class for hierarchical queues. + template <typename T, typename P> + class hqueue + { + public: + hqueue(); + hqueue(const value::interval<P>& inter); + hqueue(const P& first, const P& last); + + unsigned nelements() const; + + bool is_empty() const; + bool is_empty_at(const P& bucket) const; + + void push(const T& t, const P& bucket); + T pop(const P& bucket); + + // FIXME: add some reserve strategies... + + private: + std::vector< internal::queue_<T> > v_; + value::interval<P> inter_; + unsigned n_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename T, typename P> + hqueue<T,P>::hqueue() + { + n_ = 0; + } + + template <typename T, typename P> + hqueue<T,P>::hqueue(const value::interval<P>& inter) + { + v_.resize(inter.nelements()); + inter_ = inter; + n_ = 0; + } + + template <typename T, typename P> + hqueue<T,P>::hqueue(const P& first, const P& last) + { + v_.resize(inter_.nelements()); + inter_ = value::interval<P>(first, last); + n_ = 0; + } + + template <typename T, typename P> + unsigned + hqueue<T,P>::nelements() const + { + return n_; + } + + template <typename T, typename P> + bool + hqueue<T,P>::is_empty_at(const P& bucket) const + { + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + return v_[i].is_empty(); + } + + template <typename T, typename P> + bool + hqueue<T,P>::is_empty() const + { + return n_ == 0; + } + + template <typename T, typename P> + void + hqueue<T,P>::push(const T& t, const P& bucket) + { + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + v_[i].push(t); + } + + template <typename T, typename P> + T + hqueue<T,P>::pop(const P& bucket) + { + mln_precondition(! is_empty_at(bucket)); + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + return v_[i].pop(); + } + + // template <typename T, typename P> + // std::ostream& + // operator<<(std::ostream& ostr, const hqueue<T,P>& q) + // { + // unsigned n = q.size(); + // ostr << '('; + // for (unsigned i = 0; i < n; ++i) + // ostr << q.v_[i] << (i + 1 == n ? "" : ", "); + // return ostr << ')'; + // } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::world::kn::internal + + } // end of namespace mln::world::kn + + } // end of namespace mln::world + +} // end of namespace mln + +#endif // ! MLN_WORLD_KN_INTERNAL_HQUEUE_HH diff --git a/milena/mln/world/kn/internal/domain_from_k0.hh b/milena/mln/world/kn/internal/queue.hh similarity index 53% copy from milena/mln/world/kn/internal/domain_from_k0.hh copy to milena/mln/world/kn/internal/queue.hh index 1950280..6a3fbe5 100644 --- a/milena/mln/world/kn/internal/domain_from_k0.hh +++ b/milena/mln/world/kn/internal/queue.hh @@ -23,16 +23,16 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. +#ifndef MLN_WORLD_KN_INTERNAL_QUEUE_HH +# define MLN_WORLD_KN_INTERNAL_QUEUE_HH + /// \file -/// -/// \brief Return the equivalent domain in Kn from a domain in -/// K0. +/// \brief Class for hierarchical queues. + + +# include <vector> -#ifndef MLN_WORLD_KN_DOMAIN_FROM_K0_HH -# define MLN_WORLD_KN_DOMAIN_FROM_K0_HH -# include <mln/core/concept/box.hh> -# include <mln/world/kn/internal/immerse_point.hh> namespace mln { @@ -46,51 +46,86 @@ namespace mln namespace internal { - /// \brief Return the equivalent domain in Kn from a domain in - /// K0. - template <typename B> - B - domain_from_k0(const Box<B>& b, const unsigned n, - unsigned inner_border_thickness); + /// \internal + /// \brief Classical queue structure. + template <typename T> + struct queue_ + { + queue_(); + + void reserve(unsigned n); + + unsigned nelements() const; + bool is_empty() const; - /// \overload - /// \p inner_border_thickness is set to 0. - template <typename B> - B - domain_from_k0(const Box<B>& b, const unsigned n); + const T& operator[](unsigned i) const; + + void push(const T& t); + T pop(); + + std::vector<T> v_; + unsigned head_; + }; # ifndef MLN_INCLUDE_ONLY - template <typename B> - B - domain_from_k0(const Box<B>& b_, const unsigned n, - unsigned inner_border_thickness) + template <typename T> + queue_<T>::queue_() + { + head_ = 0; + } + + template <typename T> + void + queue_<T>::reserve(unsigned n) + { + v_.reserve(n); + } + + template <typename T> + unsigned + queue_<T>::nelements() const + { + mln_precondition(head_ >= v_.size()); + return v_.size() - head_; + } + + template <typename T> + bool + queue_<T>::is_empty() const + { + return head_ == v_.size(); + } + + template <typename T> + const T& + queue_<T>::operator[](unsigned i) const { - mln_precondition(exact(b_).is_valid()); - const B& b = exact(b_); - - mln_deduce(B, site, delta) one; - one.set_all(1); - B bout = B(immerse_point(b.pmin(), n, inner_border_thickness) - - (inner_border_thickness * 2 * one) - one, - immerse_point(b.pmax(), n, inner_border_thickness) - + (std::pow(2,n) - 1) * one + (inner_border_thickness * 2 * one)); - return bout; + mln_precondition(head_ + i < v_.size()); + return v_[head_ + i]; } + template <typename T> + void + queue_<T>::push(const T& t) + { + v_.push_back(t); + } - template <typename B> - B - domain_from_k0(const Box<B>& b, const unsigned n) + template <typename T> + T + queue_<T>::pop() { - return domain_from_K0(b, n, 0); + mln_precondition(! is_empty()); + mln_precondition(head_ < v_.size()); + return v_[head_++]; } # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::work::kn::internal + } // end of namespace mln::world::kn::internal } // end of namespace mln::world::kn @@ -98,6 +133,4 @@ namespace mln } // end of namespace mln -#endif // ! MLN_WORLD_KN_DOMAIN_FROM_K0_HH - - +#endif // ! MLN_WORLD_KN_INTERNAL_QUEUE_HH -- 1.7.2.5