Recent

Author Topic: Generic Array Sorting  (Read 1516 times)

Nitorami

  • Sr. Member
  • ****
  • Posts: 476
Generic Array Sorting
« on: February 09, 2024, 05:32:43 pm »
I converted a C routine to Pascal via CodeConvert. It uses generics which I don't necessarily need but thought this might be a chance to learn about them. I got to the point below but now get an error in the last line where the array should be sorted - "Syntax Error, Create expected but Sort found".
I am a bit lost here. I assume CodeConvert put the TArray in as placeholder for some sort of generic array. The docs say TArray (under sysutils) is "not needed in Free Pascal, where 2 array types are equal if their element types are equal." WTF ? And why in sysutils? Is there another TArray in Generics.Collection I should use ?

Maybe remove sysutils from the uses clause - aha, now the error message changes to "Generics without specialization cannot be used as a type for variables". That seems to make more sense but I can't get the specialization right. I beg for a hint.


Code: Pascal  [Select][+][-]
  1. function count_repeats(var rng: TRandom; expanse: SizeInt): SizeInt;
  2. type
  3.   rngval_t = Integer; // Assuming RNG_TYPE::result_type is an Integer
  4. var
  5.   values:  specialize TArray<rngval_t>;
  6.   prev, curr: rngval_t;
  7.   i, duplicates: SizeInt;
  8. begin
  9.   // Allocate an array to hold all the output.
  10.   SetLength(values, expanse);
  11.   Values := specialize TArray <integer>.Create;
  12.   // Store all the output from the generator.
  13.   for i := 0 to expanse - 1 do
  14.     values[i] := rng.Next; // Assuming rng() is equivalent to rng.Next
  15.   // Sort the array
  16.   TArray.Sort<rngval_t>(values);
  17.  

TRon

  • Hero Member
  • *****
  • Posts: 2278
Re: Generic Array Sorting
« Reply #1 on: February 09, 2024, 05:42:35 pm »
Specialize as a new type, see also wiki.

In casw you have competing typenames for generics you can prefix them with the name of the unit ,e.g.
Code: Pascal  [Select][+][-]
  1. type
  2.   TMyValues:  specialize sysutils.TArray<integer>;
  3.  

Nitorami

  • Sr. Member
  • ****
  • Posts: 476
Re: Generic Array Sorting
« Reply #2 on: February 09, 2024, 06:24:52 pm »
Nope, that does not work. Not in FPC 3.2.2. "<" expected but "." found.

And this is not the problem. I need an Array I can specialize to various integer types, and sort it. That shouldn't be difficult. The wiki says there is a Generics Collections (fully compatible with Delphi generics library) which offers a TArray with methods for searching and sorting. No further help is available:

https://wiki.lazarus.freepascal.org/Data_Structures,_Containers,_Collections

It seems my TArray is just an ordinary dynamic array, as no sort method is known. So maybe I need something different than TArray, but I can't find it. Where are the sortable array in generics collections ?



TRon

  • Hero Member
  • *****
  • Posts: 2278
Re: Generic Array Sorting
« Reply #3 on: February 09, 2024, 08:32:26 pm »
Nope, that does not work. Not in FPC 3.2.2. "<" expected but "." found.
Drats you are right. Sorry about that. It should be though.

Quote
And this is not the problem. I need an Array I can specialize to various integer types, and sort it. That shouldn't be difficult. The wiki says there is a Generics Collections (fully compatible with Delphi generics library) which offers a TArray with methods for searching and sorting. No further help is available:
There is but because anonymous procedures and functions are not yet implemented (they are in trunk but just recently) you need to use tarrayhelper for sorting (unit generics.collections).

In the rtl-generics package examples directory are some examples and/or have a look at this post.

« Last Edit: February 09, 2024, 10:20:19 pm by TRon »

Zvoni

  • Hero Member
  • *****
  • Posts: 2237
Re: Generic Array Sorting
« Reply #4 on: February 12, 2024, 09:20:27 am »
Err.... is it just me, or is he trying to call a Class Procedure in his Line 16?!?!?
Would have expected "Values.Sort;" or some such thing

