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

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

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. :)

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

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.

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?

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

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

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

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.