Generic Array Sorting

[Nitorami]

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]

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]

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]

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.

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.

[Zvoni]

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 

[TRon]

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]

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]

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...

[Nitorami]

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]

yes for simple cases there are predefined options. That is correct.
But usually useless with more complex cases.

[TRon]

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]

It works in trunk/main, though,

[TRon]

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)

[Thaddy]

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.

[kjteng]

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).