PHPackages                             dan-on/php-interval-tree - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. dan-on/php-interval-tree

ActiveLibrary[Utility & Helpers](/categories/utility)

dan-on/php-interval-tree
========================

Is an implementation of interval binary search tree according to Thomas Cormen book "Introduction to Algorithms".

v2.1.0(4y ago)1517.6k↓37%2[2 issues](https://github.com/dan-on/php-interval-tree/issues)MITPHPPHP >=7.3CI failing

Since Apr 1Pushed 4y ago3 watchersCompare

[ Source](https://github.com/dan-on/php-interval-tree)[ Packagist](https://packagist.org/packages/dan-on/php-interval-tree)[ RSS](/packages/dan-on-php-interval-tree/feed)WikiDiscussions master Synced 1mo ago

READMEChangelog (8)Dependencies (7)Versions (13)Used By (0)

PHP Interval tree
=================

[](#php-interval-tree)

[![Latest Stable Version](https://camo.githubusercontent.com/0f0ec80189dfe062bd41de60c06913c427a5342c6ef754d23bd7550e43d432eb/687474703a2f2f706f7365722e707567782e6f72672f64616e2d6f6e2f7068702d696e74657276616c2d747265652f76)](https://packagist.org/packages/dan-on/php-interval-tree) [![Total Downloads](https://camo.githubusercontent.com/44cccd76c2501ac9da462472f48b245b4fdc85656abd417e0a90390d6be71424/687474703a2f2f706f7365722e707567782e6f72672f64616e2d6f6e2f7068702d696e74657276616c2d747265652f646f776e6c6f616473)](https://packagist.org/packages/dan-on/php-interval-tree) [![License](https://camo.githubusercontent.com/9ab91ca76db1bf74c7ca4d1fa801aefd70b16407c7863fd14c95899f6f0e3d1c/687474703a2f2f706f7365722e707567782e6f72672f64616e2d6f6e2f7068702d696e74657276616c2d747265652f6c6963656e7365)](https://packagist.org/packages/dan-on/php-interval-tree) [![PHP Version Require](https://camo.githubusercontent.com/434e23b9561438bbb5f66ed576ae0656faa9eb4b7373a45e4234c826d3d0f011/687474703a2f2f706f7365722e707567782e6f72672f64616e2d6f6e2f7068702d696e74657276616c2d747265652f726571756972652f706870)](https://packagist.org/packages/dan-on/php-interval-tree)

Overview
--------

[](#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
----------

[](#complexity)

OperationBest, Average, WorstInsertionO(log(n))SearchO(log(n))RemoveO(log(n))SpaceO(n)Installing via Composer
-----------------------

[](#installing-via-composer)

```
composer require dan-on/php-interval-tree

```

Usage
-----

[](#usage)

### Interval Tree

[](#interval-tree)

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

[](#insertintervalinterface-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>

[](#findintersectionsintervalinterface-interval-iteratorpair)

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

[](#hasintersectionintervalinterface-interval-bool)

Returns true if interval has at least one intersection in tree

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

#### countIntersections(IntervalInterface $interval): int

[](#countintersectionsintervalinterface-interval-int)

Count intersections given interval in tree

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

#### remove(IntervalInterface $interval, $value): bool

[](#removeintervalinterface-interval-value-bool)

Remove node from tree by interval and value

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

#### exist(IntervalInterface $interval, $value): bool

[](#existintervalinterface-interval-value-bool)

Returns true if interval and value exist in the tree

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

#### isEmpty(): bool

[](#isempty-bool)

Returns true if tree is empty

```
$tree->isEmpty(); // false
```

#### getSize(): int

[](#getsize-int)

Get number of items stored in the interval tree

```
$tree->getSize(); // 3
```

### Intervals

[](#intervals)

There are numeric and DateTimeInterface-based interval types included.

#### Numeric interval

[](#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

[](#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
-----

[](#tests)

```
./vendor/bin/phpunit

```

###  Health Score

34

—

LowBetter than 77% of packages

Maintenance17

Infrequent updates — may be unmaintained

Popularity36

Limited adoption so far

Community12

Small or concentrated contributor base

Maturity58

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 99.2% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~73 days

Recently: every ~94 days

Total

10

Last Release

1581d ago

Major Versions

v1.x-dev → v2.0.02021-09-23

PHP version history (4 changes)v1.0PHP ^5.3 || ^7.0

v1.0.4.x-devPHP ^7.1

v1.0.4PHP ^5.3 || ^7.0 || ^8.0

v2.0.0PHP >=7.3

### Community

Maintainers

![](https://avatars.githubusercontent.com/u/215276?v=4)[esp](/maintainers/dan1)[@dan1](https://github.com/dan1)

---

Top Contributors

[![dan-on](https://avatars.githubusercontent.com/u/7466036?v=4)](https://github.com/dan-on "dan-on (121 commits)")[![transistive](https://avatars.githubusercontent.com/u/16435930?v=4)](https://github.com/transistive "transistive (1 commits)")

---

Tags

data-structuresintersectionsinterval-treeoverlapphprange-treered-black-tree

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan, Psalm

Code StylePHP\_CodeSniffer

Type Coverage Yes

### Embed Badge

![Health badge](/badges/dan-on-php-interval-tree/health.svg)

```
[![Health](https://phpackages.com/badges/dan-on-php-interval-tree/health.svg)](https://phpackages.com/packages/dan-on-php-interval-tree)
```

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)