EDIT: Just looked at the source: It actually IS a class Function....doh me  :-[
« Last Edit: February 12, 2024, 09:25:37 am by Zvoni »
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

TRon

  • Hero Member
  • *****
  • Posts: 2278
Re: Generic Array Sorting
« Reply #5 on: February 12, 2024, 10:25:39 am »
EDIT: Just looked at the source: It actually IS a class Function....doh me  :-[
Yeah, these days you never can be sure what to expect. For old timers (like myself) it can (still) be rather confusing at times. There is that small voice in the back of the head that keeps telling something is wrong there.

Just saying that you are not the only one   :)

Nitorami

  • Sr. Member
  • ****
  • Posts: 476
Re: Generic Array Sorting
« Reply #6 on: February 12, 2024, 12:27:17 pm »
The code was proposed by CodeConvert, including the call to the sort method in line 16 which does not work. It seems CodeConvert is ahead of its time, because the method is not yet implemented in Generics.Collections !?!

But anyway, I got the sorting to work with the TArrayHelper as TRon proposed. I'm an old timer myself, only just got used to type helpers, and now it confuses me that in the generic case I need to explicitly write TArrayHelper<sometype>.sort(MyArray) instead of MyArray.Sort. TRon says it has to do with the lack of anonymous functions; I don't understand this but guess I'll just accept it.

I still scratch my head about this sentence in https://www.freepascal.org/docs-html/3.2.0/rtl/sysutils/tarray.html:

"TArray [...] definition is not needed in Free Pascal, where 2 array types are equal if their element types are equal." What has the TArray definition to do with the question if two arrays are equal ???

Thaddy

  • Hero Member
  • *****
  • Posts: 14013
  • Probably until I exterminate Putin.
Re: Generic Array Sorting
« Reply #7 on: February 12, 2024, 01:13:51 pm »
The code was proposed by CodeConvert, including the call to the sort method in line 16 which does not work. It seems CodeConvert is ahead of its time, because the method is not yet implemented in Generics.Collections !?!
No, you have to implement a comparison by yourself that is by design. There is no default. Recurring subject, answered many times...
Specialize a type, not a var.

Nitorami

  • Sr. Member
  • ****
  • Posts: 476
Re: Generic Array Sorting
« Reply #8 on: February 12, 2024, 01:55:27 pm »
The wiki https://wiki.lazarus.freepascal.org/Data_Structures,_Containers,_Collections explicitly says The Generics Collections offers TArray with static methods for searching and sorting. That would be at least misleading; and in fact the sort method exists, and it works for integers, float and chars, probably more (not tested), but it must be called via a helper such as
Code: Pascal  [Select][+][-]
  1. TArrayHelper<mytype>.sort(MyArray)

I understand that I must define compare methods for my own specific types, but it would be embarrassing if everyone would have to reinvent this for simple types.

Thaddy

  • Hero Member
  • *****
  • Posts: 14013
  • Probably until I exterminate Putin.
Re: Generic Array Sorting
« Reply #9 on: February 12, 2024, 02:07:43 pm »
yes for simple cases there are predefined options. That is correct.
But usually useless with more complex cases.
Specialize a type, not a var.

TRon

  • Hero Member
  • *****
  • Posts: 2278
Re: Generic Array Sorting
« Reply #10 on: February 12, 2024, 05:34:00 pm »
TRon says it has to do with the lack of anonymous functions; I don't understand this but guess I'll just accept it.
Delphi allows for generic TArray to do things like:
Code: Pascal  [Select][+][-]
  1. TArray.Sort<TNode>(
  2.   Node,
  3.   TComparer<TNode>.Construct(
  4.     function(const Left, Right: TNode): Integer
  5.     begin
  6.       Result := TComparer<Double>.Default.Compare(Left.HCost, Right.HCost);
  7.     end
  8.   )
  9. );
  10.  
Which currently is not possible to realize with FPC due to lack of anonymous functions. It is thus not possible (yet) to make a generic such as TArray 100% compatible with Delphi. Unfortunately even with FPC generics implementation there are (still) some issues (see bugtracker reports) that need to be resolved or implemented. For example I am personally looking forward for typehelpers being able to be specialized/generalized.

Thaddy

  • Hero Member
  • *****
  • Posts: 14013
  • Probably until I exterminate Putin.
Re: Generic Array Sorting
« Reply #11 on: February 12, 2024, 05:36:50 pm »
It works in trunk/main, though,
Specialize a type, not a var.

TRon

  • Hero Member
  • *****
  • Posts: 2278
Re: Generic Array Sorting
« Reply #12 on: February 12, 2024, 05:40:56 pm »
True Thaddy but PascalDragon did the feature announcement ... what ... a couple of months ago or so ? (I might be mistaken on the time-line there)
« Last Edit: February 12, 2024, 05:43:27 pm by TRon »

Thaddy

  • Hero Member
  • *****
  • Posts: 14013
  • Probably until I exterminate Putin.
Re: Generic Array Sorting
« Reply #13 on: February 12, 2024, 05:50:30 pm »
PascalDragon also explicitly stated the availability of the feature in trunk, not in release. Before it is in a release we have to wait and as PascalDragon wrote, that can take some time.
Specialize a type, not a var.

kjteng

  • Sr. Member
  • ****
  • Posts: 252
Re: Generic Array Sorting
« Reply #14 on: February 15, 2024, 02:18:40 pm »
I have done some research recently to develop a generic array with some methods (quicksort, indexof, commaText etc) for my own purpose. Incidentally, I have also tried certain of the methods provided in generics.collections unit. I noticed that we can actually assign a custom compare method for the TArrayHelper/sort as follows:

Code: Pascal  [Select][+][-]
  1. // custom compare method
  2. function CompareMyRec(constref X, Y: TMyRecType): integer;
  3. begin
  4.  ...
  5. end;
  6.  
  7. // to call sort method with custom compare method:-
  8. Specialize TArrayHelper<TMyRecType>.Sort(ArrayOfMyRec,
  9.           Specialize Comparer<TMyRecType>.Construct(@CompareMyRec));
  10.  
The above will override the default compare method for simple data type e.g. integer, ansistring, etc).

 

TinyPortal © 2005-2018