WIP: Another take on stable_adapter

stable_adapter.h

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2016-2018 Morwenn
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#ifndef CPPSORT_ADAPTERS_STABLE_ADAPTER_H_
#define CPPSORT_ADAPTERS_STABLE_ADAPTER_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <exception>
#include <functional>
#include <iterator>
#include <memory>
#include <tuple>
#include <type_traits>
#include <utility>
#include <cpp-sort/sorter_facade.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/utility/as_function.h>
#include <cpp-sort/utility/functional.h>
#include <cpp-sort/utility/iter_move.h>
#include "../detail/associate_iterator.h"
#include "../detail/checkers.h"
#include "../detail/iterator_traits.h"
#include "../detail/memory.h"
#include "../detail/type_traits.h"

namespace cppsort
{
    namespace detail
    {
        ////////////////////////////////////////////////////////////
        // Stable comparison functions

        template<
            typename Compare,
            typename Projection = utility::identity
        >
        class stable_compare
        {
            private:

                using projection_t = decltype(utility::as_function(std::declval<Projection&>()));
                using compare_t = decltype(utility::as_function(std::declval<Compare&>()));
                std::tuple<compare_t, projection_t> data;

            public:

                stable_compare(Compare compare, Projection projection={}):
                    data(utility::as_function(compare), utility::as_function(projection))
                {}

                template<typename T, typename U>
                auto operator()(T&& lhs, U&& rhs)
                    -> bool
                {
                    if (std::get<0>(data)(std::get<1>(data)(std::forward<T>(lhs).first),
                                          std::get<1>(data)(std::forward<U>(rhs).first)))
                    {
                        return true;
                    }
                    if (std::get<0>(data)(std::get<1>(data)(std::forward<U>(rhs).first),
                                          std::get<1>(data)(std::forward<T>(lhs).first)))
                    {
                        return false;
                    }
                    return lhs.second < rhs.second;
                }
        };

        template<
            typename Compare,
            typename Projection = utility::identity
        >
        class indirect_stable_compare
        {
            private:

                using projection_t = decltype(utility::as_function(std::declval<Projection&>()));
                using compare_t = decltype(utility::as_function(std::declval<Compare&>()));
                std::tuple<compare_t, projection_t> data;

            public:

                indirect_stable_compare(Compare compare, Projection projection={}):
                    data(utility::as_function(compare), utility::as_function(projection))
                {}

                template<typename T, typename U>
                auto operator()(T&& lhs, U&& rhs)
                    -> bool
                {
                    if (std::get<0>(data)(std::get<1>(data)(std::forward<T>(lhs).get()),
                                          std::get<1>(data)(std::forward<U>(rhs).get())))
                    {
                        return true;
                    }
                    if (std::get<0>(data)(std::get<1>(data)(std::forward<U>(rhs).get()),
                                          std::get<1>(data)(std::forward<T>(lhs).get())))
                    {
                        return false;
                    }
                    return lhs.data < rhs.data;
                }
        };

        template<typename Compare, typename Projection=utility::identity>
        auto make_stable_compare(Compare compare, Projection projection={})
            -> stable_compare<Compare, Projection>
        {
            return { compare, projection };
        }

        template<typename Compare, typename Projection=utility::identity>
        auto make_indirect_stable_compare(Compare compare, Projection projection={})
            -> indirect_stable_compare<Compare, Projection>
        {
            return { compare, projection };
        }

        ////////////////////////////////////////////////////////////
        // Adapter

