Advertisement
Guest User

Standard like palindrome

a guest
Mar 10th, 2015
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. /////////////////////////////////////////////////// Header
  2.  
  3. #pragma once
  4.  
  5. #include <iterator>
  6. #include <utility>
  7. #include <cassert>
  8.  
  9. namespace palindrome_details
  10. {
  11.     template<class T> using diff = typename std::iterator_traits<T>::difference_type;
  12.    
  13.     template<class Iter, class BIter>
  14.     diff<Iter> palindrome(Iter left, BIter right, diff<Iter> const n)
  15.     {
  16.         for (auto i = 0; i < n; ++i)
  17.         {
  18.             if (*left++ != *right++)
  19.             {
  20.                 return i;
  21.             }
  22.         }
  23.         return -1;
  24.     }
  25. }
  26.  
  27. template<class Iter>
  28. std::pair<Iter, Iter> palindrome(Iter const begin, Iter const end)
  29. {
  30.     auto const n = palindrome_details::palindrome(begin, std::reverse_iterator<Iter>(end), std::distance(begin, end) / 2);
  31.     if (n < 0)
  32.     {
  33.         return make_pair(end, end);
  34.     }
  35.     return make_pair(begin + n, end - (n + 1));
  36. }
  37.  
  38. template<class Iter>
  39. inline bool is_palindrome(Iter const begin, Iter const end)
  40. {
  41.     return palindrome(begin, end).first == end;
  42. }
  43.  
  44. /////////////////////////////////////////////////// Source
  45.  
  46. #include "palindrome.h"
  47. #define all(c) std::begin(c), std::end(c)
  48.  
  49. void test_palindrome()
  50. {
  51.     cout << "Testing palindrome...\n";
  52.    
  53.     vector<int> itis = { 2, 3, 5, 7, 5, 3, 2 };
  54.     assert(is_palindrome(all(itis)));
  55.    
  56.     itis.erase(find(all(itis), 7));
  57.     assert(is_palindrome(all(itis)));
  58.    
  59.     auto three = find(all(itis), 3);
  60.     *three = 0;
  61.     assert(!is_palindrome(all(itis)));
  62.     auto problem = palindrome(all(itis));
  63.     assert(problem.first == three);
  64.     *problem.second = *problem.first;
  65.     assert(is_palindrome(problem.first, problem.second + 1));
  66.    
  67.     itis.erase(itis.begin() + 1, itis.end() - 1);
  68.     assert(is_palindrome(all(itis)));
  69.    
  70.     itis.erase(itis.begin());
  71.     assert(is_palindrome(all(itis)));
  72.    
  73.     itis.clear();
  74.     assert(is_palindrome(all(itis)));
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement