Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
82.05% covered (warning)
82.05%
64 / 78
80.00% covered (warning)
80.00%
4 / 5
 CRAP
0.00% covered (danger)
0.00%
0 / 1
ArrayUtils
83.12% covered (warning)
83.12%
64 / 77
80.00% covered (warning)
80.00%
4 / 5
 36.93
0.00% covered (danger)
0.00%
0 / 1
 consistentHashSort
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 2
 pickRandom
0.00% covered (danger)
0.00%
0 / 13
0.00% covered (danger)
0.00%
0 / 1
 56
 findLowerBound
100.00% covered (success)
100.00%
20 / 20
100.00% covered (success)
100.00%
1 / 1
 6
 arrayDiffAssocRecursive
100.00% covered (success)
100.00%
15 / 15
100.00% covered (success)
100.00%
1 / 1
 9
 cartesianProduct
100.00% covered (success)
100.00%
23 / 23
100.00% covered (success)
100.00%
1 / 1
 8
1<?php
2/**
3 * Methods to play with arrays.
4 *
5 * @license GPL-2.0-or-later
6 * @file
7 */
8
9namespace Wikimedia\ArrayUtils;
10
11/**
12 * A collection of static methods to play with arrays.
13 *
14 * @since 1.21
15 */
16class ArrayUtils {
17    /**
18     * Sort the given array in a pseudo-random order which depends only on the
19     * given key and each element value in $array. This is typically used for load
20     * balancing between servers each with a local cache.
21     *
22     * Keys are preserved. The input array is modified in place.
23     *
24     * Note: Benchmarking on PHP 5.3 and 5.4 indicates that for small
25     * strings, md5() is only 10% slower than hash('joaat',...) etc.,
26     * since the function call overhead dominates. So there's not much
27     * justification for breaking compatibility with installations
28     * compiled with ./configure --disable-hash.
29     *
30     * @param array &$array Array to sort
31     * @param string $key
32     * @param string $separator A separator used to delimit the array elements and the
33     *     key. This can be chosen to provide backwards compatibility with
34     *     various consistent hash implementations that existed before this
35     *     function was introduced.
36     */
37    public static function consistentHashSort( &$array, $key, $separator = "\000" ) {
38        $hashes = [];
39        foreach ( $array as $elt ) {
40            $hashes[$elt] = md5( $elt . $separator . $key );
41        }
42        uasort( $array, static function ( $a, $b ) use ( $hashes ) {
43            return strcmp( $hashes[$a], $hashes[$b] );
44        } );
45    }
46
47    /**
48     * Given an array of non-normalised probabilities, this function will select
49     * an element and return the appropriate key
50     *
51     * @param array $weights
52     * @return int|string|false
53     */
54    public static function pickRandom( $weights ) {
55        if ( !is_array( $weights ) || count( $weights ) == 0 ) {
56            return false;
57        }
58
59        $sum = array_sum( $weights );
60        if ( $sum == 0 ) {
61            # No loads on any of them
62            # In previous versions, this triggered an unweighted random selection,
63            # but this feature has been removed as of April 2006 to allow for strict
64            # separation of query groups.
65            return false;
66        }
67        $max = mt_getrandmax();
68        $rand = mt_rand( 0, $max ) / $max * $sum;
69
70        $sum = 0;
71        foreach ( $weights as $i => $w ) {
72            $sum += $w;
73            # Do not return keys if they have 0 weight.
74            # Note that the "all 0 weight" case is handed above
75            if ( $w > 0 && $sum >= $rand ) {
76                break;
77            }
78        }
79
80        return $i;
81    }
82
83    /**
84     * Do a binary search, and return the index of the largest item that sorts
85     * less than or equal to the target value.
86     *
87     * @since 1.23
88     *
89     * @param callable $valueCallback A function to call to get the value with
90     *     a given array index.
91     * @param int $valueCount The number of items accessible via $valueCallback,
92     *     indexed from 0 to $valueCount - 1
93     * @param callable $comparisonCallback A callback to compare two values, returning
94     *     -1, 0 or 1 in the style of strcmp().
95     * @param mixed $target The target value to find.
96     *
97     * @return int|bool The item index of the lower bound, or false if the target value
98     *     sorts before all items.
99     */
100    public static function findLowerBound( $valueCallback, $valueCount,
101        $comparisonCallback, $target
102    ) {
103        if ( $valueCount === 0 ) {
104            return false;
105        }
106
107        $min = 0;
108        $max = $valueCount;
109        do {
110            $mid = $min + ( ( $max - $min ) >> 1 );
111            $item = $valueCallback( $mid );
112            $comparison = $comparisonCallback( $target, $item );
113            if ( $comparison > 0 ) {
114                $min = $mid;
115            } elseif ( $comparison == 0 ) {
116                $min = $mid;
117                break;
118            } else {
119                $max = $mid;
120            }
121        } while ( $min < $max - 1 );
122
123        if ( $min == 0 ) {
124            $item = $valueCallback( $min );
125            $comparison = $comparisonCallback( $target, $item );
126            if ( $comparison < 0 ) {
127                // Before the first item
128                return false;
129            }
130        }
131        return $min;
132    }
133
134    /**
135     * Do array_diff_assoc() on multi-dimensional arrays.
136     *
137     * Note: empty arrays are removed.
138     *
139     * @since 1.23
140     *
141     * @param array $array1 The array to compare from
142     * @param array ...$arrays More arrays to compare against
143     * @return array An array containing all the values from array1
144     *               that are not present in any of the other arrays.
145     */
146    public static function arrayDiffAssocRecursive( $array1, ...$arrays ) {
147        $ret = [];
148
149        foreach ( $array1 as $key => $value ) {
150            if ( is_array( $value ) ) {
151                $args = [ $value ];
152                foreach ( $arrays as $array ) {
153                    if ( isset( $array[$key] ) ) {
154                        $args[] = $array[$key];
155                    }
156                }
157                $valueret = self::arrayDiffAssocRecursive( ...$args );
158                if ( count( $valueret ) ) {
159                    $ret[$key] = $valueret;
160                }
161            } else {
162                foreach ( $arrays as $array ) {
163                    if ( isset( $array[$key] ) && $array[$key] === $value ) {
164                        continue 2;
165                    }
166                }
167                $ret[$key] = $value;
168            }
169        }
170
171        return $ret;
172    }
173
174    /**
175     * Make an array consisting of every combination of the elements of the
176     * input arrays. Each element of the output array is an array with a number
177     * of elements equal to the number of input parameters.
178     *
179     * In mathematical terms, this is an n-ary Cartesian product.
180     *
181     * For example, ArrayUtils::cartesianProduct( [ 1, 2 ], [ 'a', 'b' ] )
182     * produces [ [ 1, 'a' ], [ 1, 'b' ], [ 2, 'a' ], [ 2, 'b' ] ]
183     *
184     * If any of the input arrays is empty, the result is the empty array [].
185     * This is in keeping with the mathematical definition.
186     *
187     * If no parameters are given, the result is also the empty array.
188     *
189     * The array keys are ignored. This implementation uses the internal
190     * pointers of the input arrays to keep track of the current position
191     * without referring to the keys.
192     *
193     * @since 1.35
194     *
195     * @param array ...$inputArrays
196     * @return array
197     */
198    public static function cartesianProduct( ...$inputArrays ) {
199        $numInputs = count( $inputArrays );
200        if ( $numInputs === 0 ) {
201            return [];
202        }
203
204        // Reset the internal pointers
205        foreach ( $inputArrays as &$inputArray ) {
206            if ( !count( $inputArray ) ) {
207                return [];
208            }
209            reset( $inputArray );
210        }
211        unset( $inputArray );
212
213        $outputArrays = [];
214        $done = false;
215        while ( !$done ) {
216            // Construct the output array element
217            $element = [];
218            foreach ( $inputArrays as $inputArray ) {
219                $element[] = current( $inputArray );
220            }
221            $outputArrays[] = $element;
222
223            // Increment the pointers starting from the least significant.
224            // If the least significant rolls over back to the start of the
225            // array, continue with the next most significant, and so on until
226            // that stops happening. If all pointers roll over, we are done.
227            $done = true;
228            for ( $paramIndex = $numInputs - 1; $paramIndex >= 0; $paramIndex-- ) {
229                next( $inputArrays[$paramIndex] );
230                if ( key( $inputArrays[$paramIndex] ) === null ) {
231                    reset( $inputArrays[$paramIndex] );
232                    // continue
233                } else {
234                    $done = false;
235                    break;
236                }
237            }
238        }
239        return $outputArrays;
240    }
241}
242
243/** @deprecated class alias since 1.44 */
244class_alias( ArrayUtils::class, 'ArrayUtils' );