www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8371] New: Add a function to make a range from a sequence of elements

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8371

           Summary: Add a function to make a range from a sequence of
                    elements
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: yebblies gmail.com
        ReportedBy: yebblies gmail.com



As mentioned on the newsgroup, it would be useful to have a function in phobos
that can turn a bunch of values into a value type range.  What you get when you
cross tuple and chain.

foreach(x; range(23, 7, 1990)) // No allocations, unlike array literals
{
}

It could be a random access range, with slicing.
There's probably not much point in it having assignable elements.
I'll do a pull request for std.range in the next few days.
Name suggested by Andrei.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 10 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8371


timon.gehr gmx.ch changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |timon.gehr gmx.ch



I think it should have assignable elements. It is trivial to support.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 10 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8371


Christophe Travert <christophe.travert normalesup.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |christophe.travert normales
                   |                            |up.org



2012-07-10 13:46:35 PDT ---
I'm not sure how should support slicing. The most economic way to implement
this range is to use a static array and an index indicated the next value.
Slicing this range would require either:
 - to store an extra index in the range... that would be sad IMHO, because it
is often not needed.
 - to return something else than a "range":
   - a struct containing the static array and the slice. That seems to be
overkill.
   - a dynamic array. Then the slice would not be a value type like the range
is.

The dynamic array option is the most reasonable to me.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 10 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8371






 I think it should have assignable elements. It is trivial to support.


It doesn't make much sense if it's a value type.

auto r = range(3, 2, 1);
sort(r);
// r is still 3, 2, 1

If you really want to use it like a static array you could just access the
content directly.  I dunno, being a value type makes this a weird thing.




 I'm not sure how should support slicing. The most economic way to implement
 this range is to use a static array and an index indicated the next value.
 Slicing this range would require either:
  - to store an extra index in the range... that would be sad IMHO, because it
 is often not needed.
  - to return something else than a "range":
    - a struct containing the static array and the slice. That seems to be
 overkill.
    - a dynamic array. Then the slice would not be a value type like the range
 is.
 
 The dynamic array option is the most reasonable to me.


It can't be random access without being bidirectional, and it can't be
bidirectional without having a start/end index.

struct Range(T, size_t N)
{
   T[N] data;
   size_t first, last;
   void popFront() { first++; }
   void popBack() { last--; }
    property T front() { return data[first]; }
    property T back() { return data[last-1]; }
    property bool empty() { return first >= last; }
   auto opIndex(size_t i) { return data[first+i]; }
   auto save() { return this; }
   auto opSlice() { return this; }
   auto opSlice(size_t lo, size_t hi) { return typeof(this)(data, first+lo,
first+hi); }
}

So if it's random access, it can support slicing.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 10 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8371




2012-07-11 00:47:45 PDT ---

 It can't be random access without being bidirectional


Shame...


 and it can't be bidirectional without having a start/end index.


I was about to mention that, in fact, it can have a slice operator and only one
start index, which moves the elements while copying them. In the same way, the
range can be bidirectional and have only one start index if it moves its
elements while poping back. I think such range with a small capacity should
have this behavior. No need to use 2 indices to build a 2-element range, and I
don't even talk about 0- and 1-element range. By the way, no need to copy the
whole data when slicing. Only the sliced part should be copied. The same is
valid for save.

It should be noted that such range with a large capacity does not fullfill the
complexity requirements: copy, save and opSlice are O(n). When opSlice is O(n),
in principle, it should not be provided. Algorithms would better not see an
O(n) opSlice, and use normal iteration instead. An opSlice returning a cheap
dynamic array may be proposed, but it can be dangerous, since the it will not
own its data.

In any case, the implementation should be tuned for small range, and the
documentation should explicitely mention the limits of this range with a large
capacity.

Finally, convenience function to build a range with a capacity that is larger
than the initial number of elements should be provided. For example:

// r can be initialized with 1 or 2 elements, but is the same type in both
cases
auto r = test? range(1, 2): range!2(1);


side note: 
While writing this example, I wanted to write "auto range = ...". But it is not
possible if the new range is called 'range'... In some place, the code of
std.range uses the token range (I found one in walklength). That would break if
the new range is called range. In many many places, the documentation of
std.range (and std.algorithm, and probably many other), use the word "range".
That would not block the compilation, but that would break the documentation in
many places. I think the new range should not be called range. I would propose
rangeOf. Or smallRange, to insist on the fact that the range is tuned for a
small capacity.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 11 2012