Recent

Author Topic: Problem with sorting string (filepaths)  (Read 5392 times)

TomTom

  • Full Member
  • ***
  • Posts: 170
Problem with sorting string (filepaths)
« on: February 21, 2018, 09:32:14 am »
Hi :)
I need to sort filepaths (aquired using FindAllFiles) in StringGrid/StringList and I don't know where to start.
I'm working on a program that deals almost all the time (99.99%) with files (files with leading zeros) in specific folder structure
For example:
Code: Pascal  [Select][+][-]
  1. C:\35\123\0\0\1.1\1\ <-- files here
  2. C:\35\123\0\0\1.1\2\ <-- files here
  3. C:\35\123\0\0\1.1\3\ <-- files here
  4. etc.
  5.  
Digits in folder names can change. I put those file paths in StringGrid and they sort like this
Code: Pascal  [Select][+][-]
  1. C:\35\123\0\0\1.1\1\ <-- files here
  2. C:\35\123\0\0\1.1\10\ <-- files here
  3. C:\35\123\0\0\1.1\11\ <-- files here
  4. C:\35\123\0\0\1.1\2\ <-- files here
  5. C:\35\123\0\0\1.1\3\ <-- files here
  6. C:\35\123\0\0\1.1\4\ <-- files here
  7. C:\35\123\0\0\1.1\5\ <-- files here
  8. C:\35\123\0\0\1.1\6\ <-- files here
  9. C:\35\123\0\0\1.1\7\ <-- files here
  10. C:\35\123\0\0\1.1\8\ <-- files here
  11. C:\35\123\0\0\1.1\9\ <-- files here
  12. etc.
  13.  
