URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-12-07 Simon Nivault <simon.nivault@lrde.epita.fr> The set of a lazy_set can be cleared. * mln/util/lazy_set.hh: The set can be cleared. * tests/util/Makefile.am, * tests/util/lazy_set.cc: New test. * mln/core/internal/run_image.hh, * mln/core/mono_obased_rle_encode.hh, * mln/core/mono_obased_rle_image.hh, * mln/core/mono_rle_encode.hh, * mln/core/mono_rle_image.hh, * mln/core/obased_rle_encode.hh, * mln/core/obased_rle_image.hh, * mln/core/p_runs.hh, * mln/core/rle_encode.hh, * mln/core/rle_image.hh, * mln/core/sparse_encode.hh, * mln/core/sparse_image.hh: Use new lazy_set features. --- mln/core/internal/run_image.hh | 34 +++++++++++++++++ mln/core/mono_obased_rle_encode.hh | 1 mln/core/mono_obased_rle_image.hh | 14 +++++++ mln/core/mono_rle_encode.hh | 1 mln/core/mono_rle_image.hh | 11 +++++ mln/core/obased_rle_encode.hh | 1 mln/core/obased_rle_image.hh | 11 +++++ mln/core/p_runs.hh | 17 ++++++++ mln/core/rle_encode.hh | 1 mln/core/rle_image.hh | 11 +++++ mln/core/sparse_encode.hh | 5 -- mln/core/sparse_image.hh | 11 +++++ mln/util/lazy_set.hh | 71 +++++++++++++++++++++++++++++++++++-- tests/util/Makefile.am | 2 + tests/util/lazy_set.cc | 64 +++++++++++++++++++++++++++++++++ 15 files changed, 248 insertions(+), 7 deletions(-) Index: trunk/milena/tests/util/Makefile.am =================================================================== --- trunk/milena/tests/util/Makefile.am (revision 1599) +++ trunk/milena/tests/util/Makefile.am (revision 1600) @@ -8,6 +8,7 @@ branch_iter_ind \ eat \ graph \ + lazy_set \ ordpair \ tree \ tree_fast \ @@ -19,6 +20,7 @@ branch_iter_ind_SOURCES = branch_iter_ind.cc eat_SOURCES = eat.cc graph_SOURCES = graph.cc +lazy_set_SOURCES = lazy_set.cc ordpair_SOURCES = ordpair.cc tree_SOURCES = tree.cc tree_fast_SOURCES = tree_fast.cc Index: trunk/milena/tests/util/lazy_set.cc =================================================================== --- trunk/milena/tests/util/lazy_set.cc (revision 0) +++ trunk/milena/tests/util/lazy_set.cc (revision 1600) @@ -0,0 +1,64 @@ +// 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/util/lazy_set.cc + * + * \brief test of mln::util::lazy_set + * + */ + +#include <iostream> + +#include <mln/util/lazy_set.hh> + +int main () +{ + using namespace mln; + + util::lazy_set_<int> s1; + util::lazy_set_<int> s2; + + s1.insert(3); + s1.insert(-2); + s1.insert(9); + s1.insert(0); + s2.insert(3); + s2.insert(-2); + s2.insert(9); + s2.insert(0); + + mln_assertion(s1.nelements() == 4); + s2.set_const_mode(true); + mln_assertion(s2.nelements() == 4); + + for (unsigned i = 0; i < s1.nelements(); ++i) + { + std::cout << s1[i] << " = " << s2[i] << std::endl; + mln_assertion(s1[i] == s2[i]); + } +} Index: trunk/milena/mln/core/mono_rle_encode.hh =================================================================== --- trunk/milena/mln/core/mono_rle_encode.hh (revision 1599) +++ trunk/milena/mln/core/mono_rle_encode.hh (revision 1600) @@ -98,6 +98,7 @@ rstart = p; } } + output.finalize(); return output; } Index: trunk/milena/mln/core/sparse_encode.hh =================================================================== --- trunk/milena/mln/core/sparse_encode.hh (revision 1599) +++ trunk/milena/mln/core/sparse_encode.hh (revision 1600) @@ -88,30 +88,27 @@ { ++len; rstart = p; - std::cout << "New run " << p << ": *"; rvalue.push_back(ima(p)); } else if ((!ignore_zero || ima(p) != literal::zero) && on_the_same_line(rstart, mln_point(I)(p), len)) { - std::cout << "*"; ++len; rvalue.push_back(ima(p)); } else { - std::cout << std::endl; output.insert(p_run<P>(rstart, len), rvalue); rvalue.clear(); if ((len = (!ignore_zero || ima(p) != literal::zero))) { rstart = p; - std::cout << "New run " << p << ": "; rvalue.push_back(ima(p)); } } } + output.finalize(); return output; } Index: trunk/milena/mln/core/internal/run_image.hh =================================================================== --- trunk/milena/mln/core/internal/run_image.hh (revision 1599) +++ trunk/milena/mln/core/internal/run_image.hh (revision 1600) @@ -56,7 +56,22 @@ run_image_(); public: + /*! \brief Give the rate of compression. + * + * Give the rate of space gained by coding an image in this + * format. A rate of 1 means there is no compression. Less than + * 1 means we have gained space. + * + * \return The rate of compression. + */ float compression() const; + + /*! \brief Finalize the construction. + * + * For internal use, this method has to be called to have + * actually an lighter image. So it improves compression. + */ + void finalize(); }; # ifndef MLN_INCLUDE_ONLY @@ -72,10 +87,29 @@ float run_image_<T, P, E>::compression() const { + std::cout << float(exact(this)->data_->size_mem()) + << " / ( " + << float (sizeof(T)) + << " * " + << float (exact(this)->data_->domain_.bbox().npoints()) + << " )" + << std::endl; + std::cout << exact(this)->data_->domain_.bbox().pmin() + << " " + << exact(this)->data_->domain_.bbox().pmax() + << std::endl; return float(exact(this)->data_->size_mem()) / float (sizeof(T) * exact(this)->data_->domain_.bbox().npoints()); } + template <typename T, typename P, typename E> + inline + void + run_image_<T, P, E>::finalize() + { + exact(this)->data_->finalize(); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace internal Index: trunk/milena/mln/core/rle_image.hh =================================================================== --- trunk/milena/mln/core/rle_image.hh (revision 1599) +++ trunk/milena/mln/core/rle_image.hh (revision 1600) @@ -62,6 +62,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + + /// Finalize the domain (internal use). + void finalize(); }; } // end of namespace mln::internal @@ -157,6 +160,14 @@ return sizeof(T) * values_.size() + domain_.size_mem(); } + template <typename P, typename T> + inline + void + data_< rle_image<P,T> >::finalize() + { + domain_.finalize(); + } + } // end of namespace mln::internal template <typename P, typename T> Index: trunk/milena/mln/core/obased_rle_encode.hh =================================================================== --- trunk/milena/mln/core/obased_rle_encode.hh (revision 1599) +++ trunk/milena/mln/core/obased_rle_encode.hh (revision 1600) @@ -110,6 +110,7 @@ } } } + output.finalize(); return output; } Index: trunk/milena/mln/core/mono_rle_image.hh =================================================================== --- trunk/milena/mln/core/mono_rle_image.hh (revision 1599) +++ trunk/milena/mln/core/mono_rle_image.hh (revision 1600) @@ -62,6 +62,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + + /// Finalize the domain (internal use). + void finalize(); }; } // end of namespace mln::internal @@ -162,6 +165,14 @@ return sizeof(T) + domain_.size_mem(); } + template <typename P, typename T> + inline + void + data_< mono_rle_image<P,T> >::finalize() + { + domain_.finalize(); + } + } // end of namespace mln::internal template <typename P, typename T> Index: trunk/milena/mln/core/obased_rle_image.hh =================================================================== --- trunk/milena/mln/core/obased_rle_image.hh (revision 1599) +++ trunk/milena/mln/core/obased_rle_image.hh (revision 1600) @@ -72,6 +72,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + + /// Finalize the domain (internal use). + void finalize(); }; } // end of namespace mln::internal @@ -179,6 +182,14 @@ + (sizeof(unsigned) + sizeof(T)) * domain_.nruns(); } + template <typename P, typename T> + inline + void + data_< obased_rle_image<P,T> >::finalize() + { + domain_.finalize(); + } + } // end of namespace mln::internal template <typename P, typename T> Index: trunk/milena/mln/core/mono_obased_rle_encode.hh =================================================================== --- trunk/milena/mln/core/mono_obased_rle_encode.hh (revision 1599) +++ trunk/milena/mln/core/mono_obased_rle_encode.hh (revision 1600) @@ -110,6 +110,7 @@ } } } + output.finalize(); return output; } Index: trunk/milena/mln/core/mono_obased_rle_image.hh =================================================================== --- trunk/milena/mln/core/mono_obased_rle_image.hh (revision 1599) +++ trunk/milena/mln/core/mono_obased_rle_image.hh (revision 1600) @@ -67,6 +67,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + + /// Finalize the domain (internal use). + void finalize(); }; } // end of namespace mln::internal @@ -166,6 +169,17 @@ return domain_.size_mem() * 2 + sizeof(T) * (values_.size() + ima_.size()); } + template <typename P, typename T> + inline + void + data_< mono_obased_rle_image<P,T> >::finalize() + { + domain_.finalize(); + for (typename std::vector< mono_rle_image<P, T> >::iterator it = ima_.begin(); + it != ima_.end(); ++it) + it->finalize(); + } + } // end of namespace mln::internal template <typename P, typename T> Index: trunk/milena/mln/core/rle_encode.hh =================================================================== --- trunk/milena/mln/core/rle_encode.hh (revision 1599) +++ trunk/milena/mln/core/rle_encode.hh (revision 1600) @@ -103,6 +103,7 @@ } } } + output.finalize(); return output; } Index: trunk/milena/mln/core/sparse_image.hh =================================================================== --- trunk/milena/mln/core/sparse_image.hh (revision 1599) +++ trunk/milena/mln/core/sparse_image.hh (revision 1600) @@ -62,6 +62,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + + /// Finalize the domain (internal use). + void finalize(); }; } // end of namespace mln::internal @@ -157,6 +160,14 @@ return sizeof(T) * domain_.npoints() + domain_.size_mem(); } + template <typename P, typename T> + inline + void + data_< sparse_image<P,T> >::finalize() + { + domain_.finalize(); + } + } // end of namespace mln::internal template <typename P, typename T> Index: trunk/milena/mln/core/p_runs.hh =================================================================== --- trunk/milena/mln/core/p_runs.hh (revision 1599) +++ trunk/milena/mln/core/p_runs.hh (revision 1600) @@ -93,6 +93,9 @@ /// Return the size of the data in memory. unsigned size_mem() const; + /// Finalize the lazy_set (internal use) + void finalize(); + // /// Return the container of the pset (internal use only). // const container& con() const; @@ -225,9 +228,21 @@ unsigned p_runs_<P>::size_mem() const { - return nruns() * 2 * (sizeof(P) + sizeof(unsigned)); + if (con_.get_mode()) + return nruns() * (sizeof(P) + sizeof(unsigned)); + else + return 2 * nruns() * (sizeof(P) + sizeof(unsigned)); } + template <typename P> + inline + void + p_runs_<P>::finalize() + { + con_.set_const_mode(true); + } + + // template <typename P> // const typename p_runs_<P>::container& // p_runs_<P>::con() const Index: trunk/milena/mln/util/lazy_set.hh =================================================================== --- trunk/milena/mln/util/lazy_set.hh (revision 1599) +++ trunk/milena/mln/util/lazy_set.hh (revision 1600) @@ -39,6 +39,7 @@ # include <algorithm> # include <mln/core/internal/force_exact.hh> +# include <mln/core/contract.hh> namespace mln @@ -136,6 +137,8 @@ * * All elements contained in the set are destroyed so the set is * emptied. + * The lazy set can be cleared even if it is in const mode + * and then it is set in non-const mode. * * \post is_empty() == true */ @@ -153,6 +156,21 @@ /// Constructor without arguments. lazy_set_(); + /*! \brief Set the mode of the lazy_set + * + * The lazy set can have two modes : + * - const : The lazy set is as light as a vector but you cannot + * modify it + * - non-const : The lazy set use a std::set to have lazy manipulation + * + * \param[in] mode True for const mode, false for non-const. + * + */ + void set_const_mode(bool mode); + + /// Get the mode of the lazy set. + bool get_mode() const; + private: /*! \brief Array of elements. @@ -177,6 +195,9 @@ /// Tell if \a v_ needs to be updated. mutable bool needs_update_; + + /// Tell what the lazy set mode is. + bool mode_; }; @@ -203,6 +224,7 @@ lazy_set_<E>::lazy_set_() { needs_update_ = false; + mode_ = false; } template <typename E> @@ -210,6 +232,7 @@ lazy_set_<E>& lazy_set_<E>::insert(const E& elt) { + mln_assertion(!mode_); s_.insert(elt); if (needs_update_ == false) needs_update_ = true; @@ -221,6 +244,7 @@ lazy_set_<E>& lazy_set_<E>::remove(const E& elt) { + mln_assertion(!mode_); // FIXME : doesn't compile std::remove(s_.begin(), s_.end(), elt); if (needs_update_ == false) @@ -233,7 +257,9 @@ const E& lazy_set_<E>::element(unsigned i) const { - assert(i < s_.size()); + assert((!mode_ && i < s_.size()) + || i < v_.size()); + if (!mode_) if (needs_update_) update_(); return v_[i]; @@ -252,7 +278,10 @@ unsigned lazy_set_<E>::nelements() const { + if (!mode_) return s_.size(); + else + return v_.size(); } template <typename E> @@ -260,7 +289,10 @@ bool lazy_set_<E>::has(const E& elt) const { + if (!mode_) return s_.find(elt) != s_.end(); + else + return v_.find(elt) != v_.end(); } template <typename E> @@ -279,6 +311,7 @@ v_.clear(); s_.clear(); needs_update_ = false; + mode_ = false; mln_postcondition(is_empty()); } @@ -287,6 +320,7 @@ const std::vector<E>& lazy_set_<E>::vect() const { + if (!mode_) if (needs_update_) update_(); return v_; @@ -295,9 +329,42 @@ template <typename E> inline void + lazy_set_<E>::set_const_mode(bool mode) + { + if (mode != mode_) + { + if (mode) + { + if (needs_update_) + update_(); + s_.clear(); + } + else + { + mln_assertion(s_.size() == 0); + for (typename std::vector<E>::iterator it = v_.begin(); + it != v_.end(); it++) + s_.insert(*it); + needs_update_ = false; + } + mode_ = mode; + } + } + + template <typename E> + inline + bool + lazy_set_<E>::get_mode() const + { + return mode_; + } + + template <typename E> + inline + void lazy_set_<E>::update_() const { - mln_precondition(needs_update_); + mln_precondition(needs_update_ && !mode_); v_.clear(); std::copy(s_.begin(), s_.end(), std::back_inserter(v_)); // no s_.clear() here: