includes/libs/ArrayUtils.php

   1 <?php
   2 /**
   3  * Methods to play with arrays.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  */
  22
  23 /**
  24  * A collection of static methods to play with arrays.
  25  *
  26  * @since 1.21
  27  */
  28 class ArrayUtils {
  29         /**
  30          * Sort the given array in a pseudo-random order which depends only on the
  31          * given key and each element value in $array. This is typically used for load
  32          * balancing between servers each with a local cache.
  33          *
  34          * Keys are preserved. The input array is modified in place.
  35          *
  36          * Note: Benchmarking on PHP 5.3 and 5.4 indicates that for small
  37          * strings, md5() is only 10% slower than hash('joaat',...) etc.,
  38          * since the function call overhead dominates. So there's not much
  39          * justification for breaking compatibility with installations
  40          * compiled with ./configure --disable-hash.
  41          *
  42          * @param array &$array Array to sort
  43          * @param string $key
  44          * @param string $separator A separator used to delimit the array elements and the
  45          *     key. This can be chosen to provide backwards compatibility with
  46          *     various consistent hash implementations that existed before this
  47          *     function was introduced.
  48          */
  49         public static function consistentHashSort( &$array, $key, $separator = "\000" ) {
  50                 $hashes = [];
  51                 foreach ( $array as $elt ) {
  52                         $hashes[$elt] = md5( $elt . $separator . $key );
  53                 }
  54                 uasort( $array, static function ( $a, $b ) use ( $hashes ) {
  55                         return strcmp( $hashes[$a], $hashes[$b] );
  56                 } );
  57         }
  58
  59         /**
  60          * Given an array of non-normalised probabilities, this function will select
  61          * an element and return the appropriate key
  62          *
  63          * @param array $weights
  64          * @return int|string|false
  65          */
  66         public static function pickRandom( $weights ) {
  67                 if ( !is_array( $weights ) || count( $weights ) == 0 ) {
  68                         return false;
  69                 }
  70
  71                 $sum = array_sum( $weights );
  72                 if ( $sum == 0 ) {
  73                         # No loads on any of them
  74                         # In previous versions, this triggered an unweighted random selection,
  75                         # but this feature has been removed as of April 2006 to allow for strict
  76                         # separation of query groups.
  77                         return false;
  78                 }
  79                 $max = mt_getrandmax();
  80                 $rand = mt_rand( 0, $max ) / $max * $sum;
  81
  82                 $sum = 0;
  83                 foreach ( $weights as $i => $w ) {
  84                         $sum += $w;
  85                         # Do not return keys if they have 0 weight.
  86                         # Note that the "all 0 weight" case is handed above
  87                         if ( $w > 0 && $sum >= $rand ) {
  88                                 break;
  89                         }
  90                 }
  91
  92                 return $i;
  93         }
  94
  95         /**
  96          * Do a binary search, and return the index of the largest item that sorts
  97          * less than or equal to the target value.
  98          *
  99          * @since 1.23
 100          *
 101          * @param callable $valueCallback A function to call to get the value with
 102          *     a given array index.
 103          * @param int $valueCount The number of items accessible via $valueCallback,
 104          *     indexed from 0 to $valueCount - 1
 105          * @param callable $comparisonCallback A callback to compare two values, returning
 106          *     -1, 0 or 1 in the style of strcmp().
 107          * @param mixed $target The target value to find.
 108          *
 109          * @return int|bool The item index of the lower bound, or false if the target value
 110          *     sorts before all items.
 111          */
 112         public static function findLowerBound( $valueCallback, $valueCount,
 113                 $comparisonCallback, $target
 114         ) {
 115                 if ( $valueCount === 0 ) {
 116                         return false;
 117                 }
 118
 119                 $min = 0;
 120                 $max = $valueCount;
 121                 do {
 122                         $mid = $min + ( ( $max - $min ) >> 1 );
 123                         $item = $valueCallback( $mid );
 124                         $comparison = $comparisonCallback( $target, $item );
 125                         if ( $comparison > 0 ) {
 126                                 $min = $mid;
 127                         } elseif ( $comparison == 0 ) {
 128                                 $min = $mid;
 129                                 break;
 130                         } else {
 131                                 $max = $mid;
 132                         }
 133                 } while ( $min < $max - 1 );
 134
 135                 if ( $min == 0 ) {
 136                         $item = $valueCallback( $min );
 137                         $comparison = $comparisonCallback( $target, $item );
 138                         if ( $comparison < 0 ) {
 139                                 // Before the first item
 140                                 return false;
 141                         }
 142                 }
 143                 return $min;
 144         }
 145
 146         /**
 147          * Do array_diff_assoc() on multi-dimensional arrays.
 148          *
 149          * Note: empty arrays are removed.
 150          *
 151          * @since 1.23
 152          *
 153          * @param array $array1 The array to compare from
 154          * @param array ...$arrays More arrays to compare against
 155          * @return array An array containing all the values from array1
 156          *               that are not present in any of the other arrays.
 157          */
 158         public static function arrayDiffAssocRecursive( $array1, ...$arrays ) {
 159                 $ret = [];
 160
 161                 foreach ( $array1 as $key => $value ) {
 162                         if ( is_array( $value ) ) {
 163                                 $args = [ $value ];
 164                                 foreach ( $arrays as $array ) {
 165                                         if ( isset( $array[$key] ) ) {
 166                                                 $args[] = $array[$key];
 167                                         }
 168                                 }
 169                                 $valueret = self::arrayDiffAssocRecursive( ...$args );
 170                                 if ( count( $valueret ) ) {
 171                                         $ret[$key] = $valueret;
 172                                 }
 173                         } else {
 174                                 foreach ( $arrays as $array ) {
 175                                         if ( isset( $array[$key] ) && $array[$key] === $value ) {
 176                                                 continue 2;
 177                                         }
 178                                 }
 179                                 $ret[$key] = $value;
 180                         }
 181                 }
 182
 183                 return $ret;
 184         }
 185
 186         /**
 187          * Make an array consisting of every combination of the elements of the
 188          * input arrays. Each element of the output array is an array with a number
 189          * of elements equal to the number of input parameters.
 190          *
 191          * In mathematical terms, this is an n-ary Cartesian product.
 192          *
 193          * For example, ArrayUtils::cartesianProduct( [ 1, 2 ], [ 'a', 'b' ] )
 194          * produces [ [ 1, 'a' ], [ 1, 'b' ], [ 2, 'a' ], [ 2, 'b' ] ]
 195          *
 196          * If any of the input arrays is empty, the result is the empty array [].
 197          * This is in keeping with the mathematical definition.
 198          *
 199          * If no parameters are given, the result is also the empty array.
 200          *
 201          * The array keys are ignored. This implementation uses the internal
 202          * pointers of the input arrays to keep track of the current position
 203          * without referring to the keys.
 204          *
 205          * @since 1.35
 206          *
 207          * @param array ...$inputArrays
 208          * @return array
 209          */
 210         public static function cartesianProduct( ...$inputArrays ) {
 211                 $numInputs = count( $inputArrays );
 212                 if ( $numInputs === 0 ) {
 213                         return [];
 214                 }
 215
 216                 // Reset the internal pointers
 217                 foreach ( $inputArrays as &$inputArray ) {
 218                         if ( !count( $inputArray ) ) {
 219                                 return [];
 220                         }
 221                         reset( $inputArray );
 222                 }
 223                 unset( $inputArray );
 224
 225                 $outputArrays = [];
 226                 $done = false;
 227                 while ( !$done ) {
 228                         // Construct the output array element
 229                         $element = [];
 230                         foreach ( $inputArrays as $inputArray ) {
 231                                 $element[] = current( $inputArray );
 232                         }
 233                         $outputArrays[] = $element;
 234
 235                         // Increment the pointers starting from the least significant.
 236                         // If the least significant rolls over back to the start of the
 237                         // array, continue with the next most significant, and so on until
 238                         // that stops happening. If all pointers roll over, we are done.
 239                         $done = true;
 240                         for ( $paramIndex = $numInputs - 1; $paramIndex >= 0; $paramIndex-- ) {
 241                                 next( $inputArrays[$paramIndex] );
 242                                 if ( key( $inputArrays[$paramIndex] ) === null ) {
 243                                         reset( $inputArrays[$paramIndex] );
 244                                         // continue
 245                                 } else {
 246                                         $done = false;
 247                                         break;
 248                                 }
 249                         }
 250                 }
 251                 return $outputArrays;
 252         }
 253 }