From 4d21ab1dcc458d31c72add1742af3717f02a0063 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Reimar=20D=C3=B6ffinger?= Date: Sat, 18 Mar 2017 16:38:07 +0100 Subject: [PATCH] Add hack to make binary search a bit more robust. --- .../android/dictionary/engine/Index.java | 25 +++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) diff --git a/src/com/hughes/android/dictionary/engine/Index.java b/src/com/hughes/android/dictionary/engine/Index.java index 375e3b5..e289f49 100644 --- a/src/com/hughes/android/dictionary/engine/Index.java +++ b/src/com/hughes/android/dictionary/engine/Index.java @@ -293,6 +293,11 @@ public final class Index implements RAFSerializable { return index != -1 ? sortedIndexEntries.get(index) : null; } + private int compareIdx(String token, final Comparator sortCollator, int idx) { + final IndexEntry entry = sortedIndexEntries.get(idx); + return NormalizeComparator.compareWithoutDash(token, entry.normalizedToken(), sortCollator, dict.dictFileVersion); + } + public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) { token = normalizeToken(token); @@ -316,11 +321,27 @@ public final class Index implements RAFSerializable { } else if (comp < 0) { // System.out.println("Upper bound: " + midEntry + ", norm=" + // midEntry.normalizedToken() + ", mid=" + mid); - end = mid; + + // Hack for robustness if sort order is broken + if (mid + 2 < end && + compareIdx(token, sortCollator, mid + 1) > 0 && + compareIdx(token, sortCollator, mid + 2) > 0) { + start = mid; + } else { + end = mid; + } } else { // System.out.println("Lower bound: " + midEntry + ", norm=" + // midEntry.normalizedToken() + ", mid=" + mid); - start = mid + 1; + + // Hack for robustness if sort order is broken + if (mid - 2 >= start && + compareIdx(token, sortCollator, mid - 1) < 0 && + compareIdx(token, sortCollator, mid - 2) < 0) { + end = mid + 1; + } else { + start = mid + 1; + } } } -- 2.43.0