std.algorithm imporvments

monarch_dodra monarchdodra at gmail.com
Mon Jul 16 03:43:10 PDT 2012


I had a discussion recently about the proper use of "save" when 
passing to foreach or algorithms, as well as read the thread 
about algorithms being hard to use. It was concluded this the 
problem mostly came from:
a) Lack of proper testing.
b) Missing or inaccurate input type checking.

I decided to donate some of my time to investigate and improve on 
both these points.

Here is what I found:

*"Save" issues:
*"minPos". Atsolutly no backup is ever made, and this method will 
return an empty range ALL the time.
*"fill(Range1, Range2)". Save occurs only once, but not within 
loop body. An out of range exception occurs should Range1.length 
 > 2* Range2.length.

*"No specifier" issues:
*The following algorithms do not validate the type of their 
ranges:
**"minPos": Should be "isInputRange".
**"skipOver": Should be "isInputRange".

*"isForwardRange" could be "isInputRange" issues:
**"countUntil".

Also, the functions:
*"fill(Range, Value)"
*"uninitializedFill(Range, Value)"
*"fill(Range1, Range2)"
*"initializeAll(Range)"
*"moveAll(Range1, Range2)"
*"moveSome(Range1, Range2)"
*"swapFront(R1, R2)"

For some reason, the output ranges (Range/Range2/R2) for all the 
above functions are defined as needing "isInputRange", when it 
should really be "isOutputRange" (or Forward range for 
uninitializedFill/initializeAll ?)

Finally: "fill(Range1, Range2)" requires "Range1" to be a forward 
range, so that it can be repeated. However, if Range1 
hasInfinity, then only isInputRange is needed.

----
I did not go much more in depth, but I think it may be a good 
starting point? I apologize if I gave any false positives. Would 
this be something I should fix myself?

----
Something else I noticed it that even the most basic algorithms 
seem to go out of their way to avoid using "foreach". For 
example, "count", "equal", "minCount", "minPos". etc. Doing this 
potentially short-circuits any call to opApply if that range 
defines it.


More information about the Digitalmars-d mailing list