Online PHP editor | output for EFHJQ

<?php declare(strict_types=1); /** * Value Object Segment — неизменяемый сегмент с флагами принадлежности. * * @property-read int $start * @property-read int $end * @property-read array $flags */ final class Segment { /** @var int */ private $start; /** @var int */ private $end; /** @var string[] */ private $flags; /** * @param int $start Начало интервала (включительно) * @param int $end Конец интервала (включительно) * @param string[] $flags Флаги принадлежности (только 'A' и/или 'B') * * @throws InvalidArgumentException если start > end или переданы недопустимые флаги */ public function __construct(int $start, int $end, array $flags) { if ($start > $end) { throw new \InvalidArgumentException( \sprintf('Начало сегмента (%d) не может быть больше конца (%d)', $start, $end) ); } $allowedFlags = ['A', 'B']; $normalizedFlags = []; foreach ($flags as $flag) { if (!\is_string($flag) || !\in_array($flag, $allowedFlags, true)) { throw new \InvalidArgumentException( \sprintf('Недопустимый флаг "%s". Разрешены только "A" и "B"', \is_scalar($flag) ? $flag : \gettype($flag)) ); } $normalizedFlags[] = $flag; } if (empty($normalizedFlags)) { throw new \InvalidArgumentException('Сегмент должен иметь хотя бы один флаг'); } // Упорядочиваем флаги для консистентности сравнения \sort($normalizedFlags); $this->flags = $normalizedFlags; $this->start = $start; $this->end = $end; } public function getStart(): int { return $this->start; } public function getEnd(): int { return $this->end; } /** * @return string[] Флаги (отсортированные) */ public function getFlags(): array { return $this->flags; } /** * Длина сегмента (количество целых точек) = end - start + 1 */ public function getLength(): int { return $this->end - $this->start + 1; } public function hasFlag(string $flag): bool { return \in_array($flag, $this->flags, true); } public function __toString(): string { return \sprintf('Segment(%d, %d, [%s])', $this->start, $this->end, \implode(',', $this->flags)); } } /** * Интерфейс алгоритма наложения интервалов. */ interface OverlapAlgorithmInterface { /** * Обрабатывает два набора интервалов и возвращает массив сегментов Segment[]. * * @param int[][] $intervalsA Массив интервалов A, каждый элемент — [start, end] * @param int[][] $intervalsB Массив интервалов B * @return Segment[] */ public function process(array $intervalsA, array $intervalsB): array; } /** * Стандартная реализация алгоритма наложения с дублированием границ. * * Логика: * 1. При $normalize=true каждый входной массив предварительно объединяет * пересекающиеся и соприкасающиеся интервалы. * 2. Из каждого интервала A вычитаются все интервалы B → чистые куски A. * 3. Из каждого интервала B вычитаются все интервалы A → чистые куски B. * 4. Находятся все попарные пересечения A∩B. * 5. Все куски собираются в Segment[], дубликаты удаляются, результат сортируется. */ final class DefaultOverlapAlgorithm implements OverlapAlgorithmInterface { /** @var bool */ private $normalize; /** * @param bool $normalize Нужно ли предварительно объединять пересекающиеся/касающиеся интервалы */ public function __construct(bool $normalize = true) { $this->normalize = $normalize; } /** * {@inheritdoc} */ public function process(array $intervalsA, array $intervalsB): array { $A = $intervalsA; $B = $intervalsB; if ($this->normalize) { $A = $this->normalizeIntervals($A); $B = $this->normalizeIntervals($B); } $cleanA = []; foreach ($A as $aInterval) { foreach ($this->subtractIntervals($aInterval, $B) as $piece) { $cleanA[] = $piece; } } $cleanB = []; foreach ($B as $bInterval) { foreach ($this->subtractIntervals($bInterval, $A) as $piece) { $cleanB[] = $piece; } } $intersections = $this->intersectIntervals($A, $B); // Собираем сегменты $segments = []; foreach ($cleanA as $int) { $segments[] = new Segment($int[0], $int[1], ['A']); } foreach ($cleanB as $int) { $segments[] = new Segment($int[0], $int[1], ['B']); } foreach ($intersections as $int) { $segments[] = new Segment($int[0], $int[1], ['A', 'B']); } // Удаление дубликатов (одинаковые начало, конец и флаги) $unique = []; foreach ($segments as $seg) { $key = $seg->getStart() . '_' . $seg->getEnd() . '_' . \implode(',', $seg->getFlags()); if (!isset($unique[$key])) { $unique[$key] = $seg; } } $segments = \array_values($unique); // Сортировка: сначала по start, затем по end, затем по флагам \usort($segments, static function (Segment $a, Segment $b): int { if ($a->getStart() !== $b->getStart()) { return $a->getStart() - $b->getStart(); } if ($a->getEnd() !== $b->getEnd()) { return $a->getEnd() - $b->getEnd(); } return \strcmp(\implode(',', $a->getFlags()), \implode(',', $b->getFlags())); }); return $segments; } /** * Нормализация: сортировка по start и объединение пересекающихся/касающихся интервалов. * * @param int[][] $intervals * @return int[][] */ private function normalizeIntervals(array $intervals): array { if (empty($intervals)) { return []; } // Сортировка по началу \usort($intervals, static function (array $a, array $b): int { return $a[0] - $b[0]; }); $merged = []; foreach ($intervals as $int) { if (empty($merged)) { $merged[] = $int; continue; } $last = &$merged[\count($merged) - 1]; // Касающиеся считаются объединяемыми: [10,20] и [21,30] -> [10,30] if ($int[0] <= $last[1] + 1) { if ($int[1] > $last[1]) { $last[1] = $int[1]; } } else { $merged[] = $int; } } return $merged; } /** * Вычитание набора интервалов из одного интервала. * Возвращает части $interval, не попавшие ни в один из $subtrahends, * с дублированием граничных точек. * * @param int[] $interval [start, end] * @param int[][] $subtrahends Массив вычитаемых интервалов (отсортированных, без пересечений) * @return int[][] Массив интервалов [start, end] */ private function subtractIntervals(array $interval, array $subtrahends): array { $pieces = [$interval]; foreach ($subtrahends as $sub) { $newPieces = []; foreach ($pieces as $piece) { $overlapStart = \max($piece[0], $sub[0]); $overlapEnd = \min($piece[1], $sub[1]); if ($overlapStart <= $overlapEnd) { // Есть пересечение – отрезаем левую и правую части if ($piece[0] < $overlapStart) { $newPieces[] = [$piece[0], $overlapStart]; } if ($overlapEnd < $piece[1]) { $newPieces[] = [$overlapEnd, $piece[1]]; } // Полное поглощение куска – ничего не добавляем } else { // Пересечения нет, кусок остаётся как есть $newPieces[] = $piece; } } $pieces = $newPieces; } return $pieces; } /** * Попарные пересечения двух массивов интервалов. * * @param int[][] $A * @param int[][] $B * @return int[][] */ private function intersectIntervals(array $A, array $B): array { $result = []; foreach ($A as $a) { foreach ($B as $b) { $start = \max($a[0], $b[0]); $end = \min($a[1], $b[1]); if ($start <= $end) { $result[] = [$start, $end]; } } } return $result; } } /** * Менеджер для вычисления и предоставления результатов наложения интервалов. */ final class IntervalOverlapManager { /** @var OverlapAlgorithmInterface */ private $algorithm; /** @var Segment[] */ private $segments = []; /** @var int[][] Оригинальный набор A */ private $originalA = []; /** @var int[][] Оригинальный набор B */ private $originalB = []; /** * @param OverlapAlgorithmInterface|null $algorithm Алгоритм (если null – стандартный с нормализацией) */ public function __construct(?OverlapAlgorithmInterface $algorithm = null) { $this->algorithm = $algorithm ?? new DefaultOverlapAlgorithm(); } /** * Запуск вычислений. * * @param int[][] $intervalsA * @param int[][] $intervalsB * @return self */ public function calculate(array $intervalsA, array $intervalsB): self { $this->originalA = $intervalsA; $this->originalB = $intervalsB; $this->segments = $this->algorithm->process($intervalsA, $intervalsB); return $this; } /** * @return Segment[] Все сегменты разбиения */ public function getSegments(): array { return $this->segments; } /** * @return Segment[] Сегменты пересечения (флаги ['A','B']) */ public function getIntersections(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['A', 'B']; })); } /** * @return Segment[] Сегменты только A (флаг ['A']) */ public function getUniqueA(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['A']; })); } /** * @return Segment[] Сегменты только B (флаг ['B']) */ public function getUniqueB(): array { return \array_values(\array_filter($this->segments, static function (Segment $s): bool { return $s->getFlags() === ['B']; })); } /** * «Дыры» — промежутки между объединением всех исходных интервалов. * Объединение строится с той же логикой, что и нормализация. * * @return int[][] Массив [start, end] */ public function getHoles(): array { $all = \array_merge($this->originalA, $this->originalB); $united = $this->normalizeIntervals($all); $holes = []; for ($i = 0, $c = \count($united) - 1; $i < $c; ++$i) { $gapStart = $united[$i][1] + 1; $gapEnd = $united[$i + 1][0] - 1; if ($gapStart <= $gapEnd) { $holes[] = [$gapStart, $gapEnd]; } } return $holes; } /** * Количество сегментов (с учётом дублирующихся границ). */ public function count(): int { return \count($this->segments); } /** * Сумма длин всех сегментов. Из-за дублирования границ может превышать реальную длину покрытия. */ public function totalDuration(): int { $sum = 0; foreach ($this->segments as $seg) { $sum += $seg->getLength(); } return $sum; } /** * Объединение всех покрытых чисел (без повторов, одна нормализованная картина). * * @return int[][] */ public function getUnion(): array { $all = \array_merge($this->originalA, $this->originalB); return $this->normalizeIntervals($all); } /** * Вспомогательный метод нормализации (аналогичен используемому в алгоритме). * * @param int[][] $intervals * @return int[][] */ private function normalizeIntervals(array $intervals): array { if (empty($intervals)) { return []; } \usort($intervals, static function (array $a, array $b): int { return $a[0] - $b[0]; }); $merged = []; foreach ($intervals as $int) { if (empty($merged)) { $merged[] = $int; continue; } $last = &$merged[\count($merged) - 1]; if ($int[0] <= $last[1] + 1) { if ($int[1] > $last[1]) { $last[1] = $int[1]; } } else { $merged[] = $int; } } return $merged; } } // ------------------------------------------------------- // Пример использования и проверка // ------------------------------------------------------- $manager = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager->calculate( [[10, 30]], // A [[20, 40]] // B ); $segments = $manager->getSegments(); // Ожидаемый порядок (по start): // Segment(10, 20, ['A']) // Segment(20, 30, ['A','B']) // Segment(30, 40, ['B']) echo "Сегменты:\n"; foreach ($segments as $seg) { echo $seg . "\n"; } echo "\nПересечения (AB):\n"; foreach ($manager->getIntersections() as $seg) { echo $seg . "\n"; } echo "\nУникальные A:\n"; foreach ($manager->getUniqueA() as $seg) { echo $seg . "\n"; } echo "\nУникальные B:\n"; foreach ($manager->getUniqueB() as $seg) { echo $seg . "\n"; } echo "\nОбщая сумма длин сегментов (totalDuration): " . $manager->totalDuration() . "\n"; echo "Количество сегментов: " . $manager->count() . "\n"; // Проверка дыр $manager2 = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager2->calculate( [[10, 15]], // A [[20, 25]] // B ); echo "\nДыры (A [10,15], B [20,25]):\n"; foreach ($manager2->getHoles() as $hole) { echo '[' . $hole[0] . ', ' . $hole[1] . "]\n"; } // Проверка с нормализацией A: [[10,20],[15,30]] -> [10,30] $manager3 = new IntervalOverlapManager(new DefaultOverlapAlgorithm(true)); $manager3->calculate( [[10, 20], [15, 30]], [[20, 40]] ); echo "\nС нормализацией (A: [10,20],[15,30]; B: [20,40]):\n"; foreach ($manager3->getSegments() as $seg) { echo $seg . "\n"; } // Union проверка echo "\nОбъединение покрытия (Union):\n"; foreach ($manager3->getUnion() as $int) { echo '[' . $int[0] . ', ' . $int[1] . "]\n"; }