View mode: basic / threaded / horizontal-split · Log in · Help
June 26, 2012
Re: Get rid of isInfinite()?
On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:
> You could store those elements internally as you iterate over 
> them



That's *precisely* the point of my wrapper... sorry if that 
wasn't clear.

Why shouldn't that be sufficient for making it random-access?






> If you can somehow figure out how to do that via buffering, 
> then you could make it a forward range as well as whatever 
> other range types you could define the functions for, but you'd 
> have to figure out a way to define save.



OK, now we're at the same place. :P

What I'm saying is, I __CAN__ get the buffering to work.

What I __cannot__ figure out what to do with is 'length'... I 
can't think of anything reasonable to return, since it's not 
infinite (which I might represent as ulong.max, if anything) but 
it's unbounded.


So the _ONLY_ problem I'm running into right now is length() -- 
any ideas how I could fix that?
June 26, 2012
Re: Get rid of isInfinite()?
On Tuesday, June 26, 2012 05:40:10 Mehrdad wrote:
> On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:
> > You could store those elements internally as you iterate over
> > them
> 
> That's *precisely* the point of my wrapper... sorry if that
> wasn't clear.
> 
> Why shouldn't that be sufficient for making it random-access?
> 
> > If you can somehow figure out how to do that via buffering,
> > then you could make it a forward range as well as whatever
> > other range types you could define the functions for, but you'd
> > have to figure out a way to define save.
> 
> OK, now we're at the same place. :P
> 
> What I'm saying is, I __CAN__ get the buffering to work.
> 
> What I __cannot__ figure out what to do with is 'length'... I
> can't think of anything reasonable to return, since it's not
> infinite (which I might represent as ulong.max, if anything) but
> it's unbounded.
> 
> 
> So the _ONLY_ problem I'm running into right now is length() --
> any ideas how I could fix that?

If you can't calculate the length in O(1), then you're stuck using walkLength, 
which means iterating over the entire range to get its length. And if that's 
the case, then you can't make it a random access range, because for it to be a 
random access range, it either needs to have a length property (which must be 
O(1)) or be infinite. And I would fully expect for your code to run into a 
variety of bugs if you tried to claim that it was a length that it wasn't 
(e.g. ulong.max), since a number of functions will expect that that's its 
actual length and won't work properly if it's not.

For a range to be random access, it must fulfill these requirements:

template isRandomAccessRange(R)
{
   enum bool isRandomAccessRange = is(typeof(
   (inout int _dummy=0)
   {
       static assert(isBidirectionalRange!R ||
                     isForwardRange!R && isInfinite!R);
       R r = void;
       auto e = r[1];
       static assert(!isNarrowString!R);
       static assert(hasLength!R || isInfinite!R);
   }));
}

and I'm not sure that you can squeeze your range into that. You could do it if 
you just read in the entire range and created another range from it (be it an 
array or whatever), but you appear to be attempting something which probably 
won't quite work with the current range design. I suspect that you'd do better 
trying to claim that it wasn infinite rather than had a length, but then you'd 
have to be able to deal with the fact that empty is always false.

- Jonathan M Davis
June 26, 2012
Re: Get rid of isInfinite()?
On Tuesday, 26 June 2012 at 03:40:11 UTC, Mehrdad wrote:
> On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:
>> If you can somehow figure out how to do that via buffering, 
>> then you could make it a forward range as well as whatever 
>> other range types you could define the functions for, but 
>> you'd have to figure out a way to define save.
>
> OK, now we're at the same place. :P
>
> What I'm saying is, I __CAN__ get the buffering to work.
>
> What I __cannot__ figure out what to do with is 'length'... I 
> can't think of anything reasonable to return, since it's not 
> infinite (which I might represent as ulong.max, if anything) 
> but it's unbounded.
>
>
> So the _ONLY_ problem I'm running into right now is length() -- 
> any ideas how I could fix that?

You should decide what is length **conceptually** in your 
abstraction. In a similar situation I might want to create a 
forward range, and add indexing or slicing if they are needed. Or 
create a forward range of arrays, each representing a buffer. Or 
specify that semantically length is allowed to increase if some 
condition / predicate is true (the user might pass this predicate 
if needed).

