Recent

Author Topic: Sorting and Counting  (Read 36212 times)

avk

  • Hero Member
  • *****
  • Posts: 752
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: 3921
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. ;)
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

mpknap

  • Full Member
  • ***
  • Posts: 155
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

  • Hero Member
  • *****
  • Posts: 752
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

  • Full Member
  • ***
  • Posts: 155
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

  • Hero Member
  • *****
  • Posts: 752
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: 14157
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
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

  • Hero Member
  • *****
  • Posts: 752
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: 3921
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 ;)
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

avk

  • Hero Member
  • *****
  • Posts: 752
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

  • Full Member
  • ***
  • Posts: 155
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: 14157
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: Sorting and Counting
« Reply #163 on: November 14, 2019, 08:31:18 am »
@mpknap, please test this version.

Thaddy

  • Hero Member
  • *****
  • Posts: 14157
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

 

TinyPortal © 2005-2018