[Libreoffice-commits] online.git: loleaflet/src

[Dennis Francis (via logerrit)]

 loleaflet/src/layer/tile/CalcTileLayer.js |   39 ++++++++++++++++++++++++++----
 1 file changed, 34 insertions(+), 5 deletions(-)

New commits:
commit a77ca892813632d72c8013560c3cba99d00b208b
Author:     Dennis Francis <dennis.francis at collabora.com>
AuthorDate: Sat May 16 16:41:29 2020 +0530
Commit:     Dennis Francis <dennis.francis at collabora.com>
CommitDate: Sun Jul 5 10:04:14 2020 +0200

    Add ability to get first match in binarySearch
    
    (more details in the comments)
    This can help in a corner case (very improbable though) when we query
    for the exact end-position of a span with trailing empty span.  Lets do
    the right thing, even if that does happen only extremely rarely.
    
    Change-Id: Ib1370811c257e6ef3d52d29caf2963641bad8e40
    Reviewed-on: https://gerrit.libreoffice.org/c/online/+/97951
    Tested-by: Jenkins CollaboraOffice <jenkinscollaboraoffice at gmail.com>
    Reviewed-by: Dennis Francis <dennis.francis at collabora.com>

diff --git a/loleaflet/src/layer/tile/CalcTileLayer.js b/loleaflet/src/layer/tile/CalcTileLayer.js
index ee8173adf..030152594 100644
--- a/loleaflet/src/layer/tile/CalcTileLayer.js
+++ b/loleaflet/src/layer/tile/CalcTileLayer.js
@@ -1300,7 +1300,9 @@ L.SpanList = L.Class.extend({
 				}
 				return (testValue < valueStart) ? -1 :
 					(valueEnd < testValue) ? 1 : 0;
-			});
+			}, true /* find the first match in case of duplicates */);
+		// About the last argument: duplicates can happen, for instance if the
+		// custom field represents positions, and there are spans with zero sizes (hidden/filtered).
 	}
 
 });
@@ -1582,6 +1584,9 @@ L.DimensionOutlines = L.Class.extend({
 // Of course, this assumes that the array is sorted (w.r.t to the semantics of
 // the directionProvider when it is provided).
 // It returns the index of the match if successful else returns -1.
+// 'firstMatch' if true, some additional work is done to ensure that the index of
+// the first match (from the 0 index of the array) is returned in case there are
+// duplicates.
 //
 // directionProvider will be provided the following parameters :
 // (key, previousArrayElement, currentArrayElement, nextArrayElement)
@@ -1592,19 +1597,21 @@ L.DimensionOutlines = L.Class.extend({
 //   1: to try searching upper half,
 //  -1: to try searching lower half
 
-function binarySearch(array, key, directionProvider) {
+function binarySearch(array, key, directionProvider, firstMatch) {
 
 	if (!Array.isArray(array) || !array.length) {
 		return -1;
 	}
 
 	if (typeof directionProvider != 'function') {
-		directionProvider = function (key, testvalue) {
+		directionProvider = function (key, prevvalue, testvalue) {
 			return (key === testvalue) ? 0 :
 				(key < testvalue) ? -1 : 1;
 		};
 	}
 
+	firstMatch = (firstMatch === true);
+
 	var start = 0;
 	var end = array.length - 1;
 
@@ -1616,7 +1623,12 @@ function binarySearch(array, key, directionProvider) {
 
 	var endDir = directionProvider(key, array[end - 1], array[end]);
 	if (endDir >= 0) {
-		return endDir ? -1 : end;
+
+		if (endDir === 1) {
+			return -1;
+		}
+
+		return firstMatch ? _findFirstMatch(array, key, directionProvider, end) : end;
 	}
 
 	var mid = -1;
@@ -1637,5 +1649,22 @@ function binarySearch(array, key, directionProvider) {
 		}
 	}
 
-	return (start > end) ? -1 : mid;
+	return (start > end) ? -1 :
+		firstMatch ? _findFirstMatch(array, key, directionProvider, mid) : mid;
+}
+
+// Helper function for binarySearch().
+function _findFirstMatch(array, key, directionProvider, randomMatchingIndex) {
+
+	if (randomMatchingIndex === 0) {
+		return 0;
+	}
+
+	var index = randomMatchingIndex - 1;
+	while (index >= 0 && directionProvider(key,
+		array[index - 1], array[index], array[index + 1]) == 0) {
+		--index;
+	}
+
+	return index + 1;
 }