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>

4 files changed, 237 insertions, 7 deletions

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>
     {};
 };