Discussion:
Stringlist customsort
(too old to reply)
Franz Müller
2018-11-29 19:32:11 UTC
Permalink
Hi everybody!

Currently, the implementation of cutomsorted stringlists ist very far
from satisfactory; you have to call the sort routine again whenever a
string is added to the stringlist or an item is changed, because the
stringlist cannot keep itself automatically sorted using a custom
compare function. There is a better implemetation using the
"experimental" define FPC_TESTGENERICS, but this code has not become
"mainstream" FPC for a long time now, and I feel that the use of
generics for the implementation of stringlists will also introduce quite
some unnecessary overhead.

I would like to propose one of two versions of improvement of the
non-FPC_TESTGENERICS TStringlist, that I would also be willing to
program and to submit a patch for it.

Variation one:

Just add a property OnSort of type TListSortCompare and always sort
using the user-provided function if the property is not nil. Automatic
sorting would only occur if sortstyle=sslauto, while the behaviour for
sortstyle=ssluser would remain as before for backward compatibility.

Variation two, more flexible:

Add a property OnSort of type TStringListSortCompare, which would allow
stringlists to be sorted not only by the value of the string, but also
by the value of the fields of the associated object. In that case it
would be necessary to add a new sortstyle sslobject, which would have to
be used when OnSort uses fields from the object for comparing, as in
this case the find method cannot use binary search for locating an item,
just like for unsorted stringlists (and the stringlist wouldn't know
otherwise that it can't use binary search).

Franz


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.
Michael Van Canneyt
2018-11-30 08:15:28 UTC
Permalink
Post by Franz Müller
Hi everybody!
Currently, the implementation of cutomsorted stringlists ist very far
from satisfactory; you have to call the sort routine again whenever a
string is added to the stringlist or an item is changed, because the
stringlist cannot keep itself automatically sorted using a custom
compare function. There is a better implemetation using the
"experimental" define FPC_TESTGENERICS, but this code has not become
"mainstream" FPC for a long time now, and I feel that the use of
generics for the implementation of stringlists will also introduce quite
some unnecessary overhead.
The reason for not using the generic based version is that the generics code is slower.
Post by Franz Müller
I would like to propose one of two versions of improvement of the
non-FPC_TESTGENERICS TStringlist, that I would also be willing to
program and to submit a patch for it.
Just add a property OnSort of type TListSortCompare and always sort
using the user-provided function if the property is not nil. Automatic
sorting would only occur if sortstyle=sslauto, while the behaviour for
sortstyle=ssluser would remain as before for backward compatibility.
I don't see the value of this proposal.
Post by Franz Müller
Add a property OnSort of type TStringListSortCompare, which would allow
stringlists to be sorted not only by the value of the string, but also
by the value of the fields of the associated object. In that case it
would be necessary to add a new sortstyle sslobject, which would have to
be used when OnSort uses fields from the object for comparing, as in
this case the find method cannot use binary search for locating an item,
just like for unsorted stringlists (and the stringlist wouldn't know
otherwise that it can't use binary search).
I can understand an extension where you want to be able to sort on the value
of an associated object. But as you point out, the Find or IndexOf will then
become useless.

So the question then becomes whether you would not be better off with another
class altogether if you want such customized behaviour.

From what you describe, I think you should not be using TStrings (Or TStringList)
at all. TStrings is a very general-purpose class for use in a GUI, which
IMHO should not be burdened with additional highly specialized mechanisms.

Do not forget that TStringlist is just a possible implementation of
TStrings. You are free to create your own. For example, the inifiles unit has a
specialized version which is optimized for containing name=value pairs.

The generic lists from generics.collections, rtl-stl or even fgl seem more suitable
for what you describe.

Michael.
Andrea Mauri
2018-11-30 13:29:32 UTC
Permalink
Dear all,
if TStringList sort will be changed, please take into account the issue
related to randomised pivot initialisation in TStringList sort and the
consequences to Random sequence (
http://forum.lazarus-ide.org/index.php?topic=43257.0).

Andrea

Il giorno ven 30 nov 2018 alle ore 09:15 Michael Van Canneyt <
Post by Michael Van Canneyt
Post by Franz Müller
Hi everybody!
Currently, the implementation of cutomsorted stringlists ist very far
from satisfactory; you have to call the sort routine again whenever a
string is added to the stringlist or an item is changed, because the
stringlist cannot keep itself automatically sorted using a custom
compare function. There is a better implemetation using the
"experimental" define FPC_TESTGENERICS, but this code has not become
"mainstream" FPC for a long time now, and I feel that the use of
generics for the implementation of stringlists will also introduce quite
some unnecessary overhead.
The reason for not using the generic based version is that the generics code is slower.
Post by Franz Müller
I would like to propose one of two versions of improvement of the
non-FPC_TESTGENERICS TStringlist, that I would also be willing to
program and to submit a patch for it.
Just add a property OnSort of type TListSortCompare and always sort
using the user-provided function if the property is not nil. Automatic
sorting would only occur if sortstyle=sslauto, while the behaviour for
sortstyle=ssluser would remain as before for backward compatibility.
I don't see the value of this proposal.
Post by Franz Müller
Add a property OnSort of type TStringListSortCompare, which would allow
stringlists to be sorted not only by the value of the string, but also
by the value of the fields of the associated object. In that case it
would be necessary to add a new sortstyle sslobject, which would have to
be used when OnSort uses fields from the object for comparing, as in
this case the find method cannot use binary search for locating an item,
just like for unsorted stringlists (and the stringlist wouldn't know
otherwise that it can't use binary search).
I can understand an extension where you want to be able to sort on the value
of an associated object. But as you point out, the Find or IndexOf will then
become useless.
So the question then becomes whether you would not be better off with another
class altogether if you want such customized behaviour.
From what you describe, I think you should not be using TStrings (Or TStringList)
at all. TStrings is a very general-purpose class for use in a GUI, which
IMHO should not be burdened with additional highly specialized mechanisms.
Do not forget that TStringlist is just a possible implementation of
TStrings. You are free to create your own. For example, the inifiles unit has a
specialized version which is optimized for containing name=value pairs.
The generic lists from generics.collections, rtl-stl or even fgl seem more suitable
for what you describe.
Michael._______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Bart
2018-11-30 22:37:33 UTC
Permalink
if TStringList sort will be changed, please take into account the issue related to randomised pivot initialisation in TStringList sort and the consequences to Random sequence (http://forum.lazarus-ide.org/index.php?topic=43257.0).
https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot suggest to
either use a random value as pivot or the mean of the first, middle
and last element.

Bart
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinf
Tomas Hajny
2018-11-30 13:42:42 UTC
Permalink
Hello all,

Please note that the original poster (in Cc: of this e-mail) is not
subscribed to the list. I don't know if he has access to the list using
some other method, or whether he just forgot to mention that he wasn't
subscribed to the list in his message, but it might be better to include
him in Cc: of messages for this topic unless he states otherwise.

Tomas
(one of FPC mailing list moderators)


---------------------------- Original Message ----------------------------
Subject: Re: [fpc-devel] Stringlist customsort
From: "Andrea Mauri" <***@gmail.com>
Date: Fri, November 30, 2018 14:29
To: "FPC developers' list" <fpc-***@lists.freepascal.org>


Dear all,
if TStringList sort will be changed, please take into account the issue
related to randomised pivot initialisation in TStringList sort and the
consequences to Random sequence (
http://forum.lazarus-ide.org/index.php?topic=43257.0).

Andrea

Il giorno ven 30 nov 2018 alle ore 09:15 Michael Van Canneyt <
Post by Michael Van Canneyt
Post by Franz Müller
Hi everybody!
Currently, the implementation of cutomsorted stringlists ist very far
from satisfactory; you have to call the sort routine again whenever a
string is added to the stringlist or an item is changed, because the
stringlist cannot keep itself automatically sorted using a custom
compare function. There is a better implemetation using the
"experimental" define FPC_TESTGENERICS, but this code has not become
"mainstream" FPC for a long time now, and I feel that the use of
generics for the implementation of stringlists will also introduce quite
some unnecessary overhead.
The reason for not using the generic based version is that the generics
code is slower.
Post by Franz Müller
I would like to propose one of two versions of improvement of the
non-FPC_TESTGENERICS TStringlist, that I would also be willing to
program and to submit a patch for it.
Just add a property OnSort of type TListSortCompare and always sort
using the user-provided function if the property is not nil. Automatic
sorting would only occur if sortstyle=sslauto, while the behaviour for
sortstyle=ssluser would remain as before for backward compatibility.
I don't see the value of this proposal.
Post by Franz Müller
Add a property OnSort of type TStringListSortCompare, which would allow
stringlists to be sorted not only by the value of the string, but also
by the value of the fields of the associated object. In that case it
would be necessary to add a new sortstyle sslobject, which would have to
be used when OnSort uses fields from the object for comparing, as in
this case the find method cannot use binary search for locating an item,
just like for unsorted stringlists (and the stringlist wouldn't know
otherwise that it can't use binary search).
I can understand an extension where you want to be able to sort on the
value
of an associated object. But as you point out, the Find or IndexOf will
then
become useless.
So the question then becomes whether you would not be better off with
another
class altogether if you want such customized behaviour.
From what you describe, I think you should not be using TStrings (Or
TStringList)
at all. TStrings is a very general-purpose class for use in a GUI, which
IMHO should not be burdened with additional highly specialized mechanisms.
Do not forget that TStringlist is just a possible implementation of
TStrings. You are free to create your own. For example, the inifiles unit
has a
specialized version which is optimized for containing name=value pairs.
The generic lists from generics.collections, rtl-stl or even fgl seem more
suitable
for what you describe.
Michael.
Franz Müller
2018-11-30 12:53:18 UTC
Permalink
Post by Franz Müller
Hi everybody!
Currently, the implementation of cutomsorted stringlists ist very far
from satisfactory; you have to call the sort routine again whenever a
string is added to the stringlist or an item is changed, because the
stringlist cannot keep itself automatically sorted using a custom
compare function. There is a better implemetation using the
"experimental" define FPC_TESTGENERICS, but this code has not become
"mainstream" FPC for a long time now, and I feel that the use of
generics for the implementation of stringlists will also introduce
quite some unnecessary overhead.
The reason for not using the generic based version is that the generics
code is slower.

That is what I meant with unnecessary overhead
Post by Franz Müller
I would like to propose one of two versions of improvement of the
non-FPC_TESTGENERICS TStringlist, that I would also be willing to
program and to submit a patch for it.
Just add a property OnSort of type TListSortCompare and always sort
using the user-provided function if the property is not nil. Automatic
sorting would only occur if sortstyle=sslauto, while the behaviour for
sortstyle=ssluser would remain as before for backward compatibility.
I don't see the value of this proposal.

It would allow stringlists with a non standard sort order (for example
numeric sort instead of alphanumeric) to remain automatically sorted
when items are added or changed. But I also feel the second variation is
better.
Post by Franz Müller
Add a property OnSort of type TStringListSortCompare, which would
allow stringlists to be sorted not only by the value of the string,
but also by the value of the fields of the associated object. In that
case it would be necessary to add a new sortstyle sslobject, which
would have to be used when OnSort uses fields from the object for
comparing, as in this case the find method cannot use binary search
for locating an item, just like for unsorted stringlists (and the
stringlist wouldn't know otherwise that it can't use binary search).
I can understand an extension where you want to be able to sort on the
value
of an associated object. But as you point out, the Find or IndexOf will
then
become useless.

Useless? Why? Slower - yes. Don't matter with stringlists of a few dozen
up to a few hundred  items. If you have more data, maybe you need a
specialized class.


So the question then becomes whether you would not be better off with
another class altogether if you want such customized behaviour.

From what you describe, I think you should not be using TStrings (Or
TStringList) at all. TStrings is a very general-purpose class for use in
a GUI, which IMHO should not be burdened with additional highly
specialized mechanisms.

Take a simple example: Suppose you have a drop down box and want to keep
the 5 most recently used items in front, and all the other items sorted
alphabetically. With a custom sort which is not restricted to the string
values for sorting, you could do this easily by placing an additional
value for sorting in the object field. As the drop down box uses
TStrings, you are bound to use something like a stringlist.


Do not forget that TStringlist is just a possible implementation of
TStrings. You are free to create your own. For example, the inifiles
unit has a
specialized version which is optimized for containing name=value pairs.

Of course, everyone can create his own basic classes for everything, but
I think that is not how high level programming is supposed to work. The
improvement that I propose is 100% compatible with current code, if you
don' t need the feature (which will be the case most of the time), you
just don't use it, but if you need this added flexibility, it is there.
The implementation is very simple and no complexity is added for
programmers who don't need the feature.


Franz
Michael Van Canneyt
2018-12-01 08:09:30 UTC
Permalink
Post by Michael Van Canneyt
Do not forget that TStringlist is just a possible implementation of
TStrings. You are free to create your own. For example, the inifiles unit has
a
specialized version which is optimized for containing name=value pairs.
Of course, everyone can create his own basic classes for everything, but I
think that is not how high level programming is supposed to work. The
improvement that I propose is 100% compatible with current code, if you don'
t need the feature (which will be the case most of the time), you just don't
use it, but if you need this added flexibility, it is there. The
implementation is very simple and no complexity is added for programmers who
don't need the feature.
That sounds as if you have an implementation ready ?
If so, please submit a patch to the bugtracker. I'll evaluate it and if it
is indeed simple, as you claim, I will apply the patch.

Michael.
Franz Müller
2018-12-01 21:24:58 UTC
Permalink
Post by Michael Van Canneyt
That sounds as if you have an implementation ready ?
If so, please submit a patch to the bugtracker. I'll evaluate it and
if it
is indeed simple, as you claim, I will apply the patch.
Michael.
Havent programmed it yet, but I am going to do now. This is my first
contribution to the project, so most work for me will be to download
trunc, learn how create a patch etc.

The implemetation of the new feature should be rather simple. I will do
that and submit the patch to the bugtracker.

BTW.: @ Tomas Hyjny: What made you think that I am not subscribed to the
mailing list?


Franz


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepasc
Tomas Hajny
2018-12-02 10:02:09 UTC
Permalink
On Sat, December 1, 2018 22:24, Franz Müller wrote:
.
.
Post by Franz Müller
mailing list?
The fact that all your posts sent from the e-mail address used for sending
them (@focusdata.at) are held in the moderation queue waiting for approval
and marked as sent from an address not subscribed to the list in the list
moderation interface. ;-) Checking the list of members manually gives the
same result. Obviously, you may be subscribed using a different address,
there's no way for finding out that some other address among the many
subscribed ones belongs to you as well. Anyway, if this is the case, but
you prefer being able to send messages to the list using both addresses,
it's the best to subscribe both, but set one of them (whichever you like)
to non-delivery mode. Then your posts will be recognized as coming from
one of the list members and delivered without delays and you'll keep
receiving the messages only once and just to the address you choose.

Tomas


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://
Franz Müller
2018-12-02 13:56:51 UTC
Permalink
@Tomas Hajny

Ah - thank you. Very strange. I did not expect and did not notice that
when I click on "reply to list", the reply uses another mail address
than the one the mail was sent to.

Looks like an error of the thunderbird mailprogramm, I think replies
should always use the same mail address that the incoming mail used.
Anyway, I will try to take care that in the future I send my replies to
the list from my registered address.

Franz


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.free

Loading...