Numeric sort file system names in C#, like Windows Explorer

I was trying to figure out how to do this last night, getting nowhere, and can’t afford to go online the rest of this month, having spent most of my money already…

Update: This code has a couple of issues. See my next post for an updated and improved implementation.

So first thing at work this morning, I Googled it, and found the answer immediately on Stack Overflow, which is to use the Windows API function, StrCmpLogicalW. That’s what my RomyView program currently does.

But what interested me more afterwards, was the fact that several people have struggled to try and implement a natural numeric search in C#. Some have done a great job, while many have failed. But being lazy, my first thought on this was: Why not do the obvious? Search for the C implementation of StrCmpLogicalW, then just convert it to C#. So that’s what I did.

I found the Wine implementation, not the Windows one, but so what?

C# StrCmpLogicalW implementation
  1. public static int StrCmpLogicalW(string x, string y)
  2. {
  3.     if (x != null && y != null)
  4.     {
  5.         int xIndex = 0;
  6.         int yIndex = 0;
  7.  
  8.         while (xIndex < x.Length)
  9.         {
  10.             if (yIndex >= y.Length)
  11.                 return 1;
  12.  
  13.             if (char.IsDigit(x[xIndex]))
  14.             {
  15.                 if (!char.IsDigit(y[yIndex]))
  16.                     return -1;
  17.  
  18.                 // Compare the numbers
  19.                 List<char> xText = new List<char>();
  20.                 List<char> yText = new List<char>();
  21.  
  22.                 for (int i = xIndex; i < x.Length; i++)
  23.                 {
  24.                     var xChar = x[i];
  25.  
  26.                     if (char.IsDigit(xChar))
  27.                         xText.Add(xChar);
  28.                     else
  29.                         break;
  30.                 }
  31.  
  32.                 for (int j = yIndex; j < y.Length; j++)
  33.                 {
  34.                     var yChar = y[j];
  35.  
  36.                     if (char.IsDigit(yChar))
  37.                         yText.Add(yChar);
  38.                     else
  39.                         break;
  40.                 }
  41.  
  42.                 int xValue = Convert.ToInt32(new string(xText.ToArray()));
  43.                 int yValue = Convert.ToInt32(new string(yText.ToArray()));
  44.  
  45.                 if (xValue < yValue)
  46.                     return -1;
  47.                 else if (xValue > yValue)
  48.                     return 1;
  49.  
  50.                 // Skip
  51.                 xIndex += xText.Count;
  52.                 yIndex += yText.Count;
  53.             }
  54.             else if (char.IsDigit(y[yIndex]))
  55.                 return 1;
  56.             else
  57.             {
  58.                 int difference = char.ToUpperInvariant(x[xIndex]).CompareTo(char.ToUpperInvariant(y[yIndex]));
  59.                 if (difference > 0)
  60.                     return 1;
  61.                 else if (difference < 0)
  62.                     return -1;
  63.  
  64.                 xIndex++;
  65.                 yIndex++;
  66.             }
  67.         }
  68.  
  69.         if (yIndex < y.Length)
  70.             return -1;
  71.     }
  72.  
  73.     return 0;
  74. }

 

I call it from an IComparer<string>, which is used to compare, and thus sort, the files and directories displayed in the application. A simple comparer implementation might look like this:

  1. private static readonly IComparer<string> directoryComparer = Comparer<string>.Create((x, y) =>
  2. {
  3.     return IO.Sort.Direction == SortDirection.Ascending ? StrCmpLogicalW(x, y) : StrCmpLogicalW(y, x);
  4. });

 

Here is the original C code for reference. Of course it’s a few lines less than my C# port, which uses indexes into the strings, not pointers, and in C# we don’t have such convenient functions as StrToIntExW. Other than that, I deliberately stuck to the original code layout, rather than refactor it, and resisted the urge to use Linq when building the numbers to compare (or even StringBuilder in those for loops, for no reason really).

