Algorithms and slices

Jonathan M Davis jmdavisProg at gmx.com
Fri Aug 26 13:45:03 PDT 2011


On Friday, August 26, 2011 11:49 Timon Gehr wrote:
> On 08/26/2011 08:24 PM, Mafi wrote:
> > The algorithms in std.algorithm are great. They operate the same on
> > arrays/slices and generic ranges. But they return their own range-types.
> > Often this ok but sometimes you need a T[]. You may say to just use
> > array() but this allocates a new array! I think you sometimes want to
> > get a slice to the original array. I wrote this function. It checks if
> > it is ok what it is doing at runtime.
> > 
> > ////////////
> > import std.stdio, std.algorithm, std.range, std.conv, std.exception;
> > 
> > void main() {
> > auto x = [0, 1, 2, 3, 4, 5];
> > auto t = x.take(3);
> > foreach(i, ref elem; t) {
> > writefln("%s : %s (%s)", i, elem, &elem);
> > }
> > foreach(i, ref elem; array(t)) {
> > writefln("%s : %s (%s)", i, elem, &elem);
> > }
> > foreach(i, ref elem; slice(t)) {
> > writefln("%s : %s (%s)", i, elem, &elem);
> > }
> > }
> > 
> > /**
> > Retuns a slices of the data the given range represents.
> > 
> > throws: ConvException if the data is not continous.
> > *
> > ElementType!(R)[] slice(R)(R range) if(isInputRange!R) {
> > alias ElementType!(R) E;
> > E* addr = null;
> > size_t length = 0;
> > foreach(i, ref e; range) {
> > static assert(is(typeof(e) == E));
> > 
> > if(addr is null) {
> > addr = &e;
> > } else {
> > enforce(&e is (addr + i), new ConvException("Could not create a
> > continous slice."));
> > }
> > 
> > length++;
> > assert(i == length-1);
> > }
> > if (addr is null) return null;
> > else return addr[0.. length];
> > }
> > //////////////
> > 
> > Is there functinality like this in phobos? Does such a function fit into
> > the range world.
> 
> That exposes the implementation details of all range-based functions.
> Are there even any range types in Phobos that do save their elements in
> a continuous array?

No. I believe that the only ranges which have an array underneath are arrays 
and std.container.Array's range type. Phobos' range-based functions either 
return the range type that it was given or a wrapper around that type (and the 
range which was passed to it could already have been a wrapper around another 
range). If a range-based function can return the original range type, then it 
does (generally - if not always - because the range was sliceable). Otherwise, 
you get a wrapper. Almost by definition, the fact that the range returned from 
a range-based function is not the same type as the range passed in means that 
the result is not a contiguous sub-range of the range which was passed in. 
There are a few cases where you end up with a contiguous range which can't be 
a slice, but they're all lazy ranges (e.g. until). And if you really want to 
have a slice in that sort of situation, then you can just take the length of 
the resultant lazy range and then take a slice of that length from the 
beginning of the original range. e.g.

static assert(isSliceable!(typeof(range)));
auto slice = range[0 .. walkLength(until(range, delimiter))];

That won't work with strings, but neither will the proposed function. For 
strings, you'd have to do something like

static assert(isSomeString!(typeof(range)));
auto slice = range[0 .. toUCSindex(walkLength(until(range, delimiter)))];

So, even if it works, I don't think that the proposed function buys us 
anything.

- Jonathan M Davis


More information about the Digitalmars-d mailing list