2

Есть задача, описать интервал средствами ООП. По сути вопрос не совсем в том как, а вопрос в том - есть ли готовые решения? Программирование существует уже десятки лет и эта задача должна была возникать неоднократно и соответственно должно быть и общее решение которого я по видимому не знаю.

Понятно что интервал определяется 2 точками и множеством точек на числовой прямой между ними. Если у нас есть интервал, то логично что мы можем проверить входит ли некая точка в заданный интервал. И тут возникают проблемы, так как интервалы бывают 4 типов - [a, b], (a, b), [a, b), (a, b].

Так же точка не обязательно должна быть числом. Это может быть дата, время или даже IP. Отсюда возникает куча комбинаций и сложности в конфигурировании. Может есть что-то готовое?

Updated

В моем случае язык PHP, но подойдет и решение на Java или C#. Мне бы общий принцип.

2
  • Хотите готовое - укажите язык программирования Commented 10 нояб. 2016 в 11:46
  • @DmitriySimushev в моем случае PHP, но решение не обязательно давать на нем
    – ghost404
    Commented 10 нояб. 2016 в 11:59

3 ответа 3

6

Давайте начнем с разбираться с вашей проблемой с конца.

Так же точка не обязательно должна быть числом. Это может быть дата, время или даже IP. Отсюда возникает куча комбинаций и сложности в конфигурировании. Может есть что-то готовое?

Во всех языках программирования существуют операции сравнения величин. Это всегда работает для чисел, а вот с другими типами данных могут быть проблемы.

Если вам повезло и ваш язык программирования поддерживает переопределение операций сравнения, то вы можете ввести свой тип данных (например IPAddress) и реализовать для него правильное поведение операторов >, <, == (все прочие операторы сравнения - производные от этих трех).

Если вам не повезло и ваш язык программирования не поддерживает переопределение операторов сравнения, то на помощь придет специальный интерфейс, содержащий необходимые методы в явном виде:

interface IPPointInterface
{
    public function isEqualTo(IPPointInterface $ip): bool;
    public function isGraterThan(IPPointInterface $ip): bool;
    public function isLessThan(IPPointInterface $ip): bool;
}

По аналогии можно ввести интерфейс для любого типа данных.

Понятно что интервал определяется 2 точками и множеством точек на числовой прямой между ними. Если у нас есть интервал, то логично что мы можем проверить входит ли некая точка в заданный интервал.

Вы правильно уловили основную суть интервала - он может проверять входит в него точка или нет. Именно это вы и должны отразить в его интерфейсе. Кроме того, нужно предоставить возможность клиентскому коду получать начальную и конечную точки:

interface IPIntervalInterface {
    public function containsPoint(IPPointInterface $ip): bool;
    public function getStartPoint(IPPointInterface $ip): IPPoint;
    public function getEndPoint(IPPointInterface $ip): IPPoint;
}

Из личного опыта хочу добавить, что в 99% случаев есть еще несколько методов, которые должен поддерживать интерфейс интервала, например, проверка пересечения с другим интервалом.

И тут возникают проблемы, так как интервалы бывают 4 типов - [a, b], (a, b), [a, b), (a, b].

А вот это уже детали реализации. Вы можете либо реализовать четыре класса интервалов либо схитрить и реализовать базовый класс для отрезка (закрытого интервала [a, b]):

class IPClosedInterval implements IPIntervalInterface {
    private $start;
    private $end;

    public function __construct(IPPointInterface $start, IPPointInterface $end) {
        $this->start = $start;
        $this->end = $end;
    }

    public function getStartPoint() {
        return $this->start;
    }

    public function getEndPoint() {
        return $this->end;
    }

    public function containsPoint(IPPointInterface $ip) {
        return $ip->isLessThan($this->getEndPoint())
            && $ip->isGreaterThan($this->getStartEndPoint());
    }
}

И два декоратора "открывающих" границы (приведу код только для "открытия" левой границы):

class IPIntervalLeftOpenDecorator implements IPIntervalInterface {
    private $interval;

