1// This file is part of the ustl library, an STL implementation.
2//
3// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4// This file is free software, distributed under the MIT License.
5//
6// \file uctralgo.h
7//
8// \brief Implementation of STL algorithms with container shortcuts.
9//
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.
13//
14
15#ifndef UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0
16#define UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0
17
18#include "uassert.h"
19
20namespace ustl {
21
22/// Copy copies elements from the range [first, last) to the range
23/// [result, result + (last - first)). That is, it performs the assignments
24/// *result = *first, *(result + 1) = *(first + 1), and so on. [1] Generally,
25/// for every integer n from 0 to last - first, copy performs the assignment
26/// *(result + n) = *(first + n). Assignments are performed in forward order,
27/// i.e. in order of increasing n.
28/// \ingroup MutatingAlgorithms
29///
30template <typename Container, typename OutputIterator>
31inline OutputIterator copy (const Container& ctr, OutputIterator result)
32{
33    return (copy (ctr.begin(), ctr.end(), result));
34}
35
36/// Copy_if copies elements from the range [first, last) to the range
37/// [result, result + (last - first)) if pred(*i) returns true.
38/// \ingroup MutatingAlgorithms
39///
40template <typename Container, typename OutputIterator, typename Predicate>
41inline OutputIterator copy_if (Container& ctr, OutputIterator result, Predicate pred)
42{
43    return (copy_if (ctr.begin(), ctr.end(), result, pred));
44}
45
46/// For_each applies the function object f to each element in the range
47/// [first, last); f's return value, if any, is ignored. Applications are
48/// performed in forward order, i.e. from first to last. For_each returns
49/// the function object after it has been applied to each element.
50/// \ingroup MutatingAlgorithms
51///
52template <typename Container, typename UnaryFunction>
53inline UnaryFunction for_each (Container& ctr, UnaryFunction f)
54{
55    return (for_each (ctr.begin(), ctr.end(), f));
56}
57
58/// For_each applies the function object f to each element in the range
59/// [first, last); f's return value, if any, is ignored. Applications are
60/// performed in forward order, i.e. from first to last. For_each returns
61/// the function object after it has been applied to each element.
62/// \ingroup MutatingAlgorithms
63///
64template <typename Container, typename UnaryFunction>
65inline UnaryFunction for_each (const Container& ctr, UnaryFunction f)
66{
67    return (for_each (ctr.begin(), ctr.end(), f));
68}
69
70/// Returns the first iterator i in the range [first, last) such that
71/// *i == value. Returns last if no such iterator exists.
72/// \ingroup SearchingAlgorithms
73///
74template <typename Container, typename EqualityComparable>
75inline typename Container::const_iterator find (const Container& ctr, const EqualityComparable& value)
76{
77    return (find (ctr.begin(), ctr.end(), value));
78}
79template <typename Container, typename EqualityComparable>
80inline typename Container::iterator find (Container& ctr, const EqualityComparable& value)
81{
82    return (find (ctr.begin(), ctr.end(), value));
83}
84
85/// Returns the first iterator i in the range [first, last) such that
86/// pred(*i) is true. Returns last if no such iterator exists.
87/// \ingroup SearchingAlgorithms
88///
89template <typename Container, typename Predicate>
90inline typename Container::const_iterator find_if (const Container& ctr, Predicate pred)
91{
92    return (find_if (ctr.begin(), ctr.end(), pred));
93}
94template <typename Container, typename Predicate>
95inline typename Container::iterator find_if (Container& ctr, Predicate pred)
96{
97    return (find_if (ctr.begin(), ctr.end(), pred));
98}
99
100/// Count finds the number of elements in [first, last) that are equal
101/// to value. More precisely, the first version of count returns the
102/// number of iterators i in [first, last) such that *i == value.
103/// \ingroup ConditionAlgorithms
104///
105template <typename Container, typename EqualityComparable>
106inline size_t count (const Container& ctr, const EqualityComparable& value)
107{
108    return (count (ctr.begin(), ctr.end(), value));
109}
110
111/// Count_if finds the number of elements in [first, last) that satisfy the
112/// predicate pred. More precisely, the first version of count_if returns the
113/// number of iterators i in [first, last) such that pred(*i) is true.
114/// \ingroup ConditionAlgorithms
115///
116template <typename Container, typename Predicate>
117inline size_t count_if (const Container& ctr, Predicate pred)
118{
119    return (count_if (ctr.begin(), ctr.end(), pred));
120}
121
122/// The first version of transform performs the operation op(*i) for each
123/// iterator i in the range [first, last), and assigns the result of that
124/// operation to *o, where o is the corresponding output iterator. That is,
125/// for each n such that 0 <= n < last - first, it performs the assignment
126/// *(result + n) = op(*(first + n)).
127/// The return value is result + (last - first).
128/// \ingroup MutatingAlgorithms
129///
130template <typename Container, typename UnaryFunction>
131inline void transform (Container& ctr, UnaryFunction op)
132{
133    transform (ctr.begin(), ctr.end(), ctr.begin(), op);
134}
135
136/// The first version of transform performs the operation op(*i) for each
137/// iterator i in the range [first, last), and assigns the result of that
138/// operation to *o, where o is the corresponding output iterator. That is,
139/// for each n such that 0 <= n < last - first, it performs the assignment
140/// *(result + n) = op(*(first + n)).
141/// The return value is result + (last - first).
142/// \ingroup MutatingAlgorithms
143///
144template <typename Container, typename OutputIterator, typename UnaryFunction>
145inline OutputIterator transform (Container& ctr, OutputIterator result, UnaryFunction op)
146{
147    return (transform (ctr.begin(), ctr.end(), result, op));
148}
149
150/// The second version of transform is very similar, except that it uses a
151/// Binary Function instead of a Unary Function: it performs the operation
152/// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns
153/// the result to *o, where i2 is the corresponding iterator in the second
154/// input range and where o is the corresponding output iterator. That is,
155/// for each n such that 0 <= n < last1 - first1, it performs the assignment
156/// *(result + n) = op(*(first1 + n), *(first2 + n).
157/// The return value is result + (last1 - first1).
158/// \ingroup MutatingAlgorithms
159///
160template <typename Container, typename InputIterator, typename OutputIterator, typename BinaryFunction>
161inline OutputIterator transform (Container& ctr, InputIterator first, OutputIterator result, BinaryFunction op)
162{
163    return (transform (ctr.begin(), ctr.end(), first, result, op));
164}
165
166/// Replace replaces every element in the range [first, last) equal to
167/// old_value with new_value. That is: for every iterator i,
168/// if *i == old_value then it performs the assignment *i = new_value.
169/// \ingroup MutatingAlgorithms
170///
171template <typename Container, typename T>
172inline void replace (Container& ctr, const T& old_value, const T& new_value)
173{
174    replace (ctr.begin(), ctr.end(), old_value, new_value);
175}
176
177/// Replace_if replaces every element in the range [first, last) for which
178/// pred returns true with new_value. That is: for every iterator i, if
179/// pred(*i) is true then it performs the assignment *i = new_value.
180/// \ingroup MutatingAlgorithms
181///
182template <typename Container, typename Predicate, typename T>
183inline void replace_if (Container& ctr, Predicate pred, const T& new_value)
184{
185    replace_if (ctr.begin(), ctr.end(), pred, new_value);
186}
187
188/// Replace_copy copies elements from the range [first, last) to the range
189/// [result, result + (last-first)), except that any element equal to old_value
190/// is not copied; new_value is copied instead. More precisely, for every
191/// integer n such that 0 <= n < last-first, replace_copy performs the
192/// assignment *(result+n) = new_value if *(first+n) == old_value, and
193/// *(result+n) = *(first+n) otherwise.
194/// \ingroup MutatingAlgorithms
195///
196template <typename Container, typename OutputIterator, typename T>
197inline OutputIterator replace_copy (const Container& ctr, OutputIterator result, const T& old_value, const T& new_value)
198{
199    return (replace_copy (ctr.begin(), ctr.end(), result, old_value, new_value));
200}
201
202/// Replace_copy_if copies elements from the range [first, last) to the range
203/// [result, result + (last-first)), except that any element for which pred is
204/// true is not copied; new_value is copied instead. More precisely, for every
205/// integer n such that 0 <= n < last-first, replace_copy_if performs the
206/// assignment *(result+n) = new_value if pred(*(first+n)),
207/// and *(result+n) = *(first+n) otherwise.
208/// \ingroup MutatingAlgorithms
209///
210template <typename Container, typename OutputIterator, typename Predicate, typename T>
211inline OutputIterator replace_copy_if (const Container& ctr, OutputIterator result, Predicate pred, const T& new_value)
212{
213    return (replace_copy_if (ctr.begin(), ctr.end(), result, pred, new_value));
214}
215
216/// Fill assigns the value value to every element in the range [first, last).
217/// That is, for every iterator i in [first, last),
218/// it performs the assignment *i = value.
219/// \ingroup GeneratorAlgorithms
220///
221template <typename Container, typename T>
222inline void fill (Container& ctr, const T& value)
223{
224    fill (ctr.begin(), ctr.end(), value);
225}
226
227/// Generate assigns the result of invoking gen, a function object that
228/// takes no arguments, to each element in the range [first, last).
229/// \ingroup GeneratorAlgorithms
230///
231template <typename Container, typename Generator>
232inline void generate (Container& ctr, Generator gen)
233{
234    generate (ctr.begin(), ctr.end(), gen);
235}
236
237/// Randomly permute the elements of the container.
238/// \ingroup GeneratorAlgorithms
239///
240template <typename Container>
241inline void random_shuffle (Container& ctr)
242{
243    random_shuffle (ctr.begin(), ctr.end());
244}
245
246/// Remove_copy copies elements that are not equal to value from the range
247/// [first, last) to a range beginning at result. The return value is the
248/// end of the resulting range. This operation is stable, meaning that the
249/// relative order of the elements that are copied is the same as in the
250/// range [first, last).
251/// \ingroup MutatingAlgorithms
252///
253template <typename Container, typename OutputIterator, typename T>
254inline OutputIterator remove_copy (const Container& ctr, OutputIterator result, const T& value)
255{
256    return (remove_copy (ctr.begin(), ctr.end(), result, value));
257}
258
259/// Remove_copy_if copies elements from the range [first, last) to a range
260/// beginning at result, except that elements for which pred is true are not
261/// copied. The return value is the end of the resulting range. This operation
262/// is stable, meaning that the relative order of the elements that are copied
263/// is the same as in the range [first, last).
264/// \ingroup MutatingAlgorithms
265///
266template <typename Container, typename OutputIterator, typename Predicate>
267inline OutputIterator remove_copy_if (const Container& ctr, OutputIterator result, Predicate pred)
268{
269    return (remove_copy_if (ctr.begin(), ctr.end(), result, pred));
270}
271
272/// Remove removes from the range [first, last) all elements that are equal to
273/// value. That is, remove returns an iterator new_last such that the range
274/// [first, new_last) contains no elements equal to value. Remove is stable,
275/// meaning that the relative order of elements that are not equal to value is
276/// unchanged.
277/// \ingroup MutatingAlgorithms
278///
279template <typename Container, typename T>
280inline void remove (Container& ctr, const T& value)
281{
282    ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), value), ctr.end());
283}
284
285/// Remove removes from the range [first, last) all elements that have an iterator
286/// in range [rfirst, rlast). The range is assumed to be sorted. That is, remove
287/// returns an iterator new_last such that the range [first, new_last) contains
288/// no elements whose iterators are in [rfirst, rlast). Remove is stable,
289/// meaning that the relative order of elements that are not equal to value is
290/// unchanged. This version of the algorithm is a uSTL extension.
291/// \ingroup MutatingAlgorithms
292///
293template <typename Container, typename ForwardIterator>
294inline void remove (Container& ctr, ForwardIterator rfirst, ForwardIterator rlast)
295{
296    ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), rfirst, rlast), ctr.end());
297}
298
299/// Remove_if removes from the range [first, last) every element x such that
300/// pred(x) is true. That is, remove_if returns an iterator new_last such that
301/// the range [first, new_last) contains no elements for which pred is true.
302/// The iterators in the range [new_last, last) are all still dereferenceable,
303/// but the elements that they point to are unspecified. Remove_if is stable,
304/// meaning that the relative order of elements that are not removed is
305/// unchanged.
306/// \ingroup MutatingAlgorithms
307///
308template <typename Container, typename Predicate>
309inline void remove_if (Container& ctr, Predicate pred)
310{
311    ctr.erase (remove_copy_if (ctr.begin(), ctr.end(), ctr.begin(), pred), ctr.end());
312}
313
314/// Unique_copy copies elements from the range [first, last) to a range
315/// beginning with result, except that in a consecutive group of duplicate
316/// elements only the first one is copied. The return value is the end of
317/// the range to which the elements are copied. This behavior is similar
318/// to the Unix filter uniq.
319/// \ingroup MutatingAlgorithms
320///
321template <typename Container, typename OutputIterator>
322inline OutputIterator unique_copy (const Container& ctr, OutputIterator result)
323{
324    return (unique_copy (ctr.begin(), ctr.end(), result));
325}
326
327/// Every time a consecutive group of duplicate elements appears in the range
328/// [first, last), the algorithm unique removes all but the first element.
329/// That is, unique returns an iterator new_last such that the range [first,
330/// new_last) contains no two consecutive elements that are duplicates.
331/// The iterators in the range [new_last, last) are all still dereferenceable,
332/// but the elements that they point to are unspecified. Unique is stable,
333/// meaning that the relative order of elements that are not removed is
334/// unchanged.
335/// \ingroup MutatingAlgorithms
336///
337template <typename Container>
338inline void unique (Container& ctr)
339{
340    ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin()), ctr.end());
341}
342
343/// Every time a consecutive group of duplicate elements appears in the range
344/// [first, last), the algorithm unique removes all but the first element.
345/// That is, unique returns an iterator new_last such that the range [first,
346/// new_last) contains no two consecutive elements that are duplicates.
347/// The iterators in the range [new_last, last) are all still dereferenceable,
348/// but the elements that they point to are unspecified. Unique is stable,
349/// meaning that the relative order of elements that are not removed is
350/// unchanged.
351/// \ingroup MutatingAlgorithms
352///
353template <typename Container, typename BinaryPredicate>
354inline void unique (Container& ctr, BinaryPredicate binary_pred)
355{
356    ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin(), binary_pred), ctr.end());
357}
358
359/// Reverse reverses a range.
360/// That is: for every i such that 0 <= i <= (last - first) / 2),
361/// it exchanges *(first + i) and *(last - (i + 1)).
362/// \ingroup MutatingAlgorithms
363///
364template <typename Container>
365inline void reverse (Container& ctr)
366{
367    reverse (ctr.begin(), ctr.end());
368}
369
370/// Exchanges ranges [first, middle) and [middle, last)
371/// \ingroup MutatingAlgorithms
372///
373template <typename Container>
374inline void rotate (Container& ctr, off_t offset)
375{
376    assert (size_t(offset > 0 ? offset : -offset) < ctr.size());
377    if (offset > 0)
378	rotate (ctr.begin(), ctr.end() - offset, ctr.end());
379    else
380	rotate (ctr.begin(), ctr.begin() - offset, ctr.end());
381}
382
383/// Returns the furthermost iterator i in [first, last) such that,
384/// for every iterator j in [first, i), *j < value
385/// Assumes the range is sorted.
386/// \ingroup SearchingAlgorithms
387///
388template <typename Container, typename LessThanComparable>
389inline typename Container::const_iterator lower_bound (const Container& ctr, const LessThanComparable& value)
390{
391    return (lower_bound (ctr.begin(), ctr.end(), value));
392}
393template <typename Container, typename LessThanComparable>
394inline typename Container::iterator lower_bound (Container& ctr, const LessThanComparable& value)
395{
396    return (lower_bound (ctr.begin(), ctr.end(), value));
397}
398
399/// Returns the furthermost iterator i in [first,last) such that for
400/// every iterator j in [first,i), value < *j is false.
401/// \ingroup SearchingAlgorithms
402///
403template <typename Container, typename LessThanComparable>
404inline typename Container::const_iterator upper_bound (const Container& ctr, const LessThanComparable& value)
405{
406    return (upper_bound (ctr.begin(), ctr.end(), value));
407}
408template <typename Container, typename LessThanComparable>
409inline typename Container::iterator upper_bound (Container& ctr, const LessThanComparable& value)
410{
411    return (upper_bound (ctr.begin(), ctr.end(), value));
412}
413
414/// Performs a binary search for \p value.
415/// Assumes the range is sorted.
416/// \ingroup SearchingAlgorithms
417///
418template <typename Container>
419inline typename Container::const_iterator binary_search (const Container& ctr, const typename Container::value_type& value)
420{
421    return (binary_search (ctr.begin(), ctr.end(), value));
422}
423template <typename Container>
424inline typename Container::iterator binary_search (Container& ctr, const typename Container::value_type& value)
425{
426    return (binary_search (ctr.begin(), ctr.end(), value));
427}
428
429/// Returns pair<lower_bound,upper_bound>
430/// \ingroup SearchingAlgorithms
431///
432template <typename Container, typename LessThanComparable>
433inline pair<typename Container::const_iterator,typename Container::const_iterator> equal_range (const Container& ctr, const LessThanComparable& value)
434{
435    return (equal_range (ctr.begin(), ctr.end(), value));
436}
437template <typename Container, typename LessThanComparable>
438inline pair<typename Container::iterator,typename Container::iterator> equal_range (Container& ctr, const LessThanComparable& value)
439{
440    return (equal_range (ctr.begin(), ctr.end(), value));
441}
442
443/// Sorts the container
444/// \ingroup SortingAlgorithms
445///
446template <typename Container>
447inline void sort (Container& ctr)
448{
449    sort (ctr.begin(), ctr.end());
450}
451
452/// Sorts the container
453/// \ingroup SortingAlgorithms
454///
455template <typename Container, typename Compare>
456inline void sort (Container& ctr, Compare comp)
457{
458    sort (ctr.begin(), ctr.end(), comp);
459}
460
461/// Sorts the container
462/// \ingroup SortingAlgorithms
463///
464template <typename Container>
465inline void stable_sort (Container& ctr)
466{
467    stable_sort (ctr.begin(), ctr.end());
468}
469
470/// Sorts the container
471/// \ingroup SortingAlgorithms
472///
473template <typename Container, typename Compare>
474inline void stable_sort (Container& ctr, Compare comp)
475{
476    stable_sort (ctr.begin(), ctr.end(), comp);
477}
478
479} // namespace ustl
480
481#endif
482
483