Liangent has uploaded a new change for review. https://gerrit.wikimedia.org/r/87290
Change subject: Create and move some functions for class ArrayUtils ...................................................................... Create and move some functions for class ArrayUtils Change-Id: Id9ca20925f49e314918810fb54b3819ba9cf9c39 --- M includes/ArrayUtils.php M includes/Collation.php A tests/phpunit/includes/ArrayUtilsTest.php 3 files changed, 427 insertions(+), 30 deletions(-) git pull ssh://gerrit.wikimedia.org:29418/mediawiki/core refs/changes/90/87290/1 diff --git a/includes/ArrayUtils.php b/includes/ArrayUtils.php index 985271f..7867b93 100644 --- a/includes/ArrayUtils.php +++ b/includes/ArrayUtils.php @@ -1,5 +1,28 @@ <?php +/** + * Methods to play with arrays. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * http://www.gnu.org/copyleft/gpl.html + * + * @file + */ +/** + * A collection of static methods to play with arrays. + */ class ArrayUtils { /** * Sort the given array in a pseudo-random order which depends only on the @@ -66,4 +89,92 @@ } return $i; } + + /** + * Do a binary search, and return the index of the largest item that sorts + * less than or equal to the target value. + * + * @param array $valueCallback A function to call to get the value with + * a given array index. + * @param $valueCount int The number of items accessible via $valueCallback, + * indexed from 0 to $valueCount - 1 + * @param $comparisonCallback array A callback to compare two values, returning + * -1, 0 or 1 in the style of strcmp(). + * @param $target string The target value to find. + * + * @return int|bool The item index of the lower bound, or false if the target value + * sorts before all items. + */ + public static function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) { + if ( $valueCount === 0 ) { + return false; + } + + $min = 0; + $max = $valueCount; + do { + $mid = $min + ( ( $max - $min ) >> 1 ); + $item = call_user_func( $valueCallback, $mid ); + $comparison = call_user_func( $comparisonCallback, $target, $item ); + if ( $comparison > 0 ) { + $min = $mid; + } elseif ( $comparison == 0 ) { + $min = $mid; + break; + } else { + $max = $mid; + } + } while ( $min < $max - 1 ); + + if ( $min == 0 ) { + $item = call_user_func( $valueCallback, $min ); + $comparison = call_user_func( $comparisonCallback, $target, $item ); + if ( $comparison < 0 ) { + // Before the first item + return false; + } + } + return $min; + } + + /** + * Do array_diff_assoc() on multi-dimensional arrays. + * + * Note: empty arrays are removed. + * + * @param $array1 array The array to compare from + * @param $array2 array An array to compare against + * @param ... array More arrays to compare against + * @return array An array containing all the values from array1 + * that are not present in any of the other arrays. + */ + public static function arrayDiffAssocRecursive( $array1 ) { + $arrays = func_get_args(); + array_shift( $arrays ); + $ret = array(); + + foreach ( $array1 as $key => $value ) { + if ( is_array( $value ) ) { + $args = array( $value ); + foreach ( $arrays as $array ) { + if ( isset( $array[$key] ) ) { + $args[] = $array[$key]; + } + } + $valueret = call_user_func_array( __METHOD__, $args ); + if ( count( $valueret ) ) { + $ret[$key] = $valueret; + } + } else { + foreach ( $arrays as $array ) { + if ( isset( $array[$key] ) && $array[$key] === $value ) { + continue 2; + } + } + $ret[$key] = $value; + } + } + + return $ret; + } } diff --git a/includes/Collation.php b/includes/Collation.php index b0252c7..c939aa9 100644 --- a/includes/Collation.php +++ b/includes/Collation.php @@ -328,7 +328,7 @@ $sortKey = $this->getPrimarySortKey( $string ); // Do a binary search to find the correct letter to sort under - $min = $this->findLowerBound( + $min = ArrayUtils::findLowerBound( array( $this, 'getSortKeyByLetterIndex' ), $this->getFirstLetterCount(), 'strcmp', @@ -503,6 +503,8 @@ * Do a binary search, and return the index of the largest item that sorts * less than or equal to the target value. * + * @deprecated in 1.22; use ArrayUtils::findLowerBound() instead + * * @param array $valueCallback A function to call to get the value with * a given array index. * @param int $valueCount The number of items accessible via $valueCallback, @@ -515,35 +517,8 @@ * sorts before all items. */ function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) { - if ( $valueCount === 0 ) { - return false; - } - - $min = 0; - $max = $valueCount; - do { - $mid = $min + ( ( $max - $min ) >> 1 ); - $item = call_user_func( $valueCallback, $mid ); - $comparison = call_user_func( $comparisonCallback, $target, $item ); - if ( $comparison > 0 ) { - $min = $mid; - } elseif ( $comparison == 0 ) { - $min = $mid; - break; - } else { - $max = $mid; - } - } while ( $min < $max - 1 ); - - if ( $min == 0 ) { - $item = call_user_func( $valueCallback, $min ); - $comparison = call_user_func( $comparisonCallback, $target, $item ); - if ( $comparison < 0 ) { - // Before the first item - return false; - } - } - return $min; + wfDeprecated( __METHOD__, '1.22' ); + return ArrayUtils::findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ); } static function isCjk( $codepoint ) { diff --git a/tests/phpunit/includes/ArrayUtilsTest.php b/tests/phpunit/includes/ArrayUtilsTest.php new file mode 100644 index 0000000..3e5ebb7 --- /dev/null +++ b/tests/phpunit/includes/ArrayUtilsTest.php @@ -0,0 +1,311 @@ +<?php +/** + * Test class for ArrayUtils class + * + * @group Database + */ + +class ArrayUtilsTest extends MediaWikiTestCase { + private $search; + + /** + * @covers ArrayUtils::findLowerBound + * @dataProvider provideFindLowerBound + */ + function testFindLowerBound( + $valueCallback, $valueCount, $comparisonCallback, $target, $expected + ) { + $this->assertSame( + ArrayUtils::findLowerBound( + $valueCallback, $valueCount, $comparisonCallback, $target + ), $expected + ); + } + + function provideFindLowerBound() { + $self = $this; + $indexValueCallback = function( $size ) use ( $self ) { + return function( $val ) use ( $self, $size ) { + $self->assertTrue( $val >= 0 ); + $self->assertTrue( $val < $size ); + return $val; + }; + }; + $comparisonCallback = function( $a, $b ) { + return $a - $b; + }; + + return array( + array( + $indexValueCallback( 0 ), + 0, + $comparisonCallback, + 1, + false, + ), + array( + $indexValueCallback( 1 ), + 1, + $comparisonCallback, + -1, + false, + ), + array( + $indexValueCallback( 1 ), + 1, + $comparisonCallback, + 0, + 0, + ), + array( + $indexValueCallback( 1 ), + 1, + $comparisonCallback, + 1, + 0, + ), + array( + $indexValueCallback( 2 ), + 2, + $comparisonCallback, + -1, + false, + ), + array( + $indexValueCallback( 2 ), + 2, + $comparisonCallback, + 0, + 0, + ), + array( + $indexValueCallback( 2 ), + 2, + $comparisonCallback, + 0.5, + 0, + ), + array( + $indexValueCallback( 2 ), + 2, + $comparisonCallback, + 1, + 1, + ), + array( + $indexValueCallback( 2 ), + 2, + $comparisonCallback, + 1.5, + 1, + ), + array( + $indexValueCallback( 3 ), + 3, + $comparisonCallback, + 1, + 1, + ), + array( + $indexValueCallback( 3 ), + 3, + $comparisonCallback, + 1.5, + 1, + ), + array( + $indexValueCallback( 3 ), + 3, + $comparisonCallback, + 2, + 2, + ), + array( + $indexValueCallback( 3 ), + 3, + $comparisonCallback, + 3, + 2, + ), + ); + } + + /** + * @covers ArrayUtils::arrayDiffAssocRecursive + * @dataProvider provideArrayDiffAssocRecursive + */ + function testArrayDiffAssocRecursive( $expected ) { + $args = func_get_args(); + array_shift( $args ); + $this->assertEquals( call_user_func_array( + 'ArrayUtils::arrayDiffAssocRecursive', $args + ), $expected ); + } + + function provideArrayDiffAssocRecursive() { + return array( + array( + array(), + array(), + array(), + ), + array( + array(), + array(), + array(), + array(), + ), + array( + array( 1 ), + array( 1 ), + array(), + ), + array( + array( 1 ), + array( 1 ), + array(), + array(), + ), + array( + array(), + array(), + array( 1 ), + ), + array( + array(), + array(), + array( 1 ), + array( 2 ), + ), + array( + array( '' => 1 ), + array( '' => 1 ), + array(), + ), + array( + array(), + array(), + array( '' => 1 ), + ), + array( + array( 1 ), + array( 1 ), + array( 2 ), + ), + array( + array(), + array( 1 ), + array( 2 ), + array( 1 ), + ), + array( + array(), + array( 1 ), + array( 1, 2 ), + ), + array( + array( 1 => 1 ), + array( 1 => 1 ), + array( 1 ), + ), + array( + array(), + array( 1 => 1 ), + array( 1 ), + array( 1 => 1), + ), + array( + array(), + array( 1 => 1 ), + array( 1, 1, 1 ), + ), + array( + array(), + array( array() ), + array(), + ), + array( + array(), + array( array( array() ) ), + array(), + ), + array( + array( 1, array( 1 ) ), + array( 1, array( 1 ) ), + array(), + ), + array( + array( 1 ), + array( 1, array( 1 ) ), + array( 2, array( 1 ) ), + ), + array( + array(), + array( 1, array( 1 ) ), + array( 2, array( 1 ) ), + array( 1, array( 2 ) ), + ), + array( + array( 1 ), + array( 1, array() ), + array( 2 ), + ), + array( + array(), + array( 1, array() ), + array( 2 ), + array( 1 ), + ), + array( + array( 1, array( 1 => 2 ) ), + array( 1, array( 1, 2 ) ), + array( 2, array( 1 ) ), + ), + array( + array( 1 ), + array( 1, array( 1, 2 ) ), + array( 2, array( 1 ) ), + array( 2, array( 1 => 2 ) ), + ), + array( + array( 1 => array( 1, 2 ) ), + array( 1, array( 1, 2 ) ), + array( 1, array( 2 ) ), + ), + array( + array( 1 => array( array( 2, 3 ), 2 ) ), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1, array( 2 ) ), + ), + array( + array( 1 => array( array( 2 ), 2 ) ), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1, array( array( 1 => 3 ) ) ), + ), + array( + array( 1 => array( 1 => 2 ) ), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1, array( array( 1 => 3, 0 => 2 ) ) ), + ), + array( + array( 1 => array( 1 => 2 ) ), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1, array( array( 1 => 3 ) ) ), + array( 1 => array( array( 2 ) ) ), + ), + array( + array(), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1 => array( 1 => 2, 0 => array( 1 => 3, 0 => 2 ) ), 0 => 1 ), + ), + array( + array(), + array( 1, array( array( 2, 3 ), 2 ) ), + array( 1 => array( 1 => 2 ) ), + array( 1 => array( array( 1 => 3 ) ) ), + array( 1 => array( array( 2 ) ) ), + array( 1 ), + ), + ); + } +} -- To view, visit https://gerrit.wikimedia.org/r/87290 To unsubscribe, visit https://gerrit.wikimedia.org/r/settings Gerrit-MessageType: newchange Gerrit-Change-Id: Id9ca20925f49e314918810fb54b3819ba9cf9c39 Gerrit-PatchSet: 1 Gerrit-Project: mediawiki/core Gerrit-Branch: master Gerrit-Owner: Liangent <liang...@gmail.com> _______________________________________________ MediaWiki-commits mailing list MediaWiki-commits@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