    public function __construct(IPIntervalInterface $interval) {
        $this->interval = $interval;
    }

    public function containsPoint(IPPointInterface $ip) {
        return $this->interval->containsPoint($ip)
            || $ip->isEqualTo($this->getStartPoint());
    }

    public function getStartPoint() {
        return $this->interval->getStartPoint();
    }

    public function getEndPoint() {
        return $this->interval->getEndPoint();
    }
}

При желании, конструктор и код, возвращающий границы можно вынести в абстрактный декоратор.

А вот и пример того, как это можно использовать:

$a = new IPPoint('...');
$b = new IPPoint('...');

$closed_int = new IPIntervalClosed($a, $b); // [a, b]
$left_opened_int = new IPIntervalLeftOpenDecorator($closed_int); // (a, b]
$right_opened_int = new IPIntervalRightOpenDecorator($closed_int); // [a, b)
$opened_int = new IPIntervalLeftOpenDecorator($right_opened_int); // (a, b)

Программирование существует уже десятки лет и эта задача должна была возникать неоднократно и соответственно должно быть и общее решение которого я по видимому не знаю.

Это очень сильно зависит от используемого вами языка программирования. Например в C++ вы можете определить базовый тип для точки и параметризовывать класс интервала этим типом.

Что касается PHP, то тут вы тоже можете определить базовый тип для точки (полностью аналогичный моему IPPointInterface за исключением типов у аргументов методов), но тогда вам придется вручную контролировать совпадение сравниваемых типов в методах интервала. Это не так сложно, как кажется, но я все же предпочитаю автоматический контроль типов.

Если все-таки нужен автоматический контроль типов в PHP, то можно реализовать автоматическую генерацию классов интервалов для различных типов точек, но эта тема требует отдельного обсуждения.

По сути вопрос не совсем в том как, а вопрос в том - есть ли готовые решения?

Лично мне попадался только класс, для работы с интервалами дат: league/period. В тоже время, я никогда и не искал какого-то решения для работы с другими типами интервалов.

6
  • здесь не влезает, потому добавил пример своей реализации в основной вопрос
    – ghost404
    Commented 10 нояб. 2016 в 14:27
  • Декораторы не очень подходят так как декораторы нужно создавать на каждый тип интервала что уже избыточно и усложняет конфигурирование интервалов.
    – ghost404
    Commented 10 нояб. 2016 в 14:29
  • @ghost404, честно говоря, я не понял зачем вы изуродовали вопрос, добавив в него ответ. А что касается декораторов - это только один из вариантов решения. Я еще в ответе упомянул, хоть и вскользь, автогенерацию кода интервалов для каждой из точек, возможно этот путь вам поможет Commented 10 нояб. 2016 в 14:52
  • @ghost404 ну и что касается ValueObject - то да, интервалы и точки - хорошие кандидаты для этого. Только вам нужно помнить, что, например, в Doctrine - вы не сможете реализовать наследование для Embeddable классов... Commented 10 нояб. 2016 в 14:54
  • этим мне и не нравится stackoverflow что нельзя написать развернутый комментарий. В результате приходится либо дописывать в вопрос либо писать свой ответ который не является ответом на вопрос
    – ghost404
    Commented 10 нояб. 2016 в 14:57
2

Учёба учёбой, но надо помнить, что в более прикладной реальности много ООП ради ООП легко перерастает в антипаттерн.

Также многое зависит от прикладной задачи. Например, если вам требуется довольно широкий набор операций по, например, пересечению или объединению, если возможно, интервалов, то различные классы для различного вида открытости интервалов, или навороты на базовый класс декораторов могут в итоге только вымучить без полезного выхлопа.

Я бы сделал например так:

    abstract class AbstractValue
    {
        protected $value;

        public function __construct($value)
        {
            $this->value = $value;
        }

        public function __toString()
        {
            return strval($this->value);
        }

        public function getValue()
        {
            return $this->value;
        }

        public function setValue($value)
        {
            $this->value = $value;
            return $this;
        }

        protected function compareCheck(AbstractValue $b)
        {
            $class = get_class($this);
            if (!$b instanceof $class) {
                throw new \Exception("Uncomparable entities: " . get_class($b) . " vs " . get_class($this));
            }
        }

        final public function compareWith(AbstractValue $b)
        {
            $this->compareCheck($b);
            return $this->doCompareWith($b);
        }

        protected function doCompareWith(AbstractValue $b)
        {
            $diff = $this->value - $b->getValue();
            return (int)$diff;
        }

        final public function isEqualTo(AbstractValue $b)
        {
            $this->compareCheck($b);
            return $this->doIsEqualTo($b);
        }

        protected function doIsEqualTo(AbstractValue $b)
        {
            return $this->value == $b->getValue();
        }

        final public function isGreaterThan(AbstractValue $b)
        {
            $this->compareCheck($b);
            return $this->doIsGreaterThan($b);
        }

        protected function doIsGreaterThan(AbstractValue $b)
        {
            return $this->value > $b->getValue();
        }

        final public function isLessThan(AbstractValue $b)
        {
            $this->compareCheck($b);
            return $this->doIsLessThan($b);
        }

        protected function doIsLessThan(AbstractValue $b)
        {
            return $this->value < $b->getValue();
        }

    }

    class Interval
    {
        const TYPE_CLOSED = 0;
        const TYPE_START_EXCLUDED = 1;
        const TYPE_END_EXCLUDED = 2;
        const TYPE_OPEN = 3; // = TYPE_START_EXCLUDED | TYPE_END_EXCLUDED

        private $start;
        private $end;
        private $type;
        private $isStartExcluded = false;
        private $isEndExcluded = false;

        public function __construct(AbstractValue $start, AbstractValue $end, $type = self::TYPE_CLOSED)
        {
            // We already sure that "start" & "end" is like same type and comparable
            if ($start->isLessThan($end)) {
                $this->start = $start;
                $this->end = $end; 
            } else {
                $this->start = $end;
                $this->end = $start; 
            }
            $this->type = $type; // We can add a filter for bad values here
            $this->isStartExcluded = (bool) ($type & self::TYPE_START_EXCLUDED);
            $this->isEndExcluded = (bool) ($type & self::TYPE_END_EXCLUDED);
        }

        public function __toString()
        {
            return ($this->isStartExcluded ? '(' : '[')
                . $this->start . ', ' . $this->end
                . ($this->isEndExcluded ? ')' : ']');
        }

        public function getStart()
        {
            return $this->start;
        }

        public function setStart($start)
        {
            if ($start->isLessThan($this->end)) {
                $this->start = $start;
            } else {
                $this->start = $this->end;
                $this->end = $start; 
            }
            return $this;
        }

        public function getEnd()
        {
            return $this->end;
        }

        public function setEnd($end)
        {
            if ($this->start->isLessThan($end)) {
                $this->end = $end; 
            } else {
                $this->end = $this->start; 
                $this->start = $end;
            }
            return $this;
        }

        public function getType()
        {
            return $this->type;
        }

        public function setType($type)
        {
            $this->type = $type; // We can add a filter for bad values here
            $this->isStartExcluded = (bool) ($type & self::TYPE_START_EXCLUDED);
            $this->isEndExcluded = (bool) ($type & self::TYPE_END_EXCLUDED);
            return $this;
        }

        public function getIsStartExcluded()
        {
            return $this->isStartExcluded;
        }

        public function setIsStartExcluded($value)
        {
            $value = (bool) $value;
            $this->isStartExcluded = $value;
            $this->type = $value ? ($type | TYPE_START_EXCLUDED) : ($type & ~TYPE_START_EXCLUDED);
            return $this;
        }

        public function getIsEndExcluded()
        {
            return $this->isEndExcluded;
        }

        public function setIsEndExcluded($value)
        {
            $value = (bool) $value;
            $this->isEndExcluded = $value;
            $this->type = $value ? ($type | TYPE_END_EXCLUDED) : ($type & ~TYPE_END_EXCLUDED);
            return $this;
        }

        public function contains(AbstractValue $point)
        {
            $cmpStart = $point->compareWith($this->start);
            if ($cmpStart < 0) return false;
            $cmpEnd = $point->compareWith($this->end);
            if ($cmpEnd > 0) return false;
            if ($this->isStartExcluded && $cmpStart == 0) return false;
            if ($this->isEndExcluded && $cmpEnd == 0) return false;
            return true;
        }

        public function intersect(Interval $second)
        {
            $cmp_start2_start1 = $second->getStart()->compareWith($this->start);
            $cmp_end2_end1 = $second->getEnd()->compareWith($this->end);

            if ($cmp_start2_start1 > 0) {
                $start = $second->getStart();
                $isStartExcluded = $second->getIsStartExcluded();
            } else {
                $start = $this->start;
                $isStartExcluded = $cmp_start2_start1 < 0 ? $this->isStartExcluded : 
                    $this->isStartExcluded || $second->getIsStartExcluded();
            }
            if ($cmp_end2_end1 < 0) {
                $end = $second->getEnd();
                $isEndExcluded = $second->getIsEndExcluded();
            } else {
                $end = $this->end;
                $isEndExcluded = $cmp_end2_end1 > 0 ? $this->isEndExcluded : 
                    $this->isEndExcluded || $second->getIsEndExcluded();
            }
            $type = $isStartExcluded ? Interval::TYPE_START_EXCLUDED : 0;
            $type |= ($isEndExcluded ? Interval::TYPE_END_EXCLUDED : 0);

            $cmp_start_end = $start->compareWith($end);

            // single point real interval
            if ($cmp_start_end == 0 && $type == Interval::TYPE_CLOSED) {
                return new Interval($start, $start, Interval::TYPE_CLOSED);
            }
            // null-interval (any) of current type
            if ($cmp_start_end >= 0) {
                return new Interval($start, $start, Interval::TYPE_OPEN);
            }

            return new Interval($start, $end, $type);
        }
    }


    class MathNumber extends AbstractValue
    {
    }

    class DateTimePoint extends AbstractValue
    {
        public function __construct(\DateTime $value)
        {
            parent::__construct($value);
        }

        public function __toString()
        {
            return $this->value->format('Y-m-d H:i:s');
        }

        public function setValue(\DateTime $value)
        {
            return parent::setValue($value);
        }

        public function doCompareWith(DateTimePoint $b)
        {
            if ($this->getValue() > $b->getValue()) {
                return 1;
            }
            if ($this->getValue() < $b->getValue()) {
                return -1;
            }
            return 0;
        }
    }

