* mln/value/range.hh, * tests/value/range.cc: Rename as... * mln/value/interval.hh, * tests/value/interval.cc: ... this and improve it. * tests/value/Makefile.am: Update target name. --- milena/ChangeLog | 11 + milena/mln/value/interval.hh | 371 ++++++++++++++++++++--- milena/mln/value/range.hh | 425 -------------------------- milena/tests/value/Makefile.am | 6 +- milena/tests/value/{range.cc => interval.cc} | 47 +++- 5 files changed, 386 insertions(+), 474 deletions(-) delete mode 100644 milena/mln/value/range.hh rename milena/tests/value/{range.cc => interval.cc} (60%) diff --git a/milena/ChangeLog b/milena/ChangeLog index 3d191ab..9392818 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,16 @@ 2012-10-04 Guillaume Lazzara <z@lrde.epita.fr> + Replace range class with interval and improve it. + + * mln/value/range.hh, + * tests/value/range.cc: Rename as... + * mln/value/interval.hh, + * tests/value/interval.cc: ... this and improve it. + + * tests/value/Makefile.am: Update target name. + +2012-10-04 Guillaume Lazzara <z@lrde.epita.fr> + Improve value::intsub class. * mln/value/intsub.hh: Improve class. diff --git a/milena/mln/value/interval.hh b/milena/mln/value/interval.hh index 92ccfad..a4cdf8c 100644 --- a/milena/mln/value/interval.hh +++ b/milena/mln/value/interval.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2007, 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2012 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -26,15 +26,14 @@ #ifndef MLN_VALUE_INTERVAL_HH # define MLN_VALUE_INTERVAL_HH -/*! \file - * - * \brief Define an interval between two values. - * - * \todo Likewise, code value::not_equal(t), less_than, etc. - */ - -# include <mln/core/concept/object.hh> +/// \file +/// +/// Define an interval. +# include <cstdlib> +# include <iostream> +# include <mln/value/inc.hh> +# include <mln/value/concept/interval.hh> namespace mln { @@ -42,61 +41,355 @@ namespace mln namespace value { - /// FIXME: Doc! - + /// \brief Interval of values. template <typename T> - struct interval_ : public Object< interval_<T> > + class interval : public value::Interval<interval<T> > { - interval_(const T& from, const T& to); - T from, to; + public: + typedef T enc; + typedef T equiv; + + interval(); + interval(T first, T last); + + interval& operator=(const interval& rhs); + + /// Return True if a value is within this interval. + bool has(const T& v) const; + + /// Return the distance between the first and the last value. + T length() const; + + /// Return the ith value in this interval. + T ith_element(unsigned i) const; + + /// Return the index of value \p v in this interval. + unsigned index_of(const T& v) const; + + /// Return the number of values in this interval. + unsigned nelements() const; + + /// Return True if this interval contains only one value. + bool is_degenerated() const; - template <typename U> - operator interval_<U>() const; + /// The first value included in this interval. + const T& first() const; + /// The last value included in this interval. + const T& last() const; + + private: + T first_; + T last_; + unsigned nelements_; }; - + + // comparison + + template <typename T> + bool + operator==(const interval<T>& lhs, const interval<T>& rhs); + + template <typename T> + bool + operator!=(const interval<T>& lhs, const interval<T>& rhs); + + // deactivation of ordering related operators + + template <typename T> + void operator<(const interval<T>&, const interval<T>&); template <typename T> - interval_<T> - interval(const T& from, const T& to); + void operator<=(const interval<T>&, const interval<T>&); + + template <typename T> + void operator>(const interval<T>&, const interval<T>&); + + template <typename T> + void operator>=(const interval<T>&, const interval<T>&); + + // set ops + + /*! \p r1 and \p r2 intersection is empty and the number of + elements in the span is equal to the sum of the number of + elements in \p r1 and \p r2. + + \verbatim + span(r1,r2) + <--------------------> + r1 r2 + [x--x--x] [x--x--x--x] + <------->-<----------> + ^ ^ ^ + | | | + | iota | + | | + length(r1) length(r2) + \endverbatim + + */ + template <typename T> + bool + are_adjacent(const interval<T>& r1, const interval<T>& r2); + + /* \brief Return true if \p r1 and \p r2 intersect. + */ + template <typename T> + bool + do_intersect(const interval<T>& r1, const interval<T>& r2); + + /* \brief Perform the intersection of \p r1 and \p r2. + */ + template <typename T> + interval<T> + inter(const interval<T>& r1, const interval<T>& r2); + + // min / max + + /*! \brief Re-implementation of the min function. + \sa math::min + */ + template <typename T> + interval<T> + min_(const interval<T>& r1, const interval<T>& r2); + + /*! \brief Re-implementation of the max function. + \sa math::max + */ + template <typename T> + interval<T> + max_(const interval<T>& r1, const interval<T>& r2); + + /// \brief Compute the span of \p r1 and \p r2. + template <typename T> + interval<T> + span(const interval<T>& r1, const interval<T>& r2); + + // op<< + + template <typename T> + std::ostream& + operator<<(std::ostream& ostr, const interval<T>& i); + + } // end of namespace mln::value + +} // end of namespace mln + + +// for sorting purpose + +namespace std +{ + + template <typename T> + struct less< mln::value::interval<T> > + { + bool operator()(const mln::value::interval<T>& l, + const mln::value::interval<T>& r) const; + }; + +} // std + # ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace value + { + + template <typename T> - inline - interval_<T>::interval_(const T& from, const T& to) - : from(from), - to(to) + interval<T>::interval() { - mln_precondition(from <= to); } template <typename T> - template <typename U> - inline - interval_<T>::operator interval_<U>() const + interval<T>::interval(T first, T last) { - mln_invariant(from <= to); - interval_<U> tmp(from, to); - mln_postcondition(tmp.from <= tmp.to); - return tmp; + mln_precondition(last >= first); + first_ = first; + last_ = last; + + nelements_ = 0; + for (T v = first_; v <= last_; value::inc(v)) + ++nelements_; } template <typename T> - inline - interval_<T> - interval(const T& from, const T& to) + interval<T>& + interval<T>::operator=(const interval& rhs) { - mln_precondition(from <= to); - interval_<T> tmp(from, to); - return tmp; + first_ = rhs.first_; + last_ = rhs.last_; + return *this; + } + + template <typename T> + bool + interval<T>::has(const T& v) const + { + return first_ <= v && v <= last_; + } + + template <typename T> + T + interval<T>::length() const + { + return last_ - first_; + } + + template <typename T> + T + interval<T>::ith_element(unsigned i) const + { + return first_ + i * iota<T>::value(); + } + + template <typename T> + unsigned + interval<T>::index_of(const T& v) const + { + return (v - first_) / iota<T>::value(); + } + + template <typename T> + unsigned + interval<T>::nelements() const + { + return nelements_; + } + + template <typename T> + bool + interval<T>::is_degenerated() const + { + return last_ == first_; + } + + template <typename T> + const T& + interval<T>::first() const + { + return first_; + } + + template <typename T> + const T& + interval<T>::last() const + { + return last_; + } + + + // comparison + + template <typename T> + bool + operator==(const interval<T>& lhs, const interval<T>& rhs) + { + return lhs.first() == rhs.first() && lhs.last() == rhs.last(); + } + + template <typename T> + bool + operator!=(const interval<T>& lhs, const interval<T>& rhs) + { + return ! (lhs == rhs); + } + + + // set ops + + template <typename T> + bool + are_adjacent(const interval<T>& r1, const interval<T>& r2) + { + return span(r1, r2).length() == r1.length() + r2.length() + + value::iota<T>::value(); + } + + template <typename T> + bool + do_intersect(const interval<T>& r1, const interval<T>& r2) + { + return span(r1, r2).length() <= r1.length() + r2.length(); + } + + template <typename T> + interval<T> + inter(const interval<T>& r1, const interval<T>& r2) + { + mln_precondition(do_intersect(r1, r2)); + return interval<T>(std::max(r1.first(), r2.first()), + std::min(r1.last(), r2.last())); + } + + + template <typename T> + interval<T> + min_(const interval<T>& r1, const interval<T>& r2) + { + return interval<T>(std::min(r1.first(), r2.first()), + std::min(r1.last(), r2.last())); + } + + template <typename T> + interval<T> + max_(const interval<T>& r1, const interval<T>& r2) + { + return interval<T>(std::max(r1.first(), r2.first()), + std::max(r1.last(), r2.last())); + } + + + // span + + template <typename T> + interval<T> + span(const interval<T>& r1, const interval<T>& r2) + { + return interval<T>(std::min(r1.first(), r2.first()), + std::max(r1.last(), r2.last())); + } + + + + // op<< + + template <typename T> + std::ostream& + operator<<(std::ostream& ostr, const interval<T>& i) + { + if (i.is_degenerated()) + return ostr << '{' << i.first() << '}'; + else + return ostr << '[' << i.first() << ',' << i.last() << ']'; } -# endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::value } // end of namespace mln -#endif // ! MLN_VALUE_INTERVAL_HH +namespace std +{ + + template <typename T> + bool less< mln::value::interval<T> >::operator()( + const mln::value::interval<T>& l, + const mln::value::interval<T>& r) const + { + mln_precondition(l.is_degenerated() && r.is_degenerated()); + return l.first() < r.first(); + } + +} // std + + +# endif // ! MLN_INCLUDE_ONLY + +#endif // ndef MLN_VALUE_INTERVAL_HH diff --git a/milena/mln/value/range.hh b/milena/mln/value/range.hh deleted file mode 100644 index 5c90de7..0000000 --- a/milena/mln/value/range.hh +++ /dev/null @@ -1,425 +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_VALUE_RANGE_HH -# define MLN_VALUE_RANGE_HH - -/// \file -/// -/// Define a range value. - -# include <cstdlib> -# include <iostream> -# include <mln/value/next.hh> - -namespace mln -{ - - namespace value - { - - template <typename T> - class range - { - public: - range(); - - template <typename T_> - range(T_ value); - - range(T lower, T upper); - - range& operator=(const range& rhs); - - template <typename T_> - range& operator=(T_ value); - - bool has(const T& v) const; - - T length() const; - - unsigned nelements() const; - - bool is_degenerated() const; - - const T& lower() const; - const T& upper() const; - - const T& first() const; - const T& last() const; - - operator T() const; - - private: - T lower_; - T upper_; - }; - -// comparison - - template <typename T> - bool - operator==(const range<T>& lhs, const range<T>& rhs); - - template <typename T> - bool - operator!=(const range<T>& lhs, const range<T>& rhs); - -// deactivation of ordering related operators - - template <typename T> - void operator<(const range<T>&, const range<T>&); - - template <typename T> - void operator<=(const range<T>&, const range<T>&); - - template <typename T> - void operator>(const range<T>&, const range<T>&); - - template <typename T> - void operator>=(const range<T>&, const range<T>&); - -// set ops - - template <typename T> - bool - are_adjacent(const range<T>& r1, const range<T>& r2); - - template <typename T> - bool - do_intersect(const range<T>& r1, const range<T>& r2); - - template <typename T> - range<T> - inter(const range<T>& r1, const range<T>& r2); - -// min / max - - template <typename T> - range<T> - min(const range<T>& r1, const range<T>& r2); - - template <typename T> - range<T> - max(const range<T>& r1, const range<T>& r2); - -// mean - - template <typename T> - range<T> - mean(const range<T>& r1, const range<T>& r2); - -// span - - template <typename T> - range<T> - span(const range<T>& r1, const range<T>& r2); - -// op<< - - template <typename T> - std::ostream& - operator<<(std::ostream& ostr, const range<T>& i); - - } // end of namespace mln::value - -} // end of namespace mln - - -// for sorting purpose - -namespace std -{ - - template <typename T> - struct less< mln::value::range<T> > - { - bool operator()(const mln::value::range<T>& l, - const mln::value::range<T>& r) const; - }; - -} // std - - - -# ifndef MLN_INCLUDE_ONLY - - -namespace mln -{ - - namespace value - { - - - template <typename T> - range<T>::range() - { - } - - template <typename T> - template <typename T_> - range<T>::range(T_ value) - { - lower_ = upper_ = value; - } - - template <typename T> - range<T>::range(T lower, T upper) - { - if (upper < lower) - std::abort(); - lower_ = lower; - upper_ = upper; - } - - template <typename T> - range<T>& - range<T>::operator=(const range& rhs) - { - lower_ = rhs.lower_; - upper_ = rhs.upper_; - return *this; - } - - template <typename T> - template <typename T_> - range<T>& - range<T>::operator=(T_ value) - { - lower_ = upper_ = value; - return *this; - } - - template <typename T> - bool - range<T>::has(const T& v) const - { - return lower_ <= v && v <= upper_; - } - - template <typename T> - T - range<T>::length() const - { - return upper_ - lower_; - } - - template <typename T> - unsigned - range<T>::nelements() const - { - unsigned n = 1; - T v = lower_; - for (; v != upper_; v = value::succ(v)) - n += 1; - - return n; - } - - template <typename T> - bool - range<T>::is_degenerated() const - { - return upper_ == lower_; - } - - template <typename T> - const T& - range<T>::lower() const - { - return lower_; - } - - template <typename T> - const T& - range<T>::upper() const - { - return upper_; - } - - template <typename T> - const T& - range<T>::first() const - { - return lower_; - } - - template <typename T> - const T& - range<T>::last() const - { - return upper_; - } - - template <typename T> - range<T>::operator T() const - { - if (! is_degenerated()) - std::abort(); - return upper_; - } - - -// comparison - - template <typename T> - bool - operator==(const range<T>& lhs, const range<T>& rhs) - { - return lhs.lower() == rhs.lower() && lhs.upper() == rhs.upper(); - } - - template <typename T> - bool - operator!=(const range<T>& lhs, const range<T>& rhs) - { - return ! (lhs == rhs); - } - - -// deactivation of ordering related operators - - template <typename T> - void operator<(const range<T>&, const range<T>&); - - template <typename T> - void operator<=(const range<T>&, const range<T>&); - - template <typename T> - void operator>(const range<T>&, const range<T>&); - - template <typename T> - void operator>=(const range<T>&, const range<T>&); - - - -// set ops - - template <typename T> - bool - are_adjacent(const range<T>& r1, const range<T>& r2) - { - return span(r1, r2).length() == r1.length() + r2.length() - + (value::succ(r2.lower()) - r2.lower()); - } - - template <typename T> - bool - do_intersect(const range<T>& r1, const range<T>& r2) - { - return span(r1, r2).length() <= r1.length() + r2.length(); - } - - template <typename T> - range<T> - inter(const range<T>& r1, const range<T>& r2) - { - if (! do_intersect(r1, r2)) - std::abort(); - return range<T>(std::max(r1.lower(), r2.lower()), - std::min(r1.upper(), r2.upper())); - } - - - -// min / max - - template <typename T> - range<T> - min(const range<T>& r1, const range<T>& r2) - { - return range<T>(std::min(r1.lower(), r2.lower()), - std::min(r1.upper(), r2.upper())); - } - - template <typename T> - range<T> - max(const range<T>& r1, const range<T>& r2) - { - return range<T>(std::max(r1.lower(), r2.lower()), - std::max(r1.upper(), r2.upper())); - } - - -// mean - - template <typename T> - range<T> - mean(const range<T>& r1, const range<T>& r2) - { - return range<T>(mean(r1.lower(), r2.lower()), - mean(r1.upper(), r2.upper())); - } - - -// span - - template <typename T> - range<T> - span(const range<T>& r1, const range<T>& r2) - { - return range<T>(std::min(r1.lower(), r2.lower()), - std::max(r1.upper(), r2.upper())); - } - - - -// op<< - - template <typename T> - std::ostream& - operator<<(std::ostream& ostr, const range<T>& i) - { - if (i.is_degenerated()) - return ostr << i.lower(); - else - return ostr << '[' << i.lower() << ',' << i.upper() << ']'; - } - - - } // end of namespace mln::value - -} // end of namespace mln - - -namespace std -{ - - template <typename T> - bool less< mln::value::range<T> >::operator()(const mln::value::range<T>& l, - const mln::value::range<T>& r) const - { - if (! l.is_degenerated() || ! r.is_degenerated()) - std::abort(); - return l.lower() < r.lower(); - } - -} // std - - -# endif // ! MLN_INCLUDE_ONLY - -#endif // ndef MLN_VALUE_RANGE_HH diff --git a/milena/tests/value/Makefile.am b/milena/tests/value/Makefile.am index 8d6718f..537eb76 100644 --- a/milena/tests/value/Makefile.am +++ b/milena/tests/value/Makefile.am @@ -1,4 +1,4 @@ -# Copyright (C) 2007, 2008, 2009 EPITA Research and Development +# Copyright (C) 2007, 2008, 2009, 2012 EPITA Research and Development # Laboratory (LRDE). # # This file is part of Olena. @@ -31,7 +31,7 @@ check_PROGRAMS = \ interop \ label \ proxy \ - range \ + interval \ rgb8 \ scalar \ set \ @@ -56,7 +56,7 @@ int_u8_SOURCES = int_u8.cc interop_SOURCES = interop.cc label_SOURCES = label.cc proxy_SOURCES = proxy.cc -range_SOURCES = range.cc +interval_SOURCES = interval.cc rgb8_SOURCES = rgb8.cc scalar_SOURCES = scalar.cc set_SOURCES = set.cc diff --git a/milena/tests/value/range.cc b/milena/tests/value/interval.cc similarity index 60% rename from milena/tests/value/range.cc rename to milena/tests/value/interval.cc index 22421ed..86b9a55 100644 --- a/milena/tests/value/range.cc +++ b/milena/tests/value/interval.cc @@ -29,16 +29,19 @@ #include <vector> #include <algorithm> -#include <mln/value/unsignedh.hh> -#include <mln/value/range.hh> +#include <mln/value/intsub.hh> +#include <mln/value/interval.hh> +#include <mln/value/inc.hh> -static const char *ref[] = { "1", "1.5", "2", "2.5", "3", "3.5", "4", "4.5", "5" }; +# include <mln/math/min.hh> +# include <mln/math/max.hh> int main() { using namespace mln::value; + using namespace mln; - typedef range<unsignedh> R; + typedef interval<intsub<2> > R; { R r(0, 0); @@ -63,9 +66,39 @@ int main() assert(r.length() == 4); assert(r.nelements() == 9); - int ref_i = 0; - for (unsignedh v = r.first(); v != r.last(); v.goto_succ()) - mln_assertion(static_cast<std::string>(v) == ref[ref_i++]); + int ref_i = 2; + for (intsub<2> v = r.first(); v <= r.last(); inc(v)) + mln_assertion(v.to_enc() == ref_i++); + } + + { + // are_adjacent / span / do_intersect + R r1(3, 4); + R r2(4.5, 6); + mln_assertion(r1 != r2); + mln_assertion(are_adjacent(r1, r2)); + mln_assertion(span(r1, r2) == R(3,6)); + mln_assertion(!do_intersect(r1, r2)); + + // Interset / Inter + R r3(1, 3.5); + mln_assertion(do_intersect(r1, r3)); + mln_assertion(inter(r1, r3) == R(3, 3.5)); + + // Min / Max + mln_assertion(math::min(r1, r3) == R(1, 3.5)); + mln_assertion(math::max(r1, r3) == R(3, 4)); + } + + // Access from/to indexes. + { + R r1(7.5, 11.5); + mln_assertion(r1.index_of(7.5) == 0); + mln_assertion(r1.index_of(9.5) == 4); + mln_assertion(r1.index_of(11.5) == 8); + mln_assertion(r1.ith_element(0) == 7.5); + mln_assertion(r1.ith_element(4) == 9.5); + mln_assertion(r1.ith_element(8) == 11.5); } } -- 1.7.2.5