diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/include/algorithm | 365 | ||||
| -rw-r--r-- | src/include/functional | 204 | ||||
| -rw-r--r-- | src/include/util/impl/qsort.H | 189 | ||||
| -rw-r--r-- | src/usr/testcore/lib/stltest.H | 124 |
4 files changed, 879 insertions, 3 deletions
diff --git a/src/include/algorithm b/src/include/algorithm index d59087412..7ee1106e6 100644 --- a/src/include/algorithm +++ b/src/include/algorithm @@ -24,6 +24,7 @@ #define ALGORITHM #include <iterator> +#include <util/impl/qsort.H> #ifdef __cplusplus namespace std @@ -173,7 +174,35 @@ namespace std if ((*first) == value) return first; - 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; @@ -203,7 +232,7 @@ namespace std { e = first; } - first++; + ++first; } return e; } @@ -234,12 +263,73 @@ namespace std { e = first; } - 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. @@ -323,6 +413,275 @@ namespace std 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); + } + + }; #endif diff --git a/src/include/functional b/src/include/functional index ac0b070f4..809116cf5 100644 --- a/src/include/functional +++ b/src/include/functional @@ -73,6 +73,210 @@ namespace std { return x > y; } }; +// --------------- mem_fun templates --------------- // + + template<typename Result, typename X> + struct mem_fun_t : public unary_function<X*, Result> + { + explicit mem_fun_t(Result (X::*f)()) : func(f) {} + Result operator()(X* x) const { return (x->*func)(); } + + private: + Result (X::*func)(); + }; + + template<typename Result, typename X> + struct const_mem_fun_t : public unary_function<X*, Result> + { + explicit const_mem_fun_t(Result (X::*f)() const) : func(f) {} + Result operator()(const X* x) const { return (x->*func)(); } + + private: + Result (X::*func)() const; + }; + + template<typename Result, typename X> + mem_fun_t<Result, X> mem_fun(Result (X::*f)()) + { + return mem_fun_t<Result, X>(f); + } + + template<typename Result, typename X> + const_mem_fun_t<Result, X> mem_fun(Result (X::*f)() const) + { + return const_mem_fun_t<Result, X>(f); + } + +// --------------- mem_fun1 templates --------------- // + + template<typename Result, typename X, typename Arg> + struct mem_fun1_t : public binary_function<X*, Arg, Result> + { + explicit mem_fun1_t(Result (X::*f)(Arg)) : func(f) {} + Result operator()(X* x, Arg a) const { return (x->*func)(a); } + + private: + Result (X::*func)(Arg); + }; + + template<typename Result, typename X, typename Arg> + struct const_mem_fun1_t : public binary_function<X*, Arg, Result> + { + explicit const_mem_fun1_t(Result (X::*f)(Arg) const) : func(f) {} + Result operator()(const X* x, Arg a) const { return (x->*func)(a); } + + private: + Result (X::*func)(Arg) const; + }; + + template<typename Result, typename X, typename Arg> + mem_fun1_t<Result, X, Arg> mem_fun(Result (X::*f)(Arg)) + { + return mem_fun1_t<Result, X, Arg>(f); + } + + template<typename Result, typename X, typename Arg> + const_mem_fun1_t<Result, X, Arg> mem_fun(Result (X::*f)(Arg) const) + { + return const_mem_fun1_t<Result, X, Arg>(f); + } + +// --------------- mem_fun_ref templates --------------- // + + template<typename Result, typename X> + struct mem_fun_ref_t : public unary_function<X, Result> + { + explicit mem_fun_ref_t(Result (X::*f)()) : func(f) {} + Result operator()(X& x) const { return (x.*func)(); } + + private: + Result (X::*func)(); + }; + + template<typename Result, typename X> + struct const_mem_fun_ref_t : public unary_function<X, Result> + { + explicit const_mem_fun_ref_t(Result (X::*f)() const) : func(f) {} + Result operator()(const X& x) const { return (x.*func)(); } + + private: + Result (X::*func)() const; + }; + + template<typename Result, typename X> + mem_fun_ref_t<Result, X> mem_fun_ref(Result (X::*f)()) + { + return mem_fun_ref_t<Result, X>(f); + } + + template<typename Result, typename X> + const_mem_fun_ref_t<Result, X> mem_fun_ref(Result (X::*f)() const) + { + return const_mem_fun_ref_t<Result, X>(f); + } + +// --------------- mem_fun1_ref templates --------------- // + + template<typename Result, typename X, typename Arg> + struct mem_fun1_ref_t : public binary_function<X, Arg, Result> + { + explicit mem_fun1_ref_t(Result (X::*f)(Arg)) : func(f) {} + Result operator()(X& x, Arg a) const { return (x.*func)(a); } + + private: + Result (X::*func)(Arg); + }; + + template<typename Result, typename X, typename Arg> + struct const_mem_fun1_ref_t : public binary_function<X, Arg, Result> + { + explicit const_mem_fun1_ref_t(Result (X::*f)(Arg) const) : func(f) {} + Result operator()(const X& x, Arg a) const { return (x.*func)(a); } + + private: + Result (X::*func)(Arg) const; + }; + + template<typename Result, typename X, typename Arg> + mem_fun1_ref_t<Result, X, Arg> mem_fun_ref(Result (X::*f)(Arg)) + { + return mem_fun1_ref_t<Result, X, Arg>(f); + } + + template<typename Result, typename X, typename Arg> + const_mem_fun1_ref_t<Result, X, Arg> mem_fun_ref(Result (X::*f)(Arg) const) + { + return const_mem_fun1_ref_t<Result, X, Arg>(f); + } + +// --------------- bind1st templates --------------- // + + template<typename AdaptableBinaryFunction> + struct binder1st : + public unary_function< + typename AdaptableBinaryFunction::second_argument_type, + typename AdaptableBinaryFunction::result_type + > + { + binder1st(const AdaptableBinaryFunction& F, + typename AdaptableBinaryFunction::first_argument_type c) : + func(F), arg(c) {} + + typename AdaptableBinaryFunction::result_type + operator()(const typename + AdaptableBinaryFunction::second_argument_type& x) const + { + return func(arg, x); + } + + private: + AdaptableBinaryFunction func; + typename AdaptableBinaryFunction::first_argument_type arg; + }; + + template<typename AdaptableBinaryFunction, typename T> + binder1st<AdaptableBinaryFunction> + bind1st(const AdaptableBinaryFunction& F, + const T& c) + { + return binder1st<AdaptableBinaryFunction>(F, + typename AdaptableBinaryFunction::first_argument_type(c)); + }; + +// --------------- bind2nd templates --------------- // + + template<typename AdaptableBinaryFunction> + struct binder2nd : + public unary_function< + typename AdaptableBinaryFunction::first_argument_type, + typename AdaptableBinaryFunction::result_type + > + { + binder2nd(const AdaptableBinaryFunction& F, + typename AdaptableBinaryFunction::second_argument_type c) : + func(F), arg(c) {} + + typename AdaptableBinaryFunction::result_type + operator()(const typename + AdaptableBinaryFunction::first_argument_type& x) const + { + return func(x, arg); + } + + private: + AdaptableBinaryFunction func; + typename AdaptableBinaryFunction::second_argument_type arg; + }; + + template<typename AdaptableBinaryFunction, typename T> + binder2nd<AdaptableBinaryFunction> + bind2nd(const AdaptableBinaryFunction& F, + const T& c) + { + return binder2nd<AdaptableBinaryFunction>(F, + typename AdaptableBinaryFunction::second_argument_type(c)); + }; + }; #endif diff --git a/src/include/util/impl/qsort.H b/src/include/util/impl/qsort.H new file mode 100644 index 000000000..3146d7d73 --- /dev/null +++ b/src/include/util/impl/qsort.H @@ -0,0 +1,189 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/qsort.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_QSORT_H +#define __UTIL_IMPL_QSORT_H + +/** @file qsort.H + * + * Contains the internal implementation details of std::sort implemented as + * quick-sort. + */ + +#include <iterator> + +// Forward declaration due to 'swap' being defined in <algorithm> which is +// including this file itself. +namespace std +{ + template <typename T> void swap(T& a, T& b); +}; + +namespace Util +{ + namespace __Util_QSort_Impl + { + template <typename RandomAccessIterator> + void sort(RandomAccessIterator first, RandomAccessIterator last) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (*next < *first) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (*pos < *pivot) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + + template <typename RandomAccessIterator, typename StrictWeakOrdering> + void sort(RandomAccessIterator first, RandomAccessIterator last, + StrictWeakOrdering pred) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (pred(*next,*first)) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (pred(*pos,*pivot)) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + }; +}; + +#endif diff --git a/src/usr/testcore/lib/stltest.H b/src/usr/testcore/lib/stltest.H index dd308fdc2..7cc8963ea 100644 --- a/src/usr/testcore/lib/stltest.H +++ b/src/usr/testcore/lib/stltest.H @@ -29,6 +29,7 @@ #include <map> #include <algorithm> #include <iterator> +#include <functional> class STLTest : public CxxTest::TestSuite { @@ -349,5 +350,128 @@ class STLTest : public CxxTest::TestSuite TS_FAIL("Vector erase to end not at end()"); } } + + template<typename T> struct ForEachFunctor + : public std::unary_function<const T&, void> + { + ForEachFunctor() : count(0) {}; + + void operator()(const T&) { ++count; }; + + size_t count; + }; + + void testForEach() + { + std::vector<int> v; + const size_t COUNT = 10; + for (size_t i = 0; i < COUNT; i++) + { + v.push_back(i); + } + ForEachFunctor<int> f; + f = std::for_each(v.begin(), v.end(), f); + + if (f.count != COUNT) + { + TS_FAIL("Functor called incorrect number of times."); + } + } + + template<typename T> struct RemoveFunctor + : public std::unary_function<const T&, bool> + { + bool operator()(const T& i) { return (i == 3) || (i == 7); } + }; + + void testRemove() + { + std::vector<int> v; + const size_t COUNT = 10; + for (size_t i = 0; i < COUNT; i++) + { + v.push_back(i); + } + + if (std::distance(v.begin(), v.end()) != (ssize_t) COUNT) + { + TS_FAIL("Incorrect number of elements in the vector."); + } + + std::vector<int>::iterator new_last = + std::remove(v.begin(), v.end(), 4); + + if (std::distance(v.begin(), new_last) != (COUNT - 1)) + { + TS_FAIL("Remove did not move 1 element."); + } + + new_last = + std::remove_if(v.begin(), new_last, RemoveFunctor<int>()); + + if (std::distance(v.begin(), new_last) != (COUNT - 3)) + { + TS_FAIL("Remove_if did not move 2 element."); + } + } + + void testUnique() + { + std::vector<int> v; + const size_t COUNT = 10; + for (size_t i = 0; i < COUNT; i++) + { + v.push_back(i); + } + + std::vector<int>::iterator new_last = + std::unique(v.begin(), v.end()); + + if (new_last != v.end()) + { + TS_FAIL("Unique removed elements."); + } + + v.clear(); + v.push_back(1); + v.push_back(2); + v.push_back(2); // Remove item 1 + v.push_back(3); + v.push_back(4); + v.push_back(4); // Remove item 2 + v.push_back(4); // Remove item 3 + v.push_back(5); + // Total of 8 items. + + new_last = std::unique(v.begin(), v.end()); + + if (std::distance(v.begin(), new_last) != 5) + { + TS_FAIL("Incorrect number of items removed by unique."); + } + } + + void testSort() + { + std::vector<int> v; + v.push_back(1); + v.push_back(4); + v.push_back(2); + v.push_back(8); + v.push_back(5); + v.push_back(7); + std::sort(v.begin(), v.end()); + + for(size_t i = 0; i < (v.size()-1); i++) + { + if (v[i] >= v[i+1]) + { + TS_FAIL("Element %d is in incorrect position. %d:%d", + i, v[i], v[i+1]); + } + } + + } + }; #endif |
