Create and move some functions for class ArrayUtils

Change-Id: Id9ca20925f49e314918810fb54b3819ba9cf9c39

3 files changed, 427 insertions, 30 deletions

diff --git a/includes/Collation.php b/includes/Collation.php
index 7204f3129dfb..b51256b281e7 100644
--- a/includes/Collation.php
+++ b/includes/Collation.php
@@ -333,7 +333,7 @@ class IcuCollation extends Collation {
 		$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',
@@ -514,6 +514,8 @@ class IcuCollation extends Collation {
 	 * 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,
@@ -526,35 +528,8 @@ class IcuCollation extends Collation {
 	 *     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/includes/utils/ArrayUtils.php b/includes/utils/ArrayUtils.php
index a222f81f8c0a..802cdbcf8df7 100644
--- a/includes/utils/ArrayUtils.php
+++ b/includes/utils/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 @@ class ArrayUtils {
 
 		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/tests/phpunit/includes/ArrayUtilsTest.php b/tests/phpunit/includes/ArrayUtilsTest.php
new file mode 100644
index 000000000000..3e5ebb7a9ddc
--- /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 ),
+			),
+		);
+	}
+}