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

2 | Copyright (c) Marshall Clow 2011-2012. |

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 |

10 | /// \author Marshall Clow |

11 | |

12 | #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP |

13 | #define BOOST_ALGORITHM_IS_PERMUTATION11_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/range/begin.hpp> |

21 | #include <boost/range/end.hpp> |

22 | #include <boost/utility/enable_if.hpp> |

23 | #include <boost/type_traits/is_same.hpp> |

24 | |

25 | namespace boost { namespace algorithm { |

26 | |

27 | /// \cond DOXYGEN_HIDE |

28 | namespace detail { |

29 | template <typename Predicate, typename Iterator> |

30 | struct value_predicate { |

31 | value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {} |

32 | |

33 | template <typename T1> |

34 | bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); } |

35 | private: |

36 | Predicate p_; |

37 | Iterator it_; |

38 | }; |

39 | |

40 | // Preconditions: |

41 | // 1. The sequences are the same length |

42 | // 2. Any common elements on the front have been removed (not necessary for correctness, just for performance) |

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

44 | bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1, |

45 | ForwardIterator2 first2, ForwardIterator2 last2, |

46 | BinaryPredicate p ) { |

47 | // for each unique value in the sequence [first1,last1), count how many times |

48 | // it occurs, and make sure it occurs the same number of times in [first2, last2) |

49 | for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) { |

50 | value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter ); |

51 | |

52 | /* For each value we haven't seen yet... */ |

53 | if ( std::find_if ( first1, iter, pred ) == iter ) { |

54 | std::size_t dest_count = std::count_if ( first2, last2, pred ); |

55 | if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred )) |

56 | return false; |

57 | } |

58 | } |

59 | |

60 | return true; |

61 | } |

62 | |

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

64 | bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1, |

65 | ForwardIterator2 first2, ForwardIterator2 last2, |

66 | BinaryPredicate p, |

67 | std::forward_iterator_tag, std::forward_iterator_tag ) { |

68 | |

69 | // Skip the common prefix (if any) |

70 | while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) { |

71 | ++first1; |

72 | ++first2; |

73 | } |

74 | if ( first1 != last1 && first2 != last2 ) |

75 | return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, |

76 | std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); |

77 | return first1 == last1 && first2 == last2; |

78 | } |

79 | |

80 | template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate> |

81 | bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1, |

82 | RandomAccessIterator2 first2, RandomAccessIterator2 last2, |

83 | BinaryPredicate p, |

84 | std::random_access_iterator_tag, std::random_access_iterator_tag ) { |

85 | // Cheap check |

86 | if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 )) |

87 | return false; |

88 | // Skip the common prefix (if any) |

89 | while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) { |

90 | ++first1; |

91 | ++first2; |

92 | } |

93 | |

94 | if ( first1 != last1 && first2 != last2 ) |

95 | return is_permutation_inner (first1, last1, first2, last2, p); |

96 | return first1 == last1 && first2 == last2; |

97 | } |

98 | |

99 | } |

100 | /// \endcond |

101 | |

102 | /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p ) |

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

104 | /// |

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

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

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

108 | /// \param p The predicate to compare elements with |

109 | /// |

110 | /// \note This function is part of the C++2011 standard library. |

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

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

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

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

115 | ForwardIterator2 first2, BinaryPredicate p ) |

116 | { |

117 | // Skip the common prefix (if any) |

118 | std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p); |

119 | first1 = eq.first; |

120 | first2 = eq.second; |

121 | if ( first1 != last1 ) { |

122 | // Create last2 |

123 | ForwardIterator2 last2 = first2; |

124 | std::advance ( last2, std::distance (first1, last1)); |

125 | return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p ); |

126 | } |

127 | |

128 | return true; |

129 | } |

130 | |

131 | /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) |

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

133 | /// |

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

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

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

137 | /// \note This function is part of the C++2011 standard library. |

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

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

140 | template< class ForwardIterator1, class ForwardIterator2 > |

141 | bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 ) |

142 | { |

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

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

145 | // Skip the common prefix (if any) |

146 | std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 ); |

147 | first1 = eq.first; |

148 | first2 = eq.second; |

149 | if ( first1 != last1 ) { |

150 | // Create last2 |

151 | ForwardIterator2 last2 = first2; |

152 | std::advance ( last2, std::distance (first1, last1)); |

153 | return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, |

154 | std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); |

155 | } |

156 | return true; |

157 | } |

158 | |

159 | |

160 | /// \fn is_permutation ( const Range &r, ForwardIterator first2 ) |

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

162 | /// |

163 | /// \param r The input range |

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

165 | template <typename Range, typename ForwardIterator> |

166 | bool is_permutation ( const Range &r, ForwardIterator first2 ) |

167 | { |

168 | return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 ); |

169 | } |

170 | |

171 | /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) |

172 | |

173 | /// |

174 | /// \param r The input range |

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

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

177 | /// |

178 | // Disable this template when the first two parameters are the same type |

179 | // That way the non-range version will be chosen. |

180 | template <typename Range, typename ForwardIterator, typename BinaryPredicate> |

181 | typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type |

182 | is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) |

183 | { |

184 | return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred ); |

185 | } |

186 | |

187 | }} |

188 | |

189 | #endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP |

190 |