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.

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

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.

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

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

My code is a little bit broken though because if nothing is found the entire range is returned.

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

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

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

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