stlab.adobe.com Adobe Systems Incorporated
selection_algorithms.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 /*************************************************************************************************/
7 
8 #ifndef ADOBE_ALGORITHM_SELECTION_HPP
9 #define ADOBE_ALGORITHM_SELECTION_HPP
10 
11 #include <adobe/config.hpp>
12 
13 #include <algorithm>
14 #include <functional>
15 #include <vector>
16 
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>
22 
26 
27 /*************************************************************************************************/
28 
29 namespace adobe {
30 
31 /*************************************************************************************************/
47 /*************************************************************************************************/
54 template <typename S, // S models ForwardIterator, value_type(S) == I
55  typename O, // O models OutputIterator
56  typename P> // P models BinaryPredicate
58  S last,
59  O output,
60  bool this_inside,
61  bool other_inside,
62  P pred)
63 {
64  bool prev_op_result(pred(this_inside, other_inside));
65 
66  while (first != last)
67  {
68  this_inside = !this_inside;
69 
70  bool cur_op_result(pred(this_inside, other_inside));
71 
72  if (prev_op_result ^ cur_op_result)
73  *output++ = *first;
74 
75  prev_op_result = cur_op_result;
76 
77  ++first;
78  }
79 
80  return output;
81 }
82 
83 /*************************************************************************************************/
89 template <typename C1, // C1 models ConvertibleToBool
90  typename C2 = C1> // C2 models ConvertibleToBool
91 struct logical_xor : std::binary_function<C1, C2, bool>
92 {
94  bool operator()(const C1& x, const C2& y) const
95  { return static_cast<bool>(x) ^ static_cast<bool>(y); }
96 };
97 
98 /*************************************************************************************************/
104 template <typename S1, // S1 models ForwardIterator, value_type(S1) == value_type(S2)
105  typename S2, // S2 models ForwardIterator, value_type(S2) == value_type(S1)
106  typename O, // O models OutputIterator
107  typename P, // P models BinaryPredicate
108  typename C> // C models StrictWeakOrdering
109 O selection_operation(S1 s1_first,
110  S1 s1_last,
111  S2 s2_first,
112  S2 s2_last,
113  O output,
114  bool s1_inside,
115  bool s2_inside,
116  P pred,
117  C comp)
118 {
119  if (s1_first == s1_last)
120  return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside, pred);
121  else if (s2_first == s2_last)
122  return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside, pred);
123 
124  bool prev_op_result(pred(s1_inside, s2_inside));
125 
126  while (true)
127  {
128  typename std::iterator_traits<S1>::value_type next(comp(*s1_first, *s2_first) ? *s1_first : *s2_first);
129 
130  if (*s1_first == next)
131  {
132  s1_inside = !s1_inside;
133 
134  ++s1_first;
135  }
136 
137  if (*s2_first == next)
138  {
139  s2_inside = !s2_inside;
140 
141  ++s2_first;
142  }
143 
144  bool cur_op_result(pred(s1_inside, s2_inside));
145 
146  if (prev_op_result ^ cur_op_result)
147  *output++ = next;
148 
149  prev_op_result = cur_op_result;
150 
151  if (s1_first == s1_last)
152  return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside, pred);
153  else if (s2_first == s2_last)
154  return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside, pred);
155  }
156 
157  return output;
158 }
159 
160 /*************************************************************************************************/
166 template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
167  typename S2, // S2 models ForwardIterator, value_type(S2) == I
168  typename O, // O models OutputIterator
169  typename C> // C models StrictWeakOrdering
170 inline O selection_union(S1 s1_first,
171  S1 s1_last,
172  S2 s2_first,
173  S2 s2_last,
174  O output,
175  C comp,
176  bool s1_inside = false,
177  bool s2_inside = false)
178 {
179  return selection_operation(s1_first, s1_last,
180  s2_first, s2_last,
181  output,
182  s1_inside,
183  s2_inside,
184  std::logical_or<bool>(),
185  comp);
186 }
187 
188 /*************************************************************************************************/
194 template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
195  typename S2, // S2 models ForwardIterator, value_type(S2) == I
196  typename O, // O models OutputIterator
197  typename C> // C models StrictWeakOrdering
198 inline O selection_intersection(S1 s1_first,
199  S1 s1_last,
200  S2 s2_first,
201  S2 s2_last,
202  O output,
203  C comp,
204  bool s1_inside = false,
205  bool s2_inside = false)
206 {
207  return selection_operation(s1_first, s1_last,
208  s2_first, s2_last,
209  output,
210  s1_inside,
211  s2_inside,
212  std::logical_and<bool>(),
213  comp);
214 }
215 
216 /*************************************************************************************************/
222 template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
223  typename S2, // S2 models ForwardIterator, value_type(S2) == I
224  typename O, // O models OutputIterator
225  typename C> // C models StrictWeakOrdering
226 inline O selection_difference(S1 s1_first,
227  S1 s1_last,
228  S2 s2_first,
229  S2 s2_last,
230  O output,
231  C comp,
232  bool s1_inside = false,
233  bool s2_inside = false)
234 {
235  return selection_intersection(s1_first, s1_last,
236  s2_first, s2_last,
237  output,
238  comp,
239  s1_inside,
240  !s2_inside);
241 }
242 
243 /*************************************************************************************************/
249 template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
250  typename S2, // S2 models ForwardIterator, value_type(S2) == I
251  typename O, // O models OutputIterator
252  typename C> // C models StrictWeakOrdering
253 inline O selection_symmetric_difference(S1 s1_first,
254  S1 s1_last,
255  S2 s2_first,
256  S2 s2_last,
257  O output,
258  C comp,
259  bool s1_inside = false,
260  bool s2_inside = false)
261 {
262  return selection_operation(s1_first, s1_last,
263  s2_first, s2_last,
264  output,
265  s1_inside,
266  s2_inside,
268  comp);
269 }
270 
271 /*************************************************************************************************/
277 template <typename S1, // S1 models InputIterator, value_type(S1) == I
278  typename S2, // S2 models InputIterator, value_type(S2) == I
279  typename C> // C models StrictWeakOrdering
280 inline bool selection_includes(S1 s1_first,
281  S1 s1_last,
282  S2 s2_first,
283  S2 s2_last,
284  C comp,
285  bool s1_inside = false,
286  bool s2_inside = false)
287 {
288  if (s1_inside == s2_inside)
289  {
290  typedef typename std::iterator_traits<S1>::value_type value_type;
291 
292  std::vector<value_type> result;
293 
294  selection_intersection(s1_first, s1_last,
295  s2_first, s2_last,
296  std::back_inserter(result),
297  comp,
298  s1_inside, s2_inside);
299 
300  return std::equal(s2_first, s2_last, result.begin());
301  }
302  else if (s1_inside)
303  {
304  return selection_includes(boost::next(s1_first), s1_last,
305  s2_first, s2_last,
306  comp, !s1_inside, s2_inside);
307  }
308 
309  // s2_inside == true
310  return selection_includes(s1_first, s1_last,
311  boost::next(s2_first), s2_last,
312  comp, s1_inside, !s2_inside);
313 }
314 
315 /****************************************************************************************************/
321 template <typename Selection1, typename Selection2>
322 Selection1 selection_intersection(const Selection1& x, const Selection2& y)
323 {
324  if (&x == &y)
325  return x;
326 
327  Selection1 result;
328 
329  adobe::selection_intersection(x.begin(), x.end(),
330  y.begin(), y.end(),
331  std::back_inserter(result),
332  std::less<typename boost::range_value<Selection1>::type>(),
333  start_selected(x),
334  start_selected(y));
335 
336  return result;
337 }
338 
339 /****************************************************************************************************/
345 template <typename Selection1, typename Selection2>
346 Selection1 selection_union(const Selection1& x, const Selection2& y)
347 {
348  if (&x == &y)
349  return x;
350 
351  Selection1 result;
352 
353  adobe::selection_union(x.begin(), x.end(),
354  y.begin(), y.end(),
355  std::back_inserter(result),
356  std::less<typename boost::range_value<Selection1>::type>(),
357  start_selected(x),
358  start_selected(y));
359 
360  return result;
361 }
362 
363 /****************************************************************************************************/
369 template <typename Selection1, typename Selection2>
370 Selection1 selection_difference(const Selection1& x, const Selection2& y)
371 {
372  if (&x == &y)
373  return Selection1();
374 
375  Selection1 result;
376 
377  adobe::selection_difference(x.begin(), x.end(),
378  y.begin(), y.end(),
379  std::back_inserter(result),
380  std::less<typename boost::range_value<Selection1>::type>(),
381  start_selected(x),
382  start_selected(y));
383 
384  return result;
385 }
386 
387 /****************************************************************************************************/
393 template <typename Selection1, typename Selection2>
394 Selection1 selection_symmetric_difference(const Selection1& x, const Selection2& y)
395 {
396  if (&x == &y)
397  return Selection1();
398 
399  Selection1 result;
400 
401  adobe::selection_symmetric_difference(x.begin(), x.end(),
402  y.begin(), y.end(),
403  std::back_inserter(result),
404  std::less<typename boost::range_value<Selection1>::type>(),
405  start_selected(x),
406  start_selected(y));
407 
408  return result;
409 }
410 
411 /****************************************************************************************************/
417 template <typename Selection1, typename Selection2>
418 bool selection_includes(const Selection1& x, const Selection2& y)
419 {
420  if (&x == &y)
421  return true;
422 
423  return adobe::selection_includes(x.begin(), x.end(),
424  y.begin(), y.end(),
425  std::less<typename boost::range_value<Selection1>::type>(),
426  start_selected(x),
427  start_selected(y));
428 }
429 
430 /****************************************************************************************************/
436 template <typename Selection>
437 inline void invert(Selection& x)
438 { x.invert(); }
439 
440 /****************************************************************************************************/
446 template <typename Selection>
447 inline bool start_selected(const Selection& x)
448 { return x.start_selected(); }
449 
450 /****************************************************************************************************/
456 template <typename Selection>
457 inline typename boost::range_size<Selection>::type size(const Selection& x)
458 { return x.size(); }
459 
460 /****************************************************************************************************/
466 template <typename Selection, typename ForwardRange>
467 typename boost::range_size<Selection>::type size(const Selection& x, const ForwardRange& range)
468 {
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;
472 
473  if (x.empty())
474  return 0;
475 
476  // this is the case when the selection has no elements, but it starts selected
477  // (in other words, every item in the selection is toggled as selected)
478  if (x.size() == 0)
479  return boost::size(range);
480 
481  selection_const_iterator s_iter(boost::begin(x));
482  selection_const_iterator s_last(boost::end(x));
483 
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));
487 
488  selection_size_type result(0);
489  bool inside(start_selected(x));
490 
491  while (true)
492  {
493  if (inside)
494  result += static_cast<selection_size_type>(std::distance(prev, iter));
495 
496  if (iter == last)
497  break;
498 
499  prev = iter;
500 
501  iter = ++s_iter == s_last ? last : boost::next(boost::begin(range), *s_iter);
502 
503  inside = !inside;
504  }
505 
506  return result;
507 }
508 
509 /****************************************************************************************************/
515 template <typename Selection>
516 bool is_selected(const Selection& x, typename Selection::value_type index)
517 {
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));
520 
521  return (count % 2 == 1) ^ start_selected(x);
522 }
523 
524 /****************************************************************************************************/
531 template <typename Selection, typename ForwardRange, typename OutputIterator>
532 OutputIterator selection_copy(const Selection& x, const ForwardRange& range, OutputIterator output)
533 {
534  typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
535  typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
536 
537  if (boost::size(range) == 0)
538  return output;
539 
540  bool inside(start_selected(x));
541 
542  selection_const_iterator s_iter(boost::begin(x));
543  selection_const_iterator s_last(boost::end(x));
544 
545  range_const_iterator iter(boost::begin(range));
546  range_const_iterator last(boost::end(range));
547 
548  while (iter != last)
549  {
550  if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter))
551  {
552  ++s_iter;
553 
554  inside = !inside;
555  }
556 
557  if (inside)
558  *output++ = *iter;
559 
560  ++iter;
561  }
562 
563  return output;
564 }
565 
566 /*************************************************************************************************/
572 template <typename Selection,
573  typename ForwardRange,
574  typename O1, // O1 models OutputIterator
575  typename O2> // O2 models OutputIterator
576 std::pair<O1, O2> selection_partition_copy(const Selection& selection,
577  ForwardRange& range,
578  O1 false_output,
579  O2 true_output)
580 {
581  typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
582  typedef typename boost::range_iterator<ForwardRange>::type range_iterator;
583 
584  if (boost::size(range) == 0)
585  return std::make_pair(false_output, true_output);
586 
587  selection_const_iterator selection_first(boost::begin(selection));
588  selection_const_iterator selection_last(boost::end(selection));
589 
590  range_iterator first(boost::begin(range));
591  range_iterator last(boost::end(range));
592 
593  bool inside(start_selected(selection));
594 
595  while (true)
596  {
597  range_iterator copy_last(selection_first == selection_last ? last : boost::next(boost::begin(range), *selection_first));
598 
599  // REVISIT (fbrereto) : It'd be nice to collapse the following into ? :
600  // notation, but some compilers require that the
601  // types returned by ? : be the same, which we cannot
602  // guarantee here.
603  if (inside)
604  std::copy(first, copy_last, true_output);
605  else
606  std::copy(first, copy_last, false_output);
607 
608  if (copy_last == last)
609  break;
610 
611  first = copy_last;
612  ++selection_first;
613  inside = !inside;
614  }
615 
616  return std::make_pair(false_output, true_output);
617 }
618 
619 /****************************************************************************************************/
625 template <typename Selection, typename ForwardRange, typename UnaryFunction>
626 UnaryFunction selection_foreach(const Selection& x, const ForwardRange& range, UnaryFunction proc)
627 {
628  typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
629  typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
630 
631  bool inside(start_selected(x));
632 
633  selection_const_iterator s_iter(boost::begin(x));
634  selection_const_iterator s_last(boost::end(x));
635 
636  range_const_iterator iter(boost::begin(range));
637  range_const_iterator last(boost::end(range));
638 
639  while (iter != last)
640  {
641  if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter))
642  {
643  ++s_iter;
644 
645  inside = !inside;
646  }
647 
648  if (inside)
649  proc(*iter);
650 
651  ++iter;
652  }
653 
654  return proc;
655 }
656 
657 /****************************************************************************************************/
663 template <typename Selection>
664 inline
665 std::pair<typename boost::range_const_iterator<Selection>::type,
666  typename boost::range_size<Selection>::type>
667 selection_find_boundary(const Selection& selection,
668  typename Selection::size_type p,
669  std::random_access_iterator_tag)
670 {
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;
674 
675  const_iterator bound(std::lower_bound(boost::begin(selection), boost::end(selection), p));
676 
677  return result_type(bound, static_cast<size_type>(std::distance(boost::begin(selection), bound)));
678 }
679 
680 /****************************************************************************************************/
686 template <typename Selection>
687 std::pair<typename boost::range_const_iterator<Selection>::type,
688  typename boost::range_size<Selection>::type>
689 selection_find_boundary(const Selection& selection,
690  typename Selection::size_type p,
691  std::forward_iterator_tag)
692 {
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;
696 
697  const_iterator iter(boost::begin(selection));
698  const_iterator last(boost::end(selection));
699  size_type boundary_count(0);
700 
701  while (iter != last && *iter < p)
702  {
703  ++boundary_count;
704  ++iter;
705  }
706 
707  return result_type(iter, boundary_count);
708 }
709 
710 /****************************************************************************************************/
729 template <typename Selection>
730 inline
731 std::pair<typename boost::range_const_iterator<Selection>::type,
732  typename boost::range_size<Selection>::type>
733 selection_find_boundary(const Selection& selection,
734  typename Selection::size_type p)
735 {
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;
740 
741  if (boost::size(selection) == 0)
742  return result_type(boost::end(selection), 0);
743 
744  return selection_find_boundary(selection, p, iterator_category());
745 }
746 
747 /****************************************************************************************************/
779 template <typename SelectionIterator, typename RangeIterator>
780 RangeIterator selection_stable_partition(SelectionIterator selection_first,
781  SelectionIterator selection_last,
782  RangeIterator first,
783  RangeIterator range_first,
784  RangeIterator range_last,
785  std::size_t boundary_count = 0)
786 {
787  std::size_t n(static_cast<std::size_t>(std::distance(selection_first, selection_last)));
788 
789  if (n == 0)
790  return boundary_count % 2 ? range_first : range_last;
791 
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));
795 
796  RangeIterator i(selection_stable_partition(selection_first, selection_middle,
797  first, range_first, range_middle,
798  boundary_count));
799 
800  RangeIterator j(selection_stable_partition(boost::next(selection_middle), selection_last,
801  first, range_middle, range_last,
802  boundary_count + half + 1));
803 
804  return other_of(adobe::rotate(i, range_middle, j), range_middle);
805 }
806 
807 /*************************************************************************************************/
813 template <typename Selection,
814  typename ForwardRange>
815 inline
816 typename boost::range_iterator<ForwardRange>::type
817 selection_stable_partition(const Selection& selection,
818  ForwardRange& range)
819 {
820  return selection_stable_partition(boost::begin(selection), boost::end(selection),
821  boost::begin(range),
822  boost::begin(range), boost::end(range),
823  start_selected(selection));
824 }
825 
826 /*************************************************************************************************/
862 template <typename Selection,
863  typename ForwardRange>
864 std::pair<typename boost::range_iterator<ForwardRange>::type,
865  typename boost::range_iterator<ForwardRange>::type>
866 selection_stable_partition_about(const Selection& selection,
867  ForwardRange& range,
868  std::size_t p,
869  typename boost::range_size<Selection>::type prior_boundary_count = 0)
870 {
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;
874 
875  std::pair<selection_const_iterator, size_type> selection_split =
876  adobe::selection_find_boundary(selection, p);
877 
878  range_iterator first(boost::begin(range));
879  range_iterator range_p(boost::next(first, p));
880  range_iterator last(boost::end(range));
881 
882  range_iterator i(selection_stable_partition(boost::begin(selection), selection_split.first,
883  first, first, range_p,
884  prior_boundary_count));
885 
886  range_iterator j(selection_stable_partition(selection_split.first, boost::end(selection),
887  first, range_p, last,
888  selection_split.second + 1));
889 
890  return std::pair<range_iterator, range_iterator>(i, j);
891 }
892 
893 /****************************************************************************************************/
899 template <typename Selection,
900  typename ForwardRange>
901 Selection index_set_to_selection(const ForwardRange& index_set)
902 {
903  Selection result;
904 
905  // REVISIT (fbrereto) : This would go much faster using divide-and-conquer
906  // and eventually balanced reduction.
907 
908  typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
909 
910  range_const_iterator iter(boost::begin(index_set));
911  range_const_iterator last(boost::end(index_set));
912 
913  for (; iter != last; ++iter)
914  {
915  Selection tmp;
916 
917  tmp.push_back(*iter);
918  tmp.push_back(*iter + 1);
919 
920  result = selection_union(result, tmp);
921  }
922 
923  return result;
924 }
925 
926 /****************************************************************************************************/
932 template <typename Selection,
933  typename OutputIterator>
934 OutputIterator selection_to_index_set(const Selection& selection,
935  typename boost::range_size<Selection>::type max_index,
936  OutputIterator output)
937 {
938  typedef typename boost::range_size<Selection>::type size_type;
939  typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
940 
941  bool selected(start_selected(selection));
942  std::size_t index(0);
943  selection_const_iterator iter(boost::begin(selection));
944  selection_const_iterator last(boost::end(selection));
945 
946  while (iter != last)
947  {
948  while (index != *iter && index != max_index)
949  {
950  if (selected)
951  *output++ = index;
952 
953  ++index;
954  }
955 
956  selected = !selected;
957  ++iter;
958  }
959 
960  return output;
961 }
962 
963 /*************************************************************************************************/
964 
965 } // namespace adobe
966 
967 /*************************************************************************************************/
968 
969 #endif
970 
971 /*************************************************************************************************/
std::pair< I, I > rotate(I f, I m, I l, std::bidirectional_iterator_tag)
Definition: rotate.hpp:39
O selection_difference(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
selection_difference implementation
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
Definition: equal.hpp:38
const T & other_of(const P &pair, const T &x, BinaryPredicate pred)
other_of implementation
Definition: other_of.hpp:37
boost::range_size< Selection >::type size(const Selection &x, const ForwardRange &range)
std::pair< typename boost::range_iterator< ForwardRange >::type, typename boost::range_iterator< ForwardRange >::type > selection_stable_partition_about(const Selection &selection, ForwardRange &range, std::size_t p, typename boost::range_size< Selection >::type prior_boundary_count=0)
O selection_intersection(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
selection_intersection implementation
I lower_bound(I f, I l, const T &x)
O selection_union(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
selection_union implementation
bool operator()(const C1 &x, const C2 &y) const
xor funtion object
void invert(Selection &x)
invert implementation
RangeIterator selection_stable_partition(SelectionIterator selection_first, SelectionIterator selection_last, RangeIterator first, RangeIterator range_first, RangeIterator range_last, std::size_t boundary_count=0)
bool selection_includes(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, C comp, bool s1_inside=false, bool s2_inside=false)
selection_includes implementation
boost::difference_type< I >::type distance(I &range)
Definition: distance.hpp:29
std::pair< O1, O2 > selection_partition_copy(const Selection &selection, ForwardRange &range, O1 false_output, O2 true_output)
selection_partition_copy implementation
OutputIterator copy(const InputRange &range, OutputIterator result)
copy implementation
Definition: copy.hpp:43
O selection_symmetric_difference(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
selection_symmetric_difference implementation
OutputIterator selection_to_index_set(const Selection &selection, typename boost::range_size< Selection >::type max_index, OutputIterator output)
Selection index_set_to_selection(const ForwardRange &index_set)
bool start_selected(const Selection &x)
start_selected implementation
boost::range_difference< InputRange >::type count(InputRange &range, T &value)
count implementation
Definition: count.hpp:41
std::pair< typename boost::range_const_iterator< Selection >::type, typename boost::range_size< Selection >::type > selection_find_boundary(const Selection &selection, typename Selection::size_type p, std::random_access_iterator_tag)
OutputIterator selection_copy(const Selection &x, const ForwardRange &range, OutputIterator output)
O selection_operation_remainder(S first, S last, O output, bool this_inside, bool other_inside, P pred)
O selection_operation(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, bool s1_inside, bool s2_inside, P pred, C comp)
selection_operation implementation
bool is_selected(const Selection &x, typename Selection::value_type index)
UnaryFunction selection_foreach(const Selection &x, const ForwardRange &range, UnaryFunction proc)
selection_foreach implementation
boost::range_size< Selection >::type size(const Selection &x)
pair< T1, T2 > make_pair(T1 x, T2 y)
Definition: pair.hpp:109
I upper_bound(I f, I l, const T &x)

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google