Generalise for to allow filtered ranges

Source Link

edited Jan 16 at 13:34

81.8k
14
101
309

#include <algorithm>
#include <concepts>
#include <ranges>
#include <string_view>
#include <utility>

// Start with string-view version
template<typename Char, typename Traits>
constexpr bool is_palindrome(std::basic_string_view<Char,Traits> const s) noexcept
{
    // We round down, because we can ignore a middle char (it will always match itself)
    auto const half_size = s.size() / 2;
    auto const r = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return std::ranges::starts_with(s, r);
#else
    return std::ranges::equal(s | std::views::take(half_size), r);
#endif
}

// Integer version - use decimal representation
template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n) noexcept
{
    // a trailing zero disqualifies, as we ignore leading zeros
    if (n == 0) { return true; }
    if (n % 10 == 0) { return false; }

    Number r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        if (r == n) { return true; }
        n /= 10;
    }
    return r == n;
}

// AdaptorRange overloadversion for(matches stringstrings literalsand string-views)
template<typenameconstexpr Char,bool is_palindrome(std::size_tranges::bidirectional_range N>auto&& s) noexcept
constexpr{
 bool is_palindrome  // We round down, because we can ignore a middle char (Charit will always match itself)
    auto const half_size = std::ranges::distance(&s)[N]s) noexcept/ 2;
{    auto rev_right = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return is_palindrome(std::basic_string_view{ranges::starts_with(s, N-1}rev_right);
}
#else
// Adaptor overload for other stringauto types
template<typenameleft String>
= s | std::views::take(half_size);
 // We can't usereturn std::convertible_toranges::equal(left, withoutrev_right);
#endif
}

// knowingAdaptor theoverload characterfor typestring literals
template<typename Char, std::size_t N>
constexpr requiresbool requiresis_palindrome(StringChar sconst (&s)[N]) noexcept
{
    return is_palindrome(std::basic_string_view({s, N-1});  
} 

// Adaptor overload for null-terminated strings
template<typename Char>
constexpr bool is_palindrome(String&&Char sconst *const &s) noexcept
{
    return is_palindrome(std::basic_string_view{std::forward<String>(s)});
}

#include <cctype>
#include <string>
#include <gtest/gtest.h>

using namespace std::literals;

TEST(is_palindrome_string, yes)
{
    EXPECT_TRUE(is_palindrome(""));
    EXPECT_TRUE(is_palindrome(L""s));
    EXPECT_TRUE(is_palindrome(L""sv));
    EXPECT_TRUE(is_palindrome("a"sv));
    EXPECT_TRUE(is_palindrome("aa"));
    EXPECT_TRUE(is_palindrome("aba"sv));
    EXPECT_TRUE(is_palindrome(L"abcba"sv));
    EXPECT_TRUE(is_palindrome("ab\0ba"));
    EXPECT_TRUE(is_palindrome("ab\0ba"sv));
    EXPECT_TRUE(is_palindrome(L"ab\0ba"s));
    {
        const char *s = "aa\0bb"; // \0 terminates this one
        EXPECT_TRUE(is_palindrome(s));
    }
}

TEST(is_palindrome_string, no)
{
    EXPECT_FALSE(is_palindrome("ab"));
    EXPECT_FALSE(is_palindrome(L"ab"sv));
    EXPECT_FALSE(is_palindrome("abc"));
    EXPECT_FALSE(is_palindrome("abca"));
    EXPECT_FALSE(is_palindrome("aab"));
    EXPECT_FALSE(is_palindrome("aa\0"));
    EXPECT_FALSE(is_palindrome(u8"abcab"sv));
    {
        const char *s = "ab\0ba"; // \0 terminates this one
        EXPECT_FALSE(is_palindrome(s));
    }
}

TEST(is_palindrome_int, yes)
{
    EXPECT_TRUE(is_palindrome(0ul));
    EXPECT_TRUE(is_palindrome(1u));
    EXPECT_TRUE(is_palindrome(11u));
    EXPECT_TRUE(is_palindrome(101u));
    EXPECT_TRUE(is_palindrome(1001u));
    EXPECT_TRUE(is_palindrome(121u));
    EXPECT_TRUE(is_palindrome(12345678987654321ull));
    EXPECT_TRUE(is_palindrome(123456789987654321ull));
}

TEST(is_palindrome_int, no)
{
    EXPECT_FALSE(is_palindrome(12u));
    EXPECT_FALSE(is_palindrome(112u));
    EXPECT_FALSE(is_palindrome(110u));
}

// A useful view for mixed-case sentence palindromes
auto constexpr palindrome_view =
    std::views::filter([](unsigned char c){ return std::isalnum(c); }) |
    std::views::transform([](unsigned char c){ return static_cast<char>(std::toupper(c)); });

TEST(is_palindrome_sentence, yes)
{
    EXPECT_TRUE(is_palindrome("A man, a plan, a canal: Panama!"sv | palindrome_view));
}

#include <algorithm>
#include <concepts>
#include <ranges>
#include <string_view>
#include <utility>

// Start with string-view version
template<typename Char, typename Traits>
constexpr bool is_palindrome(std::basic_string_view<Char,Traits> const s) noexcept
{
    // We round down, because we can ignore a middle char (it will always match itself)
    auto const half_size = s.size() / 2;
    auto const r = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return std::ranges::starts_with(s, r);
#else
    return std::ranges::equal(s | std::views::take(half_size), r);
#endif
}

// Integer version - use decimal representation
template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n) noexcept
{
    // a trailing zero disqualifies, as we ignore leading zeros
    if (n == 0) { return true; }
    if (n % 10 == 0) { return false; }

    Number r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        if (r == n) { return true; }
        n /= 10;
    }
    return r == n;
}

