Anyone have a good resource or provide a sample of a natural order sort in C# for an FileInfo array? I am implementing the IComparer interface in my sorts.
Natural Sort Order in C#
Viewed 64242
18 Answers
The easiest thing to do is just P/Invoke the built-in function in Windows, and use it as the comparison function in your IComparer:
[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
private static extern int StrCmpLogicalW(string psz1, string psz2);
Michael Kaplan has some examples of how this function works here, and the changes that were made for Vista to make it work more intuitively. The plus side of this function is that it will have the same behaviour as the version of Windows it runs on, however this does mean that it differs between versions of Windows so you need to consider whether this is a problem for you.
So a complete implementation would be something like:
[SuppressUnmanagedCodeSecurity]
internal static class SafeNativeMethods
{
[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
public static extern int StrCmpLogicalW(string psz1, string psz2);
}
public sealed class NaturalStringComparer : IComparer<string>
{
public int Compare(string a, string b)
{
return SafeNativeMethods.StrCmpLogicalW(a, b);
}
}
public sealed class NaturalFileInfoNameComparer : IComparer<FileInfo>
{
public int Compare(FileInfo a, FileInfo b)
{
return SafeNativeMethods.StrCmpLogicalW(a.Name, b.Name);
}
}
Pure C# solution for linq orderby:
http://zootfroot.blogspot.com/2009/09/natural-sort-compare-with-linq-orderby.html
public class NaturalSortComparer<T> : IComparer<string>, IDisposable
{
private bool isAscending;
public NaturalSortComparer(bool inAscendingOrder = true)
{
this.isAscending = inAscendingOrder;
}
#region IComparer<string> Members
public int Compare(string x, string y)
{
throw new NotImplementedException();
}
#endregion
#region IComparer<string> Members
int IComparer<string>.Compare(string x, string y)
{
if (x == y)
return 0;
string[] x1, y1;
if (!table.TryGetValue(x, out x1))
{
x1 = Regex.Split(x.Replace(" ", ""), "([0-9]+)");
table.Add(x, x1);
}
if (!table.TryGetValue(y, out y1))
{
y1 = Regex.Split(y.Replace(" ", ""), "([0-9]+)");
table.Add(y, y1);
}
int returnVal;
for (int i = 0; i < x1.Length && i < y1.Length; i++)
{
if (x1[i] != y1[i])
{
returnVal = PartCompare(x1[i], y1[i]);
return isAscending ? returnVal : -returnVal;
}
}
if (y1.Length > x1.Length)
{
returnVal = 1;
}
else if (x1.Length > y1.Length)
{
returnVal = -1;
}
else
{
returnVal = 0;
}
return isAscending ? returnVal : -returnVal;
}
private static int PartCompare(string left, string right)
{
int x, y;
if (!int.TryParse(left, out x))
return left.CompareTo(right);
if (!int.TryParse(right, out y))
return left.CompareTo(right);
return x.CompareTo(y);
}
#endregion
private Dictionary<string, string[]> table = new Dictionary<string, string[]>();
public void Dispose()
{
table.Clear();
table = null;
}
}
Here's a version for .NET Core 2.1+ / .NET 5.0+, using spans to avoid allocations
public class NaturalSortStringComparer : IComparer<string>
{
public static NaturalSortStringComparer Ordinal { get; } = new NaturalSortStringComparer(StringComparison.Ordinal);
public static NaturalSortStringComparer OrdinalIgnoreCase { get; } = new NaturalSortStringComparer(StringComparison.OrdinalIgnoreCase);
public static NaturalSortStringComparer CurrentCulture { get; } = new NaturalSortStringComparer(StringComparison.CurrentCulture);
public static NaturalSortStringComparer CurrentCultureIgnoreCase { get; } = new NaturalSortStringComparer(StringComparison.CurrentCultureIgnoreCase);
public static NaturalSortStringComparer InvariantCulture { get; } = new NaturalSortStringComparer(StringComparison.InvariantCulture);
public static NaturalSortStringComparer InvariantCultureIgnoreCase { get; } = new NaturalSortStringComparer(StringComparison.InvariantCultureIgnoreCase);
private readonly StringComparison _comparison;
public NaturalSortStringComparer(StringComparison comparison)
{
_comparison = comparison;
}
public int Compare(string x, string y)
{
// Let string.Compare handle the case where x or y is null
if (x is null || y is null)
return string.Compare(x, y, _comparison);
var xSegments = GetSegments(x);
var ySegments = GetSegments(y);
while (xSegments.MoveNext() && ySegments.MoveNext())
{
int cmp;
// If they're both numbers, compare the value
if (xSegments.CurrentIsNumber && ySegments.CurrentIsNumber)
{
var xValue = long.Parse(xSegments.Current);
var yValue = long.Parse(ySegments.Current);
cmp = xValue.CompareTo(yValue);
if (cmp != 0)
return cmp;
}
// If x is a number and y is not, x is "lesser than" y
else if (xSegments.CurrentIsNumber)
{
return -1;
}
// If y is a number and x is not, x is "greater than" y
else if (ySegments.CurrentIsNumber)
{
return 1;
}
// OK, neither are number, compare the segments as text
cmp = xSegments.Current.CompareTo(ySegments.Current, _comparison);
if (cmp != 0)
return cmp;
}
// At this point, either all segments are equal, or one string is shorter than the other
// If x is shorter, it's "lesser than" y
if (x.Length < y.Length)
return -1;
// If x is longer, it's "greater than" y
if (x.Length > y.Length)
return 1;
// If they have the same length, they're equal
return 0;
}
private static StringSegmentEnumerator GetSegments(string s) => new StringSegmentEnumerator(s);
private struct StringSegmentEnumerator
{
private readonly string _s;
private int _start;
private int _length;
public StringSegmentEnumerator(string s)
{
_s = s;
_start = -1;
_length = 0;
CurrentIsNumber = false;
}
public ReadOnlySpan<char> Current => _s.AsSpan(_start, _length);
public bool CurrentIsNumber { get; private set; }
public bool MoveNext()
{
var currentPosition = _start >= 0
? _start + _length
: 0;
if (currentPosition >= _s.Length)
return false;
int start = currentPosition;
bool isFirstCharDigit = Char.IsDigit(_s[currentPosition]);
while (++currentPosition < _s.Length && Char.IsDigit(_s[currentPosition]) == isFirstCharDigit)
{
}
_start = start;
_length = currentPosition - start;
CurrentIsNumber = isFirstCharDigit;
return true;
}
}
}
I've actually implemented it as an extension method on the StringComparer so that you could do for example:
StringComparer.CurrentCulture.WithNaturalSort()orStringComparer.OrdinalIgnoreCase.WithNaturalSort().
The resulting IComparer<string> can be used in all places like OrderBy, OrderByDescending, ThenBy, ThenByDescending, SortedSet<string>, etc. And you can still easily tweak case sensitivity, culture, etc.
The implementation is fairly trivial and it should perform quite well even on large sequences.
I've also published it as a tiny NuGet package, so you can just do:
Install-Package NaturalSort.Extension
The code including XML documentation comments and suite of tests is available in the NaturalSort.Extension GitHub repository.
The entire code is this (if you cannot use C# 7 yet, just install the NuGet package):
public static class StringComparerNaturalSortExtension
{
public static IComparer<string> WithNaturalSort(this StringComparer stringComparer) => new NaturalSortComparer(stringComparer);
private class NaturalSortComparer : IComparer<string>
{
public NaturalSortComparer(StringComparer stringComparer)
{
_stringComparer = stringComparer;
}
private readonly StringComparer _stringComparer;
private static readonly Regex NumberSequenceRegex = new Regex(@"(\d+)", RegexOptions.Compiled | RegexOptions.CultureInvariant);
private static string[] Tokenize(string s) => s == null ? new string[] { } : NumberSequenceRegex.Split(s);
private static ulong ParseNumberOrZero(string s) => ulong.TryParse(s, NumberStyles.None, CultureInfo.InvariantCulture, out var result) ? result : 0;
public int Compare(string s1, string s2)
{
var tokens1 = Tokenize(s1);
var tokens2 = Tokenize(s2);
var zipCompare = tokens1.Zip(tokens2, TokenCompare).FirstOrDefault(x => x != 0);
if (zipCompare != 0)
return zipCompare;
var lengthCompare = tokens1.Length.CompareTo(tokens2.Length);
return lengthCompare;
}
private int TokenCompare(string token1, string token2)
{
var number1 = ParseNumberOrZero(token1);
var number2 = ParseNumberOrZero(token2);
var numberCompare = number1.CompareTo(number2);
if (numberCompare != 0)
return numberCompare;
var stringCompare = _stringComparer.Compare(token1, token2);
return stringCompare;
}
}
}
Here is a naive one-line regex-less LINQ way (borrowed from python):
var alphaStrings = new List<string>() { "10","2","3","4","50","11","100","a12","b12" };
var orderedString = alphaStrings.OrderBy(g => new Tuple<int, string>(g.ToCharArray().All(char.IsDigit)? int.Parse(g) : int.MaxValue, g));
// Order Now: ["2","3","4","10","11","50","100","a12","b12"]
Inspired by Michael Parker's solution, here is an IComparer implementation that you can drop in to any of the linq ordering methods:
private class NaturalStringComparer : IComparer<string>
{
public int Compare(string left, string right)
{
int max = new[] { left, right }
.SelectMany(x => Regex.Matches(x, @"\d+").Cast<Match>().Select(y => (int?)y.Value.Length))
.Max() ?? 0;
var leftPadded = Regex.Replace(left, @"\d+", m => m.Value.PadLeft(max, '0'));
var rightPadded = Regex.Replace(right, @"\d+", m => m.Value.PadLeft(max, '0'));
return string.Compare(leftPadded, rightPadded);
}
}
A version that's easier to read/maintain.
public class NaturalStringComparer : IComparer<string>
{
public static NaturalStringComparer Instance { get; } = new NaturalStringComparer();
public int Compare(string x, string y) {
const int LeftIsSmaller = -1;
const int RightIsSmaller = 1;
const int Equal = 0;
var leftString = x;
var rightString = y;
var stringComparer = CultureInfo.CurrentCulture.CompareInfo;
int rightIndex;
int leftIndex;
for (leftIndex = 0, rightIndex = 0;
leftIndex < leftString.Length && rightIndex < rightString.Length;
leftIndex++, rightIndex++) {
var leftChar = leftString[leftIndex];
var rightChar = rightString[leftIndex];
var leftIsNumber = char.IsNumber(leftChar);
var rightIsNumber = char.IsNumber(rightChar);
if (!leftIsNumber && !rightIsNumber) {
var result = stringComparer.Compare(leftString, leftIndex, 1, rightString, leftIndex, 1);
if (result != 0) return result;
} else if (leftIsNumber && !rightIsNumber) {
return LeftIsSmaller;
} else if (!leftIsNumber && rightIsNumber) {
return RightIsSmaller;
} else {
var leftNumberLength = NumberLength(leftString, leftIndex, out var leftNumber);
var rightNumberLength = NumberLength(rightString, rightIndex, out var rightNumber);
if (leftNumberLength < rightNumberLength) {
return LeftIsSmaller;
} else if (leftNumberLength > rightNumberLength) {
return RightIsSmaller;
} else {
if(leftNumber < rightNumber) {
return LeftIsSmaller;
} else if(leftNumber > rightNumber) {
return RightIsSmaller;
}
}
}
}
if (leftString.Length < rightString.Length) {
return LeftIsSmaller;
} else if(leftString.Length > rightString.Length) {
return RightIsSmaller;
}
return Equal;
}
public int NumberLength(string str, int offset, out int number) {
if (string.IsNullOrWhiteSpace(str)) throw new ArgumentNullException(nameof(str));
if (offset >= str.Length) throw new ArgumentOutOfRangeException(nameof(offset), offset, "Offset must be less than the length of the string.");
var currentOffset = offset;
var curChar = str[currentOffset];
if (!char.IsNumber(curChar))
throw new ArgumentException($"'{curChar}' is not a number.", nameof(offset));
int length = 1;
var numberString = string.Empty;
for (currentOffset = offset + 1;
currentOffset < str.Length;
currentOffset++, length++) {
curChar = str[currentOffset];
numberString += curChar;
if (!char.IsNumber(curChar)) {
number = int.Parse(numberString);
return length;
}
}
number = int.Parse(numberString);
return length;
}
}
Let me explain my problem and how i was able to solve it.
Problem:- Sort files based on FileName from FileInfo objects which are retrieved from a Directory.
Solution:- I selected the file names from FileInfo and trimed the ".png" part of the file name. Now, just do List.Sort(), which sorts the filenames in Natural sorting order. Based on my testing i found that having .png messes up sorting order. Have a look at the below code
var imageNameList = new DirectoryInfo(@"C:\Temp\Images").GetFiles("*.png").Select(x =>x.Name.Substring(0, x.Name.Length - 4)).ToList();
imageNameList.Sort();
Related