I would appreciate comments on my palindrome predicate function

bool isPalindrome(R)(in R range) @safe pure
    if (isBidirectionalRange!(R))
{
    import std.range: retro, take;
    import std.algorithm: equal;
    static if (hasLength!R)
    {
        const mid = range.length/2; // too long for string
        return equal(range.retro.take(mid),
                     range.take(mid));
    }
    else
    {
        return range.retro.equal(range);
    }
}
unittest
{
    assert("dallassallad".isPalindrome);
    assert(!"ab".isPalindrome);
    assert("a".isPalindrome);
    assert("åäå".isPalindrome);
    assert("".isPalindrome);
    assert([1, 2, 2, 1].isPalindrome);
}
alias isSymmetrical = isPalindrome;

also defined here

https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L773

Specifically I wonder what to do with

    const mid = range.length/2; // TODO too long for string

when R is a string.

Further, I would like to extend isPalindrome() with a minimum length argument minLength that for string and wstring does

import std.uni: byDchar;
range.byDchar.array.length >= minLength.

AFAIK this will however prevent my algorithm from being single-pass right?

On Fri, Oct 24, 2014 at 09:56:18PM +0000, "Nordlöw" via Digitalmars-d-learn wrote:
> I would appreciate comments on my palindrome predicate function
> 
> bool isPalindrome(R)(in R range) @safe pure
>     if (isBidirectionalRange!(R))
> {
>     import std.range: retro, take;
>     import std.algorithm: equal;
>     static if (hasLength!R)
>     {
>         const mid = range.length/2; // too long for string
>         return equal(range.retro.take(mid),
>                      range.take(mid));
>     }
>     else
>     {
>         return range.retro.equal(range);
>     }
> }
[...]

I'd just do it the simple way using range primitives:

	bool isPalindrome(R)(in R range)
		if (isBidirectionalRange!R)
	{
		auto r = range.save;
		while (!r.empty)
		{
			if (r.front != r.back)
				return false;
			r.popFront();
			r.popBack();
		}
		return true;
	}

This is guaranteed to work on all bidirectional ranges in single-pass, handles odd/even lengths correctly, and doesn't depend on .length.

Offhand remark: in general you shouldn't annotate template functions with @safe or pure. Instead, let the compiler infer those attributes, and use @safe/pure unittests with known @safe/pure ranges to ensure your code itself doesn't introduce any un-@safe or impure operations. Otherwise, your function cannot be used with a range that has un-@safe or impure range methods.


T

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.

On Friday, 24 October 2014 at 21:56:20 UTC, Nordlöw wrote:
> bool isPalindrome(R)(in R range) @safe pure

Aside: for templates, just let the compiler infer @safe and pure. You don't know whether the range operations on R are pure or not.

As for the actual algorithm, there's no need for the random access version, and you bidirectional version does twice as much as necessary:

Just do:

while (!range.empty)
{
  if (range.front != range.back) return false;
  range.popFront();
  if (range.empty) break;
  range.popBack();
}
return true;

This automatically handles narrow strings.


> Further, I would like to extend isPalindrome() with a minimum length argument minLength that for string and wstring does
>
> import std.uni: byDchar;
> range.byDchar.array.length >= minLength.
>
> AFAIK this will however prevent my algorithm from being single-pass right?

I'm not sure what you are saying here, but hopefully the above code obviates this anyway.

On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander wrote:
> On Friday, 24 October 2014 at 21:56:20 UTC, Nordlöw wrote:
>> bool isPalindrome(R)(in R range) @safe pure
>
> Aside: for templates, just let the compiler infer @safe and pure. You don't know whether the range operations on R are pure or not.
>
> As for the actual algorithm, there's no need for the random access version, and you bidirectional version does twice as much as necessary:
>
> Just do:
>
> while (!range.empty)
> {
>   if (range.front != range.back) return false;
>   range.popFront();
>   if (range.empty) break;
>   range.popBack();
> }
> return true;
>
> This automatically handles narrow strings.
>
>
>> Further, I would like to extend isPalindrome() with a minimum length argument minLength that for string and wstring does
>>
>> import std.uni: byDchar;
>> range.byDchar.array.length >= minLength.
>>
>> AFAIK this will however prevent my algorithm from being single-pass right?
>
> I'm not sure what you are saying here, but hopefully the above code obviates this anyway.

Clever. Thx!

On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander wrote:
>> Further, I would like to extend isPalindrome() with a minimum length argument minLength that for string and wstring does

I extended my algorithm with a minLength argument https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L774

On Sunday, 26 October 2014 at 20:38:29 UTC, Nordlöw wrote:
> On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander wrote:
>>> Further, I would like to extend isPalindrome() with a minimum length argument minLength that for string and wstring does
>
> I extended my algorithm with a minLength argument https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L774

You could add an early `return false;` if the range has length and it is less than minLength.

On Monday, 27 October 2014 at 12:10:59 UTC, Marc Schütz wrote:
> You could add an early `return false;` if the range has length and it is less than minLength.

See update :)

Thanks!

On Monday, 27 October 2014 at 16:59:19 UTC, Nordlöw wrote:
> On Monday, 27 October 2014 at 12:10:59 UTC, Marc Schütz wrote:
>> You could add an early `return false;` if the range has length and it is less than minLength.
>
> See update :)
>
> Thanks!

And you can return true if length <= 1

Why bidirectional range only?

On Monday, 27 October 2014 at 21:28:17 UTC, Andrea Fontana wrote:
> And you can return true if length <= 1

Thanks.

> Why bidirectional range only?

popBack() only for

http://dlang.org/phobos/std_range.html#isBidirectionalRange

Hi,

I don't know if I'm missing something but I did some tests with the popFront and popBack version:

bool isPalindrome(R)(R range)
if (isBidirectionalRange!(R))
{
	while (!range.empty){
		if (range.front != range.back) return false;
  		range.popFront();
  	if (range.empty) break;
  	range.popBack();
	}
	return true;
}

Against the older known version (or implementation):

bool isPalindrome2(R)(R r){
    auto len = r.length;
    auto mid = len/2;
    --len;
    for(auto i=0;i<mid;++i){
        if(r[i]!=r[len-i]){
            return false;
	}
    }
    return true;
}

And in my benchmark test, the first version is 3x "slower" than the second one.

Matheus.