< Summary

Information
Class: SwiftCollections.SwiftIntAscendingComparer
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Utility/SwiftArraySortHelper.cs
Line coverage
100%
Covered lines: 1
Uncovered lines: 0
Coverable lines: 1
Total lines: 325
Line coverage: 100%
Branch coverage
N/A
Covered branches: 0
Total branches: 0
Branch coverage: N/A
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
Compare(...)100%11100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Utility/SwiftArraySortHelper.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftArraySortHelper.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Collections.Generic;
 10using System.Runtime.CompilerServices;
 11
 12namespace SwiftCollections;
 13
 14internal static class SwiftArraySortHelper
 15{
 16    private const int InsertionSortThreshold = 16;
 17
 18    public static void Sort<T>(T[] array, int index, int length, IComparer<T>? comparer)
 19    {
 20        if (length <= 1)
 21            return;
 22
 23        if (comparer == null || ReferenceEquals(comparer, Comparer<T>.Default))
 24        {
 25            Array.Sort(array, index, length);
 26            return;
 27        }
 28
 29        IntroSort(array, index, index + length - 1, FloorLog2(length) * 2, comparer);
 30    }
 31
 32    public static void Sort<T, TComparer>(T[] array, int index, int length, TComparer comparer)
 33        where TComparer : struct, IComparer<T>
 34    {
 35        if (length <= 1)
 36            return;
 37
 38        // Keep the struct-comparer path generic: it avoids boxing and lets the JIT devirtualize hot comparer calls.
 39        IntroSort(array, index, index + length - 1, FloorLog2(length) * 2, comparer);
 40    }
 41
 42    private static void IntroSort<T>(T[] array, int lo, int hi, int depthLimit, IComparer<T> comparer)
 43    {
 44        while (hi > lo)
 45        {
 46            int partitionSize = hi - lo + 1;
 47            if (partitionSize <= InsertionSortThreshold)
 48            {
 49                InsertionSort(array, lo, hi, comparer);
 50                return;
 51            }
 52
 53            if (depthLimit == 0)
 54            {
 55                HeapSort(array, lo, hi, comparer);
 56                return;
 57            }
 58
 59            depthLimit--;
 60            int partition = PickPivotAndPartition(array, lo, hi, comparer);
 61
 62            if (partition - lo < hi - partition)
 63            {
 64                IntroSort(array, lo, partition - 1, depthLimit, comparer);
 65                lo = partition + 1;
 66            }
 67            else
 68            {
 69                IntroSort(array, partition + 1, hi, depthLimit, comparer);
 70                hi = partition - 1;
 71            }
 72        }
 73    }
 74
 75    private static int PickPivotAndPartition<T>(T[] array, int lo, int hi, IComparer<T> comparer)
 76    {
 77        int middle = lo + ((hi - lo) >> 1);
 78
 79        SwapIfGreater(array, comparer, lo, middle);
 80        SwapIfGreater(array, comparer, lo, hi);
 81        SwapIfGreater(array, comparer, middle, hi);
 82
 83        T pivot = array[middle];
 84        Swap(array, middle, hi - 1);
 85
 86        int left = lo;
 87        int right = hi - 1;
 88
 89        while (true)
 90        {
 91            while (comparer.Compare(array[++left], pivot) < 0)
 92            {
 93            }
 94
 95            while (comparer.Compare(pivot, array[--right]) < 0)
 96            {
 97            }
 98
 99            if (left >= right)
 100                break;
 101
 102            Swap(array, left, right);
 103        }
 104
 105        Swap(array, left, hi - 1);
 106        return left;
 107    }
 108
 109    private static void HeapSort<T>(T[] array, int lo, int hi, IComparer<T> comparer)
 110    {
 111        int count = hi - lo + 1;
 112        for (int i = count >> 1; i >= 1; i--)
 113            DownHeap(array, i, count, lo, comparer);
 114
 115        for (int i = count; i > 1; i--)
 116        {
 117            Swap(array, lo, lo + i - 1);
 118            DownHeap(array, 1, i - 1, lo, comparer);
 119        }
 120    }
 121
 122    private static void DownHeap<T>(T[] array, int index, int count, int lo, IComparer<T> comparer)
 123    {
 124        T value = array[lo + index - 1];
 125
 126        while (index <= (count >> 1))
 127        {
 128            int child = index << 1;
 129            if (child < count && comparer.Compare(array[lo + child - 1], array[lo + child]) < 0)
 130                child++;
 131
 132            if (comparer.Compare(value, array[lo + child - 1]) >= 0)
 133                break;
 134
 135            array[lo + index - 1] = array[lo + child - 1];
 136            index = child;
 137        }
 138
 139        array[lo + index - 1] = value;
 140    }
 141
 142    private static void InsertionSort<T>(T[] array, int lo, int hi, IComparer<T> comparer)
 143    {
 144        for (int i = lo + 1; i <= hi; i++)
 145        {
 146            T value = array[i];
 147            int j = i - 1;
 148            while (j >= lo && comparer.Compare(value, array[j]) < 0)
 149            {
 150                array[j + 1] = array[j];
 151                j--;
 152            }
 153
 154            array[j + 1] = value;
 155        }
 156    }
 157
 158    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 159    private static void SwapIfGreater<T>(T[] array, IComparer<T> comparer, int left, int right)
 160    {
 161        if (left != right && comparer.Compare(array[left], array[right]) > 0)
 162            Swap(array, left, right);
 163    }
 164
 165    private static void IntroSort<T, TComparer>(T[] array, int lo, int hi, int depthLimit, TComparer comparer)
 166        where TComparer : struct, IComparer<T>
 167    {
 168        while (hi > lo)
 169        {
 170            int partitionSize = hi - lo + 1;
 171            if (partitionSize <= InsertionSortThreshold)
 172            {
 173                InsertionSort(array, lo, hi, comparer);
 174                return;
 175            }
 176
 177            if (depthLimit == 0)
 178            {
 179                HeapSort(array, lo, hi, comparer);
 180                return;
 181            }
 182
 183            depthLimit--;
 184            int partition = PickPivotAndPartition(array, lo, hi, comparer);
 185
 186            if (partition - lo < hi - partition)
 187            {
 188                IntroSort(array, lo, partition - 1, depthLimit, comparer);
 189                lo = partition + 1;
 190            }
 191            else
 192            {
 193                IntroSort(array, partition + 1, hi, depthLimit, comparer);
 194                hi = partition - 1;
 195            }
 196        }
 197    }
 198
 199    private static int PickPivotAndPartition<T, TComparer>(T[] array, int lo, int hi, TComparer comparer)
 200        where TComparer : struct, IComparer<T>
 201    {
 202        int middle = lo + ((hi - lo) >> 1);
 203
 204        SwapIfGreater(array, comparer, lo, middle);
 205        SwapIfGreater(array, comparer, lo, hi);
 206        SwapIfGreater(array, comparer, middle, hi);
 207
 208        T pivot = array[middle];
 209        Swap(array, middle, hi - 1);
 210
 211        int left = lo;
 212        int right = hi - 1;
 213
 214        while (true)
 215        {
 216            while (comparer.Compare(array[++left], pivot) < 0)
 217            {
 218            }
 219
 220            while (comparer.Compare(pivot, array[--right]) < 0)
 221            {
 222            }
 223
 224            if (left >= right)
 225                break;
 226
 227            Swap(array, left, right);
 228        }
 229
 230        Swap(array, left, hi - 1);
 231        return left;
 232    }
 233
 234    private static void HeapSort<T, TComparer>(T[] array, int lo, int hi, TComparer comparer)
 235        where TComparer : struct, IComparer<T>
 236    {
 237        int count = hi - lo + 1;
 238        for (int i = count >> 1; i >= 1; i--)
 239            DownHeap(array, i, count, lo, comparer);
 240
 241        for (int i = count; i > 1; i--)
 242        {
 243            Swap(array, lo, lo + i - 1);
 244            DownHeap(array, 1, i - 1, lo, comparer);
 245        }
 246    }
 247
 248    private static void DownHeap<T, TComparer>(T[] array, int index, int count, int lo, TComparer comparer)
 249        where TComparer : struct, IComparer<T>
 250    {
 251        T value = array[lo + index - 1];
 252
 253        while (index <= (count >> 1))
 254        {
 255            int child = index << 1;
 256            if (child < count && comparer.Compare(array[lo + child - 1], array[lo + child]) < 0)
 257                child++;
 258
 259            if (comparer.Compare(value, array[lo + child - 1]) >= 0)
 260                break;
 261
 262            array[lo + index - 1] = array[lo + child - 1];
 263            index = child;
 264        }
 265
 266        array[lo + index - 1] = value;
 267    }
 268
 269    private static void InsertionSort<T, TComparer>(T[] array, int lo, int hi, TComparer comparer)
 270        where TComparer : struct, IComparer<T>
 271    {
 272        for (int i = lo + 1; i <= hi; i++)
 273        {
 274            T value = array[i];
 275            int j = i - 1;
 276            while (j >= lo && comparer.Compare(value, array[j]) < 0)
 277            {
 278                array[j + 1] = array[j];
 279                j--;
 280            }
 281
 282            array[j + 1] = value;
 283        }
 284    }
 285
 286    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 287    private static void SwapIfGreater<T, TComparer>(T[] array, TComparer comparer, int left, int right)
 288        where TComparer : struct, IComparer<T>
 289    {
 290        if (left != right && comparer.Compare(array[left], array[right]) > 0)
 291            Swap(array, left, right);
 292    }
 293
 294    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 295    private static void Swap<T>(T[] array, int left, int right)
 296    {
 297        if (left == right)
 298            return;
 299
 300        T value = array[left];
 301        array[left] = array[right];
 302        array[right] = value;
 303    }
 304
 305    private static int FloorLog2(int value)
 306    {
 307        int result = 0;
 308        while (value >= 2)
 309        {
 310            result++;
 311            value >>= 1;
 312        }
 313
 314        return result;
 315    }
 316}
 317
 318internal readonly struct SwiftIntAscendingComparer : IComparer<int>
 319{
 320    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 321    public int Compare(int x, int y)
 322    {
 36323        return x.CompareTo(y);
 324    }
 325}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
GitHub | reportgenerator.io

Methods/Properties

Compare(System.Int32,System.Int32)