algorithm API design question

[Timon Gehr]

On 09/30/2013 04:35 AM, Andrei Alexandrescu wrote:
> I need a function that finds a run of length k of elements equal to x in
> a range r, and I presume such a simple yet nontrivial algorithm (a
> dozen-liner) should be part of std.algorithm.
>
> This raises an interesting question - what form should the API have. I
> see three options:
>
> 1. The existing find(r1, r2) figures out a way to dynamically check that
> r2 is a run of identical elements and tailor the argument accordingly.
> For example, during Boyer-Moore initialization that test comes cheap.
>

This kind of thing tends to not pay off in the average case.

> 2. We should statically specialize find(r1, r2) for the case r2 is an
> instance of Repeat. The specialization runs the tailored algorithm. The
> user is supposed to call e.g. find(r, repeat(x, k)) to benefit of the
> specialized algorithm.
>

If the specialized algorithm runs faster, this should be done anyway.
What is the optimization that would the specialized algorithm run faster 
though?

> 3. We should introduce a new function called e.g. findRun(r, x, k).
>

:(

> Each option has advantages and disadvantages. What do you all think is
> the best API?
>
>
> Andrei

We already have 2.