<commit_before>/*
 * Copyright (c) 2021 Morwenn
 * SPDX-License-Identifier: MIT
 */
#ifndef CPPSORT_DETAIL_CONTAINER_AWARE_MEL_SORT_H_
#define CPPSORT_DETAIL_CONTAINER_AWARE_MEL_SORT_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <forward_list>
#include <functional>
#include <iterator>
#include <list>
#include <type_traits>
#include <utility>
#include <vector>
#include <cpp-sort/comparators/projection_compare.h>
#include <cpp-sort/fwd.h>
#include <cpp-sort/sorter_facade.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/utility/functional.h>
#include <cpp-sort/utility/size.h>
#include "../functional.h"
#include "../lower_bound.h"

namespace cppsort
{
    namespace detail
    {
        template<typename Compare, typename Projection, typename... Args>
        auto list_mel_sort(std::list<Args...>& collection, Compare compare, Projection projection)
            -> void
        {
            // NOTE: see detail/melsort.h for detailed explanations
            auto&& comp = utility::as_function(compare);
            auto&& proj = utility::as_function(projection);

            if (collection.size() < 2) return;

            // Encroaching lists
            std::vector<std::list<Args...>> lists;
            lists.emplace_back();
            lists.back().splice(lists.back().begin(), collection, collection.begin());

            ////////////////////////////////////////////////////////////
            // Create encroaching lists

            while (not collection.empty()) {
                auto&& value = proj(collection.front());

                auto& last_list = lists.back();
                if (not comp(value, proj(last_list.back()))) {
                    // Element belongs to the tails (bigger elements)
                    auto insertion_point = detail::lower_bound(
                        lists.begin(), std::prev(lists.end()), value, invert(compare),
                        [&proj](auto& list) -> decltype(auto) { return proj(list.back()); }
                    );
                    insertion_point->splice(insertion_point->end(), collection, collection.begin());
                } else if (not comp(proj(last_list.front()), value)) {
                    // Element belongs to the heads (smaller elements)
                    auto insertion_point = detail::lower_bound(
                        lists.begin(), std::prev(lists.end()), value, compare,
                        [&proj](auto& list) -> decltype(auto) { return proj(list.front()); }
                    );
                    insertion_point->splice(insertion_point->begin(), collection, collection.begin());
                } else {
                    // Element does not belong to the existing encroaching lists,
                    // create a new list for it
                    lists.emplace_back();
                    lists.back().splice(lists.back().begin(), collection, collection.begin());
                }
            }

            ////////////////////////////////////////////////////////////
            // Merge encroaching lists

            while (lists.size() > 1) {
                if (lists.size() % 2 != 0) {
                    auto last_it = std::prev(lists.end());
                    auto last_1_it = std::prev(last_it);
                    last_1_it->merge(*last_it, make_projection_compare(comp, proj));
                    lists.pop_back();
                }

                auto first_it = lists.begin();
                auto half_it = first_it + lists.size() / 2;
                while (half_it != lists.end()) {
                    first_it->merge(*half_it, make_projection_compare(comp, proj));
                    ++first_it;
                    ++half_it;
                }

                lists.erase(lists.begin() + lists.size() / 2, lists.end());
            }

            // Merge lists back into the original collection
            collection.splice(collection.begin(), std::move(lists.front()));
        }

