diff options
Diffstat (limited to 'boost/move/algo/detail/merge.hpp')
-rw-r--r-- | boost/move/algo/detail/merge.hpp | 126 |
1 files changed, 51 insertions, 75 deletions
diff --git a/boost/move/algo/detail/merge.hpp b/boost/move/algo/detail/merge.hpp index 621dfa28af..860773579c 100644 --- a/boost/move/algo/detail/merge.hpp +++ b/boost/move/algo/detail/merge.hpp @@ -256,56 +256,67 @@ void swap_merge_right op_merge_right(first1, last1, last2, buf_last, comp, swap_op()); } -template <class BidirIt, class Distance, class Compare> +//Complexity: min(len1,len2)^2 + max(len1,len2) +template<class RandIt, class Compare> +void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp) +{ + if((middle - first) < (last - middle)){ + while(first != middle){ + RandIt const old_last1 = middle; + middle = boost::movelib::lower_bound(middle, last, *first, comp); + first = rotate_gcd(first, old_last1, middle); + if(middle == last){ + break; + } + do{ + ++first; + } while(first != middle && !comp(*middle, *first)); + } + } + else{ + while(middle != last){ + RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp); + last = rotate_gcd(p, middle, last); + middle = p; + if(middle == first){ + break; + } + --p; + do{ + --last; + } while(middle != last && !comp(last[-1], *p)); + } + } +} + +static const std::size_t MergeBufferlessONLogNRotationThreshold = 32; + +template <class RandIt, class Distance, class Compare> void merge_bufferless_ONlogN_recursive - (BidirIt first, BidirIt middle, BidirIt last, Distance len1, Distance len2, Compare comp) + (RandIt first, RandIt middle, RandIt last, Distance len1, Distance len2, Compare comp) { - typedef typename iterator_traits<BidirIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::size_type size_type; + while(1) { - //#define MERGE_BUFFERLESS_RECURSIVE_OPT - #ifndef MERGE_BUFFERLESS_RECURSIVE_OPT - if (len2 == 0) { + //trivial cases + if (!len2) { return; } - - if (!len1) { + else if (!len1) { return; } - - if ((len1 | len2) == 1) { + else if (size_type(len1 | len2) == 1u) { if (comp(*middle, *first)) adl_move_swap(*first, *middle); return; } - #else - if (len2 == 0) { + else if(size_type(len1+len2) < MergeBufferlessONLogNRotationThreshold){ + merge_bufferless_ON2(first, middle, last, comp); return; } - if (!len1) { - return; - } - BidirIt middle_prev = middle; --middle_prev; - if(!comp(*middle, *middle_prev)) - return; - - while(true) { - if (comp(*middle, *first)) - break; - ++first; - if(--len1 == 1) - break; - } - - if (len1 == 1 && len2 == 1) { - //comp(*middle, *first) == true already tested in the loop - adl_move_swap(*first, *middle); - return; - } - #endif - - BidirIt first_cut = first; - BidirIt second_cut = middle; + RandIt first_cut = first; + RandIt second_cut = middle; Distance len11 = 0; Distance len22 = 0; if (len1 > len2) { @@ -320,20 +331,18 @@ void merge_bufferless_ONlogN_recursive first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); len11 = size_type(first_cut - first); } - BidirIt new_middle = rotate_gcd(first_cut, middle, second_cut); + RandIt new_middle = rotate_gcd(first_cut, middle, second_cut); //Avoid one recursive call doing a manual tail call elimination on the biggest range const Distance len_internal = len11+len22; if( len_internal < (len1 + len2 - len_internal) ) { merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp); - //merge_bufferless_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp); first = new_middle; middle = second_cut; len1 -= len11; len2 -= len22; } else { - //merge_bufferless_recursive(first, first_cut, new_middle, len11, len22, comp); merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp); middle = first_cut; last = new_middle; @@ -344,50 +353,17 @@ void merge_bufferless_ONlogN_recursive } //Complexity: NlogN -template<class BidirIt, class Compare> -void merge_bufferless_ONlogN(BidirIt first, BidirIt middle, BidirIt last, Compare comp) +template<class RandIt, class Compare> +void merge_bufferless_ONlogN(RandIt first, RandIt middle, RandIt last, Compare comp) { merge_bufferless_ONlogN_recursive (first, middle, last, middle - first, last - middle, comp); } -//Complexity: min(len1,len2)^2 + max(len1,len2) -template<class RandIt, class Compare> -void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp) -{ - if((middle - first) < (last - middle)){ - while(first != middle){ - RandIt const old_last1 = middle; - middle = boost::movelib::lower_bound(middle, last, *first, comp); - first = rotate_gcd(first, old_last1, middle); - if(middle == last){ - break; - } - do{ - ++first; - } while(first != middle && !comp(*middle, *first)); - } - } - else{ - while(middle != last){ - RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp); - last = rotate_gcd(p, middle, last); - middle = p; - if(middle == first){ - break; - } - --p; - do{ - --last; - } while(middle != last && !comp(last[-1], *p)); - } - } -} - template<class RandIt, class Compare> void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp) { - //#define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE + #define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE merge_bufferless_ONlogN(first, middle, last, comp); #else |