Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
84.78% |
78 / 92 |
|
85.71% |
6 / 7 |
CRAP | |
0.00% |
0 / 1 |
| ArrayUtils | |
85.71% |
78 / 91 |
|
85.71% |
6 / 7 |
40.99 | |
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 | |||
| arrayPlus2d | |
100.00% |
5 / 5 |
|
100.00% |
1 / 1 |
3 | |||
| insertAfter | |
100.00% |
9 / 9 |
|
100.00% |
1 / 1 |
2 | |||
| 1 | <?php |
| 2 | /** |
| 3 | * Methods to play with arrays. |
| 4 | * |
| 5 | * @license GPL-2.0-or-later |
| 6 | * @file |
| 7 | */ |
| 8 | |
| 9 | namespace Wikimedia\ArrayUtils; |
| 10 | |
| 11 | use function array_flip; |
| 12 | use function array_key_exists; |
| 13 | use function array_keys; |
| 14 | use function array_slice; |
| 15 | use function count; |
| 16 | |
| 17 | /** |
| 18 | * A collection of static methods to play with arrays. |
| 19 | * |
| 20 | * @since 1.21 |
| 21 | */ |
| 22 | class ArrayUtils { |
| 23 | /** |
| 24 | * Sort the given array in a pseudo-random order which depends only on the |
| 25 | * given key and each element value in $array. This is typically used for load |
| 26 | * balancing between servers each with a local cache. |
| 27 | * |
| 28 | * Keys are preserved. The input array is modified in place. |
| 29 | * |
| 30 | * Note: Benchmarking on PHP 5.3 and 5.4 indicates that for small |
| 31 | * strings, md5() is only 10% slower than hash('joaat',...) etc., |
| 32 | * since the function call overhead dominates. So there's not much |
| 33 | * justification for breaking compatibility with installations |
| 34 | * compiled with ./configure --disable-hash. |
| 35 | * |
| 36 | * @param array &$array Array to sort |
| 37 | * @param string $key |
| 38 | * @param string $separator A separator used to delimit the array elements and the |
| 39 | * key. This can be chosen to provide backwards compatibility with |
| 40 | * various consistent hash implementations that existed before this |
| 41 | * function was introduced. |
| 42 | */ |
| 43 | public static function consistentHashSort( &$array, $key, $separator = "\000" ) { |
| 44 | $hashes = []; |
| 45 | foreach ( $array as $elt ) { |
| 46 | $hashes[$elt] = md5( $elt . $separator . $key ); |
| 47 | } |
| 48 | uasort( $array, static function ( $a, $b ) use ( $hashes ) { |
| 49 | return strcmp( $hashes[$a], $hashes[$b] ); |
| 50 | } ); |
| 51 | } |
| 52 | |
| 53 | /** |
| 54 | * Given an array of non-normalised probabilities, this function will select |
| 55 | * an element and return the appropriate key |
| 56 | * |
| 57 | * @param array $weights |
| 58 | * @return int|string|false |
| 59 | */ |
| 60 | public static function pickRandom( $weights ) { |
| 61 | if ( !is_array( $weights ) || count( $weights ) == 0 ) { |
| 62 | return false; |
| 63 | } |
| 64 | |
| 65 | $sum = array_sum( $weights ); |
| 66 | if ( $sum == 0 ) { |
| 67 | # No loads on any of them |
| 68 | # In previous versions, this triggered an unweighted random selection, |
| 69 | # but this feature has been removed as of April 2006 to allow for strict |
| 70 | # separation of query groups. |
| 71 | return false; |
| 72 | } |
| 73 | $max = mt_getrandmax(); |
| 74 | $rand = mt_rand( 0, $max ) / $max * $sum; |
| 75 | |
| 76 | $sum = 0; |
| 77 | foreach ( $weights as $i => $w ) { |
| 78 | $sum += $w; |
| 79 | # Do not return keys if they have 0 weight. |
| 80 | # Note that the "all 0 weight" case is handed above |
| 81 | if ( $w > 0 && $sum >= $rand ) { |
| 82 | break; |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | return $i; |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Do a binary search, and return the index of the largest item that sorts |
| 91 | * less than or equal to the target value. |
| 92 | * |
| 93 | * @since 1.23 |
| 94 | * |
| 95 | * @param callable $valueCallback A function to call to get the value with |
| 96 | * a given array index. |
| 97 | * @param int $valueCount The number of items accessible via $valueCallback, |
| 98 | * indexed from 0 to $valueCount - 1 |
| 99 | * @param callable $comparisonCallback A callback to compare two values, returning |
| 100 | * -1, 0 or 1 in the style of strcmp(). |
| 101 | * @param mixed $target The target value to find. |
| 102 | * |
| 103 | * @return int|bool The item index of the lower bound, or false if the target value |
| 104 | * sorts before all items. |
| 105 | */ |
| 106 | public static function findLowerBound( $valueCallback, $valueCount, |
| 107 | $comparisonCallback, $target |
| 108 | ) { |
| 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 = $valueCallback( $mid ); |
| 118 | $comparison = $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 = $valueCallback( $min ); |
| 131 | $comparison = $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 | * @since 1.23 |
| 146 | * |
| 147 | * @param array $array1 The array to compare from |
| 148 | * @param array ...$arrays More arrays to compare against |
| 149 | * @return array An array containing all the values from array1 |
| 150 | * that are not present in any of the other arrays. |
| 151 | */ |
| 152 | public static function arrayDiffAssocRecursive( $array1, ...$arrays ) { |
| 153 | $ret = []; |
| 154 | |
| 155 | foreach ( $array1 as $key => $value ) { |
| 156 | if ( is_array( $value ) ) { |
| 157 | $args = [ $value ]; |
| 158 | foreach ( $arrays as $array ) { |
| 159 | if ( isset( $array[$key] ) ) { |
| 160 | $args[] = $array[$key]; |
| 161 | } |
| 162 | } |
| 163 | $valueret = self::arrayDiffAssocRecursive( ...$args ); |
| 164 | if ( count( $valueret ) ) { |
| 165 | $ret[$key] = $valueret; |
| 166 | } |
| 167 | } else { |
| 168 | foreach ( $arrays as $array ) { |
| 169 | if ( isset( $array[$key] ) && $array[$key] === $value ) { |
| 170 | continue 2; |
| 171 | } |
| 172 | } |
| 173 | $ret[$key] = $value; |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | return $ret; |
| 178 | } |
| 179 | |
| 180 | /** |
| 181 | * Make an array consisting of every combination of the elements of the |
| 182 | * input arrays. Each element of the output array is an array with a number |
| 183 | * of elements equal to the number of input parameters. |
| 184 | * |
| 185 | * In mathematical terms, this is an n-ary Cartesian product. |
| 186 | * |
| 187 | * For example, ArrayUtils::cartesianProduct( [ 1, 2 ], [ 'a', 'b' ] ) |
| 188 | * produces [ [ 1, 'a' ], [ 1, 'b' ], [ 2, 'a' ], [ 2, 'b' ] ] |
| 189 | * |
| 190 | * If any of the input arrays is empty, the result is the empty array []. |
| 191 | * This is in keeping with the mathematical definition. |
| 192 | * |
| 193 | * If no parameters are given, the result is also the empty array. |
| 194 | * |
| 195 | * The array keys are ignored. This implementation uses the internal |
| 196 | * pointers of the input arrays to keep track of the current position |
| 197 | * without referring to the keys. |
| 198 | * |
| 199 | * @since 1.35 |
| 200 | * |
| 201 | * @param array ...$inputArrays |
| 202 | * @return array |
| 203 | */ |
| 204 | public static function cartesianProduct( ...$inputArrays ) { |
| 205 | $numInputs = count( $inputArrays ); |
| 206 | if ( $numInputs === 0 ) { |
| 207 | return []; |
| 208 | } |
| 209 | |
| 210 | // Reset the internal pointers |
| 211 | foreach ( $inputArrays as &$inputArray ) { |
| 212 | if ( !count( $inputArray ) ) { |
| 213 | return []; |
| 214 | } |
| 215 | reset( $inputArray ); |
| 216 | } |
| 217 | unset( $inputArray ); |
| 218 | |
| 219 | $outputArrays = []; |
| 220 | $done = false; |
| 221 | while ( !$done ) { |
| 222 | // Construct the output array element |
| 223 | $element = []; |
| 224 | foreach ( $inputArrays as $inputArray ) { |
| 225 | $element[] = current( $inputArray ); |
| 226 | } |
| 227 | $outputArrays[] = $element; |
| 228 | |
| 229 | // Increment the pointers starting from the least significant. |
| 230 | // If the least significant rolls over back to the start of the |
| 231 | // array, continue with the next most significant, and so on until |
| 232 | // that stops happening. If all pointers roll over, we are done. |
| 233 | $done = true; |
| 234 | for ( $paramIndex = $numInputs - 1; $paramIndex >= 0; $paramIndex-- ) { |
| 235 | next( $inputArrays[$paramIndex] ); |
| 236 | if ( key( $inputArrays[$paramIndex] ) === null ) { |
| 237 | reset( $inputArrays[$paramIndex] ); |
| 238 | // continue |
| 239 | } else { |
| 240 | $done = false; |
| 241 | break; |
| 242 | } |
| 243 | } |
| 244 | } |
| 245 | return $outputArrays; |
| 246 | } |
| 247 | |
| 248 | /** |
| 249 | * Merges two (possibly) 2 dimensional arrays into the target array ($baseArray). |
| 250 | * |
| 251 | * Values that exist in both values will be combined with += (all values of the array |
| 252 | * of $newValues will be added to the values of the array of $baseArray, while values, |
| 253 | * that exists in both, the value of $baseArray will be used). |
| 254 | * |
| 255 | * @param array $baseArray The array where you want to add the values of $newValues to |
| 256 | * @param array $newValues An array with new values |
| 257 | * @return array The combined array |
| 258 | * @since 1.46 |
| 259 | */ |
| 260 | public static function arrayPlus2d( array $baseArray, array $newValues ): array { |
| 261 | // First merge items that are in both arrays |
| 262 | foreach ( $baseArray as $name => &$groupVal ) { |
| 263 | if ( isset( $newValues[$name] ) ) { |
| 264 | $groupVal += $newValues[$name]; |
| 265 | } |
| 266 | } |
| 267 | // Now add items that didn't exist yet |
| 268 | $baseArray += $newValues; |
| 269 | |
| 270 | return $baseArray; |
| 271 | } |
| 272 | |
| 273 | /** |
| 274 | * Insert an array into another array after the specified key. If the key is |
| 275 | * not present in the input array, it is returned without modification. |
| 276 | * |
| 277 | * @param array $array |
| 278 | * @param array $insert The array to insert. |
| 279 | * @param string|int $after The key to insert after. |
| 280 | * @return array |
| 281 | * @since 1.46 |
| 282 | */ |
| 283 | public static function insertAfter( array $array, array $insert, string|int $after ): array { |
| 284 | // Find the offset of the element to insert after. |
| 285 | $keys = array_keys( $array ); |
| 286 | $offsetByKey = array_flip( $keys ); |
| 287 | |
| 288 | if ( !array_key_exists( $after, $offsetByKey ) ) { |
| 289 | return $array; |
| 290 | } |
| 291 | $offset = $offsetByKey[$after]; |
| 292 | |
| 293 | // Insert at the specified offset |
| 294 | $before = array_slice( $array, 0, $offset + 1, true ); |
| 295 | $after = array_slice( $array, $offset + 1, count( $array ) - $offset, true ); |
| 296 | |
| 297 | $output = $before + $insert + $after; |
| 298 | |
| 299 | return $output; |
| 300 | } |
| 301 | } |
| 302 | |
| 303 | /** @deprecated class alias since 1.44 */ |
| 304 | class_alias( ArrayUtils::class, 'ArrayUtils' ); |