dan-on / php-interval-tree
Is an implementation of interval binary search tree according to Thomas Cormen book "Introduction to Algorithms".
Installs: 9 561
Dependents: 0
Suggesters: 0
Security: 0
Stars: 14
Watchers: 2
Forks: 2
Open Issues: 1
Requires
- php: >=7.3
Requires (Dev)
- phpbench/phpbench: ^1.0
- phpmd/phpmd: ^2.10
- phpstan/phpstan: ^1.3.3
- phpunit/php-code-coverage: ^9.2
- phpunit/phpunit: ^9
- squizlabs/php_codesniffer: ^3.6
- vimeo/psalm: ^4.8
This package is auto-updated.
Last update: 2025-03-18 23:53:56 UTC
README
Overview
Package dan-on/php-interval-tree is an implementation of self balancing binary search tree data structure called Red-Black Tree.
Based on interval tree described in "Introduction to Algorithms 3rd Edition", published by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Complexity
Operation | Best, Average, Worst |
---|---|
Insertion | O(log(n)) |
Search | O(log(n)) |
Remove | O(log(n)) |
Space | O(n) |
Installing via Composer
composer require dan-on/php-interval-tree
Usage
Interval Tree
insert(IntervalInterface $interval, mixed $value): void
Insert new pair (interval + value) into interval tree
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>
Find pairs which intervals intersect with given interval
$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
Returns true if interval has at least one intersection in tree
$tree->hasIntersection(new NumericInterval(3, 5)); // true
countIntersections(IntervalInterface $interval): int
Count intersections given interval in tree
$tree->countIntersections(new NumericInterval(3, 5)); // 2
remove(IntervalInterface $interval, $value): bool
Remove node from tree by interval and value
$tree->remove(new NumericInterval(11, 12), 'val3'); // true
exist(IntervalInterface $interval, $value): bool
Returns true if interval and value exist in the tree
$tree->exists(new NumericInterval(11, 12), 'val3'); // true
isEmpty(): bool
Returns true if tree is empty
$tree->isEmpty(); // false
getSize(): int
Get number of items stored in the interval tree
$tree->getSize(); // 3
Intervals
There are numeric and DateTimeInterface-based interval types included.
Numeric interval
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);
DateTime interval
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') );
Tests
./vendor/bin/phpunit