| // This file is part of the ustl library, an STL implementation. |
| // |
| // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> |
| // This file is free software, distributed under the MIT License. |
| // |
| // \file uctralgo.h |
| // |
| // \brief Implementation of STL algorithms with container shortcuts. |
| // |
| // The function prototypes are copied |
| // exactly from the SGI version of STL documentation along with comments about |
| // their use. The code is NOT the same, though the functionality usually is. |
| // |
| |
| #ifndef UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0 |
| #define UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0 |
| |
| #include "uassert.h" |
| |
| namespace ustl { |
| |
| /// Copy copies elements from the range [first, last) to the range |
| /// [result, result + (last - first)). That is, it performs the assignments |
| /// *result = *first, *(result + 1) = *(first + 1), and so on. [1] Generally, |
| /// for every integer n from 0 to last - first, copy performs the assignment |
| /// *(result + n) = *(first + n). Assignments are performed in forward order, |
| /// i.e. in order of increasing n. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator> |
| inline OutputIterator copy (const Container& ctr, OutputIterator result) |
| { |
| return (copy (ctr.begin(), ctr.end(), result)); |
| } |
| |
| /// Copy_if copies elements from the range [first, last) to the range |
| /// [result, result + (last - first)) if pred(*i) returns true. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename Predicate> |
| inline OutputIterator copy_if (Container& ctr, OutputIterator result, Predicate pred) |
| { |
| return (copy_if (ctr.begin(), ctr.end(), result, pred)); |
| } |
| |
| /// For_each applies the function object f to each element in the range |
| /// [first, last); f's return value, if any, is ignored. Applications are |
| /// performed in forward order, i.e. from first to last. For_each returns |
| /// the function object after it has been applied to each element. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename UnaryFunction> |
| inline UnaryFunction for_each (Container& ctr, UnaryFunction f) |
| { |
| return (for_each (ctr.begin(), ctr.end(), f)); |
| } |
| |
| /// For_each applies the function object f to each element in the range |
| /// [first, last); f's return value, if any, is ignored. Applications are |
| /// performed in forward order, i.e. from first to last. For_each returns |
| /// the function object after it has been applied to each element. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename UnaryFunction> |
| inline UnaryFunction for_each (const Container& ctr, UnaryFunction f) |
| { |
| return (for_each (ctr.begin(), ctr.end(), f)); |
| } |
| |
| /// Returns the first iterator i in the range [first, last) such that |
| /// *i == value. Returns last if no such iterator exists. |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container, typename EqualityComparable> |
| inline typename Container::const_iterator find (const Container& ctr, const EqualityComparable& value) |
| { |
| return (find (ctr.begin(), ctr.end(), value)); |
| } |
| template <typename Container, typename EqualityComparable> |
| inline typename Container::iterator find (Container& ctr, const EqualityComparable& value) |
| { |
| return (find (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Returns the first iterator i in the range [first, last) such that |
| /// pred(*i) is true. Returns last if no such iterator exists. |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container, typename Predicate> |
| inline typename Container::const_iterator find_if (const Container& ctr, Predicate pred) |
| { |
| return (find_if (ctr.begin(), ctr.end(), pred)); |
| } |
| template <typename Container, typename Predicate> |
| inline typename Container::iterator find_if (Container& ctr, Predicate pred) |
| { |
| return (find_if (ctr.begin(), ctr.end(), pred)); |
| } |
| |
| /// Count finds the number of elements in [first, last) that are equal |
| /// to value. More precisely, the first version of count returns the |
| /// number of iterators i in [first, last) such that *i == value. |
| /// \ingroup ConditionAlgorithms |
| /// |
| template <typename Container, typename EqualityComparable> |
| inline size_t count (const Container& ctr, const EqualityComparable& value) |
| { |
| return (count (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Count_if finds the number of elements in [first, last) that satisfy the |
| /// predicate pred. More precisely, the first version of count_if returns the |
| /// number of iterators i in [first, last) such that pred(*i) is true. |
| /// \ingroup ConditionAlgorithms |
| /// |
| template <typename Container, typename Predicate> |
| inline size_t count_if (const Container& ctr, Predicate pred) |
| { |
| return (count_if (ctr.begin(), ctr.end(), pred)); |
| } |
| |
| /// The first version of transform performs the operation op(*i) for each |
| /// iterator i in the range [first, last), and assigns the result of that |
| /// operation to *o, where o is the corresponding output iterator. That is, |
| /// for each n such that 0 <= n < last - first, it performs the assignment |
| /// *(result + n) = op(*(first + n)). |
| /// The return value is result + (last - first). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename UnaryFunction> |
| inline void transform (Container& ctr, UnaryFunction op) |
| { |
| transform (ctr.begin(), ctr.end(), ctr.begin(), op); |
| } |
| |
| /// The first version of transform performs the operation op(*i) for each |
| /// iterator i in the range [first, last), and assigns the result of that |
| /// operation to *o, where o is the corresponding output iterator. That is, |
| /// for each n such that 0 <= n < last - first, it performs the assignment |
| /// *(result + n) = op(*(first + n)). |
| /// The return value is result + (last - first). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename UnaryFunction> |
| inline OutputIterator transform (Container& ctr, OutputIterator result, UnaryFunction op) |
| { |
| return (transform (ctr.begin(), ctr.end(), result, op)); |
| } |
| |
| /// The second version of transform is very similar, except that it uses a |
| /// Binary Function instead of a Unary Function: it performs the operation |
| /// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns |
| /// the result to *o, where i2 is the corresponding iterator in the second |
| /// input range and where o is the corresponding output iterator. That is, |
| /// for each n such that 0 <= n < last1 - first1, it performs the assignment |
| /// *(result + n) = op(*(first1 + n), *(first2 + n). |
| /// The return value is result + (last1 - first1). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename InputIterator, typename OutputIterator, typename BinaryFunction> |
| inline OutputIterator transform (Container& ctr, InputIterator first, OutputIterator result, BinaryFunction op) |
| { |
| return (transform (ctr.begin(), ctr.end(), first, result, op)); |
| } |
| |
| /// Replace replaces every element in the range [first, last) equal to |
| /// old_value with new_value. That is: for every iterator i, |
| /// if *i == old_value then it performs the assignment *i = new_value. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename T> |
| inline void replace (Container& ctr, const T& old_value, const T& new_value) |
| { |
| replace (ctr.begin(), ctr.end(), old_value, new_value); |
| } |
| |
| /// Replace_if replaces every element in the range [first, last) for which |
| /// pred returns true with new_value. That is: for every iterator i, if |
| /// pred(*i) is true then it performs the assignment *i = new_value. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename Predicate, typename T> |
| inline void replace_if (Container& ctr, Predicate pred, const T& new_value) |
| { |
| replace_if (ctr.begin(), ctr.end(), pred, new_value); |
| } |
| |
| /// Replace_copy copies elements from the range [first, last) to the range |
| /// [result, result + (last-first)), except that any element equal to old_value |
| /// is not copied; new_value is copied instead. More precisely, for every |
| /// integer n such that 0 <= n < last-first, replace_copy performs the |
| /// assignment *(result+n) = new_value if *(first+n) == old_value, and |
| /// *(result+n) = *(first+n) otherwise. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename T> |
| inline OutputIterator replace_copy (const Container& ctr, OutputIterator result, const T& old_value, const T& new_value) |
| { |
| return (replace_copy (ctr.begin(), ctr.end(), result, old_value, new_value)); |
| } |
| |
| /// Replace_copy_if copies elements from the range [first, last) to the range |
| /// [result, result + (last-first)), except that any element for which pred is |
| /// true is not copied; new_value is copied instead. More precisely, for every |
| /// integer n such that 0 <= n < last-first, replace_copy_if performs the |
| /// assignment *(result+n) = new_value if pred(*(first+n)), |
| /// and *(result+n) = *(first+n) otherwise. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename Predicate, typename T> |
| inline OutputIterator replace_copy_if (const Container& ctr, OutputIterator result, Predicate pred, const T& new_value) |
| { |
| return (replace_copy_if (ctr.begin(), ctr.end(), result, pred, new_value)); |
| } |
| |
| /// Fill assigns the value value to every element in the range [first, last). |
| /// That is, for every iterator i in [first, last), |
| /// it performs the assignment *i = value. |
| /// \ingroup GeneratorAlgorithms |
| /// |
| template <typename Container, typename T> |
| inline void fill (Container& ctr, const T& value) |
| { |
| fill (ctr.begin(), ctr.end(), value); |
| } |
| |
| /// Generate assigns the result of invoking gen, a function object that |
| /// takes no arguments, to each element in the range [first, last). |
| /// \ingroup GeneratorAlgorithms |
| /// |
| template <typename Container, typename Generator> |
| inline void generate (Container& ctr, Generator gen) |
| { |
| generate (ctr.begin(), ctr.end(), gen); |
| } |
| |
| /// Randomly permute the elements of the container. |
| /// \ingroup GeneratorAlgorithms |
| /// |
| template <typename Container> |
| inline void random_shuffle (Container& ctr) |
| { |
| random_shuffle (ctr.begin(), ctr.end()); |
| } |
| |
| /// Remove_copy copies elements that are not equal to value from the range |
| /// [first, last) to a range beginning at result. The return value is the |
| /// end of the resulting range. This operation is stable, meaning that the |
| /// relative order of the elements that are copied is the same as in the |
| /// range [first, last). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename T> |
| inline OutputIterator remove_copy (const Container& ctr, OutputIterator result, const T& value) |
| { |
| return (remove_copy (ctr.begin(), ctr.end(), result, value)); |
| } |
| |
| /// Remove_copy_if copies elements from the range [first, last) to a range |
| /// beginning at result, except that elements for which pred is true are not |
| /// copied. The return value is the end of the resulting range. This operation |
| /// is stable, meaning that the relative order of the elements that are copied |
| /// is the same as in the range [first, last). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator, typename Predicate> |
| inline OutputIterator remove_copy_if (const Container& ctr, OutputIterator result, Predicate pred) |
| { |
| return (remove_copy_if (ctr.begin(), ctr.end(), result, pred)); |
| } |
| |
| /// Remove removes from the range [first, last) all elements that are equal to |
| /// value. That is, remove returns an iterator new_last such that the range |
| /// [first, new_last) contains no elements equal to value. Remove is stable, |
| /// meaning that the relative order of elements that are not equal to value is |
| /// unchanged. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename T> |
| inline void remove (Container& ctr, const T& value) |
| { |
| ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), value), ctr.end()); |
| } |
| |
| /// Remove removes from the range [first, last) all elements that have an iterator |
| /// in range [rfirst, rlast). The range is assumed to be sorted. That is, remove |
| /// returns an iterator new_last such that the range [first, new_last) contains |
| /// no elements whose iterators are in [rfirst, rlast). Remove is stable, |
| /// meaning that the relative order of elements that are not equal to value is |
| /// unchanged. This version of the algorithm is a uSTL extension. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename ForwardIterator> |
| inline void remove (Container& ctr, ForwardIterator rfirst, ForwardIterator rlast) |
| { |
| ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), rfirst, rlast), ctr.end()); |
| } |
| |
| /// Remove_if removes from the range [first, last) every element x such that |
| /// pred(x) is true. That is, remove_if returns an iterator new_last such that |
| /// the range [first, new_last) contains no elements for which pred is true. |
| /// The iterators in the range [new_last, last) are all still dereferenceable, |
| /// but the elements that they point to are unspecified. Remove_if is stable, |
| /// meaning that the relative order of elements that are not removed is |
| /// unchanged. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename Predicate> |
| inline void remove_if (Container& ctr, Predicate pred) |
| { |
| ctr.erase (remove_copy_if (ctr.begin(), ctr.end(), ctr.begin(), pred), ctr.end()); |
| } |
| |
| /// Unique_copy copies elements from the range [first, last) to a range |
| /// beginning with result, except that in a consecutive group of duplicate |
| /// elements only the first one is copied. The return value is the end of |
| /// the range to which the elements are copied. This behavior is similar |
| /// to the Unix filter uniq. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename OutputIterator> |
| inline OutputIterator unique_copy (const Container& ctr, OutputIterator result) |
| { |
| return (unique_copy (ctr.begin(), ctr.end(), result)); |
| } |
| |
| /// Every time a consecutive group of duplicate elements appears in the range |
| /// [first, last), the algorithm unique removes all but the first element. |
| /// That is, unique returns an iterator new_last such that the range [first, |
| /// new_last) contains no two consecutive elements that are duplicates. |
| /// The iterators in the range [new_last, last) are all still dereferenceable, |
| /// but the elements that they point to are unspecified. Unique is stable, |
| /// meaning that the relative order of elements that are not removed is |
| /// unchanged. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container> |
| inline void unique (Container& ctr) |
| { |
| ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin()), ctr.end()); |
| } |
| |
| /// Every time a consecutive group of duplicate elements appears in the range |
| /// [first, last), the algorithm unique removes all but the first element. |
| /// That is, unique returns an iterator new_last such that the range [first, |
| /// new_last) contains no two consecutive elements that are duplicates. |
| /// The iterators in the range [new_last, last) are all still dereferenceable, |
| /// but the elements that they point to are unspecified. Unique is stable, |
| /// meaning that the relative order of elements that are not removed is |
| /// unchanged. |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container, typename BinaryPredicate> |
| inline void unique (Container& ctr, BinaryPredicate binary_pred) |
| { |
| ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin(), binary_pred), ctr.end()); |
| } |
| |
| /// Reverse reverses a range. |
| /// That is: for every i such that 0 <= i <= (last - first) / 2), |
| /// it exchanges *(first + i) and *(last - (i + 1)). |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container> |
| inline void reverse (Container& ctr) |
| { |
| reverse (ctr.begin(), ctr.end()); |
| } |
| |
| /// Exchanges ranges [first, middle) and [middle, last) |
| /// \ingroup MutatingAlgorithms |
| /// |
| template <typename Container> |
| inline void rotate (Container& ctr, off_t offset) |
| { |
| assert (size_t(offset > 0 ? offset : -offset) < ctr.size()); |
| if (offset > 0) |
| rotate (ctr.begin(), ctr.end() - offset, ctr.end()); |
| else |
| rotate (ctr.begin(), ctr.begin() - offset, ctr.end()); |
| } |
| |
| /// Returns the furthermost iterator i in [first, last) such that, |
| /// for every iterator j in [first, i), *j < value |
| /// Assumes the range is sorted. |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container, typename LessThanComparable> |
| inline typename Container::const_iterator lower_bound (const Container& ctr, const LessThanComparable& value) |
| { |
| return (lower_bound (ctr.begin(), ctr.end(), value)); |
| } |
| template <typename Container, typename LessThanComparable> |
| inline typename Container::iterator lower_bound (Container& ctr, const LessThanComparable& value) |
| { |
| return (lower_bound (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Returns the furthermost iterator i in [first,last) such that for |
| /// every iterator j in [first,i), value < *j is false. |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container, typename LessThanComparable> |
| inline typename Container::const_iterator upper_bound (const Container& ctr, const LessThanComparable& value) |
| { |
| return (upper_bound (ctr.begin(), ctr.end(), value)); |
| } |
| template <typename Container, typename LessThanComparable> |
| inline typename Container::iterator upper_bound (Container& ctr, const LessThanComparable& value) |
| { |
| return (upper_bound (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Performs a binary search for \p value. |
| /// Assumes the range is sorted. |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container> |
| inline typename Container::const_iterator binary_search (const Container& ctr, const typename Container::value_type& value) |
| { |
| return (binary_search (ctr.begin(), ctr.end(), value)); |
| } |
| template <typename Container> |
| inline typename Container::iterator binary_search (Container& ctr, const typename Container::value_type& value) |
| { |
| return (binary_search (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Returns pair<lower_bound,upper_bound> |
| /// \ingroup SearchingAlgorithms |
| /// |
| template <typename Container, typename LessThanComparable> |
| inline pair<typename Container::const_iterator,typename Container::const_iterator> equal_range (const Container& ctr, const LessThanComparable& value) |
| { |
| return (equal_range (ctr.begin(), ctr.end(), value)); |
| } |
| template <typename Container, typename LessThanComparable> |
| inline pair<typename Container::iterator,typename Container::iterator> equal_range (Container& ctr, const LessThanComparable& value) |
| { |
| return (equal_range (ctr.begin(), ctr.end(), value)); |
| } |
| |
| /// Sorts the container |
| /// \ingroup SortingAlgorithms |
| /// |
| template <typename Container> |
| inline void sort (Container& ctr) |
| { |
| sort (ctr.begin(), ctr.end()); |
| } |
| |
| /// Sorts the container |
| /// \ingroup SortingAlgorithms |
| /// |
| template <typename Container, typename Compare> |
| inline void sort (Container& ctr, Compare comp) |
| { |
| sort (ctr.begin(), ctr.end(), comp); |
| } |
| |
| /// Sorts the container |
| /// \ingroup SortingAlgorithms |
| /// |
| template <typename Container> |
| inline void stable_sort (Container& ctr) |
| { |
| stable_sort (ctr.begin(), ctr.end()); |
| } |
| |
| /// Sorts the container |
| /// \ingroup SortingAlgorithms |
| /// |
| template <typename Container, typename Compare> |
| inline void stable_sort (Container& ctr, Compare comp) |
| { |
| stable_sort (ctr.begin(), ctr.end(), comp); |
| } |
| |
| } // namespace ustl |
| |
| #endif |
| |