Documentation Overview Building ASL Documentation Library Wiki Docs Indices Browse Perforce More Info Release Notes Wiki Site Search License Success Stories Contributors Media Download Perforce Depots Support ASL SourceForge Home Mailing Lists Discussion Forums Report Bugs Suggest Features Contribute to ASL RSS Short-text news Full-text news File releases Other Adobe Projects Adobe Air Adobe GIL C++ Benchmarks Adobe Labs Adobe Media Gallery Adobe XMP Tamarin project (Mozilla Foundation) Other Resources Boost RIAForge SGI STL

selection_algorithms.hpp Go to the documentation of this file. /* Copyright 2005-2007 Adobe Systems Incorporated Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt or a copy at http://stlab.adobe.com/licenses.html) */ /*************************************************************************************************/ #ifndef ADOBE_ALGORITHM_SELECTION_HPP #define ADOBE_ALGORITHM_SELECTION_HPP #include <adobe/config.hpp> #include <algorithm> #include <functional> #include <vector> #include <boost/range/begin.hpp> #include <boost/range/end.hpp> #include <boost/range/value_type.hpp> #include <boost/range/size_type.hpp> #include <boost/range/size.hpp> #include <adobe/algorithm/other_of.hpp> #include <adobe/algorithm/rotate.hpp> #include <adobe/iterator/type_functions.hpp> /*************************************************************************************************/ namespace adobe { /*************************************************************************************************/ /*************************************************************************************************/ template <typename S, // S models ForwardIterator, value_type(S) == I typename O, // O models OutputIterator typename P> // P models BinaryPredicate inline O selection_operation_remainder(S first, S last, O output, bool this_inside, bool other_inside, P pred) { bool prev_op_result(pred(this_inside, other_inside)); while (first != last) { this_inside = !this_inside; bool cur_op_result(pred(this_inside, other_inside)); if (prev_op_result ^ cur_op_result) *output++ = *first; prev_op_result = cur_op_result; ++first; } return output; } /*************************************************************************************************/ template <typename C1, // C1 models ConvertibleToBool typename C2 = C1> // C2 models ConvertibleToBool struct logical_xor : std::binary_function<C1, C2, bool> { bool operator()(const C1& x, const C2& y) const { return static_cast<bool>(x) ^ static_cast<bool>(y); } }; /*************************************************************************************************/ template <typename S1, // S1 models ForwardIterator, value_type(S1) == value_type(S2) typename S2, // S2 models ForwardIterator, value_type(S2) == value_type(S1) typename O, // O models OutputIterator typename P, // P models BinaryPredicate typename C> // C models StrictWeakOrdering 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) { if (s1_first == s1_last) return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside, pred); else if (s2_first == s2_last) return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside, pred); bool prev_op_result(pred(s1_inside, s2_inside)); while (true) { typename std::iterator_traits<S1>::value_type next(comp(*s1_first, *s2_first) ? *s1_first : *s2_first); if (*s1_first == next) { s1_inside = !s1_inside; ++s1_first; } if (*s2_first == next) { s2_inside = !s2_inside; ++s2_first; } bool cur_op_result(pred(s1_inside, s2_inside)); if (prev_op_result ^ cur_op_result) *output++ = next; prev_op_result = cur_op_result; if (s1_first == s1_last) return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside, pred); else if (s2_first == s2_last) return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside, pred); } return output; } /*************************************************************************************************/ template <typename S1, // S1 models ForwardIterator, value_type(S1) == I typename S2, // S2 models ForwardIterator, value_type(S2) == I typename O, // O models OutputIterator typename C> // C models StrictWeakOrdering inline 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) { return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside, std::logical_or<bool>(), comp); } /*************************************************************************************************/ template <typename S1, // S1 models ForwardIterator, value_type(S1) == I typename S2, // S2 models ForwardIterator, value_type(S2) == I typename O, // O models OutputIterator typename C> // C models StrictWeakOrdering inline 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) { return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside, std::logical_and<bool>(), comp); } /*************************************************************************************************/ template <typename S1, // S1 models ForwardIterator, value_type(S1) == I typename S2, // S2 models ForwardIterator, value_type(S2) == I typename O, // O models OutputIterator typename C> // C models StrictWeakOrdering inline 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) { return selection_intersection(s1_first, s1_last, s2_first, s2_last, output, comp, s1_inside, !s2_inside); } /*************************************************************************************************/ template <typename S1, // S1 models ForwardIterator, value_type(S1) == I typename S2, // S2 models ForwardIterator, value_type(S2) == I typename O, // O models OutputIterator typename C> // C models StrictWeakOrdering inline 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) { return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside, logical_xor<bool>(), comp); } /*************************************************************************************************/ template <typename S1, // S1 models InputIterator, value_type(S1) == I typename S2, // S2 models InputIterator, value_type(S2) == I typename C> // C models StrictWeakOrdering inline 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) { if (s1_inside == s2_inside) { typedef typename std::iterator_traits<S1>::value_type value_type; std::vector<value_type> result; selection_intersection(s1_first, s1_last, s2_first, s2_last, std::back_inserter(result), comp, s1_inside, s2_inside); return std::equal(s2_first, s2_last, result.begin()); } else if (s1_inside) { return selection_includes(boost::next(s1_first), s1_last, s2_first, s2_last, comp, !s1_inside, s2_inside); } // s2_inside == true return selection_includes(s1_first, s1_last, boost::next(s2_first), s2_last, comp, s1_inside, !s2_inside); } /****************************************************************************************************/ template <typename Selection1, typename Selection2> Selection1 selection_intersection(const Selection1& x, const Selection2& y) { if (&x == &y) return x; Selection1 result; adobe::selection_intersection(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result), std::less<typename boost::range_value<Selection1>::type>(), start_selected(x), start_selected(y)); return result; } /****************************************************************************************************/ template <typename Selection1, typename Selection2> Selection1 selection_union(const Selection1& x, const Selection2& y) { if (&x == &y) return x; Selection1 result; adobe::selection_union(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result), std::less<typename boost::range_value<Selection1>::type>(), start_selected(x), start_selected(y)); return result; } /****************************************************************************************************/ template <typename Selection1, typename Selection2> Selection1 selection_difference(const Selection1& x, const Selection2& y) { if (&x == &y) return Selection1(); Selection1 result; adobe::selection_difference(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result), std::less<typename boost::range_value<Selection1>::type>(), start_selected(x), start_selected(y)); return result; } /****************************************************************************************************/ template <typename Selection1, typename Selection2> Selection1 selection_symmetric_difference(const Selection1& x, const Selection2& y) { if (&x == &y) return Selection1(); Selection1 result; adobe::selection_symmetric_difference(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result), std::less<typename boost::range_value<Selection1>::type>(), start_selected(x), start_selected(y)); return result; } /****************************************************************************************************/ template <typename Selection1, typename Selection2> bool selection_includes(const Selection1& x, const Selection2& y) { if (&x == &y) return true; return adobe::selection_includes(x.begin(), x.end(), y.begin(), y.end(), std::less<typename boost::range_value<Selection1>::type>(), start_selected(x), start_selected(y)); } /****************************************************************************************************/ template <typename Selection> inline void invert(Selection& x) { x.invert(); } /****************************************************************************************************/ template <typename Selection> inline bool start_selected(const Selection& x) { return x.start_selected(); } /****************************************************************************************************/ template <typename Selection> inline typename boost::range_size<Selection>::type size(const Selection& x) { return x.size(); } /****************************************************************************************************/ template <typename Selection, typename ForwardRange> typename boost::range_size<Selection>::type size(const Selection& x, const ForwardRange& range) { typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; typedef typename boost::range_size<Selection>::type selection_size_type; typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator; if (x.empty()) return 0; // this is the case when the selection has no elements, but it starts selected // (in other words, every item in the selection is toggled as selected) if (x.size() == 0) return boost::size(range); selection_const_iterator s_iter(boost::begin(x)); selection_const_iterator s_last(boost::end(x)); range_const_iterator prev(boost::begin(range)); range_const_iterator iter(boost::next(prev, *s_iter)); range_const_iterator last(boost::end(range)); selection_size_type result(0); bool inside(start_selected(x)); while (true) { if (inside) result += static_cast<selection_size_type>(std::distance(prev, iter)); if (iter == last) break; prev = iter; iter = ++s_iter == s_last ? last : boost::next(boost::begin(range), *s_iter); inside = !inside; } return result; } /****************************************************************************************************/ template <typename Selection> bool is_selected(const Selection& x, typename Selection::value_type index) { typename boost::range_const_iterator<Selection>::type found(std::upper_bound(boost::begin(x), boost::end(x), index)); typename boost::range_size<Selection>::type count(std::distance(boost::begin(x), found)); return (count % 2 == 1) ^ start_selected(x); } /****************************************************************************************************/ template <typename Selection, typename ForwardRange, typename OutputIterator> OutputIterator selection_copy(const Selection& x, const ForwardRange& range, OutputIterator output) { typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator; if (boost::size(range) == 0) return output; bool inside(start_selected(x)); selection_const_iterator s_iter(boost::begin(x)); selection_const_iterator s_last(boost::end(x)); range_const_iterator iter(boost::begin(range)); range_const_iterator last(boost::end(range)); while (iter != last) { if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter)) { ++s_iter; inside = !inside; } if (inside) *output++ = *iter; ++iter; } return output; } /*************************************************************************************************/ template <typename Selection, typename ForwardRange, typename O1, // O1 models OutputIterator typename O2> // O2 models OutputIterator std::pair<O1, O2> selection_partition_copy(const Selection& selection, ForwardRange& range, O1 false_output, O2 true_output) { typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; typedef typename boost::range_iterator<ForwardRange>::type range_iterator; if (boost::size(range) == 0) return std::make_pair(false_output, true_output); selection_const_iterator selection_first(boost::begin(selection)); selection_const_iterator selection_last(boost::end(selection)); range_iterator first(boost::begin(range)); range_iterator last(boost::end(range)); bool inside(start_selected(selection)); while (true) { range_iterator copy_last(selection_first == selection_last ? last : boost::next(boost::begin(range), *selection_first)); // REVISIT (fbrereto) : It'd be nice to collapse the following into ? : // notation, but some compilers require that the // types returned by ? : be the same, which we cannot // guarantee here. if (inside) std::copy(first, copy_last, true_output); else std::copy(first, copy_last, false_output); if (copy_last == last) break; first = copy_last; ++selection_first; inside = !inside; } return std::make_pair(false_output, true_output); } /****************************************************************************************************/ template <typename Selection, typename ForwardRange, typename UnaryFunction> UnaryFunction selection_foreach(const Selection& x, const ForwardRange& range, UnaryFunction proc) { typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator; bool inside(start_selected(x)); selection_const_iterator s_iter(boost::begin(x)); selection_const_iterator s_last(boost::end(x)); range_const_iterator iter(boost::begin(range)); range_const_iterator last(boost::end(range)); while (iter != last) { if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter)) { ++s_iter; inside = !inside; } if (inside) proc(*iter); ++iter; } return proc; } /****************************************************************************************************/ template <typename Selection> inline 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) { typedef typename boost::range_const_iterator<Selection>::type const_iterator; typedef typename boost::range_size<Selection>::type size_type; typedef std::pair<const_iterator, size_type> result_type; const_iterator bound(std::lower_bound(boost::begin(selection), boost::end(selection), p)); return result_type(bound, static_cast<size_type>(std::distance(boost::begin(selection), bound))); } /****************************************************************************************************/ template <typename Selection> 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::forward_iterator_tag) { typedef typename boost::range_const_iterator<Selection>::type const_iterator; typedef typename boost::range_size<Selection>::type size_type; typedef std::pair<const_iterator, size_type> result_type; const_iterator iter(boost::begin(selection)); const_iterator last(boost::end(selection)); size_type boundary_count(0); while (iter != last && *iter < p) { ++boundary_count; ++iter; } return result_type(iter, boundary_count); } /****************************************************************************************************/ template <typename Selection> inline 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) { typedef typename boost::range_const_iterator<Selection>::type const_iterator; typedef typename boost::range_size<Selection>::type size_type; typedef std::pair<const_iterator, size_type> result_type; typedef typename iterator_category<const_iterator>::type iterator_category; if (boost::size(selection) == 0) return result_type(boost::end(selection), 0); return selection_find_boundary(selection, p, iterator_category()); } /****************************************************************************************************/ template <typename SelectionIterator, typename RangeIterator> RangeIterator selection_stable_partition(SelectionIterator selection_first, SelectionIterator selection_last, RangeIterator first, RangeIterator range_first, RangeIterator range_last, std::size_t boundary_count = 0) { std::size_t n(static_cast<std::size_t>(std::distance(selection_first, selection_last))); if (n == 0) return boundary_count % 2 ? range_first : range_last; std::size_t half(n / 2); SelectionIterator selection_middle(boost::next(selection_first, half)); RangeIterator range_middle(boost::next(first, *selection_middle)); RangeIterator i(selection_stable_partition(selection_first, selection_middle, first, range_first, range_middle, boundary_count)); RangeIterator j(selection_stable_partition(boost::next(selection_middle), selection_last, first, range_middle, range_last, boundary_count + half + 1)); return other_of(adobe::rotate(i, range_middle, j), range_middle); } /*************************************************************************************************/ template <typename Selection, typename ForwardRange> inline typename boost::range_iterator<ForwardRange>::type selection_stable_partition(const Selection& selection, ForwardRange& range) { return selection_stable_partition(boost::begin(selection), boost::end(selection), boost::begin(range), boost::begin(range), boost::end(range), start_selected(selection)); } /*************************************************************************************************/ template <typename Selection, typename ForwardRange> 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) { typedef typename boost::range_size<Selection>::type size_type; typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; typedef typename boost::range_iterator<ForwardRange>::type range_iterator; std::pair<selection_const_iterator, size_type> selection_split = adobe::selection_find_boundary(selection, p); range_iterator first(boost::begin(range)); range_iterator range_p(boost::next(first, p)); range_iterator last(boost::end(range)); range_iterator i(selection_stable_partition(boost::begin(selection), selection_split.first, first, first, range_p, prior_boundary_count)); range_iterator j(selection_stable_partition(selection_split.first, boost::end(selection), first, range_p, last, selection_split.second + 1)); return std::pair<range_iterator, range_iterator>(i, j); } /****************************************************************************************************/ template <typename Selection, typename ForwardRange> Selection index_set_to_selection(const ForwardRange& index_set) { Selection result; // REVISIT (fbrereto) : This would go much faster using divide-and-conquer // and eventually balanced reduction. typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator; range_const_iterator iter(boost::begin(index_set)); range_const_iterator last(boost::end(index_set)); for (; iter != last; ++iter) { Selection tmp; tmp.push_back(*iter); tmp.push_back(*iter + 1); result = selection_union(result, tmp); } return result; } /****************************************************************************************************/ template <typename Selection, typename OutputIterator> OutputIterator selection_to_index_set(const Selection& selection, typename boost::range_size<Selection>::type max_index, OutputIterator output) { typedef typename boost::range_size<Selection>::type size_type; typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator; bool selected(start_selected(selection)); std::size_t index(0); selection_const_iterator iter(boost::begin(selection)); selection_const_iterator last(boost::end(selection)); while (iter != last) { while (index != *iter && index != max_index) { if (selected) *output++ = index; ++index; } selected = !selected; ++iter; } return output; } /*************************************************************************************************/ } // namespace adobe /*************************************************************************************************/ #endif /*************************************************************************************************/

• Company | 
• Online Privacy Policy | 
• Terms of Use | 
• Contact Us | 
• Accessibility | 
• Report Piracy | 
• Permissions & Trademarks | 
• Product License Agreements | 
• Send Feedback

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