www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Isn't using find with retro awkward?

reply Andrej Mitrovic <none none.none> writes:
import std.stdio, std.algorithm, std.range;

void main()
{
    writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
    writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
}

Output:
[5, 1, 2, 3, 4, 5, 1]
[5, 4, 3, 2, 1, 5]

The docs for find are:
"returns : haystack advanced such that binaryFun!pred(haystack.front, needle)
is true "
"To find the last occurence of needle in haystack, call find(retro(haystack),
needle). "

To me, if I was looking for the last element in a range I would expect to get a
range with the found element followed by an elements after it. Obviously retro
reverses the range (it just hard-wires front=back, back=front for those not in
the know), so this code is correct.

Still, I would expect that finding a last element in this range:
[5, 1, 2, 3, 4, 5, 1]

would return the range:
[5, 1]

and not:
[5, 4, 3, 2, 1, 5]

Isn't that what most people would want when they're looking for the last
matching element?
Feb 14 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 14 February 2011 19:35:21 Andrej Mitrovic wrote:
 import std.stdio, std.algorithm, std.range;
 
 void main()
 {
     writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
     writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }
 
 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]
 
 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front,
 needle) is true " "To find the last occurence of needle in haystack, call
 find(retro(haystack), needle). "
 
 To me, if I was looking for the last element in a range I would expect to
 get a range with the found element followed by an elements after it.
 Obviously retro reverses the range (it just hard-wires front=back,
 back=front for those not in the know), so this code is correct.
 
 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]
 
 would return the range:
 [5, 1]
 
 and not:
 [5, 4, 3, 2, 1, 5]
 
 Isn't that what most people would want when they're looking for the last
 matching element?

retro revereses the whole range. What you want is something like findFromBack. Of course, retro isn't going to be what you want (though I guess I can understand why you would think that it would work if you didn't think it through). I don't think that we have any functions like findFromBack though. It's probably worth an enhancement request. - Jonathan M Davis
Feb 14 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/15/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:
 retro revereses the whole range. What you want is something like
 findFromBack.
 I don't think that we have any functions like findFromBack though. It's
 probably
 worth an enhancement request.

