static I impl()

in include/range/v3/algorithm/stable_partition.hpp [59:118]

• 39 lines of code
• 7 McCabe index (conditional complexity)

            static I impl(I begin, I end, C pred, P proj, D len, Pair p, concepts::ForwardIterator *fi)
            {
                // *begin is known to be false
                // len >= 1
                if (len == 1)
                    return begin;
                if(len == 2)
                {
                    I tmp = begin;
                    if(pred(proj(*++tmp)))
                    {
                        ranges::iter_swap(begin, tmp);
                        return tmp;
                    }
                    return begin;
                }
                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));
                    // 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
                    ranges::move(p.first, std::get<2>(res).base().base(), std::get<1>(res));
                    // h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
                    return std::get<1>(res);
                }
                // Else not enough buffer, do in place
                // len >= 3
                D half = len / 2;  // half >= 2
                I middle = next(begin, half);
                // recurse on [begin, middle), *begin know to be false
                // F?????????????????
                // f       m         l
                I begin_false = stable_partition_fn::impl(begin, middle, pred, proj, half, p, fi);
                // TTTFFFFF??????????
                // f  ff   m         l
                // recurse on [middle, end], except increase middle until *(middle) is false, *end know to be true
                I m1 = middle;
                D len_half = len - half;
                while(pred(proj(*m1)))
                {
                    if(++m1 == end)
                        return ranges::rotate(begin_false, middle, end).begin();
                    --len_half;
                }
                // TTTFFFFFTTTF??????
                // f  ff   m  m1     l
                I end_false = stable_partition_fn::impl(m1, end, pred, proj, len_half, p, fi);
                // TTTFFFFFTTTTTFFFFF
                // f  ff   m    sf   l
                return ranges::rotate(begin_false, middle, end_false).begin();
                // TTTTTTTTFFFFFFFFFF
                //         |
            }