// Adaptor overload for string literals
template<typename Char, std::size_t N>
constexpr bool is_palindrome(Char const (&s)[N]) noexcept
{
    return is_palindrome(std::basic_string_view{s, N-1});
}

// Adaptor overload for other string types
template<typename String>
    // We can't use std::convertible_to without knowing the character type
    requires requires(String s) { std::basic_string_view(s); }
constexpr bool is_palindrome(String&& s) noexcept
{
    return is_palindrome(std::basic_string_view{std::forward<String>(s)});
}

#include <string>
#include <gtest/gtest.h>

using namespace std::literals;

TEST(is_palindrome_string, yes)
{
    EXPECT_TRUE(is_palindrome(""));
    EXPECT_TRUE(is_palindrome(L""s));
    EXPECT_TRUE(is_palindrome(L""sv));
    EXPECT_TRUE(is_palindrome("a"sv));
    EXPECT_TRUE(is_palindrome("aa"));
    EXPECT_TRUE(is_palindrome("aba"sv));
    EXPECT_TRUE(is_palindrome(L"abcba"sv));
    EXPECT_TRUE(is_palindrome("ab\0ba"));
    EXPECT_TRUE(is_palindrome("ab\0ba"sv));
    EXPECT_TRUE(is_palindrome(L"ab\0ba"s));
    {
        const char *s = "aa\0bb"; // \0 terminates this one
        EXPECT_TRUE(is_palindrome(s));
    }
}

TEST(is_palindrome_string, no)
{
    EXPECT_FALSE(is_palindrome("ab"));
    EXPECT_FALSE(is_palindrome(L"ab"sv));
    EXPECT_FALSE(is_palindrome("abc"));
    EXPECT_FALSE(is_palindrome("abca"));
    EXPECT_FALSE(is_palindrome("aab"));
    EXPECT_FALSE(is_palindrome("aa\0"));
    EXPECT_FALSE(is_palindrome(u8"abcab"sv));
    {
        const char *s = "ab\0ba"; // \0 terminates this one
        EXPECT_FALSE(is_palindrome(s));
    }
}

TEST(is_palindrome_int, yes)
{
    EXPECT_TRUE(is_palindrome(0ul));
    EXPECT_TRUE(is_palindrome(1u));
    EXPECT_TRUE(is_palindrome(11u));
    EXPECT_TRUE(is_palindrome(101u));
    EXPECT_TRUE(is_palindrome(1001u));
    EXPECT_TRUE(is_palindrome(121u));
    EXPECT_TRUE(is_palindrome(12345678987654321ull));
    EXPECT_TRUE(is_palindrome(123456789987654321ull));
}

