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. 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 = array();
  51                 foreach ( $array as $elt ) {
  52                         $hashes[$elt] = md5( $elt . $separator . $key );
  53                 }
  54                 uasort( $array, 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 bool|int|string
  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 string $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 = call_user_func( $valueCallback, $mid );
 124                         $comparison = call_user_func( $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 = call_user_func( $valueCallback, $min );
 137                         $comparison = call_user_func( $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 $array2,... 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 ) {
 159                 $arrays = func_get_args();
 160                 array_shift( $arrays );
 161                 $ret = array();
 162
 163                 foreach ( $array1 as $key => $value ) {
 164                         if ( is_array( $value ) ) {
 165                                 $args = array( $value );
 166                                 foreach ( $arrays as $array ) {
 167                                         if ( isset( $array[$key] ) ) {
 168                                                 $args[] = $array[$key];
 169                                         }
 170                                 }
 171                                 $valueret = call_user_func_array( __METHOD__, $args );
 172                                 if ( count( $valueret ) ) {
 173                                         $ret[$key] = $valueret;
 174                                 }
 175                         } else {
 176                                 foreach ( $arrays as $array ) {
 177                                         if ( isset( $array[$key] ) && $array[$key] === $value ) {
 178                                                 continue 2;
 179                                         }
 180                                 }
 181                                 $ret[$key] = $value;
 182                         }
 183                 }
 184
 185                 return $ret;
 186         }
 187 }