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
45namespace boost { namespace gil {
46
47//forward declarations
48template <typename ChannelPtr, typename ColorSpace>
49struct planar_pixel_iterator;
50template <typename Iterator>
51class memory_based_step_iterator;
52template <typename StepIterator>
53class memory_based_2d_locator;
54
55// a tag denoting incompatible arguments
56struct 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.
96template <typename Derived, typename Result=void>
97struct 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(); }
111private:
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
143namespace std {
144
145/// \ingroup STLOptimizations
146/// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
147template<typename T, typename Cs>
148GIL_FORCEINLINE boost::gil::pixel<T,Cs>*
149copy(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
156template<typename T, typename Cs>
157GIL_FORCEINLINE boost::gil::pixel<T,Cs>*
158copy(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
164namespace boost { namespace gil {
165namespace detail {
166template <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
172namespace std {
173/// \ingroup STLOptimizations
174/// \brief Copy when both src and dst are planar pointers is copy for each channel
175template<typename Cs, typename IC1, typename IC2> GIL_FORCEINLINE
176boost::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
183namespace boost { namespace gil {
184namespace 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
187template <typename I, typename O>
188struct 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
193template <typename IL, typename O> // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
194struct 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
212template <typename I, typename OL> // I Models ConstPixelIteratorConcept, OL Models PixelLocatorConcept
213struct 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
230template <typename IL, typename OL>
231struct 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
252template <typename SrcIterator, typename DstIterator>
253GIL_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
276namespace std {
277/// \ingroup STLOptimizations
278/// \brief std::copy(I1,I1,I2) with I1 and I2 being a iterator_from_2d
279template <typename IL, typename OL>
280GIL_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
286namespace boost { namespace gil {
287
288
289/// \ingroup ImageViewSTLAlgorithmsCopyPixels
290/// \brief std::copy for image views
291template <typename View1, typename View2> GIL_FORCEINLINE
292void 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
309namespace detail {
310template <typename CC>
311class copy_and_convert_pixels_fn : public binary_operation_obj<copy_and_convert_pixels_fn<CC> > {
312private:
313 CC _cc;
314public:
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
333template <typename V1, typename V2,typename CC>
334GIL_FORCEINLINE
335void 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
340struct default_color_converter;
341
342/// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
343template <typename View1, typename View2>
344GIL_FORCEINLINE
345void 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
363namespace 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
372template <typename IL, typename V>
373void 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>(a: n,b: (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
390namespace boost { namespace gil {
391
392namespace detail {
393/// struct to do std::fill
394struct 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
401template <typename It, typename P>
402GIL_FORCEINLINE
403void 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
407template <typename It, typename P>
408GIL_FORCEINLINE
409void 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
416template <typename View, typename Value> GIL_FORCEINLINE
417void 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
438namespace detail {
439
440template <typename It> GIL_FORCEINLINE
441void 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}
450template <typename It> GIL_FORCEINLINE
451void destruct_range_impl(It, It, mpl::false_) {}
452
453template <typename It> GIL_FORCEINLINE
454void destruct_range(It first, It last) {
455 destruct_range_impl(first,last,typename is_pointer<It>::type());
456}
457
458struct 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
463template <typename It>
464GIL_FORCEINLINE
465void destruct_aux(It first, It last, mpl::true_) {
466 static_for_each(first,last,std_destruct_t());
467}
468/// destruct for interleaved iterators
469template <typename It>
470GIL_FORCEINLINE
471void 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
479template <typename View> GIL_FORCEINLINE
480void 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
501namespace detail {
502
503/// std::uninitialized_fill for planar iterators
504/// If an exception is thrown destructs any in-place copy-constructed objects
505template <typename It, typename P>
506GIL_FORCEINLINE
507void 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
526template <typename It, typename P>
527GIL_FORCEINLINE
528void 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
539template <typename View, typename Value>
540void 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
568namespace detail {
569
570template <typename It> GIL_FORCEINLINE
571void 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
585template <typename It> GIL_FORCEINLINE
586void default_construct_range_impl(It, It, mpl::false_) {}
587
588template <typename It> GIL_FORCEINLINE
589void 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
592template <typename It>
593GIL_FORCEINLINE
594void 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
610template <typename It>
611GIL_FORCEINLINE
612void default_construct_aux(It first, It last, mpl::false_) {
613 default_construct_range(first,last);
614}
615
616template <typename View, bool IsPlanar>
617struct has_trivial_pixel_constructor : public boost::has_trivial_constructor<typename View::value_type> {};
618template <typename View>
619struct 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
627template <typename View>
628void 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
658namespace detail {
659
660/// std::uninitialized_copy for pairs of planar iterators
661template <typename It1, typename It2>
662GIL_FORCEINLINE
663void 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
681template <typename It1, typename It2>
682GIL_FORCEINLINE
683void 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
693template <typename View1, typename View2>
694void 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
732template <typename V, typename F>
733F 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
748template <typename View, typename F>
749F 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
772template <typename View, typename F>
773void 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
792template <typename I1, typename I2> GIL_FORCEINLINE bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2);
793
794namespace detail {
795
796template <typename I1, typename I2>
797struct 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
803template<typename T, typename Cs>
804struct 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};
809template<typename T, typename Cs>
810struct 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
815template<typename IC, typename Cs>
816struct 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
829template <typename Loc, typename I2> // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
830struct 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
847template <typename I1, typename Loc> // I Models PixelIteratorConcept, OL Models PixelLocatorConcept
848struct 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
865template <typename Loc1, typename Loc2>
866struct 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
888template <typename I1, typename I2> GIL_FORCEINLINE
889bool 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
894namespace 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
906template <typename Loc1, typename Loc2> GIL_FORCEINLINE
907bool 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
925namespace boost { namespace gil {
926
927/// \ingroup ImageViewSTLAlgorithmsEqualPixels
928/// \brief std::equal for image views
929template <typename View1, typename View2> GIL_FORCEINLINE
930bool 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
947template <typename View1, typename View2, typename F> GIL_FORCEINLINE
948F 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
961template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE
962F 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
979template <typename View1, typename View2, typename F> GIL_FORCEINLINE
980F 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
994template <typename View1, typename View2, typename View3, typename F> GIL_FORCEINLINE
995F 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
1017

source code of boost/boost/gil/algorithm.hpp