[Summary view] [Print] [Text view]

   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 array $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 array $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  }