boost/algorithm/is_palindrome.hpp

   1 /*
   2   Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.com>, 2016
   3
   4   Distributed under the Boost Software License, Version 1.0. (See
   5   accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt)
   7
   8   See http://www.boost.org/ for latest version.
   9 */
  10
  11 /// \file  is_palindrome.hpp
  12 /// \brief Checks the input sequence on palindrome.
  13 /// \author Alexander Zaitsev
  14
  15 #ifndef BOOST_ALGORITHM_IS_PALINDROME_HPP
  16 #define BOOST_ALGORITHM_IS_PALINDROME_HPP
  17
  18 #include <iterator>
  19 #include <functional>
  20 #include <cstring>
  21
  22 #include <boost/config.hpp>
  23 #include <boost/range/begin.hpp>
  24 #include <boost/range/end.hpp>
  25
  26 namespace boost {  namespace algorithm {
  27
  28 /// \fn is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end, Predicate p )
  29 /// \return true if the entire sequence is palindrome
  30 ///
  31 /// \param begin    The start of the input sequence
  32 /// \param end          One past the end of the input sequence
  33 /// \param p        A predicate used to compare the values.
  34 ///
  35 /// \note This function will return true for empty sequences and for palindromes.
  36 ///     For other sequences function will return false.
  37 ///     Complexity: O(N).
  38 template <typename BidirectionalIterator, typename Predicate>
  39 bool is_palindrome(BidirectionalIterator begin, BidirectionalIterator end, Predicate p)
  40 {
  41     if(begin == end)
  42     {
  43         return true;
  44     }
  45
  46     --end;
  47     while(begin != end)
  48     {
  49         if(!p(*begin, *end))
  50         {
  51             return false;
  52         }
  53         ++begin;
  54         if(begin == end)
  55         {
  56             break;
  57         }
  58         --end;
  59     }
  60     return true;
  61 }
  62
  63 /// \fn is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end )
  64 /// \return true if the entire sequence is palindrome
  65 ///
  66 /// \param begin    The start of the input sequence
  67 /// \param end      One past the end of the input sequence
  68 ///
  69 /// \note This function will return true for empty sequences and for palindromes.
  70 ///     For other sequences function will return false.
  71 ///     Complexity: O(N).
  72 template <typename BidirectionalIterator>
  73 bool is_palindrome(BidirectionalIterator begin, BidirectionalIterator end)
  74 {
  75     return is_palindrome(begin, end,
  76                          std::equal_to<typename std::iterator_traits<BidirectionalIterator>::value_type> ());
  77 }
  78
  79 /// \fn is_palindrome ( const R& range )
  80 /// \return true if the entire sequence is palindrome
  81 ///
  82 /// \param range The range to be tested.
  83 ///
  84 /// \note This function will return true for empty sequences and for palindromes.
  85 ///     For other sequences function will return false.
  86 ///     Complexity: O(N).
  87 template <typename R>
  88 bool is_palindrome(const R& range)
  89 {
  90     return is_palindrome(boost::begin(range), boost::end(range));
  91 }
  92
  93 /// \fn is_palindrome ( const R& range, Predicate p )
  94 /// \return true if the entire sequence is palindrome
  95 ///
  96 /// \param range The range to be tested.
  97 /// \param p     A predicate used to compare the values.
  98 ///
  99 /// \note This function will return true for empty sequences and for palindromes.
 100 ///     For other sequences function will return false.
 101 ///     Complexity: O(N).
 102 template <typename R, typename Predicate>
 103 bool is_palindrome(const R& range, Predicate p)
 104 {
 105     return is_palindrome(boost::begin(range), boost::end(range), p);
 106 }
 107
 108 /// \fn is_palindrome ( const char* str )
 109 /// \return true if the entire sequence is palindrome
 110 ///
 111 /// \param str C-string to be tested.
 112 ///
 113 /// \note This function will return true for empty sequences and for palindromes.
 114 ///     For other sequences function will return false.
 115 ///     Complexity: O(N).
 116 bool is_palindrome(const char* str)
 117 {
 118     if(!str)
 119             return true;
 120     return is_palindrome(str, str + strlen(str));
 121 }
 122
 123 /// \fn is_palindrome ( const char* str, Predicate p )
 124 /// \return true if the entire sequence is palindrome
 125 ///
 126 /// \param str C-string to be tested.
 127 /// \param p   A predicate used to compare the values.
 128 ///
 129 /// \note This function will return true for empty sequences and for palindromes.
 130 ///     For other sequences function will return false.
 131 ///     Complexity: O(N).
 132 template<typename Predicate>
 133 bool is_palindrome(const char* str, Predicate p)
 134 {
 135     if(!str)
 136             return true;
 137     return is_palindrome(str, str + strlen(str), p);
 138 }
 139 }}
 140
 141 #endif // BOOST_ALGORITHM_IS_PALINDROME_HPP