Всё вполне себе симпатично работает вот так:

Числа:

    echo "<pre>";

    $n1 = new MathNumber(10);
    $n2 = new MathNumber(2.5);
    $a = new Interval($n1, $n2);
    $a = new Interval($n1, $n2, Interval::TYPE_START_EXCLUDED);

    $n3 = new MathNumber(20);
    $a->setEnd($n3)->setIsEndExcluded(true);

    echo "Value " . $n2 . " is " . ($a->contains($n2) ? "" : "NOT ") . "in " . $a . "\n";
    echo "Value " . $n1 . " is " . ($a->contains($n1) ? "" : "NOT ") . "in " . $a . "\n";

    echo "\n";

Value 2.5 is NOT in (2.5, 20)

Value 10 is in (2.5, 20)

А ещё прикольно отрезки пересекать:

    $n4 = new MathNumber(12);
    $n5 = new MathNumber(55);
    $a2 = new Interval($n4, $n5);

    $a3 = $a->intersect($a2);

    echo "Value " . $n3 . " is " . ($a2->contains($n3) ? "" : "NOT ") . "in " . $a2 . "\n";
    echo "Value " . $n3 . " is " . ($a3->contains($n3) ? "" : "NOT ") . "in " . $a3 . " - intersect \n";

    echo "\n";

Value 20 is in [12, 55]

Value 20 is NOT in [12, 20) - intersect

