Recent

Author Topic: Sorting and Counting  (Read 8511 times)

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #150 on: November 12, 2019, 05:50:14 pm »
In fact, everything is not as good as you say. I just accidentally discovered that the proposed solution cannot display the contents of the last node of the treeview. So I propose a fixed solution.

440bx

  • Hero Member
  • *****
  • Posts: 1281
Re: Sorting and Counting
« Reply #151 on: November 12, 2019, 06:23:44 pm »
In fact, everything is not as good as you say.
but, you proved again that errare humanum est. ;)
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

mpknap

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #152 on: November 13, 2019, 06:20:20 am »
I installed LCLEXTENSION and VIRTUALTREEVIEW Package, but when installing LGeneric I have an error,

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #153 on: November 13, 2019, 09:59:04 am »
According to your screenshot, it is impossible to determine the version of the compiler used, but I suspect it is 3.0.4.
Quote from the LGenerics readme:
Quote
...In order to use it (FPC 3.3.1 and higher and Lazarus 1.9.0 and higher)...
If installing the appropriate version of the compiler is a serious problem for you, I might think about how to do without LGenerics.

mpknap

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #154 on: November 13, 2019, 06:31:29 pm »
Quote
If installing the appropriate version of the compiler is a serious problem for you, I might think about how to do without LGenerics.
If you could, it would be nice. This will be open code, and I don't want to oblige other interested parties to install Packages. It's supposed to be the easiest, not necessarily fast.

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #155 on: November 13, 2019, 07:23:40 pm »
Ok, basically we only need sorting and binary search algorithms.
A fairly good sorting algorithm is available in fcl-stl. But I had to write BinarySearch from scratch,
I hope that it will work correctly. Let me know if anything goes wrong.

Upd. I forgot to remove the dependency on LGenerics from the project. :-[
I replaced the attachment.
« Last Edit: November 13, 2019, 08:24:42 pm by avk »

Thaddy

  • Hero Member
  • *****
  • Posts: 9293
Re: Sorting and Counting
« Reply #156 on: November 13, 2019, 08:05:38 pm »
@avk there's a good search at http://www.martincharvey.net I even have a fpc adaptation if you are interested. But you can also add {$mode delphi} ... :D ;)
I am referring to his binarytree.pas and indexedstore.pas. The latter is the conceptually most interesting.
« Last Edit: November 13, 2019, 08:20:10 pm by Thaddy »
also related to equus asinus.

howardpc

  • Hero Member
  • *****
  • Posts: 3203
Re: Sorting and Counting
« Reply #157 on: November 13, 2019, 08:21:10 pm »
@avk
If you intended your second sort-count.zip to avoid dependency on LGenerics, did you upload the wrong file?

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #158 on: November 13, 2019, 08:31:03 pm »
@Thaddy, thank you, interesting.
@ howardpc, no, I forgot to remove the dependency, thank you very much.

440bx

  • Hero Member
  • *****
  • Posts: 1281
Re: Sorting and Counting
« Reply #159 on: November 13, 2019, 09:22:19 pm »
Ok, basically we only need sorting and binary search algorithms.
A fairly good sorting algorithm is available in fcl-stl. But I had to write BinarySearch from scratch,
I hope that it will work correctly. Let me know if anything goes wrong.
Just in case you may be interested and, in addition to what Thaddy above mentioned, under Windows, ntdll provides a typical bsearch function to search a sorted sequence. 

I use the following definitions:
Code: Pascal  [Select]
  1. // -----------------------------------------------------------------------------
  2. // qsort and bsearch related types
  3.  
  4. type
  5.   TCompareFunction = function (key : pointer; data : pointer) : ptrint; cdecl;
  6.  
  7. const
  8.   COMPARE_EQUAL   =  0;
  9.   COMPARE_GREATER =  1;
  10.   COMPARE_LESS    = -1;
  11.  
  12.  
  13. function bsearch(key             : pointer;
  14.                  base            : pointer;
  15.                  num             : ptruint;
  16.                  width           : ptruint;
  17.                  CompareFunction : TCompareFunction) : pointer;
  18.   cdecl; external ntdll;
  19.   // ; void *__cdecl bsearch(const void *Key,
  20.   //                         const void *Base,
  21.   //                             size_t NumOfElements,
  22.   //                             size_t SizeOfElements,
  23.   //                               int (__cdecl *PtFuncCompare)(const void *,
  24.   //                                                            const void *))
  25.  
  26. procedure qsort(base            : pointer;
  27.                 num             : ptruint;
  28.                 width           : ptruint;
  29.                 CompareFunction : TCompareFunction);
  30.   cdecl; external ntdll;
  31.   // ; void __cdecl qsort(void  *Base,
  32.   //                      size_t NumOfElements,
  33.   //                      size_t SizeOfElements,
  34.   //                         int (__cdecl *PtFuncCompare)(const void *,
  35.   //                                                      const void *))
  36.  
  37.  
  38.  
so far, it seems to be bug free ;)
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #160 on: November 14, 2019, 05:02:06 am »
@440bx, thanks. However, there is a significant point. In our case, we need a binary search that, in the case of duplicate values, returns the position of the leftmost one.

mpknap

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #161 on: November 14, 2019, 07:44:47 am »
AVK, I'm sorry but I still have problem with starting sort_count.lpk. He refers to LGeneric, and he can't find RTTI. I even installed the latest version of Lazarus 2.0.6 FPC 3.0.4. for windows 10/64.

Thank you anyway.

Thaddy

  • Hero Member
  • *****
  • Posts: 9293
Re: Sorting and Counting
« Reply #162 on: November 14, 2019, 07:48:23 am »
AVK, I'm sorry but I still have problem with starting sort_count.lpk. He refers to LGeneric, and he can't find RTTI. I even installed the latest version of Lazarus 2.0.6 FPC 3.0.4. for windows 10/64.

Thank you anyway.
lgenerics needs 3.2.0 or trunk. Not 3.0.4. avk already wrote that.
The rtti unit is also introduced in 3.2.0. See https://wiki.freepascal.org/FPC_New_Features_3.2#Rtti_unit
I suggest you install 3.2.0. It is stable, feature complete  and for major platforms there are ready builds.
And fpcdeluxe can build and install fpc3.2.0+Lazarus 2.0.6 for you.
« Last Edit: November 14, 2019, 08:20:37 am by Thaddy »
also related to equus asinus.

avk

  • Full Member
  • ***
  • Posts: 167
    • my self-education project
Re: Sorting and Counting
« Reply #163 on: November 14, 2019, 08:31:18 am »
@mpknap, please test this version.

Thaddy

  • Hero Member
  • *****
  • Posts: 9293
Re: Sorting and Counting
« Reply #164 on: November 14, 2019, 10:32:58 am »
@mpknap, please test this version.
Back-porting just before a major release?  :D :D :D :D
But lgenerics is excellent and a good addition, even replacement, to rtl-generics because it covers a wider scope.
It is not for beginners, though, but you know that.
« Last Edit: November 14, 2019, 10:35:37 am by Thaddy »
also related to equus asinus.