TEST(is_palindrome_int, no)
{
    EXPECT_FALSE(is_palindrome(12u));
    EXPECT_FALSE(is_palindrome(112u));
    EXPECT_FALSE(is_palindrome(110u));
}

#include <algorithm>
#include <concepts>
#include <ranges>
#include <string_view>

// Integer version - use decimal representation
template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n) noexcept
{
    // a trailing zero disqualifies, as we ignore leading zeros
    if (n == 0) { return true; }
    if (n % 10 == 0) { return false; }

    Number r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        if (r == n) { return true; }
        n /= 10;
    }
    return r == n;
}

// Range version (matches strings and string-views)
constexpr bool is_palindrome(std::ranges::bidirectional_range auto&& s) noexcept
{
    // We round down, because we can ignore a middle char (it will always match itself)
    auto const half_size = std::ranges::distance(s) / 2;
    auto rev_right = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return std::ranges::starts_with(s, rev_right);
#else
    auto left = s | std::views::take(half_size);
    return std::ranges::equal(left, rev_right);
#endif
}

// Adaptor overload for string literals
template<typename Char, std::size_t N>
constexpr bool is_palindrome(Char const (&s)[N]) noexcept
{
    return is_palindrome(std::basic_string_view{s, N-1}); 
} 

// Adaptor overload for null-terminated strings
template<typename Char>
constexpr bool is_palindrome(Char const *const &s) noexcept
{
    return is_palindrome(std::basic_string_view{s});
}

#include <cctype>
#include <string>
#include <gtest/gtest.h>

using namespace std::literals;

TEST(is_palindrome_string, yes)
{
    EXPECT_TRUE(is_palindrome(""));
    EXPECT_TRUE(is_palindrome(L""s));
    EXPECT_TRUE(is_palindrome(L""sv));
    EXPECT_TRUE(is_palindrome("a"sv));
    EXPECT_TRUE(is_palindrome("aa"));
    EXPECT_TRUE(is_palindrome("aba"sv));
    EXPECT_TRUE(is_palindrome(L"abcba"sv));
    EXPECT_TRUE(is_palindrome("ab\0ba"));
    EXPECT_TRUE(is_palindrome("ab\0ba"sv));
    EXPECT_TRUE(is_palindrome(L"ab\0ba"s));
    {
        const char *s = "aa\0bb"; // \0 terminates this one
        EXPECT_TRUE(is_palindrome(s));
    }
}

TEST(is_palindrome_string, no)
{
    EXPECT_FALSE(is_palindrome("ab"));
    EXPECT_FALSE(is_palindrome(L"ab"sv));
    EXPECT_FALSE(is_palindrome("abc"));
    EXPECT_FALSE(is_palindrome("abca"));
    EXPECT_FALSE(is_palindrome("aab"));
    EXPECT_FALSE(is_palindrome("aa\0"));
    EXPECT_FALSE(is_palindrome(u8"abcab"sv));
    {
        const char *s = "ab\0ba"; // \0 terminates this one
        EXPECT_FALSE(is_palindrome(s));
    }
}

TEST(is_palindrome_int, yes)
{
    EXPECT_TRUE(is_palindrome(0ul));
    EXPECT_TRUE(is_palindrome(1u));
    EXPECT_TRUE(is_palindrome(11u));
    EXPECT_TRUE(is_palindrome(101u));
    EXPECT_TRUE(is_palindrome(1001u));
    EXPECT_TRUE(is_palindrome(121u));
    EXPECT_TRUE(is_palindrome(12345678987654321ull));
    EXPECT_TRUE(is_palindrome(123456789987654321ull));
}

TEST(is_palindrome_int, no)
{
    EXPECT_FALSE(is_palindrome(12u));
    EXPECT_FALSE(is_palindrome(112u));
    EXPECT_FALSE(is_palindrome(110u));
}

// A useful view for mixed-case sentence palindromes
auto constexpr palindrome_view =
    std::views::filter([](unsigned char c){ return std::isalnum(c); }) |
    std::views::transform([](unsigned char c){ return static_cast<char>(std::toupper(c)); });

TEST(is_palindrome_sentence, yes)
{
    EXPECT_TRUE(is_palindrome("A man, a plan, a canal: Panama!"sv | palindrome_view));
}

Post Undeleted by Toby Speight

occurred Jan 16 at 13:32

