README

概述

包 dan-on/php-interval-tree 是一种称为红黑树的平衡二叉搜索树数据结构的实现。

基于 Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein 出版的《算法导论》第三版中描述的区间树。

复杂性

通过 Composer 安装

composer require dan-on/php-interval-tree

用法

区间树

insert(IntervalInterface $interval, mixed $value): void

将新的（区间 + 值）对插入到区间树中

use Danon\IntervalTree\IntervalTree;

$tree = new IntervalTree();
$tree->insert(new NumericInterval(1, 10), 'val1');
$tree->insert(new NumericInterval(2, 5), 'val2');
$tree->insert(new NumericInterval(11, 12), 'val3');

findIntersections(IntervalInterface $interval): Iterator<Pair>

查找与给定区间相交的成对元素

$intersections = $tree->findIntersections(new NumericInterval(3, 5));
foreach($intersections as $pair) {
    $pair->getInterval()->getLow(); // 1, 2
    $pair->getInterval()->getHigh(); // 10, 5
    $pair->getValue(); // 'val1', 'val2'
}

hasIntersection(IntervalInterface $interval): bool

如果区间在树中至少有一个交点，则返回 true

$tree->hasIntersection(new NumericInterval(3, 5)); // true

countIntersections(IntervalInterface $interval): int

计算树中给定区间的交点数量

$tree->countIntersections(new NumericInterval(3, 5)); // 2

remove(IntervalInterface $interval, $value): bool

通过区间和值从树中删除节点

$tree->remove(new NumericInterval(11, 12), 'val3'); // true

exist(IntervalInterface $interval, $value): bool

如果区间和值存在于树中，则返回 true

$tree->exists(new NumericInterval(11, 12), 'val3'); // true

isEmpty(): bool

如果树为空，则返回 true

$tree->isEmpty(); // false

getSize(): int

获取存储在区间树中的项目数量

$tree->getSize(); // 3

区间

包含基于数字和 DateTimeInterface 的区间类型。

数值区间

use Danon\IntervalTree\Interval\NumericInterval;

// Instantiate numeric interval from array
$numericInterval = NumericInterval::fromArray([1, 100]);

// Instantiate numeric interval with constructor
$numericInterval = new NumericInterval(1, 100);

日期时间区间

use Danon\IntervalTree\Interval\DateTimeInterval;

// Instantiate DateTime interval from array
$dateTimeInterval = DateTimeInterval::fromArray([
    new DateTimeImmutable('2021-01-01 00:00:00'),
    new DateTimeImmutable('2021-01-02 00:00:00'),
]);

// Instantiate DateTime interval with constructor
$dateTimeInterval = new DateTimeInterval(
    new DateTimeImmutable('2021-01-01 00:00:00'), 
    new DateTimeImmutable('2021-01-02 00:00:00')
);

测试

./vendor/bin/phpunit