Mooeypoo has uploaded a new change for review.
https://gerrit.wikimedia.org/r/249329
Change subject: Add an OO.SortedEmitterList
......................................................................
Add an OO.SortedEmitterList
Extend OO.EmitterList to produce a sorted list that automatically
inserts items in their intended positions based on a given
sorting function.
Change-Id: I3fd569691549f24c134c0ef0c3a670c0d5a2d116
---
M Gruntfile.js
A src/SortedEmitterList.js
M tests/index.html
M tests/node-index.js
A tests/unit/SortedEmitterList.test.js
5 files changed, 294 insertions(+), 0 deletions(-)
git pull ssh://gerrit.wikimedia.org:29418/oojs/core refs/changes/29/249329/1
diff --git a/Gruntfile.js b/Gruntfile.js
index 5f20890..c8d0f78 100644
--- a/Gruntfile.js
+++ b/Gruntfile.js
@@ -39,6 +39,7 @@
'src/util.js',
'src/EventEmitter.js',
'src/EmitterList.js',
+ 'src/SortedEmitterList.js',
'src/Registry.js',
'src/Factory.js',
'src/export.js',
@@ -56,6 +57,7 @@
'src/util/jquery.js',
'src/EventEmitter.js',
'src/EmitterList.js',
+ 'src/SortedEmitterList.js',
'src/Registry.js',
'src/Factory.js',
'src/export.js',
diff --git a/src/SortedEmitterList.js b/src/SortedEmitterList.js
new file mode 100644
index 0000000..259b756
--- /dev/null
+++ b/src/SortedEmitterList.js
@@ -0,0 +1,122 @@
+/**
+ * @class oo.SortedEmitterList
+ * Contains and a sorted OO.EmitterList
+ *
+ * @constructor
+ */
+oo.SortedEmitterList = function OoSortedEmitterList() {
+ // Mixin constructors
+ oo.EmitterList.call( this );
+
+ this.setSortingCallback( function ( a, b ) {
+ var aHash = oo.getHash( a ),
+ bHash = oo.getHash( b );
+
+ return aHash > bHash ? 1 :
+ ( aHash < bHash ? -1 : 0 );
+ } );
+};
+
+oo.mixinClass( oo.SortedEmitterList, oo.EmitterList );
+
+/**
+ * Set the sorting callback for this sorted list.
+ *
+ * @param {Function} sortingCallback Sorting callback
+ */
+oo.SortedEmitterList.prototype.setSortingCallback = function ( sortingCallback
) {
+ this.sortingCallback = sortingCallback;
+};
+
+/**
+ * Add items to the sorted list.
+ *
+ * @param {OO.EventEmitter|OO.EventEmitter[]} items Item to add or
+ * an array of items to add
+ */
+oo.SortedEmitterList.prototype.addItems = function ( items ) {
+ var index, i;
+
+ if ( !Array.isArray( items ) ) {
+ items = [ items ];
+ }
+
+ if ( items.length === 0 ) {
+ return this;
+ }
+
+ // Call parent mixin
+ for ( i = 0; i < items.length; i++ ) {
+ // Find the insertion index for this item
+ index = this.findInsertionIndex( items[ i ] );
+ // Make sure the item does not yet exit. If it does
+ // exist it is already in the correct position in
+ // the list
+ if ( this.items[ index ] !== items[ i ] ) {
+ // insert item at index
+ index = this.insertItem( items[ i ], index );
+ this.emit( 'add', items[ i ], index );
+ }
+ }
+};
+
+/**
+ * Normalize requested index to fit into the array.
+ * In the case of a sorted list, the index
+ *
+ * @param {OO.EventEmitter} item Items to insert
+ * @return {number} The index the item should be inserted into
+ */
+oo.SortedEmitterList.prototype.findInsertionIndex = function ( item ) {
+ var list = this;
+
+ return this.binarySearchIndex(
+ this.items,
+ // Fake a this.sortingCallback.bind( null, item ) call here
+ // otherwise this doesn't pass tests in phantomJS
+ function ( otherItem ) {
+ return list.sortingCallback( item, otherItem );
+ },
+ true
+ );
+
+};
+
+/**
+ * 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.SortedEmitterList.prototype.binarySearchIndex = function ( arr, searchFunc,
forInsertion ) {
+ // TODO: Replace this with OO.binarySearch
+ // See https://gerrit.wikimedia.org/r/#/c/246813/
+ 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;
+};
diff --git a/tests/index.html b/tests/index.html
index dcd5de1..cd1049c 100644
--- a/tests/index.html
+++ b/tests/index.html
@@ -15,6 +15,7 @@
<script src="unit/core.test.js"></script>
<script src="unit/EventEmitter.test.js"></script>
<script src="unit/EmitterList.test.js"></script>
+ <script src="unit/SortedEmitterList.test.js"></script>
<script src="unit/Factory.test.js"></script>
<script src="unit/Prioritizer.test.js"></script>
<script src="unit/Registry.test.js"></script>
diff --git a/tests/node-index.js b/tests/node-index.js
index dec4126..2f90173 100644
--- a/tests/node-index.js
+++ b/tests/node-index.js
@@ -18,6 +18,7 @@
'./tests/unit/util.test.js',
'./tests/unit/EventEmitter.test.js',
'./tests/unit/EmitterList.test.js',
+ './tests/unit/SortedEmitterList.test.js',
'./tests/unit/Registry.test.js',
'./tests/unit/Factory.test.js'
]
diff --git a/tests/unit/SortedEmitterList.test.js
b/tests/unit/SortedEmitterList.test.js
new file mode 100644
index 0000000..4929530
--- /dev/null
+++ b/tests/unit/SortedEmitterList.test.js
@@ -0,0 +1,168 @@
+( function ( oo ) {
+
+ var SortedTestList, TestItem;
+
+ // Define a test list object using the oo.SortedEmitterList mixin
+ SortedTestList = function TestList() {
+ // Mixin constructor
+ oo.EventEmitter.call( this );
+ // Mixin constructor
+ oo.SortedEmitterList.call( this );
+ };
+ oo.mixinClass( SortedTestList, oo.EventEmitter );
+ oo.mixinClass( SortedTestList, oo.SortedEmitterList );
+
+ // Define a test item object
+ TestItem = function TestItem( content ) {
+ // Mixin constructor
+ oo.EventEmitter.call( this );
+
+ this.content = content;
+ };
+ oo.mixinClass( TestItem, oo.EventEmitter );
+
+ // Helper method to recognize items by their contents
+ TestItem.prototype.getContent = function () {
+ return this.content;
+ };
+
+ // Helper method to get an array of item contents
+ // for testing
+ function getContentArray( arr ) {
+ return arr.map( function ( item ) {
+ return item.getContent();
+ } );
+ }
+
+ QUnit.module( 'SortedEmitterList' );
+
+ QUnit.test( 'addItems', function ( assert ) {
+ var initialItems = [
+ new TestItem( 'aa' ),
+ new TestItem( 'bb' ),
+ new TestItem( 'cc' )
+ ],
+ cases = [
+ {
+ items: [
+ initialItems[ 1 ], // bb
+ initialItems[ 0 ], // aa
+ initialItems[ 2 ] // cc
+ ],
+ expected: [ 'aa', 'bb', 'cc' ],
+ msg: 'Inserting items in sorted order.'
+ },
+ {
+ items: initialItems,
+ add: {
+ items: [
+ new TestItem( 'ba' ),
+ new TestItem( 'ab' ),
+ new TestItem( 'cd' ),
+ new TestItem( 'bc' )
+ ]
+ },
+ expected: [ 'aa', 'ab', 'ba', 'bb',
'bc', 'cc', 'cd' ],
+ msg: 'Inserting items into the correct
places in an existing list'
+ }
+ ];
+
+ assert.expect( cases.length );
+
+ cases.forEach( function ( test ) {
+ var list = new SortedTestList();
+ // Sort by content
+ list.setSortingCallback( function ( a, b ) {
+ return a.getContent() > b.getContent() ? 1 :
+ (
+ a.getContent() < b.getContent()
? -1 :
+ 0
+ );
+ } );
+
+ list.addItems( test.items );
+
+ if ( test.add ) {
+ list.addItems( test.add.items, test.add.index );
+ }
+
+ assert.deepEqual( getContentArray( list.getItems() ),
test.expected, test.msg );
+ }, this );
+ } );
+
+ QUnit.test( 'Events', 1, function ( assert ) {
+ var result = [],
+ list = new SortedTestList(),
+ items = [
+ new TestItem( 'aa' ),
+ new TestItem( 'bb' ),
+ new TestItem( 'cc' ),
+ new TestItem( 'dd' )
+ ],
+ stringifyEvent = function ( type, item, index ) {
+ var result = type;
+ if ( item ) {
+ result += ':' + item.getContent();
+ }
+ if ( index !== undefined ) {
+ result += '#' + index;
+ }
+ return result;
+ };
+
+ // Register
+ list.on( 'add', function ( item, index ) {
+ result.push( stringifyEvent( 'add', item, index ) );
+ } );
+ list.on( 'move', function ( item, index ) {
+ result.push( stringifyEvent( 'move', item, index ) );
+ } );
+ list.on( 'remove', function ( item, index ) {
+ result.push( stringifyEvent( 'remove', item, index ) );
+ } );
+ list.on( 'clear', function () {
+ result.push( stringifyEvent( 'clear' ) );
+ } );
+
+ // Trigger events
+ list.addItems( items );
+ list.addItems( [ new TestItem( 'ca' ) ] );
+ list.removeItems( items[ 2 ] );
+ list.addItems( [
+ new TestItem( 'ab' ),
+ new TestItem( 'ba' ),
+ new TestItem( 'bc' ),
+ new TestItem( 'cd' )
+ ] );
+ list.clearItems();
+ // Add items out of sequence
+ list.addItems( [
+ new TestItem( 'dd' ),
+ new TestItem( 'bb' ),
+ new TestItem( 'aa' ),
+ new TestItem( 'cc' )
+ ] );
+
+ assert.deepEqual( result, [
+ // addItems
+ 'add:aa#0', // [ aa ]
+ 'add:bb#1', // [ aa, bb ]
+ 'add:cc#2', // [ aa, bb, cc ]
+ 'add:dd#3', // [ aa, bb, cc, dd ]
+ // addItems
+ 'add:ca#2', // [ aa, bb, ca, cc, dd ]
+ // removeItems
+ 'remove:cc#3', // [ aa, bb, ca, dd ]
+ // addItems
+ 'add:ab#1', // [ aa, ab, bb, ca, dd ]
+ 'add:ba#2', // [ aa, ab, ba, bb, ca, dd ]
+ 'add:bc#4', // [ aa, ab, ba, bb, bc, ca, dd ]
+ 'add:cd#6', // [ aa, ab, ba, bb, bc, ca, cd, dd ]
+ 'clear',
+ 'add:dd#0', // [ dd ]
+ 'add:bb#0', // [ bb, dd]
+ 'add:aa#0', // [ aa, bb, dd]
+ 'add:cc#2' // [ aa, bb, cc, dd]
+ ], 'Events intercepted successfuly.' );
+ } );
+}( OO ) );
--
To view, visit https://gerrit.wikimedia.org/r/249329
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I3fd569691549f24c134c0ef0c3a670c0d5a2d116
Gerrit-PatchSet: 1
Gerrit-Project: oojs/core
Gerrit-Branch: master
Gerrit-Owner: Mooeypoo <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
