1 // This file is part of the ustl library, an STL implementation.
3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4 // This file is free software, distributed under the MIT License.
8 // Implementation of STL algorithms with custom predicates.
10 // The function prototypes are copied
11 // exactly from the SGI version of STL documentation along with comments about
12 // their use. The code is NOT the same, though the functionality usually is.
15 #ifndef UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5
16 #define UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5
20 /// Copy_if copies elements from the range [first, last) to the range
21 /// [result, result + (last - first)) if pred(*i) returns true.
22 /// \ingroup MutatingAlgorithms
23 /// \ingroup PredicateAlgorithms
25 template <typename InputIterator
, typename OutputIterator
, typename Predicate
>
26 inline OutputIterator
copy_if (InputIterator first
, InputIterator last
, OutputIterator result
, Predicate pred
)
28 for (; first
!= last
; ++first
) {
37 /// Returns the first iterator i in the range [first, last) such that
38 /// pred(*i) is true. Returns last if no such iterator exists.
39 /// \ingroup SearchingAlgorithms
40 /// \ingroup PredicateAlgorithms
42 template <typename InputIterator
, typename Predicate
>
43 inline InputIterator
find_if (InputIterator first
, InputIterator last
, Predicate pred
)
45 while (first
!= last
&& !pred (*first
))
50 /// Returns the first iterator such that p(*i, *(i + 1)) == true.
51 /// \ingroup SearchingAlgorithms
52 /// \ingroup PredicateAlgorithms
54 template <typename ForwardIterator
, typename BinaryPredicate
>
55 inline ForwardIterator
adjacent_find (ForwardIterator first
, ForwardIterator last
, BinaryPredicate p
)
58 for (ForwardIterator prev
= first
; ++first
!= last
; ++ prev
)
59 if (p (*prev
, *first
))
64 /// Returns the pointer to the first pair of unequal elements.
65 /// \ingroup SearchingAlgorithms
66 /// \ingroup PredicateAlgorithms
68 template <typename InputIterator
, typename BinaryPredicate
>
69 inline pair
<InputIterator
,InputIterator
>
70 mismatch (InputIterator first1
, InputIterator last1
, InputIterator first2
, BinaryPredicate comp
)
72 while (first1
!= last1
&& comp(*first1
, *first2
))
74 return (make_pair (first1
, first2
));
77 /// Returns true if two ranges are equal.
78 /// This is an extension, present in uSTL and SGI STL.
79 /// \ingroup ConditionAlgorithms
80 /// \ingroup PredicateAlgorithms
82 template <typename InputIterator
, typename BinaryPredicate
>
83 inline bool equal (InputIterator first1
, InputIterator last1
, InputIterator first2
, BinaryPredicate comp
)
85 return (mismatch (first1
, last1
, first2
, comp
).first
== last1
);
88 /// Count_if finds the number of elements in [first, last) that satisfy the
89 /// predicate pred. More precisely, the first version of count_if returns the
90 /// number of iterators i in [first, last) such that pred(*i) is true.
91 /// \ingroup ConditionAlgorithms
92 /// \ingroup PredicateAlgorithms
94 template <typename InputIterator
, typename Predicate
>
95 inline size_t count_if (InputIterator first
, InputIterator last
, Predicate pred
)
98 for (; first
!= last
; ++first
)
104 /// Replace_if replaces every element in the range [first, last) for which
105 /// pred returns true with new_value. That is: for every iterator i, if
106 /// pred(*i) is true then it performs the assignment *i = new_value.
107 /// \ingroup MutatingAlgorithms
108 /// \ingroup PredicateAlgorithms
110 template <typename ForwardIterator
, typename Predicate
, typename T
>
111 inline void replace_if (ForwardIterator first
, ForwardIterator last
, Predicate pred
, const T
& new_value
)
113 for (; first
!= last
; ++first
)
118 /// Replace_copy_if copies elements from the range [first, last) to the range
119 /// [result, result + (last-first)), except that any element for which pred is
120 /// true is not copied; new_value is copied instead. More precisely, for every
121 /// integer n such that 0 <= n < last-first, replace_copy_if performs the
122 /// assignment *(result+n) = new_value if pred(*(first+n)),
123 /// and *(result+n) = *(first+n) otherwise.
124 /// \ingroup MutatingAlgorithms
125 /// \ingroup PredicateAlgorithms
127 template <typename InputIterator
, typename OutputIterator
, typename Predicate
, typename T
>
128 inline OutputIterator
replace_copy_if (InputIterator first
, InputIterator last
, OutputIterator result
, Predicate pred
, const T
& new_value
)
130 for (; first
!= last
; ++result
, ++first
)
131 *result
= pred(*first
) ? new_value
: *first
;
134 /// Remove_copy_if copies elements from the range [first, last) to a range
135 /// beginning at result, except that elements for which pred is true are not
136 /// copied. The return value is the end of the resulting range. This operation
137 /// is stable, meaning that the relative order of the elements that are copied
138 /// is the same as in the range [first, last).
139 /// \ingroup MutatingAlgorithms
140 /// \ingroup PredicateAlgorithms
142 template <typename InputIterator
, typename OutputIterator
, typename Predicate
>
143 inline OutputIterator
remove_copy_if (InputIterator first
, InputIterator last
, OutputIterator result
, Predicate pred
)
145 for (; first
!= last
; ++first
)
151 /// Remove_if removes from the range [first, last) every element x such that
152 /// pred(x) is true. That is, remove_if returns an iterator new_last such that
153 /// the range [first, new_last) contains no elements for which pred is true.
154 /// The iterators in the range [new_last, last) are all still dereferenceable,
155 /// but the elements that they point to are unspecified. Remove_if is stable,
156 /// meaning that the relative order of elements that are not removed is
158 /// \ingroup MutatingAlgorithms
159 /// \ingroup PredicateAlgorithms
161 template <typename ForwardIterator
, typename Predicate
>
162 inline ForwardIterator
remove_if (ForwardIterator first
, ForwardIterator last
, Predicate pred
)
164 return (remove_copy_if (first
, last
, first
, pred
));
167 /// The reason there are two different versions of unique_copy is that there
168 /// are two different definitions of what it means for a consecutive group of
169 /// elements to be duplicates. In the first version, the test is simple
170 /// equality: the elements in a range [f, l) are duplicates if, for every
171 /// iterator i in the range, either i == f or else *i == *(i-1). In the second,
172 /// the test is an arbitrary Binary Predicate binary_pred: the elements in
173 /// [f, l) are duplicates if, for every iterator i in the range, either
174 /// i == f or else binary_pred(*i, *(i-1)) is true.
175 /// \ingroup MutatingAlgorithms
176 /// \ingroup PredicateAlgorithms
178 template <typename InputIterator
, typename OutputIterator
, typename BinaryPredicate
>
179 OutputIterator
unique_copy (InputIterator first
, InputIterator last
, OutputIterator result
, BinaryPredicate binary_pred
)
183 while (++first
!= last
)
184 if (!binary_pred (*first
, *result
))
191 /// Every time a consecutive group of duplicate elements appears in the range
192 /// [first, last), the algorithm unique removes all but the first element.
193 /// That is, unique returns an iterator new_last such that the range [first,
194 /// new_last) contains no two consecutive elements that are duplicates.
195 /// The iterators in the range [new_last, last) are all still dereferenceable,
196 /// but the elements that they point to are unspecified. Unique is stable,
197 /// meaning that the relative order of elements that are not removed is
199 /// \ingroup MutatingAlgorithms
200 /// \ingroup PredicateAlgorithms
202 template <typename ForwardIterator
, typename BinaryPredicate
>
203 inline ForwardIterator
unique (ForwardIterator first
, ForwardIterator last
, BinaryPredicate binary_pred
)
205 return (unique_copy (first
, last
, first
, binary_pred
));
208 /// Returns the furthermost iterator i in [first, last) such that,
209 /// for every iterator j in [first, i), comp(*j, value) is true.
210 /// Assumes the range is sorted.
211 /// \ingroup SearchingAlgorithms
212 /// \ingroup PredicateAlgorithms
214 template <typename ForwardIterator
, typename T
, typename StrictWeakOrdering
>
215 ForwardIterator
lower_bound (ForwardIterator first
, ForwardIterator last
, const T
& value
, StrictWeakOrdering comp
)
218 while (first
!= last
) {
219 mid
= advance (first
, distance (first
,last
) / 2);
220 if (comp (*mid
, value
))
228 /// Performs a binary search inside the sorted range.
229 /// \ingroup SearchingAlgorithms
230 /// \ingroup PredicateAlgorithms
232 template <typename ForwardIterator
, typename T
, typename StrictWeakOrdering
>
233 inline ForwardIterator
binary_search (ForwardIterator first
, ForwardIterator last
, const T
& value
, StrictWeakOrdering comp
)
235 ForwardIterator found
= lower_bound (first
, last
, value
, comp
);
236 return ((found
== last
|| comp(value
, *found
)) ? last
: found
);
239 /// Returns the furthermost iterator i in [first,last) such that for
240 /// every iterator j in [first,i), comp(value,*j) is false.
241 /// \ingroup SearchingAlgorithms
242 /// \ingroup PredicateAlgorithms
244 template <typename ForwardIterator
, typename T
, typename StrictWeakOrdering
>
245 ForwardIterator
upper_bound (ForwardIterator first
, ForwardIterator last
, const T
& value
, StrictWeakOrdering comp
)
248 while (first
!= last
) {
249 mid
= advance (first
, distance (first
,last
) / 2);
250 if (comp (value
, *mid
))
258 /// Returns pair<lower_bound,upper_bound>
259 /// \ingroup SearchingAlgorithms
260 /// \ingroup PredicateAlgorithms
262 template <typename ForwardIterator
, typename T
, typename StrictWeakOrdering
>
263 inline pair
<ForwardIterator
,ForwardIterator
> equal_range (ForwardIterator first
, ForwardIterator last
, const T
& value
, StrictWeakOrdering comp
)
265 pair
<ForwardIterator
,ForwardIterator
> rv
;
266 rv
.second
= rv
.first
= lower_bound (first
, last
, value
, comp
);
267 while (rv
.second
!= last
&& !comp(value
, *(rv
.second
)))
272 /// \brief Puts \p nth element into its sorted position.
273 /// In this implementation, the entire array is sorted. The performance difference is
274 /// so small and the function use is so rare, there is no need to have code for it.
275 /// \ingroup SortingAlgorithms
276 /// \ingroup SearchingAlgorithms
277 /// \ingroup PredicateAlgorithms
279 template <typename RandomAccessIterator
, typename Compare
>
280 inline void nth_element (RandomAccessIterator first
, RandomAccessIterator
, RandomAccessIterator last
, Compare comp
)
282 sort (first
, last
, comp
);
285 /// \brief Searches for the first subsequence [first2,last2) in [first1,last1)
286 /// \ingroup SearchingAlgorithms
287 /// \ingroup PredicateAlgorithms
288 template <typename ForwardIterator1
, typename ForwardIterator2
, typename BinaryPredicate
>
289 ForwardIterator1
search (ForwardIterator1 first1
, ForwardIterator1 last1
, ForwardIterator2 first2
, ForwardIterator2 last2
, BinaryPredicate comp
)
291 const ForwardIterator1 slast
= last1
- distance(first2
, last2
) + 1;
292 for (; first1
< slast
; ++first1
) {
293 ForwardIterator2 i
= first2
;
294 ForwardIterator1 j
= first1
;
295 for (; i
!= last2
&& comp(*j
, *i
); ++i
, ++j
);
302 /// \brief Searches for the last subsequence [first2,last2) in [first1,last1)
303 /// \ingroup SearchingAlgorithms
304 /// \ingroup PredicateAlgorithms
305 template <typename ForwardIterator1
, typename ForwardIterator2
, typename BinaryPredicate
>
306 ForwardIterator1
find_end (ForwardIterator1 first1
, ForwardIterator1 last1
, ForwardIterator2 first2
, ForwardIterator2 last2
, BinaryPredicate comp
)
308 ForwardIterator1 s
= last1
- distance(first2
, last2
);
309 for (; first1
< s
; --s
) {
310 ForwardIterator2 i
= first2
, j
= s
;
311 for (; i
!= last2
&& comp(*j
, *i
); ++i
, ++j
);
318 /// \brief Searches for the first occurence of \p count \p values in [first, last)
319 /// \ingroup SearchingAlgorithms
320 /// \ingroup PredicateAlgorithms
321 template <typename Iterator
, typename T
, typename BinaryPredicate
>
322 Iterator
search_n (Iterator first
, Iterator last
, size_t count
, const T
& value
, BinaryPredicate comp
)
325 for (; first
!= last
; ++first
) {
326 if (!comp (*first
, value
))
328 else if (++n
== count
)
329 return (first
- --n
);
334 /// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2)
335 /// \ingroup SearchingAlgorithms
336 /// \ingroup PredicateAlgorithms
337 template <typename InputIterator
, typename ForwardIterator
, typename BinaryPredicate
>
338 InputIterator
find_first_of (InputIterator first1
, InputIterator last1
, ForwardIterator first2
, ForwardIterator last2
, BinaryPredicate comp
)
340 for (; first1
!= last1
; ++first1
)
341 for (ForwardIterator i
= first2
; i
!= last2
; ++i
)
342 if (comp (*first1
, *i
))
347 /// \brief Returns true if [first2,last2) is a subset of [first1,last1)
348 /// \ingroup ConditionAlgorithms
349 /// \ingroup SetAlgorithms
350 /// \ingroup PredicateAlgorithms
351 template <typename InputIterator1
, typename InputIterator2
, typename StrictWeakOrdering
>
352 bool includes (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, StrictWeakOrdering comp
)
354 for (; (first1
!= last1
) & (first2
!= last2
); ++first1
) {
355 if (comp (*first2
, *first1
))
357 first2
+= !comp (*first1
, *first2
);
359 return (first2
== last2
);
362 /// \brief Merges [first1,last1) with [first2,last2)
364 /// Result will contain every element that is in either set. If duplicate
365 /// elements are present, max(n,m) is placed in the result.
367 /// \ingroup SetAlgorithms
368 /// \ingroup PredicateAlgorithms
369 template <typename InputIterator1
, typename InputIterator2
, typename OutputIterator
, typename StrictWeakOrdering
>
370 OutputIterator
set_union (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, OutputIterator result
, StrictWeakOrdering comp
)
372 for (; (first1
!= last1
) & (first2
!= last2
); ++result
) {
373 if (comp (*first2
, *first1
))
376 first2
+= !comp (*first1
, *first2
);
380 return (copy (first2
, last2
, copy (first1
, last1
, result
)));
383 /// \brief Creates a set containing elements shared by the given ranges.
384 /// \ingroup SetAlgorithms
385 /// \ingroup PredicateAlgorithms
386 template <typename InputIterator1
, typename InputIterator2
, typename OutputIterator
, typename StrictWeakOrdering
>
387 OutputIterator
set_intersection (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, OutputIterator result
, StrictWeakOrdering comp
)
389 while ((first1
!= last1
) & (first2
!= last2
)) {
390 bool b1ge2
= !comp (*first1
, *first2
), b2ge1
= !comp (*first2
, *first1
);
399 /// \brief Removes from [first1,last1) elements present in [first2,last2)
400 /// \ingroup SetAlgorithms
401 /// \ingroup PredicateAlgorithms
402 template <typename InputIterator1
, typename InputIterator2
, typename OutputIterator
, typename StrictWeakOrdering
>
403 OutputIterator
set_difference (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, OutputIterator result
, StrictWeakOrdering comp
)
405 while ((first1
!= last1
) & (first2
!= last2
)) {
406 bool b1ge2
= !comp (*first1
, *first2
), b2ge1
= !comp (*first2
, *first1
);
412 return (copy (first1
, last1
, result
));
415 /// \brief Performs union of sets A-B and B-A.
416 /// \ingroup SetAlgorithms
417 /// \ingroup PredicateAlgorithms
418 template <typename InputIterator1
, typename InputIterator2
, typename OutputIterator
, typename StrictWeakOrdering
>
419 OutputIterator
set_symmetric_difference (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, OutputIterator result
, StrictWeakOrdering comp
)
421 while ((first1
!= last1
) & (first2
!= last2
)) {
422 bool b1l2
= comp (*first1
, *first2
), b2l1
= comp (*first2
, *first1
);
430 return (copy (first2
, last2
, copy (first1
, last1
, result
)));
433 /// \brief Returns true if the given range is sorted.
434 /// \ingroup ConditionAlgorithms
435 /// \ingroup PredicateAlgorithms
436 template <typename ForwardIterator
, typename StrictWeakOrdering
>
437 bool is_sorted (ForwardIterator first
, ForwardIterator last
, StrictWeakOrdering comp
)
439 for (ForwardIterator i
= first
; ++i
< last
; ++first
)
440 if (comp (*i
, *first
))
445 /// \brief Compares two given containers like strcmp compares strings.
446 /// \ingroup ConditionAlgorithms
447 /// \ingroup PredicateAlgorithms
448 template <typename InputIterator1
, typename InputIterator2
, typename BinaryPredicate
>
449 bool lexicographical_compare (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, BinaryPredicate comp
)
451 for (; (first1
!= last1
) & (first2
!= last2
); ++first1
, ++first2
) {
452 if (comp (*first1
, *first2
))
454 if (comp (*first2
, *first1
))
457 return ((first1
== last1
) & (first2
!= last2
));
460 /// \brief Creates the next lexicographical permutation of [first,last).
461 /// Returns false if no further permutations can be created.
462 /// \ingroup GeneratorAlgorithms
463 /// \ingroup PredicateAlgorithms
464 template <typename BidirectionalIterator
, typename StrictWeakOrdering
>
465 bool next_permutation (BidirectionalIterator first
, BidirectionalIterator last
, StrictWeakOrdering comp
)
467 if (distance (first
, last
) < 2)
469 BidirectionalIterator i
= last
;
470 for (--i
; i
!= first
; ) {
472 if (comp (i
[0], i
[1])) {
473 BidirectionalIterator j
= last
;
474 while (!comp (*i
, *--j
));
476 reverse (i
+ 1, last
);
480 reverse (first
, last
);
484 /// \brief Creates the previous lexicographical permutation of [first,last).
485 /// Returns false if no further permutations can be created.
486 /// \ingroup GeneratorAlgorithms
487 /// \ingroup PredicateAlgorithms
488 template <typename BidirectionalIterator
, typename StrictWeakOrdering
>
489 bool prev_permutation (BidirectionalIterator first
, BidirectionalIterator last
, StrictWeakOrdering comp
)
491 if (distance (first
, last
) < 2)
493 BidirectionalIterator i
= last
;
494 for (--i
; i
!= first
; ) {
496 if (comp(i
[1], i
[0])) {
497 BidirectionalIterator j
= last
;
498 while (!comp (*--j
, *i
));
500 reverse (i
+ 1, last
);
504 reverse (first
, last
);
508 /// \brief Returns iterator to the max element in [first,last)
509 /// \ingroup SearchingAlgorithms
510 /// \ingroup PredicateAlgorithms
511 template <typename ForwardIterator
, typename BinaryPredicate
>
512 inline ForwardIterator
max_element (ForwardIterator first
, ForwardIterator last
, BinaryPredicate comp
)
514 ForwardIterator result
= first
;
515 for (; first
!= last
; ++first
)
516 if (comp (*result
, *first
))
521 /// \brief Returns iterator to the min element in [first,last)
522 /// \ingroup SearchingAlgorithms
523 /// \ingroup PredicateAlgorithms
524 template <typename ForwardIterator
, typename BinaryPredicate
>
525 inline ForwardIterator
min_element (ForwardIterator first
, ForwardIterator last
, BinaryPredicate comp
)
527 ForwardIterator result
= first
;
528 for (; first
!= last
; ++first
)
529 if (comp (*first
, *result
))
534 /// \brief Makes [first,middle) a part of the sorted array.
535 /// Contents of [middle,last) is undefined. This implementation just calls stable_sort.
536 /// \ingroup SortingAlgorithms
537 /// \ingroup PredicateAlgorithms
538 template <typename RandomAccessIterator
, typename StrictWeakOrdering
>
539 inline void partial_sort (RandomAccessIterator first
, RandomAccessIterator
, RandomAccessIterator last
, StrictWeakOrdering comp
)
541 stable_sort (first
, last
, comp
);
544 /// \brief Like partial_sort, but outputs to [result_first,result_last)
545 /// \ingroup SortingAlgorithms
546 /// \ingroup PredicateAlgorithms
547 template <typename InputIterator
, typename RandomAccessIterator
, typename StrictWeakOrdering
>
548 RandomAccessIterator
partial_sort_copy (InputIterator first
, InputIterator last
, RandomAccessIterator result_first
, RandomAccessIterator result_last
, StrictWeakOrdering comp
)
550 RandomAccessIterator rend
= result_first
;
551 for (; first
!= last
; ++first
) {
552 RandomAccessIterator i
= result_first
;
553 for (; i
!= rend
&& comp (*i
, *first
); ++i
);
554 if (i
== result_last
)
556 rend
+= (rend
< result_last
);
557 copy_backward (i
, rend
- 1, rend
);
563 /// \brief Like \ref partition, but preserves equal element order.
564 /// \ingroup SortingAlgorithms
565 /// \ingroup PredicateAlgorithms
566 template <typename ForwardIterator
, typename Predicate
>
567 ForwardIterator
stable_partition (ForwardIterator first
, ForwardIterator last
, Predicate pred
)
571 ForwardIterator l
, r
, m
= advance (first
, distance (first
, last
) / 2);
573 return (pred(*first
) ? last
: first
);
574 l
= stable_partition (first
, m
, pred
);
575 r
= stable_partition (m
, last
, pred
);
577 return (advance (l
, distance (m
, r
)));
580 /// \brief Splits [first,last) in two by \p pred.
582 /// Creates two ranges [first,middle) and [middle,last), where every element
583 /// in the former is less than every element in the latter.
584 /// The return value is middle.
586 /// \ingroup SortingAlgorithms
587 /// \ingroup PredicateAlgorithms
588 template <typename ForwardIterator
, typename Predicate
>
589 inline ForwardIterator
partition (ForwardIterator first
, ForwardIterator last
, Predicate pred
)
591 return (stable_partition (first
, last
, pred
));