Catrope has uploaded a new change for review.
https://gerrit.wikimedia.org/r/203474
Change subject: Add ve.binarySearch() utility and port ve.dm.MetaList#findItem
to it
......................................................................
Add ve.binarySearch() utility and port ve.dm.MetaList#findItem to it
Change-Id: Iccd8a93d2e92183a130136fd4232a9eee9540ced
---
M src/dm/ve.dm.MetaList.js
M src/ve.utils.js
2 files changed, 40 insertions(+), 22 deletions(-)
git pull ssh://gerrit.wikimedia.org:29418/VisualEditor/VisualEditor
refs/changes/74/203474/1
diff --git a/src/dm/ve.dm.MetaList.js b/src/dm/ve.dm.MetaList.js
index 0aee422..fcc0f5a 100644
--- a/src/dm/ve.dm.MetaList.js
+++ b/src/dm/ve.dm.MetaList.js
@@ -275,28 +275,13 @@
* null if not found
*/
ve.dm.MetaList.prototype.findItem = function ( offset, index, group,
forInsertion ) {
- // Binary search for the item
- var mid,
- items = typeof group === 'string' ? ( this.groups[group] || []
) : this.items,
- left = 0,
- right = items.length;
-
- while ( left < right ) {
- // Equivalent to Math.floor( ( left + right ) / 2 ) but much
faster in V8
- /*jshint bitwise:false */
- mid = ( left + right ) >> 1;
- if ( items[mid].getOffset() === offset && items[mid].getIndex()
=== index ) {
- return mid;
- }
- if ( items[mid].getOffset() < offset || (
- items[mid].getOffset() === offset &&
items[mid].getIndex() < index
- ) ) {
- left = mid + 1;
- } else {
- right = mid;
- }
- }
- return forInsertion ? left : null;
+ var items = typeof group === 'string' ? ( this.groups[group] || [] ) :
this.items;
+ return ve.binarySearch( items, function ( a, b ) {
+ return ve.compareTuples(
+ [ a.getOffset(), a.getIndex() ],
+ [ b.getOffset(), b.getIndex() ]
+ );
+ }, true );
};
/**
diff --git a/src/ve.utils.js b/src/ve.utils.js
index 3831087..19e6bd3 100644
--- a/src/ve.utils.js
+++ b/src/ve.utils.js
@@ -317,6 +317,39 @@
};
/**
+ * 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
+ * >0 if the element we're searching for is to the right of (has a higher
index than) elem,
+ * <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
+ * >0 if a > b, <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 {bool} [forInsertion] If not found, return index where val could be
inserted
+ * @return {number|null} Index where val was found, or null if not found
+ */
+ve.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 in V8
+ /*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;
+};
+
+/**
* Log data to the console.
*
* This implementation does nothing, to add a real implementation ve.debug
needs to be loaded.
--
To view, visit https://gerrit.wikimedia.org/r/203474
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: Iccd8a93d2e92183a130136fd4232a9eee9540ced
Gerrit-PatchSet: 1
Gerrit-Project: VisualEditor/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Catrope <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
