includes/utils/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 class ArrayUtils {
  27         /**
  28          * Sort the given array in a pseudo-random order which depends only on the
  29          * given key and each element value. This is typically used for load
  30          * balancing between servers each with a local cache.
  31          *
  32          * Keys are preserved. The input array is modified in place.
  33          *
  34          * Note: Benchmarking on PHP 5.3 and 5.4 indicates that for small
  35          * strings, md5() is only 10% slower than hash('joaat',...) etc.,
  36          * since the function call overhead dominates. So there's not much
  37          * justification for breaking compatibility with installations
  38          * compiled with ./configure --disable-hash.
  39          *
  40          * @param array $array Array to sort
  41          * @param string $key
  42          * @param string $separator A separator used to delimit the array elements and the
  43          *     key. This can be chosen to provide backwards compatibility with
  44          *     various consistent hash implementations that existed before this
  45          *     function was introduced.
  46          */
  47         public static function consistentHashSort( &$array, $key, $separator = "\000" ) {
  48                 $hashes = array();
  49                 foreach ( $array as $elt ) {
  50                         $hashes[$elt] = md5( $elt . $separator . $key );
  51                 }
  52                 uasort( $array, function ( $a, $b ) use ( $hashes ) {
  53                         return strcmp( $hashes[$a], $hashes[$b] );
  54                 } );
  55         }
  56
  57         /**
  58          * Given an array of non-normalised probabilities, this function will select
  59          * an element and return the appropriate key
  60          *
  61          * @param array $weights
  62          * @return bool|int|string
  63          */
  64         public static function pickRandom( $weights ) {
  65                 if ( !is_array( $weights ) || count( $weights ) == 0 ) {
  66                         return false;
  67                 }
  68
  69                 $sum = array_sum( $weights );
  70                 if ( $sum == 0 ) {
  71                         # No loads on any of them
  72                         # In previous versions, this triggered an unweighted random selection,
  73                         # but this feature has been removed as of April 2006 to allow for strict
  74                         # separation of query groups.
  75                         return false;
  76                 }
  77                 $max = mt_getrandmax();
  78                 $rand = mt_rand( 0, $max ) / $max * $sum;
  79
  80                 $sum = 0;
  81                 foreach ( $weights as $i => $w ) {
  82                         $sum += $w;
  83                         # Do not return keys if they have 0 weight.
  84                         # Note that the "all 0 weight" case is handed above
  85                         if ( $w > 0 && $sum >= $rand ) {
  86                                 break;
  87                         }
  88                 }
  89
  90                 return $i;
  91         }
  92
  93         /**
  94          * Do a binary search, and return the index of the largest item that sorts
  95          * less than or equal to the target value.
  96          *
  97          * @param array $valueCallback A function to call to get the value with
  98          *     a given array index.
  99          * @param $valueCount int The number of items accessible via $valueCallback,
 100          *     indexed from 0 to $valueCount - 1
 101          * @param $comparisonCallback array A callback to compare two values, returning
 102          *     -1, 0 or 1 in the style of strcmp().
 103          * @param $target string The target value to find.
 104          *
 105          * @return int|bool The item index of the lower bound, or false if the target value
 106          *     sorts before all items.
 107          */
 108         public static function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
 109                 if ( $valueCount === 0 ) {
 110                         return false;
 111                 }
 112
 113                 $min = 0;
 114                 $max = $valueCount;
 115                 do {
 116                         $mid = $min + ( ( $max - $min ) >> 1 );
 117                         $item = call_user_func( $valueCallback, $mid );
 118                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 119                         if ( $comparison > 0 ) {
 120                                 $min = $mid;
 121                         } elseif ( $comparison == 0 ) {
 122                                 $min = $mid;
 123                                 break;
 124                         } else {
 125                                 $max = $mid;
 126                         }
 127                 } while ( $min < $max - 1 );
 128
 129                 if ( $min == 0 ) {
 130                         $item = call_user_func( $valueCallback, $min );
 131                         $comparison = call_user_func( $comparisonCallback, $target, $item );
 132                         if ( $comparison < 0 ) {
 133                                 // Before the first item
 134                                 return false;
 135                         }
 136                 }
 137                 return $min;
 138         }
 139
 140         /**
 141          * Do array_diff_assoc() on multi-dimensional arrays.
 142          *
 143          * Note: empty arrays are removed.
 144          *
 145          * @param $array1 array The array to compare from
 146          * @param $array2 array An array to compare against
 147          * @param ... array More arrays to compare against
 148          * @return array An array containing all the values from array1
 149          *               that are not present in any of the other arrays.
 150          */
 151         public static function arrayDiffAssocRecursive( $array1 ) {
 152                 $arrays = func_get_args();
 153                 array_shift( $arrays );
 154                 $ret = array();
 155
 156                 foreach ( $array1 as $key => $value ) {
 157                         if ( is_array( $value ) ) {
 158                                 $args = array( $value );
 159                                 foreach ( $arrays as $array ) {
 160                                         if ( isset( $array[$key] ) ) {
 161                                                 $args[] = $array[$key];
 162                                         }
 163                                 }
 164                                 $valueret = call_user_func_array( __METHOD__, $args );
 165                                 if ( count( $valueret ) ) {
 166                                         $ret[$key] = $valueret;
 167                                 }
 168                         } else {
 169                                 foreach ( $arrays as $array ) {
 170                                         if ( isset( $array[$key] ) && $array[$key] === $value ) {
 171                                                 continue 2;
 172                                         }
 173                                 }
 174                                 $ret[$key] = $value;
 175                         }
 176                 }
 177
 178                 return $ret;
 179         }
 180 }