www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - commonLength

reply =?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
parent reply =?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
next sibling parent =?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
prev sibling next sibling parent reply "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
parent reply =?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
parent =?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
prev sibling parent reply =?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
next sibling parent reply "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
next sibling parent reply =?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 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 :)
Jan 15 2015
parent =?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

 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
prev sibling parent =?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
prev sibling parent reply =?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 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
Jan 15 2015
parent =?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); Your version will assert(commonPrefixLength("abc_d", "abc-d") == 4);
Jan 15 2015