STL advance / distance.

Change-Id: I9cdf9459f2970def812b1681897fe7d0cdda37ac
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/669
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Terry J. Opie <opiet@us.ibm.com>
Reviewed-by: MIKE J. JONES <mjjones@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

8 files changed, 444 insertions, 7 deletions

diff --git a/src/include/iterator b/src/include/iterator
new file mode 100644
index 000000000..dbe4b2baa
--- /dev/null
+++ b/src/include/iterator
@@ -0,0 +1,107 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/iterator $
+//
+//  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 __STL_ITERATOR
+#define __STL_ITERATOR
+
+#include <stdint.h>
+
+#ifdef __cplusplus
+
+#include <util/impl/iterator.h>
+
+namespace std
+{
+
+/** @struct iterator_traits
+ *  Template class defining a mapping typenames to ones defined in an iterator.
+ */
+template <typename Iterator>
+struct iterator_traits
+{
+    typedef typename Iterator::value_type value_type;
+    typedef typename Iterator::difference_type difference_type;
+    typedef typename Iterator::pointer pointer;
+    typedef typename Iterator::reference reference;
+};
+
+/** @struct iterator_traits
+ *  Template specialization of iterator traits for treating pointer types
+ *  as an iterator.
+ */
+template <typename T>
+struct iterator_traits<T*>
+{
+    typedef T value_type;
+    typedef ptrdiff_t difference_type;
+    typedef T* pointer;
+    typedef T& reference;
+};
+
+/** Advance an iterator.
+ *
+ * @param[in] i - The iterator to advance.
+ * @param[in] n - The distance to advance the iterator.
+ *
+ * This function is equivalent to calling (++i) n times.  
+ *
+ * If the iterator supports random access then this function will be 
+ * implemented in linear time with respect to n.
+ * 
+ */
+template <typename InputIterator, typename Distance>
+void advance(InputIterator& i, Distance n)
+{
+    Util::__Util_Iterator_Impl::advance<InputIterator, Distance>(i, n);
+}
+
+/** Determine the distance between two iterators.
+ *
+ *  @param[in] first - The first iterator.
+ *  @param[in] last - The last iterator.
+ *
+ *  @return The distance between the two iterators.
+ *
+ *  The distance between two iterators is the number of times first would
+ *  need to be incremented so that it is equal to last.
+ *
+ *  If the iterator supports random access then this function will be
+ *  implemented in linear time with respect to the distance between the
+ *  two iterators.  A negative distance can only be obtained with random
+ *  access iterators.
+ */
+template <typename InputIterator>
+typename iterator_traits<InputIterator>::difference_type 
+    distance(InputIterator first, InputIterator last)
+{
+    return Util::__Util_Iterator_Impl::distance<
+                InputIterator, 
+                typename iterator_traits<InputIterator>::difference_type>
+        (first, last);
+}
+
+}; // namespace std.
+#endif
+
+#endif
+/* vim: set filetype=cpp : */
diff --git a/src/include/list b/src/include/list
index 34ec4f17a..8e07d6810 100644
--- a/src/include/list
+++ b/src/include/list
@@ -162,6 +162,8 @@ namespace std
             typedef ListIterator_t<T>        _This;
             typedef ListNodeData_t<T>       _Node;
 
+            typedef T                       value_type;
+            typedef ptrdiff_t               difference_type;
             typedef T*                      pointer;
             typedef T&                      reference;
 
@@ -292,6 +294,8 @@ namespace std
             typedef const ListNodeData_t<T>     _Node;
             typedef const ListIterator_t<T>     const_iterator;
 
+            typedef T                       value_type;
+            typedef ptrdiff_t               difference_type;
             typedef const T*                pointer;
             typedef const T&                const_reference;
 
diff --git a/src/include/stdint.h b/src/include/stdint.h
index 1f9ed95b9..e545e0f29 100644
--- a/src/include/stdint.h
+++ b/src/include/stdint.h
@@ -38,6 +38,8 @@ typedef unsigned long int 	uint64_t;
 typedef uint64_t 		size_t;
 typedef int64_t 		ssize_t;
 
+typedef ssize_t                 ptrdiff_t;
+
 #define UINT8_MAX	(255U)
 #define UINT16_MAX	(65535U)
 #define UINT32_MAX	(4294967295U)
