[Olena-patches] milena r4552: Add hierarchical queues for Salembier's algorithm

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-09-25 Edwin Carlinet &lt;carlinet(a)lrde.epita.fr&gt; Add hierarchical queues for Salembier's algorithm. * core/site_set/p_queue_fast.hh: Add empty method. * util/all.hh: Update. * util/hqueues.hh: New. * value/all.hh: Update. * value/value_array.hh: New. Create an array indexed by a given type. (Similar to histo::array but the values are not limited to unsigned type). --- core/site_set/p_queue_fast.hh | 11 ++ util/all.hh | 1 util/hqueues.hh | 159 ++++++++++++++++++++++++++++++++++++ value/all.hh | 2 value/value_array.hh | 184 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 356 insertions(+), 1 deletion(-) Index: trunk/milena/mln/core/site_set/p_queue_fast.hh =================================================================== --- trunk/milena/mln/core/site_set/p_queue_fast.hh (revision 4551) +++ trunk/milena/mln/core/site_set/p_queue_fast.hh (revision 4552) @@ -111,6 +111,8 @@ /// Give the number of sites. unsigned nsites() const; + /// Test if the queue is empty. + bool empty() const; /// Push a site \p p in the queue. void push(const P& p); @@ -244,6 +246,15 @@ template <typename P> inline + bool + p_queue_fast<P>::empty() const + { + mln_invariant(end_ >= begin_); + return end_ == begin_; + } + + template <typename P> + inline void p_queue_fast<P>::push(const P& p) { Index: trunk/milena/mln/value/all.hh =================================================================== --- trunk/milena/mln/value/all.hh (revision 4551) +++ trunk/milena/mln/value/all.hh (revision 4552) @@ -53,7 +53,7 @@ # include <mln/value/interval.hh> # include <mln/value/label.hh> # include <mln/value/proxy.hh> - +# include <mln/value/value_array.hh> // FIXME: that includes concept/image.hh! Index: trunk/milena/mln/value/value_array.hh =================================================================== --- trunk/milena/mln/value/value_array.hh (revision 0) +++ trunk/milena/mln/value/value_array.hh (revision 4552) @@ -0,0 +1,184 @@ +// Copyright (C) 2009 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_VALUE_VALUE_ARRAY_HH +# define MLN_VALUE_VALUE_ARRAY_HH + +/// \file +/// +/// Define a generic array indexed by an iterable type. + +# include <mln/value/set.hh> + + +namespace mln +{ + + namespace value + { + + + /// Generic array class over indexed by a value set with type \c T. + template <typename T, typename V> + struct value_array + { + enum { + nvalues = mln_card(T) + }; + + /// Constructors. + /// { + value_array(); + value_array(const V& v); + value_array(const value_array<T, V>& other); + value_array& operator=(const value_array<T, V>& other); + /// } + + /// Access elements through a value of \p T. + /// { + const V& operator()(const T& v) const; + V& operator()(const T& v); + /// } + + /// Access elements through array indexes. + /// { + const V& operator[](unsigned i) const; + V& operator[](unsigned i); + /// } + + /// Reference to the set of \p T. + const mln::value::set<T>& vset() const; + + protected: + + const mln::value::set<T>& s_; + V v_[nvalues]; + }; + + + template <typename T, typename V> + std::ostream& operator<<(std::ostream& ostr, const value_array<T, V>& a); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T, typename V> + inline + value_array<T,V>::value_array() + : s_ (mln::value::set<T>::the()) + { + typedef value::internal::iterable_set< T, set<T> > U; + mlc_is(set<T>, U)::check(); + } + + template <typename T, typename V> + inline + value_array<T,V>::value_array(const V& v) + : s_(mln::value::set<T>::the()) + { + typedef value::internal::iterable_set< T, set<T> > U; + mlc_is(set<T>, U)::check(); + + memset(v_, v, nvalues * sizeof(V)); + } + + template <typename T, typename V> + inline + value_array<T,V>::value_array(const value_array<T, V>& other) + : s_(other.s_) + { + memcpy(v_, other.v_, nvalues * sizeof(V)); + } + + template <typename T, typename V> + inline + value_array<T,V>& + value_array<T,V>::operator=(const value_array<T, V>& other) + { + if (&other != this) + memcpy(v_, other.v_, nvalues * sizeof(V)); + return *this; + } + + template <typename T, typename V> + inline + const V& + value_array<T,V>::operator()(const T& v) const + { + return v_[s_.index_of(v)]; + } + + template <typename T, typename V> + inline + V& + value_array<T,V>::operator()(const T& v) + { + return v_[s_.index_of(v)]; + } + + template <typename T, typename V> + inline + const mln::value::set<T>& + value_array<T,V>::vset() const + { + return s_; + } + + template <typename T, typename V> + inline + const V& + value_array<T,V>::operator[](unsigned i) const + { + mln_precondition(i < nvalues); + return v_[i]; + } + + template <typename T, typename V> + inline + V& + value_array<T,V>::operator[](unsigned i) + { + mln_precondition(i < nvalues); + return v_[i]; + } + + template <typename T, typename V> + inline + std::ostream& operator<<(std::ostream& ostr, const value_array<T,V>& a) + { + mln_viter(mln::value::set<T>) v(a.vset()); + for_all(v) + ostr << v << ':' << h(v) << ' '; + return ostr; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::value + +} // end of namespace mln + + +#endif // ! MLN_VALUE_VALUE_ARRAY_HH Index: trunk/milena/mln/util/all.hh =================================================================== --- trunk/milena/mln/util/all.hh (revision 4551) +++ trunk/milena/mln/util/all.hh (revision 4552) @@ -51,6 +51,7 @@ # include <mln/util/dindex.hh> # include <mln/util/eat.hh> # include <mln/util/edge.hh> +# include <mln/util/hqueues.hh> # include <mln/util/graph.hh> # include <mln/util/greater_point.hh> # include <mln/util/greater_psite.hh> Index: trunk/milena/mln/util/hqueues.hh =================================================================== --- trunk/milena/mln/util/hqueues.hh (revision 0) +++ trunk/milena/mln/util/hqueues.hh (revision 4552) @@ -0,0 +1,159 @@ +// Copyright (C) 2008, 2009 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_HQUEUES_HH +# define MLN_UTIL_HQUEUES_HH + +/// +/// \brief Generic class for hierarchical queues. +/// +/// Hierarchical queues are often used with connected operators +/// (P. Salemebier's max tree algorithm relies on these queues). To be +/// efficient, the hiererachy is a static array and each are +/// preallocated using an histogram. +/// +/// FIXME: consider hqueues as a site set ? + + +# include <mln/core/site_set/p_queue_fast.hh> +# include <mln/histo/array.hh> +# include <mln/value/set.hh> + + +namespace mln +{ + + namespace util + { + + template <typename P, typename T> + struct hqueues + { + enum { + nvalues = mln_card(T) + }; + + hqueues(const histo::array<T>& h); + + const p_queue_fast<P>& operator[](unsigned i) const; + p_queue_fast<P>& operator[](unsigned i); + + const p_queue_fast<P>& operator()(const T& v) const; + p_queue_fast<P>& operator()(const T& v); + + const mln::value::set<T>& vset() const; + + protected: + void pre_allocate_(unsigned i); + + const histo::array<T>& h_; + const mln::value::set<T>& s_; + std::vector<bool> allocated_; + std::vector< p_queue_fast<P> >queues_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T> + inline + hqueues<P,T>::hqueues(const histo::array<T>& h) + : h_ (h), + s_ (mln::value::set<T>::the()), + allocated_ (nvalues, false), + queues_ (nvalues) + { + } + + template <typename P, typename T> + inline + void + hqueues<P,T>::pre_allocate_(unsigned i) + { + mln_precondition(i < nvalues); + if (!allocated_[i]) + { + queues_[i].reserve(h_[i]); + allocated_[i] = true; + } + } + + + template <typename P, typename T> + inline + const p_queue_fast<P>& + hqueues<P,T>::operator[](unsigned i) const + { + mln_precondition(i < nvalues); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + p_queue_fast<P>& + hqueues<P,T>::operator[](unsigned i) + { + mln_precondition(i < nvalues); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + const p_queue_fast<P>& + hqueues<P,T>::operator()(const T& v) const + { + unsigned i = s_.index_of(v); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + p_queue_fast<P>& + hqueues<P,T>::operator()(const T& v) + { + unsigned i = s_.index_of(v); + pre_allocate_(i); + return queues_[i]; + } + + + template <typename P, typename T> + inline + const mln::value::set<T>& + hqueues<P,T>::vset() const + { + return s_; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util + +} // end of namespace mln + +#endif // !MLN_UTIL_HQUEUES_HH