[fpc-devel] Fwd: Re: fpc-devel Digest, Vol 175, Issue 29

[Franz Müller]

Hi,

I have finished work on the improved stringlist. There are few changes 
in the public section:  A new public property OnCompareItems: 
TStringListSortCompare allows to define the compare function, while 
keeping sslAuto as sortstyle. If OnCompareItems uses data from the 
object instead of or in addition to the string itself for sorting, the 
new public boolean property ObjectSort must be set to true; in that 
case, the function Indexof will work like for unsorted strings. Finally, 
the find method can be called with an additional object as parameter, to 
allow finding of string-object combinations through binary search. I 
made a few minor improvements, too, so there is no speed penalty for the 
increased flexibiity.

But before finalizing the patch and submitting it to the bugtracker, I 
have some questions.

1. It is not allowed to change an element of a sorted stringlist or 
insert a new string at some specific index. If that happens, 
SSortedListError is signaled. Shouldn't that also be the case when 
ExchangeItems is called on a sorted stringlist? I suggest adding the 
error message there too.

2. Eventually, I can also address the randomization problem by making a 
non-random choice of the Pivot Element according to

/On Fri, Nov 30, 2018 at 2:29 PM Andrea Mauri //<andrea.mauri.75 at gmail.com>//wrote: /

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

/On Fri, Nov 30, 2018 at 2:29 PM Andrea Mauri //<andrea.mauri.75 at gmail.com>//wrote: /

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

However, I am sceptical whether that would be worth the overhead - 
whatever the overhead is, because it is absolutely unclear to me what is 
meant with "the mean of the first, middle and last element". You can 
caculate the mean for numbers, but not for strings. So I would rather 
leave these things as they are now.

But maybe there is an easy way to save the state of the random number 
generator routine before sorting and to restore it when the sort is done?

3. The documentation should be updated. Is there a documentation about 
how to proceed to update the documentation for a class? There are a lot 
of different places with descriptions and explanations, I have no idea 
what to update and how to do that.

4. Are there test cases to validate the new stringlist, to make sure no 
existing code is broken? I have tested everything I could think of, but 
there may be constellations that I don't imagine. As stringlists have 
certainly been thoroughly tested when they were first written, there may 
already exist some "test suite" to test the behaviour. That would be 
very helpful and I would be glad to run additional tests before 
submitting the patch.

Franz
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20181222/d9225da6/attachment.html>