Recent

Author Topic: Universal Sort in Lazarus / Freepascal  (Read 15279 times)

ratmalwer

  • Jr. Member
  • **
  • Posts: 57
Universal Sort in Lazarus / Freepascal
« on: November 11, 2017, 11:09:00 pm »
Hello

I was searching the net for an universal-sort for an array of records or some universal sort with tha ability to handle: miltiple fields, ASC /DESC, casesensitiity, and Unicode (UTF8)-support.

I did not find it so I started programming my own (code for a shellsort below - not finished but working fine).

Now I read in a old article: there are plenty or sortfunctions in Freepascal.

What did I miss??? Where is this documentation I did not find?

Code: Pascal  [Select][+][-]
  1. function Compare(const ARecord1, ARecord2:TArrayA):Integer;
  2. // EQ = 0 , GR = 1 , LESS = -1
  3.  
  4. // Tipp: für DESC  einfach das Result umkehren... ungetestet  mk.
  5. // Strings ev mit UTF8Compare vergleichen
  6. // Upper / Lowercase durchdenken und implementieren
  7.  
  8.  
  9. begin
  10.  
  11.   Result := 0;
  12.   // FELD 1
  13.   Result := UTF8CompareStr(Uppercase(ARecord1.String5),uppercase(Arecord2.string5));
  14.   if Result = 0 then
  15.   begin
  16.      if ARecord1.String5 < ARecord2.string5 then
  17.      begin
  18.         Result := -1
  19.      end else
  20.      // FELD 2
  21.      begin
  22.  
  23.         if ARecord1.Field2 > Arecord2.Field2 then
  24.         begin
  25.            Result := 1;
  26.         end else
  27.         begin
  28.            if ARecord1.Field2 < ARecord2.Field2 then
  29.            begin
  30.               Result := -1
  31.            end else
  32.            // FELD 3
  33.            begin
  34.  
  35.               if ARecord1.Field3 > Arecord2.Field3 then
  36.               begin
  37.                  Result := 1;
  38.               end else
  39.               begin
  40.                  if ARecord1.Field3 < ARecord2.Field3 then
  41.                  begin
  42.                     Result := -1
  43.                  end else
  44.                  // FELD 4 .....
  45.                  begin
  46.                      // ...... usw....
  47.                  end;
  48.               end;
  49.  
  50.            end;
  51.         end;
  52.  
  53.  
  54.      end;
  55.   end;
  56. end;
  57.  
  58. procedure qsort_2(lower,upper :integer);
  59. var left, right :integer;
  60. pivot :TArrayA;
  61. temp : TArrayA;
  62. begin
  63.     pivot:= ArrayA[(lower + upper) div 2];   //Pivot in mitte setzen
  64.     left := lower;
  65.     right := upper;
  66.  
  67.     while left<=right do
  68.     begin
  69.          while Compare(ArrayA[left],pivot) = -1 do left := left+1;    // kleiner: left erhöhen wenn bereits geordnet
  70.          while Compare(ArrayA[right],pivot) = 1 do right := right-1;  // grösser: right vermindern wenn bereits geordnet
  71.          if left<=right then                                          // dies vergleicht den index aber nicht den Wert!
  72.            begin
  73.              //SWAP Record
  74.              temp := ArrayA[left];
  75.              ArrayA[left] := ArrayA[right];
  76.              ArrayA[right] := temp;
  77.              left:=left+1;
  78.              right:=right-1
  79.            end;
  80.     end;
  81.     if right>lower then qsort_2(lower,right); { Sort the LEFT  part }
  82.     if upper>left  then qsort_2(left ,upper); { Sort the RIGHT part }
  83. end;

And a extraquestion:
Is there a function-summary with brief examples like in php-manual somewhere? At the moment I program by try and error and I am a bit tired to check each found functions to detrermie what the returnvalues could be.



marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Universal Sort in Lazarus / Freepascal
« Reply #1 on: November 11, 2017, 11:18:21 pm »
Some points wrt collection sorting:

