StableSort.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Algo/BinarySearch.h"
#include "Algo/Rotate.h"
#include "Templates/IdentityFunctor.h"
#include "Templates/Invoke.h"
#include "Templates/Less.h"
#include "Templates/UnrealTemplate.h" // For GetData, GetNum, Swap
 
 
namespace AlgoImpl
{
    template <typename T, typename ProjectionType, typename PredicateType>
    void Merge(T* First, int32 Mid, int32 Num, ProjectionType Projection, PredicateType Predicate)
    {
        int32 AStart = 0;
        int32 BStart = Mid;
 
        while (AStart < BStart && BStart < Num)
        {
            int32 NewAOffset = AlgoImpl::UpperBoundInternal(First + AStart, BStart - AStart, Invoke(Projection, First[BStart]), Projection, Predicate);
            AStart += NewAOffset;
 
            if (AStart >= BStart)
            {
                return;
            }
 
            int32 NewBOffset = AlgoImpl::LowerBoundInternal(First + BStart, Num - BStart, Invoke(Projection, First[AStart]), Projection, Predicate);
            AlgoImpl::RotateInternal(First + AStart, NewBOffset + BStart - AStart, BStart - AStart);
            BStart += NewBOffset;
            AStart += NewBOffset + 1;
        }
    }
 
    inline constexpr int32 MinMergeSubgroupSize = 2;
 
    template <typename T, typename ProjectionType, typename PredicateType>
    void StableSortInternal(T* First, int32 Num, ProjectionType Projection, PredicateType Predicate)
    {
        int32 SubgroupStart = 0;
 
        if constexpr (MinMergeSubgroupSize > 1)
        {
            if constexpr (MinMergeSubgroupSize > 2)
            {
                // First pass with simple bubble-sort.
                do
                {
                    int32 GroupEnd = SubgroupStart + MinMergeSubgroupSize;
                    if (Num < GroupEnd)
                    {
                        GroupEnd = Num;
                    }
                    do
                    {
                        for (int32 It = SubgroupStart; It < GroupEnd - 1; ++It)
                        {
                            if (Invoke(Predicate, Invoke(Projection, First[It + 1]), Invoke(Projection, First[It])))
                            {
                                Swap(First[It], First[It + 1]);
                            }
                        }
                        GroupEnd--;
                    }
                    while (GroupEnd - SubgroupStart > 1);
 
                    SubgroupStart += MinMergeSubgroupSize;
                }
                while (SubgroupStart < Num);
            }
            else
            {
                for (int32 Subgroup = 0; Subgroup < Num; Subgroup += 2)
                {
                    if (Subgroup + 1 < Num && Invoke(Predicate, Invoke(Projection, First[Subgroup + 1]), Invoke(Projection, First[Subgroup])))
                    {
                        Swap(First[Subgroup], First[Subgroup + 1]);
                    }
                }
            }
        }
 
        int32 SubgroupSize = MinMergeSubgroupSize;
        while (SubgroupSize < Num)
        {
            SubgroupStart = 0;
            do
            {
                int32 MergeNum = SubgroupSize << 1;
                if (Num - SubgroupStart < MergeNum)
                {
                    MergeNum = Num - SubgroupStart;
                }
 
                Merge(First + SubgroupStart, SubgroupSize, MergeNum, Projection, Predicate);
                SubgroupStart += SubgroupSize << 1;
            }
            while (SubgroupStart < Num);
 
            SubgroupSize <<= 1;
        }
    }
}
 
namespace Algo
{
    template <typename RangeType>
    UE_REWRITE void StableSort(RangeType&& Range)
    {
        AlgoImpl::StableSortInternal(GetData(Range), GetNum(Range), FIdentityFunctor(), TLess<>());
    }
 
    template <typename RangeType, typename PredicateType>
    UE_REWRITE void StableSort(RangeType&& Range, PredicateType Pred)
    {
        AlgoImpl::StableSortInternal(GetData(Range), GetNum(Range), FIdentityFunctor(), MoveTemp(Pred));
    }
 
    template <typename RangeType, typename ProjectionType>
    UE_REWRITE void StableSortBy(RangeType&& Range, ProjectionType Proj)
    {
        AlgoImpl::StableSortInternal(GetData(Range), GetNum(Range), MoveTemp(Proj), TLess<>());
    }
 
    template <typename RangeType, typename ProjectionType, typename PredicateType>
    UE_REWRITE void StableSortBy(RangeType&& Range, ProjectionType Proj, PredicateType Pred)
    {
        AlgoImpl::StableSortInternal(GetData(Range), GetNum(Range), MoveTemp(Proj), MoveTemp(Pred));
    }
}