There are many options possible, important is what use cases you 
target and what intuitive associations to already existing 
concepts you would like your users to apply.
June 26, 2012
Re: Get rid of isInfinite()?
On Tuesday, 26 June 2012 at 06:05:49 UTC, Jonathan M Davis wrote:
> If you can't calculate the length in O(1), then you're stuck 
> using walkLength,
> which means iterating over the entire range to get its length. 
> And if that's
> the case, then you can't make it a random access range, because 
> for it to be a
> random access range, it either needs to have a length property 
> (which must be
> O(1)) or be infinite. And I would fully expect for your code to 
> run into a
> variety of bugs if you tried to claim that it was a length that 
> it wasn't
> (e.g. ulong.max), since a number of functions will expect that 
> that's its
> actual length and won't work properly if it's not.
>
> For a range to be random access, it must fulfill these 
> requirements:
>
> template isRandomAccessRange(R)
> {
>     enum bool isRandomAccessRange = is(typeof(
>     (inout int _dummy=0)
>     {
>         static assert(isBidirectionalRange!R ||
>                       isForwardRange!R && isInfinite!R);
>         R r = void;
>         auto e = r[1];
>         static assert(!isNarrowString!R);
>         static assert(hasLength!R || isInfinite!R);
>     }));
> }
>
> and I'm not sure that you can squeeze your range into that. You 
> could do it if
> you just read in the entire range and created another range 
> from it (be it an
> array or whatever), but you appear to be attempting something 
> which probably
> won't quite work with the current range design. I suspect that 
> you'd do better
> trying to claim that it wasn infinite rather than had a length, 
> but then you'd
> have to be able to deal with the fact that empty is always 
> false.
>
> - Jonathan M Davis

I actually only needed length() because random access ranges 
required it (not because I did), but maybe I can avoid it some 
way without using random access ranges at all... I'll try to 
rework stuff. Thanks for the explanations.
June 26, 2012
Re: Get rid of isInfinite()?
"Mehrdad" , dans le message (digitalmars.D:170697), a écrit :
> On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:
>> You could store those elements internally as you iterate over 
>> them
> 
> That's *precisely* the point of my wrapper... sorry if that 
> wasn't clear.
> 
> Why shouldn't that be sufficient for making it random-access?
> 
> 
>> If you can somehow figure out how to do that via buffering, 
>> then you could make it a forward range as well as whatever 
>> other range types you could define the functions for, but you'd 
>> have to figure out a way to define save.
> 
> 
> 
> OK, now we're at the same place. :P
> 
> What I'm saying is, I __CAN__ get the buffering to work.
> 
> What I __cannot__ figure out what to do with is 'length'... I 
> can't think of anything reasonable to return, since it's not 
> infinite (which I might represent as ulong.max, if anything) but 
> it's unbounded.
> 
> 
> So the _ONLY_ problem I'm running into right now is length() -- 
> any ideas how I could fix that?

I you are planning to buffer all input as you read it to enable 
random-access, then you should better read the whole file in your buffer 
from the start and get done with it, since you will end up having read 
the whole file in the buffer at the end...

-- 
Christophe
June 26, 2012
Re: Get rid of isInfinite()?
Christophe Travert, dans le message (digitalmars.D:170706), a écrit :
> "Mehrdad" , dans le message (digitalmars.D:170697), a écrit :
>> On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:
>>> You could store those elements internally as you iterate over 
>>> them
>> 
>> That's *precisely* the point of my wrapper... sorry if that 
>> wasn't clear.
>> 
>> Why shouldn't that be sufficient for making it random-access?
>> 
>> 
>>> If you can somehow figure out how to do that via buffering, 
>>> then you could make it a forward range as well as whatever 
>>> other range types you could define the functions for, but you'd 
>>> have to figure out a way to define save.
>> 
>> 
>> 
>> OK, now we're at the same place. :P
>> 
>> What I'm saying is, I __CAN__ get the buffering to work.
>> 
>> What I __cannot__ figure out what to do with is 'length'... I 
>> can't think of anything reasonable to return, since it's not 
>> infinite (which I might represent as ulong.max, if anything) but 
>> it's unbounded.
>> 
>> 
>> So the _ONLY_ problem I'm running into right now is length() -- 
>> any ideas how I could fix that?
> 
> I you are planning to buffer all input as you read it to enable 
> random-access, then you should better read the whole file in your buffer 
> from the start and get done with it, since you will end up having read 
> the whole file in the buffer at the end...
> 

Hum, sorry, that is irrelevant if your input is not a file.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home