Permute.h

Go to the documentation of this file.

 
#ifndef PBAT_COMMON_PERMUTE_H
#define PBAT_COMMON_PERMUTE_H
 
#include <concepts>
#include <iterator>
 
namespace pbat::common {

template <
    std::random_access_iterator TValuesBegin,
    std::random_access_iterator TValuesEnd,
    std::random_access_iterator TPermutationBegin>
void Permute(TValuesBegin vb, TValuesEnd ve, TPermutationBegin pb)
{
    using PermutationIndex = std::iterator_traits<TPermutationBegin>::value_type;
    static_assert(
        std::is_integral_v<PermutationIndex> and std::is_signed_v<PermutationIndex>,
        "Permutation index must be signed integer");
    auto n            = std::distance(vb, ve);
    using PtrDiffType = decltype(n);
    for (PtrDiffType i = 0; i < n; ++i)
    {
        auto pi = *(pb + i);
        if (pi < 0)
            continue;
        auto value = *(vb + i);
        auto xi    = i;
        while (pi != i)
        {
            *(pb + xi) -= n;
            *(vb + xi) = *(vb + pi);
            xi         = pi;
            pi         = *(pb + xi);
        }
        *(vb + xi) = value;
        *(pb + xi) -= n;
    }
    for (PtrDiffType i = 0; i < n; ++i)
    {
        *(pb + i) += n;
    }
}
 
} // namespace pbat::common
 
#endif // PBAT_COMMON_PERMUTE_H