        template<typename Compare, typename Projection, typename... Args>
        auto flist_mel_sort(std::forward_list<Args...>& collection, Compare compare, Projection projection)
            -> void
        {
            // NOTE: see detail/melsort.h for detailed explanations
            auto&& comp = utility::as_function(compare);
            auto&& proj = utility::as_function(projection);

            if (collection.begin() == collection.end() || std::next(collection.begin()) == collection.end()) {
                return;
            }

            // A list and its last element, the latter being required
            // to implement melsort for forward iterators
            struct flist
            {
                using iterator = typename std::forward_list<Args...>::iterator;

                flist():
                    list(),
                    last(list.begin())
                {}

                std::forward_list<Args...> list;
                iterator last;<commit_msg>Work around a false positive warning with Clang<commit_after>/*
 * Copyright (c) 2021 Morwenn
 * SPDX-License-Identifier: MIT
 */
#ifndef CPPSORT_DETAIL_CONTAINER_AWARE_MEL_SORT_H_
#define CPPSORT_DETAIL_CONTAINER_AWARE_MEL_SORT_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <forward_list>
#include <functional>
#include <iterator>
#include <list>
#include <type_traits>
#include <utility>
#include <vector>
#include <cpp-sort/comparators/projection_compare.h>
#include <cpp-sort/fwd.h>
#include <cpp-sort/sorter_facade.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/utility/functional.h>
#include <cpp-sort/utility/size.h>
#include "../functional.h"
#include "../lower_bound.h"

namespace cppsort
{
    namespace detail
    {
        template<typename Compare, typename Projection, typename... Args>
        auto list_mel_sort(std::list<Args...>& collection, Compare compare, Projection projection)
            -> void
        {
            // NOTE: see detail/melsort.h for detailed explanations
            auto&& comp = utility::as_function(compare);
            auto&& proj = utility::as_function(projection);

            if (collection.size() < 2) return;

            // Encroaching lists
            std::vector<std::list<Args...>> lists;
            lists.emplace_back();
            lists.back().splice(lists.back().begin(), collection, collection.begin());

            ////////////////////////////////////////////////////////////
            // Create encroaching lists

            while (not collection.empty()) {
                auto&& value = proj(collection.front());

                auto& last_list = lists.back();
                if (not comp(value, proj(last_list.back()))) {
                    // Element belongs to the tails (bigger elements)
                    auto insertion_point = detail::lower_bound(
                        lists.begin(), std::prev(lists.end()), value, invert(compare),
                        [&proj](auto& list) -> decltype(auto) { return proj(list.back()); }
                    );
                    insertion_point->splice(insertion_point->end(), collection, collection.begin());
                } else if (not comp(proj(last_list.front()), value)) {
                    // Element belongs to the heads (smaller elements)
                    auto insertion_point = detail::lower_bound(
                        lists.begin(), std::prev(lists.end()), value, compare,
                        [&proj](auto& list) -> decltype(auto) { return proj(list.front()); }
                    );
                    insertion_point->splice(insertion_point->begin(), collection, collection.begin());
                } else {
                    // Element does not belong to the existing encroaching lists,
                    // create a new list for it
                    lists.emplace_back();
                    lists.back().splice(lists.back().begin(), collection, collection.begin());
                }
            }

            ////////////////////////////////////////////////////////////
            // Merge encroaching lists

            while (lists.size() > 1) {
                if (lists.size() % 2 != 0) {
                    auto last_it = std::prev(lists.end());
                    auto last_1_it = std::prev(last_it);
                    last_1_it->merge(*last_it, make_projection_compare(comp, proj));
                    lists.pop_back();
                }

                auto first_it = lists.begin();
                auto half_it = first_it + lists.size() / 2;
                while (half_it != lists.end()) {
                    first_it->merge(*half_it, make_projection_compare(comp, proj));
                    ++first_it;
                    ++half_it;
                }

                lists.erase(lists.begin() + lists.size() / 2, lists.end());
            }

            // Merge lists back into the original collection
            collection.splice(collection.begin(), std::move(lists.front()));
        }

        template<typename Compare, typename Projection, typename... Args>
        auto flist_mel_sort(std::forward_list<Args...>& collection, Compare compare, Projection projection)
            -> void
        {
            // NOTE: see detail/melsort.h for detailed explanations
            auto&& comp = utility::as_function(compare);
            auto&& proj = utility::as_function(projection);

            if (collection.begin() == collection.end() || std::next(collection.begin()) == collection.end()) {
                return;
            }

            // A list and its last element, the latter being required
            // to implement melsort for forward iterators
            struct flist
            {
                flist():
                    list(),
                    last(list.begin())
                {}

                std::forward_list<Args...> list;
                typename std::forward_list<Args...>::iterator last;
{'fraction_non_alphanumeric': 0.16646825396825396, 'fraction_numerical': 0.002380952380952381, 'mean_word_length': 1.5424968474148801, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 67, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3948826', 'n_tokens_mistral': 2658, 'n_tokens_neox': 2474, 'n_words': 561}