diff --git a/src/include/util/impl/iterator.h b/src/include/util/impl/iterator.h
new file mode 100644
index 000000000..de6b445aa
--- /dev/null
+++ b/src/include/util/impl/iterator.h
@@ -0,0 +1,147 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/util/impl/iterator.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_ITERATOR_H
+#define __UTIL_IMPL_ITERATOR_H
+
+/** @file iterator.h
+ *
+ *  Contains the internal implementation details of the stl <iterator> header.
+ */
+
+#include <util/traits/has_plusequals.H>
+#include <util/traits/has_minus.H>
+
+namespace Util
+{
+    namespace __Util_Iterator_Impl
+    {
+
+        /**
+         *  Template definition of an iterator advance functor.
+         */
+        template <typename InputIterator, typename Distance,
+                  bool HasPlusEquals> struct AdvanceImpl;
+
+        /**
+         *  Template specialization of the advance functor for iterators
+         *  which do not support random access.
+         */
+        template <typename InputIterator, typename Distance>
+        struct AdvanceImpl<InputIterator, Distance, false>
+        {
+            static void advance(InputIterator& i, Distance n)
+            {
+                while(n--)
+                    ++i;
+            }
+        };
+
+        /**
+         *  Template specialization of the advance functor for iterators
+         *  which do support random access.
+         */
+        template <typename RandomIterator, typename Distance>
+        struct AdvanceImpl<RandomIterator, Distance, true>
+        {
+            static void advance(RandomIterator& i, Distance n)
+            {
+                i += n;
+            }
+        };
+
+        /**
+         *  Template wrapper function for the iterator advance.
+         *
+         *  Uses the existance of a += operator on the iterator to determine
+         *  if the random-access or non-random-access version should be used.
+         */
+        template <typename InputIterator, typename Distance>
+        void advance(InputIterator& i, Distance n)
+        {
+            AdvanceImpl<InputIterator, Distance,
+                    Util::Traits::has_plusequals<InputIterator,Distance,
+                                                 InputIterator>::value
+                >::advance(i,n);
+        }
+
+        /**
+         *  Template definition of an iterator distance functor.
+         */
+        template <typename InputIterator, typename Distance,
+                  bool HasMinus> struct DistanceImpl;
+
+        /**
+         *  Template specialization of the distance functor for iterators
+         *  which do not support random access.
+         */
+        template <typename InputIterator, typename Distance>
+        struct DistanceImpl<InputIterator, Distance, false>
+        {
+            static Distance distance(InputIterator& first,
+                                     InputIterator& last)
+            {
+                Distance i = 0;
+                while (first != last)
+                {
+                    ++i;
+                    ++first;
+                }
+                return i;
+            }
+        };
+
+        /**
+         *  Template specialization of the distance functor for iterators
+         *  which do support random access.
+         */
+        template <typename RandomIterator, typename Distance>
+        struct DistanceImpl<RandomIterator, Distance, true>
+        {
+            static Distance distance(RandomIterator& first,
+                                     RandomIterator& last)
+            {
+                return last - first;
+            }
+        };
+
+        /**
+         *  Template wrapper function for the iterator distance.
+         *
+         *  Uses the existance of a - operator on the iterator to determine
+         *  if the random-access or non-random-access version should be used.
+         */
+        template <typename InputIterator, typename Distance>
+        Distance distance(InputIterator& first,
+                          InputIterator& last)
+        {
+            return DistanceImpl<InputIterator, Distance,
+                        Util::Traits::has_minus<InputIterator, InputIterator,
+                                                Distance>::value
+                    >::distance(first,last);
+        }
+
+    };
+};
+
+#endif
diff --git a/src/include/util/traits/has_minus.H b/src/include/util/traits/has_minus.H
new file mode 100644
index 000000000..f80be8c89
--- /dev/null
+++ b/src/include/util/traits/has_minus.H
@@ -0,0 +1,40 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/traits/has_minus.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_TRAITS_HAS_MINUS
+#define __UTIL_TRAITS_HAS_MINUS
+
+/** @file has_minus.H
+ *  Creates a template class has_minus<T> who's value variable will tell
+ *  if T has a valid - operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR -
+#define UTIL_COMPARISON_OPERATOR_NAME minus
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/src/include/util/traits/has_plusequals.H b/src/include/util/traits/has_plusequals.H
new file mode 100644
index 000000000..c6fbac557
--- /dev/null
+++ b/src/include/util/traits/has_plusequals.H
@@ -0,0 +1,40 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/traits/has_plusequals.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_TRAITS_HAS_PLUSEQUALS
+#define __UTIL_TRAITS_HAS_PLUSEQUALS
+
+/** @file has_plusequals.H
+ *  Creates a template class has_plusequals<T> who's value variable will tell
+ *  if T has a valid += operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR +=
+#define UTIL_COMPARISON_OPERATOR_NAME plusequals
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/src/include/util/traits/impl/has_comparison.H b/src/include/util/traits/impl/has_comparison.H
index 4cc7a84c0..fbfb5d7ff 100644
--- a/src/include/util/traits/impl/has_comparison.H
+++ b/src/include/util/traits/impl/has_comparison.H
@@ -63,8 +63,8 @@ namespace Util
 // hide the template implementation in.
 namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
 {
-    // If "T op S" is valid, it is going to return some type (likely bool).  If
-    // it is not valid, we still need it to compile cleanly.  So what we do is
+    // If "T op S" is valid, it is going to return a type R.  If it is not
+    // valid, we still need it to compile cleanly.  So what we do is
     // create a type (convert_from_any_type) that causes implicit type
     // conversion from any other type.  We ensure that the operator against
     // convert_from_any_type returns a special type (bad_type).
@@ -84,7 +84,7 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
                                                 const convert_from_any_type&);
 
 
-    // Now, "T op T" is going to return either bad_type or something else.  We
+    // Now, "T op S" is going to return either bad_type or something else.  We
     // define a function 'has_comparison' that returns a character array of
     // different size based on the input parameter type.  Then the "sizeof"
     // can be used to tell if "T op S" returns bad_type or something else.
@@ -92,14 +92,14 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
     // The only additional oddity is the get_instance function.  Since some
     // classes cannot be directly constructed, this is a level of indirection
     // to get a type of T and S to apply the operator against.
-    template <typename _T, typename _S>
+    template <typename _T, typename _S, typename _R>
     struct UTIL_TRAIT_COMPARISON_MAKENAME(has_)
     {
         typedef char yes[1];
         typedef char no[2];
 
         static no& has_comparison(bad_type);
-        static yes& has_comparison(...);
+        static yes& has_comparison(_R);
 
         template <typename C> static C& get_instance();
 
@@ -117,10 +117,13 @@ namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
 // the __Util_Trait_Impl_OPERATOR_NAME namespace.
 namespace Traits
 {
-    template <typename _T, typename _S = _T>
+    template <typename _T, typename _S = _T,
+              typename _R = typename
+                UTIL_TRAIT_COMPARISON_MAKENAME(Util::__Util_Trait_Impl_)::
+                convert_from_any_type>
     struct UTIL_TRAIT_COMPARISON_MAKENAME(has_) :
         public UTIL_TRAIT_COMPARISON_MAKENAME(Util::__Util_Trait_Impl_)::
-               UTIL_TRAIT_COMPARISON_MAKENAME(has_)<_T,_S>
+               UTIL_TRAIT_COMPARISON_MAKENAME(has_)<_T,_S,_R>
     {};
 };
 
diff --git a/src/usr/testcore/lib/stltest.H b/src/usr/testcore/lib/stltest.H
index 8eca620cd..f2bea98c5 100644
--- a/src/usr/testcore/lib/stltest.H
+++ b/src/usr/testcore/lib/stltest.H
@@ -27,6 +27,8 @@
 #include <vector>
 #include <list>
 #include <map>
+#include <algorithm>
+#include <iterator>
 
 class STLTest : public CxxTest::TestSuite
 {
@@ -167,5 +169,97 @@ class STLTest : public CxxTest::TestSuite
                 --i;
             }
         }
+
+
+        void testAdvance()
+        {
+            // Test for a non-random-access iterator, such as list.
+            std::list<int> list;
+
+            for(int i = 0; i < 100; i++)
+                list.push_back(i);
+
+            for (int i = 0; i < 100; i++)
+            {
+                std::list<int>::iterator itr = list.begin();
+                std::advance(itr, i);
+                if (*itr != i)
+                {
+                    TS_FAIL("List iterator value mismatch %d:%d.", *itr, i);
+                }
+            }
+
+            // Test for a random-access iterator, such as vector.
+            std::vector<int> vector;
+
+            for (int i = 0; i < 100; i++)
+                vector.push_back(i);
+
+            for (int i = 0; i < 100; i++)
+            {
+                std::vector<int>::iterator itr = vector.begin();
+                std::advance(itr, i);
+                if (*itr != i)
+                {
+                    TS_FAIL("Vector iterator value mismatch %d:%d.", *itr, i);
+                }
+            }
+        }
+
+        void testDistance()
+        {
+            // Test for a non-random-access iterator, such as list.
+            std::list<int> list;
+
+            for (int i = 0; i < 100; i++)
+                list.push_back(i);
+
+            for (int i = 0; i < 100; i++)
+                for (int j = 0; j < 100; j++)
+                {
+                    // distance isn't defined for non-random-access iterator
+                    // when "first" is greater than "last".
+                    if (i > j) continue;
+
+                    std::list<int>::iterator itr_i = list.begin(),
+                                             itr_j = list.begin();
+
+                    std::advance(itr_i, i);
+                    std::advance(itr_j, j);
+
+                    ssize_t d = std::distance(itr_i, itr_j);
+
+                    if (d != (j-i))
+                    {
+                        TS_FAIL("List distance incorrect %d:%d:%d",
+                                i, j, d);
+                    }
+                }
+
+            // Test for a random-access iterator, such as vector.
+            std::vector<int> vector;
+
+            for (int i = 0; i < 100; i++)
+                vector.push_back(i);
+
+            for (int i = 0; i < 100; i++)
+                for (int j = 0; j < 100; j++)
+                {
+                    std::vector<int>::iterator itr_i = vector.begin(),
+                                               itr_j = vector.begin();
+
+                    std::advance(itr_i, i);
+                    std::advance(itr_j, j);
+
+                    ssize_t d = std::distance(itr_i, itr_j);
+
+                    if (d != (j-i))
+                    {
+                        TS_FAIL("Vector distance incorrect %d:%d:%d",
+                                i, j, d);
+                    }
+                }
+
+        }
 };
 #endif