1 | // Copyright (c) 2010 Nuovation System Designs, LLC |
---|---|

2 | // Grant Erickson <gerickson@nuovations.com> |

3 | // |

4 | // Reworked somewhat by Marshall Clow; August 2010 |

5 | // |

6 | // Distributed under the Boost Software License, Version 1.0. (See |

7 | // accompanying file LICENSE_1_0.txt or copy at |

8 | // http://www.boost.org/LICENSE_1_0.txt) |

9 | // |

10 | // See http://www.boost.org/ for latest version. |

11 | // |

12 | |

13 | #ifndef BOOST_ALGORITHM_ORDERED_HPP |

14 | #define BOOST_ALGORITHM_ORDERED_HPP |

15 | |

16 | #include <algorithm> |

17 | #include <functional> |

18 | #include <iterator> |

19 | |

20 | #include <boost/range/begin.hpp> |

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

22 | |

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

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

25 | #include <boost/mpl/identity.hpp> |

26 | |

27 | namespace boost { namespace algorithm { |

28 | |

29 | /// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) |

30 | /// \return the point in the sequence [first, last) where the elements are unordered |

31 | /// (according to the comparison predicate 'p'). |

32 | /// |

33 | /// \param first The start of the sequence to be tested. |

34 | /// \param last One past the end of the sequence |

35 | /// \param p A binary predicate that returns true if two elements are ordered. |

36 | /// |

37 | template <typename ForwardIterator, typename Pred> |

38 | ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) |

39 | { |

40 | if ( first == last ) return last; // the empty sequence is ordered |

41 | ForwardIterator next = first; |

42 | while ( ++next != last ) |

43 | { |

44 | if ( p ( *next, *first )) |

45 | return next; |

46 | first = next; |

47 | } |

48 | return last; |

49 | } |

50 | |

51 | /// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last ) |

52 | /// \return the point in the sequence [first, last) where the elements are unordered |

53 | /// |

54 | /// \param first The start of the sequence to be tested. |

55 | /// \param last One past the end of the sequence |

56 | /// |

57 | template <typename ForwardIterator> |

58 | ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ) |

59 | { |

60 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; |

61 | return boost::algorithm::is_sorted_until ( first, last, std::less<value_type>()); |

62 | } |

63 | |

64 | |

65 | /// \fn is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) |

66 | /// \return whether or not the entire sequence is sorted |

67 | /// |

68 | /// \param first The start of the sequence to be tested. |

69 | /// \param last One past the end of the sequence |

70 | /// \param p A binary predicate that returns true if two elements are ordered. |

71 | /// |

72 | template <typename ForwardIterator, typename Pred> |

73 | bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) |

74 | { |

75 | return boost::algorithm::is_sorted_until (first, last, p) == last; |

76 | } |

77 | |

78 | /// \fn is_sorted ( ForwardIterator first, ForwardIterator last ) |

79 | /// \return whether or not the entire sequence is sorted |

80 | /// |

81 | /// \param first The start of the sequence to be tested. |

82 | /// \param last One past the end of the sequence |

83 | /// |

84 | template <typename ForwardIterator> |

85 | bool is_sorted ( ForwardIterator first, ForwardIterator last ) |

86 | { |

87 | return boost::algorithm::is_sorted_until (first, last) == last; |

88 | } |

89 | |

90 | /// |

91 | /// -- Range based versions of the C++11 functions |

92 | /// |

93 | |

94 | /// \fn is_sorted_until ( const R &range, Pred p ) |

95 | /// \return the point in the range R where the elements are unordered |

96 | /// (according to the comparison predicate 'p'). |

97 | /// |

98 | /// \param range The range to be tested. |

99 | /// \param p A binary predicate that returns true if two elements are ordered. |

100 | /// |

101 | template <typename R, typename Pred> |

102 | typename boost::lazy_disable_if_c< |

103 | boost::is_same<R, Pred>::value, |

104 | typename boost::range_iterator<const R> |

105 | >::type is_sorted_until ( const R &range, Pred p ) |

106 | { |

107 | return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range ), p ); |

108 | } |

109 | |

110 | |

111 | /// \fn is_sorted_until ( const R &range ) |

112 | /// \return the point in the range R where the elements are unordered |

113 | /// |

114 | /// \param range The range to be tested. |

115 | /// |

116 | template <typename R> |

117 | typename boost::range_iterator<const R>::type is_sorted_until ( const R &range ) |

118 | { |

119 | return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range )); |

120 | } |

121 | |

122 | /// \fn is_sorted ( const R &range, Pred p ) |

123 | /// \return whether or not the entire range R is sorted |

124 | /// (according to the comparison predicate 'p'). |

125 | /// |

126 | /// \param range The range to be tested. |

127 | /// \param p A binary predicate that returns true if two elements are ordered. |

128 | /// |

129 | template <typename R, typename Pred> |

130 | typename boost::lazy_disable_if_c< boost::is_same<R, Pred>::value, boost::mpl::identity<bool> >::type |

131 | is_sorted ( const R &range, Pred p ) |

132 | { |

133 | return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range ), p ); |

134 | } |

135 | |

136 | |

137 | /// \fn is_sorted ( const R &range ) |

138 | /// \return whether or not the entire range R is sorted |

139 | /// |

140 | /// \param range The range to be tested. |

141 | /// |

142 | template <typename R> |

143 | bool is_sorted ( const R &range ) |

144 | { |

145 | return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range )); |

146 | } |

147 | |

148 | |

149 | /// |

150 | /// -- Range based versions of the C++11 functions |