std.string had a find and rfind, both of which are deprecated now (although we can still use indexOf & lastIndexOf). So std.algorithm.find will take its place, but there's no rFind. There's retro(). So I suppose rFind or lastFind would fit as a name if there's a use case for this. The problem is, there's 7 find templates in std.algorithm. I think making another 7 templates for lastFind would be too much work without a valid use case. It's much more than just replacing popBack and back calls to popFront and front, from what I can tell. Anyway, I'm posting this since I don't know if a reversed range is what most people want. It seems kind of strange to me to use retro to find a last match and then get a reversed range back, but maybe that's just me? I'd like to hear from people who've used find with retro - if so did the reversed range and its length make sense to them or not? Using retro with a string doesn't make sense since that will reverse the string and you won't match with your needle. It won't compile either, but maybe that is a bug with retro or find. Here's what I mean: import std.string : indexOf, lastIndexOf; import std.algorithm; import std.range; void main() { string mystring = "foo bar doo bar yaz"; auto leftIndex = indexOf(mystring, "bar"); assert(mystring[leftIndex .. $] == "bar doo bar yaz"); auto rightIndex = lastIndexOf(mystring, "bar"); assert(mystring[rightIndex .. $] == "bar yaz"); // now the std.algorithm.find case: auto firstRange = find(mystring, "bar"); assert(firstRange == "bar doo bar yaz"); // will never match, since retro reverses the string. // but it also errors out auto lastRange = find(retro(mystring), "bar"); assert(firstRange == "bar yaz"); } D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2403): Error: variable std.algorithm.simpleMindedFind!(pred,Retro!(string),string).simpleMindedFind.estimatedNeedleLength cannot modify immutable D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2216): Error: template instance std.algorithm.simpleMindedFind!(pred,Retro!(string),string) error instantiating stringFind2.d(20): instantiated from here: find!("a == b",Retro!(string),string) stringFind2.d(20): Error: template instance std.algorithm.find!("a == b",Retro!(string),string) error instantiating Also, std.string.indexOf conflicts with std.algorithm.indexOf, but I think some of these functions are getting fixed for the next release (IIRC there was a thread about it). Now, how would you easily get a range back so that: find("foo bar doo bar", "bar") == "bar doo bar" and: lastFind("foo bar doo bar", "bar") == "bar" without using a specialized version of find, in this case lastFind?
Feb 14 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 14 February 2011 20:40:02 Andrej Mitrovic wrote:
 On 2/15/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:
 retro revereses the whole range. What you want is something like
 findFromBack.
 I don't think that we have any functions like findFromBack though. It's
 probably
 worth an enhancement request.

std.string had a find and rfind, both of which are deprecated now (although we can still use indexOf & lastIndexOf). So std.algorithm.find will take its place, but there's no rFind. There's retro(). So I suppose rFind or lastFind would fit as a name if there's a use case for this. The problem is, there's 7 find templates in std.algorithm. I think making another 7 templates for lastFind would be too much work without a valid use case. It's much more than just replacing popBack and back calls to popFront and front, from what I can tell. Anyway, I'm posting this since I don't know if a reversed range is what most people want. It seems kind of strange to me to use retro to find a last match and then get a reversed range back, but maybe that's just me? I'd like to hear from people who've used find with retro - if so did the reversed range and its length make sense to them or not? Using retro with a string doesn't make sense since that will reverse the string and you won't match with your needle. It won't compile either, but maybe that is a bug with retro or find. Here's what I mean: import std.string : indexOf, lastIndexOf; import std.algorithm; import std.range; void main() { string mystring = "foo bar doo bar yaz"; auto leftIndex = indexOf(mystring, "bar"); assert(mystring[leftIndex .. $] == "bar doo bar yaz"); auto rightIndex = lastIndexOf(mystring, "bar"); assert(mystring[rightIndex .. $] == "bar yaz"); // now the std.algorithm.find case: auto firstRange = find(mystring, "bar"); assert(firstRange == "bar doo bar yaz"); // will never match, since retro reverses the string. // but it also errors out auto lastRange = find(retro(mystring), "bar"); assert(firstRange == "bar yaz"); } D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2403): Error: variable std.algorithm.simpleMindedFind!(pred,Retro!(string),string).simpleMindedFi nd.estimatedNeedleLength cannot modify immutable D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2216): Error: template instance std.algorithm.simpleMindedFind!(pred,Retro!(string),string) error instantiating stringFind2.d(20): instantiated from here: find!("a == b",Retro!(string),string) stringFind2.d(20): Error: template instance std.algorithm.find!("a == b",Retro!(string),string) error instantiating Also, std.string.indexOf conflicts with std.algorithm.indexOf, but I think some of these functions are getting fixed for the next release (IIRC there was a thread about it). Now, how would you easily get a range back so that: find("foo bar doo bar", "bar") == "bar doo bar" and: lastFind("foo bar doo bar", "bar") == "bar" without using a specialized version of find, in this case lastFind?

Of _course_ you get a reversed range back. You _reversed the range_. That's what retro _does_. If you use it with find, of _course_ you're going to get a reversed range back. Complaining about that is like complaining that your range is sorted after you sorted it. It did exactly what it's supposed to do. If we don't have an rFind, we should add one. If that means matching all of the versions of find, then so be it. On the bright side, the documentation for them would be simple, because they could pretty much refer to find and say that they're doing the same thing except from the back. A good rfFnd algorithm would not use retro at all. You could probably get away with using retro on both the haystack and the needle and then retro again on the result of find, but I'd have to test it to be sure (I _think_ that my logic is correct on that, but I'm not 100% certain). Really, we should have an rFind. It's probably missing because it's not useful as often as find is, but it would be perfectly normal (and likely expected) that if we have a find, we have an rFind. - Jonathan M Davis
Feb 14 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/15/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:
 Of _course_ you get a reversed range back. You _reversed the range_. That's
 what
 retro _does_. If you use it with find, of _course_ you're going to get a
 reversed
 range back. Complaining about that is like complaining that your range is
 sorted
 after you sorted it. It did exactly what it's supposed to do.

You're not reading my posts properly. I /know/ that. That's why I've put a comment there that using retro doesn't make sense. Sheesh! My concern is that in the documentation it states "if you want to find the last match use retro". I believe this can bite newcommers to D if they don't know the fact that they'll get back a reversed range. It just says "use retro", it doesn't mention what retro does. It does link to it, that's okay, but will people read the retro documentation or will they just jump to conclusions and think retro does its magic and find just returns a range as usual? Regardless of that documentation, I'm thinking lastFind might be of use. But I'd like to hear more opinions before I blindly open a feature request.
Feb 14 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 14 February 2011 21:14:18 Andrej Mitrovic wrote:
 On 2/15/11, Jonathan M Davis <jmdavisProg gmx.com> wrote:
 Of _course_ you get a reversed range back. You _reversed the range_.
 That's what
 retro _does_. If you use it with find, of _course_ you're going to get a
 reversed
 range back. Complaining about that is like complaining that your range is
 sorted
 after you sorted it. It did exactly what it's supposed to do.

You're not reading my posts properly. I /know/ that. That's why I've put a comment there that using retro doesn't make sense. Sheesh! My concern is that in the documentation it states "if you want to find the last match use retro". I believe this can bite newcommers to D if they don't know the fact that they'll get back a reversed range. It just says "use retro", it doesn't mention what retro does. It does link to it, that's okay, but will people read the retro documentation or will they just jump to conclusions and think retro does its magic and find just returns a range as usual? Regardless of that documentation, I'm thinking lastFind might be of use. But I'd like to hear more opinions before I blindly open a feature request.

If the documentation says that you should use retro, then it needs to be very clear about it. Personally, I'd suggest that you just open an enhancement request. Either Andrei will do something about it (since he's almost certainly the one who would) or he won't. But I can pretty much guarantee that there will be other people who will want it. - Jonathan M Davis
Feb 14 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/15/2011 05:03 AM, Jonathan M Davis wrote:
 On Monday 14 February 2011 19:35:21 Andrej Mitrovic wrote:
 import std.stdio, std.algorithm, std.range;

 void main()
 {
      writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
      writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }

 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]

 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front,
 needle) is true " "To find the last occurence of needle in haystack, call
 find(retro(haystack), needle). "

 To me, if I was looking for the last element in a range I would expect to
 get a range with the found element followed by an elements after it.
 Obviously retro reverses the range (it just hard-wires front=back,
 back=front for those not in the know), so this code is correct.

 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]

 would return the range:
 [5, 1]

 and not:
 [5, 4, 3, 2, 1, 5]

 Isn't that what most people would want when they're looking for the last
 matching element?

