On Wednesday, 13 July 2022 at 22:35:35 UTC, D Lark wrote:
On Wednesday, 13 July 2022 at 18:27:22 UTC, D Lark wrote:
I am trying to use a sequence range as a sorted range so that
I can apply a search on it. For instance this might be used to
implement integer square root as so:
[...]
For the first snippet, I did not get to that point, but it
appears I would have to add a search policy to lower bound
since the list is infinite and the default policy, binary
search, requires both initial bounds. i.e:
auto lowerBounds =
seqAsSorted.lowerBound!(SearchPolicy.gallop)(n);
Actually looking at the implementation of `lowerBound` it seems
that search generally is not supported for infinite ranges as
irrespective of the overload chosen via the search policy, we
still explicitly depend on `length` which is obviously not
defined for infinite ranges.
I guess that leads to the question (probably already covered
indirectly in my initial questions):
Is `SortedRange` intended to be used with infinite ranges?
It would seem that the search policies `trot` and `gallop` are
theoretically compatible with infinite ranges, but they have been
specifically implemented to depend on length.
I note that only the binary search policy overload of
`getTransitionIndex` explicitly requires the existence of a
member `length` which is consistent with my conceptual
expectation, but all the overloads actually depend on it in the
implementation.
