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 reply 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
parent reply "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
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 reply 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
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 reply 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
parent reply "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
parent reply 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
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 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
next sibling parent reply 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
parent reply 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]);
 }


 That works for random-access ranges.
 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
next sibling parent reply 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
parent reply 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.


 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.
Feb 16 2011
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
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]);
 }


 That works for random-access ranges.
 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 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 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 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 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 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