Algorithm.h

Go to the documentation of this file.

//
//      ██╗██████╗     ██╗     ██╗██████╗ ███████╗
//      ██║██╔══██╗    ██║     ██║██╔══██╗██╔════╝      ** JPLSpatial **
//      ██║██████╔╝    ██║     ██║██████╔╝███████╗
// ██   ██║██╔═══╝     ██║     ██║██╔══██╗╚════██║      https://github.com/Jaytheway/JPLSpatial
// ╚█████╔╝██║         ███████╗██║██████╔╝███████║
//  ╚════╝ ╚═╝         ╚══════╝╚═╝╚═════╝ ╚══════╝
//
//   Copyright 2024 Jaroslav Pevno, JPLSpatial is offered under the terms of the ISC license:
//
//   Permission to use, copy, modify, and/or distribute this software for any purpose with or
//   without fee is hereby granted, provided that the above copyright notice and this permission
//   notice appear in all copies. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
//   WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
//   AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
//   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
//   WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
//   CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 
#pragma once
 
#include "JPLSpatial/Core.h"
#include "JPLSpatial/Math/Math.h"
 
#include <iterator>
#include <type_traits>
#include <utility>
#include <functional>
#include <numeric>
#include <algorithm>
#include <ranges>
#include <random>
 
namespace JPL::Algo
{
    namespace Internal
    {
        template<class ContainerType>
        using ElementTypeOf = std::remove_cvref_t<decltype(*std::declval<ContainerType>().begin())>;
    }
 
    //==========================================================================
    template<class RangeType, class T, class Fn = std::plus<T>>
    [[nodiscard]] JPL_INLINE constexpr T Accumulate(RangeType&& range, T initialValue, Fn reduceOp = {})
    {
        return std::accumulate(range.begin(), range.end(), std::move(initialValue), reduceOp);
    }
 
    //==========================================================================
    template <class T = void>
    struct AccPow2
    {
        [[nodiscard]] JPL_INLINE constexpr T operator()(const T& acc, const T& value) const noexcept
        {
            return acc + value * value;
        }
    };
 
    template <class T = void>
    struct AccAbs
    {
        [[nodiscard]] JPL_INLINE constexpr T operator()(const T& acc, const T& value) const noexcept
        {
            return acc + Math::Abs(value);
        }
    };
 
    template <class T = void>
    class Multiply
    {
        T mMultiplier;
    public:
        explicit Multiply(T multiplier) : mMultiplier(multiplier) {}
        
        JPL_INLINE constexpr void operator()(T& value) const noexcept
        {
            value *= mMultiplier;
        }
    };
 
    //==========================================================================
    template<class ContainerType>
    JPL_INLINE constexpr void NormalizeL1(ContainerType&& data)
    {
        using ElementType = Internal::ElementTypeOf<ContainerType>;
        const ElementType sum = Accumulate(std::forward<ContainerType>(data), ElementType(0), AccAbs<ElementType>{});
        const float invSum = 1.0f / static_cast<float>(sum);
        std::ranges::for_each(std::forward<ContainerType>(data), Multiply(invSum));
    }
 
    template<class ContainerType>
    JPL_INLINE constexpr void NormalizeL2(ContainerType&& data)
    {
        using ElementType = Internal::ElementTypeOf<ContainerType>;
        const ElementType sum2 = Accumulate(std::forward<ContainerType>(data), ElementType(0), AccPow2<ElementType>{});
        const float invLength = Math::InvSqrt(static_cast<float>(sum2));
        std::ranges::for_each(std::forward<ContainerType>(data), Multiply(invLength));
    }
 
    template<class ContainerType>
    [[nodiscard]] JPL_INLINE constexpr bool IsNormalizedL1(const ContainerType& data, float tolerance = JPL_FLOAT_EPS)
    {
        using ElementType = Internal::ElementTypeOf<ContainerType>;
        ElementType sum = Accumulate(data, ElementType(0), AccAbs<ElementType>{});
        return Math::IsNearlyEqual(static_cast<float>(sum), 1.0f, tolerance);
    }
 
    template<class ContainerType>
    [[nodiscard]] JPL_INLINE constexpr bool IsNormalizedL2(const ContainerType& data, float tolerance = JPL_FLOAT_EPS)
    {
        using ElementType = Internal::ElementTypeOf<ContainerType>;
        const ElementType sum2 = Accumulate(data, ElementType(0), AccPow2<ElementType>{});
        return Math::IsNearlyEqual(static_cast<float>(sum2), 1.0f, tolerance);
    }
 
    template<std::random_access_iterator I, std::sentinel_for<I> S, class Gen> requires std::permutable<I> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
    constexpr I PartialShuffle(I first, S last, std::size_t count, Gen&& gen)
    {
        using diff_t = std::iter_difference_t<I>;
        using distr_t = std::uniform_int_distribution<diff_t>;
        using param_t = typename distr_t::param_type;
        
        const diff_t n = std::ranges::distance(first, last);
        const diff_t k = std::min<diff_t>(count, n);
        distr_t dist;
 
        for (diff_t i = 0; i < k; ++i)
        {
            const diff_t j = dist(gen, param_t(i, n - 1));
            std::ranges::iter_swap(first + i, first + j);
        }
 
        return first + k;
    }
 
    template<std::ranges::random_access_range R, class Gen> requires std::permutable<std::ranges::iterator_t<R>> and std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
    JPL_INLINE constexpr std::ranges::borrowed_iterator_t<R> PartialShuffle(R&& r, std::size_t count, Gen&& gen)
    {
        return PartialShuffle(std::ranges::begin(r), std::ranges::end(r), count, std::forward<Gen>(gen));
    }
} // namespace JPL::Algo