retro revereses the whole range. What you want is something like findFromBack. Of course, retro isn't going to be what you want (though I guess I can understand why you would think that it would work if you didn't think it through). I don't think that we have any functions like findFromBack though. It's probably worth an enhancement request.

Indeed. The code just does what it says. I also understand Andrej's point. But it's a different feature; and one worth inclusion in Phobos, as Jonathan says. Note: there is a mental trap here ;-) <iterating in reverse order !is reversing the array and iterating> Denis -- _________________ vita es estrany spir.wikidot.com
Feb 15 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/15/2011 05:40 AM, Andrej Mitrovic wrote:
 On 2/15/11, Jonathan M Davis<jmdavisProg gmx.com>  wrote:
 retro revereses the whole range. What you want is something like
 findFromBack.
 I don't think that we have any functions like findFromBack though. It's
 probably
 worth an enhancement request.

std.string had a find and rfind, both of which are deprecated now (although we can still use indexOf& lastIndexOf). So std.algorithm.find will take its place, but there's no rFind. There's retro(). So I suppose rFind or lastFind would fit as a name if there's a use case for this. The problem is, there's 7 find templates in std.algorithm. I think making another 7 templates for lastFind would be too much work without a valid use case. It's much more than just replacing popBack and back calls to popFront and front, from what I can tell. Anyway, I'm posting this since I don't know if a reversed range is what most people want. It seems kind of strange to me to use retro to find a last match and then get a reversed range back, but maybe that's just me? I'd like to hear from people who've used find with retro - if so did the reversed range and its length make sense to them or not? Using retro with a string doesn't make sense since that will reverse the string and you won't match with your needle. It won't compile either, but maybe that is a bug with retro or find. Here's what I mean: import std.string : indexOf, lastIndexOf; import std.algorithm; import std.range; void main() { string mystring = "foo bar doo bar yaz"; auto leftIndex = indexOf(mystring, "bar"); assert(mystring[leftIndex .. $] == "bar doo bar yaz"); auto rightIndex = lastIndexOf(mystring, "bar"); assert(mystring[rightIndex .. $] == "bar yaz"); // now the std.algorithm.find case: auto firstRange = find(mystring, "bar"); assert(firstRange == "bar doo bar yaz"); // will never match, since retro reverses the string. // but it also errors out auto lastRange = find(retro(mystring), "bar"); assert(firstRange == "bar yaz"); } D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2403): Error: variable std.algorithm.simpleMindedFind!(pred,Retro!(string),string).simpleMindedFind.estimatedNeedleLength cannot modify immutable D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(2216): Error: template instance std.algorithm.simpleMindedFind!(pred,Retro!(string),string) error instantiating stringFind2.d(20): instantiated from here: find!("a == b",Retro!(string),string) stringFind2.d(20): Error: template instance std.algorithm.find!("a == b",Retro!(string),string) error instantiating Also, std.string.indexOf conflicts with std.algorithm.indexOf, but I think some of these functions are getting fixed for the next release (IIRC there was a thread about it). Now, how would you easily get a range back so that: find("foo bar doo bar", "bar") == "bar doo bar" and: lastFind("foo bar doo bar", "bar") == "bar" without using a specialized version of find, in this case lastFind?

0. If we want a separate function for finding backwards, it should have a name starting with "find-", I guess, like Jonathan's findFromBack, or just findBack possibly? But I guess we could instead have a 'backwards' bool param for such cases (probably rare). This would also save the issue of duplicating all find template variant. (Sure, inside the func the search loop must be duplicated, I gues, but still...) What do you think? 1. About the documentation saying to use retro to find last, it is just *incorrect*. It would be ok if find would return an element, but it doesn't. Actually, seems the doc writer has fallen in /this/ trap. 2. In general, I find (!) it wrong for a func called "find" to return the "rest" range. * that is certainly not what people expect --> bugs * that is uselessly heavy & unpracticle in typical case In some situations, getting a rest range is probably just the right thing. Eg for incremental search. Even then, a findAll func would fulfill the needs in most cases, don't you think?. Maybe "findRest" for the current function would make things clearer? Also: most libs return an index (or an interval, for pattern matching) for find: this lets the user choose whether to then fetch the element, a slice, nothing, or whatever. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 15 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 14 Feb 2011 22:35:21 -0500, Andrej Mitrovic <none none.none> wrote:

 import std.stdio, std.algorithm, std.range;

 void main()
 {
     writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
     writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }

 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]

 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front,  
 needle) is true "
 "To find the last occurence of needle in haystack, call  
 find(retro(haystack), needle). "

 To me, if I was looking for the last element in a range I would expect  
 to get a range with the found element followed by an elements after it.  
 Obviously retro reverses the range (it just hard-wires front=back,  
 back=front for those not in the know), so this code is correct.

 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]

 would return the range:
 [5, 1]

 and not:
 [5, 4, 3, 2, 1, 5]

 Isn't that what most people would want when they're looking for the last  
 matching element?