Даты:

    $dt1 = new DateTimePoint(new \DateTime());
    $dt2 = new DateTimePoint(new \DateTime('+30 days'));
    $dt3 = new DateTimePoint(new \DateTime('+5 days'));
    $b = new Interval($dt1, $dt2, Interval::TYPE_OPEN);
    echo "Value " . $dt1 . " is " . ($b->contains($dt1) ? "" : "NOT ") . "in " . $b . "\n";
    echo "Value " . $dt3 . " is " . ($b->contains($dt3) ? "" : "NOT ") . "in " . $b . "\n";

    echo "\n";

Value 2016-11-11 03:26:13 is NOT in (2016-11-11 03:26:13, 2016-12-11 03:26:13)

Value 2016-11-16 03:26:13 is in (2016-11-11 03:26:13, 2016-12-11 03:26:13)

Пробуем слепить интервал из числа и даты - получаем как и задумано по щам эксцепшном:

    $c = new Interval($n1, $dt2);
    echo "Value " . $dt1 . " is " . ($c->contains($dt1) ? "" : "NOT ") . "in " . $c . "\n";

Uncomparable entities: DateTimePoint vs MathNumber

Можно заморочиться с абстрактными Интервалами, интерфейсами, трейтами, чего только. Но зачем?

Ну а если у вас никакого общего подхода в прикладной задаче не требуется и не будет, и, например, всё именно как в изначальной постановке задачи: математические отрезки, - только double и ничто больше, а считать надо будет много и быстро.. Пишите код. Быстрый код. Не ленитесь. Половина ООП хлама для такой конкретной цели не то что не нужна, но вредна. Но ООП вообще полезная штука во многих случаях.

Успехов!

1
  • Да, конечно для интервалов обязательно нужны будут, например: метод получения длины этого интервала. Для [10, 51) это будет 41, для дат надо полагать должно возвращать
    – FlameStorm
    Commented 11 нояб. 2016 в 0:52
0

Тип интервала я вынес в ValueObject и операцию проверки делал через нее. Получился такой интерфейс:

interface IntervalTypeInterface
{
    public function intervalContains(IntervalInterface $interval, $point);
}

Сам интервал имеет интерфейс:

interface IntervalInterface
{
    public function contains($point);
    public function start();
    public function end();
}

Интересная идея делать через декараторы, но это не подходит так как интервал должен сам знать свой тип (закрытый/открытый) и код который будет работать с этим интервалом ожидает конкретный тип интервала. Тоесть пользовательский код будет ожидать DateTimeInterval и попытка передать ему IPInterval должна привести к ошибке. А если мы будем создавать конкретные декараторы типа IPClosedInterval, то такие декараторы нужно создавать на каждый тип интервала что уже избыточно и усложняет кофигурирование интервалов.

Вот пример реализации интервала дат:

class DateTimeInterval implements IntervalInterface
{
    private $type;
    private $start;
    private $end;

    public function __construct(IntervalTypeInterface $type, \DateTime $start, \DateTime $end)
    {
        // это должен быть корректный интервал
        if ($start >= $end) {
            throw IncorrectIntervalException::create();
        }

        $this->type = $type;
        $this->start = clone $start;
        $this->end = clone $end;
    }

    public function contains($point)
    {
        // здесь я вынужден проверять тип данных точки
        // ожидается \DateTime, но может прийти все что угодно
        $this->checkPointType($point);

        return $this->type->intervalContains($this, $point);
    }

    // ...
}

Вот тут собственно и была проблема. Я вынужден явно проверять тип данных точки. PHP не дает возможности переопределять тип параметра в наследуемом классе. Тоесть я вынужден отказаться от использования IntervalInterface и соответсвенно возникают проблемы в использовании интерфейса IntervalTypeInterface.

Была и другая идея. Как раз обернуть значение точки интервала в класс и все операции сравнения перелажить на нее. Точкам лучше известно как их сравнивать. Тот же IP это строка и для сравнения в PHP есть функция которая в этом поможет.

Но у нас возникает проблема связанная с тем что каждую точку нужно оборачивать для того что бы использовать в интервале. Для IP это единственно возможный вариант, а для чисел и дат (PHP позволяет выполнять операции сравнение для объектов даты) в этом нет необходимости. Тогда можно оборачивать в объект точку только IP, но тогда мы получаем расхождение в стилистике.

