2 // Copyright 2005-2007 Adobe Systems Incorporated
4 // Distributed under the Boost Software License, Version 1.0
5 // See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt
8 #ifndef BOOST_GIL_ALGORITHM_HPP
9 #define BOOST_GIL_ALGORITHM_HPP
11 #include <boost/gil/bit_aligned_pixel_iterator.hpp>
12 #include <boost/gil/color_base_algorithm.hpp>
13 #include <boost/gil/concepts.hpp>
14 #include <boost/gil/image_view.hpp>
15 #include <boost/gil/image_view_factory.hpp>
16 #include <boost/gil/detail/mp11.hpp>
17 #include <boost/gil/detail/type_traits.hpp>
19 #include <boost/assert.hpp>
20 #include <boost/config.hpp>
27 #include <type_traits>
30 namespace boost { namespace gil {
32 //forward declarations
33 template <typename ChannelPtr, typename ColorSpace>
34 struct planar_pixel_iterator;
35 template <typename Iterator>
36 class memory_based_step_iterator;
37 template <typename StepIterator>
38 class memory_based_2d_locator;
40 // a tag denoting incompatible arguments
43 /// \defgroup ImageViewSTLAlgorithms STL-like Algorithms
44 /// \ingroup ImageViewAlgorithm
45 /// \brief Image view-equivalents of STL algorithms
47 /// Image views provide 1D iteration of their pixels via \p begin() and \p end() methods,
48 /// which makes it possible to use STL algorithms with them. However, using nested loops
49 /// over X and Y is in many cases more efficient. The algorithms in this section resemble
50 /// STL algorithms, but they abstract away the nested loops and take views (as opposed to ranges) as input.
52 /// Most algorithms check whether the image views are 1D-traversable. A 1D-traversable image view has no gaps
53 /// 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
54 /// it will move to the first pixel of the next row. When image views are 1D-traversable, the algorithms use
55 /// a single loop and run more efficiently. If one or more of the input views are not 1D-traversable, the algorithms
56 /// fall-back to an X-loop nested inside a Y-loop.
58 /// The algorithms typically delegate the work to their corresponding STL algorithms. For example, \p copy_pixels calls
59 /// \p std::copy either for each row, or, when the images are 1D-traversable, once for all pixels.
61 /// In addition, overloads are sometimes provided for the STL algorithms. For example, std::copy for planar iterators
62 /// is overloaded to perform \p std::copy for each of the planes. \p std::copy over bitwise-copiable pixels results in
63 /// std::copy over unsigned char, which STL typically implements via \p memmove.
65 /// As a result \p copy_pixels may result in a single call to \p memmove for interleaved 1D-traversable views,
66 /// or one per each plane of planar 1D-traversable views, or one per each row of interleaved non-1D-traversable images, etc.
68 /// \defgroup STLOptimizations Performance overloads of STL algorithms
69 /// \ingroup ImageViewAlgorithm
70 /// \brief overloads of STL algorithms allowing more efficient implementation when used with GIL constructs
72 /// \brief A generic binary operation on views
73 /// \ingroup ImageViewSTLAlgorithms
75 /// Use this class as a convenience superclass when defining an operation for any image views.
76 /// Many operations have different behavior when the two views are compatible. This class checks
77 /// for compatibility and invokes apply_compatible(V1,V2) or apply_incompatible(V1,V2) of the subclass.
78 /// You must provide apply_compatible(V1,V2) method in your subclass, but apply_incompatible(V1,V2)
79 /// is not required and the default throws std::bad_cast.
80 template <typename Derived, typename Result=void>
81 struct binary_operation_obj
83 using result_type = Result;
85 template <typename V1, typename V2> BOOST_FORCEINLINE
86 result_type operator()(const std::pair<const V1*,const V2*>& p) const {
87 return apply(*p.first, *p.second, typename views_are_compatible<V1,V2>::type());
90 template <typename V1, typename V2> BOOST_FORCEINLINE
91 result_type operator()(const V1& v1, const V2& v2) const {
92 return apply(v1, v2, typename views_are_compatible<V1,V2>::type());
95 result_type operator()(const error_t&) const { throw std::bad_cast(); }
98 // dispatch from apply overload to a function with distinct name
99 template <typename V1, typename V2>
101 result_type apply(V1 const& v1, V2 const& v2, std::false_type) const
103 return ((const Derived*)this)->apply_incompatible(v1, v2);
106 // dispatch from apply overload to a function with distinct name
107 template <typename V1, typename V2>
109 result_type apply(V1 const& v1, V2 const& v2, std::true_type) const
111 return ((const Derived*)this)->apply_compatible(v1, v2);
114 // function with distinct name - it can be overloaded by subclasses
115 template <typename V1, typename V2>
117 result_type apply_incompatible(V1 const& /*v1*/, V2 const& /*v2*/) const
119 throw std::bad_cast();
123 }} // namespace boost::gil
125 //////////////////////////////////////////////////////////////////////////////////////
126 // std::copy and gil::copy_pixels
127 //////////////////////////////////////////////////////////////////////////////////////
129 /// \defgroup ImageViewSTLAlgorithmsCopyPixels copy_pixels
130 /// \ingroup ImageViewSTLAlgorithms
131 /// \brief std::copy for image views
135 /// \ingroup STLOptimizations
136 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
137 template<typename T, typename CS>
140 boost::gil::pixel<T, CS>* first,
141 boost::gil::pixel<T, CS>* last,
142 boost::gil::pixel<T, CS>* dst)
143 -> boost::gil::pixel<T, CS>*
145 auto p = std::copy((unsigned char*)first, (unsigned char*)last, (unsigned char*)dst);
146 return reinterpret_cast<boost::gil::pixel<T, CS>*>(p);
149 /// \ingroup STLOptimizations
150 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
151 template<typename T, typename CS>
152 BOOST_FORCEINLINE boost::gil::pixel<T,CS>*
153 copy(const boost::gil::pixel<T,CS>* first, const boost::gil::pixel<T,CS>* last,
154 boost::gil::pixel<T,CS>* dst) {
155 return (boost::gil::pixel<T,CS>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
159 namespace boost { namespace gil {
161 template <typename I, typename O> struct copy_fn {
162 BOOST_FORCEINLINE I operator()(I first, I last, O dst) const { return std::copy(first,last,dst); }
164 } // namespace detail
165 } } // namespace boost::gil
168 /// \ingroup STLOptimizations
169 /// \brief Copy when both src and dst are planar pointers is copy for each channel
170 template<typename CS, typename IC1, typename IC2> BOOST_FORCEINLINE
171 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) {
172 boost::gil::gil_function_requires<boost::gil::ChannelsCompatibleConcept<typename std::iterator_traits<IC1>::value_type,typename std::iterator_traits<IC2>::value_type>>();
173 static_for_each(first,last,dst,boost::gil::detail::copy_fn<IC1,IC2>());
174 return dst+(last-first);
178 namespace boost { namespace gil {
180 /// Does a copy-n. If the inputs contain image iterators, performs a copy at each row using the row iterators
181 /// \ingroup CopyPixels
182 template <typename I, typename O>
184 BOOST_FORCEINLINE void operator()(I src, typename std::iterator_traits<I>::difference_type n, O dst) const { std::copy(src,src+n, dst); }
187 /// Source range is delimited by image iterators
188 template <typename IL, typename O> // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
189 struct copier_n<iterator_from_2d<IL>,O> {
190 using diff_t = typename std::iterator_traits<iterator_from_2d<IL>>::difference_type;
191 BOOST_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, O dst) const {
192 gil_function_requires<PixelLocatorConcept<IL>>();
193 gil_function_requires<MutablePixelIteratorConcept<O>>();
195 diff_t l=src.width()-src.x_pos();
196 diff_t numToCopy=(n<l ? n:l);
197 detail::copy_n(src.x(), numToCopy, dst);
205 /// Destination range is delimited by image iterators
206 template <typename I, typename OL> // I Models ConstPixelIteratorConcept, OL Models PixelLocatorConcept
207 struct copier_n<I,iterator_from_2d<OL>> {
208 using diff_t = typename std::iterator_traits<I>::difference_type;
209 BOOST_FORCEINLINE void operator()(I src, diff_t n, iterator_from_2d<OL> dst) const {
210 gil_function_requires<PixelIteratorConcept<I>>();
211 gil_function_requires<MutablePixelLocatorConcept<OL>>();
213 diff_t l=dst.width()-dst.x_pos();
214 diff_t numToCopy=(n<l ? n:l);
215 detail::copy_n(src, numToCopy, dst.x());
223 /// Both source and destination ranges are delimited by image iterators
224 template <typename IL, typename OL>
225 struct copier_n<iterator_from_2d<IL>,iterator_from_2d<OL>> {
226 using diff_t = typename iterator_from_2d<IL>::difference_type;
227 BOOST_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, iterator_from_2d<OL> dst) const {
228 gil_function_requires<PixelLocatorConcept<IL>>();
229 gil_function_requires<MutablePixelLocatorConcept<OL>>();
230 if (src.x_pos()!=dst.x_pos() || src.width()!=dst.width()) {
236 diff_t l=dst.width()-dst.x_pos();
237 diff_t numToCopy=(n<l ? n : l);
238 detail::copy_n(src.x(), numToCopy, dst.x());
246 template <typename SrcIterator, typename DstIterator>
247 BOOST_FORCEINLINE DstIterator copy_with_2d_iterators(SrcIterator first, SrcIterator last, DstIterator dst) {
248 using src_x_iterator = typename SrcIterator::x_iterator;
249 using dst_x_iterator = typename DstIterator::x_iterator;
251 typename SrcIterator::difference_type n = last - first;
253 if (first.is_1d_traversable()) {
254 if (dst.is_1d_traversable())
255 copier_n<src_x_iterator,dst_x_iterator>()(first.x(),n, dst.x());
257 copier_n<src_x_iterator,DstIterator >()(first.x(),n, dst);
259 if (dst.is_1d_traversable())
260 copier_n<SrcIterator,dst_x_iterator>()(first,n, dst.x());
262 copier_n<SrcIterator,DstIterator>()(first,n,dst);
266 } // namespace detail
267 } } // namespace boost::gil
270 /// \ingroup STLOptimizations
271 /// \brief std::copy(I1,I1,I2) with I1 and I2 being a iterator_from_2d
272 template <typename IL, typename OL>
273 BOOST_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) {
274 return boost::gil::detail::copy_with_2d_iterators(first,last,dst);
278 namespace boost { namespace gil {
279 /// \ingroup ImageViewSTLAlgorithmsCopyPixels
280 /// \brief std::copy for image views
281 template <typename View1, typename View2> BOOST_FORCEINLINE
282 void copy_pixels(const View1& src, const View2& dst)
284 BOOST_ASSERT(src.dimensions() == dst.dimensions());
285 detail::copy_with_2d_iterators(src.begin(),src.end(),dst.begin());
288 //////////////////////////////////////////////////////////////////////////////////////
289 // copy_and_convert_pixels
290 //////////////////////////////////////////////////////////////////////////////////////
292 /// \defgroup ImageViewSTLAlgorithmsCopyAndConvertPixels copy_and_convert_pixels
293 /// \ingroup ImageViewSTLAlgorithms
294 /// \brief copies src view into dst view, color converting if necessary.
296 /// Versions taking static and runtime views are provided. Versions taking user-defined color convered are provided.
299 template <typename CC>
300 class copy_and_convert_pixels_fn : public binary_operation_obj<copy_and_convert_pixels_fn<CC>>
305 using result_type = typename binary_operation_obj<copy_and_convert_pixels_fn<default_color_converter>>::result_type;
306 copy_and_convert_pixels_fn() {}
307 copy_and_convert_pixels_fn(CC cc_in) : _cc(cc_in) {}
308 // when the two color spaces are incompatible, a color conversion is performed
309 template <typename V1, typename V2> BOOST_FORCEINLINE
310 result_type apply_incompatible(const V1& src, const V2& dst) const {
311 copy_pixels(color_converted_view<typename V2::value_type>(src,_cc),dst);
314 // If the two color spaces are compatible, copy_and_convert is just copy
315 template <typename V1, typename V2> BOOST_FORCEINLINE
316 result_type apply_compatible(const V1& src, const V2& dst) const {
317 copy_pixels(src,dst);
320 } // namespace detail
322 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
323 template <typename V1, typename V2,typename CC>
325 void copy_and_convert_pixels(const V1& src, const V2& dst,CC cc) {
326 detail::copy_and_convert_pixels_fn<CC> ccp(cc);
330 struct default_color_converter;
332 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
333 template <typename View1, typename View2>
335 void copy_and_convert_pixels(const View1& src, const View2& dst) {
336 detail::copy_and_convert_pixels_fn<default_color_converter> ccp;
339 } } // namespace boost::gil
341 //////////////////////////////////////////////////////////////////////////////////////
342 // std::fill and gil::fill_pixels
343 //////////////////////////////////////////////////////////////////////////////////////
345 /// \defgroup ImageViewSTLAlgorithmsFillPixels fill_pixels
346 /// \ingroup ImageViewSTLAlgorithms
347 /// \brief std::fill for image views
350 /// \ingroup STLOptimizations
351 /// \brief std::fill(I,I,V) with I being a iterator_from_2d
353 /// Invoked when one calls std::fill(I,I,V) with I being a iterator_from_2d (which is
354 /// a 1D iterator over the pixels in an image). For contiguous images (i.e. images that have
355 /// no alignment gap at the end of each row) it is more efficient to use the underlying
356 /// pixel iterator that does not check for the end of rows. For non-contiguous images fill
357 /// resolves to fill of each row using the underlying pixel iterator, which is still faster
358 template <typename IL, typename V>
359 void fill(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, const V& val) {
360 boost::gil::gil_function_requires<boost::gil::MutablePixelLocatorConcept<IL>>();
361 if (first.is_1d_traversable()) {
362 std::fill(first.x(), last.x(), val);
365 std::ptrdiff_t n=last-first;
367 std::ptrdiff_t numToDo=std::min<const std::ptrdiff_t>(n,(std::ptrdiff_t)(first.width()-first.x_pos()));
368 std::fill_n(first.x(), numToDo, val);
376 namespace boost { namespace gil {
380 /// struct to do std::fill
382 template <typename It, typename P>
383 void operator()(It first, It last, const P& p_in) {
384 std::fill(first,last,p_in);
388 /// std::fill for planar iterators
389 template <typename It, typename P>
391 void fill_aux(It first, It last, P const& p, std::true_type)
393 static_for_each(first, last, p, std_fill_t());
396 /// std::fill for interleaved iterators
397 template <typename It, typename P>
399 void fill_aux(It first, It last, P const& p, std::false_type)
401 std::fill(first, last, p);
404 } // namespace detail
406 /// \ingroup ImageViewSTLAlgorithmsFillPixels
407 /// \brief std::fill for image views
408 template <typename View, typename Value>
410 void fill_pixels(View const& view, Value const& value)
412 if (view.is_1d_traversable())
415 view.begin().x(), view.end().x(), value, is_planar<View>());
419 for (std::ptrdiff_t y = 0; y < view.height(); ++y)
421 view.row_begin(y), view.row_end(y), value, is_planar<View>());
425 //////////////////////////////////////////////////////////////////////////////////////
427 //////////////////////////////////////////////////////////////////////////////////////
429 /// \defgroup ImageViewSTLAlgorithmsDestructPixels destruct_pixels
430 /// \ingroup ImageViewSTLAlgorithms
431 /// \brief invokes the destructor on every pixel of an image view
434 template <typename Iterator>
436 void destruct_range_impl(Iterator first, Iterator last,
437 typename std::enable_if
441 std::is_pointer<Iterator>,
444 detail::is_trivially_destructible<typename std::iterator_traits<Iterator>::value_type>
447 >::type* /*ptr*/ = 0)
449 while (first != last)
456 template <typename Iterator>
458 void destruct_range_impl(Iterator /*first*/, Iterator /*last*/,
459 typename std::enable_if
463 mp11::mp_not<std::is_pointer<Iterator>>,
464 detail::is_trivially_destructible<typename std::iterator_traits<Iterator>::value_type>
466 >::type* /* ptr */ = nullptr)
470 template <typename Iterator>
472 void destruct_range(Iterator first, Iterator last)
474 destruct_range_impl(first, last);
477 struct std_destruct_t
479 template <typename Iterator>
480 void operator()(Iterator first, Iterator last) const
482 destruct_range(first,last);
486 /// destruct for planar iterators
487 template <typename It>
489 void destruct_aux(It first, It last, std::true_type)
491 static_for_each(first,last,std_destruct_t());
494 /// destruct for interleaved iterators
495 template <typename It>
497 void destruct_aux(It first, It last, std::false_type)
499 destruct_range(first,last);
502 } // namespace detail
504 /// \ingroup ImageViewSTLAlgorithmsDestructPixels
505 /// \brief Invokes the in-place destructor on every pixel of the view
506 template <typename View>
508 void destruct_pixels(View const& view)
510 if (view.is_1d_traversable())
512 detail::destruct_aux(
513 view.begin().x(), view.end().x(), is_planar<View>());
517 for (std::ptrdiff_t y = 0; y < view.height(); ++y)
518 detail::destruct_aux(
519 view.row_begin(y), view.row_end(y), is_planar<View>());
523 //////////////////////////////////////////////////////////////////////////////////////
524 // uninitialized_fill_pixels
525 //////////////////////////////////////////////////////////////////////////////////////
527 /// \defgroup ImageViewSTLAlgorithmsUninitializedFillPixels uninitialized_fill_pixels
528 /// \ingroup ImageViewSTLAlgorithms
529 /// \brief std::uninitialized_fill for image views
533 /// std::uninitialized_fill for planar iterators
534 /// If an exception is thrown destructs any in-place copy-constructed objects
535 template <typename It, typename P>
537 void uninitialized_fill_aux(It first, It last, P const& p, std::true_type)
542 using pixel_t = typename std::iterator_traits<It>::value_type;
543 while (channel < num_channels<pixel_t>::value)
545 std::uninitialized_fill(
546 dynamic_at_c(first,channel),
547 dynamic_at_c(last,channel),
548 dynamic_at_c(p,channel));
555 for (int c = 0; c < channel; ++c)
556 destruct_range(dynamic_at_c(first, c), dynamic_at_c(last, c));
561 /// std::uninitialized_fill for interleaved iterators
562 /// If an exception is thrown destructs any in-place copy-constructed objects
563 template <typename It, typename P>
565 void uninitialized_fill_aux(It first, It last, P const& p, std::false_type)
567 std::uninitialized_fill(first,last,p);
570 } // namespace detail
572 /// \ingroup ImageViewSTLAlgorithmsUninitializedFillPixels
573 /// \brief std::uninitialized_fill for image views.
574 /// Does not support planar heterogeneous views.
575 /// If an exception is thrown destructs any in-place copy-constructed pixels
576 template <typename View, typename Value>
577 void uninitialized_fill_pixels(const View& view, const Value& val) {
578 if (view.is_1d_traversable())
579 detail::uninitialized_fill_aux(view.begin().x(), view.end().x(),
580 val,is_planar<View>());
582 typename View::y_coord_t y = 0;
584 for (y=0; y<view.height(); ++y)
585 detail::uninitialized_fill_aux(view.row_begin(y),view.row_end(y),
586 val,is_planar<View>());
588 for (typename View::y_coord_t y0=0; y0<y; ++y0)
589 detail::destruct_aux(view.row_begin(y0),view.row_end(y0), is_planar<View>());
595 //////////////////////////////////////////////////////////////////////////////////////
596 // default_construct_pixels
597 //////////////////////////////////////////////////////////////////////////////////////
599 /// \defgroup ImageViewSTLAlgorithmsDefaultConstructPixels default_construct_pixels
600 /// \ingroup ImageViewSTLAlgorithms
601 /// \brief invokes the default constructor on every pixel of an image view
604 template <typename It> BOOST_FORCEINLINE
605 void default_construct_range_impl(It first, It last, std::true_type)
610 using value_t = typename std::iterator_traits<It>::value_type;
611 while (first != last)
613 new (first) value_t();
619 destruct_range(first1, first);
624 template <typename It>
626 void default_construct_range_impl(It, It, std::false_type) {}
628 template <typename It>
630 void default_construct_range(It first, It last)
632 default_construct_range_impl(first, last, typename std::is_pointer<It>::type());
635 /// uninitialized_default_construct for planar iterators
636 template <typename It>
638 void default_construct_aux(It first, It last, std::true_type)
643 using pixel_t = typename std::iterator_traits<It>::value_type;
644 while (channel < num_channels<pixel_t>::value)
646 default_construct_range(dynamic_at_c(first, channel), dynamic_at_c(last, channel));
652 for (int c = 0; c < channel; ++c)
653 destruct_range(dynamic_at_c(first, c), dynamic_at_c(last, c));
658 /// uninitialized_default_construct for interleaved iterators
659 template <typename It>
661 void default_construct_aux(It first, It last, std::false_type)
663 default_construct_range(first, last);
666 template <typename View, bool IsPlanar>
667 struct has_trivial_pixel_constructor
668 : detail::is_trivially_default_constructible<typename View::value_type>
671 template <typename View>
672 struct has_trivial_pixel_constructor<View, true>
673 : detail::is_trivially_default_constructible<typename channel_type<View>::type>
676 template<typename View, bool IsTriviallyConstructible>
678 void default_construct_pixels_impl(
680 std::enable_if<!IsTriviallyConstructible>* /*ptr*/ = nullptr)
682 if (view.is_1d_traversable())
684 detail::default_construct_aux(
685 view.begin().x(), view.end().x(), is_planar<View>());
689 typename View::y_coord_t y = 0;
692 for( y = 0; y < view.height(); ++y )
693 detail::default_construct_aux(
694 view.row_begin(y), view.row_end(y), is_planar<View>());
698 for (typename View::y_coord_t y0 = 0; y0 < y; ++y0 )
699 detail::destruct_aux(
700 view.row_begin(y0), view.row_end(y0), is_planar<View>());
707 } // namespace detail
709 /// \ingroup ImageViewSTLAlgorithmsDefaultConstructPixels
710 /// \brief Invokes the in-place default constructor on every pixel of the (uninitialized) view.
711 /// Does not support planar heterogeneous views.
712 /// If an exception is thrown destructs any in-place default-constructed pixels
713 template <typename View>
714 void default_construct_pixels(View const& view)
716 detail::default_construct_pixels_impl
719 detail::has_trivial_pixel_constructor
722 is_planar<View>::value
727 //////////////////////////////////////////////////////////////////////////////////////
728 // uninitialized_copy_pixels
729 //////////////////////////////////////////////////////////////////////////////////////
731 /// \defgroup ImageViewSTLAlgorithmsUninitializedCopyPixels uninitialized_copy_pixels
732 /// \ingroup ImageViewSTLAlgorithms
733 /// \brief std::uninitialized_copy for image views
737 /// std::uninitialized_copy for pairs of planar iterators
738 template <typename It1, typename It2>
740 void uninitialized_copy_aux(It1 first1, It1 last1, It2 first2, std::true_type)
744 using pixel_t = typename std::iterator_traits<It1>::value_type;
745 while (channel < num_channels<pixel_t>::value)
747 std::uninitialized_copy(
748 dynamic_at_c(first1, channel),
749 dynamic_at_c(last1, channel),
750 dynamic_at_c(first2, channel));
757 std::advance(last2, std::distance(first1, last1));
758 for (int c = 0; c < channel; ++c)
759 destruct_range(dynamic_at_c(first2, c), dynamic_at_c(last2, c));
764 /// std::uninitialized_copy for interleaved or mixed iterators
765 template <typename It1, typename It2>
767 void uninitialized_copy_aux(It1 first1, It1 last1, It2 first2, std::false_type)
769 std::uninitialized_copy(first1, last1, first2);
771 } // namespace detail
773 /// \ingroup ImageViewSTLAlgorithmsUninitializedCopyPixels
774 /// \brief std::uninitialized_copy for image views.
775 /// Does not support planar heterogeneous views.
776 /// If an exception is thrown destructs any in-place copy-constructed objects
777 template <typename View1, typename View2>
778 void uninitialized_copy_pixels(View1 const& view1, View2 const& view2)
780 using is_planar = std::integral_constant<bool, is_planar<View1>::value && is_planar<View2>::value>;
781 BOOST_ASSERT(view1.dimensions() == view2.dimensions());
783 if (view1.is_1d_traversable() && view2.is_1d_traversable())
785 detail::uninitialized_copy_aux(
786 view1.begin().x(), view1.end().x(), view2.begin().x(), is_planar());
790 typename View1::y_coord_t y = 0;
793 for (y = 0; y < view1.height(); ++y)
794 detail::uninitialized_copy_aux(
795 view1.row_begin(y), view1.row_end(y), view2.row_begin(y), is_planar());
799 for (typename View1::y_coord_t y0 = 0; y0 < y; ++y0)
800 detail::destruct_aux(view2.row_begin(y0), view2.row_end(y0), is_planar());
806 //////////////////////////////////////////////////////////////////////////////////////
808 //////////////////////////////////////////////////////////////////////////////////////
810 /// \defgroup ImageViewSTLAlgorithmsForEachPixel for_each_pixel
811 /// \ingroup ImageViewSTLAlgorithms
812 /// \brief std::for_each for image views
814 /// For contiguous images (i.e. images that have no alignment gap at the end of each row) it is
815 /// more efficient to use the underlying pixel iterator that does not check for the end of rows.
816 /// For non-contiguous images for_each_pixel resolves to for_each of each row using the underlying
817 /// pixel iterator, which is still faster
819 /// \ingroup ImageViewSTLAlgorithmsForEachPixel
820 template <typename View, typename F>
821 F for_each_pixel(View const& view, F fun)
823 if (view.is_1d_traversable())
825 return std::for_each(view.begin().x(), view.end().x(), fun);
829 for (std::ptrdiff_t y = 0; y < view.height(); ++y)
830 std::for_each(view.row_begin(y), view.row_end(y), fun);
835 /// \defgroup ImageViewSTLAlgorithmsForEachPixelPosition for_each_pixel_position
836 /// \ingroup ImageViewSTLAlgorithms
837 /// \brief adobe::for_each_position for image views (passes locators, instead of pixel references, to the function object)
839 /// \ingroup ImageViewSTLAlgorithmsForEachPixelPosition
840 template <typename View, typename F>
841 F for_each_pixel_position(View const& view, F fun)
843 typename View::xy_locator loc = view.xy_at(0, 0);
844 for (std::ptrdiff_t y = 0; y < view.height(); ++y)
846 for (std::ptrdiff_t x = 0; x < view.width(); ++x, ++loc.x())
848 loc.x() -= view.width(); ++loc.y();
853 //////////////////////////////////////////////////////////////////////////////////////
855 //////////////////////////////////////////////////////////////////////////////////////
857 /// \defgroup ImageViewSTLAlgorithmsGeneratePixels generate_pixels
858 /// \ingroup ImageViewSTLAlgorithms
859 /// \brief std::generate for image views
861 /// \ingroup ImageViewSTLAlgorithmsGeneratePixels
862 /// \brief std::generate for image views
863 template <typename View, typename F>
864 void generate_pixels(View const& view, F fun)
866 if (view.is_1d_traversable())
868 std::generate(view.begin().x(), view.end().x(), fun);
872 for (std::ptrdiff_t y = 0; y < view.height(); ++y)
873 std::generate(view.row_begin(y), view.row_end(y), fun);
877 //////////////////////////////////////////////////////////////////////////////////////
878 // std::equal and gil::equal_pixels for GIL constructs
879 //////////////////////////////////////////////////////////////////////////////////////
881 /// \defgroup ImageViewSTLAlgorithmsEqualPixels equal_pixels
882 /// \ingroup ImageViewSTLAlgorithms
883 /// \brief std::equal for image views
885 template <typename I1, typename I2>
887 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2);
891 template <typename I1, typename I2>
895 bool operator()(I1 i1, std::ptrdiff_t n, I2 i2) const
897 return std::equal(i1, i1 + n, i2);
901 /// Equal when both ranges are interleaved and of the same type.
902 /// GIL pixels are bitwise comparable, so memcmp is used. User-defined pixels that are not bitwise comparable need to provide an overload
903 template<typename T, typename CS>
904 struct equal_n_fn<pixel<T, CS> const*, pixel<T, CS> const*>
907 bool operator()(pixel<T, CS> const* i1, std::ptrdiff_t n, pixel<T, CS> const* i2) const
909 return memcmp(i1, i2, n * sizeof(pixel<T, CS>)) == 0;
913 template<typename T, typename CS>
914 struct equal_n_fn<pixel<T, CS>*, pixel<T, CS>*>
915 : equal_n_fn<pixel<T, CS> const*, pixel<T, CS> const*>
919 /// Equal when both ranges are planar pointers of the same type. memcmp is invoked for each channel plane
920 /// User-defined channels that are not bitwise comparable need to provide an overload
921 template<typename IC, typename CS>
922 struct equal_n_fn<planar_pixel_iterator<IC, CS>, planar_pixel_iterator<IC, CS>>
925 bool operator()(planar_pixel_iterator<IC, CS> const i1, std::ptrdiff_t n, planar_pixel_iterator<IC, CS> const i2) const
927 // FIXME: ptrdiff_t vs size_t
928 constexpr std::ptrdiff_t byte_size = n * sizeof(typename std::iterator_traits<IC>::value_type);
929 for (std::ptrdiff_t i = 0; i < mp11::mp_size<CS>::value; ++i)
931 if (memcmp(dynamic_at_c(i1, i), dynamic_at_c(i2, i), byte_size) != 0)
938 /// Source range is delimited by image iterators
939 /// \tparam Loc Models ConstPixelLocatorConcept
940 /// \tparam It Models PixelIteratorConcept
941 template <typename Loc, typename It>
942 struct equal_n_fn<boost::gil::iterator_from_2d<Loc>, It>
945 bool operator()(boost::gil::iterator_from_2d<Loc> i1, std::ptrdiff_t n, It i2) const
947 gil_function_requires<boost::gil::PixelLocatorConcept<Loc>>();
948 gil_function_requires<boost::gil::PixelIteratorConcept<It>>();
951 std::ptrdiff_t const num = std::min<std::ptrdiff_t>(n, i1.width() - i1.x_pos());
952 if (!equal_n(i1.x(), num, i2))
962 /// Destination range is delimited by image iterators
963 /// \tparam It Models PixelIteratorConcept
964 /// \tparam Loc Models PixelLocatorConcept
965 template <typename It, typename Loc>
966 struct equal_n_fn<It, boost::gil::iterator_from_2d<Loc>>
969 bool operator()(It i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc> i2) const
971 gil_function_requires<boost::gil::PixelIteratorConcept<It>>();
972 gil_function_requires<boost::gil::PixelLocatorConcept<Loc>>();
975 std::ptrdiff_t const num = std::min<std::ptrdiff_t>(n, i2.width() - i2.x_pos());
976 if (!equal_n(i1, num, i2.x()))
986 /// Both source and destination ranges are delimited by image iterators
987 template <typename Loc1, typename Loc2>
988 struct equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2>> {
989 BOOST_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc1> i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc2> i2) const {
990 gil_function_requires<boost::gil::PixelLocatorConcept<Loc1>>();
991 gil_function_requires<boost::gil::PixelLocatorConcept<Loc2>>();
992 if (i1.x_pos()!=i2.x_pos() || i1.width()!=i2.width()) {
994 if (*i1++!=*i2++) return false;
998 std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
999 if (!equal_n(i1.x(), num, i2.x()))
1008 } // namespace detail
1010 template <typename I1, typename I2> BOOST_FORCEINLINE
1011 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2) {
1012 return detail::equal_n_fn<I1,I2>()(i1,n,i2);
1014 } } // namespace boost::gil
1017 /// \ingroup STLOptimizations
1018 /// \brief std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d
1020 /// Invoked when one calls std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d (which is
1021 /// a 1D iterator over the pixels in an image). Attempts to demote the source and destination
1022 /// iterators to simpler/faster types if the corresponding range is contiguous.
1023 /// For contiguous images (i.e. images that have
1024 /// no alignment gap at the end of each row) it is more efficient to use the underlying
1025 /// pixel iterator that does not check for the end of rows. If the underlying pixel iterator
1026 /// happens to be a fundamental planar/interleaved pointer, the call may further resolve
1027 /// to memcmp. Otherwise it resolves to copying each row using the underlying pixel iterator
1028 template <typename Loc1, typename Loc2> BOOST_FORCEINLINE
1029 bool equal(boost::gil::iterator_from_2d<Loc1> first, boost::gil::iterator_from_2d<Loc1> last, boost::gil::iterator_from_2d<Loc2> first2) {
1030 boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc1>>();
1031 boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc2>>();
1032 std::ptrdiff_t n=last-first;
1033 if (first.is_1d_traversable()) {
1034 if (first2.is_1d_traversable())
1035 return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,typename Loc2::x_iterator>()(first.x(),n, first2.x());
1037 return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,boost::gil::iterator_from_2d<Loc2>>()(first.x(),n, first2);
1039 if (first2.is_1d_traversable())
1040 return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,typename Loc2::x_iterator>()(first,n, first2.x());
1042 return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2>>()(first,n,first2);
1047 namespace boost { namespace gil {
1048 /// \ingroup ImageViewSTLAlgorithmsEqualPixels
1049 /// \brief std::equal for image views
1050 template <typename View1, typename View2> BOOST_FORCEINLINE
1051 bool equal_pixels(const View1& v1, const View2& v2) {
1052 BOOST_ASSERT(v1.dimensions() == v2.dimensions());
1053 return std::equal(v1.begin(),v1.end(),v2.begin()); // std::equal has overloads with GIL iterators for optimal performance
1056 //////////////////////////////////////////////////////////////////////////////////////
1058 /// transform_pixels
1060 //////////////////////////////////////////////////////////////////////////////////////
1062 /// \defgroup ImageViewSTLAlgorithmsTransformPixels transform_pixels
1063 /// \ingroup ImageViewSTLAlgorithms
1064 /// \brief std::transform for image views
1066 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
1067 /// \brief std::transform for image views
1068 template <typename View1, typename View2, typename F> BOOST_FORCEINLINE
1069 F transform_pixels(const View1& src,const View2& dst, F fun) {
1070 BOOST_ASSERT(src.dimensions() == dst.dimensions());
1071 for (std::ptrdiff_t y=0; y<src.height(); ++y) {
1072 typename View1::x_iterator srcIt=src.row_begin(y);
1073 typename View2::x_iterator dstIt=dst.row_begin(y);
1074 for (std::ptrdiff_t x=0; x<src.width(); ++x)
1075 dstIt[x]=fun(srcIt[x]);
1080 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
1081 /// \brief transform_pixels with two sources
1082 template <typename View1, typename View2, typename View3, typename F> BOOST_FORCEINLINE
1083 F transform_pixels(const View1& src1, const View2& src2,const View3& dst, F fun) {
1084 for (std::ptrdiff_t y=0; y<dst.height(); ++y) {
1085 typename View1::x_iterator srcIt1=src1.row_begin(y);
1086 typename View2::x_iterator srcIt2=src2.row_begin(y);
1087 typename View3::x_iterator dstIt=dst.row_begin(y);
1088 for (std::ptrdiff_t x=0; x<dst.width(); ++x)
1089 dstIt[x]=fun(srcIt1[x],srcIt2[x]);
1094 /// \defgroup ImageViewSTLAlgorithmsTransformPixelPositions transform_pixel_positions
1095 /// \ingroup ImageViewSTLAlgorithms
1096 /// \brief adobe::transform_positions for image views (passes locators, instead of pixel references, to the function object)
1098 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
1099 /// \brief Like transform_pixels but passes to the function object pixel locators instead of pixel references
1100 template <typename View1, typename View2, typename F> BOOST_FORCEINLINE
1101 F transform_pixel_positions(const View1& src,const View2& dst, F fun) {
1102 BOOST_ASSERT(src.dimensions() == dst.dimensions());
1103 typename View1::xy_locator loc=src.xy_at(0,0);
1104 for (std::ptrdiff_t y=0; y<src.height(); ++y) {
1105 typename View2::x_iterator dstIt=dst.row_begin(y);
1106 for (std::ptrdiff_t x=0; x<src.width(); ++x, ++loc.x())
1108 loc.x()-=src.width(); ++loc.y();
1113 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
1114 /// \brief transform_pixel_positions with two sources
1115 template <typename View1, typename View2, typename View3, typename F> BOOST_FORCEINLINE
1116 F transform_pixel_positions(const View1& src1,const View2& src2,const View3& dst, F fun) {
1117 BOOST_ASSERT(src1.dimensions() == dst.dimensions());
1118 BOOST_ASSERT(src2.dimensions() == dst.dimensions());
1119 typename View1::xy_locator loc1=src1.xy_at(0,0);
1120 typename View2::xy_locator loc2=src2.xy_at(0,0);
1121 for (std::ptrdiff_t y=0; y<src1.height(); ++y) {
1122 typename View3::x_iterator dstIt=dst.row_begin(y);
1123 for (std::ptrdiff_t x=0; x<src1.width(); ++x, ++loc1.x(), ++loc2.x())
1124 dstIt[x]=fun(loc1,loc2);
1125 loc1.x()-=src1.width(); ++loc1.y();
1126 loc2.x()-=src2.width(); ++loc2.y();
1130 } } // namespace boost::gil