jenkins-bot has submitted this change and it was merged.
Change subject: AnnotationSet optimisations.
......................................................................
AnnotationSet optimisations.
addSet:
* Instead of indexing items in the store, just union the indexStore arrays
removeSet/removeNotInSet:
* difference or intersect the indexStore arrays
filter:
* push indices into the result set instead of values
simpleArrayUnion/Intersect/Difference have been created as utilities
in ve. They are prefixed 'simple' because they use object keys to
do fast in-array comparisons. This means they are limited to string
values or values which will compare as strings (e.g. numbers).
Change-Id: I079cbdfece4f6d80ec0afd61959913f13217fcb3
---
M modules/ve/dm/ve.dm.AnnotationSet.js
M modules/ve/test/dm/ve.dm.AnnotationSet.test.js
M modules/ve/ve.js
3 files changed, 92 insertions(+), 18 deletions(-)
Approvals:
Catrope: Looks good to me, approved
jenkins-bot: Verified
diff --git a/modules/ve/dm/ve.dm.AnnotationSet.js
b/modules/ve/dm/ve.dm.AnnotationSet.js
index c6176e8..1d0b5e7 100644
--- a/modules/ve/dm/ve.dm.AnnotationSet.js
+++ b/modules/ve/dm/ve.dm.AnnotationSet.js
@@ -185,7 +185,7 @@
* @returns {ve.dm.AnnotationSet} New set containing only the matching values
*/
ve.dm.AnnotationSet.prototype.filter = function ( callback, returnBool ) {
- var i, length, result, value;
+ var i, length, result, storeIndex, value;
if ( !returnBool ) {
result = this.clone();
@@ -195,12 +195,13 @@
result.removeAll();
}
for ( i = 0, length = this.getLength(); i < length; i++ ) {
- value = this.getStore().value( this.getIndex( i ) );
+ storeIndex = this.getIndex( i );
+ value = this.getStore().value( storeIndex );
if ( callback( value ) ) {
if ( returnBool ) {
return true;
} else {
- result.push( value );
+ result.storeIndexes.push( storeIndex );
}
}
}
@@ -261,10 +262,7 @@
* @param {ve.dm.AnnotationSet} set Set to add to the set
*/
ve.dm.AnnotationSet.prototype.addSet = function ( set ) {
- var i;
- for ( i = 0; i < set.getLength(); i++ ) {
- this.push( set.get( i ) );
- }
+ this.storeIndexes = ve.simpleArrayUnion( this.getIndexes(),
set.getIndexes() );
};
/**
@@ -332,10 +330,7 @@
* @param {ve.dm.AnnotationSet} set Set to remove from the set
*/
ve.dm.AnnotationSet.prototype.removeSet = function ( set ) {
- var i;
- for ( i = 0; i < set.getLength(); i++ ) {
- this.remove( set.get( i ) );
- }
+ this.storeIndexes = ve.simpleArrayDifference( this.getIndexes(),
set.getIndexes() );
};
/**
@@ -345,12 +340,7 @@
* @param {ve.dm.AnnotationSet} set Set to intersect with the set
*/
ve.dm.AnnotationSet.prototype.removeNotInSet = function ( set ) {
- var i;
- for ( i = this.getLength() - 1; i >= 0; i-- ) {
- if ( !set.contains( this.get( i ) ) ) {
- this.removeAt( i );
- }
- }
+ this.storeIndexes = ve.simpleArrayIntersection( this.getIndexes(),
set.getIndexes() );
};
/**
diff --git a/modules/ve/test/dm/ve.dm.AnnotationSet.test.js
b/modules/ve/test/dm/ve.dm.AnnotationSet.test.js
index 65d08e9..06096a1 100644
--- a/modules/ve/test/dm/ve.dm.AnnotationSet.test.js
+++ b/modules/ve/test/dm/ve.dm.AnnotationSet.test.js
@@ -9,7 +9,7 @@
/* Tests */
-QUnit.test( 'Basic usage', 27, function ( assert ) {
+QUnit.test( 'Basic usage', 28, function ( assert ) {
var annotationSet3,
store = new ve.dm.IndexValueStore(),
bold = new ve.dm.TextStyleBoldAnnotation(),
@@ -30,6 +30,10 @@
assert.equal( annotationSet.containsAllOf( annotationSet ), true,
'containsAllOf self is true' );
assert.equal( annotationSet.indexOf( italic ), 1, 'indexOf italic is 1'
);
assert.equal( annotationSet.indexOf( underline ), -1, 'indexOf
underline is -1' );
+ assert.deepEqual(
+ annotationSet.filter( function ( annotation ) { return
annotation.name === 'textStyle/bold'; } ).get(),
+ [ bold ], 'filter for name=textStyle/bold returns just bold
annotation'
+ );
assert.equal( annotationSet.hasAnnotationWithName( 'textStyle/bold' ),
true, 'hasAnnotationWithName textStyle/bold is true' );
assert.equal( annotationSet.hasAnnotationWithName(
'textStyle/underline' ), false, 'hasAnnotationWithName underline is false' );
diff --git a/modules/ve/ve.js b/modules/ve/ve.js
index 720e224..18220ce 100644
--- a/modules/ve/ve.js
+++ b/modules/ve/ve.js
@@ -268,6 +268,86 @@
};
/**
+ * Compute the union (duplicate-free merge) of a set of arrays.
+ *
+ * Arrays values must be convertable to object keys (strings)
+ *
+ * By building an object (with the values for keys) in parallel with
+ * the array, a new item's existence in the union can be computed faster
+ *
+ * @param {Array...} arrays Arrays to union
+ * @returns {Array} Union of the arrays
+ */
+ ve.simpleArrayUnion = function () {
+ var i, ilen, j, jlen, arr, obj = {}, result = [];
+ for ( i = 0, ilen = arguments.length; i < ilen; i++ ) {
+ arr = arguments[i];
+ for ( j = 0, jlen = arr.length; j < jlen; j++ ) {
+ if ( !obj[arr[j]] ) {
+ obj[arr[j]] = true;
+ result.push( arr[j] );
+ }
+ }
+ }
+ return result;
+ };
+
+ /**
+ * Compute the intersection of two arrays (items in both arrays).
+ *
+ * Arrays values must be convertable to object keys (strings)
+ *
+ * @param {Array} a First array
+ * @param {Array} b Second array
+ * @returns {Array} Intersection of arrays
+ */
+ ve.simpleArrayIntersection = function ( a, b ) {
+ return ve.simpleArrayCombine( a, b, true );
+ };
+
+ /**
+ * Compute the difference of two arrays (items in 'a' but not 'b').
+ *
+ * Arrays values must be convertable to object keys (strings)
+ *
+ * @param {Array} a First array
+ * @param {Array} b Second array
+ * @returns {Array} Intersection of arrays
+ */
+ ve.simpleArrayDifference = function ( a, b ) {
+ return ve.simpleArrayCombine( a, b, false );
+ };
+
+ /**
+ * Combine arrays (intersection or difference).
+ *
+ * An intersection checks the item exists in 'b' while difference
checks it doesn't.
+ *
+ * Arrays values must be convertable to object keys (strings)
+ *
+ * By building an object (with the values for keys) of 'b' we can
+ * compute the result faster
+ *
+ * @param {Array} a First array
+ * @param {Array} b Second array
+ * @param {boolean} includeB Include items in 'b'
+ * @returns {Array} Combination (intersection or difference) of arrays
+ */
+ ve.simpleArrayCombine = function ( a, b, includeB ) {
+ var i, ilen, isInB, bObj = {}, result = [];
+ for ( i = 0, ilen = b.length; i < ilen; i++ ) {
+ bObj[b[i]] = true;
+ }
+ for ( i = 0, ilen = a.length; i < ilen; i++ ) {
+ isInB = !!bObj[a[i]];
+ if ( isInB === includeB ) {
+ result.push( a[i] );
+ }
+ }
+ return result;
+ };
+
+ /**
* Merge properties of one or more objects into another.
* Preserves original object's inheritance (e.g. Array, Object,
whatever).
* In case of array or array-like objects only the indexed properties
--
To view, visit https://gerrit.wikimedia.org/r/59966
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I079cbdfece4f6d80ec0afd61959913f13217fcb3
Gerrit-PatchSet: 4
Gerrit-Project: mediawiki/extensions/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Esanders <esand...@wikimedia.org>
Gerrit-Reviewer: Catrope <roan.katt...@gmail.com>
Gerrit-Reviewer: Esanders <esand...@wikimedia.org>
Gerrit-Reviewer: jenkins-bot
_______________________________________________
MediaWiki-commits mailing list
MediaWiki-commits@lists.wikimedia.org
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
