From 8e20d2e931b273b54ef369c9b75021ab04118e04 Mon Sep 17 00:00:00 2001 From: Vasily Date: Thu, 27 Feb 2020 14:51:34 +0300 Subject: Simplify AlphanumericComparer, reduce code duplication --- .../Sorting/AlphanumComparator.cs | 97 ++++++++++++++++++++++ 1 file changed, 97 insertions(+) create mode 100644 MediaBrowser.Controller/Sorting/AlphanumComparator.cs (limited to 'MediaBrowser.Controller/Sorting/AlphanumComparator.cs') diff --git a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs new file mode 100644 index 000000000..ad1eaf7bf --- /dev/null +++ b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs @@ -0,0 +1,97 @@ +using System.Collections.Generic; +using System.Text; +using MediaBrowser.Controller.Sorting; + +namespace MediaBrowser.Controller.Sorting +{ + public class AlphanumComparator : IComparer + { + public static int CompareValues(string s1, string s2) + { + if (s1 == null || s2 == null) + { + return 0; + } + + int thisMarker = 0, thisNumericChunk = 0; + int thatMarker = 0, thatNumericChunk = 0; + + while ((thisMarker < s1.Length) || (thatMarker < s2.Length)) + { + if (thisMarker >= s1.Length) + { + return -1; + } + else if (thatMarker >= s2.Length) + { + return 1; + } + char thisCh = s1[thisMarker]; + char thatCh = s2[thatMarker]; + + var thisChunk = new StringBuilder(); + var thatChunk = new StringBuilder(); + bool thisNumeric = char.IsDigit(thisCh), thatNumeric = char.IsDigit(thatCh); + + while ((thisMarker < s1.Length) && (char.IsDigit(thisCh) == thisNumeric)) + { + thisChunk.Append(thisCh); + thisMarker++; + + if (thisMarker < s1.Length) + { + thisCh = s1[thisMarker]; + } + } + + while ((thatMarker < s2.Length) && (char.IsDigit(thatCh) == thatNumeric)) + { + thatChunk.Append(thatCh); + thatMarker++; + + if (thatMarker < s2.Length) + { + thatCh = s2[thatMarker]; + } + } + + + // If both chunks contain numeric characters, sort them numerically + if (thisNumeric && thatNumeric) + { + if (!int.TryParse(thisChunk.ToString(), out thisNumericChunk) + || !int.TryParse(thatChunk.ToString(), out thatNumericChunk)) + { + return 0; + } + + if (thisNumericChunk < thatNumericChunk) + { + return -1; + } + + if (thisNumericChunk > thatNumericChunk) + { + return 1; + } + } + else + { + int result = thisChunk.ToString().CompareTo(thatChunk.ToString()); + if (result != 0) + { + return result; + } + } + + } + + return 0; + } + + public int Compare(string x, string y) + { + return CompareValues(x, y); + } + } +} -- cgit v1.2.3 From d1670f81808a74865f8c4fb2c2a77ab01eb3bde9 Mon Sep 17 00:00:00 2001 From: Vasily Date: Thu, 27 Feb 2020 16:02:18 +0300 Subject: Apply suggestions from code review Co-Authored-By: Claus Vium --- MediaBrowser.Controller/Entities/BaseItem.cs | 2 +- MediaBrowser.Controller/Sorting/AlphanumComparator.cs | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'MediaBrowser.Controller/Sorting/AlphanumComparator.cs') diff --git a/MediaBrowser.Controller/Entities/BaseItem.cs b/MediaBrowser.Controller/Entities/BaseItem.cs index 09cdfc9ea..66de080a3 100644 --- a/MediaBrowser.Controller/Entities/BaseItem.cs +++ b/MediaBrowser.Controller/Entities/BaseItem.cs @@ -392,7 +392,7 @@ namespace MediaBrowser.Controller.Entities var thisChunk = new StringBuilder(); bool isNumeric = char.IsDigit(thisCh); - while ((thisMarker < s1.Length) && (char.IsDigit(thisCh) == isNumeric)) + while (thisMarker < s1.Length && char.IsDigit(thisCh) == isNumeric) { thisChunk.Append(thisCh); thisMarker++; diff --git a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs index ad1eaf7bf..65dc120ca 100644 --- a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs +++ b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs @@ -33,7 +33,7 @@ namespace MediaBrowser.Controller.Sorting var thatChunk = new StringBuilder(); bool thisNumeric = char.IsDigit(thisCh), thatNumeric = char.IsDigit(thatCh); - while ((thisMarker < s1.Length) && (char.IsDigit(thisCh) == thisNumeric)) + while (thisMarker < s1.Length && char.IsDigit(thisCh) == thisNumeric) { thisChunk.Append(thisCh); thisMarker++; @@ -44,7 +44,7 @@ namespace MediaBrowser.Controller.Sorting } } - while ((thatMarker < s2.Length) && (char.IsDigit(thatCh) == thatNumeric)) + while (thatMarker < s2.Length && char.IsDigit(thatCh) == thatNumeric) { thatChunk.Append(thatCh); thatMarker++; -- cgit v1.2.3 From be1d4b32c6643af69c27c746578b1994a4a650ff Mon Sep 17 00:00:00 2001 From: Bond_009 Date: Thu, 5 Mar 2020 00:57:24 +0100 Subject: Add speed for alpha numeric sorting --- .../Sorting/AlphanumComparator.cs | 130 +++++++++++++-------- 1 file changed, 84 insertions(+), 46 deletions(-) (limited to 'MediaBrowser.Controller/Sorting/AlphanumComparator.cs') diff --git a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs index 65dc120ca..de7f72d1c 100644 --- a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs +++ b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs @@ -1,94 +1,132 @@ +#nullable enable + +using System; using System.Collections.Generic; -using System.Text; -using MediaBrowser.Controller.Sorting; namespace MediaBrowser.Controller.Sorting { - public class AlphanumComparator : IComparer + public class AlphanumComparator : IComparer { - public static int CompareValues(string s1, string s2) + public static int CompareValues(string? s1, string? s2) { - if (s1 == null || s2 == null) + if (s1 == null && s2 == null) { return 0; } + else if (s1 == null) + { + return -1; + } + else if (s2 == null) + { + return 1; + } - int thisMarker = 0, thisNumericChunk = 0; - int thatMarker = 0, thatNumericChunk = 0; + int len1 = s1.Length; + int len2 = s2.Length; - while ((thisMarker < s1.Length) || (thatMarker < s2.Length)) + // Early return for empty strings + if (len1 == 0 && len2 == 0) { - if (thisMarker >= s1.Length) + return 0; + } + else if (len1 == 0) + { + return -1; + } + else if (len2 == 0) + { + return 1; + } + + int pos1 = 0; + int pos2 = 0; + + do + { + int start1 = pos1; + int start2 = pos2; + + bool isNum1 = char.IsDigit(s1[pos1++]); + bool isNum2 = char.IsDigit(s2[pos2++]); + + while (pos1 < len1 && char.IsDigit(s1[pos1]) == isNum1) { - return -1; + pos1++; } - else if (thatMarker >= s2.Length) + + while (pos2 < len2 && char.IsDigit(s2[pos2]) == isNum2) { - return 1; + pos2++; } - char thisCh = s1[thisMarker]; - char thatCh = s2[thatMarker]; - var thisChunk = new StringBuilder(); - var thatChunk = new StringBuilder(); - bool thisNumeric = char.IsDigit(thisCh), thatNumeric = char.IsDigit(thatCh); + var span1 = s1.AsSpan(start1, pos1 - start1); + var span2 = s2.AsSpan(start2, pos2 - start2); - while (thisMarker < s1.Length && char.IsDigit(thisCh) == thisNumeric) + if (isNum1 && isNum2) { - thisChunk.Append(thisCh); - thisMarker++; - - if (thisMarker < s1.Length) + // Trim leading zeros so we can compare the length + // of the strings to find the largest number + span1 = span1.TrimStart('0'); + span2 = span2.TrimStart('0'); + var span1Len = span1.Length; + var span2Len = span2.Length; + if (span1Len < span2Len) { - thisCh = s1[thisMarker]; + return -1; } - } - - while (thatMarker < s2.Length && char.IsDigit(thatCh) == thatNumeric) - { - thatChunk.Append(thatCh); - thatMarker++; - - if (thatMarker < s2.Length) + else if (span1Len > span2Len) { - thatCh = s2[thatMarker]; + return 1; } - } + else if (span1Len >= 20) // Number is probably too big for a ulong + { + // Trim all the first digits that are the same + int i = 0; + while (i < span1Len && span1[i] == span2[i]) + { + i++; + } + // If there are no more digits it's the same number + if (i == span1Len) + { + continue; + } - // If both chunks contain numeric characters, sort them numerically - if (thisNumeric && thatNumeric) - { - if (!int.TryParse(thisChunk.ToString(), out thisNumericChunk) - || !int.TryParse(thatChunk.ToString(), out thatNumericChunk)) + // Only need to compare the most significant digit + span1 = span1.Slice(i, 1); + span2 = span2.Slice(i, 1); + } + + if (!ulong.TryParse(span1, out var num1) + || !ulong.TryParse(span2, out var num2)) { return 0; } - - if (thisNumericChunk < thatNumericChunk) + else if (num1 < num2) { return -1; } - - if (thisNumericChunk > thatNumericChunk) + else if (num1 > num2) { return 1; } } else { - int result = thisChunk.ToString().CompareTo(thatChunk.ToString()); + int result = span1.CompareTo(span2, StringComparison.InvariantCulture); if (result != 0) { return result; } } + } while (pos1 < len1 && pos2 < len2); - } - - return 0; + return len1 - len2; } + /// public int Compare(string x, string y) { return CompareValues(x, y); -- cgit v1.2.3