Partition.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "HAL/Platform.h"
 
namespace Algo
{
    template<class T, typename IndexType, typename UnaryPredicate>
    IndexType Partition(T* Elements, const IndexType Num, UnaryPredicate Predicate)
    {
        T* First = Elements;
        T* Last = Elements + Num;
        
        while (First != Last) 
        {
            while (Predicate(*First)) 
            {
                ++First;
                if (First == Last) 
                {   
                    return (IndexType)(First - Elements);
                }
            }
        
            do 
            {
                --Last;
                if (First == Last)
                {
                    return (IndexType)(First - Elements);
                }
            } while (!Predicate(*Last));
        
            Exchange(*First, *Last);
            ++First;
        }
    
        return (IndexType)(First - Elements);
    }
 
    template <typename RangeType, typename UnaryPredicateType>
    UE_REWRITE auto Partition(RangeType&& Range, UnaryPredicateType Predicate) -> decltype(GetNum(Range))
    {
        return Partition(GetData(Range), GetNum(Range), MoveTemp(Predicate));
    }
} //namespace Algo