This is one of the fundamental problems with ranges -- a more useful construct for find to return is a reference to the individual element, then you could create a subrange based on that element location. Essentially, there are two things find does and it's impossible to unlink them -- 1) find the needle, 2) choose which side of the needle is the range you want to get back. So really, there are *4* operations that we need, find remainder, find until, find reverse remainder, and find reverse until. I should be able to get these four ranges with the different instances of find: [] [5, 1, 2, 3, 4, 5, 1] [5, 1, 2, 3, 4] [5, 1] This is why dcollections uses cursors -- tiny ranges that refer to exactly one element. Then you can use cursors to slice the original container. -Steve
Feb 15 2011
prev sibling next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 15 Feb 2011 06:35:21 +0300, Andrej Mitrovic <none none.none> wrote:

 import std.stdio, std.algorithm, std.range;

 void main()
 {
     writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
     writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }

 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]

 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front,  
 needle) is true "
 "To find the last occurence of needle in haystack, call  
 find(retro(haystack), needle). "

 To me, if I was looking for the last element in a range I would expect  
 to get a range with the found element followed by an elements after it.  
 Obviously retro reverses the range (it just hard-wires front=back,  
 back=front for those not in the know), so this code is correct.

 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]

 would return the range:
 [5, 1]

 and not:
 [5, 4, 3, 2, 1, 5]

 Isn't that what most people would want when they're looking for the last  
 matching element?

Try retro(find(retro(haystack, needle)));
Feb 15 2011
next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 16 Feb 2011 09:22:02 +0300, Denis Koroskin <2korden gmail.com>  
wrote:

 On Tue, 15 Feb 2011 06:35:21 +0300, Andrej Mitrovic <none none.none>  
 wrote:

 import std.stdio, std.algorithm, std.range;

 void main()
 {
     writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
     writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }

 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]

 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front,  
 needle) is true "
 "To find the last occurence of needle in haystack, call  
 find(retro(haystack), needle). "

 To me, if I was looking for the last element in a range I would expect  
 to get a range with the found element followed by an elements after it.  
 Obviously retro reverses the range (it just hard-wires front=back,  
 back=front for those not in the know), so this code is correct.

 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]

 would return the range:
 [5, 1]

 and not:
 [5, 4, 3, 2, 1, 5]

 Isn't that what most people would want when they're looking for the  
 last matching element?

Try retro(find(retro(haystack, needle)));

Screw it, I didn't understand what you needed.
Feb 15 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/16/2011 07:22 AM, Denis Koroskin wrote:
 On Tue, 15 Feb 2011 06:35:21 +0300, Andrej Mitrovic <none none.none> wrote:

 import std.stdio, std.algorithm, std.range;

 void main()
 {
 writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
 writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
 }

 Output:
 [5, 1, 2, 3, 4, 5, 1]
 [5, 4, 3, 2, 1, 5]

 The docs for find are:
 "returns : haystack advanced such that binaryFun!pred(haystack.front, needle)
 is true "
 "To find the last occurence of needle in haystack, call find(retro(haystack),
 needle). "

 To me, if I was looking for the last element in a range I would expect to get
 a range with the found element followed by an elements after it. Obviously
 retro reverses the range (it just hard-wires front=back, back=front for those
 not in the know), so this code is correct.

 Still, I would expect that finding a last element in this range:
 [5, 1, 2, 3, 4, 5, 1]

 would return the range:
 [5, 1]

 and not:
 [5, 4, 3, 2, 1, 5]

 Isn't that what most people would want when they're looking for the last
 matching element?

Try retro(find(retro(haystack, needle)));

for any reason, I would prefere findBack(haystack, needle); :-) Denis -- _________________ vita es estrany spir.wikidot.com
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/16/11, spir <denis.spir gmail.com> wrote:
 for any reason, I would prefere
      findBack(haystack, needle);
 :-)

Or maybe find should have an extra parameter that decides if the search begins from the beginning or the end of the range.
Feb 16 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 Feb 2011 11:14:27 -0500, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:

 On 2/16/11, spir <denis.spir gmail.com> wrote:
 for any reason, I would prefere
      findBack(haystack, needle);
 :-)

Or maybe find should have an extra parameter that decides if the search begins from the beginning or the end of the range.

