Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
83.12% |
64 / 77 |
|
80.00% |
4 / 5 |
CRAP | |
0.00% |
0 / 1 |
| ArrayUtils | |
83.12% |
64 / 77 |
|
80.00% |
4 / 5 |
36.93 | |
0.00% |
0 / 1 |
| consistentHashSort | |
100.00% |
6 / 6 |
|
100.00% |
1 / 1 |
2 | |||
| pickRandom | |
0.00% |
0 / 13 |
|
0.00% |
0 / 1 |
56 | |||
| findLowerBound | |
100.00% |
20 / 20 |
|
100.00% |
1 / 1 |
6 | |||
| arrayDiffAssocRecursive | |
100.00% |
15 / 15 |
|
100.00% |
1 / 1 |
9 | |||
| cartesianProduct | |
100.00% |
23 / 23 |
|
100.00% |
1 / 1 |
8 | |||
| 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 | } |