www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4492] New: Version of take() which takes from the back of a range

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

           Summary: Version of take() which takes from the back of a range
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: jmdavisProg gmail.com



16:41:01 PDT ---
Most of the functions that we have in phobos at this point seem to deal with
the front of a range rather than the back. Naturally, for a lot of stuff,
that's exactly what you want, and there _are_ ranges which don't have a back,
but for some functions, it would be nice to have a corresponding function which
acts on the back of a range. The one which immediately comes to mind is take().
There's no way to take the back n elements of a range.

There are ways to get more or less the same thing - you can copy the range and
then pop off elements from the front - but there are situations where taking
from the back of a range would be useful. So, I suggest that std.range have a
function named takeBack() - or something similar - which does the same thing as
take() except that it takes from the back of the range rather than the front.

Now, there may be reasons which I haven't thought of why this wouldn't work
very well (unlike take(), it obviously wouldn't work with infinite ranges), but
I would think that it would be useful enough to at least look into adding it.

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


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dsimcha yahoo.com



What's wrong with just using take(retro(myRange), someNumber)?  This is only a
tiny bit more typing than takeBack and IIUC does exactly what you want.

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




17:39:34 PDT ---
You get the elements in the wrong order. Now, you could do

retro(take(retro(myRange), someNumber))

but that seems awfully inefficient, not to mention far more verbose than

takeBack(myRange, someNumber)

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




Two points:

1.  Retro is not inefficient.  For random access, there's the overhead of
translating the index to length - index, but this is negligible in most cases
(though I wouldn't use it in super performance critical numerics code).  In the
case of front(), popFront(), etc., all it does is forward front() to back(),
popFront() to popBack() and vice-versa.  These are virtually guaranteed to be
inlined by the compiler, resulting in truly zero overhead for non-random
access.

2.  Sorry for the misunderstanding on what you expected takeBack to do. 
However, now IIUC takeBack would be unimplementable on non-random access
ranges, unless the range had a length **and** you performed an O(n) seek.  If
you can only access the front and back element of a range at any given time,
you can't get the Nth element from the back.

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




19:57:42 PDT ---
Hmm. Well, it certainly _looks_ inefficient, but if it's not, all the better.
It would still be a bit ugly to have to code it that way though.

As for takeBack() being unimplementable... Couldn't popBack() be used to
construct a new range? Or does that not work? I haven't look at the source for
take(), but I would have half expected it to do something similar with
popFront(). What it is it about the back which would make it so much less
tractable than the front for non-random access ranges?

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


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy yahoo.com



07:50:51 PDT ---

 You get the elements in the wrong order. Now, you could do
 
 retro(take(retro(myRange), someNumber))
That won't work, retro needs a bidirectional range, and take is not a bidirectional range. Like David said, your takeBack will only work on random access ranges, an O(n) cost for constructing a range is unacceptable. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jul 22 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4492




10:33:10 PDT ---
Well, if it doesn't work, it doesn't work. It at least looks like it should
work, but I haven't gone into the guts of exactly what would be required for it
to work. And with pretty much the only ranges I've used thus far coming from
arrays or std.algorithm or std.range functions which have processed arrays, I'm
not particularly familiar with the restrictions of a given function and the
range types that it'll take (though presumably that will change as we get more
containers), so obviously I need to study up on those more. takeBack() would be
nice, but if it can't reasonably be done, then them's the breaks.

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




10:46:24 PDT ---
You might misunderstand what I was talking about.

I meant that specific example of a workaround won't work, not that you couldn't
implement takeBack.

As far as I know, the only restriction would be that the input would need to be
a random access range, so you could get the $-Nth element in O(1) time.

I'd probably call it something different however, like takeTail (or just tail),
since back implies you only want the back element, or are starting with the
back element.

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




10:55:26 PDT ---
Ah okay. I did misunderstand what you meant.

takeTail() probably would be a better name.

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


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei metalanguage.com



15:07:02 PDT ---
It looks like we're already in good shape to meet such a need. If popping
elements from the tail is needed, take(retro(range), n) should do. If getting
the last n elements from a range in the same order is needed,
range[range.length - n .. range.length] should do. I'll keep this open for a
bit more if something new shows up.

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




16:43:14 PDT ---
I wasn't aware that you could generally use subscripts on ranges such as

range[range.length - n .. range.length]

But I guess that it would make sense for random access ranges to have that, and
if you have to have a random access range to efficiently implement
takeBack()/takeTail() anyway, then you already have what you need. In that
case, the one argument that I'd make for takeTail() would be that it might be
better for generic code (it's also a bit cleaner to say takeTail(range, n)),
but if you're restricted to random access ranges for such code anyway, then it
probably doesn't really gain you anything since you can't really genericize
something that has to be specific.

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


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|nobody puremagic.com        |andrei metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 09 2011