kata-karate-chop-oo.php

<?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;
    }
    
}