Using Sequence Range as a SortedRange.

[D Lark]

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.