Post Deleted by Toby Speight

occurred Jan 16 at 8:45

Source Link

asked Jan 16 at 8:42

Toby Speight

81.8k
14
101
309

Palindrome predicate

A standard beginner problem is to determine whether a particular input is palindromic, i.e. reads the same in reverse as it does forwards.

I thought it might be fun to provide a distinctly non-beginner solution to this problem, so here's a version that is hugely over-engineered for a homework answer.

#include <algorithm>
#include <concepts>
#include <ranges>
#include <string_view>
#include <utility>

// Start with string-view version
template<typename Char, typename Traits>
constexpr bool is_palindrome(std::basic_string_view<Char,Traits> const s) noexcept
{
    // We round down, because we can ignore a middle char (it will always match itself)
    auto const half_size = s.size() / 2;
    auto const r = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return std::ranges::starts_with(s, r);
#else
    return std::ranges::equal(s | std::views::take(half_size), r);
#endif
}

// Integer version - use decimal representation
template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n) noexcept
{
    // a trailing zero disqualifies, as we ignore leading zeros
    if (n == 0) { return true; }
    if (n % 10 == 0) { return false; }

    Number r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        if (r == n) { return true; }
        n /= 10;
    }
    return r == n;
}

// Adaptor overload for string literals
template<typename Char, std::size_t N>
constexpr bool is_palindrome(Char const (&s)[N]) noexcept
{
    return is_palindrome(std::basic_string_view{s, N-1});
}

// Adaptor overload for other string types
template<typename String>
    // We can't use std::convertible_to without knowing the character type
    requires requires(String s) { std::basic_string_view(s); }
constexpr bool is_palindrome(String&& s) noexcept
{
    return is_palindrome(std::basic_string_view{std::forward<String>(s)});
}

Of course, like all good homework, it's properly tested:

#include <string>
#include <gtest/gtest.h>

using namespace std::literals;

TEST(is_palindrome_string, yes)
{
    EXPECT_TRUE(is_palindrome(""));
    EXPECT_TRUE(is_palindrome(L""s));
    EXPECT_TRUE(is_palindrome(L""sv));
    EXPECT_TRUE(is_palindrome("a"sv));
    EXPECT_TRUE(is_palindrome("aa"));
    EXPECT_TRUE(is_palindrome("aba"sv));
    EXPECT_TRUE(is_palindrome(L"abcba"sv));
    EXPECT_TRUE(is_palindrome("ab\0ba"));
    EXPECT_TRUE(is_palindrome("ab\0ba"sv));
    EXPECT_TRUE(is_palindrome(L"ab\0ba"s));
    {
        const char *s = "aa\0bb"; // \0 terminates this one
        EXPECT_TRUE(is_palindrome(s));
    }
}

TEST(is_palindrome_string, no)
{
    EXPECT_FALSE(is_palindrome("ab"));
    EXPECT_FALSE(is_palindrome(L"ab"sv));
    EXPECT_FALSE(is_palindrome("abc"));
    EXPECT_FALSE(is_palindrome("abca"));
    EXPECT_FALSE(is_palindrome("aab"));
    EXPECT_FALSE(is_palindrome("aa\0"));
    EXPECT_FALSE(is_palindrome(u8"abcab"sv));
    {
        const char *s = "ab\0ba"; // \0 terminates this one
        EXPECT_FALSE(is_palindrome(s));
    }
}

TEST(is_palindrome_int, yes)
{
    EXPECT_TRUE(is_palindrome(0ul));
    EXPECT_TRUE(is_palindrome(1u));
    EXPECT_TRUE(is_palindrome(11u));
    EXPECT_TRUE(is_palindrome(101u));
    EXPECT_TRUE(is_palindrome(1001u));
    EXPECT_TRUE(is_palindrome(121u));
    EXPECT_TRUE(is_palindrome(12345678987654321ull));
    EXPECT_TRUE(is_palindrome(123456789987654321ull));
}

TEST(is_palindrome_int, no)
{
    EXPECT_FALSE(is_palindrome(12u));
    EXPECT_FALSE(is_palindrome(112u));
    EXPECT_FALSE(is_palindrome(110u));
}

c++palindrome

Stack Exchange Network

Return to Question

Palindrome predicate