SPD binary_search

	- Implement binary_search algorithm for keyword lookup table

Change-Id: If7526d84fe3415ca0d2bf7a1de31816b77a912c5
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/674
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

1 files changed, 86 insertions, 1 deletions

diff --git a/src/include/algorithm b/src/include/algorithm
index 0c94c82ae..d59087412 100644
--- a/src/include/algorithm
+++ b/src/include/algorithm
@@ -23,6 +23,8 @@
 #ifndef ALGORITHM
 #define ALGORITHM
 
+#include <iterator>
+
 #ifdef __cplusplus
 namespace std
 {
@@ -177,7 +179,6 @@ namespace std
         return last;
     }
 
-
     /**
      * Find the minimum element within a range.
      * @param[in] first - FwdIterator to the first position in the range.
@@ -238,6 +239,90 @@ namespace std
         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;
+    }
+
 };
 #endif