My question is. How can I sort them  this way:
Code: Pascal  [Select][+][-]
  1. C:\35\123\0\0\1.1\1\ <-- files here
  2. C:\35\123\0\0\1.1\2\ <-- files here
  3. C:\35\123\0\0\1.1\3\ <-- files here
  4. C:\35\123\0\0\1.1\4\ <-- files here
  5. C:\35\123\0\0\1.1\5\ <-- files here
  6. C:\35\123\0\0\1.1\6\ <-- files here
  7. C:\35\123\0\0\1.1\7\ <-- files here
  8. C:\35\123\0\0\1.1\8\ <-- files here
  9. C:\35\123\0\0\1.1\9\ <-- files here
  10. C:\35\123\0\0\1.1\10\ <-- files here
  11. C:\35\123\0\0\1.1\11\ <-- files here
  12. etc.
  13.  


ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: Problem with sorting string (filepaths)
« Reply #1 on: February 21, 2018, 10:15:15 am »
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3. {$MODE OBJFPC}
  4.  
  5. uses SysUtils, Classes;
  6.  
  7. function TryLastPathAsInteger(const S: string; out Value: Integer): Boolean;
  8. begin
  9.   Result := TryStrToInt(ExtractFileName(ExcludeTrailingPathDelimiter(S)), Value);
  10. end;
  11.  
  12. function NaturalSort(List: TStringList; Index1, Index2: Integer): Integer;
  13. var
  14.   S1, S2: string;
  15.   N1, N2: Integer;
  16. begin
  17.   S1 := List[Index1];
  18.   S2 := List[Index2];
  19.   if TryLastPathAsInteger(S1, N1) and TryLastPathAsInteger(S2, N2) then
  20.     Result := N1 - N2
  21.   else
  22.     Result := AnsiCompareFileName(S1, S2);
  23. end;
  24.  
  25. var
  26.   List: TStringList;
  27.   i: Integer;
  28. begin
  29.   List := TStringList.Create;
  30.   try
  31.     for i := 1 to 11 do
  32.       List.Append(Format('C:\35\123\0\0\1.1\%d\', [i]));
  33.     Writeln('--Natural sorting--');
  34.     List.CustomSort(@NaturalSort);
  35.     Writeln(List.Text);
  36.     Writeln('--Alphabetical sorting--');
  37.     List.Sort;
  38.     Writeln(List.Text);
  39.   finally
  40.     List.Free;
  41.   end;
  42.   Readln;
  43. end.

RayoGlauco

  • Full Member
  • ***
  • Posts: 176
  • Beers: 1567
Re: Problem with sorting string (filepaths)
« Reply #2 on: February 21, 2018, 10:16:39 am »
I think you must use a custom sort function adapted to your needs. Like this example:

Code: Pascal  [Select][+][-]
  1. program CustomSortExample;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils, Classes;
  7.  
  8. function StringListSortProc(List: TStringList; Index1, Index2: Integer): Integer;
  9. var
  10.   i1, i2: Integer;
  11. begin
  12.   i1 := StrToInt(List[Index1]);
  13.   i2 := StrToInt(List[Index2]);
  14.   Result := i1 - i2;
  15. end;
  16.  
  17. var
  18.   SL: TStringList;
  19.   s: string;
  20. begin
  21.   SL := TStringList.Create;
  22.   SL.Add('3456');
  23.   SL.Add('345');
  24.   SL.Add('123');
  25.   SL.Add('59231');
  26.   SL.Add('545');
  27.   WriteLn('Before sort');
  28.   for s in SL do
  29.     WriteLn('  ' + s);
  30.   SL.CustomSort(@StringListSortProc);
  31.   WriteLn('');
  32.   WriteLn('After sort');
  33.   for s in SL do
  34.     WriteLn('  ' + s);
  35.   ReadLn;
  36.   SL.Free;
  37. end.

In this case, the output is:

Code: [Select]
Before sort
  3456
  345
  123
  59231
  545

After sort
  123
  345
  545
  3456
  59231
To err is human, but to really mess things up, you need a computer.

somsrina9

  • Newbie
  • Posts: 1
Re: Problem with sorting string (filepaths)
« Reply #3 on: February 21, 2018, 11:16:03 am »
I have the same problem with you. What do I need to do to fix it?

TomTom

  • Full Member
  • ***
  • Posts: 170
Re: Problem with sorting string (filepaths)
« Reply #4 on: February 21, 2018, 11:20:32 am »
@somsrina9
I will try those suggestions that RayoGlauco and ASerge wrote and I will post results later today. 
« Last Edit: February 21, 2018, 11:31:55 am by TomTom »

molly

  • Hero Member
  • *****
  • Posts: 2330
Re: Problem with sorting string (filepaths)
« Reply #5 on: February 21, 2018, 01:27:01 pm »
Attached is natural string comparing functions from Martin Pool (1:1 translation from c to Pascal) Original c files included as well as some test-data and Pascal example.

Follow ASerge's lead and use sort function like this:
Code: Pascal  [Select][+][-]
  1. function NaturalSort(List: TStringList; Index1, Index2: Integer): Integer;
  2. var
  3.   a, b: pnat_char;
  4. begin
  5.   a := pnat_char(List[index1]);
  6.   b := pnat_char(List[index2]);
  7.  
  8.   if List.CaseSensitive
  9.   then Result := strnatcmp(a, b)
  10.   else Result := strnatcasecmp(a, b);
  11. end;
  12.  

Happy coding !
« Last Edit: February 21, 2018, 01:34:45 pm by molly »

TomTom

  • Full Member
  • ***
  • Posts: 170
Re: Problem with sorting string (filepaths)
« Reply #6 on: February 21, 2018, 03:51:03 pm »
@molly
Thank You molly (or Molly?) ... Works like a charm :D

Attached is natural string comparing functions from Martin Pool (1:1 translation from c to Pascal) Original c files included as well as some test-data and Pascal example.

Follow ASerge's lead and use sort function like this:
Code: Pascal  [Select][+][-]
  1. function NaturalSort(List: TStringList; Index1, Index2: Integer): Integer;
  2. var
  3.   a, b: pnat_char;
  4. begin
  5.   a := pnat_char(List[index1]);
  6.   b := pnat_char(List[index2]);
  7.  
  8.   if List.CaseSensitive
  9.   then Result := strnatcmp(a, b)
  10.   else Result := strnatcasecmp(a, b);
  11. end;
  12.  

Happy coding !

TomTom

  • Full Member
  • ***
  • Posts: 170
Re: Problem with sorting string (filepaths)
« Reply #7 on: February 25, 2018, 07:51:01 pm »
Well... after some tests. I need to sort paths like in Windows :
Code: Pascal  [Select][+][-]
  1. c:\Fold\0\
  2. c:\Fold\1\
  3. c:\Fold\1.1\
  4. c:\Fold\1.2\
  5. c:\Fold\2\
  6. c:\Fold\2.1\
  7.  

How can I achieve this?
Now it's sorting like that

Code: Pascal  [Select][+][-]
  1. c:\Fold\0\
  2. c:\Fold\1.1\
  3. c:\Fold\1.2\
  4. c:\Fold\1\
  5. c:\Fold\2.1\
  6. c:\Fold\2\
  7. etc
  8.  

So I need that folder named 1.1 comes AFTER folder named 1 not before...  And folder 1.1.1 comes after folder named 1.1 and after folder named 1.





Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Problem with sorting string (filepaths)
« Reply #8 on: February 25, 2018, 09:04:09 pm »
Well... after some tests. I need to sort paths like in Windows :
Code: Pascal  [Select][+][-]
  1. c:\Fold\0\
  2. c:\Fold\1\
  3. c:\Fold\1.1\
  4. c:\Fold\1.2\
  5. c:\Fold\2\
  6. c:\Fold\2.1\
  7.  

How can I achieve this?
Now it's sorting like that

Code: Pascal  [Select][+][-]
  1. c:\Fold\0\
  2. c:\Fold\1.1\
  3. c:\Fold\1.2\
  4. c:\Fold\1\
  5. c:\Fold\2.1\
  6. c:\Fold\2\
  7. etc
  8.  

So I need that folder named 1.1 comes AFTER folder named 1 not before...  And folder 1.1.1 comes after folder named 1.1 and after folder named 1.
What comes into my mind is to split both strings using \ (or better: System.DirectorySeparator) then compare element by element of the resulting list. This will keep existing correctness while solving your problem where '\' > '.' from ordinal POV (92 > 46).

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Problem with sorting string (filepaths)
« Reply #9 on: February 26, 2018, 12:10:01 am »
What comes into my mind is to split both strings using \ (or better: System.DirectorySeparator) then compare element by element of the resulting list. This will keep existing correctness while solving your problem where '\' > '.' from ordinal POV (92 > 46).

Since the problem stems from (92 > 46), he could simply replace 92 with something less than 46 prior to comparison:
Code: Pascal  [Select][+][-]
  1. function StringListCompareNatural(List: TStringList;
  2.   Index1, Index2: Integer): Integer;
  3. var
  4.   s1,s2: string;
  5. begin
  6.   s1 := StringReplace(List[Index1],'\',#$01,[rfReplaceAll]);
  7.   s2 := StringReplace(List[Index2],'\',#$01,[rfReplaceAll]);
  8.   Result := YourNaturalCompareFunc(s1, s2, caseSensitive);
  9. end;

That might be faster. But then again he might have a similar problem with some other character.

molly

  • Hero Member
  • *****
  • Posts: 2330
Re: Problem with sorting string (filepaths)
« Reply #10 on: February 26, 2018, 02:25:14 am »
Well... after some tests. I need to sort paths like in Windows :
Windows is cheating because in explorer all items (at least what you visually see) are (file or directory -name) endpoints

Quote
How can I achieve this?
How would you (as a human and also explorer) achieve it ?

answer: by separating the strings (as suggested by Leledumbo) so that you create a new endpoint.

Quote
Now it's sorting like that
As written above: make the name of the directory an endpoint and you have your desired result.

Quote
So I need that folder named 1.1 comes AFTER folder named 1 not before...  And folder 1.1.1 comes after folder named 1.1 and after folder named 1.

What about this ?
Code: Pascal  [Select][+][-]
  1. function NaturalSortIndividualFoldersAsWell(List: TStringList; Index1, Index2: Integer): Integer;
  2. const
  3.   Delims = ['/','\'];
  4. var
  5.   a, b: pnat_char;
  6.   n, n1, n2, nr: integer;
  7.   parta, partb : string;
  8. begin
  9.   n1 := WordCount(List[index1], Delims);
  10.   n2 := WordCount(List[index2], Delims);
  11.  
  12.   nr := Min(n1, n2);
  13.  
  14.   for n := 1 to nr do
  15.   begin
  16.     parta := ExtractWord(n, List[index1], Delims);
  17.     partb := ExtractWord(n, List[index2], Delims);
  18.  
  19.     a := pnat_char(parta);
  20.     b := pnat_char(partb);
  21.  
  22.  
  23.     if List.CaseSensitive
  24.     then Result := strnatcmp(a, b)
  25.     else Result := strnatcasecmp(a, b);
  26.  
  27.     if (Result <> 0) then exit;
  28.   end;
  29. end;
  30.  

That would also take care of:
But then again he might have a similar problem with some other character.
.. as you can extend the list of delmis easily and to hearts desire  :)

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Problem with sorting string (filepaths)
« Reply #11 on: February 26, 2018, 03:48:43 am »
That would also take care of:
But then again he might have a similar problem with some other character.
.. as you can extend the list of delmis easily and to hearts desire  :)
Yes, as usual, you are right. What I meant to avoid is to wait to discover these characters.

I have a feeling that TomTom is targeting Windows. If so then use Windows function:
Code: Pascal  [Select][+][-]
  1. function StrCmpLogicalW(psz1, psz2: PWideChar): Integer; stdcall; external 'shlwapi.dll';
  2.  
  3. function StrCmpLogical(const s1, s2: string): Integer;
  4. begin
  5.   Result := StrCmpLogicalW(PWideChar(WideString(s1)), PWideChar(WideString(s2)));
  6. end;
  7.  
  8. function StringListCompareLogical(List: TStringList; Index1, Index2: Integer): Integer;
  9. begin
  10.   Result := StrCmpLogical(List[Index1], List[Index2]);
  11. end;

molly

  • Hero Member
  • *****
  • Posts: 2330
Re: Problem with sorting string (filepaths)
« Reply #12 on: February 26, 2018, 04:05:22 am »
What I meant to avoid is to wait to discover these characters.
Understood now. Not wanted to be/sound clever.

(btw last showed code contains a flaw but that is for TS to figure out  ;D )

Quote
I have a feeling that TomTom is targeting Windows. If so then use Windows function:

Yes, i've tried that before i posted my adjusted naturalsort but could not get it to work (as requested by TS) for this data:
Code: [Select]
C:\35\123\0\0\1\dummy.filename
C:\35\123\0\0\1.1\dummy.filename
C:\35\123\0\0\1.2\dummy.filename
C:\35\123\0\0\1.3\dummy.filename
C:\35\123\0\0\2\dummy.filename
C:\35\123\0\0\2.1\dummy.filename
C:\35\123\0\0\2.2\dummy.filename
C:\35\123\0\0\2.3\dummy.filename
C:\35\123\0\0\3.1\dummy.filename
C:\35\123\0\0\9\dummy.filename
C:\35\123\0\0\4.3\dummy.filename
With StrCmpLogicalW it sort for me as:
Code: [Select]
C:\35\123\0\0\1.1\dummy.filename
C:\35\123\0\0\1.2\dummy.filename
C:\35\123\0\0\1.3\dummy.filename
C:\35\123\0\0\1\dummy.filename
C:\35\123\0\0\2.1\dummy.filename
C:\35\123\0\0\2.2\dummy.filename
C:\35\123\0\0\2.3\dummy.filename
C:\35\123\0\0\2\dummy.filename
C:\35\123\0\0\3.1\dummy.filename
C:\35\123\0\0\4.3\dummy.filename
C:\35\123\0\0\9\dummy.filename
It seems that StrCmpLogicalW uses the same approach for sorting/comparing as the natural comparison function from Martin.

Therefor imho: only because each entry in explorer is an individual standalone 'part' of the complete folder/path it works. Shell-api seems to use (or allow to use) some other approaches but i have a hunch they fall back to a similar function like StrCmpLogicalW

Thanks for the casts and conversion though as i always seem to do that wrong  :-[

edit: typo's
« Last Edit: February 26, 2018, 04:08:22 am by molly »

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Problem with sorting string (filepaths)
« Reply #13 on: February 26, 2018, 04:18:48 am »
Yes, StrCmpLogicalW gives that order, but if you apply Leledumbo's method it gives the same results as Windows.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Problem with sorting string (filepaths)
« Reply #14 on: February 26, 2018, 07:23:01 pm »
That might be faster. But then again he might have a similar problem with some other character.
That's why I suggest using split by directory separator approach. Slower, but should give the expected result.

 

TinyPortal © 2005-2018