www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Definition of "OutputRange" insuficient

reply "monarch_dodra" <monarchdodra gmail.com> writes:
I was trying to fix a few bugs in algorithm, as well as be more 
correct in template type specifiers, and I have to say: There is 
a serious restraint in the definition of an outputRange.

The current definition of "isOutputRange" is simply that "an 
output range is defined functionally as a range that supports the 
operation put".

The problem with this is this definition is not very useful (at 
all). Not just because it lacks front/popFront (this is actually 
OK). It is because it lacks an "empty". This makes it virtually 
un-useable unless you are blind writing to an infinite output 
range.

The proof that it is useless is that NOT A SINGLE ALGORITHM is 
compatible with output ranges. All algorithms that really only 
require an "output" systematically actually require 
"isForwardRange", or, worse yet "isInputRange" (!). This is only 
because they all make use of range.empty.

Here is an example of me trying to write "fill" respecting output 
range restrictions.

----
void fill(Range1, Range2)(Range1 range, Range2 filler)
     if (isOutputRange!(Range1, ElementType!Range2) && 
isForwardRange!Range2)
{
     enforce(!filler.empty);
     auto t = filler.save;
     while (!range.empty) //Crud...
     {
         if (t.empty) t = filler.save;
         put(range, t.front);
         t.popFront();
     }
}
----
Almost... but no cookie.

If the argument against this is "but the output range "can't know 
if it empty"/"may never be empty", then is why we have an 
"isInfinite" definition... isn't it?

On the same note, why is the definitions of "inputRange" so 
divergent from outputRange. Shouldn't inputRange's definition 
mirror output's and be "supports get" (and "is empty")?

Shouldn't a correct "front/popFront" _only_ be required once we 
reach "forwardRange" and it's ability to save?

Here is an example of an implementation of fill, that only 
requires the filler to be an input range, if it has infinity.
----
void fill(Range1, Range2)(Range1 range, Range2 filler)
     if (isOutputRange!(Range1, ElementType!Range2) && 
isInputRange!Range2
         && isInfinite!Range2)
{
     while( !range.empty )
     {
         put(range, get(filler));
     }
}
----

The current definition makes anything like near impossible.
Jul 17 2012
next sibling parent travert phare.normalesup.org (Christophe Travert) writes:
"monarch_dodra" , dans le message (digitalmars.D:172586), a écrit :
 I was trying to fix a few bugs in algorithm, as well as be more 
 correct in template type specifiers, and I have to say: There is 
 a serious restraint in the definition of an outputRange.
 
 The current definition of "isOutputRange" is simply that "an 
 output range is defined functionally as a range that supports the 
 operation put".
 
 The problem with this is this definition is not very useful (at 
 all). Not just because it lacks front/popFront (this is actually 
 OK). It is because it lacks an "empty". This makes it virtually 
 un-useable unless you are blind writing to an infinite output 
 range.
 
 The proof that it is useless is that NOT A SINGLE ALGORITHM is 
 compatible with output ranges. All algorithms that really only 
 require an "output" systematically actually require 
 "isForwardRange", or, worse yet "isInputRange" (!). This is only 
 because they all make use of range.empty.

OutputRange is designed for infinite output ranges, like output files and appender. Copy is the only algorithm that uses OutputRange. But still, this is enough. That enables to do a lot of things, since copy can branch to any lazy input range performing all the generic operation you want*. However, output range with a limited capacity are not taken into account. They are partly covered by the input ranges family. Most ranges that are output ranges with a capacity are also input ranges. Arguably, we may want to cover output ranges with capacity that are not input range. This would may make fill cleaner. uninitializedFill would be fill with an output range that does not defines a front method, which would be much cleaner than using emplace arbitrarily on a range that is not designed for that. This also opens the door to an algorithm that copy a input range into an output range, but stops when the output range is full of the input range is empty, and return both filled output range and consumed input range (the input range could be taken by ref). Copy could be improved with an additional "StopPolicy" template argument. To do this, two methods could be added to output ranges, one telling if the range is full, and one telling what is the remaining capacity of the range (capacity already has a meaning, some other word should be used). These methods are like empty and length. -- Christophe Out of topic foot note: * After thoughts, one thing you can't do directly in phobos is to modify an output range to return a new output range. You are obliged to apply the operation on the input range. For example: input.map!toString().copy(output); can't be written: input.copy(output.preMap!toString()); Creating a modified output range like my (badly named) output.preMap can be useful, but may be to marginal to be put in Phobos. With a revamped stdio using more ranges, this may become less marginal. map, joiner, filter, chain, take and friends, zip and chunks may have a meaning for output range with capacity...
Jul 17 2012
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/17/12 6:44 AM, monarch_dodra wrote:
 I was trying to fix a few bugs in algorithm, as well as be more correct
 in template type specifiers, and I have to say: There is a serious
 restraint in the definition of an outputRange.

 The current definition of "isOutputRange" is simply that "an output
 range is defined functionally as a range that supports the operation put".

Actually if you look at put() it's designed to accept an input range with assignable elements, in which case it assigns to the front and moves forward. But I agree we could improve output ranges with a notion of "full". The paradox is, for an input range used for output, "full" is a synonym for "empty" :o). Andrei
Jul 17 2012
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
 OutputRange is designed for infinite output ranges, like output 
 files and appender.

 [snip]

Well, "designed" is open for interpretation. Yes, all (most) "ranges defined as output" (files, streams, appenders) are infinite, and don't define empty (or define it as false). But that does not mean that all ranges that fulfill "isOutputRange" are infinite. By leaving out the "empty" requirement from output range, we are forcing the infinity concept on anything that wishes to use the output facilities of a range. On Tuesday, 17 July 2012 at 14:53:00 UTC, Andrei Alexandrescu wrote:
 Actually if you look at put() it's designed to accept an input 
 range with assignable elements, in which case it assigns to the 
 front and moves forward. But I agree we could improve output 
 ranges with a notion of "full". The paradox is, for an input 
 range used for output, "full" is a synonym for "empty" :o).

 Andrei

Well, the "underlying" container being full makes the range empty. I don't really see how we could have a notion of a "full range". But I'll admit the contrast if funny to observe :D Regarding put, I noticed that actually. I was going to propose using it in "copy", as it could probably improve performance in the "generic case" (that, and it is _meant_ to be used that way). Right now, it defines a "genericImplementation" as: -------- static Range2 genericImpl(Range1 source, Range2 target) { for (; !source.empty; source.popFront()) { put(target, source.front); } return target; } -------- which should really just be -------- static Range2 genericImpl(Range1 source, Range2 target) { put(target, source); return target; } -------- In the case of "fill" is that "put" will throw an exception if source does fit into target. There is no real way to know this before hand either, and it is not possible to just insert until full: That is the entire problem. An easy fix at this point would be to just provide "hasEmpty", no? After all, we have "hasLength". That said, I feel this is more a bandage, and that outputRange really should define empty. -------- On a same note, I just noticed that "forwardRange" does not have to adhere to the "outputRange" concept. This is in stark opposition to the classification in C++. Is this on purpose? I took it for granted that "forward" meant "output"+"input"+"save", but it is really just "input"+"save". In theory, this means that the only "safe" way to write to a range would be to use "put". There is a "hasAssignableElements" trait, but the requirements are odd: 1) It requires the range to be at least "forward", meaning an inputRange or an outputRange (!) will fail the "hasAssignableElements" test. 2) It only checks that "front" is assignable, so that does not guarantee you can assign to the indexes of a RandomAccess range :/
Jul 17 2012