Improving std.algorithm.find

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Jul 19 12:23:05 PDT 2010


On 07/19/2010 02:12 PM, Philippe Sigaud wrote:
> On Mon, Jul 19, 2010 at 03:19, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org <mailto:SeeWebsiteForEmail at erdani.org>>
> wrote:
>
>
>     I agree that a findAll function yielding a range is nice, however
>     it's not the simplest interface. I think there should be a function
>     that just finds something somewhere.
>
>
> Yes, I agree that's the common case.
> What I personally would like is a way to find an element in an ordered
> container (binary tree...)

Wouldn't that be a member of the binary tree?

>     Aren't such scenarios better served by putting the limits inside the
>     predicate? Otherwise the list of what can be done could go on forever.
>
>
> The problem is that, as the predicate is passed at compile-time, the
> limits must be CT-defined too. I'd like the limits to be defined at
> runtime. I run into this regularly, while using predicates in
> std.algorithms.

I think this is a misunderstanding. All of std.algorithm works with 
delegates:

     int[] a = [ 1, 4, 2, 3 ];
     int b = 2;
     assert(find!((x) { return x > b; })(a) == [4, 2, 3]);

> A not-so-uncommon scenario for me is having one range delivering limits
> (or zones to explore, or any other runtime arguments), and finding a
> value inside those limits in another range. Ideally, I'd like to use
> find() on a spatial structure like an R-tree. (
> http://en.wikipedia.org/wiki/R-tree ).
>
> But I admit it's not that common.

Unless you manage to define appropriate and generally applicable 
iterators, I think that would overgeneralize find().

> Anything that can mimic regex functions on generic ranges is good, IMO.
> I regularly find myself wanting to do some regex-like matching. We do
> not need real pattern matching but even with simplified predicates, we
> can do many things.

I agree we're in desperate need for a good range-based, 
character-divorced, statically-computed regex engine.

> I'm sorry I didn't look at your implementation, as I don't know
> Boyer-Moore that much. Does it need to know the alphabet size or do you
> use another variant?

My explanation of B-M would do little more than pasting information from 
various places on the Net.


Andrei


More information about the Digitalmars-d mailing list