I want a variant of commonPrefix(a, b) at

    http://dlang.org/phobos/std_algorithm.html#commonPrefix

that only counts returns the length of commonPrefix(a, b)

Is commonPrefix lazy enough to make

    commonPrefix(a, b).count

as fast as

    zip(a, b).count!(ab => ab[0] == ab[1])

?

On Thursday, 15 January 2015 at 13:01:50 UTC, Nordlöw wrote:
> I want a variant of commonPrefix(a, b) at
>
>     http://dlang.org/phobos/std_algorithm.html#commonPrefix
>
> that only counts returns the length of commonPrefix(a, b)
>
> Is commonPrefix lazy enough to make
>
>     commonPrefix(a, b).count
>
> as fast as
>
>     zip(a, b).count!(ab => ab[0] == ab[1])
>
> ?

I just discovered that zip has StoppingPolicy so why does

auto commonPrefixLength(R...)(R ranges) if (ranges.length == 2)
{
    import std.range: zip;
    return zip!((a, b) => a[0] != b[1])(ranges);
}

unittest
{
    assert(commonPrefixLength([1, 2, 3, 10],
                              [1, 2, 4, 10]) == 2);
}

error as

algorithm_ex.d(1709,40): Error: template std.range.zip cannot deduce function from argument types !((a, b) => a[0] != b[1])(int[], int[]), candidates are:
std/range/package.d(3247,6):        std.range.zip(Ranges...)(Ranges ranges) if (Ranges.length && allSatisfy!(isInputRange, Ranges))
std/range/package.d(3265,6):        std.range.zip(Ranges...)(StoppingPolicy sp, Ranges ranges) if (Ranges.length && allSatisfy!(isInputRange, Ranges))
algorithm_ex.d(1714,30): Error: template instance algorithm_ex.commonPrefixLength!(int[], int[]) error instantiating

On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote:
>     return zip!((a, b) => a[0] != b[1])(ranges);

Update: should be

    return zip!((a, b) => a != b)(ranges);

but still fails with same error.

> I just discovered that zip has StoppingPolicy so why does
>
> auto commonPrefixLength(R...)(R ranges) if (ranges.length == 2)
> {
>     import std.range: zip;
>     return zip!((a, b) => a[0] != b[1])(ranges);
> }
>
> unittest
> {
>     assert(commonPrefixLength([1, 2, 3, 10],
>                               [1, 2, 4, 10]) == 2);
> }
>

StoppingPolicy is not a template parameter, it is this one: http://dlang.org/phobos/std_range.html#.StoppingPolicy

On Thursday, 15 January 2015 at 13:59:04 UTC, Tobias Pankrath wrote:
> StoppingPolicy is not a template parameter, it is this one: http://dlang.org/phobos/std_range.html#.StoppingPolicy

Ok, great!

However, none of the variants of zip, including all the three policies, fulfills my needs in

    assert(commonPrefixLength([1, 2, 3, 10],
                              [1, 2, 3]), 3);

which fails because

     commonPrefixLength([1, 2, 3, 10],
                        [1, 2, 3])

evaluates to -1.

This seems like a serious limitation that should be realized in yet another policy.

On Thursday, 15 January 2015 at 18:16:36 UTC, Nordlöw wrote:
> On Thursday, 15 January 2015 at 13:59:04 UTC, Tobias Pankrath wrote:
>> StoppingPolicy is not a template parameter, it is this one: http://dlang.org/phobos/std_range.html#.StoppingPolicy
>
> Ok, great!
>
> However, none of the variants of zip, including all the three policies, fulfills my needs in
>
>     assert(commonPrefixLength([1, 2, 3, 10],
>                               [1, 2, 3]), 3);
>
> which fails because
>
>      commonPrefixLength([1, 2, 3, 10],
>                         [1, 2, 3])
>
> evaluates to -1.
>
> This seems like a serious limitation that should be realized in yet another policy.

In the mean while how should I generalize

auto commonPrefixLength(S, T)(S a, T b)
{
    import std.range: zip;
    import std.algorithm: countUntil;
    return zip(a, b).countUntil!(ab => ab[0] != ab[1]);
}

to

