Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
<?php
namespace Kata\Oo;
function chop(int $needle, int ...$haystack) : int
{
try {
$sorted = new SortedIntegers(...$haystack);
return $sorted->positionOf($needle);
} catch (NotFound $e) {
return -1;
} catch (ListEmpty $e) {
return -1;
}
}
class ListEmpty extends \RuntimeException {
}
class NotFound extends \RuntimeException {
}
interface IntegerHaystack
{
public function positionOf(int $needle) : int;
public function isEmpty() : bool;
}
class SortedIntegers implements IntegerHaystack
{
private $integers;
public function __construct(int ...$integers)
{
$this->integers = $integers;
}
public function positionOf(int $needle) : int
{
return $this->range(0, count($this->integers) - 1)->positionOf($needle);
}
public function at($index) : int
{
return $this->integers[$index];
}
public function isEmpty() : bool
{
return empty($this->integers);
}
public function range($from, $to) : SortedIntegersRange
{
return new SortedIntegersRange($this, $from, $to);
}
}
class SortedIntegersRange implements IntegerHaystack
{
private $sortedIntegers;
private $indexFrom;
private $indexTo;
public function __construct(SortedIntegers $sortedIntegers, int $indexFrom, int $indexTo)
{
if ($sortedIntegers->isEmpty()) {
throw new ListEmpty();
}
$this->sortedIntegers = $sortedIntegers;
$this->indexFrom = $indexFrom;
$this->indexTo = $indexTo;
}
public function positionOf(int $needle) : int
{
if ($this->isEmpty()) {
throw new NotFound;
}
if ($this->isSingleElement()) {
return $this->firstElement()->positionOf($needle);
}
switch ($needle <=> $this->valuePivot()) {
case -1:
return $this->firstHalf()->positionOf($needle);
case 0:
return $this->indexPivot();
case 1:
return $this->secondHalf()->positionOf($needle);
}
}
public function isEmpty() : bool
{
return $this->indexFrom > $this->indexTo;
}
private function indexPivot() : int
{
return $this->indexFrom + floor(($this->indexTo - $this->indexFrom) / 2);
}
private function isSingleElement() : bool
{
return $this->indexFrom === $this->indexTo;
}
private function firstElement() : SortedIntegersElement
{
return new SortedIntegersElement($this->sortedIntegers, $this->indexFrom);
}
private function valuePivot() : int
{
return $this->sortedIntegers->at($this->indexPivot());
}
private function firstHalf() : SortedIntegersRange
{
return $this->sortedIntegers->range($this->indexFrom, $this->indexPivot() - 1);
}
private function secondHalf() : SortedIntegersRange
{
return $this->sortedIntegers->range($this->indexPivot() + 1, $this->indexTo);
}
}
class SortedIntegersElement implements IntegerHaystack
{
private $sortedIntegers;
private $index;
public function __construct(SortedIntegers $sortedIntegers, int $index)
{
$this->sortedIntegers = $sortedIntegers;
$this->index = $index;
}
public function positionOf(int $needle) : int
{
if ($this->sortedIntegers->at($this->index) === $needle) {
return $this->index;
}
throw new NotFound;
}
public function isEmpty() : bool
{
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.