< Summary

Class:Itinero.IO.Osm.Collections.QuickSort
Assembly:Itinero.IO.Osm
File(s):/home/runner/work/routing2/routing2/src/Itinero.IO.Osm/Collections/QuickSort.cs
Covered lines:0
Uncovered lines:126
Coverable lines:126
Total lines:194
Line coverage:0% (0 of 126)
Covered branches:0
Total branches:42
Branch coverage:0% (0 of 42)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
Sort(...)100%10%
Sort(...)0%80%
IsSorted(...)0%40%
.ctor(...)100%10%
get_Left()100%10%
get_Right()100%10%
Partition(...)0%200%
ThreewayPartition(...)100%10%
ThreewayPartition(...)0%100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero.IO.Osm/Collections/QuickSort.cs

#LineLine coverage
 1using System;
 2
 3namespace Itinero.IO.Osm.Collections;
 4
 5internal static class QuickSort
 6{
 7    public static void Sort(Func<long, long> value, Action<long, long> swap, long left, long right)
 08    {
 09        Sort((i1, i2) => value(i1).CompareTo(value(i2)), swap, left, right);
 010    }
 11
 12    public static void Sort(Func<long, long, int> compare, Action<long, long> swap, long left, long right)
 013    {
 014        if (left >= right)
 015        {
 016            return;
 17        }
 18
 019        var stack = new System.Collections.Generic.Stack<Pair>();
 020        stack.Push(new Pair(left, right));
 021        while (stack.Count > 0)
 022        {
 023            var pair = stack.Pop();
 024            var pivot = Partition(compare, swap, pair.Left, pair.Right);
 025            if (pair.Left < pivot)
 026            {
 027                stack.Push(new Pair(pair.Left, pivot - 1));
 028            }
 29
 030            if (pivot < pair.Right)
 031            {
 032                stack.Push(new Pair(pivot + 1, pair.Right));
 033            }
 034        }
 035    }
 36
 37    public static bool IsSorted(Func<long, long> value, long left, long right)
 038    {
 039        var previous = value(left);
 040        for (var i = left + 1; i <= right; i++)
 041        {
 042            var val = value(i);
 043            if (previous > val)
 044            {
 045                return false;
 46            }
 47
 048            previous = val;
 049        }
 50
 051        return true;
 052    }
 53
 54    private struct Pair
 55    {
 56        public Pair(long left, long right)
 057            : this()
 058        {
 059            this.Left = left;
 060            this.Right = right;
 061        }
 62
 063        public long Left { get; set; }
 064        public long Right { get; set; }
 65    }
 66
 67    private static long Partition(Func<long, long, int> compare, Action<long, long> swap, long left, long right)
 068    {
 69        // get the pivot value.
 070        if (left > right)
 071        {
 072            throw new ArgumentException("left should be smaller than or equal to right.");
 73        }
 74
 075        if (left == right)
 076        {
 77            // sorting just one item results in that item being sorted already and a pivot equal to that item itself.
 078            return right;
 79        }
 80
 81        // select the middle one as the pivot value.
 082        var pivot = (left + right) / (long)2;
 083        if (pivot != left)
 084        { // switch.
 085            swap(pivot, left);
 086        }
 87
 88        // start with the left as pivot value.
 089        pivot = left;
 90        //var pivotValue = value(pivot);
 91
 092        while (true)
 093        {
 94            // move the left to the right until the first value bigger than pivot.
 95            // var leftValue = value(left + 1);
 096            var leftComparison = compare(left + 1, pivot);
 097            while (leftComparison <= 0)
 098            {
 099                left++;
 0100                if (left == right)
 0101                {
 0102                    break;
 103                }
 104
 0105                leftComparison = compare(left + 1, pivot);
 0106            }
 107
 108            // move the right to left until the first value smaller than pivot.
 0109            if (left != right)
 0110            {
 111                // var rightValue = value(right);
 0112                var rightComparison = compare(right, pivot);
 0113                while (rightComparison > 0)
 0114                {
 0115                    right--;
 0116                    if (left == right)
 0117                    {
 0118                        break;
 119                    }
 120
 0121                    rightComparison = compare(right, pivot);
 0122                }
 0123            }
 124
 0125            if (left == right)
 0126            { // we are done searching, left == right.
 0127                if (pivot != left)
 0128                { // make sure the pivot value is where it is supposed to be.
 0129                    swap(pivot, left);
 0130                }
 131
 0132                return left;
 133            }
 134
 135            // switch left<->right.
 0136            swap(left + 1, right);
 0137        }
 0138    }
 139
 140    public static void ThreewayPartition(Func<long, long> value, Action<long, long> swap, long left, long right,
 141        out long highestLowest, out long lowestHighest)
 0142    {
 0143        ThreewayPartition(value, swap, left, right, left, out highestLowest,
 0144            out lowestHighest); // default, the left a pivot.
 0145    }
 146
 147    public static void ThreewayPartition(Func<long, long> value, Action<long, long> swap, long left, long right,
 148        long pivot,
 149        out long highestLowest, out long lowestHighest)
 0150    {
 0151        if (left > right)
 0152        {
 0153            throw new ArgumentException("left should be smaller than or equal to right.");
 154        }
 155
 0156        if (left == right)
 0157        {
 158            // sorting just one item results in that item being sorted already and a pivot equal to that item itself.
 0159            highestLowest = right;
 0160            lowestHighest = right;
 0161            return;
 162        }
 163
 164        // get pivot value.
 0165        var pivotValue = value(pivot);
 166
 0167        var i = left;
 0168        var j = left;
 0169        var n = right;
 170
 0171        while (j <= n)
 0172        {
 0173            var valueJ = value(j);
 0174            if (valueJ < pivotValue)
 0175            {
 0176                swap(i, j);
 0177                i++;
 0178                j++;
 0179            }
 0180            else if (valueJ > pivotValue)
 0181            {
 0182                swap(j, n);
 0183                n--;
 0184            }
 185            else
 0186            {
 0187                j++;
 0188            }
 0189        }
 190
 0191        highestLowest = i - 1;
 0192        lowestHighest = n + 1;
 0193    }
 194}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

Sort(...)
Sort(...)
IsSorted(...)
.ctor(...)
get_Left()
get_Right()
Partition(...)
ThreewayPartition(...)
ThreewayPartition(...)