- work as expected with the unittest above
- work with 3 or more arguments like zip do. How do check that all elements of a tuple are equal?

I believe this is an important issue because the function

    commonPrefixLength

together with sort can be used to implement

- completions (in widgets and intellisense)
- find rhymes (retro + commonPrefixLength + sort)

On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote:
> I just discovered that zip has StoppingPolicy so why does
>
> auto commonPrefixLength(R...)(R ranges) if (ranges.length == 2)
> {
>     import std.range: zip;
>     return zip!((a, b) => a[0] != b[1])(ranges);
> }

I did a silly mistake. The correct version is

auto commonPrefixLength(S, T)(S a, T b)
{
    import std.range: zip, StoppingPolicy;
    import std.algorithm: countUntil, count;
    const hit = zip(a, b).countUntil!(ab => ab[0] != ab[1]);
    return hit == -1 ? zip(a, b).count : hit;
}

This however needs to process zip(a, b) how do I avoid the extra count?

If countUntil returned zip(a, b).count upon failure I would have been done...

On Thursday, 15 January 2015 at 19:24:16 UTC, Nordlöw wrote:
> On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote:
>> I just discovered that zip has StoppingPolicy so why does
>>
>> auto commonPrefixLength(R...)(R ranges) if (ranges.length == 2)
>> {
>>    import std.range: zip;
>>    return zip!((a, b) => a[0] != b[1])(ranges);
>> }
>
> I did a silly mistake. The correct version is
>
> auto commonPrefixLength(S, T)(S a, T b)
> {
>     import std.range: zip, StoppingPolicy;
>     import std.algorithm: countUntil, count;
>     const hit = zip(a, b).countUntil!(ab => ab[0] != ab[1]);
>     return hit == -1 ? zip(a, b).count : hit;
> }
>
> This however needs to process zip(a, b) how do I avoid the extra count?
>
> If countUntil returned zip(a, b).count upon failure I would have been done...

What's wrong with commonPrefix(..).length?

On 01/15/2015 11:24 AM, "Nordlöw" wrote:
> On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote:
>> I just discovered that zip has StoppingPolicy so why does
>>
>> auto commonPrefixLength(R...)(R ranges) if (ranges.length == 2)
>> {
>>     import std.range: zip;
>>     return zip!((a, b) => a[0] != b[1])(ranges);
>> }
>
> I did a silly mistake. The correct version is
>
> auto commonPrefixLength(S, T)(S a, T b)
> {
>      import std.range: zip, StoppingPolicy;
>      import std.algorithm: countUntil, count;
>      const hit = zip(a, b).countUntil!(ab => ab[0] != ab[1]);
>      return hit == -1 ? zip(a, b).count : hit;
> }
>
> This however needs to process zip(a, b) how do I avoid the extra count?
>
> If countUntil returned zip(a, b).count upon failure I would have been
> done...

The predicate version of count() seems to work for your case. If I misunderstood, please explain with an added failing unit test:

auto commonPrefixLength(S, T)(S a, T b)
{
    import std.range: zip;
    import std.algorithm: count;
    return zip(a, b).count!(ab => ab[0] == ab[1]);
}

unittest
{
    assert(commonPrefixLength("açde", "") == 0);
    assert(commonPrefixLength("açde", "xyz") == 0);
    assert(commonPrefixLength("açd", "açde") == 3);
    assert(commonPrefixLength("açdef", "açdef") == 5);
}

void main()
{}

Ali

On Thursday, 15 January 2015 at 19:49:14 UTC, Ali Çehreli wrote:
> auto commonPrefixLength(S, T)(S a, T b)
> {
>     import std.range: zip;
>     import std.algorithm: count;
>     return zip(a, b).count!(ab => ab[0] == ab[1]);
> }
>
> unittest
> {
>     assert(commonPrefixLength("açde", "") == 0);
>     assert(commonPrefixLength("açde", "xyz") == 0);
>     assert(commonPrefixLength("açd", "açde") == 3);
>     assert(commonPrefixLength("açdef", "açdef") == 5);
> }

I want to terminate count on first mismatch like

    assert(commonPrefixLength("abc_d", "abc-d") == 3);

Your version will

    assert(commonPrefixLength("abc_d", "abc-d") == 4);