- Afaik TArray<> has a sort routine. At least in Delphi it does. Might be only in FPC trunk  though. (packages/rtl-generics)
- TStringlist can be kept sorted, no need to do ad-hoc sorting.
- Compare routines should be configurable. E.g. to pick a natural compare over a normal one. Asc/desc is then just an inverted compare routine.
- I don't know PHP or its manual, and I like to keep it that way.

Mike.Cornflake

  • Hero Member
  • *****
  • Posts: 1260
Re: Universal Sort in Lazarus / Freepascal
« Reply #2 on: November 12, 2017, 12:13:05 am »
You ask a good question (sorting for records)

Have a look at the following:

http://wiki.freepascal.org/Array_sort

As the header says, that was prior to generics.  The idea in this wiki is that there is a general sort function, you just pass it a specific function that determines the rules for how one array element should be compared to another.  (ie, based on two index, you return -1, 0 or 1).  The actual soft algorthm is handled in the AnySort code.  That idea gets used a lot.

Instead of an array, you could use generics, where you use a collection class to handle your data.  Have a look at this post for instance
http://forum.lazarus.freepascal.org/index.php?topic=17772.0
http://wiki.freepascal.org/Generics

As for the help you are looking for, as a community there's been an effort to keep http://wiki.freepascal.org updated.

Welcome to the forum by the way :-)
Lazarus Trunk/FPC Trunk on Windows [7, 10]
  Have you tried searching this forum or the wiki?:   http://wiki.lazarus.freepascal.org/Alternative_Main_Page
  BOOKS! (Free and otherwise): http://wiki.lazarus.freepascal.org/Pascal_and_Lazarus_Books_and_Magazines


Mike.Cornflake

  • Hero Member
  • *****
  • Posts: 1260
Re: Universal Sort in Lazarus / Freepascal
« Reply #4 on: November 12, 2017, 12:30:38 am »
And time for a confession.  I've got lazy in my old age.  I generally just built up a TBufDataset and sort that.  Cause I know I'm going to want to filter that data a few different ways as well. 

TBufDataset is an in-memory data store.  Think of a Table in a database.

TBufDataset is memory overkill for for most of my uses, but my code in all the different apps is a darned site more consistent, and I've created a helper unit to simplify creation, population etc.

And I've only just started using SQLite.  Seriously thinking about switching over to that instead...
Lazarus Trunk/FPC Trunk on Windows [7, 10]
  Have you tried searching this forum or the wiki?:   http://wiki.lazarus.freepascal.org/Alternative_Main_Page
  BOOKS! (Free and otherwise): http://wiki.lazarus.freepascal.org/Pascal_and_Lazarus_Books_and_Magazines

ratmalwer

  • Jr. Member
  • **
  • Posts: 57
Re: Universal Sort in Lazarus / Freepascal
« Reply #5 on: November 12, 2017, 01:51:18 am »
Thanks guys for your replies...
I glanced trough it an will look at the code more closely later.

But actually I am a bit disapointed of the capability of Freepascal. In other languages there are predefined functions for such matters that are reliable, easy to use and well and brief documented. When I red that only integes can be sorted, or that records are not supported and only one sortcriteria is accepted - that makes me whine.

So I probably go on with my solution (so I know at least whats going on) witch cost me tree days now for for something I was used to make in 5 minutes by a command like:    sort(array1,filed1,asc,field2,desc,field3,asc)
« Last Edit: November 12, 2017, 02:05:14 am by ratmalwer »

ratmalwer

  • Jr. Member
  • **
  • Posts: 57
Re: Universal Sort in Lazarus / Freepascal
« Reply #6 on: November 12, 2017, 02:13:25 am »
@BeniBela

your code look awful long.... Is it reliable?

