|
Go to the documentation of this file.
8 #ifndef ADOBE_ALGORITHM_SELECTION_HPP
9 #define ADOBE_ALGORITHM_SELECTION_HPP
17 #include <boost/range/begin.hpp>
18 #include <boost/range/end.hpp>
19 #include <boost/range/value_type.hpp>
20 #include <boost/range/size_type.hpp>
21 #include <boost/range/size.hpp>
64 bool prev_op_result(pred(this_inside, other_inside));
68 this_inside = !this_inside;
70 bool cur_op_result(pred(this_inside, other_inside));
72 if (prev_op_result ^ cur_op_result)
75 prev_op_result = cur_op_result;
89 template < typename C1,
95 { return static_cast<bool>(x) ^ static_cast<bool>(y); }
104 template < typename S1,
119 if (s1_first == s1_last)
121 else if (s2_first == s2_last)
124 bool prev_op_result(pred(s1_inside, s2_inside));
128 typename std::iterator_traits<S1>::value_type next(comp(*s1_first, *s2_first) ? *s1_first : *s2_first);
130 if (*s1_first == next)
132 s1_inside = !s1_inside;
137 if (*s2_first == next)
139 s2_inside = !s2_inside;
144 bool cur_op_result(pred(s1_inside, s2_inside));
146 if (prev_op_result ^ cur_op_result)
149 prev_op_result = cur_op_result;
151 if (s1_first == s1_last)
153 else if (s2_first == s2_last)
166 template < typename S1,
176 bool s1_inside = false,
177 bool s2_inside = false)
184 std::logical_or<bool>(),
194 template < typename S1,
204 bool s1_inside = false,
205 bool s2_inside = false)
212 std::logical_and<bool>(),
222 template < typename S1,
232 bool s1_inside = false,
233 bool s2_inside = false)
249 template < typename S1,
259 bool s1_inside = false,
260 bool s2_inside = false)
277 template < typename S1,
285 bool s1_inside = false,
286 bool s2_inside = false)
288 if (s1_inside == s2_inside)
290 typedef typename std::iterator_traits<S1>::value_type value_type;
292 std::vector<value_type> result;
296 std::back_inserter(result),
298 s1_inside, s2_inside);
300 return std::equal(s2_first, s2_last, result.begin());
306 comp, !s1_inside, s2_inside);
311 boost::next(s2_first), s2_last,
312 comp, s1_inside, !s2_inside);
321 template < typename Selection1, typename Selection2>
331 std::back_inserter(result),
332 std::less<typename boost::range_value<Selection1>::type>(),
345 template < typename Selection1, typename Selection2>
355 std::back_inserter(result),
356 std::less<typename boost::range_value<Selection1>::type>(),
369 template < typename Selection1, typename Selection2>
379 std::back_inserter(result),
380 std::less<typename boost::range_value<Selection1>::type>(),
393 template < typename Selection1, typename Selection2>
403 std::back_inserter(result),
404 std::less<typename boost::range_value<Selection1>::type>(),
417 template < typename Selection1, typename Selection2>
425 std::less<typename boost::range_value<Selection1>::type>(),
436 template < typename Selection>
446 template < typename Selection>
448 { return x.start_selected(); }
456 template < typename Selection>
457 inline typename boost::range_size<Selection>::type size( const Selection& x)
466 template < typename Selection, typename ForwardRange>
467 typename boost::range_size<Selection>::type size( const Selection& x, const ForwardRange& range)
469 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
470 typedef typename boost::range_size<Selection>::type selection_size_type;
471 typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
481 selection_const_iterator s_iter(boost::begin(x));
482 selection_const_iterator s_last(boost::end(x));
484 range_const_iterator prev(boost::begin(range));
485 range_const_iterator iter(boost::next(prev, *s_iter));
486 range_const_iterator last(boost::end(range));
488 selection_size_type result(0);
494 result += static_cast<selection_size_type >( std::distance(prev, iter));
501 iter = ++s_iter == s_last ? last : boost::next(boost::begin(range), *s_iter);
515 template < typename Selection>
516 bool is_selected( const Selection& x, typename Selection::value_type index)
518 typename boost::range_const_iterator<Selection>::type found( std::upper_bound(boost::begin(x), boost::end(x), index));
519 typename boost::range_size<Selection>::type count( std::distance(boost::begin(x), found));
531 template < typename Selection, typename ForwardRange, typename OutputIterator>
532 OutputIterator selection_copy( const Selection& x, const ForwardRange& range, OutputIterator output)
534 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
535 typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
542 selection_const_iterator s_iter(boost::begin(x));
543 selection_const_iterator s_last(boost::end(x));
545 range_const_iterator iter(boost::begin(range));
546 range_const_iterator last(boost::end(range));
550 if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter))
572 template < typename Selection,
573 typename ForwardRange,
581 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
582 typedef typename boost::range_iterator<ForwardRange>::type range_iterator;
587 selection_const_iterator selection_first(boost::begin(selection));
588 selection_const_iterator selection_last(boost::end(selection));
590 range_iterator first(boost::begin(range));
591 range_iterator last(boost::end(range));
597 range_iterator copy_last(selection_first == selection_last ? last : boost::next(boost::begin(range), *selection_first));
604 std::copy(first, copy_last, true_output);
606 std::copy(first, copy_last, false_output);
608 if (copy_last == last)
625 template < typename Selection, typename ForwardRange, typename UnaryFunction>
626 UnaryFunction selection_foreach( const Selection& x, const ForwardRange& range, UnaryFunction proc)
628 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
629 typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
633 selection_const_iterator s_iter(boost::begin(x));
634 selection_const_iterator s_last(boost::end(x));
636 range_const_iterator iter(boost::begin(range));
637 range_const_iterator last(boost::end(range));
641 if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter))
663 template < typename Selection>
665 std::pair<typename boost::range_const_iterator<Selection>::type,
666 typename boost::range_size<Selection>::type>
668 typename Selection::size_type p,
669 std::random_access_iterator_tag)
671 typedef typename boost::range_const_iterator<Selection>::type const_iterator;
672 typedef typename boost::range_size<Selection>::type size_type;
673 typedef std::pair<const_iterator, size_type> result_type;
675 const_iterator bound( std::lower_bound(boost::begin(selection), boost::end(selection), p));
677 return result_type(bound, static_cast<size_type>( std::distance(boost::begin(selection), bound)));
686 template < typename Selection>
687 std::pair<typename boost::range_const_iterator<Selection>::type,
688 typename boost::range_size<Selection>::type>
690 typename Selection::size_type p,
691 std::forward_iterator_tag)
693 typedef typename boost::range_const_iterator<Selection>::type const_iterator;
694 typedef typename boost::range_size<Selection>::type size_type;
695 typedef std::pair<const_iterator, size_type> result_type;
697 const_iterator iter(boost::begin(selection));
698 const_iterator last(boost::end(selection));
699 size_type boundary_count(0);
701 while (iter != last && *iter < p)
707 return result_type(iter, boundary_count);
729 template < typename Selection>
731 std::pair<typename boost::range_const_iterator<Selection>::type,
732 typename boost::range_size<Selection>::type>
734 typename Selection::size_type p)
736 typedef typename boost::range_const_iterator<Selection>::type const_iterator;
737 typedef typename boost::range_size<Selection>::type size_type;
738 typedef std::pair<const_iterator, size_type> result_type;
739 typedef typename iterator_category<const_iterator>::type iterator_category;
742 return result_type(boost::end(selection), 0);
779 template < typename SelectionIterator, typename RangeIterator>
781 SelectionIterator selection_last,
783 RangeIterator range_first,
784 RangeIterator range_last,
785 std::size_t boundary_count = 0)
787 std::size_t n(static_cast<std::size_t>( std::distance(selection_first, selection_last)));
790 return boundary_count % 2 ? range_first : range_last;
792 std::size_t half(n / 2);
793 SelectionIterator selection_middle(boost::next(selection_first, half));
794 RangeIterator range_middle(boost::next(first, *selection_middle));
797 first, range_first, range_middle,
801 first, range_middle, range_last,
802 boundary_count + half + 1));
813 template < typename Selection,
814 typename ForwardRange>
816 typename boost::range_iterator<ForwardRange>::type
822 boost::begin(range), boost::end(range),
862 template < typename Selection,
863 typename ForwardRange>
864 std::pair<typename boost::range_iterator<ForwardRange>::type,
865 typename boost::range_iterator<ForwardRange>::type>
869 typename boost::range_size<Selection>::type prior_boundary_count = 0)
871 typedef typename boost::range_size<Selection>::type size_type;
872 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
873 typedef typename boost::range_iterator<ForwardRange>::type range_iterator;
875 std::pair<selection_const_iterator, size_type> selection_split =
878 range_iterator first(boost::begin(range));
879 range_iterator range_p(boost::next(first, p));
880 range_iterator last(boost::end(range));
883 first, first, range_p,
884 prior_boundary_count));
887 first, range_p, last,
888 selection_split.second + 1));
890 return std::pair<range_iterator, range_iterator>(i, j);
899 template < typename Selection,
900 typename ForwardRange>
908 typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
910 range_const_iterator iter(boost::begin(index_set));
911 range_const_iterator last(boost::end(index_set));
913 for (; iter != last; ++iter)
917 tmp.push_back(*iter);
918 tmp.push_back(*iter + 1);
932 template < typename Selection,
933 typename OutputIterator>
935 typename boost::range_size<Selection>::type max_index,
936 OutputIterator output)
938 typedef typename boost::range_size<Selection>::type size_type;
939 typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
942 std::size_t index(0);
943 selection_const_iterator iter(boost::begin(selection));
944 selection_const_iterator last(boost::end(selection));
948 while (index != *iter && index != max_index)
956 selected = !selected;
|