static I impl()

in include/range/v3/algorithm/stable_partition.hpp [145:228]


            static I impl(I begin, I end, C pred, P proj, D len, Pair p, concepts::BidirectionalIterator *bi)
            {
                // *begin is known to be false
                // *end is known to be true
                // len >= 2
                if(len == 2)
                {
                    ranges::iter_swap(begin, end);
                    return end;
                }
                if(len == 3)
                {
                    I tmp = begin;
                    if(pred(proj(*++tmp)))
                    {
                        ranges::iter_swap(begin, tmp);
                        ranges::iter_swap(tmp, end);
                        return end;
                    }
                    ranges::iter_swap(tmp, end);
                    ranges::iter_swap(begin, tmp);
                    return tmp;
                }
                if(len <= p.second)
                {   // The buffer is big enough to use
                    using value_type = iterator_value_t<I>;
                    std::unique_ptr<value_type, detail::destroy_n<value_type>> h{p.first, {}};
                    // Move the falses into the temporary buffer, and the trues to the front of the line
                    // Update begin to always point to the end of the trues
                    auto buf = ranges::make_counted_raw_storage_iterator(p.first, h.get_deleter());
                    *buf = iter_move(begin);
                    ++buf;
                    auto res = partition_move(next(begin), end, begin, buf, std::ref(pred), std::ref(proj));
                    begin = std::get<1>(res);
                    // move *end, known to be true
                    *begin = iter_move(std::get<0>(res));
                    ++begin;
                    // All trues now at start of range, all falses in buffer
                    // Move falses back into range, but don't mess up begin which points to first false
                    move(p.first, std::get<2>(res).base().base(), begin);
                    // h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
                    return begin;
                }
                // Else not enough buffer, do in place
                // len >= 4
                I middle = begin;
                D half = len / 2;  // half >= 2
                advance(middle, half);
                // recurse on [begin, middle-1], except reduce middle-1 until *(middle-1) is true, *begin know to be false
                // F????????????????T
                // f       m        l
                I m1 = middle;
                I begin_false = begin;
                D len_half = half;
                while(!pred(proj(*--m1)))
                {
                    if(m1 == begin)
                        goto first_half_done;
                    --len_half;
                }
                // F???TFFF?????????T
                // f   m1  m        l
                begin_false = stable_partition_fn::impl(begin, m1, pred, proj, len_half, p, bi);
            first_half_done:
                // TTTFFFFF?????????T
                // f  ff   m        l
                // recurse on [middle, end], except increase middle until *(middle) is false, *end know to be true
                m1 = middle;
                len_half = len - half;
                while(pred(proj(*m1)))
                {
                    if(++m1 == end)
                        return ranges::rotate(begin_false, middle, ++end).begin();
                    --len_half;
                }
                // TTTFFFFFTTTF?????T
                // f  ff   m  m1    l
                I end_false = stable_partition_fn::impl(m1, end, pred, proj, len_half, p, bi);
                // TTTFFFFFTTTTTFFFFF
                // f  ff   m    sf  l
                return ranges::rotate(begin_false, middle, end_false).begin();
                // TTTTTTTTFFFFFFFFFF
                //         |
            }