Sorting parallel arrays a.k.a. Structure of Arrays (SOA) is not that easy in UE4 since the default sort implementation can only work on one array at a time.
As far as I know, there’s no easy way to get it to work with SOAs since element swapping happens via hardcoded calls to TArray::Swap(), so what I’ve done is ripped the code out of the engine and modified it to suit my needs.
Example usage below, this sorts both scores and abc based on scores:
TArray scores = { 7, 6, 5, 4, 3, 2, 1, 0 }; TArray abc = { 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a', }; FArrayUtils::SortArray(scores, [&scores, &abc](const int32 Index1, const int32 Index2) { scores.SwapMemory(Index1, Index2); abc.SwapMemory(Index1, Index2); }); // scores: 0,1,2,3,4,5,6,7 // abc : a,b,c,d,e,f,g,h
Below is the sort function and assorted utility functions wrapped in a class.
Copy-paste and put it in a header such as MyArrayUtils.h
#pragma once class FArrayUtils { private: // HeapSiftDown() with custom swap function support template<typename ElementType, typename InAllocator, typename SwapFunctionType, typename PredicateType = TLess<>> FORCEINLINE static void HeapSiftDown(TArray<ElementType, InAllocator>& RESTRICT Array, const int iFirst, int Index, const int Count, const SwapFunctionType& RESTRICT SwapFunction, PredicateType Predicate) { const ElementType* RESTRICT data = Array.GetData() + iFirst; while (Index * 2 + 1 < Count) { const int32 LeftChildIndex = Index * 2 + 1; const int32 RightChildIndex = LeftChildIndex + 1; int32 MinChildIndex = LeftChildIndex; if (RightChildIndex < Count) MinChildIndex = Predicate(data[LeftChildIndex], data[RightChildIndex]) ? LeftChildIndex : RightChildIndex; if (!Predicate(data[MinChildIndex], data[Index])) break; SwapFunction(iFirst + Index, iFirst + MinChildIndex); Index = MinChildIndex; } } // HeapifyInternal() with custom swap function support template<typename ElementType, typename InAllocator, typename SwapFunctionType, typename PredicateType = TLess<>> FORCEINLINE static void HeapifyInternal(TArray<ElementType, InAllocator>& RESTRICT Array, const int iFirst, const int Num, const SwapFunctionType& RESTRICT SwapFunction, PredicateType Predicate) { for (int32 Index = (Num - 2) / 2; Index >= 0; Index--) HeapSiftDown(Array, iFirst, Index, Num, SwapFunction, Predicate); } // HeapSortInternal() with custom swap function support template<typename ElementType, typename InAllocator, typename SwapFunctionType, typename PredicateType = TLess<>> FORCEINLINE static void HeapSortInternal(TArray<ElementType, InAllocator>& RESTRICT Array, const int iFirst, const int Num, const SwapFunctionType& RESTRICT SwapFunction, PredicateType Predicate) { TReversePredicate<PredicateType> ReversePredicateWrapper(Predicate); // Reverse the predicate to build a max-heap instead of a min-heap HeapifyInternal(Array, iFirst, Num, SwapFunction, ReversePredicateWrapper); for (int32 Index = Num - 1; Index > 0; Index--) { SwapFunction(iFirst, iFirst + Index); HeapSiftDown(Array, iFirst, 0, Index, SwapFunction, ReversePredicateWrapper); } } public: // IntroSortInternal() with custom swap function support template<typename ElementType, typename InAllocator, typename SwapFunctionType, typename PredicateType = TLess<>> FORCEINLINE static void SortArray(TArray<ElementType, InAllocator>& RESTRICT Array, const int iFirst, const int Num, const SwapFunctionType& RESTRICT SwapFunction, PredicateType Predicate = TLess<>()) { struct FStack { int iMin; int iMax; uint32 MaxDepth; }; if (Num < 2) return; FStack RecursionStack[32] = { {iFirst, iFirst + Num - 1, (uint32)(FMath::Loge(Num) * 2.f)} }, Current, Inner; for (FStack* StackTop = RecursionStack; StackTop >= RecursionStack; --StackTop) //-V625 { Current = *StackTop; Loop: int Count = Current.iMax - Current.iMin + 1; if (Current.MaxDepth == 0) { // We're too deep into quick sort, switch to heap sort HeapSortInternal(Array, Current.iMin, Count, SwapFunction, Predicate); continue; } if (Count <= 8) { // Use simple bubble-sort. while (Current.iMax > Current.iMin) { int Max, Item; for (Max = Current.iMin, Item = Current.iMin + 1; Item <= Current.iMax; Item++) if (Predicate(Array[Max], Array[Item])) Max = Item; SwapFunction(Max, Current.iMax--); } } else { // Grab middle element so sort doesn't exhibit worst-case behavior with presorted lists. SwapFunction(Current.iMin + (Count / 2), Current.iMin); // Divide list into two halves, one with items <=Current.Min, the other with items >Current.Max. Inner.iMin = Current.iMin; Inner.iMax = Current.iMax + 1; for (; ; ) { while (++Inner.iMin <= Current.iMax && !Predicate(Array[Current.iMin], Array[Inner.iMin])); while (--Inner.iMax > Current.iMin && !Predicate(Array[Inner.iMax], Array[Current.iMin])); if (Inner.iMin > Inner.iMax) break; SwapFunction(Inner.iMin, Inner.iMax); } SwapFunction(Current.iMin, Inner.iMax); --Current.MaxDepth; // Save big half and recurse with small half. if (Inner.iMax - 1 - Current.iMin >= Current.iMax - Inner.iMin) { if (Current.iMin + 1 < Inner.iMax) { StackTop->iMin = Current.iMin; StackTop->iMax = Inner.iMax - 1; StackTop->MaxDepth = Current.MaxDepth; StackTop++; } if (Current.iMax > Inner.iMin) { Current.iMin = Inner.iMin; goto Loop; } } else { if (Current.iMax > Inner.iMin) { StackTop->iMin = Inner.iMin; StackTop->iMax = Current.iMax; StackTop->MaxDepth = Current.MaxDepth; StackTop++; } if (Current.iMin + 1 < Inner.iMax) { Current.iMax = Inner.iMax - 1; goto Loop; } } } } } // IntroSortInternal() with custom swap function support template<typename ElementType, typename InAllocator, typename SwapFunctionType, typename PredicateType = TLess<>> FORCEINLINE static void SortArray(TArray<ElementType, InAllocator>& RESTRICT Array, const SwapFunctionType& RESTRICT SwapFunction, PredicateType Predicate = TLess<>()) { SortArray(Array, 0, Array.Num(), SwapFunction, Predicate); } };
Comments
No Comments