jenkins-bot has submitted this change and it was merged.
Change subject: core: Add binarySearch() utility from VisualEditor
......................................................................
core: Add binarySearch() utility from VisualEditor
Change-Id: I39eb1ebe7ad1e7656128fa0a33f3288029095861
---
M src/core.js
M tests/unit/core.test.js
2 files changed, 83 insertions(+), 0 deletions(-)
Approvals:
Catrope: Looks good to me, approved
jenkins-bot: Verified
diff --git a/src/core.js b/src/core.js
index cd785a2..62d2a6d 100644
--- a/src/core.js
+++ b/src/core.js
@@ -279,6 +279,42 @@
};
/**
+ * Use binary search to locate an element in a sorted array.
+ *
+ * searchFunc is given an element from the array. `searchFunc(elem)` must
return a number
+ * above 0 if the element we're searching for is to the right of (has a higher
index than) elem,
+ * below 0 if it is to the left of elem, or zero if it's equal to elem.
+ *
+ * To search for a specific value with a comparator function (a `function
cmp(a,b)` that returns
+ * above 0 if `a > b`, below 0 if `a < b`, and 0 if `a == b`), you can use
+ * `searchFunc = cmp.bind( null, value )`.
+ *
+ * @param {Array} arr Array to search in
+ * @param {Function} searchFunc Search function
+ * @param {boolean} [forInsertion] If not found, return index where val could
be inserted
+ * @return {number|null} Index where val was found, or null if not found
+ */
+oo.binarySearch = function ( arr, searchFunc, forInsertion ) {
+ var mid, cmpResult,
+ left = 0,
+ right = arr.length;
+ while ( left < right ) {
+ // Equivalent to Math.floor( ( left + right ) / 2 ) but much
faster
+ /*jshint bitwise:false */
+ mid = ( left + right ) >> 1;
+ cmpResult = searchFunc( arr[ mid ] );
+ if ( cmpResult < 0 ) {
+ right = mid;
+ } else if ( cmpResult > 0 ) {
+ left = mid + 1;
+ } else {
+ return mid;
+ }
+ }
+ return forInsertion ? right : null;
+};
+
+/**
* Recursively compare properties between two objects.
*
* A false result may be caused by property inequality or by properties in one
object missing from
diff --git a/tests/unit/core.test.js b/tests/unit/core.test.js
index 493a961..22eb296 100644
--- a/tests/unit/core.test.js
+++ b/tests/unit/core.test.js
@@ -405,6 +405,53 @@
);
} );
+ QUnit.test( 'binarySearch', function ( assert ) {
+ var data = [ -42, -10, 0, 2, 5, 7, 12, 21, 42, 70, 144, 1001 ];
+
+ function dir( target, item ) {
+ return target > item ? 1 : ( target < item ? -1 : 0 );
+ }
+
+ function assertSearch( target, expectedPath, expectedRet ) {
+ var ret, path = [];
+
+ ret = oo.binarySearch( data, function ( item ) {
+ path.push( item );
+ return dir( target, item );
+ } );
+
+ assert.deepEqual( path, expectedPath, 'Search ' +
target );
+ assert.strictEqual( ret, expectedRet, 'Search ' +
target + ' (index)' );
+ }
+
+ assertSearch( 12, [ 12 ], 6 );
+ assertSearch( -42, [ 12, 2, -10, -42 ], 0 );
+ assertSearch( 42, [ 12, 70, 42 ], 8 );
+
+ // Out of bounds
+ assertSearch( -2000, [ 12, 2, -10, -42 ], null );
+ assertSearch( 2000, [ 12, 70, 1001 ], null );
+
+ assert.strictEqual(
+ 0,
+ oo.binarySearch( data, function ( item ) { return dir(
-2000, item ); }, true ),
+ 'forInsertion at start'
+ );
+
+ assert.strictEqual(
+ 2,
+ oo.binarySearch( [ 1, 2, 4, 5 ], function ( item ) {
return dir( 3, item ); }, true ),
+ 'forInsertion in the middle'
+ );
+
+ assert.strictEqual(
+ 12,
+ oo.binarySearch( data, function ( item ) { return dir(
2000, item ); }, true ),
+ 'forInsertion at end'
+ );
+
+ } );
+
QUnit.test( 'compare', function ( assert ) {
var x, y, z;
--
To view, visit https://gerrit.wikimedia.org/r/246813
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I39eb1ebe7ad1e7656128fa0a33f3288029095861
Gerrit-PatchSet: 3
Gerrit-Project: oojs/core
Gerrit-Branch: master
Gerrit-Owner: Esanders <[email protected]>
Gerrit-Reviewer: Bartosz Dziewoński <[email protected]>
Gerrit-Reviewer: Catrope <[email protected]>
Gerrit-Reviewer: Esanders <[email protected]>
Gerrit-Reviewer: Jforrester <[email protected]>
Gerrit-Reviewer: Krinkle <[email protected]>
Gerrit-Reviewer: jenkins-bot <>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