I just realized, this isn't possible in the general case. That is, given your original range [5, 1, 2, 3, 4, 5, 1], the only way to get [5, 1] is to use popFront. Think about this. What are the basic operations of a bidirectional range? popFront and popBack. There is no way to search from the back, and then use that as the front end of the resulting range. Essentially, the range API does not allow what you want unless you have a random-access range, and I don't even know if that can be generalized. The operation you are looking for is very different from what find does. -Steve
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Poor implementation, but wouldn't this work?:

import std.stdio;
import std.range;
import std.array;

auto findBack(alias pred = "a == b", R, E)(R haystack, E needle)
    if (isBidirectionalRange!R)
{
    R result;

    size_t index;
    auto reversed = retro(haystack);
    foreach (item; reversed)
    {
        index++;
        if (item == needle)
            break;
    }

    while (index)
    {
        result ~= reversed.front;
        reversed.popFront;
        index--;
    }

    return retro(result);
}

void main()
{
    auto orig = [5, 1, 2, 3, 4, 5, 1];

    auto result = findBack(orig, 4);
    assert(array(result) == [4, 5, 1]);
}
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
My code is a little bit broken though because if nothing is found the
entire range is returned.
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Quick fix:

import std.stdio;
import std.range;
import std.array;

auto findBack(alias pred = "a == b", R, E)(R haystack, E needle)
    if (isBidirectionalRange!R)
{
    R result;

    size_t index;
    auto reversed = retro(haystack);
    bool found;

    foreach (item; reversed)
    {
        index++;
        if (item == needle)
        {
            found = true;
            break;
        }
    }

    if (found)
    {
        while (index)
        {
            result ~= reversed.front;
            reversed.popFront;
            index--;
        }
    }

    return retro(result);
}

void main()
{
    auto orig = [5, 1, 2, 3, 4, 5, 1];

    auto result = findBack(orig, 4);
    assert(array(result) == [4, 5, 1]);
}
Feb 16 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 Feb 2011 12:37:04 -0500, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:

 Quick fix:

 import std.stdio;
 import std.range;
 import std.array;

 auto findBack(alias pred = "a == b", R, E)(R haystack, E needle)
     if (isBidirectionalRange!R)
 {
     R result;

     size_t index;
     auto reversed = retro(haystack);
     bool found;

     foreach (item; reversed)
     {
         index++;
         if (item == needle)
         {
             found = true;
             break;
         }
     }

     if (found)
     {
         while (index)
         {
             result ~= reversed.front;
             reversed.popFront;
             index--;
         }
     }

     return retro(result);
 }

 void main()
 {
     auto orig = [5, 1, 2, 3, 4, 5, 1];

     auto result = findBack(orig, 4);
     assert(array(result) == [4, 5, 1]);
 }

Your code has a rather large design flaw. It does not return a subrange to the original, it returns a new range. That's not in the charter of find, find must return a portion of the original. Not to mention it assumes R can be appended to. For example, if I want to find the last 5 and change it to 6, I could do: find(retro(r)).front = 6; In your code, findBack(r).front = 6 does nothing. -Steve
Feb 16 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 Feb 2011 13:43:57 -0500, spir <denis.spir gmail.com> wrote:

 On 02/16/2011 05:24 PM, Steven Schveighoffer wrote:
 On Wed, 16 Feb 2011 11:14:27 -0500, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 On 2/16/11, spir <denis.spir gmail.com> wrote:
 for any reason, I would prefere
 findBack(haystack, needle);
 :-)

Or maybe find should have an extra parameter that decides if the search begins from the beginning or the end of the range.

I just realized, this isn't possible in the general case. That is, given your original range [5, 1, 2, 3, 4, 5, 1], the only way to get [5, 1] is to use popFront. Think about this. What are the basic operations of a bidirectional range? popFront and popBack. There is no way to search from the back, and then use that as the front end of the resulting range. Essentially, the range API does not allow what you want unless you have a random-access range, and I don't even know if that can be generalized. The operation you are looking for is very different from what find does.

Agreed. On the other hand, it is a basic operation very often provided by APIs for collections --together with several other operations having a right- or -last or version. And it's not like a trivial one-liner one would occasionnally re-implement on occasion. This is ypically, I guess, the kind of service std.algorithm is supposed to deliver. And we shouldn't find it elsewhere since this module is precisely supposed to provide general purpose algorithms. Thus, don't we face a contradiction, due to the fact that std.algorithm is mainly range-oriented? How to reconciliate this with the broader "range" of operations one would expect to find there? In this case, couldn't we still have the extra parameter, and check the collection allows random-access? Or have a variant with this extra param beeing non-optional and a stricter template constraint allowing only random-access ranges/collections?

