summaryrefslogtreecommitdiff
path: root/boost/move/algo/detail/merge.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/move/algo/detail/merge.hpp')
-rw-r--r--boost/move/algo/detail/merge.hpp126
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