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?

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

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?

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

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.

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

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

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

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

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)));