151 | /// |

152 | |

153 | /// \fn is_increasing ( ForwardIterator first, ForwardIterator last ) |

154 | /// \return true if the entire sequence is increasing; i.e, each item is greater than or |

155 | /// equal to the previous one. |

156 | /// |

157 | /// \param first The start of the sequence to be tested. |

158 | /// \param last One past the end of the sequence |

159 | /// |

160 | /// \note This function will return true for sequences that contain items that compare |

161 | /// equal. If that is not what you intended, you should use is_strictly_increasing instead. |

162 | template <typename ForwardIterator> |

163 | bool is_increasing ( ForwardIterator first, ForwardIterator last ) |

164 | { |

165 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; |

166 | return boost::algorithm::is_sorted (first, last, std::less<value_type>()); |

167 | } |

168 | |

169 | |

170 | /// \fn is_increasing ( const R &range ) |

171 | /// \return true if the entire sequence is increasing; i.e, each item is greater than or |

172 | /// equal to the previous one. |

173 | /// |

174 | /// \param range The range to be tested. |

175 | /// |

176 | /// \note This function will return true for sequences that contain items that compare |

177 | /// equal. If that is not what you intended, you should use is_strictly_increasing instead. |

178 | template <typename R> |

179 | bool is_increasing ( const R &range ) |

180 | { |

181 | return is_increasing ( boost::begin ( range ), boost::end ( range )); |

182 | } |

183 | |

184 | |

185 | |

186 | /// \fn is_decreasing ( ForwardIterator first, ForwardIterator last ) |

187 | /// \return true if the entire sequence is decreasing; i.e, each item is less than |

188 | /// or equal to the previous one. |

189 | /// |

190 | /// \param first The start of the sequence to be tested. |

191 | /// \param last One past the end of the sequence |

192 | /// |

193 | /// \note This function will return true for sequences that contain items that compare |

194 | /// equal. If that is not what you intended, you should use is_strictly_decreasing instead. |

195 | template <typename ForwardIterator> |

196 | bool is_decreasing ( ForwardIterator first, ForwardIterator last ) |

197 | { |

198 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; |

199 | return boost::algorithm::is_sorted (first, last, std::greater<value_type>()); |

200 | } |

201 | |

202 | /// \fn is_decreasing ( const R &range ) |

203 | /// \return true if the entire sequence is decreasing; i.e, each item is less than |

204 | /// or equal to the previous one. |

205 | /// |

206 | /// \param range The range to be tested. |

207 | /// |

208 | /// \note This function will return true for sequences that contain items that compare |

209 | /// equal. If that is not what you intended, you should use is_strictly_decreasing instead. |

210 | template <typename R> |

211 | bool is_decreasing ( const R &range ) |

212 | { |

213 | return is_decreasing ( boost::begin ( range ), boost::end ( range )); |

214 | } |

215 | |

216 | |

217 | |

218 | /// \fn is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) |

219 | /// \return true if the entire sequence is strictly increasing; i.e, each item is greater |

220 | /// than the previous one |

221 | /// |

222 | /// \param first The start of the sequence to be tested. |

223 | /// \param last One past the end of the sequence |

224 | /// |

225 | /// \note This function will return false for sequences that contain items that compare |

226 | /// equal. If that is not what you intended, you should use is_increasing instead. |

227 | template <typename ForwardIterator> |

228 | bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) |

229 | { |

230 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; |

231 | return boost::algorithm::is_sorted (first, last, std::less_equal<value_type>()); |

232 | } |

233 | |

234 | /// \fn is_strictly_increasing ( const R &range ) |

235 | /// \return true if the entire sequence is strictly increasing; i.e, each item is greater |

236 | /// than the previous one |

237 | /// |

238 | /// \param range The range to be tested. |

239 | /// |

240 | /// \note This function will return false for sequences that contain items that compare |

241 | /// equal. If that is not what you intended, you should use is_increasing instead. |

242 | template <typename R> |

243 | bool is_strictly_increasing ( const R &range ) |

244 | { |

245 | return is_strictly_increasing ( boost::begin ( range ), boost::end ( range )); |

246 | } |

247 | |

248 | |

249 | /// \fn is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) |

250 | /// \return true if the entire sequence is strictly decreasing; i.e, each item is less than |

251 | /// the previous one |

252 | /// |

253 | /// \param first The start of the sequence to be tested. |

254 | /// \param last One past the end of the sequence |

255 | /// |

256 | /// \note This function will return false for sequences that contain items that compare |

257 | /// equal. If that is not what you intended, you should use is_decreasing instead. |

258 | template <typename ForwardIterator> |

259 | bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) |

260 | { |

261 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; |

262 | return boost::algorithm::is_sorted (first, last, std::greater_equal<value_type>()); |

263 | } |

264 | |

265 | /// \fn is_strictly_decreasing ( const R &range ) |

266 | /// \return true if the entire sequence is strictly decreasing; i.e, each item is less than |

267 | /// the previous one |

268 | /// |

269 | /// \param range The range to be tested. |

270 | /// |

271 | /// \note This function will return false for sequences that contain items that compare |

272 | /// equal. If that is not what you intended, you should use is_decreasing instead. |

273 | template <typename R> |

274 | bool is_strictly_decreasing ( const R &range ) |

275 | { |

276 | return is_strictly_decreasing ( boost::begin ( range ), boost::end ( range )); |

277 | } |

278 | |

279 | }} // namespace boost |

280 | |

281 | #endif // BOOST_ALGORITHM_ORDERED_HPP |

282 |