1 | /* |
---|---|

2 | Copyright (c) Marshall Clow 2014. |

3 | |

4 | Distributed under the Boost Software License, Version 1.0. (See accompanying |

5 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |

6 | */ |

7 | |

8 | /// \file is_permutation.hpp |

9 | /// \brief Is a sequence a permutation of another sequence (four iterator versions) |

10 | /// \author Marshall Clow |

11 | |

12 | #ifndef BOOST_ALGORITHM_IS_PERMUTATION14_HPP |

13 | #define BOOST_ALGORITHM_IS_PERMUTATION14_HPP |

14 | |

15 | #include <algorithm> // for std::less, tie, mismatch and is_permutation (if available) |

16 | #include <utility> // for std::make_pair |

17 | #include <functional> // for std::equal_to |

18 | #include <iterator> |

19 | |

20 | #include <boost/algorithm/cxx11/is_permutation.hpp> |

21 | #include <boost/algorithm/cxx14/mismatch.hpp> |

22 | |

23 | namespace boost { namespace algorithm { |

24 | |

25 | /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, |

26 | /// ForwardIterator2 first2, ForwardIterator2 last2 ) |

27 | /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 |

28 | /// |

29 | /// \param first1 The start of the input sequence |

30 | /// \param last2 One past the end of the input sequence |

31 | /// \param first2 The start of the second sequence |

32 | /// \param last1 One past the end of the second sequence |

33 | /// \note This function is part of the C++2014 standard library. |

34 | /// We will use the standard one if it is available, |

35 | /// otherwise we have our own implementation. |

36 | template< class ForwardIterator1, class ForwardIterator2 > |

37 | bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, |

38 | ForwardIterator2 first2, ForwardIterator2 last2 ) |

39 | { |

40 | // How should I deal with the idea that ForwardIterator1::value_type |

41 | // and ForwardIterator2::value_type could be different? Define my own comparison predicate? |

42 | std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch |

43 | ( first1, last1, first2, last2 ); |

44 | if ( eq.first == last1 && eq.second == last2) |

45 | return true; |

46 | return boost::algorithm::detail::is_permutation_tag ( |

47 | eq.first, last1, eq.second, last2, |

48 | std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (), |

49 | typename std::iterator_traits<ForwardIterator1>::iterator_category (), |

50 | typename std::iterator_traits<ForwardIterator2>::iterator_category ()); |

51 | } |

52 | |

53 | /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, |

54 | /// ForwardIterator2 first2, ForwardIterator2 last2, |

55 | /// BinaryPredicate p ) |

56 | /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 |

57 | /// |

58 | /// \param first1 The start of the input sequence |

59 | /// \param last1 One past the end of the input sequence |

60 | /// \param first2 The start of the second sequence |

61 | /// \param last2 One past the end of the second sequence |

62 | /// \param pred The predicate to compare elements with |

63 | /// |

64 | /// \note This function is part of the C++2014 standard library. |

65 | /// We will use the standard one if it is available, |

66 | /// otherwise we have our own implementation. |

67 | template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > |

68 | bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, |

69 | ForwardIterator2 first2, ForwardIterator2 last2, |

70 | BinaryPredicate pred ) |

71 | { |

72 | std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch |

73 | ( first1, last1, first2, last2, pred ); |

74 | if ( eq.first == last1 && eq.second == last2) |

75 | return true; |

76 | return boost::algorithm::detail::is_permutation_tag ( |

77 | first1, last1, first2, last2, pred, |

78 | typename std::iterator_traits<ForwardIterator1>::iterator_category (), |

79 | typename std::iterator_traits<ForwardIterator2>::iterator_category ()); |

80 | } |

81 | |

82 | }} |

83 | |

84 | #endif // BOOST_ALGORITHM_IS_PERMUTATION14_HPP |

85 |