digitalmars.D.learn - commonLength
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (8/8) Jan 15 2015 I want a variant of commonPrefix(a, b) at
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (24/32) Jan 15 2015 I just discovered that zip has StoppingPolicy so why does
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (4/5) Jan 15 2015 Update: should be
- Tobias Pankrath (2/13) Jan 15 2015 StoppingPolicy is not a template parameter, it is this one:
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (13/15) Jan 15 2015 Ok, great!
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (17/32) Jan 15 2015 In the mean while how should I generalize
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (13/19) Jan 15 2015 I did a silly mistake. The correct version is
- Tobias Pankrath (2/22) Jan 15 2015 What's wrong with commonPrefix(..).length?
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (19/46) Jan 15 2015 Only works if all input arguments have length property.
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (4/11) Jan 15 2015 I wonder if we could add an extra overload to countUntil in
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (9/10) Jan 15 2015 Ahh, sorry that works too. I'm surprised :)
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (19/38) Jan 15 2015 The predicate version of count() seems to work for your case. If I
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/18) Jan 15 2015 I want to terminate count on first mismatch like
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
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>
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
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:
Jan 15 2015
On Thursday, 15 January 2015 at 13:59:04 UTC, Tobias Pankrath wrote:StoppingPolicy is not a template parameter, it is this one: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
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: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)StoppingPolicy is not a template parameter, it is this one: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
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
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:What's wrong with commonPrefix(..).length?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
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:Only works if all input arguments have length property. I would have implemented countUntil() to return -length upon failure instead of -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 :)On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote:What's wrong with commonPrefix(..).length?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
On Thursday, 15 January 2015 at 20:21:26 UTC, Nordlöw wrote:
I would have implemented countUntil() to return
-length
upon failure instead of
-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
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
On 01/15/2015 11:24 AM, "Nordlöw" wrote:On Thursday, 15 January 2015 at 13:13:57 UTC, Nordlöw wrote: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() {} AliI 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
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);
Jan 15 2015