refactor LookupUtils

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1895542 13f79535-47bb-0310-9956-ffa450edef68

2 files changed, 55 insertions, 2 deletions

diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
index 4f55a70122..be113ec4bd 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
@@ -18,6 +18,7 @@
 package org.apache.poi.ss.formula.functions;
 
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.regex.Matcher;
@@ -624,7 +625,9 @@ public final class LookupUtils {
     public static int xlookupIndexOfValue(ValueEval lookupValue, ValueVector vector, MatchMode matchMode, SearchMode searchMode) throws EvaluationException {
         LookupValueComparer lookupComparer = createTolerantLookupComparer(lookupValue, true, true);
         int result;
-        if (searchMode == SearchMode.IterateBackward || searchMode == SearchMode.BinarySearchBackward) {
+        if (searchMode == SearchMode.BinarySearchForward || searchMode == SearchMode.BinarySearchBackward) {
+            result = binarySearchIndexOfValue(lookupComparer, vector, matchMode);
+        } else if (searchMode == SearchMode.IterateBackward) {
             result = lookupLastIndexOfValue(lookupComparer, vector, matchMode);
         } else {
             result = lookupFirstIndexOfValue(lookupComparer, vector, matchMode);
@@ -707,6 +710,57 @@ public final class LookupUtils {
         return bestMatchIdx;
     }
 
+    private static int binarySearchIndexOfValue(LookupValueComparer lookupComparer, ValueVector vector,
+                                                MatchMode matchMode) {
+        int bestMatchIdx = -1;
+        ValueEval bestMatchEval = null;
+        HashSet<Integer> alreadySearched = new HashSet<>();
+        BinarySearchIndexes bsi = new BinarySearchIndexes(vector.getSize());
+        while (true) {
+            int i = bsi.getMidIx();
+            if(i < 0 || alreadySearched.contains(i)) {
+                return bestMatchIdx;
+            }
+            alreadySearched.add(i);
+            ValueEval valueEval = vector.getItem(i);
+            CompareResult result = lookupComparer.compareTo(valueEval);
+            if (result.isEqual()) {
+                return i;
+            }
+            switch (matchMode) {
+                case ExactMatchFallbackToLargerValue:
+                    if (result.isLessThan()) {
+                        if (bestMatchEval == null) {
+                            bestMatchIdx = i;
+                            bestMatchEval = valueEval;
+                        } else {
+                            LookupValueComparer matchComparer = createTolerantLookupComparer(valueEval, true, true);
+                            if (matchComparer.compareTo(bestMatchEval).isLessThan()) {
+                                bestMatchIdx = i;
+                                bestMatchEval = valueEval;
+                            }
+                        }
+                    }
+                    break;
+                case ExactMatchFallbackToSmallerValue:
+                    if (result.isGreaterThan()) {
+                        if (bestMatchEval == null) {
+                            bestMatchIdx = i;
+                            bestMatchEval = valueEval;
+                        } else {
+                            LookupValueComparer matchComparer = createTolerantLookupComparer(valueEval, true, true);
+                            if (matchComparer.compareTo(bestMatchEval).isGreaterThan()) {
+                                bestMatchIdx = i;
+                                bestMatchEval = valueEval;
+                            }
+                        }
+                    }
+                    break;
+            }
+            bsi.narrowSearch(i, result.isLessThan());
+        }
+    }
+
     /**
      * Encapsulates some standard binary search functionality so the unusual Excel behaviour can
      * be clearly distinguished.
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/atp/TestXLookupFunction.java b/poi/src/test/java/org/apache/poi/ss/formula/atp/TestXLookupFunction.java
index 834a90f424..b50a2e5bc5 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/atp/TestXLookupFunction.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/atp/TestXLookupFunction.java
@@ -94,7 +94,6 @@ public class TestXLookupFunction {
         }
     }
 
-
     private HSSFWorkbook initWorkbook1() {
         HSSFWorkbook wb = new HSSFWorkbook();
         HSSFSheet sheet = wb.createSheet();