Esanders has uploaded a new change for review.
https://gerrit.wikimedia.org/r/59966
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, 88 insertions(+), 18 deletions(-)
git pull ssh://gerrit.wikimedia.org:29418/mediawiki/extensions/VisualEditor
refs/changes/66/59966/1
diff --git a/modules/ve/dm/ve.dm.AnnotationSet.js
b/modules/ve/dm/ve.dm.AnnotationSet.js
index 3e6ff43..32197a7 100644
--- a/modules/ve/dm/ve.dm.AnnotationSet.js
+++ b/modules/ve/dm/ve.dm.AnnotationSet.js
@@ -187,7 +187,7 @@
* @returns {ve.dm.AnnotationSet} New set containing only the matching values
*/
ve.dm.AnnotationSet.prototype.filter = function ( property, filter, returnBool
) {
- var i, length, result, value;
+ var i, length, result, storeIndex, value;
if ( !returnBool ) {
// TODO: Consider alternative ways to instantiate a new set of
the same type as the subclass
result = this.clone();
@@ -197,7 +197,8 @@
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 (
( filter instanceof RegExp && filter.test(
value[property] ) ) ||
( typeof filter === 'string' && value[property] ===
filter )
@@ -205,7 +206,7 @@
if ( returnBool ) {
return true;
} else {
- result.push( value );
+ result.storeIndexes.push( storeIndex );
}
}
}
@@ -267,10 +268,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() );
};
/**
@@ -338,10 +336,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() );
};
/**
@@ -351,12 +346,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..650cf33 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,7 @@
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( '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..c5a033b 100644
--- a/modules/ve/ve.js
+++ b/modules/ve/ve.js
@@ -268,6 +268,85 @@
};
/**
+ * 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, bObj = {}, result = [];
+ for ( i = 0, ilen = b.length; i < ilen; i++ ) {
+ bObj[b[i]] = true;
+ }
+ for ( i = 0, ilen = a.length; i < ilen; i++ ) {
+ if ( Boolean(bObj[a[i]]) === 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: newchange
Gerrit-Change-Id: I079cbdfece4f6d80ec0afd61959913f13217fcb3
Gerrit-PatchSet: 1
Gerrit-Project: mediawiki/extensions/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Esanders <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
