Generic Image Library : algorithm.hpp Source File

00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003    
00004     Use, modification and distribution are subject to the Boost Software License,
00005     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
00006     http://www.boost.org/LICENSE_1_0.txt).
00007 
00008     See http://opensource.adobe.com/gil for most recent version including documentation.
00009 */
00010 
00011 
00012 /*************************************************************************************************/
00013 
00014 #ifndef GIL_ALGORITHM_HPP
00015 #define GIL_ALGORITHM_HPP
00016 
00017 #include <cassert>
00018 #include <cstddef>
00019 #include <algorithm>
00020 #include <iterator>
00021 #include <memory>
00022 #include "gil_config.hpp"
00023 #include "gil_concept.hpp"
00024 #include "color_base_algorithm.hpp"
00025 #include "image_view.hpp"
00026 #include "image_view_factory.hpp"
00027 #include "bit_aligned_pixel_iterator.hpp"
00028 
00037 
00038 #ifdef _MSC_VER
00039 #pragma warning(push)
00040 #pragma warning(disable : 4244)     // conversion from 'gil::image<V,Alloc>::coord_t' to 'int', possible loss of data (visual studio compiler doesn't realize that the two types are the same)
00041 #endif
00042 
00043 namespace boost { namespace gil {
00044 
00045 //forward declarations
00046 template <typename ChannelPtr, typename ColorSpace>
00047 struct planar_pixel_iterator;
00048 template <typename Iterator>
00049 class memory_based_step_iterator;
00050 template <typename StepIterator>
00051 class memory_based_2d_locator;
00052 
00053 // a tag denoting incompatible arguments
00054 struct error_t {};
00055 
00080 
00081 
00085 
00094 template <typename Derived, typename Result=void>
00095 struct binary_operation_obj {
00096     typedef Result result_type;
00097 
00098     template <typename V1, typename V2> GIL_FORCEINLINE
00099     result_type operator()(const std::pair<const V1*,const V2*>& p) const {
00100         return apply(*p.first, *p.second, typename views_are_compatible<V1,V2>::type());
00101     }
00102 
00103     template <typename V1, typename V2> GIL_FORCEINLINE
00104     result_type operator()(const V1& v1, const V2& v2) const {
00105         return apply(v1, v2, typename views_are_compatible<V1,V2>::type());
00106     }
00107 
00108     result_type operator()(const error_t&) const { throw std::bad_cast(); }
00109 private:
00110 
00111     // dispatch from apply overload to a function with distinct name
00112     template <typename V1, typename V2>
00113     GIL_FORCEINLINE result_type apply(const V1& v1, const V2& v2, mpl::false_) const {
00114         return ((const Derived*)this)->apply_incompatible(v1,v2);
00115     }
00116 
00117     // dispatch from apply overload to a function with distinct name
00118     template <typename V1, typename V2>
00119     GIL_FORCEINLINE result_type apply(const V1& v1, const V2& v2, mpl::true_) const {
00120         return ((const Derived*)this)->apply_compatible(v1,v2);
00121     }
00122 
00123     // function with distinct name - it can be overloaded by subclasses
00124     template <typename V1, typename V2>
00125     GIL_FORCEINLINE result_type apply_incompatible(const V1& v1, const V2& v2) const {
00126         throw std::bad_cast();
00127     }
00128 };
00129 } }  // namespace boost::gil
00130 
00136 
00140 
00141 namespace std {
00142 
00145 template<typename T, typename Cs> 
00146 GIL_FORCEINLINE boost::gil::pixel<T,Cs>* 
00147 copy(boost::gil::pixel<T,Cs>* first, boost::gil::pixel<T,Cs>* last, 
00148      boost::gil::pixel<T,Cs>* dst) { 
00149     return (boost::gil::pixel<T,Cs>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
00150 }
00151 
00154 template<typename T, typename Cs> 
00155 GIL_FORCEINLINE boost::gil::pixel<T,Cs>* 
00156 copy(const boost::gil::pixel<T,Cs>* first, const boost::gil::pixel<T,Cs>* last, 
00157      boost::gil::pixel<T,Cs>* dst) { 
00158     return (boost::gil::pixel<T,Cs>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
00159 }
00160 } // namespace std
00161 
00162 namespace boost { namespace gil {
00163 namespace detail {
00164 template <typename I, typename O> struct copy_fn { 
00165     GIL_FORCEINLINE I operator()(I first, I last, O dst) const { return std::copy(first,last,dst); } 
00166 };
00167 } // namespace detail
00168 } }  // namespace boost::gil
00169 
00170 namespace std {
00173 template<typename Cs, typename IC1, typename IC2> GIL_FORCEINLINE
00174 boost::gil::planar_pixel_iterator<IC2,Cs> copy(boost::gil::planar_pixel_iterator<IC1,Cs> first, boost::gil::planar_pixel_iterator<IC1,Cs> last, boost::gil::planar_pixel_iterator<IC2,Cs> dst) { 
00175     boost::gil::gil_function_requires<boost::gil::ChannelsCompatibleConcept<typename std::iterator_traits<IC1>::value_type,typename std::iterator_traits<IC2>::value_type> >();
00176     static_for_each(first,last,dst,boost::gil::detail::copy_fn<IC1,IC2>());
00177     return dst+(last-first);
00178 }
00179 } // namespace std
00180 
00181 namespace boost { namespace gil {
00182 namespace detail {
00185 template <typename I, typename O>
00186 struct copier_n {
00187     GIL_FORCEINLINE void operator()(I src, typename std::iterator_traits<I>::difference_type n, O dst) const { std::copy(src,src+n, dst); }
00188 };
00189 
00191 template <typename IL, typename O>  // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
00192 struct copier_n<iterator_from_2d<IL>,O> {
00193     typedef typename std::iterator_traits<iterator_from_2d<IL> >::difference_type diff_t;
00194     GIL_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, O dst) const {
00195         gil_function_requires<PixelLocatorConcept<IL> >();
00196         gil_function_requires<MutablePixelIteratorConcept<O> >();
00197         while (n>0) {
00198             typedef typename iterator_from_2d<IL>::difference_type diff_t;
00199             diff_t l=src.width()-src.x_pos();
00200             diff_t numToCopy=(n<l ? n:l);
00201             detail::copy_n(src.x(), numToCopy, dst);
00202             dst+=numToCopy;
00203             src+=numToCopy;
00204             n-=numToCopy;
00205         }
00206     }
00207 };
00208 
00210 template <typename I, typename OL> // I Models ConstPixelIteratorConcept, OL Models PixelLocatorConcept
00211 struct copier_n<I,iterator_from_2d<OL> > {
00212     typedef typename std::iterator_traits<I>::difference_type diff_t;
00213     GIL_FORCEINLINE void operator()(I src, diff_t n, iterator_from_2d<OL> dst) const {
00214         gil_function_requires<PixelIteratorConcept<I> >();
00215         gil_function_requires<MutablePixelLocatorConcept<OL> >();
00216         while (n>0) {
00217             diff_t l=dst.width()-dst.x_pos();
00218             diff_t numToCopy=(n<l ? n:l);
00219             detail::copy_n(src, numToCopy, dst.x());
00220             dst+=numToCopy;
00221             src+=numToCopy;
00222             n-=numToCopy;
00223         }
00224     }
00225 };
00226 
00228 template <typename IL, typename OL>
00229 struct copier_n<iterator_from_2d<IL>,iterator_from_2d<OL> > {
00230    typedef typename iterator_from_2d<IL>::difference_type diff_t;
00231    GIL_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, iterator_from_2d<OL> dst) const {
00232         gil_function_requires<PixelLocatorConcept<IL> >();
00233         gil_function_requires<MutablePixelLocatorConcept<OL> >();
00234         if (src.x_pos()!=dst.x_pos() || src.width()!=dst.width()) {
00235             while(n-->0) {
00236                 *dst++=*src++;
00237             }
00238         }
00239         while (n>0) {
00240             diff_t l=dst.width()-dst.x_pos();
00241             diff_t numToCopy=(n<l ? n : l);
00242             detail::copy_n(src.x(), numToCopy, dst.x());
00243             dst+=numToCopy;
00244             src+=numToCopy;
00245             n-=numToCopy;
00246         }
00247     }
00248 };
00249 
00250 template <typename SrcIterator, typename DstIterator>
00251 GIL_FORCEINLINE DstIterator copy_with_2d_iterators(SrcIterator first, SrcIterator last, DstIterator dst) {
00252     typedef typename SrcIterator::x_iterator src_x_iterator;
00253     typedef typename DstIterator::x_iterator dst_x_iterator;
00254 
00255     typename SrcIterator::difference_type n = last - first;
00256 
00257     if (first.is_1d_traversable()) {
00258         if (dst.is_1d_traversable())
00259             copier_n<src_x_iterator,dst_x_iterator>()(first.x(),n, dst.x());
00260         else
00261             copier_n<src_x_iterator,DstIterator >()(first.x(),n, dst);
00262     } else {
00263         if (dst.is_1d_traversable())
00264             copier_n<SrcIterator,dst_x_iterator>()(first,n, dst.x());
00265         else
00266             copier_n<SrcIterator,DstIterator>()(first,n,dst);
00267     }
00268     return dst+n;
00269 }
00270 
00271 } // namespace detail
00272 } }  // namespace boost::gil
00273 
00274 namespace std {
00277 template <typename IL, typename OL>
00278 GIL_FORCEINLINE boost::gil::iterator_from_2d<OL> copy1(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, boost::gil::iterator_from_2d<OL> dst) {
00279     return boost::gil::detail::copy_with_2d_iterators(first,last,dst);
00280 }
00281 
00282 } // namespace std
00283 
00284 namespace boost { namespace gil {
00285 
00286 
00289 template <typename View1, typename View2> GIL_FORCEINLINE
00290 void copy_pixels(const View1& src, const View2& dst) { 
00291     assert(src.dimensions()==dst.dimensions());
00292     detail::copy_with_2d_iterators(src.begin(),src.end(),dst.begin());
00293 }
00294 
00300 
00306 
00307 namespace detail {
00308 template <typename CC>
00309 class copy_and_convert_pixels_fn : public binary_operation_obj<copy_and_convert_pixels_fn<CC> > {
00310 private:
00311     CC _cc;
00312 public:
00313     typedef typename binary_operation_obj<copy_and_convert_pixels_fn<CC> >::result_type result_type;
00314     copy_and_convert_pixels_fn() {}
00315     copy_and_convert_pixels_fn(CC cc_in) : _cc(cc_in) {}
00316    // when the two color spaces are incompatible, a color conversion is performed
00317     template <typename V1, typename V2> GIL_FORCEINLINE 
00318     result_type apply_incompatible(const V1& src, const V2& dst) const {
00319         copy_pixels(color_converted_view<typename V2::value_type>(src,_cc),dst);
00320     }
00321 
00322     // If the two color spaces are compatible, copy_and_convert is just copy
00323     template <typename V1, typename V2> GIL_FORCEINLINE 
00324     result_type apply_compatible(const V1& src, const V2& dst) const {
00325          copy_pixels(src,dst);
00326     }
00327 };
00328 } // namespace detail
00329 
00331 template <typename V1, typename V2,typename CC> 
00332 GIL_FORCEINLINE 
00333 void copy_and_convert_pixels(const V1& src, const V2& dst,CC cc) { 
00334     detail::copy_and_convert_pixels_fn<CC> ccp(cc);
00335     ccp(src,dst);
00336 }
00337 
00338 struct default_color_converter;
00339 
00341 template <typename View1, typename View2> 
00342 GIL_FORCEINLINE 
00343 void copy_and_convert_pixels(const View1& src, const View2& dst) { 
00344     detail::copy_and_convert_pixels_fn<default_color_converter> ccp;
00345     ccp(src,dst);
00346 }
00347 
00348 } }  // namespace boost::gil
00349 
00351 //
00352 // std::fill and gil::fill_pixels
00353 //
00355 
00359 
00360 
00361 namespace std {
00370 template <typename IL, typename V>
00371 void fill(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, const V& val) {
00372     boost::gil::gil_function_requires<boost::gil::MutablePixelLocatorConcept<IL> >();
00373     if (first.is_1d_traversable()) {
00374         std::fill(first.x(), last.x(), val);
00375     } else {
00376         // fill row by row
00377         std::ptrdiff_t n=last-first;
00378         while (n>0) {
00379             std::ptrdiff_t numToDo=std::min<const std::ptrdiff_t>(n,(std::ptrdiff_t)(first.width()-first.x_pos()));
00380             fill_n(first.x(), numToDo, val);
00381             first+=numToDo;
00382             n-=numToDo;
00383         }
00384     }
00385 } 
00386 } // namespace std
00387 
00388 namespace boost { namespace gil {
00389 
00390 namespace detail {
00392 struct std_fill_t {
00393     template <typename It, typename P>
00394     void operator()(It first, It last, const P& p_in) {
00395         std::fill(first,last,p_in);
00396     }
00397 };
00399 template <typename It, typename P>
00400 GIL_FORCEINLINE 
00401 void fill_aux(It first, It last, const P& p, mpl::true_) {
00402     static_for_each(first,last,p,std_fill_t());
00403 }
00405 template <typename It, typename P>
00406 GIL_FORCEINLINE 
00407 void fill_aux(It first, It last, const P& p,mpl::false_) {
00408     std::fill(first,last,p);
00409 }
00410 } // namespace detail
00411 
00414 template <typename View, typename Value> GIL_FORCEINLINE 
00415 void fill_pixels(const View& img_view, const Value& val) {
00416     if (img_view.is_1d_traversable())
00417         detail::fill_aux(img_view.begin().x(), img_view.end().x(), 
00418                  val,is_planar<View>());
00419     else
00420         for (std::ptrdiff_t y=0; y<img_view.height(); ++y)
00421             detail::fill_aux(img_view.row_begin(y),img_view.row_end(y),
00422                      val,is_planar<View>());
00423 }
00424 
00430 
00434 
00435 
00436 namespace detail {
00437 
00438 template <typename It> GIL_FORCEINLINE
00439 void destruct_range_impl(It first, It last, mpl::true_) {
00440     typedef typename std::iterator_traits<It>::value_type value_t;
00441     if (boost::has_trivial_destructor<value_t>::value)
00442         return;
00443     while (first!=last) {
00444         first->~value_t();
00445         ++first;
00446     }
00447 }
00448 template <typename It> GIL_FORCEINLINE
00449 void destruct_range_impl(It first, It last, mpl::false_) {}
00450 
00451 template <typename It> GIL_FORCEINLINE
00452 void destruct_range(It first, It last) {
00453     destruct_range_impl(first,last,typename is_pointer<It>::type());
00454 }
00455 
00456 struct std_destruct_t {
00457     template <typename It> void operator()(It first, It last) const { destruct_range(first,last); }
00458 };
00459 
00461 template <typename It>
00462 GIL_FORCEINLINE 
00463 void destruct_aux(It first, It last, mpl::true_) {
00464     static_for_each(first,last,std_destruct_t());
00465 }
00467 template <typename It>
00468 GIL_FORCEINLINE 
00469 void destruct_aux(It first, It last, mpl::false_) {
00470     destruct_range(first,last);
00471 }
00472 
00473 } // namespace detail
00474 
00477 template <typename View> GIL_FORCEINLINE 
00478 void destruct_pixels(const View& img_view) {
00479     if (img_view.is_1d_traversable()) 
00480         detail::destruct_aux(img_view.begin().x(), img_view.end().x(), 
00481                                        is_planar<View>());
00482     else
00483         for (std::ptrdiff_t y=0; y<img_view.height(); ++y)
00484             detail::destruct_aux(img_view.row_begin(y),img_view.row_end(y),
00485                                            is_planar<View>());
00486 }
00487 
00493 
00497 
00498 
00499 namespace detail {
00500 
00503 template <typename It, typename P>
00504 GIL_FORCEINLINE 
00505 void uninitialized_fill_aux(It first, It last,
00506                             const P& p, mpl::true_) {
00507     int channel=0;
00508     try {
00509         typedef typename std::iterator_traits<It>::value_type pixel_t;
00510         while (channel < num_channels<pixel_t>::value) {
00511             std::uninitialized_fill(dynamic_at_c(first,channel), dynamic_at_c(last,channel), 
00512                                     dynamic_at_c(p,channel));
00513             ++channel;
00514         }
00515     } catch (...) {
00516         for (int c=0; c<channel; ++c)
00517             destruct_range(dynamic_at_c(first,c), dynamic_at_c(last,c));
00518         throw;
00519     }
00520 }
00521 
00524 template <typename It, typename P>
00525 GIL_FORCEINLINE 
00526 void uninitialized_fill_aux(It first, It last,
00527                             const P& p,mpl::false_) {
00528     std::uninitialized_fill(first,last,p);
00529 }
00530 
00531 } // namespace detail
00532 
00537 template <typename View, typename Value> 
00538 void uninitialized_fill_pixels(const View& img_view, const Value& val) {
00539     if (img_view.is_1d_traversable()) 
00540         detail::uninitialized_fill_aux(img_view.begin().x(), img_view.end().x(), 
00541                                        val,is_planar<View>());
00542     else {
00543         typename View::y_coord_t y;
00544         try {
00545             for (y=0; y<img_view.height(); ++y)
00546                 detail::uninitialized_fill_aux(img_view.row_begin(y),img_view.row_end(y),
00547                                                val,is_planar<View>());
00548         } catch(...) {
00549             for (typename View::y_coord_t y0=0; y0<y; ++y0)
00550                 detail::destruct_aux(img_view.row_begin(y0),img_view.row_end(y0), is_planar<View>());
00551             throw;
00552         }
00553     }
00554 }
00555 
00561 
00565 
00566 namespace detail {
00567 
00568 template <typename It> GIL_FORCEINLINE 
00569 void default_construct_range_impl(It first, It last, mpl::true_) {
00570     typedef typename std::iterator_traits<It>::value_type value_t;
00571     It first1=first;
00572     try {
00573         while (first!=last) {
00574             new (first) value_t();
00575             ++first;
00576         }
00577     } catch (...) {
00578         destruct_range(first1,first);
00579         throw;
00580     }
00581 }
00582 
00583 template <typename It> GIL_FORCEINLINE 
00584 void default_construct_range_impl(It first, It last, mpl::false_) {}
00585 
00586 template <typename It> GIL_FORCEINLINE 
00587 void default_construct_range(It first, It last) { default_construct_range_impl(first, last, typename is_pointer<It>::type()); }
00588 
00590 template <typename It>
00591 GIL_FORCEINLINE 
00592 void default_construct_aux(It first, It last, mpl::true_) {
00593     int channel=0;
00594     try {
00595         typedef typename std::iterator_traits<It>::value_type pixel_t;
00596         while (channel < num_channels<pixel_t>::value) {
00597             default_construct_range(dynamic_at_c(first,channel), dynamic_at_c(last,channel));
00598             ++channel;
00599         }
00600     } catch (...) {
00601         for (int c=0; c<channel; ++c)
00602             destruct_range(dynamic_at_c(first,c), dynamic_at_c(last,c));
00603         throw;
00604     }
00605 }
00606 
00608 template <typename It>
00609 GIL_FORCEINLINE 
00610 void default_construct_aux(It first, It last, mpl::false_) {
00611     default_construct_range(first,last);
00612 }
00613 
00614 template <typename View, bool IsPlanar>
00615 struct has_trivial_pixel_constructor : public boost::has_trivial_constructor<typename View::value_type> {};
00616 template <typename View>
00617 struct has_trivial_pixel_constructor<View, true> : public boost::has_trivial_constructor<typename channel_type<View>::type> {};
00618 
00619 } // namespace detail
00620 
00625 template <typename View> 
00626 void default_construct_pixels(const View& img_view) {
00627     if (detail::has_trivial_pixel_constructor<View, is_planar<View>::value>::value)
00628         return;
00629 
00630     if (img_view.is_1d_traversable()) 
00631         detail::default_construct_aux(img_view.begin().x(), img_view.end().x(), is_planar<View>());
00632     else {
00633         typename View::y_coord_t y;
00634         try {
00635             for (y=0; y<img_view.height(); ++y)
00636                 detail::default_construct_aux(img_view.row_begin(y),img_view.row_end(y), is_planar<View>());
00637         } catch(...) {
00638             for (typename View::y_coord_t y0=0; y0<y; ++y0)
00639                 detail::destruct_aux(img_view.row_begin(y0),img_view.row_end(y0), is_planar<View>());
00640             throw;
00641         }
00642     }
00643 }
00644 
00645 
00651 
00655 
00656 namespace detail {
00657 
00659 template <typename It1, typename It2>
00660 GIL_FORCEINLINE 
00661 void uninitialized_copy_aux(It1 first1, It1 last1,
00662                             It2 first2, mpl::true_) {
00663     int channel=0;
00664     try {
00665         typedef typename std::iterator_traits<It1>::value_type pixel_t;
00666         while (channel < num_channels<pixel_t>::value) {
00667             std::uninitialized_copy(dynamic_at_c(first1,channel), dynamic_at_c(last1,channel), dynamic_at_c(first2,channel));
00668             ++channel;
00669         }
00670     } catch (...) {
00671         It2 last2=first2;
00672         std::advance(last2, std::distance(first1,last1));
00673         for (int c=0; c<channel; ++c)
00674             destruct_range(dynamic_at_c(first2,c), dynamic_at_c(last2,c));
00675         throw;
00676     }
00677 }
00679 template <typename It1, typename It2>
00680 GIL_FORCEINLINE 
00681 void uninitialized_copy_aux(It1 first1, It1 last1,
00682                             It2 first2,mpl::false_) {
00683     std::uninitialized_copy(first1,last1,first2);
00684 }
00685 } // namespace detail
00686 
00691 template <typename View1, typename View2> 
00692 void uninitialized_copy_pixels(const View1& view1, const View2& view2) {
00693     typedef mpl::bool_<is_planar<View1>::value && is_planar<View2>::value> is_planar;  
00694     assert(view1.dimensions()==view2.dimensions());
00695     if (view1.is_1d_traversable() && view2.is_1d_traversable())
00696         detail::uninitialized_copy_aux(view1.begin().x(), view1.end().x(), 
00697                                        view2.begin().x(), 
00698                                        is_planar());
00699     else {
00700         typename View1::y_coord_t y;
00701         try {
00702             for (y=0; y<view1.height(); ++y)
00703                 detail::uninitialized_copy_aux(view1.row_begin(y), view1.row_end(y),
00704                                                view2.row_begin(y),
00705                                                is_planar());
00706         } catch(...) {
00707             for (typename View1::y_coord_t y0=0; y0<y; ++y0)
00708                 detail::destruct_aux(view2.row_begin(y0),view2.row_end(y0), is_planar());
00709             throw;
00710         }
00711     }
00712 }
00713 
00719 
00728 
00730 template <typename V, typename F>
00731 F for_each_pixel(const V& img, F fun) {
00732     if (img.is_1d_traversable()) {
00733         return std::for_each(img.begin().x(), img.end().x(), fun);
00734     } else {
00735         for (std::ptrdiff_t y=0; y<img.height(); ++y)
00736             fun = std::for_each(img.row_begin(y),img.row_end(y),fun);
00737         return fun;
00738     }
00739 }
00740 
00744 
00746 template <typename View, typename F>
00747 F for_each_pixel_position(const View& img, F fun) {
00748     typename View::xy_locator loc=img.xy_at(0,0);
00749     for (std::ptrdiff_t y=0; y<img.height(); ++y) {
00750         for (std::ptrdiff_t x=0; x<img.width(); ++x, ++loc.x())
00751             fun(loc);
00752         loc.x()-=img.width(); ++loc.y();
00753     }
00754     return fun;
00755 }
00756 
00757 
00763 
00767 
00770 template <typename View, typename F>
00771 void generate_pixels(const View& v, F fun) {
00772     if (v.is_1d_traversable()) {
00773         std::generate(v.begin().x(), v.end().x(), fun);
00774     } else {
00775         for (std::ptrdiff_t y=0; y<v.height(); ++y)
00776             std::generate(v.row_begin(y),v.row_end(y),fun);
00777     }
00778 }
00779 
00785 
00789 
00790 template <typename I1, typename I2> GIL_FORCEINLINE bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2);
00791 
00792 namespace detail {
00793 
00794 template <typename I1, typename I2>
00795 struct equal_n_fn {
00796     GIL_FORCEINLINE bool operator()(I1 i1, std::ptrdiff_t n, I2 i2) const { return std::equal(i1,i1+n, i2); }
00797 };
00798 
00801 template<typename T, typename Cs>
00802 struct equal_n_fn<const pixel<T,Cs>*, const pixel<T,Cs>*> {
00803     GIL_FORCEINLINE bool operator()(const pixel<T,Cs>* i1, std::ptrdiff_t n, const pixel<T,Cs>* i2) const { 
00804         return memcmp(i1, i2, n*sizeof(pixel<T,Cs>))==0;
00805     }
00806 };
00807 template<typename T, typename Cs>
00808 struct equal_n_fn<pixel<T,Cs>*, pixel<T,Cs>*> : equal_n_fn<const pixel<T,Cs>*, const pixel<T,Cs>*> {};
00809 
00813 template<typename IC, typename Cs>
00814 struct equal_n_fn<planar_pixel_iterator<IC,Cs>, planar_pixel_iterator<IC,Cs> > {
00815     GIL_FORCEINLINE bool operator()(const planar_pixel_iterator<IC,Cs> i1, std::ptrdiff_t n, const planar_pixel_iterator<IC,Cs> i2) const { 
00816         ptrdiff_t numBytes=n*sizeof(typename std::iterator_traits<IC>::value_type);
00817 
00818         for (std::ptrdiff_t i=0; i<mpl::size<Cs>::value; ++i)
00819             if (memcmp(dynamic_at_c(i1,i), dynamic_at_c(i2,i), numBytes)!=0)
00820                 return false;
00821         return true;
00822     }
00823 };
00824 
00825 
00827 template <typename Loc, typename I2>  // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
00828 struct equal_n_fn<boost::gil::iterator_from_2d<Loc>,I2> {
00829     GIL_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc> i1, std::ptrdiff_t n, I2 i2) const {
00830         gil_function_requires<boost::gil::PixelLocatorConcept<Loc> >();
00831         gil_function_requires<boost::gil::PixelIteratorConcept<I2> >();
00832         while (n>0) {
00833             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n, i1.width()-i1.x_pos());
00834             if (!equal_n(i1.x(), num, i2))
00835                 return false;
00836             i1+=num;
00837             i2+=num;
00838             n-=num;
00839         }
00840         return true;
00841     }
00842 };
00843 
00845 template <typename I1, typename Loc> // I Models PixelIteratorConcept, OL Models PixelLocatorConcept
00846 struct equal_n_fn<I1,boost::gil::iterator_from_2d<Loc> > {
00847     GIL_FORCEINLINE bool operator()(I1 i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc> i2) const {
00848         gil_function_requires<boost::gil::PixelIteratorConcept<I1> >();
00849         gil_function_requires<boost::gil::PixelLocatorConcept<Loc> >();
00850         while (n>0) {
00851             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
00852             if (!equal_n(i1, num, i2.x()))
00853                 return false;
00854             i1+=num;
00855             i2+=num;
00856             n-=num;
00857         }
00858         return true;
00859     }
00860 };
00861 
00863 template <typename Loc1, typename Loc2>
00864 struct equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2> > {
00865    GIL_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc1> i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc2> i2) const {
00866         gil_function_requires<boost::gil::PixelLocatorConcept<Loc1> >();
00867         gil_function_requires<boost::gil::PixelLocatorConcept<Loc2> >();
00868         if (i1.x_pos()!=i2.x_pos() || i1.width()!=i2.width()) {
00869             while(n-->0) {
00870                 if (*i1++!=*i2++) return false;
00871             }
00872         }
00873         while (n>0) {
00874             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
00875             if (!equal_n(i1.x(), num, i2.x()))
00876                 return false;
00877             i1+=num;
00878             i2+=num;
00879             n-=num;
00880         }
00881         return true;
00882     }
00883 };
00884 } // namespace detail
00885 
00886 template <typename I1, typename I2> GIL_FORCEINLINE
00887 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2) {
00888     return detail::equal_n_fn<I1,I2>()(i1,n,i2);
00889 }
00890 } }  // namespace boost::gil
00891 
00892 namespace std {
00904 template <typename Loc1, typename Loc2> GIL_FORCEINLINE 
00905 bool equal(boost::gil::iterator_from_2d<Loc1> first, boost::gil::iterator_from_2d<Loc1> last, boost::gil::iterator_from_2d<Loc2> first2) {
00906     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc1> >();
00907     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc2> >();
00908     std::ptrdiff_t n=last-first;
00909     if (first.is_1d_traversable()) {
00910         if (first2.is_1d_traversable())
00911             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,typename Loc2::x_iterator>()(first.x(),n, first2.x());
00912         else
00913             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,boost::gil::iterator_from_2d<Loc2> >()(first.x(),n, first2);
00914     } else {
00915         if (first2.is_1d_traversable())
00916             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,typename Loc2::x_iterator>()(first,n, first2.x());
00917         else
00918             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2> >()(first,n,first2);
00919     }
00920 }
00921 } // namespace std
00922 
00923 namespace boost { namespace gil {
00924 
00927 template <typename View1, typename View2> GIL_FORCEINLINE 
00928 bool equal_pixels(const View1& v1, const View2& v2) {
00929     assert(v1.dimensions()==v2.dimensions());
00930     return std::equal(v1.begin(),v1.end(),v2.begin()); // std::equal has overloads with GIL iterators for optimal performance
00931 }
00932 
00938 
00942 
00945 template <typename View1, typename View2, typename F> GIL_FORCEINLINE 
00946 F transform_pixels(const View1& src,const View2& dst, F fun) {
00947     assert(src.dimensions()==dst.dimensions());
00948     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
00949         typename View1::x_iterator srcIt=src.row_begin(y);
00950         typename View2::x_iterator dstIt=dst.row_begin(y);
00951         for (std::ptrdiff_t x=0; x<src.width(); ++x)
00952             dstIt[x]=fun(srcIt[x]);
00953     }
00954     return fun;
00955 }
00956 
00959 template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE 
00960 F transform_pixels(const View1& src1, const View2& src2,const View3& dst, F fun) {
00961     for (std::ptrdiff_t y=0; y<dst.height(); ++y) {
00962         typename View1::x_iterator srcIt1=src1.row_begin(y);
00963         typename View2::x_iterator srcIt2=src2.row_begin(y);
00964         typename View3::x_iterator dstIt=dst.row_begin(y);
00965         for (std::ptrdiff_t x=0; x<dst.width(); ++x)
00966             dstIt[x]=fun(srcIt1[x],srcIt2[x]);
00967     }
00968     return fun;
00969 }
00970 
00974 
00977 template <typename View1, typename View2, typename F> GIL_FORCEINLINE 
00978 F transform_pixel_positions(const View1& src,const View2& dst, F fun) {
00979     assert(src.dimensions()==dst.dimensions());
00980     typename View1::xy_locator loc=src.xy_at(0,0);
00981     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
00982         typename View2::x_iterator dstIt=dst.row_begin(y);
00983         for (std::ptrdiff_t x=0; x<src.width(); ++x, ++loc.x())
00984             dstIt[x]=fun(loc);
00985         loc.x()-=src.width(); ++loc.y();
00986     }
00987     return fun;
00988 }
00989 
00992 template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE 
00993 F transform_pixel_positions(const View1& src1,const View2& src2,const View3& dst, F fun) {
00994     assert(src1.dimensions()==dst.dimensions());
00995     assert(src2.dimensions()==dst.dimensions());
00996     typename View1::xy_locator loc1=src1.xy_at(0,0);
00997     typename View2::xy_locator loc2=src2.xy_at(0,0);
00998     for (std::ptrdiff_t y=0; y<src1.height(); ++y) {
00999         typename View3::x_iterator dstIt=dst.row_begin(y);
01000         for (std::ptrdiff_t x=0; x<src1.width(); ++x, ++loc1.x(), ++loc2.x())
01001             dstIt[x]=fun(loc1,loc2);
01002         loc1.x()-=src1.width(); ++loc1.y();
01003         loc2.x()-=src2.width(); ++loc2.y();
01004     }
01005     return fun;
01006 }
01007 
01008 } }  // namespace boost::gil
01009 
01010 #ifdef _MSC_VER
01011 #pragma warning(pop)
01012 #endif
01013 
01014 #endif