Natural string comparison?

[Dibo]

Hi,

I'm using AnsiCompareText() function but it is not natural, instead of:

file_1.txt
file_2.txt
file_10.txt
file_20.txt

I get:
file_1.txt
file_10.txt
file_2.txt
file_20.txt

Does free pascal has natural string comparision function?

Regards

[Bart]

Not AFAIK.

While for the human eye this sorting is very easy, I think it'll be rather hard to write a generic algoritm for it.

Bart

[taazz]

it is easy for you to do instead of comparing file_1.txt compare file_01.txt and so on just make sure that you add enough zeros infrond of your number to cover the biggest number you have and you are set to go. In this  case I would say that going with 4 or 5 will suffice for all your file names and the patter is easy too everything between _ and . non inclusive is a number and must be padded to the correct length before comparison.

[engkin]

If you have control over these names, then Taazz's idea would be the best. Otherwise you can use something like:

Code: [Select]

function AnsiNaturalCompare(str1, str2: string; vCaseSensitive: boolean = False): integer;
var
  l1, l2: integer; //Str length
  n1, n2: integer; //numrical part
  i1, i2: integer; //index in Str
  d: integer;
begin
  if not vCaseSensitive then
  begin
    str1 := UpperCase(str1);
    str2 := UpperCase(str2);
  end;

  l1 := Length(str1);
  l2 := Length(str2);

  i1 := 1;
  i2 := 1;
  while i1 <= l1 do
  begin
    //Compare non-numbers
    d := Ord(str1[i1]) - Ord(str2[i2]);
    if not (str1[i1] in ['0'..'9']) then
    begin
      if (d <> 0) then
      begin
        Result := d;
        exit;
      end;
    end
    else
    begin
      //Convert a section of str1 to a number
      n1 := 0;
      repeat
        n1 := 10 * n1 + Ord(str1[i1]) - Ord('0');
        Inc(i1);
      until (i1 > l1) or not (str1[i1] in ['0'..'9']);

      //Convert a section of str2 to a number
      n2 := 0;
      repeat
        n2 := 10 * n2 + Ord(str2[i2]) - Ord('0');
        Inc(i2);
      until (i2 > l2) or not (str2[i2] in ['0'..'9']);

      //Compare numbers naturally
      d := n1 - n2;
      if d <> 0 then
      begin
        Result := d;
        exit;
      end
      else
        Continue;
    end;
    Inc(i1);
    Inc(i2);
  end;
  Result := (i1 - l1) - (i2 - l2);
end;

The result is <0 if str1<str2, 0 if str1=str2, and >0 if str1>str2

[JuhaManninen]

I didn't know it is called "Natural string comparison" but I had a similar problem with Refdes values in electronic schematic design part lists. I made a custom datatype for sorting them.
It was simple. I first checked if a string starts with an alphabet and ends with a number. Then a parser separated the textual and numeric parts. A comparison function used them both.

You also must handle the file suffix part correctly.

[Mike.Cornflake]

If you have control over these names, then Taazz's idea would be the best. Otherwise you can use something like:
...
The result is <0 if str1<str2, 0 if str1=str2, and >0 if str1>str2

Nice!  I've now nicked this routine, added it to my library and put you and this forum link down as the source.  Many thanks

[typo]

http://www.davekoelle.com/alphanum.html

[BeniBela]

My bbutils have such functions  (strCompareClever, striCompareClever), too

[taazz]

Actually my idea is based on the fact that he does not have control over the names. that is why I said the pattern to extract the numbers was from _ to . not inclusive.

I like the alphanum sort link by typo which sprout an interest to see what it exists for pascal and ended up at http://objectmix.com/delphi/401713-alphanumeric-sort-routine-delphi.html which on the end of the page has a reference to StrCmpLogicalW in shlwapi.dll which should be quit helpful in windows development.

AAAAAAAnd I'm to bored to search any further at least for today.

[engkin]

Actually my idea is based on the fact that he does not have control over the names.

@Taazz,
You are right. I did not pay enough attention. Your post was clear on that: "... and must be padded to the correct length before comparison."

Thanks for the information about StrCmpLogicalW in shlwapi.dll. I knew it was there somewhere but did not know where exactly and what name.

@Mike.Cornflake,
My pleasure. I give Dibo credit for the name, I had a cryptic name before.

[taazz]

well I did spend some more time search after all and I found an interesting looking pascal routine for natural sorting in delphi http://objectmix.com/delphi/722211-natural-sorting-optimizing-working-solution-3.html nothing ground shaking and I do not like the fact that they convert the string to integer for comparison on top of extracting/copying the number from the original string. I'm guessing this is going to be slow and is not needed just a length comparison and if they have the same length a simple string comparison will do which should be faster from multiple divisions by 10 to get the integer out of the string.

and then there is this which I do not understand nor access.
http://www.delphipraxis.net/29910-natuerliche-sortierungen-von-strings.html

[typo]

http://stackoverflow.com/questions/15257746/custom-sort-method-in-delphi-to-sort-list-of-strings

[Blaazen]

It would be nice to have it in StrUtils.

[typo]

I agree.

[typo]

My test project (attached).