From df74fcca6d811f21b0e61835843b03cf07e4a564 Mon Sep 17 00:00:00 2001
From: Mark Hoemmen <mhoemme@sandia.gov>
Date: Fri, 11 Mar 2016 12:40:48 +0800
Subject: [PATCH 3/3] TMP Tpetra::CrsGraph::findLocalIndex: Use findRelOffset
 (#205)

WARNING: This is a TEMPORARY COMMIT, NOT to be pushed to master
directly.

Use new Tpetra::Details::findRelOffset function in
Tpetra::CrsGraph::findLocalIndex, just to try it out.
That function will address #205.
---
 packages/tpetra/core/src/Tpetra_CrsGraph_def.hpp | 59 +++++++-----------------
 1 file changed, 16 insertions(+), 43 deletions(-)

diff --git a/packages/tpetra/core/src/Tpetra_CrsGraph_def.hpp b/packages/tpetra/core/src/Tpetra_CrsGraph_def.hpp
index dd366df..a6623fc 100644
--- a/packages/tpetra/core/src/Tpetra_CrsGraph_def.hpp
+++ b/packages/tpetra/core/src/Tpetra_CrsGraph_def.hpp
@@ -55,6 +55,7 @@
 #include "Teuchos_NullIteratorTraits.hpp"
 #include "Teuchos_as.hpp"
 #include "Teuchos_SerialDenseMatrix.hpp"
+#include "Tpetra_Util.hpp" // Tpetra::Details::findRelOffset
 
 #include <algorithm>
 #include <string>
@@ -2221,7 +2222,6 @@ namespace Tpetra {
     return this->findLocalIndex (rowinfo, ind, colInds, hint);
   }
 
-
   template <class LocalOrdinal, class GlobalOrdinal, class Node, const bool classic>
   size_t
   CrsGraph<LocalOrdinal, GlobalOrdinal, Node, classic>::
@@ -2231,50 +2231,23 @@ namespace Tpetra {
                     Kokkos::MemoryUnmanaged>& colInds,
                   const size_t hint) const
   {
-    typedef const LocalOrdinal* IT;
-
-    // NOTE (mfh 11 Oct 2015) This method assumes UVM.  We could
-    // imagine templating this method on the memory space, but makes
-    // more sense to let UVM work.
-
-    // If the hint was correct, then the hint is the offset to return.
-    if (hint < rowinfo.numEntries && colInds(hint) == ind) {
-      return hint;
-    }
-
-    // The hint was wrong, so we must search for the given column
-    // index in the column indices for the given row.  How we do the
-    // search depends on whether the graph's column indices are
-    // sorted.
-    IT beg = colInds.ptr_on_device ();
-    IT end = beg + rowinfo.numEntries;
-    IT ptr = beg + rowinfo.numEntries; // "null"
-    bool found = true;
-
-    if (isSorted ()) {
-      std::pair<IT,IT> p = std::equal_range (beg, end, ind); // binary search
-      if (p.first == p.second) {
-        found = false;
-      } else {
-        ptr = p.first;
-      }
-    }
-    else {
-      ptr = std::find (beg, end, ind); // direct search
-      if (ptr == end) {
-        found = false;
-      }
-    }
-
-    if (found) {
-      return static_cast<size_t> (ptr - beg);
-    }
-    else {
-      return Teuchos::OrdinalTraits<size_t>::invalid ();
-    }
+    using ::Tpetra::Details::findRelOffset;
+    typedef LocalOrdinal LO;
+    typedef Kokkos::View<const LO*, device_type, Kokkos::MemoryUnmanaged> IVT;
+
+    // Use the smallest possible offset type in the search.
+    const LO numEnt = rowinfo.numEntries;
+    const LO relOff = findRelOffset<LO, IVT> (colInds, numEnt, ind,
+					      static_cast<LO> (hint),
+					      this->isSorted ());
+
+    // relOff == numEnt means "not found" (compare to C++ Standard
+    // Library returning "end of sequence" in that case).
+    return (relOff == numEnt) ? 
+      Teuchos::OrdinalTraits<size_t>::invalid () : 
+      static_cast<size_t> (relOff);
   }
 
-
   template <class LocalOrdinal, class GlobalOrdinal, class Node, const bool classic>
   size_t
   CrsGraph<LocalOrdinal, GlobalOrdinal, Node, classic>::
-- 
2.5.4 (Apple Git-61)