|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
declare(strict_types=1); |
|
4
|
|
|
|
|
5
|
|
|
namespace PhpSpellcheck\Utils; |
|
6
|
|
|
|
|
7
|
|
|
use PhpSpellcheck\Exception\InvalidArgumentException; |
|
8
|
|
|
use Webmozart\Assert\Assert; |
|
9
|
|
|
|
|
10
|
|
|
/** |
|
11
|
|
|
* @see https://github.com/cheeaun/kohana-core/blob/master/classes/kohana/arr.php#L151 |
|
12
|
|
|
*/ |
|
13
|
|
|
class SortedNumericArrayNearestValueFinder |
|
14
|
|
|
{ |
|
15
|
|
|
|
|
16
|
|
|
public const FIND_LOWER = -1; |
|
17
|
|
|
public const FIND_DEFAULT = 0; |
|
18
|
|
|
public const FIND_HIGHER = 1; |
|
19
|
3 |
|
|
|
20
|
|
|
public static function findIndex(int $needle, array $haystack, int $mode = self::FIND_DEFAULT): int |
|
21
|
3 |
|
{ |
|
22
|
3 |
|
Assert::notEmpty($haystack); |
|
23
|
|
|
$high = count($haystack); |
|
24
|
3 |
|
$low = 0; |
|
25
|
3 |
|
|
|
26
|
3 |
|
while ($high - $low > 1) { |
|
27
|
3 |
|
$probe = ($high + $low) / 2; |
|
28
|
|
|
|
|
29
|
3 |
|
Assert::integerish($haystack[$probe]); |
|
30
|
|
|
if ($haystack[$probe] < $needle) { |
|
31
|
|
|
$low = $probe; |
|
32
|
3 |
|
} else { |
|
33
|
3 |
|
$high = $probe; |
|
34
|
3 |
|
} |
|
35
|
|
|
} |
|
36
|
|
|
if ($high === count($haystack) or $haystack[$high] !== $needle) { |
|
37
|
3 |
|
if ($high === count($haystack)) { |
|
38
|
3 |
|
Assert::integerish($haystack[$high - 1]); |
|
39
|
3 |
|
|
|
40
|
3 |
|
return $high - 1; |
|
41
|
|
|
} |
|
42
|
3 |
|
|
|
43
|
1 |
|
$ceil_low = (int) ceil($low); |
|
44
|
|
|
$floor_low = (int) floor($low); |
|
45
|
|
|
$high_distance = $haystack[$ceil_low] - $needle; |
|
46
|
3 |
|
$low_distance = $needle - $haystack[$floor_low]; |
|
47
|
3 |
|
|
|
48
|
|
|
if ($mode === self::FIND_LOWER) { |
|
49
|
|
|
return $floor_low; |
|
50
|
1 |
|
} |
|
51
|
1 |
|
|
|
52
|
|
|
if ($mode === self::FIND_HIGHER) { |
|
53
|
|
|
return $ceil_low; |
|
54
|
|
|
} |
|
55
|
|
|
|
|
56
|
|
|
if ($mode === self::FIND_DEFAULT) { |
|
57
|
1 |
|
return ($high_distance >= $low_distance) ? $ceil_low : $floor_low; |
|
58
|
|
|
} |
|
59
|
|
|
|
|
60
|
|
|
throw new InvalidArgumentException('Finding mode value "' . $mode . '" is not supported'); |
|
61
|
|
|
} |
|
62
|
|
|
|
|
63
|
|
|
return (int) $high; |
|
64
|
|
|
} |
|
65
|
|
|
} |
|
66
|
|
|
|
tigitz /
php-spellchecker