И это не решает проблемы с типом интервала. Типов интервала всего 4. Не больше и не меньше. Они выполняют одинаковые действия сравнения для всех типов точек. В этом случае логично сделать общий интерфейс для точек:

interface PointInterface
{
    public function isEqualTo(PointInterface $point): bool;
    public function isGreaterThan(PointInterface $point): bool;
    public function isLessThan(PointInterface $point): bool;
}

Тип будет иметь интерфейс:

interface IntervalTypeInterface
{
    public function intervalContains(IntervalInterface $interval, PointInterface $point);
}

Ну и пример реализации открытого интервала

class OpenInterval implements IntervalTypeInterface
{
    public function intervalContains(IntervalInterface $interval, PointInterface $point)
    {
        return $interval->start()->isLessThan($point) && $interval->end()->isGreaterThan($point);
    }
}

Вроде уже лучше, но PHP не позволяет переопределять тип параметров методов, тоесть нельзя сделать так:

interface IPPointInterface extends PointInterface
{
    public function isEqualTo(IPPointInterface $ip): bool;
    public function isGreaterThan(IPPointInterface $ip): bool;
    public function isLessThan(IPPointInterface $ip): bool;
}

И получается внутри точки мы будем вынуждены явно проверять тип данных что не очень хорошо. И получается единственный вариант который я пока вижу это использование switch/case в интервале:

class IPInterval
{
    private $type;
    private $start;
    private $end;

    const TYPE_CLOSED = 'closed';
    const TYPE_OPEN = 'open';
    const TYPE_HALF_CLOSED = 'half-closed';
    const TYPE_HALF_OPEN = 'half-open';

    public function __construct(IPPointInterface $start, IPPointInterface $end, $type = self::TYPE_CLOSED)
    {
        // проверка допустимости типа интервала
        if (!in_array($type, self::types())) {
            throw IncorrectIntervalTypeException::create();
        }

        // это должен быть корректный интервал
        if ($start->isEqualTo($end) || $start->isGreaterThan($end)) {
            throw IncorrectIntervalException::create();
        }

        $this->type = $type;
        $this->start = $start;
        $this->end = $end;
    }

    public start function types() // можно вынести в базовый класс
    {
        return [
            self::TYPE_CLOSED,
            self::TYPE_OPEN,
            self::TYPE_HALF_CLOSED,
            self::TYPE_HALF_OPEN,
        ];
    }

    public function contains(IPPointInterface $point)
    {
        // этот код дублируется для всех типов интервалов если мы будем оборачивать точки в классы
        // если будем оборачивать только IP то дублироваться будет в интервалах дат, времени и числовых интервалах
        switch ($this->type) {
            case self::TYPE_OPEN:
                return $this->start->isLessThan($point) && $this->end->isGreaterThan($point);
            // дальше по аналогии
        }
    }
}

Вроде рабочий вариант, но какой-то корявый.

Можно сделать общий ValueObject типа интервала для каждого типа интервала:

class IPIntervalType
{
    const TYPE_CLOSED = 'closed';
    const TYPE_OPEN = 'open';
    const TYPE_HALF_CLOSED = 'half-closed';
    const TYPE_HALF_OPEN = 'half-open';

    private function __construct($type)
    {
        // тип можно не проверять так как тип определяется только через фабричные методы
        $this->type = $type;
    }

    // фабричный метод
    public static function closed()
    {
        return new self(self::TYPE_CLOSED);
    }

    // другие фабричные методы
    // ..

    // все что выше можно вынести в базовый класс

    public function intervalContains(IPIntervalInterface $interval, IPPointInterface $point)
    {
        return $interval->start()->isLessThan($point) && $interval->end()->isGreaterThan($point);
    }
}

тогда в интервале получаем упрощение

class IPInterval
{
    // ..
    public function contains(IPPointInterface $point)
    {
        return $this->type->intervalContains($this, $point);
    }
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.