[Olena-patches] 1003: Add progressive histogram and median in milena.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add progressive histogram and median in milena. * tests/median.cc: New. * mln/value/vset.hh: Rename as... * mln/value/set.hh: ... this new file. * tests/vset.cc: Update. * tests/histo.cc: New. * mln/histo: New. * mln/core/concept/value_set.hh: Update. * mln/core/concept/doc/value_set.hh: Update. * mln/value/histo.hh: New. * mln/value/median.hh: New. * mln/value/int_u.hh: Update. mln/core/concept/doc/value_set.hh | 4 mln/core/concept/value_set.hh | 3 mln/value/histo.hh | 206 ++++++++++++++++++++++++++++ mln/value/int_u.hh | 11 + mln/value/median.hh | 270 ++++++++++++++++++++++++++++++++++++++ mln/value/set.hh | 61 +++++++- tests/histo.cc | 67 +++++++++ tests/median.cc | 184 +++++++++++++++++++++++++ tests/vset.cc | 6 9 files changed, 798 insertions(+), 14 deletions(-) Index: tests/median.cc --- tests/median.cc (revision 0) +++ tests/median.cc (revision 0) @@ -0,0 +1,184 @@ +// 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. + +/*! \file tests/median.cc + * + * \brief Tests on mln::value::median<S>. + */ + +#include <mln/value/int_u.hh> +#include <mln/value/median.hh> + + + +int main() +{ + using namespace mln; + using namespace mln::value; + + typedef set_<int_u8> S; + + median<S> m(S::the()); + + + { + + unsigned vals[] = { 42, 69, 51, 12, 51, 12, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (int i = int(n) - 1; i >= 0; --i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + { + + unsigned vals[] = { 42, 69, 51, 12, 51, 12, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + + { + + unsigned vals[] = { 42, 42, 69, 69, 51, 51, 12, 12, 51, 51, 12, 12, 42, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (int i = int(n) - 1; i >= 0; --i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + { + + unsigned vals[] = { 42, 42, 69, 69, 51, 51, 12, 12, 51, 51, 12, 12, 42, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + + + { + + unsigned vals[] = { 42, 69, 51, 12, 51, 12, 42, 69, 51, 12, 51, 12, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (int i = int(n) - 1; i >= 0; --i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + { + + unsigned vals[] = { 42, 69, 51, 12, 51, 12, 42, 69, 51, 12, 51, 12, 42 }; + unsigned n = sizeof(vals)/sizeof(unsigned); + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "taking " << vals[i] << ':' << std::endl; + m.take(vals[i]); + std::cout << m << std::endl; + } + + for (unsigned i = 0; i < n; ++i) + { + std::cout << "untaking " << vals[i] << ':' << std::endl; + m.untake(vals[i]); + std::cout << m << std::endl; + } + + } + + + +} Index: tests/vset.cc --- tests/vset.cc (revision 1002) +++ tests/vset.cc (working copy) @@ -27,11 +27,11 @@ /*! \file tests/vset.cc * - * \brief Tests on mln::vset. + * \brief Tests on mln::value::set_<T>. */ #include <mln/value/int_u.hh> -#include <mln/value/vset.hh> +#include <mln/value/set.hh> @@ -43,7 +43,7 @@ // typedef value::int_u8 T; // typedef short T; - typedef value::vset_<T> S; + typedef value::set_<T> S; S s; { Index: tests/histo.cc --- tests/histo.cc (revision 0) +++ tests/histo.cc (revision 0) @@ -0,0 +1,67 @@ +// 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. + +/*! \file tests/histo.cc + * + * \brief Tests on mln::value::histo<S>. + */ + +#include <mln/value/int_u.hh> +#include <mln/value/set.hh> +#include <mln/value/histo.hh> + + + +int main() +{ + using namespace mln; + using namespace mln::value; + + + histo_on_type<bool> h; + + for (unsigned i = 0; i < 5; ++i) + h.take(false); + for (unsigned i = 0; i < 2; ++i) + h.take(true); + h.untake(true); + + std::cout << h << std::endl; + std::cout << h[0] * 10 + h[1] << std::endl; + std::cout << h(false) * 10 + h(true) << std::endl; + + h.clear(); + std::cout << h << std::endl; + + + // ... + + + typedef value::set_<int_u8> S; + histo_on_set<S> h_u8(S::the()); + std::cout << h_u8 << std::endl; +} Index: mln/core/concept/value_set.hh --- mln/core/concept/value_set.hh (revision 1002) +++ mln/core/concept/value_set.hh (working copy) @@ -53,7 +53,10 @@ typedef bkd_viter; bool has(const value& v) const; + value operator[](std::size_t i) const; + std::size_t index_of(const value& v) const; + std::size_t nvalues() const; */ Index: mln/core/concept/doc/value_set.hh --- mln/core/concept/doc/value_set.hh (revision 1002) +++ mln/core/concept/doc/value_set.hh (working copy) @@ -72,6 +72,10 @@ /*! \brief Give the \p i-th value of this set. */ value operator[](std::size_t i) const; + + /*! \brief Give the index of value \p v in this set. + */ + std::size_t index_of(const value& v) const; }; } // end of namespace mln::doc Index: mln/value/histo.hh --- mln/value/histo.hh (revision 0) +++ mln/value/histo.hh (revision 0) @@ -0,0 +1,206 @@ +// 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_VALUE_HISTO_HH +# define MLN_VALUE_HISTO_HH + +/*! \file mln/value/histo.hh + * + * \brief Define a couple of generic histogram classes. + */ + +# include <vector> +# include <algorithm> + +# include <mln/core/concept/value_set.hh> +# include <mln/value/set.hh> + + +namespace mln +{ + + namespace value + { + + + /*! Generic histogram class over a value set with type \c S. + */ + template <typename S> + struct histo_on_set + { + histo_on_set(const Value_Set<S>& s); + + typedef mln_value(S) value; + + void take(const value& v); + void untake(const value& v); + void clear(); + + std::size_t operator()(const value& v) const; + std::size_t operator[](std::size_t i) const; + std::size_t nvalues() const; + std::size_t sum() const; + + const std::vector<std::size_t>& vec() const; + + const S& vset() const; + + protected: + + const S& s_; + std::vector<std::size_t> h_; + std::size_t sum_; + }; + + + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const histo_on_set<S>& h); + + + + + /*! Generic histogram class over the set of values of type \c T. + */ + template <typename T> + struct histo_on_type : public histo_on_set< set_<T> > + { + histo_on_type(); + }; + + + + +# ifndef MLN_INCLUDE_ONLY + + + // histo_on_set<S> + + template <typename S> + histo_on_set<S>::histo_on_set(const Value_Set<S>& s) + : s_(exact(s)), + h_(exact(s).nvalues(), 0), + sum_(0) + { + } + + template <typename S> + void + histo_on_set<S>::take(const value& v) + { + ++h_[s_.index_of(v)]; + ++sum_; + } + + template <typename S> + void + histo_on_set<S>::untake(const value& v) + { + mln_precondition(h_[s_.index_of(v)] > 0); + mln_precondition(sum_ > 0); + --h_[s_.index_of(v)]; + --sum_; + } + + template <typename S> + void + histo_on_set<S>::clear() + { + std::fill(h_.begin(), h_.end(), 0); + } + + template <typename S> + std::size_t + histo_on_set<S>::operator()(const value& v) const + { + return h_[s_.index_of(v)]; + } + + template <typename S> + std::size_t + histo_on_set<S>::operator[](std::size_t i) const + { + mln_precondition(i < s_.nvalues()); + return h_[i]; + } + + template <typename S> + std::size_t + histo_on_set<S>::nvalues() const + { + return s_.nvalues(); + } + + template <typename S> + std::size_t + histo_on_set<S>::sum() const + { + return sum_; + } + + template <typename S> + const std::vector<std::size_t>& + histo_on_set<S>::vec() const + { + return h_; + } + + template <typename S> + const S& + histo_on_set<S>::vset() const + { + return s_; + } + + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const histo_on_set<S>& h) + { + mln_viter(S) v(h.vset()); + for_all(v) + ostr << v << ':' << h(v) << ' '; + ostr << std::endl; + return ostr; + } + + + // histo_on_type<T> + + template <typename T> + histo_on_type<T>::histo_on_type() + : histo_on_set< set_<T> >(set_<T>::the()) + { + } + + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::value + +} // end of namespace mln + + +#endif // ! MLN_VALUE_HISTO_HH Index: mln/value/set.hh --- mln/value/set.hh (revision 1002) +++ mln/value/set.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_VALUE_VSET_HH -# define MLN_VALUE_VSET_HH +#ifndef MLN_VALUE_SET_HH +# define MLN_VALUE_SET_HH /*! \file mln/value/vset.hh * @@ -48,37 +48,55 @@ template <typename S> struct bkd_viter_; - /*! Class that defines the properties of the value type \c T. + /*! Class that defines the set of values of type \c T. + * + * This is an exhaustive value set over \c T. */ template <typename T> - struct vset_ : public Value_Set< vset_<T> > + struct set_ : public Value_Set< set_<T> > { + /// Value associated type. typedef T value; - typedef fwd_viter_< vset_<T> > fwd_viter; - typedef bkd_viter_< vset_<T> > bkd_viter; + /// Forward Viter associated type. + typedef fwd_viter_< set_<T> > fwd_viter; + + /// Backward Viter associated type. + typedef bkd_viter_< set_<T> > bkd_viter; + + /// Viter associated type. typedef fwd_viter viter; + /// Test if \p v belongs to this set: always true! bool has(const T& v) const; + /// Give the \p i-th value. T operator[](std::size_t i) const; + /// Give the index of value \p v in this set. + std::size_t index_of(const T& v) const; + + /// Give the number of values. std::size_t nvalues() const; + + /// Return a singleton. + static const set_<T>& the(); }; + # ifndef MLN_INCLUDE_ONLY template <typename T> bool - vset_<T>::has(const T& v) const + set_<T>::has(const T& v) const { return true; } template <typename T> T - vset_<T>::operator[](std::size_t i) const + set_<T>::operator[](std::size_t i) const { mln_precondition(i < nvalues()); return mln_min(T) + i; @@ -86,19 +104,42 @@ template <typename T> std::size_t - vset_<T>::nvalues() const + set_<T>::index_of(const T& v) const + { + return v - mln_min(T); + } + + template <typename T> + std::size_t + set_<T>::nvalues() const { return mln_card(T); } + template <typename T> + const set_<T>& + set_<T>::the() + { + static set_<T> the_; + return the_; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::value + + + typedef value::set_<bool> Booleans; + typedef value::set_<int> integers(); + typedef value::set_<unsigned> naturals(); + + + } // end of namespace mln # include <mln/value/viter.hh> -#endif // ! MLN_VALUE_VSET_HH +#endif // ! MLN_VALUE_SET_HH Index: mln/value/median.hh --- mln/value/median.hh (revision 0) +++ mln/value/median.hh (revision 0) @@ -0,0 +1,270 @@ +// 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_VALUE_MEDIAN_HH +# define MLN_VALUE_MEDIAN_HH + +/*! \file mln/value/median.hh + * + * \brief Define FIXME + */ + +# include <mln/value/histo.hh> + + +namespace mln +{ + + namespace value + { + + + /*! Generic median function based on histogram over a value set + * with type \c S. + */ + template <typename S> + struct median + { + typedef mln_value(S) value; + + median(const Value_Set<S>& s); + + void take(const value& v); + void untake(const value& v); + void clear(); + + operator value() const; + value to_value() const; + + // FIXME: remove + void debug__() const + { + std::cout << " i = " << i_ + << " v = " << v_ + << " s = " << sum_minus_ << " ; " << h_[i_] << " ; " << sum_plus_ << " = " << h_.sum() + << std::endl; + } + + protected: + + histo_on_set<S> h_; + const S& s_; // derived from h_ + + std::size_t sum_minus_, sum_plus_; + + std::size_t i_; // the median index + value v_; // the median value + + // Auxiliary methods + void go_minus_(); + void go_plus_(); + }; + + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename S> + median<S>::median(const Value_Set<S>& s) + : h_(s), + s_(h_.vset()) + { + clear(); + } + + + template <typename S> + void + median<S>::take(const value& v) + { + // update h_ + h_.take(v); + + // particular case: + // current state was initialization + if (h_[i_] = 0) + { + // std::cout << "init!" << std::endl; + i_ = s_.index_of(v); + v_ = v; + return; + } + + // particular case: + // the median does not change + if (v = v_) + { + // std::cout << "no change!" << std::endl; + return; + } + + // general case: + + if (v < v_) + { + ++sum_minus_; + if (2 * sum_minus_ > h_.sum()) + go_minus_(); + } + else + // v > v_ + { + ++sum_plus_; + if (2 * sum_plus_ > h_.sum()) + go_plus_(); + } + } + + + template <typename S> + void + median<S>::untake(const value& v) + { + mln_precondition(h_(v) != 0); + + // update h_ + h_.untake(v); + + // particular case: + // the only value has been removed + if (h_.sum() = 0) + { + clear(); + return; + } + + // general case: + if (v < v_) + { + --sum_minus_; + if (2 * sum_plus_ > h_.sum()) + go_plus_(); + } + else if (v > v_) + { + --sum_plus_; + if (2 * sum_minus_ > h_.sum()) + go_minus_(); + } + else + // v = v_ + { + if (h_[i_] = 0) + { + // go to the heaviest side + if (sum_plus_ > sum_minus_) + go_plus_(); + else + go_minus_(); // default when both sides are balanced + } + else + { + if (2 * sum_plus_ > h_.sum()) + go_plus_(); + else if (2 * sum_minus_ > h_.sum()) + go_minus_(); + // else no change + } + } + } + + + template <typename S> + void + median<S>::go_minus_() + { + do + { + sum_plus_ += h_[i_]; + do + --i_; + while (h_[i_] = 0); + sum_minus_ -= h_[i_]; + } + while (2 * sum_minus_ > h_.sum()); + v_ = s_[i_]; + } + + + template <typename S> + void + median<S>::go_plus_() + { + do + { + sum_minus_ += h_[i_]; + do + ++i_; + while (h_[i_] = 0); + sum_plus_ -= h_[i_]; + } + while (2 * sum_plus_ > h_.sum()); + v_ = s_[i_]; + } + + + template <typename S> + void + median<S>::clear() + { + h_.clear(); + sum_minus_ = 0; + sum_plus_ = 0; + i_ = (mln_max(value) - mln_min(value)) / 2; + v_ = s_[i_]; + } + + template <typename S> + median<S>::operator typename median<S>::value () const + { + return v_; + } + + template <typename S> + typename median<S>::value + median<S>::to_value() const + { + return v_; + } + + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const median<S>& m) + { + m.debug__(); + return ostr << m.to_value(); + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::value + +} // end of namespace mln + + +#endif // ! MLN_VALUE_MEDIAN_HH Index: mln/value/int_u.hh --- mln/value/int_u.hh (revision 1002) +++ mln/value/int_u.hh (working copy) @@ -86,8 +86,17 @@ }; + // Fwd decl. + template <typename T> struct vset_; + + /// Alias for unsigned 8bit integers. - typedef value::int_u_<8> int_u8; + typedef int_u_<8> int_u8; + + /// Alias for the set of unsigned 8bit integers. + typedef vset_<int_u8> int_u8_set; + + /*! \brief Print an int_u8 \p i into the output stream \p ostr.