contiguous ranges

[Pasqui23 via Digitalmars-d]

On Wednesday, 18 February 2015 at 08:34:49 UTC, Vlad Levenfeld 
wrote:
>
> I would argue that the only operations which preserve 
> contiguity are slicing, concatenating and appending; r.retro, 
> r.stride, r.map!f, etc should yield a RandomAccessRange.
>
> I don't think this is a deal breaker, as conceptually its akin 
> to losing random-accessiblity under a filtering or grouping. 
> Input ranges are ubiquitous, RandomAccessRanges are more rare, 
> and ContiguousRanges are rarer still. It stands to reason that 
> contiguity is unlikely to be preserved under a given 
> transformation.

No.The main strenght of the range api is its ability to preserve 
range categories.The loss of range categories is a *price* we pay 
for lazy  evalutation,categories wich can be restored by .array 
in exchange for the usual price for dynamic allocation.

>> This needs, however, a few more implementations that
>> motivate the concept.
>
> The main use cases I had in mind was for optimized data 
> transfers and passing arguments to C APIs, and in this regard 
> the definition of ContiguousRange would need a bit of 
> refinement, maybe like so:
>
>   A ContiguousRange r of type R is a RandomAccessRange which 
> satisfies hasLValueElements and defines a member called ptr 
> which satisfies the following conditions:
>
>     1) *r.ptr == r[0] && r.ptr == &r[0]
>     2) for all 0 <= i < r.length, *(r.ptr + i) == r[i] && r.ptr 
> + i == &r[i]
>
> We could then have:
>
>   void load_data (R)(R r) {
>     static if (isContiguousRange!R)
>       auto ptr = r.ptr;
>     else {
>       auto cache = r.array;
>       auto ptr = cache.ptr;
>     }
>
>     some_C_lib_call (r.length, ptr);
>   }
>
>   and
>
>   void copy (R,S)(R r, S s) if (allSatisfy!(isContiguousRange, 
> R, S)) {
>     // type and length equality assertions
>     vectorized_blit (ElementType!R.sizeof, r.length r.ptr, 
> s.ptr);
>   }
>
>  ---

You are on track when you say the main use case would be 
optimized data transfer and comunication with C.However you are 
describing ContiguousRange as
a type implicitly convertable to T[],wich I deem too 
restrictive.Optimized data transfers don't care at all that the 
bytes are in order,only that the data are in the slice you gave 
them.

Instead a contiguous range is one wich satisfies the following  
contract:

R r;
static assert(hasLValueElements!R && !isInfinite!R);
void[]s=r.toContiguous;
foreach(ref i;r)assert(s.ptr<=&i<s.ptr+s.lenght);

This allow,for example,to say:

void copy(R)(R r1,R r2)if(isContiguousRange!R){
   void[]s1=r1.toContiguous,s2=r2.toContiguous;
   memcpy(s1.ptr,s2.ptr,min(s1.lenght,s2.lenght);
}

It even give us a contiguous BinaryHeap,simply by

struct BinaryHeap(Store){
   ...
   private Store store;
   @propriety void[]toContiguous()if(isContiguousRange!Store){
     return store.toContiguous;
   }
}

and this BinaryHeap will be copied using only 1 call to memcpy.

> Extending the concept to multiple dimensions is thorny, but 
> then, I've found that the same is true for everything but 
> RandomAccessRanges.

My proposal allow simple extension to multiple dimension.
if  r is a n-dimensional range,then then the following must hold 
true:

void[]s=r.toContiguous;
foreach(i1;r)foreach(i2;i1)...foreach(in;inprev)
   assert(s.ptr<=&in<s.ptr+s.lenght);

On Tuesday, 17 February 2015 at 15:50:17 UTC, Andrei Alexandrescu 
wrote:
> for an array r, is r.retro contiguous or not?

I would say yes.In general,a good rule of thumb would be:this 
range can be copied via memcpy?Then preserve contiguous-ness.

For funcion accepting ranges ia a bit more complicated:
If the function cares that r[i]==*(s+i) then it should accept 
only T[]
else it should accept contiguous ranges.