The problem is ranges are missing some features that iterators make possible. If we think back to C++ iterators, a "range" is a pair of iterators. But you have the power to use whatever two iterators you want for your range. So what Andrej wants is possible in C++ (although ugly): target = std::find(std::reverse_iterator(r.end), std::reverse_iterator(r.begin), 5); target++; myrange = Range(target.base(), r.end) now the "range" myrange is [5, 1] one could easily abstract this into a function (e.g. rfind) so you could do: myrange = Range(rfind(r.begin, r.end), r.end); The issue is that find returns a range, and you cannot easily "flip" ranges given the original range. But if you get an iterator (or cursor in the case of dcollections), then constructing the correct subrange is trivial. With dcollections cursors, it's actually also safe too. -Steve
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
The only thing I could come up with is exhausting the entire range to
get the length of a bidirectional range. But that's inefficient.
Anyway here's the dull thing:

import std.stdio;
import std.range;
import std.array;

R findBack(alias pred = "a == b", R, E)(R haystack, E needle)
    if (isBidirectionalRange!R)
{
    size_t index;
    bool found;
    auto saved = haystack;

    foreach (item; retro(haystack))
    {
        if (item == needle)
        {
            found = true;
            index++;
            break;
        }
        index++;
    }

    if (found)
    {
        size_t newIndex;
        while (!haystack.empty)
        {
            newIndex++;
            haystack.popBack;
        }

        newIndex -= index;
        while (!saved.empty && newIndex)
        {
            saved.popFront;
            newIndex--;
        }
    }

    return saved;
}

void main()
{
    auto orig = [4, 0, 4, 0];
    auto result = findBack(orig, 4);

    assert(array(result) == [4, 0]);

    result.front = 10;
    assert(orig == [4, 0, 10, 0]);
}

You'll have to forgive me but I have yet to study algorithms properly. :)
Feb 16 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 Feb 2011 14:24:36 -0500, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:

 The only thing I could come up with is exhausting the entire range to
 get the length of a bidirectional range. But that's inefficient.
 Anyway here's the dull thing:

 import std.stdio;
 import std.range;
 import std.array;

 R findBack(alias pred = "a == b", R, E)(R haystack, E needle)
     if (isBidirectionalRange!R)
 {
     size_t index;
     bool found;
     auto saved = haystack;

     foreach (item; retro(haystack))
     {
         if (item == needle)
         {
             found = true;
             index++;
             break;
         }
         index++;
     }

     if (found)
     {
         size_t newIndex;
         while (!haystack.empty)
         {
             newIndex++;
             haystack.popBack;
         }

         newIndex -= index;
         while (!saved.empty && newIndex)
         {
             saved.popFront;
             newIndex--;
         }
     }

     return saved;
 }

 void main()
 {
     auto orig = [4, 0, 4, 0];
     auto result = findBack(orig, 4);

     assert(array(result) == [4, 0]);

     result.front = 10;
     assert(orig == [4, 0, 10, 0]);
 }

 You'll have to forgive me but I have yet to study algorithms properly. :)

Hehe if you are willing to traverse the whole range, it's much easier than this: auto saved = R.init; while(!haystack.empty) { if(haystack.front == needle) saved = haystack.save(); haystack.popFront(); } return saved; The point is, no matter what you do, the missing ability to construct a range from two iterators/cursors means you must degrade performance to get the desired effect. This might be able to be simulated with having a range "flip" itself based on certain criteria, but it must be a range-supported feature, which means more complexity goes into the range concept. -Steve
Feb 16 2011
prev sibling next sibling parent reply jam <gr0v3er+d gmail.com> writes:
On Wed, 16 Feb 2011 20:24:36 +0100, Andrej Mitrovic wrote:

 The only thing I could come up with is exhausting the entire range to
 get the length of a bidirectional range. But that's inefficient. Anyway
 here's the dull thing:
 
 import std.stdio;
 import std.range;
 import std.array;
 
 R findBack(alias pred = "a == b", R, E)(R haystack, E needle)
     if (isBidirectionalRange!R)
 {
     size_t index;
     bool found;
     auto saved = haystack;
 
     foreach (item; retro(haystack))
     {
         if (item == needle)
         {
             found = true;
             index++;
             break;
         }
         index++;
     }
 
     if (found)
     {
         size_t newIndex;
         while (!haystack.empty)
         {
             newIndex++;
             haystack.popBack;
         }
 
         newIndex -= index;
         while (!saved.empty && newIndex)
         {
             saved.popFront;
             newIndex--;
         }
     }
 
     return saved;
 }
 
 void main()
 {
     auto orig = [4, 0, 4, 0];
     auto result = findBack(orig, 4);
 
     assert(array(result) == [4, 0]);
 
     result.front = 10;
     assert(orig == [4, 0, 10, 0]);
 }
 
 You'll have to forgive me but I have yet to study algorithms properly.
 :)

import std.stdio,std.algorithm,std.range; void main() { auto a = [5,1,2,3,4,5,1]; auto index = countUntil(retro(a),5); writeln(a[a.length-1-index .. a.length]); } outputs: [5,1] but yeah, it is a little awkward.
Feb 16 2011
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 16, 2011 13:00:13 Andrej Mitrovic wrote:
 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 void main()
 {
 
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     writeln(a[a.length-1-index .. a.length]);
 
 }

That works for random-access ranges. But I was under the impression that bidirectional ranges don't necessarily have a length property?

