[Olena-patches] 873: New rle_encode function.

Index: ChangeLog from Nicolas Ballas &lt;ballas(a)lrde.epita.fr&gt; New rle_encode function. * oln/core/encode, * oln/core/encode/rle_encode.hh: New encode/rle_encode.hh | 81 ++++++++++++++++++++++++++++++++++++++ rle/rle_image.hh | 34 ++++++++++------ rle/rle_pset.hh | 108 ++++++++++++++++++++++++++++++++++++--------------- rle/rle_psite.hh | 29 +------------ 4 files changed, 185 insertions(+), 67 deletions(-) Index: oln/core/rle/rle_image.hh --- oln/core/rle/rle_image.hh (revision 872) +++ oln/core/rle/rle_image.hh (working copy) @@ -67,7 +67,6 @@ typedef rle_psite<P> psite; typedef rle_pset<point> pset; -// typedef typename pset::box box; typedef mlc::none plain; @@ -75,7 +74,19 @@ }; - // Rle image class + /* + ** \class rle_image + ** \brief rle image (use a pair of point range and value as representation) + ** + ** method: + ** pset impl_points() const : return image pset + ** box impl_bbox() const : return image bbox + ** bool impl_has(const point& p) const : rle_image has p? + ** bool impl_owns_(const psite& p) const : same has impl_has + ** void insert(const point& p, unsigned len, value val) : insert a new range on the image + ** rvalue impl_read(const psite& p) const : return value associated to psite (for reading) + ** lvalue impl_read_write(const psite& p) : lvalue impl_read_write(const psite& p) (for writing) + */ template < typename P, typename T> class rle_image : public internal::primitive_image_< rle_image<P, T> > { @@ -136,7 +147,7 @@ bool rle_image<P, T>::impl_owns_(const typename rle_image<P, T>::psite& p) const { - return this->data_->first.has(p); + return this->data_->first.has(p.start_); } template <typename P, typename T> @@ -151,21 +162,22 @@ typename rle_image<P, T>::rvalue rle_image<P, T>::impl_read(const rle_image<P, T>::psite& ps) const { - // precondition(p.iterator_() != this->data_->second.end()); - return this->data_->second[ps]; + typename std::map<point, value>::const_iterator irun; + + irun = this->data_->second.find(ps.start_); + assert(irun != this->data_->second.end() && ps.index_ < this->data_->first.range_len_(ps.start_)); + return irun->second; } - int a = 5; template <typename P, typename T> typename rle_image<P, T>::lvalue rle_image<P, T>::impl_read_write(const rle_image<P, T>::psite& ps) { - std::cout << "read_write: " << std::endl; - std::cout << (point)ps << std::endl; + typename std::map<point, value>::iterator irun; - // precondition(p.iterator_() != this->data_->second.end()); - //return this->data_->second[ps]; - return a; + irun = this->data_->second.find(ps.start_); + assert(irun != this->data_->second.end() && ps.index_ < this->data_->first.range_len_(ps.start_)); + return irun->second; } # endif // !OLN_INCLUDE_ONLY Index: oln/core/rle/rle_psite.hh --- oln/core/rle/rle_psite.hh (revision 872) +++ oln/core/rle/rle_psite.hh (working copy) @@ -43,16 +43,16 @@ ** \class rle_piste ** \brief psite for rle image ** - ** - ** + ** Note: P must be a point type + ** method: + ** to_point: convert the psite to corresponding point + ** operator P(): convert psite to the corresponding point */ template <typename P> class rle_psite { public: rle_psite(); - // template <typename T> -// rle_psite(const rle_image<P, T>& ima, const P& p); P to_point() const; operator P () const; @@ -68,27 +68,6 @@ { } -// template <typename P> -// template <typename T> -// rle_psite<P>::rle_psite(const rle_image<P, T>& ima, const P& p) : start_(p) -// { -// P pend; - -// typename rle_image<P, T>::piter it (ima.points()); - -// for (it.start(); it.is_valid(); it.next()) -// { -// pend = it; -// pend[0] += it->second - 1; -// if (*it >= p && p <= pend) -// { -// this->start_ = it->first; -// this->index_ = it->second - this->start[0]; -// } -// } -// } - - template <typename P> P rle_psite<P>::to_point() const Index: oln/core/rle/rle_pset.hh --- oln/core/rle/rle_pset.hh (revision 872) +++ oln/core/rle/rle_pset.hh (working copy) @@ -47,21 +47,38 @@ template <typename P> struct rle_pset_fwd_piter_; template <typename P> struct rle_pset_bkd_piter_; + // Super type. + template <typename P> + struct super_trait_< rle_pset<P> > + { + typedef rle_pset<P> current; + typedef internal::point_set_base_<current> ret; + }; + // Vtypes associated to rle_pset class template <typename P> struct vtypes< rle_pset<P> > { typedef P point; - typedef typename P::grid grid; - - typedef box_<point> box; typedef rle_pset_fwd_piter_<P> fwd_piter; typedef rle_pset_bkd_piter_<P> bkd_piter; - typedef fwd_piter piter; }; // rle_pset class + /* + ** \class rle_pset + ** \brief pset correspoding to the rle_image class + ** + ** Note: P must be a point type + ** method: + ** unsigned impl_npoints() const : return number of point in the point set + ** const box& impl_bbox() const : return a box which includes all poin into the set + ** void insert(const P& p, unsigned len): insert a new range on the point set + ** bool impl_has(const P& p) const : if p include in the set + ** const std_container& con() const : return the container of the point + ** + */ template <typename P> class rle_pset : public internal::point_set_base_<rle_pset <P> > { @@ -81,11 +98,11 @@ bool impl_has(const P& p) const; const std_container& con() const; - unsigned range_len_(const P& range_start); + unsigned range_len_(const P& range_len_) const; protected: - unsigned npts; - std_container con_; - fbbox_<point> fb_; + unsigned npts; /*!< number of point in the set*/ + std_container con_; /*!< container of the set*/ + fbbox_<point> fb_; /*!< pset box*/ }; @@ -133,18 +150,10 @@ bool rle_pset<P>::impl_has(const P& p) const { - P pend; + typename std_container::const_iterator irun; - typename std_container::const_iterator iter; - - for (iter = con_.begin(); iter != con_.end(); ++iter ) - { - pend = iter->first; - pend[0] += iter->second - 1; - if (iter->first >= p && p <= pend) - return 1; - } - return 0; + irun = this->con_.find(p); + return irun != this->con_.end(); } template <typename P> @@ -156,9 +165,13 @@ template <typename P> unsigned - rle_pset<P>::range_len_(const P& range_start) + rle_pset<P>::range_len_(const P& range_start) const { - return this->con_[range_start]; + typename std_container::const_iterator irun; + + irun = this->con_.find(range_start); + assert(irun != this->con_.end()); + return (irun->second); } # endif // !OLN_INCLUDE_ONLY @@ -166,11 +179,18 @@ // end of rle_pset class // -------------------- iterators on classes deriving from internal::rle_pset<P> - // Forward declaration template <typename P> class rle_pset_fwd_piter_; + // Super type. + template <typename P> + struct super_trait_< rle_pset_fwd_piter_<P> > + { + typedef rle_pset_fwd_piter_<P> current; + typedef Iterator_on_Points<current> ret; + }; + // Virtual types template <typename P> struct vtypes< rle_pset_fwd_piter_<P> > @@ -179,6 +199,18 @@ }; // class rle_pset_fwd_iterator_ + /* + ** \class rle_pset_fwd_piter_ + ** \brief foward iterator for rle_pset + ** + ** P must be a point type + ** method: + ** void impl_start(): set the iterator to the start of pset + ** void impl_next(): go to next point + ** void impl_invalidate(): invalidate iterator + ** void impl_valid(): is the iterator valid? + ** + conversions methods + */ template <typename P> class rle_pset_fwd_piter_ : public Iterator_on_Points< rle_pset_fwd_piter_<P> > { @@ -203,7 +235,7 @@ protected: const typename rle_pset<P>::std_container& con_; typename rle_pset<P>::std_container::const_iterator it_; - rle_psite<P> ps_; + rle_psite<P> ps_; /*!< current point */ }; # ifndef OLN_INCLUDE_ONLY @@ -229,11 +261,8 @@ { precondition(this->is_valid()); - std::cout << "next: " << std::endl; - std::cout << "point start: " << ps_.start_ << " index: " << ps_.index_ << std::endl; - std::cout << "point start: " << it_->first << " index: " << it_->second << " ref" << std::endl; - ++this->ps_.index_; + if (this->ps_.index_ >= this->it_->second) { ++it_; @@ -291,6 +320,14 @@ template <typename P> class rle_pset_bkd_piter_; + // Super type. + template <typename P> + struct super_trait_< rle_pset_bkd_piter_<P> > + { + typedef rle_pset_bkd_piter_<P> current; + typedef Iterator_on_Points<current> ret; + }; + // Virtual type template <typename P> struct vtypes< rle_pset_bkd_piter_<P> > @@ -298,8 +335,18 @@ typedef P point; }; - // class rle_pset_bkd_piter_ - + /* + ** \class rle_pset_bkd_piter_ + ** \brief backward iterator for rle_pset + ** + ** P must be a point type + ** method: + ** void impl_start(): set the iterator to the start of pset + ** void impl_next(): go to next point + ** void impl_invalidate(): invalidate iterator + ** void impl_valid(): is the iterator valid? + ** + conversion method + */ template <typename P> class rle_pset_bkd_piter_ : public Iterator_on_Points< rle_pset_bkd_piter_<P> > { @@ -322,7 +369,7 @@ protected: const typename rle_pset<P>::std_container& con_; typename rle_pset<P>::std_container::const_reverse_iterator it_; - rle_psite<P> ps_; + rle_psite<P> ps_; /*!< current point*/ }; # ifndef OLN_INCLUDE_ONLY @@ -350,7 +397,6 @@ --ps_.index_; - // ps.index_ is unsigned if (ps_.index_ + 1 == 0) { ++it_; Index: oln/core/encode/rle_encode.hh --- oln/core/encode/rle_encode.hh (revision 0) +++ oln/core/encode/rle_encode.hh (revision 0) @@ -0,0 +1,81 @@ +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 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 RLE_ENCODE_HH_ +# define RLE_ENCODE_HH_ + +# include <oln/core/concept/image.hh> + +# include <oln/core/rle/rle_image.hh> + +namespace oln +{ + + /*! + ** encode an image class to a rle_image + ** + ** @param input has to respect the Image concept + ** + ** @return rle_image + */ + template <typename I> + rle_image<typename Image<I>::point, typename I::value> + rle_encode(const Image<I>& input) + { + rle_image<typename I::point, typename I::value> output; + typename I::piter p (input.points()); + unsigned len = 1; + typename I::point rstart; /*!< range pointstart */ + typename I::value rvalue; /*!< range value */ + + p.start(); + if (!p.is_valid()) + return output; + + rstart = p; + rvalue = input(p); + p.next(); + while (p.is_valid()) + { + if (rvalue == input(p)) + ++len; + else + { + output.insert(rstart, len, rvalue); + len = 1; + rstart = p; + rvalue = input(p); + } + p.next(); + } + output.insert(rstart, len, rvalue); + return output; + } +} // end of namespace oln + +#endif /* !RLE_ENCODE_HH_ */