Wine’s C StrCmpLogicalW implementation
  1. /*************************************************************************
  2. * StrCmpLogicalW       [SHLWAPI.@]
  3. *
  4. * Compare two strings, ignoring case and comparing digits as numbers.
  5. *
  6. * PARAMS
  7. *  lpszStr  [I] First string to compare
  8. *  lpszComp [I] Second string to compare
  9. *  iLen     [I] Length to compare
  10. *
  11. * RETURNS
  12. *  TRUE  If the strings are equal.
  13. *  FALSE Otherwise.
  14. */
  15. INT WINAPI StrCmpLogicalW(LPCWSTR lpszStr, LPCWSTR lpszComp)
  16. {
  17.   INT iDiff;
  18.  
  19.   TRACE(“(%s,%s)\n”, debugstr_w(lpszStr), debugstr_w(lpszComp));
  20.  
  21.   if (lpszStr && lpszComp)
  22.   {
  23.     while (*lpszStr)
  24.     {
  25.       if (!*lpszComp)
  26.         return 1;
  27.       else if (isdigitW(*lpszStr))
  28.       {
  29.         int iStr, iComp;
  30.  
  31.         if (!isdigitW(*lpszComp))
  32.           return -1;
  33.  
  34.         /* Compare the numbers */
  35.         StrToIntExW(lpszStr, 0, &iStr);
  36.         StrToIntExW(lpszComp, 0, &iComp);
  37.  
  38.         if (iStr < iComp)
  39.           return -1;
  40.         else if (iStr > iComp)
  41.           return 1;
  42.  
  43.         /* Skip */
  44.         while (isdigitW(*lpszStr))
  45.           lpszStr++;
  46.         while (isdigitW(*lpszComp))
  47.           lpszComp++;
  48.       }
  49.       else if (isdigitW(*lpszComp))
  50.         return 1;
  51.       else
  52.       {
  53.         iDiff = ChrCmpIW(*lpszStr,*lpszComp);
  54.         if (iDiff > 0)
  55.           return 1;
  56.         else if (iDiff < 0)
  57.           return -1;
  58.  
  59.         lpszStr++;
  60.         lpszComp++;
  61.       }
  62.     }
  63.     if (*lpszComp)
  64.       return -1;
  65.   }
  66.   return 0;
  67. }
Advertisements

About Jerome

I am a senior C# developer in Johannesburg, South Africa. I am also a recovering addict, who spent nearly eight years using methamphetamine. I write on my recovery blog about my lessons learned and sometimes give advice to others who have made similar mistakes, often from my viewpoint as an atheist, and I also write some C# programming articles on my programming blog.
This entry was posted in Programming and tagged , , . Bookmark the permalink.

One Response to Numeric sort file system names in C#, like Windows Explorer

  1. KI WON PARK says:

    I’m sorry.

    I need PHP code for StrCmpLogicalW
    So I implemented PHP code.
    And it works good.

    usort ($jpegs,’StrCmpLogical’);

    /*************************************************************************
    function like StrCmpLogicalW [SHLWAPI.@]
    */
    function StrCmpLogical($lpszStr, $lpszComp)
    {
    // INT iDiff;
    // TRACE(“(%s,%s)\n”, debugstr_w(lpszStr), debugstr_w(lpszComp));

    if ($lpszStr==”” || $lpszComp==””)
    return strcasecmp ( $lpszStr,$lpszComp );

    while ($lpszStr!=””)
    {
    if ($lpszComp==””){
    return 1;
    }else
    if (ctype_digit (substr($lpszStr,0,1)))
    {
    if (!ctype_digit (substr($lpszComp,0,1)))
    return -1;

    /* Compare the numbers */
    $iStr = (int)$lpszStr;
    $iComp = (int)$lpszComp;

    if ($iStr $iComp)
    return 1;

    /* Skip */
    while (ctype_digit (substr($lpszStr,0,1)))
    $lpszStr = substr($lpszStr,1);

    while (ctype_digit (substr($lpszComp,0,1)))
    $lpszComp = substr($lpszComp,1);
    }else
    if (ctype_digit (substr($lpszComp,0,1)))
    {
    return 1;
    }else
    {
    $iDiff = strncasecmp ( $lpszStr,$lpszComp,1 );
    if ($iDiff > 0)
    return 1;
    else if ($iDiff < 0)
    return -1;

    $lpszStr = substr($lpszStr,1);
    $lpszComp = substr($lpszComp,1);
    }
    }
    if ($lpszComp)
    return -1;

    return 0;
    }

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s