Last active
December 26, 2016 16:10
-
-
Save mcordingley/019a407a81a57e16a3e1ad23205c0df6 to your computer and use it in GitHub Desktop.
median
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| /** | |
| * @param array $items | |
| * @param callable|int|string|null $callback | |
| * @return mixed | |
| */ | |
| public static function median($items, $callback = null) | |
| { | |
| return static::nthOrder($items, (int) ((count($items) - 1) / 2), $callback); | |
| } | |
| /** | |
| * Returns the element with the requested zero-based nth order statistic from the passed array. | |
| * | |
| * @param array $items | |
| * @param int $n | |
| * @param callable|int|string|null $callback | |
| * @return mixed | |
| */ | |
| public static function nthOrder($items, $n, $callback = null) | |
| { | |
| $count = count($items); | |
| if ($n < 0 || $n >= $count) { | |
| return null; | |
| } | |
| $values = array_values($items); | |
| return static::select($values, 0, $count - 1, $n, $callback); | |
| } | |
| /** | |
| * @param array $items | |
| * @param int $start | |
| * @param int $end | |
| * @param int $nthOrder | |
| * @param callable|int|string|null $callback | |
| * @return mixed | |
| */ | |
| private static function select(&$items, $start, $end, $nthOrder, $callback = null) | |
| { | |
| if ($start === $end) { | |
| return $items[$start]; | |
| } | |
| $pivot = static::partition($items, $start, $end, random_int($start, $end), $callback); | |
| if ($nthOrder === $pivot) { | |
| return $items[$pivot]; | |
| } | |
| if ($nthOrder < $pivot) { | |
| return static::select($items, $start, $pivot - 1, $nthOrder, $callback); | |
| } | |
| return static::select($items, $pivot + 1, $end, $nthOrder, $callback); | |
| } | |
| /** | |
| * Rearranges a subarray in place, so that the element index described by the index `$reference` is in its sorted | |
| * position in the subarray, all elements less than that element are in lower positions, and all elements greater | |
| * than that element are in higher positions. Returns the new index of this element. | |
| * | |
| * @param array $items Array to be rearranged, with sequential integer indexes starting at zero. | |
| * @param int $start Starting index of the subarray to rearrange. | |
| * @param int $end Ending index of the subarray to rearrange. | |
| * @param int $reference Index of the reference element | |
| * @param callable|int|string|null $callback | |
| * @return int | |
| */ | |
| private static function partition(&$items, $start, $end, $reference, $callback = null) | |
| { | |
| list($items[$end], $items[$reference]) = [$items[$reference], $items[$end]]; | |
| $pivot = $items[$end]; | |
| $lower = $start; | |
| for ($i = $start; $i < $end; $i++) { | |
| if (is_string($callback)) { | |
| $comparisonValue = array_get($items[$i], $callback); | |
| $pivotValue = array_get($pivot, $callback); | |
| } elseif (is_int($callback)) { | |
| $comparisonValue = $items[$i][$callback]; | |
| $pivotValue = $pivot[$callback]; | |
| } elseif (is_callable($callback)) { | |
| $comparisonValue = $callback($items[$i], $pivot); | |
| $pivotValue = 0; | |
| } else { | |
| $comparisonValue = $items[$i]; | |
| $pivotValue = $pivot; | |
| } | |
| if ($comparisonValue < $pivotValue) { | |
| list($items[$lower], $items[$i]) = [$items[$i], $items[$lower]]; | |
| $lower++; | |
| } | |
| } | |
| list($items[$lower], $items[$end]) = [$items[$end], $items[$lower]]; | |
| return $lower; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| public function testMedian() | |
| { | |
| $array = range(1, 3); | |
| shuffle($array); | |
| static::assertEquals(2, Arr::median($array)); | |
| $array = range(1, 4); | |
| shuffle($array); | |
| static::assertEquals(2, Arr::median($array)); | |
| } | |
| public function testMedianOfStrings() | |
| { | |
| $array = [ | |
| '1996-01-06 14:39:17', | |
| '1983-05-14 07:51:14', | |
| '1983-05-14 07:52:43', | |
| ]; | |
| static::assertEquals('1983-05-14 07:52:43', Arr::median($array)); | |
| } | |
| public function testNthOrderSimple() | |
| { | |
| $array = range(1, 20); | |
| shuffle($array); | |
| static::assertEquals(1, Arr::nthOrder($array, 0)); | |
| static::assertEquals(5, Arr::nthOrder($array, 4)); | |
| static::assertEquals(10, Arr::nthOrder($array, 9)); | |
| } | |
| public function testNthOrderIntegerCallback() | |
| { | |
| $array = [ | |
| [1], | |
| [8], | |
| [7], | |
| [2], | |
| ]; | |
| static::assertEquals([2], Arr::nthOrder($array, 1, 0)); | |
| } | |
| public function testNthOrderStringCallback() | |
| { | |
| $array = [ | |
| ['foo' => 1], | |
| ['foo' => 8], | |
| ['foo' => 7], | |
| ['foo' => 2], | |
| ]; | |
| static::assertEquals(['foo' => 2], Arr::nthOrder($array, 1, 'foo')); | |
| } | |
| public function testNthOrderCallableCallback() | |
| { | |
| $array = [ | |
| ['foo' => 1], | |
| ['foo' => 8], | |
| ['foo' => 7], | |
| ['foo' => 2], | |
| ]; | |
| static::assertEquals(['foo' => 2], Arr::nthOrder($array, 1, function ($a, $b) { | |
| return $a['foo'] - $b['foo']; | |
| })); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment