## digitalmars.D.learn - commonLength

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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])

?
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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.
```
Jan 15 2015
"Tobias Pankrath" <tobias pankrath.net> writes:
``` 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
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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.
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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)
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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...
```
Jan 15 2015
"Tobias Pankrath" <tobias pankrath.net> writes:
```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?
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```On Thursday, 15 January 2015 at 19:30:21 UTC, Tobias Pankrath
wrote:
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?

Only works if all input arguments have length property.

I would have implemented countUntil() to return

-length

-1
.

Then I could have just returned abs of the return value from
commonUntil.

However

auto commonPrefixLengthAlt(S, T)(S a, T b)  safe pure  nogc
nothrow
{
import std.algorithm: commonPrefix, count;
return commonPrefix(a, b).count;
}

works on dmd git master!

Limited to 2 arguments, though, but I'm find with that for now :)
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```On Thursday, 15 January 2015 at 20:21:26 UTC, Nordlöw wrote:
I would have implemented countUntil() to return

-length

-1
.

Then I could have just returned abs of the return value from
commonUntil.

I wonder if we could add an extra overload to countUntil in
Phobos that takes an enum as first argument similar to zip's
StoppingPolicy. Something like FailCountPolicy.
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```On Thursday, 15 January 2015 at 19:30:21 UTC, Tobias Pankrath
wrote:
What's wrong with commonPrefix(..).length?

Ahh, sorry that works too. I'm surprised :)
DMD/Phobos has become really clever at avoiding allocation.

Seems there may be need for both

commonPrefixCount

and

commonPrefixLength

depending on whether string auto-decoding is needed or not.
```
Jan 15 2015
=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
```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

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
```
Jan 15 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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);