Should we just redefine random access ranges such that they must either have a length or be infinite?  I'm trying to improve the unit tests in std.range in preparation for some bug fixing and consistency improvements and I'm finding the mother lode of bugs in the process (which I'll file or fix relatively soon).  I basically made a dummy range template, made a tuple of instantiations with every combination of (ref, non-ref returns), (length, no length) and (input, forward, bidirectional, random access) and tried to instantiate the higher order ranges with every one of these that made sense.  One recurring theme is that the case of a random access range that isn't infinite and doesn't have a length is not properly dealt with.

Since I can't imagine how a range could offer O(1) random access w/o either knowing its length or being infinite, I suggest we just add this requirement to the definition of a random access range and be done with it.  Counterexamples?

On 06/23/2010 10:22 PM, David Simcha wrote:
> Should we just redefine random access ranges such that they must either have a length or be infinite?

I think that's reasonable. If a finite range didn't define length, it would be easy to find it in O(log n) by binary search.

> I'm trying to improve the unit tests in
> std.range in preparation for some bug fixing and consistency
> improvements and I'm finding the mother lode of bugs in the process
> (which I'll file or fix relatively soon).

Congrats to you and everybody else for the great work. Phobos is really starting to come together.


Andrei

On 6/23/2010 11:36 PM, Andrei Alexandrescu wrote:
> On 06/23/2010 10:22 PM, David Simcha wrote:
>> Should we just redefine random access ranges such that they must either have a length or be infinite?
>
> I think that's reasonable. If a finite range didn't define length, it would be easy to find it in O(log n) by binary search.
I guess you're assuming some method of signaling on out of bounds access, such as throwing an exception?

On 06/23/2010 10:42 PM, David Simcha wrote:
> On 6/23/2010 11:36 PM, Andrei Alexandrescu wrote:
>> On 06/23/2010 10:22 PM, David Simcha wrote:
>>> Should we just redefine random access ranges such that they must either have a length or be infinite?
>>
>> I think that's reasonable. If a finite range didn't define length, it would be easy to find it in O(log n) by binary search.
> I guess you're assuming some method of signaling on out of bounds access, such as throwing an exception?

Yah. What I'm basically saying is, if you can decide in O(1) what element at position n is, there's no way you can't write (inside the range) some sort of a test that gives you the length in logarithmic time. A range can't be at the same time random-access, finite, and unable to figure its bounds. Or so I believe :o).

Andrei