I'm not sure. IIRC was assuming that they would and later someone pointed out a valid case where they wouldn't. So, in the long run, they probably won't but they may right now. Actually, I'll check... No. They don't require a range. They must be a forward range and then have popBack and back in addition, but length is not required. - Jonathan M Davis
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 void main()
 {
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     writeln(a[a.length-1-index .. a.length]);
 }

That works for random-access ranges. But I was under the impression that bidirectional ranges don't necessarily have a length property?
Feb 16 2011
prev sibling next sibling parent jam <gr0v3er+d gmail.com> writes:
On Wed, 16 Feb 2011 22:00:13 +0100, Andrej Mitrovic wrote:

 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 void main()
 {
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     writeln(a[a.length-1-index .. a.length]);
 }

But I was under the impression that bidirectional ranges don't necessarily have a length property?

Doh. That is exactly correct. I guess the following would work for bidirectional ranges: import std.stdio,std.algorithm,std.range,std.container; void main() { auto a = [5,1,2,3,4,5,1]; auto index = countUntil(retro(a),5); auto R = retro(take(retro(a),index+1)); writeln(R); R[0] = 6; writeln(a); } but this is just getting nutty.
Feb 16 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 import std.stdio,std.algorithm,std.range,std.container;

 void main()
 {
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     auto R = retro(take(retro(a),index+1));
     writeln(R);
     R[0] = 6;
     writeln(a);
 }

 but this is just getting nutty.

Nutty, but it's great how much lines you can save when composing ranges. retro and take are both lazy afaik, so this can't be that bad?
Feb 16 2011
prev sibling next sibling parent jam <gr0v3er+d gmail.com> writes:
On Thu, 17 Feb 2011 00:05:15 +0100, Andrej Mitrovic wrote:

 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 import std.stdio,std.algorithm,std.range,std.container;

 void main()
 {
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     auto R = retro(take(retro(a),index+1)); writeln(R);
     R[0] = 6;
     writeln(a);
 }

 but this is just getting nutty.

retro and take are both lazy afaik, so this can't be that bad?

Well take is for sure, but I'm not sure about retro(I didn't see anything in range.d or the online docs that indicate it is). You could save some work by just reversing the container once at the start though.
Feb 16 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 Feb 2011 17:58:12 -0500, jam <gr0v3er+d gmail.com> wrote:

 On Wed, 16 Feb 2011 22:00:13 +0100, Andrej Mitrovic wrote:

 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 void main()
 {
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     writeln(a[a.length-1-index .. a.length]);
 }

But I was under the impression that bidirectional ranges don't necessarily have a length property?

Doh. That is exactly correct. I guess the following would work for bidirectional ranges: import std.stdio,std.algorithm,std.range,std.container; void main() { auto a = [5,1,2,3,4,5,1]; auto index = countUntil(retro(a),5); auto R = retro(take(retro(a),index+1)); writeln(R); R[0] = 6; writeln(a); } but this is just getting nutty.

This doesn't work, you can't retro take because take is not a bidirectional range. It might work in the case of arrays, but it won't work for something like a string. -Steve
Feb 17 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/16/2011 05:14 PM, Andrej Mitrovic wrote:
 On 2/16/11, spir<denis.spir gmail.com>  wrote:
 for any reason, I would prefere
       findBack(haystack, needle);
 :-)

Or maybe find should have an extra parameter that decides if the search begins from the beginning or the end of the range.

Yes, I would support this additional parameter; probably the simplest solution. (Actually had the same idea in mind, but don't remember whether I posted it :-) Denis -- _________________ vita es estrany spir.wikidot.com
Feb 16 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/16/2011 05:24 PM, Steven Schveighoffer wrote:
 On Wed, 16 Feb 2011 11:14:27 -0500, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 On 2/16/11, spir <denis.spir gmail.com> wrote:
 for any reason, I would prefere
 findBack(haystack, needle);
 :-)

Or maybe find should have an extra parameter that decides if the search begins from the beginning or the end of the range.

I just realized, this isn't possible in the general case. That is, given your original range [5, 1, 2, 3, 4, 5, 1], the only way to get [5, 1] is to use popFront. Think about this. What are the basic operations of a bidirectional range? popFront and popBack. There is no way to search from the back, and then use that as the front end of the resulting range. Essentially, the range API does not allow what you want unless you have a random-access range, and I don't even know if that can be generalized. The operation you are looking for is very different from what find does.

