URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [language/] [cxx/] [ustl/] [current/] [include/] [ustl/] [upredalgo.h] - Rev 786
Compare with Previous | Blame | View Log
// This file is part of the uSTL library, an STL implementation. // // Copyright (c) 2005-2009 by Mike Sharov <msharov@users.sourceforge.net> // This file is free software, distributed under the MIT License. #ifndef UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5 #define UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5 namespace ustl { /// Copy_if copies elements from the range [first, last) to the range /// [result, result + (last - first)) if pred(*i) returns true. /// \ingroup MutatingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename OutputIterator, typename Predicate> inline OutputIterator copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred) { for (; first != last; ++first) { if (pred(*first)) { *result = *first; ++ result; } } return (result); } /// 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 /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename Predicate> inline InputIterator find_if (InputIterator first, InputIterator last, Predicate pred) { while (first != last && !pred (*first)) ++ first; return (first); } /// Returns the first iterator such that p(*i, *(i + 1)) == true. /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename BinaryPredicate> inline ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate p) { if (first != last) for (ForwardIterator prev = first; ++first != last; ++ prev) if (p (*prev, *first)) return (prev); return (last); } /// Returns the pointer to the first pair of unequal elements. /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename BinaryPredicate> inline pair<InputIterator,InputIterator> mismatch (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp) { while (first1 != last1 && comp(*first1, *first2)) ++ first1, ++ first2; return (make_pair (first1, first2)); } /// Returns true if two ranges are equal. /// This is an extension, present in uSTL and SGI STL. /// \ingroup ConditionAlgorithms /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename BinaryPredicate> inline bool equal (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp) { return (mismatch (first1, last1, first2, comp).first == last1); } /// 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 /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename Predicate> inline size_t count_if (InputIterator first, InputIterator last, Predicate pred) { size_t total = 0; for (; first != last; ++first) if (pred (*first)) ++ total; return (total); } /// 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 /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename Predicate, typename T> inline void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) { for (; first != last; ++first) if (pred (*first)) *first = 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 /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename OutputIterator, typename Predicate, typename T> inline OutputIterator replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value) { for (; first != last; ++result, ++first) *result = pred(*first) ? new_value : *first; } /// 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 /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename OutputIterator, typename Predicate> inline OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred) { for (; first != last; ++first) if (pred (*first)) *result++ = *first; return (result); } /// 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 /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename Predicate> inline ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate pred) { return (remove_copy_if (first, last, first, pred)); } /// The reason there are two different versions of unique_copy is that there /// are two different definitions of what it means for a consecutive group of /// elements to be duplicates. In the first version, the test is simple /// equality: the elements in a range [f, l) are duplicates if, for every /// iterator i in the range, either i == f or else *i == *(i-1). In the second, /// the test is an arbitrary Binary Predicate binary_pred: the elements in /// [f, l) are duplicates if, for every iterator i in the range, either /// i == f or else binary_pred(*i, *(i-1)) is true. /// \ingroup MutatingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename InputIterator, typename OutputIterator, typename BinaryPredicate> OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred) { if (first != last) { *result = *first; while (++first != last) if (!binary_pred (*first, *result)) *++result = *first; ++ result; } return (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 /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename BinaryPredicate> inline ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) { return (unique_copy (first, last, first, binary_pred)); } /// Returns the furthermost iterator i in [first, last) such that, /// for every iterator j in [first, i), comp(*j, value) is true. /// Assumes the range is sorted. /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename T, typename StrictWeakOrdering> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) { ForwardIterator mid; while (first != last) { mid = advance (first, distance (first,last) / 2); if (comp (*mid, value)) first = mid + 1; else last = mid; } return (first); } /// Performs a binary search inside the sorted range. /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename T, typename StrictWeakOrdering> inline bool binary_search (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) { ForwardIterator found = lower_bound (first, last, value, comp); return (found != last && !comp(*found, value)); } /// Returns the furthermost iterator i in [first,last) such that for /// every iterator j in [first,i), comp(value,*j) is false. /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename T, typename StrictWeakOrdering> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) { ForwardIterator mid; while (first != last) { mid = advance (first, distance (first,last) / 2); if (comp (value, *mid)) last = mid; else first = mid + 1; } return (last); } /// Returns pair<lower_bound,upper_bound> /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename ForwardIterator, typename T, typename StrictWeakOrdering> inline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) { pair<ForwardIterator,ForwardIterator> rv; rv.second = rv.first = lower_bound (first, last, value, comp); while (rv.second != last && !comp(value, *(rv.second))) ++ rv.second; return (rv); } /// \brief Puts \p nth element into its sorted position. /// In this implementation, the entire array is sorted. The performance difference is /// so small and the function use is so rare, there is no need to have code for it. /// \ingroup SortingAlgorithms /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms /// template <typename RandomAccessIterator, typename Compare> inline void nth_element (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, Compare comp) { sort (first, last, comp); } /// \brief Searches for the first subsequence [first2,last2) in [first1,last1) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp) { const ForwardIterator1 slast = last1 - distance(first2, last2) + 1; for (; first1 < slast; ++first1) { ForwardIterator2 i = first2; ForwardIterator1 j = first1; for (; i != last2 && comp(*j, *i); ++i, ++j) ; if (i == last2) return (first1); } return (last1); } /// \brief Searches for the last subsequence [first2,last2) in [first1,last1) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate> ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp) { ForwardIterator1 s = last1 - distance(first2, last2); for (; first1 < s; --s) { ForwardIterator2 i = first2, j = s; for (; i != last2 && comp(*j, *i); ++i, ++j) ; if (i == last2) return (s); } return (last1); } /// \brief Searches for the first occurence of \p count \p values in [first, last) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename Iterator, typename T, typename BinaryPredicate> Iterator search_n (Iterator first, Iterator last, size_t count, const T& value, BinaryPredicate comp) { size_t n = 0; for (; first != last; ++first) { if (!comp (*first, value)) n = 0; else if (++n == count) return (first - --n); } return (last); } /// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate> InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp) { for (; first1 != last1; ++first1) for (ForwardIterator i = first2; i != last2; ++i) if (comp (*first1, *i)) return (first1); return (first1); } /// \brief Returns true if [first2,last2) is a subset of [first1,last1) /// \ingroup ConditionAlgorithms /// \ingroup SetAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename StrictWeakOrdering> bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp) { for (; (first1 != last1) & (first2 != last2); ++first1) { if (comp (*first2, *first1)) return (false); first2 += !comp (*first1, *first2); } return (first2 == last2); } /// \brief Merges [first1,last1) with [first2,last2) /// /// Result will contain every element that is in either set. If duplicate /// elements are present, max(n,m) is placed in the result. /// /// \ingroup SetAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) { for (; (first1 != last1) & (first2 != last2); ++result) { if (comp (*first2, *first1)) *result = *first2++; else { first2 += !comp (*first1, *first2); *result = *first1++; } } return (copy (first2, last2, copy (first1, last1, result))); } /// \brief Creates a set containing elements shared by the given ranges. /// \ingroup SetAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) { while ((first1 != last1) & (first2 != last2)) { bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1); if (b1ge2 & b2ge1) *result++ = *first1; first1 += b2ge1; first2 += b1ge2; } return (result); } /// \brief Removes from [first1,last1) elements present in [first2,last2) /// \ingroup SetAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) { while ((first1 != last1) & (first2 != last2)) { bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1); if (!b1ge2) *result++ = *first1; first1 += b2ge1; first2 += b1ge2; } return (copy (first1, last1, result)); } /// \brief Performs union of sets A-B and B-A. /// \ingroup SetAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) { while ((first1 != last1) & (first2 != last2)) { bool b1l2 = comp (*first1, *first2), b2l1 = comp (*first2, *first1); if (b1l2) *result++ = *first1; else if (b2l1) *result++ = *first2; first1 += !b2l1; first2 += !b1l2; } return (copy (first2, last2, copy (first1, last1, result))); } /// \brief Returns true if the given range is sorted. /// \ingroup ConditionAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator, typename StrictWeakOrdering> bool is_sorted (ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp) { for (ForwardIterator i = first; ++i < last; ++first) if (comp (*i, *first)) return (false); return (true); } /// \brief Compares two given containers like strcmp compares strings. /// \ingroup ConditionAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate> bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp) { for (; (first1 != last1) & (first2 != last2); ++first1, ++first2) { if (comp (*first1, *first2)) return (true); if (comp (*first2, *first1)) return (false); } return ((first1 == last1) & (first2 != last2)); } /// \brief Creates the next lexicographical permutation of [first,last). /// Returns false if no further permutations can be created. /// \ingroup GeneratorAlgorithms /// \ingroup PredicateAlgorithms template <typename BidirectionalIterator, typename StrictWeakOrdering> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) { if (distance (first, last) < 2) return (false); BidirectionalIterator i = last; for (--i; i != first; ) { --i; if (comp (i[0], i[1])) { BidirectionalIterator j = last; while (!comp (*i, *--j)) ; iter_swap (i, j); reverse (i + 1, last); return (true); } } reverse (first, last); return (false); } /// \brief Creates the previous lexicographical permutation of [first,last). /// Returns false if no further permutations can be created. /// \ingroup GeneratorAlgorithms /// \ingroup PredicateAlgorithms template <typename BidirectionalIterator, typename StrictWeakOrdering> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) { if (distance (first, last) < 2) return (false); BidirectionalIterator i = last; for (--i; i != first; ) { --i; if (comp(i[1], i[0])) { BidirectionalIterator j = last; while (!comp (*--j, *i)) ; iter_swap (i, j); reverse (i + 1, last); return (true); } } reverse (first, last); return (false); } /// \brief Returns iterator to the max element in [first,last) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator, typename BinaryPredicate> inline ForwardIterator max_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp) { ForwardIterator result = first; for (; first != last; ++first) if (comp (*result, *first)) result = first; return (result); } /// \brief Returns iterator to the min element in [first,last) /// \ingroup SearchingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator, typename BinaryPredicate> inline ForwardIterator min_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp) { ForwardIterator result = first; for (; first != last; ++first) if (comp (*first, *result)) result = first; return (result); } /// \brief Makes [first,middle) a part of the sorted array. /// Contents of [middle,last) is undefined. This implementation just calls stable_sort. /// \ingroup SortingAlgorithms /// \ingroup PredicateAlgorithms template <typename RandomAccessIterator, typename StrictWeakOrdering> inline void partial_sort (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, StrictWeakOrdering comp) { stable_sort (first, last, comp); } /// \brief Like partial_sort, but outputs to [result_first,result_last) /// \ingroup SortingAlgorithms /// \ingroup PredicateAlgorithms template <typename InputIterator, typename RandomAccessIterator, typename StrictWeakOrdering> RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering comp) { RandomAccessIterator rend = result_first; for (; first != last; ++first) { RandomAccessIterator i = result_first; for (; i != rend && comp (*i, *first); ++i) ; if (i == result_last) continue; rend += (rend < result_last); copy_backward (i, rend - 1, rend); *i = *first; } return (rend); } /// \brief Like partition, but preserves equal element order. /// \ingroup SortingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator, typename Predicate> ForwardIterator stable_partition (ForwardIterator first, ForwardIterator last, Predicate pred) { if (first == last) return (first); ForwardIterator l, r, m = advance (first, distance (first, last) / 2); if (first == m) return (pred(*first) ? last : first); l = stable_partition (first, m, pred); r = stable_partition (m, last, pred); rotate (l, m, r); return (advance (l, distance (m, r))); } /// \brief Splits [first,last) in two by \p pred. /// /// Creates two ranges [first,middle) and [middle,last), where every element /// in the former is less than every element in the latter. /// The return value is middle. /// /// \ingroup SortingAlgorithms /// \ingroup PredicateAlgorithms template <typename ForwardIterator, typename Predicate> inline ForwardIterator partition (ForwardIterator first, ForwardIterator last, Predicate pred) { return (stable_partition (first, last, pred)); } } // namespace ustl #endif