Functional.php

<?php

// ...

function window(array $array, int $width): array {
    $results = [];

    $count = count($array);
    if ($count < $width) {
        throw new InvalidArgumentException('Not enough items in array');
    }

    for ($i = 0; ($i + $width - 1) < $count; $i++) {
        $window = [];
        $results[] = array_slice($array, $i, $width);
    }

    return $results;
}

Timeline.php

<?php

declare(strict_types=1);

namespace Gammadia\Collections\Timeline;

use Brick\DateTime\LocalDateTime;
use Traversable;
use RangeException;
use IteratorAggregate;
use Gammadia\DateTimeExtra\LocalDateTimeInterval;
use Generator;
use Webmozart\Assert\Assert;

use function Gammadia\Collections\Functional\collect;
use function Gammadia\Collections\Functional\concat;
use function Gammadia\Collections\Functional\filter;
use function Gammadia\Collections\Functional\first;
use function Gammadia\Collections\Functional\last;
use function Gammadia\Collections\Functional\map;
use function Gammadia\Collections\Functional\mapSpread;
use function Gammadia\Collections\Functional\reduce;
use function Gammadia\Collections\Functional\unique;
use function Gammadia\Collections\Functional\window;

/**
 * A timeline of a time-varying values for a single concept.
 * 
 * This is basically a collection of non-overlapping time ranges, each representing
 * a continuous range during which the value of the concept does not vary. Each change
 * of value is associated with a new range in the collection.
 * 
 * The value might be undefined for some duration in the timeline, in which case it
 * is assumed to be null. While a timeline can safely store and manipulate null values,
 * some functions might not provide a way to distinguish between an explicit null value
 * and the absence of value. Purposely storing nulls in a timeline is discouraged.
 */
class Timeline implements IteratorAggregate {
    /**
     * @var array<int, LocalDateTimeInterval|mixed>
     */
    private $items = [];

    private function __construct(array $items) {
        // We assume that items are correctly sorted and without overlapping range
        // This is enforced by add()
        $this->items = $items;
    }

    public static function empty(): self {
        return new self([]);
    }

    public static function with(LocalDateTimeInterval $range, $value): self {
        return self::empty()->add($range, $value);
    }

    public static function constant($value): self {
        return self::with(LocalDateTimeInterval::between(null, null), $value);
    }

    public static function import(array $items, callable $range): self {
        return reduce(
            $items,
            static function ($timeline, $item) use ($range): self {
                return $timeline->add($range($item), $item);
            },
            self::empty()
        );
    }

    /**
     * @todo doc
     */
    public static function zipAll(Timeline ...$timelines): self {
        $hasInfiniteStart = false;
        $starts = collect($timelines, function (Timeline $timeline) use (&$hasInfiniteStart): Generator {
            yield from collect($timeline->items, static function (array $item) use (&$hasInfiniteStart): Generator {
                /**
                 * @var LocalDateTimeInterval $range
                 */
                [$range,] = $item;
                $start = $range->getStart();
                if (null === $start) {
                    $hasInfiniteStart = true;
                } else {
                    yield $start;
                }
            });
        });

        $hasInfiniteEnd = false;
        $ends = collect($timelines, function (Timeline $timeline) use (&$hasInfiniteEnd): Generator {
            yield from collect($timeline->items, static function (array $item) use (&$hasInfiniteEnd): Generator {
                /**
                 * @var LocalDateTimeInterval $range
                 */
                [$range,] = $item;
                $end = $range->getEnd();
                if (null === $end) {
                    $hasInfiniteEnd = true;
                } else {
                    yield $end;
                }
            });
        });

        $boundaries = unique(concat($starts, $ends), static function (LocalDateTime $boundary): string {
            return (string) $boundary;
        });

        usort($boundaries, static function (LocalDateTime $a, LocalDateTime $b): int {
            switch (true) {
                case $a->isBefore($b):
                    return -1;
                case $a->isEqualTo($b):
                    return 0;
                default:
                    return 1;
            }
        });

        $boundaries = concat(
            $hasInfiniteStart ? [null] : [],
            $boundaries,
            $hasInfiniteEnd ? [null] : [],
        );

        $items = map(
            mapSpread(window($boundaries, 2), static function (?LocalDateTime $start, ?LocalDateTime $end): LocalDateTimeInterval {
                return LocalDateTimeInterval::between($start, $end);
            }),
            static function (LocalDateTimeInterval $range) use ($timelines): array {
                return [$range, map($timelines, static function (Timeline $timeline) use ($range) {
                    $slice = $timeline->slice($range);

                    if (empty($slice->items)) {
                        return null;
                    }

                    /**
                     * @var LocalDateTimeInterval $itemRange
                     */
                    [$itemRange, $itemValue] = first($slice->items);

                    // This is only a sanity check, cannot happen unless a bug is introduced somewhere in this class.
                    Assert::count($slice->items, 1, 'must not have more than one item in slice since every boundaries were extracted');
                    Assert::true($itemRange->isEqualTo($range), 'must have same range as slice since every boundaries were extracted');

                    return $itemValue;
                })];
            }
        );

        // Remove slices of the timeline without any matching items in all other timelines
        return (new self($items))->filter(static function (array $zipped): bool {
            return !empty(filter($zipped));
        });
    }

