* mln/util/hqueue.hh: Add a precondition. * mln/value/interval.hh: Relax types of the constructor arguments and the counting of elements. * mln/value/intsub.hh: Remove constructor from int_u8 and min/max traits. * mln/world/kn/compute_tree_of_shapes.hh: Pass interval of values as argument and fix overlow issues. * tests/value/interval.cc: Add more tests. * tests/value/intsub.cc: Use math::mean and math::median. --- milena/ChangeLog | 19 ++++++ milena/mln/util/hqueue.hh | 1 + milena/mln/value/interval.hh | 35 +++------- milena/mln/value/intsub.hh | 11 --- milena/mln/world/kn/compute_tree_of_shapes.hh | 84 +++++++++++++++---------- milena/tests/value/interval.cc | 18 +++++ milena/tests/value/intsub.cc | 11 ++-- 7 files changed, 105 insertions(+), 74 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 41719b9..3b898e8 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,24 @@ 2012-10-26 Guillaume Lazzara <z@lrde.epita.fr> + Various fixes. + + * mln/util/hqueue.hh: Add a precondition. + + * mln/value/interval.hh: Relax types of the constructor arguments + and the counting of elements. + + * mln/value/intsub.hh: Remove constructor from int_u8 and min/max + traits. + + * mln/world/kn/compute_tree_of_shapes.hh: Pass interval of values + as argument and fix overlow issues. + + * tests/value/interval.cc: Add more tests. + + * tests/value/intsub.cc: Use math::mean and math::median. + +2012-10-26 Guillaume Lazzara <z@lrde.epita.fr> + Add specific accumulators to work in kn. * mln/accu/stat/median_h_interval.hh, diff --git a/milena/mln/util/hqueue.hh b/milena/mln/util/hqueue.hh index 3a68b5c..3d28b30 100644 --- a/milena/mln/util/hqueue.hh +++ b/milena/mln/util/hqueue.hh @@ -135,6 +135,7 @@ namespace mln hqueue<T,P>::pop(const P& priority) { mln_precondition(!is_empty()); + mln_precondition(priority < v_.size()); T front = v_[priority].front(); v_[priority].pop(); return front; diff --git a/milena/mln/value/interval.hh b/milena/mln/value/interval.hh index b40f989..e835630 100644 --- a/milena/mln/value/interval.hh +++ b/milena/mln/value/interval.hh @@ -55,12 +55,12 @@ namespace mln interval(); template <typename U> - interval(U single); + interval(const U& single); - template <typename U> - interval(U first, U last); + template <typename U, typename V> + interval(const U& first, const V& last); - interval& operator=(const interval& rhs); + // interval& operator=(const interval& rhs); /// Return True if a value is within this interval. bool has(const T& v) const; @@ -228,7 +228,7 @@ namespace mln template <typename T> template <typename U> - interval<T>::interval(U single) + interval<T>::interval(const U& single) { mlc_converts_to(U,T)::check(); first_ = single; @@ -237,33 +237,18 @@ namespace mln nelements_ = 1; } - template <typename T> - template <typename U> - interval<T>::interval(U first, U last) + template <typename U, typename V> + interval<T>::interval(const U& first, const V& last) { mlc_converts_to(U,T)::check(); + mlc_converts_to(V,T)::check(); mln_precondition(last >= first); first_ = first; last_ = last; - nelements_ = 1; - // The second condition in the for-loop is required in case of - // overflow... - if (first != last) - { - for (T v = value::succ(first_); v <= last_ && v > first_; value::inc(v)) - ++nelements_; - } - } - - template <typename T> - interval<T>& - interval<T>::operator=(const interval& rhs) - { - first_ = rhs.first_; - last_ = rhs.last_; - return *this; + nelements_ = (last_ - first_) + / static_cast<float>(iota<T>::value()) + 1.f; } template <typename T> diff --git a/milena/mln/value/intsub.hh b/milena/mln/value/intsub.hh index 9fc7007..0a1dabc 100644 --- a/milena/mln/value/intsub.hh +++ b/milena/mln/value/intsub.hh @@ -83,8 +83,6 @@ namespace mln typedef trait::value::kind::data kind; typedef mln_value_quant_from_(card) quant; - static const self_ max() { return mln::value::internal::limits<int>::max() / n; } - static const self_ min() { return - max(); } static const self_ epsilon() { return 0; } typedef mln::value::intsub<n> comp; @@ -139,9 +137,6 @@ namespace mln template <unsigned m> intsub(const intsub<m>& rhs); - // FIXME: Really ? - intsub(const value::int_u<8>& rhs); - /// Construct an intsub with value : \p int_part + 1 / \p denominator. intsub(int int_part, unsigned denominator); intsub(const literal::zero_t&); @@ -304,12 +299,6 @@ namespace mln } template <unsigned n> - intsub<n>::intsub(const value::int_u<8>& rhs) - { - this->v_ = n * rhs.to_equiv(); - } - - template <unsigned n> intsub<n>::intsub(const literal::zero_t&) { this->v_ = 0; diff --git a/milena/mln/world/kn/compute_tree_of_shapes.hh b/milena/mln/world/kn/compute_tree_of_shapes.hh index 63cf1a5..e503d66 100644 --- a/milena/mln/world/kn/compute_tree_of_shapes.hh +++ b/milena/mln/world/kn/compute_tree_of_shapes.hh @@ -36,12 +36,9 @@ # include <mln/core/alias/neighb2d.hh> -# include <mln/data/compute.hh> - -# include <mln/accu/math/span.hh> - # include <mln/value/dec.hh> # include <mln/value/inc.hh> +# include <mln/value/interval.hh> # include <mln/util/hqueue.hh> # include <mln/util/tree_of_shapes.hh> @@ -62,9 +59,16 @@ namespace mln { /// \brief Compute the tree of shape from a Kn 2D image. + /*! + + \param[in] F A 2D image in Kn. It's values are considered of + type value::interval<>. + \param[in] inter Interval of the possible values in \p F. + + */ template <typename I> util::tree_of_shapes<I> - compute_tree_of_shapes(const Image<I>& F); + compute_tree_of_shapes(const Image<I>& F, const mln_value(I)& inter); # ifndef MLN_INCLUDE_ONLY @@ -87,7 +91,8 @@ namespace mln compute_tree_of_shapes_t(); - util::tree_of_shapes<I> operator()(const I& F_); + util::tree_of_shapes<I> operator()(const I& F_, + const mln_value(I)& inter); void do_union(P p_, P r_, T& zpar, U& rank, U& last); @@ -104,7 +109,8 @@ namespace mln EV level_next_to_lcur(q_type& q); - void sort(const Image<I>& F_, util::tree_of_shapes<I>& t, display& dsp); + void sort(const Image<I>& F_, util::tree_of_shapes<I>& t, + display& dsp); void canonicalize_tree(util::tree_of_shapes<I>& t); @@ -117,8 +123,7 @@ namespace mln unsigned N; box2d D; - - V vspan_; + mln_value(I) inter_; }; @@ -207,18 +212,6 @@ namespace mln } - - // std::ostream& - // operator<<(std::ostream& ostr, const q_type& q) - // { - // ostr << "q = "; - // for (unsigned i = 0; i < q.size(); ++i) - // if (! q[i].empty()) - // ostr << i << ':' << q[i].size() << " "; - // return ostr; - // } - - template <typename I> void compute_tree_of_shapes_t<I>::priority_push(q_type& q, const P& p, const I& F) @@ -242,12 +235,25 @@ namespace mln typename compute_tree_of_shapes_t<I>::EV compute_tree_of_shapes_t<I>::upper_level_next_to_lcur(q_type& q, bool& found) { - for (EV l_ = lcur; l_ <= vspan_.last(); value::inc(l_)) + EV l_ = lcur; + + for (; l_ < inter_.last(); value::inc(l_)) + { if (! q[l_].empty()) { found = true; return l_; } + } + + // Avoid overflow on last element. + if (l_ == inter_.last()) + if (! q[l_].empty()) + { + found = true; + return l_; + } + found = false; return EV(); } @@ -256,12 +262,23 @@ namespace mln typename compute_tree_of_shapes_t<I>::EV compute_tree_of_shapes_t<I>::lower_level_next_to_lcur(q_type& q, bool& found) { - for (EV l_ = lcur; l_ >= vspan_.first(); value::dec(l_)) + EV l_ = lcur; + + for (; l_ > inter_.first(); value::dec(l_)) + if (! q[l_].empty()) + { + found = true; + return l_; + } + + // Avoid overflow on first element. + if (l_ == inter_.first()) if (! q[l_].empty()) { found = true; return l_; } + found = false; return EV(); } @@ -341,7 +358,7 @@ namespace mln mln_ch_value(I,bool) deja_vu(D), done(D); mln_piter(B) p(D); - q_type q(vspan_); + q_type q(inter_); for_all(p) { @@ -445,19 +462,15 @@ namespace mln template <typename I> util::tree_of_shapes<I> - compute_tree_of_shapes_t<I>::operator()(const I& F) + compute_tree_of_shapes_t<I>::operator()(const I& F, + const mln_value(I)& inter) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(F.is_valid()); - /// FIXME: Really ? - /// Useful while sorting sites and constructing the hqueue. - accu::math::span<V> accu; - vspan_ = data::compute(accu, F | kn::is_2_face); - /// End of FIXME - N = F.nsites(); D = F.domain(); + inter_ = inter; util::tree_of_shapes<I> t; @@ -474,20 +487,25 @@ namespace mln + template <typename I> util::tree_of_shapes<I> - compute_tree_of_shapes(const Image<I>& F) + compute_tree_of_shapes(const Image<I>& F, + const mln_value(I)& inter) { 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(); util::tree_of_shapes<I> - t = internal::compute_tree_of_shapes_t<I>()(exact(F)); + t = internal::compute_tree_of_shapes_t<I>()(exact(F), inter); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::world::kn diff --git a/milena/tests/value/interval.cc b/milena/tests/value/interval.cc index fe5a183..43b5c26 100644 --- a/milena/tests/value/interval.cc +++ b/milena/tests/value/interval.cc @@ -107,4 +107,22 @@ int main() mln_assertion(r1.ith_element(4) == 4); } + + // Check of nelements() + { + interval<intsub<1> > r(0, 255); + mln_assertion(r.nelements() == 256); + } + { + interval<intsub<2> > r(0, 255); + mln_assertion(r.nelements() == 511); + } + { + interval<intsub<2> > r(3.5, 4.5); + mln_assertion(r.nelements() == 3); + } + { + interval<intsub<4> > r(2.25, 10.50); + mln_assertion(r.nelements() == 34); + } } diff --git a/milena/tests/value/intsub.cc b/milena/tests/value/intsub.cc index 82a87fb..06b8f1a 100644 --- a/milena/tests/value/intsub.cc +++ b/milena/tests/value/intsub.cc @@ -33,6 +33,7 @@ #include <mln/value/succ.hh> #include <mln/value/prev.hh> #include <mln/math/mean.hh> +#include <mln/math/median.hh> #include <mln/math/min.hh> #include <mln/math/ceil.hh> #include <mln/math/floor.hh> @@ -50,10 +51,10 @@ int main() mln_assertion(i == half + 2); // (2.5 + 0.5) / 2 == 1.5 - mln_assertion(mean(i, half) == 1 + half); + mln_assertion(math::mean(i, half) == 1 + half); // (2.5 + 2) / 2 = 2.25 - intsub<4> res = mean(i, intsub<2>(2)); + intsub<4> res = math::mean(i, intsub<2>(2)); mln_assertion(res == 2.25); // i == 3 @@ -95,15 +96,15 @@ int main() mln_assertion(mln::math::min(i, l) == 2.5); // mean(6,2,2.5,3) = 3.375 - mln_assertion(mean(i, intsub<2>(2), l, intsub<2>(3)) == 3.375); + mln_assertion(math::mean(i, intsub<2>(2), l, intsub<2>(3)) == 3.375); // ceil(2.5) mln_assertion(math::ceil(l) == 3); mln_assertion(math::floor(l) == 2); // median(6,2,2.5,3) = 2.75 - mln_assertion(median(i, intsub<2>(2), l, intsub<2>(3)) == 2.75); + mln_assertion(math::median(i, intsub<2>(2), l, intsub<2>(3)) == 2.75); // median(6,2) = 4 - mln_assertion(median(i, intsub<2>(2)) == 4); + mln_assertion(math::median(i, intsub<2>(2)) == 4); } -- 1.7.2.5