Agreed. On the other hand, it is a basic operation very often provided by APIs for collections --together with several other operations having a right- or -last or version. And it's not like a trivial one-liner one would occasionnally re-implement on occasion. This is ypically, I guess, the kind of service std.algorithm is supposed to deliver. And we shouldn't find it elsewhere since this module is precisely supposed to provide general purpose algorithms. Thus, don't we face a contradiction, due to the fact that std.algorithm is mainly range-oriented? How to reconciliate this with the broader "range" of operations one would expect to find there? In this case, couldn't we still have the extra parameter, and check the collection allows random-access? Or have a variant with this extra param beeing non-optional and a stricter template constraint allowing only random-access ranges/collections? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 16 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/16/2011 06:22 PM, Andrej Mitrovic wrote:
 Poor implementation, but wouldn't this work?:

 import std.stdio;
 import std.range;
 import std.array;

 auto findBack(alias pred = "a == b", R, E)(R haystack, E needle)
      if (isBidirectionalRange!R)
 {
      R result;

      size_t index;
      auto reversed = retro(haystack);
      foreach (item; reversed)
      {
          index++;
          if (item == needle)
              break;
      }

      while (index)
      {
          result ~= reversed.front;
          reversed.popFront;
          index--;
      }

      return retro(result);
 }

 void main()
 {
      auto orig = [5, 1, 2, 3, 4, 5, 1];

      auto result = findBack(orig, 4);
      assert(array(result) == [4, 5, 1]);
 }

Of course, it would work (I mean the principle, didn't test). But isn't it stupid to (1) reconstruct the result by stepping in reversed (2) reverse twice to finally provide a forward result ;-) The issue I see is the typical case find in an array, a list or another kind of sequential collection. You wouldn't do that in any case with such collections. Don't you find it foolish algorithmically? With a list (*), you would step backward, then just return the node/list from there; with an array, ditto and just slice from there. (And note in you case find(orig, 4) returns the same result ;-) Denis (*) If singly-linked only, there could be a need for reverse, but actually this would rather reveal a poor choice of data structure, non matching the needs. -- _________________ vita es estrany spir.wikidot.com
Feb 16 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 16, 2011 13:36:54 Jonathan M Davis wrote:
 On Wednesday, February 16, 2011 13:00:13 Andrej Mitrovic wrote:
 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 void main()
 {
 
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     writeln(a[a.length-1-index .. a.length]);
 
 }

That works for random-access ranges. But I was under the impression that bidirectional ranges don't necessarily have a length property?

I'm not sure. IIRC was assuming that they would and later someone pointed out a valid case where they wouldn't. So, in the long run, they probably won't but they may right now. Actually, I'll check... No. They don't require a range. They must be a forward range and then have popBack and back in addition, but length is not required.

Yikes. I should re-read my posts more. I meant to so that "IIRC, Andrei was assuming that they would." However, regardless of what was assumed before, bidirectional ranges do _not_ have to a length property. - Jonathan M Davis
Feb 16 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/16/2011 09:42 PM, jam wrote:
 On Wed, 16 Feb 2011 20:24:36 +0100, Andrej Mitrovic wrote:

 The only thing I could come up with is exhausting the entire range to
 get the length of a bidirectional range. But that's inefficient. Anyway
 here's the dull thing:

 import std.stdio;
 import std.range;
 import std.array;

 R findBack(alias pred = "a == b", R, E)(R haystack, E needle)
      if (isBidirectionalRange!R)
 {
      size_t index;
      bool found;
      auto saved = haystack;

      foreach (item; retro(haystack))
      {
          if (item == needle)
          {
              found = true;
              index++;
              break;
          }
          index++;
      }

      if (found)
      {
          size_t newIndex;
          while (!haystack.empty)
          {
              newIndex++;
              haystack.popBack;
          }

          newIndex -= index;
          while (!saved.empty&&  newIndex)
          {
              saved.popFront;
              newIndex--;
          }
      }

      return saved;
 }

 void main()
 {
      auto orig = [4, 0, 4, 0];
      auto result = findBack(orig, 4);

      assert(array(result) == [4, 0]);

      result.front = 10;
      assert(orig == [4, 0, 10, 0]);
 }

 You'll have to forgive me but I have yet to study algorithms properly.
 :)

import std.stdio,std.algorithm,std.range; void main() { auto a = [5,1,2,3,4,5,1]; auto index = countUntil(retro(a),5); writeln(a[a.length-1-index .. a.length]); } outputs: [5,1] but yeah, it is a little awkward.

And you're assuming the range is slice-able (I mean at arbitrary position, witout popping it); which you cannot do in the general case. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 16 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 16, 2011 15:19:01 jam wrote:
 On Thu, 17 Feb 2011 00:05:15 +0100, Andrej Mitrovic wrote:
 On 2/16/11, jam <gr0v3er+d gmail.com> wrote:
 import std.stdio,std.algorithm,std.range,std.container;
 
 void main()
 {
 
     auto a = [5,1,2,3,4,5,1];
     auto index = countUntil(retro(a),5);
     auto R = retro(take(retro(a),index+1)); writeln(R);
     R[0] = 6;
     writeln(a);
 
 }
 
 but this is just getting nutty.

Nutty, but it's great how much lines you can save when composing ranges. retro and take are both lazy afaik, so this can't be that bad?

Well take is for sure, but I'm not sure about retro(I didn't see anything in range.d or the online docs that indicate it is). You could save some work by just reversing the container once at the start though.

All retro does is forward front and popFront to back and popBack and back and popBack to front and popFront. So, the only overhead is the extra function call, which is probably inlined anyway. - Jonathan M Davis
Feb 16 2011