    /**
     * Alias for `Timeline::zipAll()->map()` with intermediate array unpacking
     */
    public static function merge(callable $fn, Timeline ...$timelines): self {
        return self::zipAll(...$timelines)
            ->map(static function (array $values, LocalDateTimeInterval $range) use ($fn) {
                $values[] = $range; // Add the range as the last parameter to map
                return $fn(...$values);
            });
    }

    public function size(): int {
        return count($this->items);
    }

    /**
     * Returns a new timeline with a new value for the given range.
     * 
     * @throws RangeException If the range overlaps an already defined range in this timeline
     */
    public function add(LocalDateTimeInterval $range, $value): self {
        $items = $this->items;


        // @todo test this, never ran it \o/
        for (
            $start = 0, $end = count($items);
            $i = $start + (int)(($end-$start) / 2), $i < $end;
        ) {
            /**
             * @var LocalDateTimeInterval $itemRange
             */
            [$itemRange,] = $items[$i];

            if ($itemRange->intersects($range)) {
                throw new RangeException('Overlapping ranges');
            } else if ($itemRange->isBeforeInterval($range)) {
                // If $items[$i] is before the range, we drop the lower half of indices
                $start = $i + 1;
            } else {
                // If $items[$i] is after the range, we instead drop the higher half of indices
                $end = $i;
            }
        }

        array_splice($items, $i, 0, [[$range, $value]]);

        return new self($items);
    }

    /**
     * Returns a timeline without any ranges outside the given range.
     * 
     * If some ranges in this timeline cross the given range boundaries, they will be truncated.
     */
    public function slice(LocalDateTimeInterval $range): self {
        $items = $this->items;

        $min = $range->getStart();
        if (null !== $min) {
            for (
                $start = 0, $end = count($items);
                $i = $start + (int)(($end-$start) / 2), $i < $end;
            ) {
                /**
                 * @var LocalDateTimeInterval $itemRange
                 */
                [$itemRange,] = $items[$i];
                
                if ($itemRange->contains($min)) {
                    $items[$i][0] = $itemRange->withStart($min);
                    break;
                } else if ($itemRange->isBefore($min)) {
                    $start = $i + 1;
                } else {
                    $end = $i;
                }
            }

            $items = array_slice($items, $i);
        }

        $max = $range->getEnd();
        if (null !== $max) {
            for (
                $start = 0, $end = count($items);
                $i = $start + (int)(($end-$start) / 2), $i < $end;
            ) {
                /**
                 * @var LocalDateTimeInterval $itemRange
                 */
                [$itemRange,] = $items[$i];
                
                if ($itemRange->contains($max)) {
                    $items[$i][0] = $itemRange->withEnd($max);
                    ++$i;
                    break;
                } else if ($itemRange->isBefore($max)) {
                    $start = $i + 1;
                } else {
                    $end = $i;
                }
            }

            $items = array_slice($items, 0, $i);
        }

        return new self($items);
    }

    /**
     * Applies the given function to every ranges of value in this timeline.
     */
    public function map(callable $fn): self {
        return new self(map($this->items, static function(array $item) use ($fn): array {
            [$range, $value] = $item;
            return [$range, $fn($value, $range)];
        }));
    }

    /**
     * Filters the timeline, keeping only ranges of value for which the predicate returns true.
     */
    public function filter(callable $predicate): self {
        return new self(filter($this->items, static function(array $item) use ($predicate): bool {
            [$range, $value] = $item;
            return $predicate($value, $range);
        }));
    }

    /**
     * Reduces this interval by invoking the reducer with every range of values in this timeline.
     */
    public function reduce(callable $reducer, $initialValue = null) {
        return reduce($this->items, static function($carry, array $item) use ($reducer) {
            [$range, $value] = $item;
            return $reducer($carry, $value, $range);
        }, $initialValue);
    }

    /**
     * Simplifies the timeline such that no two item with meeting ranges with equal values,
     * merging adjacent items if necessary.
     */
    public function simplify(callable $equals = null): self {
        return reduce($this->items, static function ($items, array $item) use ($equals): array {
            /**
             * @var LocalDateTimeInterval $range
             */
            [$range, $value] = $item;

            /**
             * @var LocalDateTimeInterval $lastRange
             */
            [$lastRange, $lastValue] = last($items);

            if (
                $lastRange->meets($range) &&
                (null === $equals ? $value == $lastValue : $equals($value, $lastValue))
            ) {
                array_splice($items, -1, 1, [
                    LocalDateTimeInterval::between($lastRange->getStart(), $range->getEnd()),
                    $value
                ]);
            } else {
                $items[] = $item;
            }

            return $items;
        });
    }

    /**
     * Alias for Timeline::zipAll($this, ...$others).
     */
    public function zip(self ...$other): self {
        return self::zipAll($this, ...$other);
    }

    /**
     * Returns a iterator over every ranges of values in this timeline.
     * Keys are the ranges of each item.
     */
    public function getIterator(): Traversable {
        foreach ($this->items as [$range, $value]) {
            yield $range => $value;
        }
    }
}