boost/gil/algorithm.hpp

   1 /*
   2     Copyright 2005-2007 Adobe Systems Incorporated
   3
   4     Use, modification and distribution are subject to the Boost Software License,
   5     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt).
   7
   8     See http://opensource.adobe.com/gil for most recent version including documentation.
   9 */
  10
  11
  12 /*************************************************************************************************/
  13
  14 #ifndef GIL_ALGORITHM_HPP
  15 #define GIL_ALGORITHM_HPP
  16
  17 #include <cassert>
  18 #include <cstddef>
  19 #include <cstring>
  20 #include <algorithm>
  21 #include <iterator>
  22 #include <memory>
  23 #include <typeinfo>
  24 #include "gil_config.hpp"
  25 #include "gil_concept.hpp"
  26 #include "color_base_algorithm.hpp"
  27 #include "image_view.hpp"
  28 #include "image_view_factory.hpp"
  29 #include "bit_aligned_pixel_iterator.hpp"
  30
  31 ////////////////////////////////////////////////////////////////////////////////////////
  32 /// \file
  33 /// \brief Some basic STL-style algorithms when applied to image views
  34 /// \author Lubomir Bourdev and Hailin Jin \n
  35 ///         Adobe Systems Incorporated
  36 /// \date   2005-2008 \n Last updated on March 12, 2008
  37 ///
  38 ////////////////////////////////////////////////////////////////////////////////////////
  39
  40 //#ifdef _MSC_VER
  41 //#pragma warning(push)
  42 //#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)
  43 //#endif
  44
  45 namespace boost { namespace gil {
  46
  47 //forward declarations
  48 template <typename ChannelPtr, typename ColorSpace>
  49 struct planar_pixel_iterator;
  50 template <typename Iterator>
  51 class memory_based_step_iterator;
  52 template <typename StepIterator>
  53 class memory_based_2d_locator;
  54
  55 // a tag denoting incompatible arguments
  56 struct error_t {};
  57
  58 /// \defgroup ImageViewSTLAlgorithms STL-like Algorithms
  59 /// \ingroup ImageViewAlgorithm
  60 /// \brief Image view-equivalents of STL algorithms
  61 ///
  62 /// Image views provide 1D iteration of their pixels via \p begin() and \p end() methods,
  63 /// which makes it possible to use STL algorithms with them. However, using nested loops
  64 /// over X and Y is in many cases more efficient. The algorithms in this section resemble
  65 /// STL algorithms, but they abstract away the nested loops and take views (as opposed to ranges) as input.
  66 ///
  67 /// Most algorithms check whether the image views are 1D-traversable. A 1D-traversable image view has no gaps
  68 /// at the end of the rows. In other words, if an x_iterator of that view is advanced past the last pixel in a row
  69 /// it will move to the first pixel of the next row. When image views are 1D-traversable, the algorithms use
  70 /// a single loop and run more efficiently. If one or more of the input views are not 1D-traversable, the algorithms
  71 /// fall-back to an X-loop nested inside a Y-loop.
  72 ///
  73 /// The algorithms typically delegate the work to their corresponding STL algorithms. For example, \p copy_pixels calls
  74 /// \p std::copy either for each row, or, when the images are 1D-traversable, once for all pixels.
  75 ///
  76 /// In addition, overloads are sometimes provided for the STL algorithms. For example, std::copy for planar iterators
  77 /// is overloaded to perform \p std::copy for each of the planes. \p std::copy over bitwise-copiable pixels results in
  78 /// std::copy over unsigned char, which STL typically implements via \p memmove.
  79 ///
  80 /// As a result \p copy_pixels may result in a single call to \p memmove for interleaved 1D-traversable views,
  81 /// or one per each plane of planar 1D-traversable views, or one per each row of interleaved non-1D-traversable images, etc.
  82
  83
  84 /// \defgroup STLOptimizations  Performance overloads of STL algorithms
  85 /// \ingroup ImageViewAlgorithm
  86 /// \brief overloads of STL algorithms allowing more efficient implementation when used with GIL constructs
  87
  88 /// \brief A generic binary operation on views
  89 /// \ingroup ImageViewSTLAlgorithms
  90 ///
  91 /// Use this class as a convenience superclass when defining an operation for any image views.
  92 /// Many operations have different behavior when the two views are compatible. This class checks
  93 /// for compatibility and invokes apply_compatible(V1,V2) or apply_incompatible(V1,V2) of the subclass.
  94 /// You must provide apply_compatible(V1,V2) method in your subclass, but apply_incompatible(V1,V2)
  95 /// is not required and the default throws std::bad_cast.
  96 template <typename Derived, typename Result=void>
  97 struct binary_operation_obj {
  98     typedef Result result_type;
  99
 100     template <typename V1, typename V2> GIL_FORCEINLINE
 101     result_type operator()(const std::pair<const V1*,const V2*>& p) const {
 102         return apply(*p.first, *p.second, typename views_are_compatible<V1,V2>::type());
 103     }
 104
 105     template <typename V1, typename V2> GIL_FORCEINLINE
 106     result_type operator()(const V1& v1, const V2& v2) const {
 107         return apply(v1, v2, typename views_are_compatible<V1,V2>::type());
 108     }
 109
 110     result_type operator()(const error_t&) const { throw std::bad_cast(); }
 111 private:
 112
 113     // dispatch from apply overload to a function with distinct name
 114     template <typename V1, typename V2>
 115     GIL_FORCEINLINE result_type apply(const V1& v1, const V2& v2, mpl::false_) const {
 116         return ((const Derived*)this)->apply_incompatible(v1,v2);
 117     }
 118
 119     // dispatch from apply overload to a function with distinct name
 120     template <typename V1, typename V2>
 121     GIL_FORCEINLINE result_type apply(const V1& v1, const V2& v2, mpl::true_) const {
 122         return ((const Derived*)this)->apply_compatible(v1,v2);
 123     }
 124
 125     // function with distinct name - it can be overloaded by subclasses
 126     template <typename V1, typename V2>
 127     GIL_FORCEINLINE result_type apply_incompatible(const V1& v1, const V2& v2) const {
 128         throw std::bad_cast();
 129     }
 130 };
 131 } }  // namespace boost::gil
 132
 133 //////////////////////////////////////////////////////////////////////////////////////
 134 ///
 135 /// std::copy and gil::copy_pixels
 136 ///
 137 //////////////////////////////////////////////////////////////////////////////////////
 138
 139 /// \defgroup ImageViewSTLAlgorithmsCopyPixels copy_pixels
 140 /// \ingroup ImageViewSTLAlgorithms
 141 /// \brief std::copy for image views
 142
 143 namespace std {
 144
 145 /// \ingroup STLOptimizations
 146 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
 147 template<typename T, typename Cs>
 148 GIL_FORCEINLINE boost::gil::pixel<T,Cs>*
 149 copy(boost::gil::pixel<T,Cs>* first, boost::gil::pixel<T,Cs>* last,
 150      boost::gil::pixel<T,Cs>* dst) {
 151     return (boost::gil::pixel<T,Cs>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
 152 }
 153
 154 /// \ingroup STLOptimizations
 155 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
 156 template<typename T, typename Cs>
 157 GIL_FORCEINLINE boost::gil::pixel<T,Cs>*
 158 copy(const boost::gil::pixel<T,Cs>* first, const boost::gil::pixel<T,Cs>* last,
 159      boost::gil::pixel<T,Cs>* dst) {
 160     return (boost::gil::pixel<T,Cs>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
 161 }
 162 } // namespace std
 163
 164 namespace boost { namespace gil {
 165 namespace detail {
 166 template <typename I, typename O> struct copy_fn {
 167     GIL_FORCEINLINE I operator()(I first, I last, O dst) const { return std::copy(first,last,dst); }
 168 };
 169 } // namespace detail
 170 } }  // namespace boost::gil
 171
 172 namespace std {
 173 /// \ingroup STLOptimizations
 174 /// \brief Copy when both src and dst are planar pointers is copy for each channel
 175 template<typename Cs, typename IC1, typename IC2> GIL_FORCEINLINE
 176 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) {
 177     boost::gil::gil_function_requires<boost::gil::ChannelsCompatibleConcept<typename std::iterator_traits<IC1>::value_type,typename std::iterator_traits<IC2>::value_type> >();
 178     static_for_each(first,last,dst,boost::gil::detail::copy_fn<IC1,IC2>());
 179     return dst+(last-first);
 180 }
 181 } // namespace std
 182
 183 namespace boost { namespace gil {
 184 namespace detail {
 185 /// Does a copy-n. If the inputs contain image iterators, performs a copy at each row using the row iterators
 186 /// \ingroup CopyPixels
 187 template <typename I, typename O>
 188 struct copier_n {
 189     GIL_FORCEINLINE void operator()(I src, typename std::iterator_traits<I>::difference_type n, O dst) const { std::copy(src,src+n, dst); }
 190 };
 191
 192 /// Source range is delimited by image iterators
 193 template <typename IL, typename O>  // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
 194 struct copier_n<iterator_from_2d<IL>,O> {
 195     typedef typename std::iterator_traits<iterator_from_2d<IL> >::difference_type diff_t;
 196     GIL_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, O dst) const {
 197         gil_function_requires<PixelLocatorConcept<IL> >();
 198         gil_function_requires<MutablePixelIteratorConcept<O> >();
 199         while (n>0) {
 200             typedef typename iterator_from_2d<IL>::difference_type diff_t;
 201             diff_t l=src.width()-src.x_pos();
 202             diff_t numToCopy=(n<l ? n:l);
 203             detail::copy_n(src.x(), numToCopy, dst);
 204             dst+=numToCopy;
 205             src+=numToCopy;
 206             n-=numToCopy;
 207         }
 208     }
 209 };
 210
 211 /// Destination range is delimited by image iterators
 212 template <typename I, typename OL> // I Models ConstPixelIteratorConcept, OL Models PixelLocatorConcept
 213 struct copier_n<I,iterator_from_2d<OL> > {
 214     typedef typename std::iterator_traits<I>::difference_type diff_t;
 215     GIL_FORCEINLINE void operator()(I src, diff_t n, iterator_from_2d<OL> dst) const {
 216         gil_function_requires<PixelIteratorConcept<I> >();
 217         gil_function_requires<MutablePixelLocatorConcept<OL> >();
 218         while (n>0) {
 219             diff_t l=dst.width()-dst.x_pos();
 220             diff_t numToCopy=(n<l ? n:l);
 221             detail::copy_n(src, numToCopy, dst.x());
 222             dst+=numToCopy;
 223             src+=numToCopy;
 224             n-=numToCopy;
 225         }
 226     }
 227 };
 228
 229 /// Both source and destination ranges are delimited by image iterators
 230 template <typename IL, typename OL>
 231 struct copier_n<iterator_from_2d<IL>,iterator_from_2d<OL> > {
 232    typedef typename iterator_from_2d<IL>::difference_type diff_t;
 233    GIL_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, iterator_from_2d<OL> dst) const {
 234         gil_function_requires<PixelLocatorConcept<IL> >();
 235         gil_function_requires<MutablePixelLocatorConcept<OL> >();
 236         if (src.x_pos()!=dst.x_pos() || src.width()!=dst.width()) {
 237             while(n-->0) {
 238                 *dst++=*src++;
 239             }
 240         }
 241         while (n>0) {
 242             diff_t l=dst.width()-dst.x_pos();
 243             diff_t numToCopy=(n<l ? n : l);
 244             detail::copy_n(src.x(), numToCopy, dst.x());
 245             dst+=numToCopy;
 246             src+=numToCopy;
 247             n-=numToCopy;
 248         }
 249     }
 250 };
 251
 252 template <typename SrcIterator, typename DstIterator>
 253 GIL_FORCEINLINE DstIterator copy_with_2d_iterators(SrcIterator first, SrcIterator last, DstIterator dst) {
 254     typedef typename SrcIterator::x_iterator src_x_iterator;
 255     typedef typename DstIterator::x_iterator dst_x_iterator;
 256
 257     typename SrcIterator::difference_type n = last - first;
 258
 259     if (first.is_1d_traversable()) {
 260         if (dst.is_1d_traversable())
 261             copier_n<src_x_iterator,dst_x_iterator>()(first.x(),n, dst.x());
 262         else
 263             copier_n<src_x_iterator,DstIterator >()(first.x(),n, dst);
 264     } else {
 265         if (dst.is_1d_traversable())
 266             copier_n<SrcIterator,dst_x_iterator>()(first,n, dst.x());
 267         else
 268             copier_n<SrcIterator,DstIterator>()(first,n,dst);
 269     }
 270     return dst+n;
 271 }
 272
 273 } // namespace detail
 274 } }  // namespace boost::gil
 275
 276 namespace std {
 277 /// \ingroup STLOptimizations
 278 /// \brief  std::copy(I1,I1,I2) with I1 and I2 being a iterator_from_2d
 279 template <typename IL, typename OL>
 280 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) {
 281     return boost::gil::detail::copy_with_2d_iterators(first,last,dst);
 282 }
 283
 284 } // namespace std
 285
 286 namespace boost { namespace gil {
 287
 288
 289 /// \ingroup ImageViewSTLAlgorithmsCopyPixels
 290 /// \brief std::copy for image views
 291 template <typename View1, typename View2> GIL_FORCEINLINE
 292 void copy_pixels(const View1& src, const View2& dst) {
 293     assert(src.dimensions()==dst.dimensions());
 294     detail::copy_with_2d_iterators(src.begin(),src.end(),dst.begin());
 295 }
 296
 297 //////////////////////////////////////////////////////////////////////////////////////
 298 ///
 299 /// copy_and_convert_pixels
 300 ///
 301 //////////////////////////////////////////////////////////////////////////////////////
 302
 303 /// \defgroup ImageViewSTLAlgorithmsCopyAndConvertPixels copy_and_convert_pixels
 304 /// \ingroup ImageViewSTLAlgorithms
 305 /// \brief copies src view into dst view, color converting if necessary.
 306 ///
 307 /// Versions taking static and runtime views are provided. Versions taking user-defined color convered are provided.
 308
 309 namespace detail {
 310 template <typename CC>
 311 class copy_and_convert_pixels_fn : public binary_operation_obj<copy_and_convert_pixels_fn<CC> > {
 312 private:
 313     CC _cc;
 314 public:
 315     typedef typename binary_operation_obj<copy_and_convert_pixels_fn<CC> >::result_type result_type;
 316     copy_and_convert_pixels_fn() {}
 317     copy_and_convert_pixels_fn(CC cc_in) : _cc(cc_in) {}
 318    // when the two color spaces are incompatible, a color conversion is performed
 319     template <typename V1, typename V2> GIL_FORCEINLINE
 320     result_type apply_incompatible(const V1& src, const V2& dst) const {
 321         copy_pixels(color_converted_view<typename V2::value_type>(src,_cc),dst);
 322     }
 323
 324     // If the two color spaces are compatible, copy_and_convert is just copy
 325     template <typename V1, typename V2> GIL_FORCEINLINE
 326     result_type apply_compatible(const V1& src, const V2& dst) const {
 327          copy_pixels(src,dst);
 328     }
 329 };
 330 } // namespace detail
 331
 332 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
 333 template <typename V1, typename V2,typename CC>
 334 GIL_FORCEINLINE
 335 void copy_and_convert_pixels(const V1& src, const V2& dst,CC cc) {
 336     detail::copy_and_convert_pixels_fn<CC> ccp(cc);
 337     ccp(src,dst);
 338 }
 339
 340 struct default_color_converter;
 341
 342 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
 343 template <typename View1, typename View2>
 344 GIL_FORCEINLINE
 345 void copy_and_convert_pixels(const View1& src, const View2& dst) {
 346     detail::copy_and_convert_pixels_fn<default_color_converter> ccp;
 347     ccp(src,dst);
 348 }
 349
 350 } }  // namespace boost::gil
 351
 352 //////////////////////////////////////////////////////////////////////////////////////
 353 //
 354 // std::fill and gil::fill_pixels
 355 //
 356 //////////////////////////////////////////////////////////////////////////////////////
 357
 358 /// \defgroup ImageViewSTLAlgorithmsFillPixels fill_pixels
 359 /// \ingroup ImageViewSTLAlgorithms
 360 /// \brief std::fill for image views
 361
 362
 363 namespace std {
 364 /// \ingroup STLOptimizations
 365 /// \brief std::fill(I,I,V) with I being a iterator_from_2d
 366 ///
 367 /// Invoked when one calls std::fill(I,I,V) with I being a iterator_from_2d (which is
 368 /// a 1D iterator over the pixels in an image). For contiguous images (i.e. images that have
 369 /// no alignment gap at the end of each row) it is more efficient to use the underlying
 370 /// pixel iterator that does not check for the end of rows. For non-contiguous images fill
 371 /// resolves to fill of each row using the underlying pixel iterator, which is still faster
 372 template <typename IL, typename V>
 373 void fill(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, const V& val) {
 374     boost::gil::gil_function_requires<boost::gil::MutablePixelLocatorConcept<IL> >();
 375     if (first.is_1d_traversable()) {
 376         std::fill(first.x(), last.x(), val);
 377     } else {
 378         // fill row by row
 379         std::ptrdiff_t n=last-first;
 380         while (n>0) {
 381             std::ptrdiff_t numToDo=std::min<const std::ptrdiff_t>(n,(std::ptrdiff_t)(first.width()-first.x_pos()));
 382             fill_n(first.x(), numToDo, val);
 383             first+=numToDo;
 384             n-=numToDo;
 385         }
 386     }
 387 }
 388 } // namespace std
 389
 390 namespace boost { namespace gil {
 391
 392 namespace detail {
 393 /// struct to do std::fill
 394 struct std_fill_t {
 395     template <typename It, typename P>
 396     void operator()(It first, It last, const P& p_in) {
 397         std::fill(first,last,p_in);
 398     }
 399 };
 400 /// std::fill for planar iterators
 401 template <typename It, typename P>
 402 GIL_FORCEINLINE
 403 void fill_aux(It first, It last, const P& p, mpl::true_) {
 404     static_for_each(first,last,p,std_fill_t());
 405 }
 406 /// std::fill for interleaved iterators
 407 template <typename It, typename P>
 408 GIL_FORCEINLINE
 409 void fill_aux(It first, It last, const P& p,mpl::false_) {
 410     std::fill(first,last,p);
 411 }
 412 } // namespace detail
 413
 414 /// \ingroup ImageViewSTLAlgorithmsFillPixels
 415 /// \brief std::fill for image views
 416 template <typename View, typename Value> GIL_FORCEINLINE
 417 void fill_pixels(const View& img_view, const Value& val) {
 418     if (img_view.is_1d_traversable())
 419         detail::fill_aux(img_view.begin().x(), img_view.end().x(),
 420                  val,is_planar<View>());
 421     else
 422         for (std::ptrdiff_t y=0; y<img_view.height(); ++y)
 423             detail::fill_aux(img_view.row_begin(y),img_view.row_end(y),
 424                      val,is_planar<View>());
 425 }
 426
 427 //////////////////////////////////////////////////////////////////////////////////////
 428 ///
 429 /// destruct_pixels
 430 ///
 431 //////////////////////////////////////////////////////////////////////////////////////
 432
 433 /// \defgroup ImageViewSTLAlgorithmsDestructPixels destruct_pixels
 434 /// \ingroup ImageViewSTLAlgorithms
 435 /// \brief invokes the destructor on every pixel of an image view
 436
 437
 438 namespace detail {
 439
 440 template <typename It> GIL_FORCEINLINE
 441 void destruct_range_impl(It first, It last, mpl::true_) {
 442     typedef typename std::iterator_traits<It>::value_type value_t;
 443     if (boost::has_trivial_destructor<value_t>::value)
 444         return;
 445     while (first!=last) {
 446         first->~value_t();
 447         ++first;
 448     }
 449 }
 450 template <typename It> GIL_FORCEINLINE
 451 void destruct_range_impl(It, It, mpl::false_) {}
 452
 453 template <typename It> GIL_FORCEINLINE
 454 void destruct_range(It first, It last) {
 455     destruct_range_impl(first,last,typename is_pointer<It>::type());
 456 }
 457
 458 struct std_destruct_t {
 459     template <typename It> void operator()(It first, It last) const { destruct_range(first,last); }
 460 };
 461
 462 /// destruct for planar iterators
 463 template <typename It>
 464 GIL_FORCEINLINE
 465 void destruct_aux(It first, It last, mpl::true_) {
 466     static_for_each(first,last,std_destruct_t());
 467 }
 468 /// destruct for interleaved iterators
 469 template <typename It>
 470 GIL_FORCEINLINE
 471 void destruct_aux(It first, It last, mpl::false_) {
 472     destruct_range(first,last);
 473 }
 474
 475 } // namespace detail
 476
 477 /// \ingroup ImageViewSTLAlgorithmsDestructPixels
 478 /// \brief Invokes the in-place destructor on every pixel of the view
 479 template <typename View> GIL_FORCEINLINE
 480 void destruct_pixels(const View& img_view) {
 481     if (img_view.is_1d_traversable())
 482         detail::destruct_aux(img_view.begin().x(), img_view.end().x(),
 483                                        is_planar<View>());
 484     else
 485         for (std::ptrdiff_t y=0; y<img_view.height(); ++y)
 486             detail::destruct_aux(img_view.row_begin(y),img_view.row_end(y),
 487                                            is_planar<View>());
 488 }
 489
 490 //////////////////////////////////////////////////////////////////////////////////////
 491 ///
 492 /// uninitialized_fill_pixels
 493 ///
 494 //////////////////////////////////////////////////////////////////////////////////////
 495
 496 /// \defgroup ImageViewSTLAlgorithmsUninitializedFillPixels uninitialized_fill_pixels
 497 /// \ingroup ImageViewSTLAlgorithms
 498 /// \brief std::uninitialized_fill for image views
 499
 500
 501 namespace detail {
 502
 503 /// std::uninitialized_fill for planar iterators
 504 /// If an exception is thrown destructs any in-place copy-constructed objects
 505 template <typename It, typename P>
 506 GIL_FORCEINLINE
 507 void uninitialized_fill_aux(It first, It last,
 508                             const P& p, mpl::true_) {
 509     int channel=0;
 510     try {
 511         typedef typename std::iterator_traits<It>::value_type pixel_t;
 512         while (channel < num_channels<pixel_t>::value) {
 513             std::uninitialized_fill(dynamic_at_c(first,channel), dynamic_at_c(last,channel),
 514                                     dynamic_at_c(p,channel));
 515             ++channel;
 516         }
 517     } catch (...) {
 518         for (int c=0; c<channel; ++c)
 519             destruct_range(dynamic_at_c(first,c), dynamic_at_c(last,c));
 520         throw;
 521     }
 522 }
 523
 524 /// std::uninitialized_fill for interleaved iterators
 525 /// If an exception is thrown destructs any in-place copy-constructed objects
 526 template <typename It, typename P>
 527 GIL_FORCEINLINE
 528 void uninitialized_fill_aux(It first, It last,
 529                             const P& p,mpl::false_) {
 530     std::uninitialized_fill(first,last,p);
 531 }
 532
 533 } // namespace detail
 534
 535 /// \ingroup ImageViewSTLAlgorithmsUninitializedFillPixels
 536 /// \brief std::uninitialized_fill for image views.
 537 /// Does not support planar heterogeneous views.
 538 /// If an exception is thrown destructs any in-place copy-constructed pixels
 539 template <typename View, typename Value>
 540 void uninitialized_fill_pixels(const View& img_view, const Value& val) {
 541     if (img_view.is_1d_traversable())
 542         detail::uninitialized_fill_aux(img_view.begin().x(), img_view.end().x(),
 543                                        val,is_planar<View>());
 544     else {
 545         typename View::y_coord_t y;
 546         try {
 547             for (y=0; y<img_view.height(); ++y)
 548                 detail::uninitialized_fill_aux(img_view.row_begin(y),img_view.row_end(y),
 549                                                val,is_planar<View>());
 550         } catch(...) {
 551             for (typename View::y_coord_t y0=0; y0<y; ++y0)
 552                 detail::destruct_aux(img_view.row_begin(y0),img_view.row_end(y0), is_planar<View>());
 553             throw;
 554         }
 555     }
 556 }
 557
 558 //////////////////////////////////////////////////////////////////////////////////////
 559 ///
 560 /// default_construct_pixels
 561 ///
 562 //////////////////////////////////////////////////////////////////////////////////////
 563
 564 /// \defgroup ImageViewSTLAlgorithmsDefaultConstructPixels default_construct_pixels
 565 /// \ingroup ImageViewSTLAlgorithms
 566 /// \brief invokes the default constructor on every pixel of an image view
 567
 568 namespace detail {
 569
 570 template <typename It> GIL_FORCEINLINE
 571 void default_construct_range_impl(It first, It last, mpl::true_) {
 572     typedef typename std::iterator_traits<It>::value_type value_t;
 573     It first1=first;
 574     try {
 575         while (first!=last) {
 576             new (first) value_t();
 577             ++first;
 578         }
 579     } catch (...) {
 580         destruct_range(first1,first);
 581         throw;
 582     }
 583 }
 584
 585 template <typename It> GIL_FORCEINLINE
 586 void default_construct_range_impl(It, It, mpl::false_) {}
 587
 588 template <typename It> GIL_FORCEINLINE
 589 void default_construct_range(It first, It last) { default_construct_range_impl(first, last, typename is_pointer<It>::type()); }
 590
 591 /// uninitialized_default_construct for planar iterators
 592 template <typename It>
 593 GIL_FORCEINLINE
 594 void default_construct_aux(It first, It last, mpl::true_) {
 595     int channel=0;
 596     try {
 597         typedef typename std::iterator_traits<It>::value_type pixel_t;
 598         while (channel < num_channels<pixel_t>::value) {
 599             default_construct_range(dynamic_at_c(first,channel), dynamic_at_c(last,channel));
 600             ++channel;
 601         }
 602     } catch (...) {
 603         for (int c=0; c<channel; ++c)
 604             destruct_range(dynamic_at_c(first,c), dynamic_at_c(last,c));
 605         throw;
 606     }
 607 }
 608
 609 /// uninitialized_default_construct for interleaved iterators
 610 template <typename It>
 611 GIL_FORCEINLINE
 612 void default_construct_aux(It first, It last, mpl::false_) {
 613     default_construct_range(first,last);
 614 }
 615
 616 template <typename View, bool IsPlanar>
 617 struct has_trivial_pixel_constructor : public boost::has_trivial_constructor<typename View::value_type> {};
 618 template <typename View>
 619 struct has_trivial_pixel_constructor<View, true> : public boost::has_trivial_constructor<typename channel_type<View>::type> {};
 620
 621 } // namespace detail
 622
 623 /// \ingroup ImageViewSTLAlgorithmsDefaultConstructPixels
 624 /// \brief Invokes the in-place default constructor on every pixel of the (uninitialized) view.
 625 /// Does not support planar heterogeneous views.
 626 /// If an exception is thrown destructs any in-place default-constructed pixels
 627 template <typename View>
 628 void default_construct_pixels(const View& img_view) {
 629     if (detail::has_trivial_pixel_constructor<View, is_planar<View>::value>::value)
 630         return;
 631
 632     if (img_view.is_1d_traversable())
 633         detail::default_construct_aux(img_view.begin().x(), img_view.end().x(), is_planar<View>());
 634     else {
 635         typename View::y_coord_t y;
 636         try {
 637             for (y=0; y<img_view.height(); ++y)
 638                 detail::default_construct_aux(img_view.row_begin(y),img_view.row_end(y), is_planar<View>());
 639         } catch(...) {
 640             for (typename View::y_coord_t y0=0; y0<y; ++y0)
 641                 detail::destruct_aux(img_view.row_begin(y0),img_view.row_end(y0), is_planar<View>());
 642             throw;
 643         }
 644     }
 645 }
 646
 647
 648 //////////////////////////////////////////////////////////////////////////////////////
 649 ///
 650 /// uninitialized_copy_pixels
 651 ///
 652 //////////////////////////////////////////////////////////////////////////////////////
 653
 654 /// \defgroup ImageViewSTLAlgorithmsUninitializedCopyPixels uninitialized_copy_pixels
 655 /// \ingroup ImageViewSTLAlgorithms
 656 /// \brief std::uninitialized_copy for image views
 657
 658 namespace detail {
 659
 660 /// std::uninitialized_copy for pairs of planar iterators
 661 template <typename It1, typename It2>
 662 GIL_FORCEINLINE
 663 void uninitialized_copy_aux(It1 first1, It1 last1,
 664                             It2 first2, mpl::true_) {
 665     int channel=0;
 666     try {
 667         typedef typename std::iterator_traits<It1>::value_type pixel_t;
 668         while (channel < num_channels<pixel_t>::value) {
 669             std::uninitialized_copy(dynamic_at_c(first1,channel), dynamic_at_c(last1,channel), dynamic_at_c(first2,channel));
 670             ++channel;
 671         }
 672     } catch (...) {
 673         It2 last2=first2;
 674         std::advance(last2, std::distance(first1,last1));
 675         for (int c=0; c<channel; ++c)
 676             destruct_range(dynamic_at_c(first2,c), dynamic_at_c(last2,c));
 677         throw;
 678     }
 679 }
 680 /// std::uninitialized_copy for interleaved or mixed iterators
 681 template <typename It1, typename It2>
 682 GIL_FORCEINLINE
 683 void uninitialized_copy_aux(It1 first1, It1 last1,
 684                             It2 first2,mpl::false_) {
 685     std::uninitialized_copy(first1,last1,first2);
 686 }
 687 } // namespace detail
 688
 689 /// \ingroup ImageViewSTLAlgorithmsUninitializedCopyPixels
 690 /// \brief std::uninitialized_copy for image views.
 691 /// Does not support planar heterogeneous views.
 692 /// If an exception is thrown destructs any in-place copy-constructed objects
 693 template <typename View1, typename View2>
 694 void uninitialized_copy_pixels(const View1& view1, const View2& view2) {
 695     typedef mpl::bool_<is_planar<View1>::value && is_planar<View2>::value> is_planar;
 696     assert(view1.dimensions()==view2.dimensions());
 697     if (view1.is_1d_traversable() && view2.is_1d_traversable())
 698         detail::uninitialized_copy_aux(view1.begin().x(), view1.end().x(),
 699                                        view2.begin().x(),
 700                                        is_planar());
 701     else {
 702         typename View1::y_coord_t y;
 703         try {
 704             for (y=0; y<view1.height(); ++y)
 705                 detail::uninitialized_copy_aux(view1.row_begin(y), view1.row_end(y),
 706                                                view2.row_begin(y),
 707                                                is_planar());
 708         } catch(...) {
 709             for (typename View1::y_coord_t y0=0; y0<y; ++y0)
 710                 detail::destruct_aux(view2.row_begin(y0),view2.row_end(y0), is_planar());
 711             throw;
 712         }
 713     }
 714 }
 715
 716 //////////////////////////////////////////////////////////////////////////////////////
 717 ///
 718 /// for_each_pixel
 719 ///
 720 //////////////////////////////////////////////////////////////////////////////////////
 721
 722 /// \defgroup ImageViewSTLAlgorithmsForEachPixel for_each_pixel
 723 /// \ingroup ImageViewSTLAlgorithms
 724 /// \brief std::for_each for image views
 725 ///
 726 /// For contiguous images (i.e. images that have no alignment gap at the end of each row) it is
 727 /// more efficient to use the underlying pixel iterator that does not check for the end of rows.
 728 /// For non-contiguous images for_each_pixel resolves to for_each of each row using the underlying
 729 /// pixel iterator, which is still faster
 730
 731 /// \ingroup ImageViewSTLAlgorithmsForEachPixel
 732 template <typename V, typename F>
 733 F for_each_pixel(const V& img, F fun) {
 734     if (img.is_1d_traversable()) {
 735         return std::for_each(img.begin().x(), img.end().x(), fun);
 736     } else {
 737         for (std::ptrdiff_t y=0; y<img.height(); ++y)
 738             fun = std::for_each(img.row_begin(y),img.row_end(y),fun);
 739         return fun;
 740     }
 741 }
 742
 743 /// \defgroup ImageViewSTLAlgorithmsForEachPixelPosition for_each_pixel_position
 744 /// \ingroup ImageViewSTLAlgorithms
 745 /// \brief adobe::for_each_position for image views (passes locators, instead of pixel references, to the function object)
 746
 747 /// \ingroup ImageViewSTLAlgorithmsForEachPixelPosition
 748 template <typename View, typename F>
 749 F for_each_pixel_position(const View& img, F fun) {
 750     typename View::xy_locator loc=img.xy_at(0,0);
 751     for (std::ptrdiff_t y=0; y<img.height(); ++y) {
 752         for (std::ptrdiff_t x=0; x<img.width(); ++x, ++loc.x())
 753             fun(loc);
 754         loc.x()-=img.width(); ++loc.y();
 755     }
 756     return fun;
 757 }
 758
 759
 760 //////////////////////////////////////////////////////////////////////////////////////
 761 ///
 762 /// generate_pixels
 763 ///
 764 //////////////////////////////////////////////////////////////////////////////////////
 765
 766 /// \defgroup ImageViewSTLAlgorithmsGeneratePixels generate_pixels
 767 /// \ingroup ImageViewSTLAlgorithms
 768 /// \brief std::generate for image views
 769
 770 /// \ingroup ImageViewSTLAlgorithmsGeneratePixels
 771 /// \brief std::generate for image views
 772 template <typename View, typename F>
 773 void generate_pixels(const View& v, F fun) {
 774     if (v.is_1d_traversable()) {
 775         std::generate(v.begin().x(), v.end().x(), fun);
 776     } else {
 777         for (std::ptrdiff_t y=0; y<v.height(); ++y)
 778             std::generate(v.row_begin(y),v.row_end(y),fun);
 779     }
 780 }
 781
 782 //////////////////////////////////////////////////////////////////////////////////////
 783 ///
 784 /// std::equal and gil::equal_pixels for GIL constructs
 785 ///
 786 //////////////////////////////////////////////////////////////////////////////////////
 787
 788 /// \defgroup ImageViewSTLAlgorithmsEqualPixels equal_pixels
 789 /// \ingroup ImageViewSTLAlgorithms
 790 /// \brief std::equal for image views
 791
 792 template <typename I1, typename I2> GIL_FORCEINLINE bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2);
 793
 794 namespace detail {
 795
 796 template <typename I1, typename I2>
 797 struct equal_n_fn {
 798     GIL_FORCEINLINE bool operator()(I1 i1, std::ptrdiff_t n, I2 i2) const { return std::equal(i1,i1+n, i2); }
 799 };
 800
 801 /// Equal when both ranges are interleaved and of the same type.
 802 /// GIL pixels are bitwise comparable, so memcmp is used. User-defined pixels that are not bitwise comparable need to provide an overload
 803 template<typename T, typename Cs>
 804 struct equal_n_fn<const pixel<T,Cs>*, const pixel<T,Cs>*> {
 805     GIL_FORCEINLINE bool operator()(const pixel<T,Cs>* i1, std::ptrdiff_t n, const pixel<T,Cs>* i2) const {
 806         return memcmp(i1, i2, n*sizeof(pixel<T,Cs>))==0;
 807     }
 808 };
 809 template<typename T, typename Cs>
 810 struct equal_n_fn<pixel<T,Cs>*, pixel<T,Cs>*> : equal_n_fn<const pixel<T,Cs>*, const pixel<T,Cs>*> {};
 811
 812 /// EqualPixels
 813 /// Equal when both ranges are planar pointers of the same type. memcmp is invoked for each channel plane
 814 ///  User-defined channels that are not bitwise comparable need to provide an overload
 815 template<typename IC, typename Cs>
 816 struct equal_n_fn<planar_pixel_iterator<IC,Cs>, planar_pixel_iterator<IC,Cs> > {
 817     GIL_FORCEINLINE bool operator()(const planar_pixel_iterator<IC,Cs> i1, std::ptrdiff_t n, const planar_pixel_iterator<IC,Cs> i2) const {
 818         ptrdiff_t numBytes=n*sizeof(typename std::iterator_traits<IC>::value_type);
 819
 820         for (std::ptrdiff_t i=0; i<mpl::size<Cs>::value; ++i)
 821             if (memcmp(dynamic_at_c(i1,i), dynamic_at_c(i2,i), numBytes)!=0)
 822                 return false;
 823         return true;
 824     }
 825 };
 826
 827
 828 /// Source range is delimited by image iterators
 829 template <typename Loc, typename I2>  // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
 830 struct equal_n_fn<boost::gil::iterator_from_2d<Loc>,I2> {
 831     GIL_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc> i1, std::ptrdiff_t n, I2 i2) const {
 832         gil_function_requires<boost::gil::PixelLocatorConcept<Loc> >();
 833         gil_function_requires<boost::gil::PixelIteratorConcept<I2> >();
 834         while (n>0) {
 835             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n, i1.width()-i1.x_pos());
 836             if (!equal_n(i1.x(), num, i2))
 837                 return false;
 838             i1+=num;
 839             i2+=num;
 840             n-=num;
 841         }
 842         return true;
 843     }
 844 };
 845
 846 /// Destination range is delimited by image iterators
 847 template <typename I1, typename Loc> // I Models PixelIteratorConcept, OL Models PixelLocatorConcept
 848 struct equal_n_fn<I1,boost::gil::iterator_from_2d<Loc> > {
 849     GIL_FORCEINLINE bool operator()(I1 i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc> i2) const {
 850         gil_function_requires<boost::gil::PixelIteratorConcept<I1> >();
 851         gil_function_requires<boost::gil::PixelLocatorConcept<Loc> >();
 852         while (n>0) {
 853             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
 854             if (!equal_n(i1, num, i2.x()))
 855                 return false;
 856             i1+=num;
 857             i2+=num;
 858             n-=num;
 859         }
 860         return true;
 861     }
 862 };
 863
 864 /// Both source and destination ranges are delimited by image iterators
 865 template <typename Loc1, typename Loc2>
 866 struct equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2> > {
 867    GIL_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc1> i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc2> i2) const {
 868         gil_function_requires<boost::gil::PixelLocatorConcept<Loc1> >();
 869         gil_function_requires<boost::gil::PixelLocatorConcept<Loc2> >();
 870         if (i1.x_pos()!=i2.x_pos() || i1.width()!=i2.width()) {
 871             while(n-->0) {
 872                 if (*i1++!=*i2++) return false;
 873             }
 874         }
 875         while (n>0) {
 876             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
 877             if (!equal_n(i1.x(), num, i2.x()))
 878                 return false;
 879             i1+=num;
 880             i2+=num;
 881             n-=num;
 882         }
 883         return true;
 884     }
 885 };
 886 } // namespace detail
 887
 888 template <typename I1, typename I2> GIL_FORCEINLINE
 889 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2) {
 890     return detail::equal_n_fn<I1,I2>()(i1,n,i2);
 891 }
 892 } }  // namespace boost::gil
 893
 894 namespace std {
 895 /// \ingroup STLOptimizations
 896 /// \brief  std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d
 897 ///
 898 /// Invoked when one calls std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d (which is
 899 /// a 1D iterator over the pixels in an image). Attempts to demote the source and destination
 900 /// iterators to simpler/faster types if the corresponding range is contiguous.
 901 /// For contiguous images (i.e. images that have
 902 /// no alignment gap at the end of each row) it is more efficient to use the underlying
 903 /// pixel iterator that does not check for the end of rows. If the underlying pixel iterator
 904 /// happens to be a fundamental planar/interleaved pointer, the call may further resolve
 905 /// to memcmp. Otherwise it resolves to copying each row using the underlying pixel iterator
 906 template <typename Loc1, typename Loc2> GIL_FORCEINLINE
 907 bool equal(boost::gil::iterator_from_2d<Loc1> first, boost::gil::iterator_from_2d<Loc1> last, boost::gil::iterator_from_2d<Loc2> first2) {
 908     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc1> >();
 909     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc2> >();
 910     std::ptrdiff_t n=last-first;
 911     if (first.is_1d_traversable()) {
 912         if (first2.is_1d_traversable())
 913             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,typename Loc2::x_iterator>()(first.x(),n, first2.x());
 914         else
 915             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,boost::gil::iterator_from_2d<Loc2> >()(first.x(),n, first2);
 916     } else {
 917         if (first2.is_1d_traversable())
 918             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,typename Loc2::x_iterator>()(first,n, first2.x());
 919         else
 920             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2> >()(first,n,first2);
 921     }
 922 }
 923 } // namespace std
 924
 925 namespace boost { namespace gil {
 926
 927 /// \ingroup ImageViewSTLAlgorithmsEqualPixels
 928 /// \brief std::equal for image views
 929 template <typename View1, typename View2> GIL_FORCEINLINE
 930 bool equal_pixels(const View1& v1, const View2& v2) {
 931     assert(v1.dimensions()==v2.dimensions());
 932     return std::equal(v1.begin(),v1.end(),v2.begin()); // std::equal has overloads with GIL iterators for optimal performance
 933 }
 934
 935 //////////////////////////////////////////////////////////////////////////////////////
 936 ///
 937 /// transform_pixels
 938 ///
 939 //////////////////////////////////////////////////////////////////////////////////////
 940
 941 /// \defgroup ImageViewSTLAlgorithmsTransformPixels transform_pixels
 942 /// \ingroup ImageViewSTLAlgorithms
 943 /// \brief std::transform for image views
 944
 945 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
 946 /// \brief std::transform for image views
 947 template <typename View1, typename View2, typename F> GIL_FORCEINLINE
 948 F transform_pixels(const View1& src,const View2& dst, F fun) {
 949     assert(src.dimensions()==dst.dimensions());
 950     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
 951         typename View1::x_iterator srcIt=src.row_begin(y);
 952         typename View2::x_iterator dstIt=dst.row_begin(y);
 953         for (std::ptrdiff_t x=0; x<src.width(); ++x)
 954             dstIt[x]=fun(srcIt[x]);
 955     }
 956     return fun;
 957 }
 958
 959 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
 960 /// \brief transform_pixels with two sources
 961 template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE
 962 F transform_pixels(const View1& src1, const View2& src2,const View3& dst, F fun) {
 963     for (std::ptrdiff_t y=0; y<dst.height(); ++y) {
 964         typename View1::x_iterator srcIt1=src1.row_begin(y);
 965         typename View2::x_iterator srcIt2=src2.row_begin(y);
 966         typename View3::x_iterator dstIt=dst.row_begin(y);
 967         for (std::ptrdiff_t x=0; x<dst.width(); ++x)
 968             dstIt[x]=fun(srcIt1[x],srcIt2[x]);
 969     }
 970     return fun;
 971 }
 972
 973 /// \defgroup ImageViewSTLAlgorithmsTransformPixelPositions transform_pixel_positions
 974 /// \ingroup ImageViewSTLAlgorithms
 975 /// \brief adobe::transform_positions for image views (passes locators, instead of pixel references, to the function object)
 976
 977 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
 978 /// \brief Like transform_pixels but passes to the function object pixel locators instead of pixel references
 979 template <typename View1, typename View2, typename F> GIL_FORCEINLINE
 980 F transform_pixel_positions(const View1& src,const View2& dst, F fun) {
 981     assert(src.dimensions()==dst.dimensions());
 982     typename View1::xy_locator loc=src.xy_at(0,0);
 983     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
 984         typename View2::x_iterator dstIt=dst.row_begin(y);
 985         for (std::ptrdiff_t x=0; x<src.width(); ++x, ++loc.x())
 986             dstIt[x]=fun(loc);
 987         loc.x()-=src.width(); ++loc.y();
 988     }
 989     return fun;
 990 }
 991
 992 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
 993 /// \brief transform_pixel_positions with two sources
 994 template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE
 995 F transform_pixel_positions(const View1& src1,const View2& src2,const View3& dst, F fun) {
 996     assert(src1.dimensions()==dst.dimensions());
 997     assert(src2.dimensions()==dst.dimensions());
 998     typename View1::xy_locator loc1=src1.xy_at(0,0);
 999     typename View2::xy_locator loc2=src2.xy_at(0,0);
1000     for (std::ptrdiff_t y=0; y<src1.height(); ++y) {
1001         typename View3::x_iterator dstIt=dst.row_begin(y);
1002         for (std::ptrdiff_t x=0; x<src1.width(); ++x, ++loc1.x(), ++loc2.x())
1003             dstIt[x]=fun(loc1,loc2);
1004         loc1.x()-=src1.width(); ++loc1.y();
1005         loc2.x()-=src2.width(); ++loc2.y();
1006     }
1007     return fun;
1008 }
1009
1010 } }  // namespace boost::gil
1011
1012 //#ifdef _MSC_VER
1013 //#pragma warning(pop)
1014 //#endif
1015
1016 #endif