Enhanced STL capabilities.

    - max_element
    - for_each
    - remove / remove_if
    - unique
    - sort
    - mem_fun / mem_fun_ref
    - bind1st / bind2nd

RTC: 41636
Change-Id: Icf15ef90562ed20097306a15f4a314e05511b199
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/1068
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Bradley W. Bishop <bradleyb@us.ibm.com>
Reviewed-by: Terry J. Opie <opiet@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

1 files changed, 189 insertions, 0 deletions

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