        template<typename Sorter>
        struct stable_adapter_impl:
            check_iterator_category<Sorter>
        {
            template<
                typename Iterator,
                typename Compare = std::less<>,
                typename Projection = utility::identity,
                typename = std::enable_if_t<is_projection_iterator_v<
                    Projection, Iterator, Compare
                >>
            >
            auto operator()(Iterator first, Iterator last,
                            Compare compare={}, Projection projection={}) const
                -> decltype(auto)
            {
                //
                // The idea behind this algorithm is to compare two values with the
                // given function, and to also compare their original positions in
                // the collection to ensure stability when they are equivalent
                //
                // The algorithm tries to allocate enough memory for value/position
                // pairs that it will sort in the temporary buffer before moving the
                // sorted values back to the original collection
                //
                // If it can't allocate that much memory, it will then try to allocate
                // memory for iterator/position pairs instead and sort the original
                // collection at a distance while sorting the pairs in the temporary
                // buffer
                //

                using difference_type = difference_type_t<Iterator>;
                using rvalue_reference = remove_cvref_t<rvalue_reference_t<Iterator>>;

                // If possible, store value/position pairs
                using value_position_t = std::pair<rvalue_reference, difference_type>;
                // Otherwise store iterator/position pairs
                using iterator_position_t = association<Iterator, difference_type>;

                auto size = std::distance(first, last);

                // Use the throwing allocation function if iterator/position pairs
                // aren't smaller than value/position ones to avoid retrying to
                // allocate memory when there's obviously not enough
                auto buffer_size = size * sizeof(value_position_t);
                std::unique_ptr<value_position_t, operator_deleter> buffer(static_cast<value_position_t*>(
                    sizeof(value_position_t) <= sizeof(iterator_position_t) ?
                        ::operator new(buffer_size) :
                        ::operator new(buffer_size, std::nothrow)
                ));

                if (buffer != nullptr) {
                    ////////////////////////////////////////////////////////////
                    // Decorate-sort-undecorate algorithm

                    destruct_n<value_position_t> d(0);
                    std::unique_ptr<value_position_t, destruct_n<value_position_t>&> h2(buffer.get(), d);

                    // Create value/position pairs
                    difference_type count = 0;
                    auto it = first;
                    for (auto ptr = buffer.get() ; it != last ; ++d, (void) ++it, ++ptr) {
                        using utility::iter_move;
                        ::new(ptr) value_position_t(iter_move(it), count++);
                    }

                    // This should be called *after* the return, but no regular void, etc...
                    // so dirty hand-made local scope_exit thingy instead
                    struct move_back_t
                    {
                        Iterator first;
                        Iterator last;
                        std::unique_ptr<value_position_t, operator_deleter>& buffer;

                        move_back_t(Iterator first, Iterator last,
                                    std::unique_ptr<value_position_t, operator_deleter>& buffer):
                            first(first), last(last),
                            buffer(buffer)
                        {}

                        ~move_back_t()
                        {
#ifndef __cpp_lib_uncaught_exceptions
                            if (not std::uncaught_exception()) {
#else
                            if (std::uncaught_exceptions() == 0) {
#endif
                                // If we exit the scope normally, move the sorted values back
                                // to the original collection
                                for (auto ptr = buffer.get() ; first != last ; ++first, (void) ++ptr) {
                                    *first = std::move(ptr->first);
                                }
                            }
                        };
                    } move_back(first, last, buffer);

                    // Stably sort the value/position pairs
                    return Sorter{}(
                        buffer.get(), buffer.get() + size,
                        make_stable_compare(std::move(compare), std::move(projection))
                    );

                } else {
                    ////////////////////////////////////////////////////////////
                    // Decorate-sort at a distance algorithm

                    std::unique_ptr<iterator_position_t, operator_deleter> iterators(
                        static_cast<iterator_position_t*>(::operator new(size * sizeof(iterator_position_t)))
                    );
                    destruct_n<iterator_position_t> d(0);
                    std::unique_ptr<iterator_position_t, destruct_n<iterator_position_t>&> h2(iterators.get(), d);

                    // Associate iterators to their position
                    difference_type count = 0;
                    for (auto ptr = iterators.get() ; first != last ; ++d, (void) ++first, ++ptr) {
                        ::new(ptr) iterator_position_t(first, count++);
                    }

                    // Sort at a distance
                    return Sorter{}(
                        make_associate_iterator(iterators.get()),
                        make_associate_iterator(iterators.get() + size),
                        make_indirect_stable_compare(std::move(compare), std::move(projection))
                    );
                }
            }

            ////////////////////////////////////////////////////////////
            // Sorter traits

            using is_always_stable = std::true_type;
        };
    }

    // Expose the underlying mechanism
    template<typename Sorter>
    struct make_stable:
        sorter_facade<detail::stable_adapter_impl<Sorter>>
    {
        make_stable() = default;

        // Automatic deduction guide
        constexpr explicit make_stable(Sorter) noexcept {}
    };

    // Actual sorter
    template<typename Sorter>
    struct stable_adapter:
        detail::check_iterator_category<Sorter>,
        sorter_facade_fptr<stable_adapter<Sorter>>
    {
        stable_adapter() = default;

        // Automatic deduction guide
        constexpr explicit stable_adapter(Sorter) noexcept {}


        template<
            typename... Args,
            typename = std::enable_if_t<is_stable_v<Sorter(Args...)>>
        >
        auto operator()(Args&&... args) const
            -> decltype(Sorter{}(std::forward<Args>(args)...))
        {
            return Sorter{}(std::forward<Args>(args)...);
        }

        template<
            typename... Args,
            typename = std::enable_if_t<not is_stable_v<Sorter(Args...)>>,
            typename = void
        >
        auto operator()(Args&&... args) const
            -> decltype(make_stable<Sorter>{}(std::forward<Args>(args)...))
        {
            return make_stable<Sorter>{}(std::forward<Args>(args)...);
        }

        ////////////////////////////////////////////////////////////
        // Sorter traits

        using is_always_stable = std::true_type;
    };
}

#ifdef CPPSORT_ADAPTERS_SELF_SORT_ADAPTER_DONE_
#include "../detail/stable_adapter_self_sort_adapter.h"
#endif

#define CPPSORT_ADAPTERS_STABLE_ADAPTER_DONE_

#endif // CPPSORT_ADAPTERS_STABLE_ADAPTER_H_