2
\$\begingroup\$

Adding another level to my previous question on 'normal' palindrome identification, in this one I'm interested in identifying genetic palindromes. Here's my attempt:

#include <iterator>
#include <algorithm>
#include <array>

namespace detail
{
    static constexpr std::array<char, 128> complement_table
    {
        4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
        4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
        4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
        4, 4,  4, 4,  4,  4,  4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
        4, 84, 4, 71, 4,  4,  4, 67, 4, 4, 4, 4,  4, 4, 78, 4,
        4, 4,  4, 4,  65, 65, 4, 4,  4, 4, 4, 4,  4, 4, 4,  4,
        4, 84, 4, 71, 4,  4,  4, 67, 4, 4, 4, 4,  4, 4, 4,  4,
        4, 4,  4, 4,  65, 65, 4, 4,  4, 4, 4, 4,  4, 4, 4,  4
    };
} // namespace detail

inline constexpr char complement(const char base)
{
    return detail::complement_table[base];
}

namespace detail
{
    template <typename RandomIt>
    bool is_palindromic(RandomIt first, RandomIt last, std::random_access_iterator_tag)
    {
        if (first == last) return true;

        const auto size = std::distance(first, last);

        if (size % 2 != 0) return false;

        return std::equal(first, std::next(first, size / 2), std::make_reverse_iterator(last),
                          [] (const char lhs, const char rhs) {
                              return lhs == complement(rhs);
                          });
    }

    template <typename BidirIt>
    bool is_palindromic(BidirIt first, BidirIt last, std::bidirectional_iterator_tag)
    {
        if (first == last)   return true;
        if (first == --last) return false;

        for (; first != last; ++first, --last) {
            if (*first != complement(*last)) return false;
            if (std::next(first) == last) return true;
        }

        return false;
    }
} // namespace detail

template <typename BidirIt>
bool is_palindromic(BidirIt first, BidirIt last)
{
    return detail::is_palindromic(first, last, typename std::iterator_traits<BidirIt>::iterator_category {});
}

template <typename SequenceType>
bool is_palindromic(const SequenceType& sequence)
{
    return is_palindromic(std::cbegin(sequence), std::cend(sequence));
}

Used as such:

#include <iostream>
#include <string>
#include <list>

int main()
{
    std::cout << std::boolalpha;
    std::string str {"ACCTAGGT"};
    std::cout << is_palindromic(str) << std::endl;
    std::list<char> lst {str.cbegin(), str.cend()};
    std::cout << is_palindromic(lst) << std::endl;
    return 0;
}

Performance is my primary concern here. Comments and suggested improvements are welcome!

\$\endgroup\$
  • \$\begingroup\$ I see that "N" is its own complement, but there's no compliment for "n". Is that intentional? \$\endgroup\$ – user1118321 Jan 28 '16 at 5:28
  • \$\begingroup\$ In fact, will your table work if the string is of mixed or all lower case? For example, "A" has a compliment of "T" and vice-versa, but "a" has a complement of "T" and "t" a compliment of "A". It seems like if the string is all lowercase, it won't work properly. \$\endgroup\$ – user1118321 Jan 28 '16 at 5:38
  • \$\begingroup\$ @user1118321 Fair point, I'm also missing other amino acid codes (H, D, B, etc). I'm not really sure if there's an accepted way of dealing with lower case / mixed codes. In my experience, lower case codes are rarely used, and usually a marker of some sort (e.g. areas of low complexity). \$\endgroup\$ – Daniel Jan 28 '16 at 8:03
  • \$\begingroup\$ This definitely doesn't work on non-ASCII systems, though I guess you probably don't care about them. \$\endgroup\$ – T.C. Feb 1 '16 at 4:40
  • \$\begingroup\$ Re the above comments: The proper primitive here isn't char complement(char); it's bool are_complementary(char, char). If you rewrite the code that way, I'll do a style review. ;) \$\endgroup\$ – Quuxplusone Feb 1 '16 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.