If so could you send me an examle how to implement it. I am using Freepascal/Lazarus only since a month and struggle with implementing a lot.

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Universal Sort in Lazarus / Freepascal
« Reply #7 on: November 12, 2017, 09:46:20 am »
Thanks guys for your replies...
I glanced trough it an will look at the code more closely later.

But actually I am a bit disapointed of the capability of Freepascal. In other languages there are predefined functions for such matters that are reliable, easy to use and well and brief documented. When I red that only integes can be sorted, or that records are not supported and only one sortcriteria is accepted - that makes me whine.

So I probably go on with my solution (so I know at least whats going on) witch cost me tree days now for for something I was used to make in 5 minutes by a command like:    sort(array1,filed1,asc,field2,desc,field3,asc)

Apart from rtl-generics, amongst other things, the fgl unit also has generic sorted lists, maps etc
Specialize a type, not a var.

guest58172

  • Guest
Re: Universal Sort in Lazarus / Freepascal
« Reply #8 on: November 12, 2017, 11:54:54 am »
Hello

I was searching the net for an universal-sort for an array of records or some universal sort with tha ability to handle: miltiple fields, ASC /DESC, casesensitiity, and Unicode (UTF8)-support.

I did not find it so I started programming my own (code for a shellsort below - not finished but working fine).

Now I read in a old article: there are plenty or sortfunctions in Freepascal.

Universal sort would need an wider vision of algorithms, a vision that usually doesn't exist in the FPC libraries that is: more template and duck types. Maybe also closures. The idea is to sop making specialized members functions and rather start making free functions, that can be called with aggregates providing certain methods (aka duck types, concepts, compile-time interface etc), so that an built-int array, a TArray<>, a TList, etc couldbe sorted with the same free function.

munair

  • Hero Member
  • *****
  • Posts: 798
  • compiler developer @SharpBASIC
    • SharpBASIC
Re: Universal Sort in Lazarus / Freepascal
« Reply #9 on: November 12, 2017, 01:11:18 pm »
I wouldn't waste my time trying to find a universal sorting routine. If your type doesn't provide a sort function then simply implement your own. Shellsort is small and easy. Here is an example:
Code: Pascal  [Select][+][-]
  1. procedure SortMyElements(var arr: TMyElements);
  2. var
  3.   gap, i, j, lim, max, pos: longword;
  4.   tmp: TMyElement
  5. begin
  6.   max := high(arr);
  7.   if max < 1 then
  8.     exit;
  9.  
  10.   gap := (max div 2) + 1;
  11.  
  12.   while gap > 0 do
  13.     begin
  14.       lim := max - gap;
  15.       repeat
  16.         begin
  17.           pos := 0;
  18.           for i := 0 to lim do
  19.             begin
  20.               j := i + gap;
  21.               if arr[i].SortMe > arr[j].SortMe then
  22.                 begin
  23.                   { switch items }
  24.                   tmp := arr[i];
  25.                   arr[i] := arr[j];
  26.                   arr[j] := tmp;
  27.                   pos := i;
  28.                 end;
  29.             end;
  30.           lim := pos - gap;
  31.         end;
  32.       until pos = 0;
  33.       gap := gap div 2;
  34.     end;
  35. end;

Another way to switch elements would be:
Code: Pascal  [Select][+][-]
  1. Move(arr1, tmp, SizeOf(TMyElement));
  2. Move(arr2, arr1, SizeOf(TMyElement));
  3. Move(tmp, arr2, SizeOf(TMyElement));
« Last Edit: November 12, 2017, 01:17:52 pm by Munair »
keep it simple

BeniBela

  • Hero Member
  • *****
  • Posts: 905
    • homepage
Re: Universal Sort in Lazarus / Freepascal
« Reply #10 on: November 12, 2017, 02:56:08 pm »
@BeniBela

your code look awful long.... Is it reliable?

If so could you send me an examle how to implement it. I am using Freepascal/Lazarus only since a month and struggle with implementing a lot.

Should be reliable, but could be faster

Implement it? You can see how the sort is implemented there

