-
-
Save schmengler/de59fc7ef928181ac260876a5b812c8d to your computer and use it in GitHub Desktop.
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 | |
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