www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Algorithms and slices

reply Mafi <mafi example.org> writes:
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.
Aug 26 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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?
Aug 26 2011
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Aug 26 2011
prev sibling next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 26.08.2011 22:24, 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.

I'd argue that functions in question should return slice if the input range is sliceable. IIRC they do this when possible e.g. as in find but not filter, am I missing something? --- Dmitry Olshansky
Aug 26 2011
prev sibling parent Ali =?iso-8859-1?q?=C7ehreli?= <acehreli yahoo.com> writes:
On Fri, 26 Aug 2011 20:24:43 +0200, 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[].

I have a feeling that std.range.inputRangeObject() will be helpful here. It provides a polymorphic interface to different types of ranges. It returns an InputRangeObject(R), but don't let its name give the wrong impression: it can be used as any non-OutputRange :), as long as the range R supports that interface. Say, the element type is int and the range is a ForwardRange. Then you can have ForwardRange!int r = inputRangeObject(my_range_returning_algo()); Or, when you don't need the ForwardRange functionality, you can specify another type on the left hand side: InputRange!int r = inputRangeObject(my_range_returning_algo()); (You must specify the type explicitly.) Then you can have arrays of interfaces to these actually unrelated ranges: InputRange!int[] my_input_ranges; my_input_ranges ~= inputRangeObject(foo_algo()); my_input_ranges ~= inputRangeObject(bar_algo()); (Not tested. Type casting may be needed on the right hand sides as well.) Ali
Aug 26 2011