diff options
Diffstat (limited to 'include/std/algorithm')
| -rw-r--r-- | include/std/algorithm | 762 |
1 files changed, 0 insertions, 762 deletions
diff --git a/include/std/algorithm b/include/std/algorithm deleted file mode 100644 index e47671fd..00000000 --- a/include/std/algorithm +++ /dev/null @@ -1,762 +0,0 @@ -/* IBM_PROLOG_BEGIN_TAG */ -/* This is an automatically generated prolog. */ -/* */ -/* $Source: src/include/algorithm $ */ -/* */ -/* OpenPOWER HostBoot Project */ -/* */ -/* Contributors Listed Below - COPYRIGHT 2011,2014 */ -/* [+] International Business Machines Corp. */ -/* */ -/* */ -/* Licensed under the Apache License, Version 2.0 (the "License"); */ -/* you may not use this file except in compliance with the License. */ -/* You may obtain a copy of the License at */ -/* */ -/* http://www.apache.org/licenses/LICENSE-2.0 */ -/* */ -/* Unless required by applicable law or agreed to in writing, software */ -/* distributed under the License is distributed on an "AS IS" BASIS, */ -/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or */ -/* implied. See the License for the specific language governing */ -/* permissions and limitations under the License. */ -/* */ -/* IBM_PROLOG_END_TAG */ -#ifndef ALGORITHM -#define ALGORITHM - -#include <iterator> -#include <util/impl/qsort.H> -#include <type_traits> - -#ifdef __cplusplus -namespace std -{ - /** - * Copy a range of elements - * @param[in] first InputIterator to the initial position in the source sequence. - * @param[in] last InputIterator to last position + 1 in the source sequence. - * @param[in] result OutputIterator to initial position in the destination sequence. - * @return an iterator to the last element in the destination range - * @note If both ranges overlap in such a way that result points to an elmenent in the source - * range then fuction copy_backward should be used. - */ - template <class InputIterator, class OutputIterator> - inline OutputIterator - copy (InputIterator first, InputIterator last, OutputIterator result ) - { - while(first!=last) - { - *result = *first; - ++result; - ++first; - } - return result; - } - - /** - * Copy a range of elements backwards - * @param[in] first Bidirectional iterator to the initial source position - * @param[in] last Bidirectional iterator to the final source position + 1 - * @param[in] result Bidirectional iterator to end of the destination sequence + 1. - * @return an iterator to the first element in the destination sequence. - * @note If both ranges overlap in such a way that result points to an element in the source - * range, the function copy should be used instead. - */ - template <class BidirectionalIterator1, class BidirectionalIterator2> - inline BidirectionalIterator2 - copy_backward ( BidirectionalIterator1 first, - BidirectionalIterator1 last, - BidirectionalIterator2 result ) - { - while(last!=first) - { - --result; - --last; - *result = *last; - } - return result; - } - - /** - * Exchange values of two objects - * @param[in] a reference to an object to be swaped with b - * @param[in] b reference to an object to be swaped with a - * @note this function may not be an efficient way to swap large objects. - */ - template <class T> - inline void - swap(T& a, T&b ) - { - T c(a); - a=b; - b=c; - } - - /** - * Fill a range with value - * @param[in] first ForwardIterator to the first position in the source range. - * @param[in] last ForwardIterator to the last position +1 in the source range. - * @param[in] value reference to the object used to fill the sequence. - */ - template < class ForwardIterator, class T > - inline void - fill (ForwardIterator first, ForwardIterator last, const T& value ) - { - while (first != last) - { - *first = value; - ++first; - } - } - - /** - * Fill a sequence with value - * @param[in] first OutputIterator to the first position in the sequence. - * @param[in] n number of elements in the sequence - * @param[in] value reference to the value used to fill the sequence. - */ - template < class OutputIterator, class Size, class T > - inline void - fill_n( OutputIterator first, Size n, const T& value ) - { - for(; n>0; --n) - { - *first = value; - ++first; - } - } - - /** - * Fill a sequence with a generated value - * @param[in] first OutputIterator to the first position in the sequence. - * @param[in] n number of elements in the sequence - * @param[in] gen functor to create values used to fill the sequence. - */ - template <typename OutputIterator, typename Size, typename Generator> - OutputIterator generate_n(OutputIterator first, Size n, Generator gen) - { - for(; n>0; --n) - { - *first = gen(); - ++first; - } - - return first; - } - - /** - * Return the lesser of two arguments - * @param[in] a object reference - * @param[in] b object reference - * @return reference to te lesser object - */ - template <class T> - inline const T& - min(const T& a, const T& b) - { - if( b < a) return b; - return a; - } - - /** - * Return the greater of two arguments - * @param[in] a object reference - * @param[in] b object reference - * @return reference to te greater object - */ - template <class T> - inline const T& - max(const T& a, const T& b) - { - if(a < b) return b; - return a; - } - - /** - * Find the location of an element within a range. - * @param[in] first InputIterator to the first position in the range. - * @param[in] last InputIterator to the last position in the range. - * @param[in] value Value to use for comparison. - * - * Returns the first iterator i in the range [first,last) such that - * (*i == value) or else last if no element is found. - * - * @return An iterator in the range [first,last]. last implies that no - * matching element was found. - */ - template <typename InputIterator, typename EqualityComparable> - inline InputIterator - find(InputIterator first, InputIterator last, - const EqualityComparable& value) - { - while(first != last) - { - if ((*first) == value) - return first; - - ++first; - } - - return last; - } - - /** - * Find the location of an element within a range. - * @param[in] first InputIterator to the first position in the range. - * @param[in] last InputIterator to the last position in the range. - * @param[in] pred Predicate used to compare equality. - * - * Returns the first iterator i in the range [first,last) such that - * pred(*i) is true or else last if no element is found. - * - * @return An iterator in the range [first,last]. last implies that no - * matching element was found. - */ - template <typename InputIterator, typename Predicate> - inline InputIterator - find_if(InputIterator first, InputIterator last, - Predicate pred) - { - while(first != last) - { - if (pred(*first)) - return first; - - ++first; - } - - return last; - } - - /** - * Find the minimum element within a range. - * @param[in] first - FwdIterator to the first position in the range. - * @param[in] last - FwdIterator to the last position in the range. - * - * Returns the first element (i) such that (*j) < (*i) is false for all - * other iterators. - * - * The iterator last is returned only when the range contains no elements. - * - * @return An iterator in [first, last) containing the minimum element. - * - */ - template <typename FwdIterator> - inline FwdIterator min_element(FwdIterator first, FwdIterator last) - { - if (first == last) return last; - FwdIterator e = first++; - while(first != last) - { - if ((*first) < (*e)) - { - e = first; - } - ++first; - } - return e; - } - - /** - * Find the minimum element within a range. - * @param[in] first - FwdIterator to the first position in the range. - * @param[in] last - FwdIterator to the last position in the range. - * @param[in] comp - BinaryPredicate used to perform comparison. - * - * Returns the first element (i) such that comp(*j,*i) is false for all - * other iterators. - * - * The iterator last is returned only when the range contains no elements. - * - * @return An iterator in [first, last) containing the minimum element. - * - */ - template <typename FwdIterator, typename BinaryPredicate> - inline FwdIterator min_element(FwdIterator first, FwdIterator last, - BinaryPredicate comp) - { - if (first == last) return last; - FwdIterator e = first++; - while(first != last) - { - if (comp((*first),(*e))) - { - e = first; - } - ++first; - } - return e; - } - - /** - * Find the maximum element within a range. - * @param[in] first - FwdIterator to the first position in the range. - * @param[in] last - FwdIterator to the last position in the range. - * - * Returns the first element (i) such that (*i) < (*j) is false for all - * other iterators. - * - * The iterator last is returned only when the range contains no elements. - * - * @return An iterator in [first, last) containing the minimum element. - * - */ - template <typename FwdIterator> - inline FwdIterator max_element(FwdIterator first, FwdIterator last) - { - if (first == last) return last; - FwdIterator e = first++; - while(first != last) - { - if ((*e) < (*first)) - { - e = first; - } - ++first; - } - return e; - } - - /** - * Find the maximum element within a range. - * @param[in] first - FwdIterator to the first position in the range. - * @param[in] last - FwdIterator to the last position in the range. - * @param[in] comp - BinaryPredicate used to perform comparison. - * - * Returns the first element (i) such that comp(*i,*j) is false for all - * other iterators. - * - * The iterator last is returned only when the range contains no elements. - * - * @return An iterator in [first, last) containing the minimum element. - * - */ - template <typename FwdIterator, typename BinaryPredicate> - inline FwdIterator max_element(FwdIterator first, FwdIterator last, - BinaryPredicate comp) - { - if (first == last) return last; - FwdIterator e = first++; - while(first != last) - { - if (comp((*e),(*first))) - { - e = first; - } - ++first; - } - return e; - } - - - /** - * Find the element value in an ordered range [first, last]. Specifically, - * it returns the first position where value could be inserted without - * violating the ordering. - * - * @param[in] first ForwardIterator to the first position in the range. - * @param[in] last ForwardIterator to the last position in the range. - * @param[in] value Value to use for comparison. - */ - - template <class ForwardIterator, class LessThanComparable> - inline ForwardIterator - lower_bound ( ForwardIterator first, - ForwardIterator last, - const LessThanComparable& value ) - { - ForwardIterator it; - int num = 0x0; - int range = std::distance<ForwardIterator>( first, - last ); - - while( range > 0 ) - { - it = first; - num = range / 2; - std::advance( it, num ); - - if( (*it) < value ) - { - first = ++it; - range = (range - (num+1)); - } - else - { - range = num; - } - } - - return first; - } - - /** - * Find the element value in an ordered range [first, last]. Specifically, - * it returns the first position where value could be inserted without - * violating the ordering. This is done using the comparison function - * parameter that is passed in. - * - * @param[in] first ForwardIterator to the first position in the range. - * @param[in] last ForwardIterator to the last position in the range. - * @param[in] value Value to use for comparison. - * @param[in] comp Function to do the comparison - */ - template <class ForwardIterator, class T, class StrictWeakOrdering> - inline ForwardIterator - lower_bound ( ForwardIterator first, - ForwardIterator last, - const T& value, - StrictWeakOrdering comp ) - { - ForwardIterator it; - int num = 0x0; - int range = std::distance<ForwardIterator>( first, - last ); - - while( range > 0 ) - { - it = first; - num = range / 2; - std::advance( it, num ); - - if( comp( (*it), value ) ) - { - first = ++it; - range = (range - (num+1)); - } - else - { - range = num; - } - } - - return first; - } - - /** - * Apply a functor to each element in a range. - * - * Applies functor 'f' to each element in [first, last). - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * @param[in] f - The functor. - * - * @return The functor after being having been applied. - */ - template <typename InputIterator, typename UnaryFunction> - UnaryFunction for_each(InputIterator first, InputIterator last, - UnaryFunction f) - { - while(first != last) - { - f(*first); - ++first; - } - return f; - } - - /** - * Remove a value from a range. - * - * Removes all instances matching 'value' in the range [first, last) - * and returns an iterator to the end of the new range [first, new_last) - * where nothing in the new range has 'value'. - * - * Remove does not decrease the size of the container. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * @param[in] value - The value to remove. - * - * @return An iterator 'new_last' from [first, new_last). - */ - template <typename ForwardIterator, typename T> - ForwardIterator remove(ForwardIterator first, ForwardIterator last, - const T& value) - { - // Find first match. - first = find(first, last, value); - - if (first == last) // No match found, return un-changed 'last'. - { - return last; - } - - // Match was found. 'new_last' is now the first removed element. - ForwardIterator new_last = first; - ++first; - - // Iterate through all the others. - while(first != last) - { - // If 'first' is a desired value, we need to copy it and move - // 'new_last'. - if (!(*first == value)) - { - *new_last = *first; - ++new_last; - } - - ++first; - } - - return new_last; - - } - - /** - * Remove a value from a range using a predicate. - * - * Removes all instances pred(*i) is true in the range [first, last) - * and returns an iterator to the end of the new range [first, new_last) - * where nothing in the new range has pred(*i) true. - * - * Remove does not decrease the size of the container. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * @param[in] pred - The predicate to use for comparison. - * - * @return An iterator 'new_last' from [first, new_last). - */ - template <typename ForwardIterator, typename Predicate> - ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, - Predicate pred) - { - // Find first match. - first = find_if(first, last, pred); - - if (first == last) // No match found, return un-changed 'last'. - { - return last; - } - - // Match was found. 'new_last' is now the first removed element. - ForwardIterator new_last = first; - ++first; - - // Iterate through all the others. - while(first != last) - { - // If 'first' is a desired value, we need to copy it and move - // 'new_last'. - if (!(pred(*first))) - { - *new_last = *first; - ++new_last; - } - - ++first; - } - - return new_last; - - } - - /** - * Removes consecutive duplicate entries from a range. - * - * Removes all instances where (*i == *(i-1)) in the range [first, last) - * and returns an iterator to the end of the new range [first, new_last) - * where nothing in the new range is a consecutive duplicate. - * - * Unique does not decrease the size of the container. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * - * @return An iterator 'new_last' from [first, new_last). - * - */ - template <typename ForwardIterator> - ForwardIterator unique(ForwardIterator first, ForwardIterator last) - { - // Trivial case of 0 items, return. - if (first == last) return last; - - // The algorithm keeps 3 iterators 'prev', 'first', and 'last'. The - // 'prev' iterator is always the last instance to be kept. 'last' is - // the end of the original range. 'first' is kept to be the item - // being compared. - - // Point 'prev' at the first element of the range since first item is - // a keeper. - ForwardIterator prev = first; - ++first; - - while (first != last) - { - // If the two items are not the same, we found a new item to keep. - if (!(*prev == *first)) - { - // Increment the "keep slot". - ++prev; - - // If the "keep slot" is not the element being compared, we - // need to move the new item down to that keep slot. - if (prev != first) - { - *prev = *first; - } - } - - // Advance to the next element. - ++first; - } - - // 'prev' points to the last item to be kept. Increment it to make - // it point to the one past. - ++prev; - return prev; - } - - /** - * Removes consecutive duplicate entries from a range by predicate. - * - * Removes all instances where pred(*i,*(i-1)) is true in the - * range [first, last) and returns an iterator to the end of the new - * range [first, new_last) where nothing in the new range is a - * consecutive duplicate. - * - * Unique does not decrease the size of the container. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * @param[in] pred - The predicate. - * - * @return An iterator 'new_last' from [first, new_last). - * - */ - template <typename ForwardIterator, typename BinaryPredicate> - ForwardIterator unique(ForwardIterator first, ForwardIterator last, - BinaryPredicate pred) - { - // Trivial case of 0 items, return. - if (first == last) return last; - - // The algorithm keeps 3 iterators 'prev', 'first', and 'last'. The - // 'prev' iterator is always the last instance to be kept. 'last' is - // the end of the original range. 'first' is kept to be the item - // being compared. - - // Point 'prev' at the first element of the range since first item is - // a keeper. - ForwardIterator prev = first; - ++first; - - while (first != last) - { - // If the two items are not the same, we found a new item to keep. - if (!(pred(*prev,*first))) - { - // Increment the "keep slot". - ++prev; - - // If the "keep slot" is not the element being compared, we - // need to move the new item down to that keep slot. - if (prev != first) - { - *prev = *first; - } - } - - // Advance to the next element. - ++first; - } - - // 'prev' points to the last item to be kept. Increment it to make - // it point to the one past. - ++prev; - return prev; - } - - /** Sort a range. - * - * Sorts all the elements in [first, last) using such that *i < *(i+1) - * for all items in the range. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - */ - template <typename RandomAccessIterator> - void sort(RandomAccessIterator first, RandomAccessIterator last) - { - Util::__Util_QSort_Impl::sort(first, last); - } - - /** Sort a range using a predicate - * - * Sorts all the elements in [first, last) using such that - * pred(*i, *(i+1)) is true for all items in the range. - * - * @param[in] first - The beginning of the range. - * @param[in] last - The end of the range. - * @param[in] pred - The predicate to use for comparison. - */ - template <typename RandomAccessIterator, typename StrictWeakOrdering> - void sort(RandomAccessIterator first, RandomAccessIterator last, - StrictWeakOrdering pred) - { - Util::__Util_QSort_Impl::sort(first, last, pred); - } - - /** Transform one sequence into another. - * - * Executes an operator against all elements in [first, last) and writes - * the result to another sequence. - * - * @param first - Beginning of the input range. - * @param last - Ending of the input range. - * @param result - Beginning of the output range. - * @param op - The transformation operator. - */ - template <typename InputIterator, typename OutputIterator, - typename UnaryFunction> - OutputIterator transform(InputIterator first, InputIterator last, - OutputIterator result, UnaryFunction op) - { - while (first != last) - { - *result = op(*first); - ++result; - ++first; - } - return result; - } - - /** Transform two sequences into another. - * - * Executes an operator against all elements in [first1, last1) along - * with the peer from [first2, ...) and writes the result to - * another sequence. - * - * @param first1 - Beginning of the first input range. - * @param last1 - Ending of the first input range. - * @param first2 - Beginning of the second input range. - * @param result - Beginning of the output range. - * @param op - The transformation operator. - */ - template <typename InputIterator1, typename InputIterator2, - typename OutputIterator, typename BinaryFunction> - OutputIterator transform(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, OutputIterator result, - BinaryFunction op) - { - while (first1 != last1) - { - *result = op(*first1, *first2); - ++result; - ++first1; ++first2; - } - return result; - } - - - -}; -#endif - -#endif -/* vim: set filetype=cpp : */ |
