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 parent reply 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
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