algorithm.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (C) 2014 swift Project Community / Contributors
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-swift-pilot-client-1
 
 
#ifndef SWIFT_MISC_ALGORITHM_H
#define SWIFT_MISC_ALGORITHM_H
 
#include <algorithm>
#include <iterator>
#include <random>
#include <tuple>
#include <utility>
 
#include <QtGlobal>
 
namespace swift::misc
{
    template <typename I, typename J>
    auto removeIfIn(I begin1, I end1, J begin2, J end2)
    {
        auto newEnd = end1;
        std::for_each(begin2, end2, [&](const auto &rm) {
            const auto found = std::find(begin1, end1, rm);
            Q_ASSERT(found != end1);
            if (newEnd == end1) { newEnd = found; }
            else { newEnd = std::move(begin1, found, newEnd); }
            begin1 = std::next(found);
        });
        if (newEnd != end1) { newEnd = std::move(begin1, end1, newEnd); }
        return newEnd;
    }
 
    namespace private_ns
    {
        inline std::mt19937 &defaultRandomGenerator()
        {
            thread_local std::mt19937 rng(std::random_device {}());
            return rng;
        }
    } // namespace private_ns
 
    template <typename ForwardIt, typename OutputIt, typename Generator>
    void copyRandomElements(ForwardIt in, ForwardIt end, OutputIt out, int n, Generator &&rng)
    {
        for (auto size = static_cast<int>(std::distance(in, end)); in != end && n > 0; ++in, --size)
        {
            if (std::uniform_int_distribution<>(0, size - 1)(rng) < n)
            {
                *out++ = *in;
                --n;
            }
        }
    }
 
    template <typename ForwardIt, typename OutputIt>
    void copyRandomElements(ForwardIt in, ForwardIt end, OutputIt out, int n)
    {
        copyRandomElements(in, end, out, n, private_ns::defaultRandomGenerator());
    }
 
    template <typename ForwardIt, typename OutputIt, typename Generator>
    void copySampleElements(ForwardIt in, ForwardIt end, OutputIt out, int n, Generator &&rng)
    {
        const auto size = static_cast<int>(std::distance(in, end));
        for (int i = 0; i < std::min(n, size); ++i)
        {
            const auto index = std::uniform_int_distribution<>(0, std::max(size / n, 1) - 1)(rng);
            std::advance(in, index);
            *out++ = *in;
            std::advance(in, std::max(size / n, 1) - index);
        }
    }
 
    template <typename ForwardIt, typename OutputIt>
    void copySampleElements(ForwardIt in, ForwardIt end, OutputIt out, int n)
    {
        copySampleElements(in, end, out, n, private_ns::defaultRandomGenerator());
    }
 
    template <typename I, typename F>
    void topologicalSort(I begin, I end, F comparator)
    {
        using value_type = typename std::iterator_traits<I>::value_type;
        auto part = begin;
        while (part != end)
        {
            auto newPart = std::partition(part, end, [=](const value_type &a) {
                return std::none_of(part, end, [=, &a](const value_type &b) { return comparator(b, a); });
            });
            Q_ASSERT_X(newPart != part, "swift::misc::topologicalSort",
                       "Cyclic less-than relation detected (not a partial ordering)");
            part = newPart;
        }
    }
 
    template <typename C, typename T, typename F>
    void topologicallySortedInsert(C &container, T &&value, F comparator)
    {
        using value_type = typename C::value_type;
        using reverse = std::reverse_iterator<typename C::iterator>;
        auto rit = std::find_if(reverse(container.end()), reverse(container.begin()),
                                [=, &value](const value_type &lhs) { return comparator(lhs, value); });
        Q_ASSERT_X(std::none_of(rit, reverse(container.begin()),
                                [=, &value](const value_type &rhs) { return comparator(value, rhs); }),
                   "swift::misc::topologicallySortedInsert",
                   "Cyclic less-than relation detected (not a partial ordering)");
        container.insert(rit.base(), std::forward<T>(value));
    }
 
    namespace private_ns
    {
        template <typename T, typename F, size_t... Is>
        void tupleForEachPairImpl(T &&tuple, F &&visitor, std::index_sequence<Is...>)
        {
            // cppcheck-suppress accessForwarded
            (static_cast<void>(std::forward<F>(visitor)(std::get<Is * 2>(std::forward<T>(tuple)),
                                                        std::get<Is * 2 + 1>(std::forward<T>(tuple)))),
             ...);
        }
    } // namespace private_ns
 
    template <typename T, typename F>
    void tupleForEachPair(T &&tuple, F &&visitor)
    {
        using seq = std::make_index_sequence<std::tuple_size_v<std::decay_t<T>> / 2>;
        return private_ns::tupleForEachPairImpl(std::forward<T>(tuple), std::forward<F>(visitor), seq());
    }
} // namespace swift::misc
 
#endif // SWIFT_MISC_ALGORITHM_H