It can take a pointer to a custom comparison function and uses to CompareByte if no custom function is given


marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Universal Sort in Lazarus / Freepascal
« Reply #11 on: November 12, 2017, 03:00:35 pm »
But actually I am a bit disapointed of the capability of Freepascal. In other languages there are predefined functions for such matters that are reliable, easy to use and well and brief documented.

No beating around the bush Freepascal is relatively late.  While some basics were always covered ( e.g. for strings, one can simple use tstringlist, with custom sorting sorting, and there is a generalized qsort in the FPC examples and many circulate on the web).

And SQL-like sorting using custom datasets (like Mike Cornflake says) already works for ages , because there sorting rules are more fixed

For sorts parameterized with functions, you need two (sort and compare, and having generics eliminates the swap, but that only emerged late.

Note that such features are different for dynamically typed languages like PHP than for statically compiled languages like FPC. PHP is an interpreter, and its datastructures are more interpreter like, and aligned with SQL thinking.

FPC's datastructures are not, and thus database components are a more closer relative to PHP there than "normal"  pascal datastructures, which are a level more lowlevel. So  if you just want normal database like operation, use datasets.


guest58172

  • Guest
Re: Universal Sort in Lazarus / Freepascal
« Reply #12 on: November 12, 2017, 03:47:12 pm »
data structures should not matter. "What does something need to define as function to be sorted ?" that's all that matters. Things that can be sorted should implement these functions and it works.

soerensen3

  • Full Member
  • ***
  • Posts: 213
Re: Universal Sort in Lazarus / Freepascal
« Reply #13 on: November 12, 2017, 04:58:07 pm »
How about using an object instead of a record. You could implement a Compare function like this:

Code: Pascal  [Select][+][-]
  1. TTestObj = object
  2.   Field1: String;
  3.   Field2: String;
  4.   Field3: String;
  5.   Field4: Integer;
  6.   function Compare( AObj: TTestObj ): Integer;
  7. end;
  8. ...
  9. function TTestObj.Compare( AObj: TTestObj ): Integer;
  10.   function CompareStringField( Field1, Field2: String ): Integer;
  11.   begin
  12.     if ( Field1 < Field2 ) then
  13.       Result:= -1
  14.     else if ( Field1 > Field2 ) then
  15.       Result:= 1
  16.     else
  17.       Result:= 0;
  18.   end;
  19.   function CompareIntField( Field1, Field2: Integer ): Integer;
  20.   ... // Same as above
  21. begin
  22.   Result:= CompareStringField( Field1, AObj.Field1 );
  23.   if ( Result = 0 ) then
  24.     Result:= CompareStringField( Field2, AObj.Field2 );
  25.   if ( Result = 0 ) then
  26.     Result:= CompareStringField( Field3, AObj.Field3 );
  27.   if ( Result = 0 ) then
  28.     Result:= CompareIntField( Field4, AObj.Field4 );
  29. end;
You only need one sort function with this method. If you really need you can also use RTTI with properties on the object for a dynamic solution to have also only one compare function to work with different objects.
You could use a string array with the field names to implement a switchable sort order.

Another option instead of using an object would be to overload the compare operators in fpc for your record. There are examples on how to do that.
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)

lainz

  • Hero Member
  • *****
  • Posts: 4460
    • https://lainz.github.io/
Re: Universal Sort in Lazarus / Freepascal
« Reply #14 on: November 12, 2017, 05:04:57 pm »
data structures should not matter. "What does something need to define as function to be sorted ?" that's all that matters. Things that can be sorted should implement these functions and it works.

I agree.

I do always in JavaScript

Code: Javascript  [Select][+][-]
  1. something.sort((a, b) => { if(a.someField > b.someField) return 1; if (b.someField < b.someField) return -1; return 0; })

or just something.sort() if it is a string or a number array, already works.

Basically just implementing the comparator method, as it is done in Java for example (Comparable or Comparator).

 

TinyPortal © 2005-2018