PHPackages                             martanlv/koki - 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. martanlv/koki

ActiveLibrary

martanlv/koki
=============

Php data structures and utilities

v1.0.7(8y ago)02.6k1[1 PRs](https://github.com/MartanLV/koki/pulls)MITPHPPHP ^7.0

Since Dec 10Pushed 4y agoCompare

[ Source](https://github.com/MartanLV/koki)[ Packagist](https://packagist.org/packages/martanlv/koki)[ RSS](/packages/martanlv-koki/feed)WikiDiscussions master Synced 3d ago

READMEChangelog (2)Dependencies (2)Versions (9)Used By (0)

Interval Tree: The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time.

---

[![Scrutinizer Code Quality](https://camo.githubusercontent.com/56da207f6c608548443617bcf062e10c620a4af63d57b315571f405c5873493c/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f4d617274616e4c562f6b6f6b692f6261646765732f7175616c6974792d73636f72652e706e673f623d6d6173746572)](https://scrutinizer-ci.com/g/MartanLV/koki/?branch=master)

Todo:

- \*\*\**Segment tree* stores intervals, and optimized for "which of these intervals contains a given point" queries.
- *Interval tree* stores intervals as well, but optimized for "which of these intervals overlap with a given interval" queries. It can also be used for point queries - similar to segment tree.
- *Range tree stores points*, and optimized for "which points fall within a given interval" queries.
- *Binary indexed tree* stores items-count per index, and optimized for "how many items are there between index m and n" queries.

Performance / Space consumption for one dimension:

- Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space
- Interval tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
- Range tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
- Binary Indexed tree - O(n logn) preprocessing time, O(logn) query time, O(n) space (k is the number of reported results).

All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:

- Segment tree - interval can be added/deleted in O(logn) time (see here)
- Interval tree - interval can be added/deleted in O(logn) time
- Range tree - new points can be added/deleted in O(logn) time (see here)
- Binary Indexed tree - the items-count per index can be increased in O(logn) time

Higher dimensions (d>1):

- Segment tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space
- Interval tree - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space
- Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space
- Binary Indexed tree - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space

Beethooven approves.

[![https://habrastorage.org/webt/lf/hw/dn/lfhwdnvjxlt9vrsbrd_ajpitubc.png](https://camo.githubusercontent.com/ba18690664ee666979bd431dbbb7296b1ae7a29bf8af3a3a709e7c28cb5af913/68747470733a2f2f686162726173746f726167652e6f72672f776562742f6c662f68772f646e2f6c666877646e766a786c74397672736272645f616a7069747562632e706e67)](https://camo.githubusercontent.com/ba18690664ee666979bd431dbbb7296b1ae7a29bf8af3a3a709e7c28cb5af913/68747470733a2f2f686162726173746f726167652e6f72672f776562742f6c662f68772f646e2f6c666877646e766a786c74397672736272645f616a7069747562632e706e67)

\--

[![Latest Stable Version](https://camo.githubusercontent.com/7c0d2a28229696adb9ffc2b3695a031feb0d08e7ff51b53136296c12b43a1ea5/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f762f737461626c65)](https://packagist.org/packages/martanlv/koki)[![Total Downloads](https://camo.githubusercontent.com/a44d9e43691602343a373eb0a559ae6902ea09e592f0bd958de590bacc02cb9d/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f646f776e6c6f616473)](https://packagist.org/packages/martanlv/koki)[![Latest Unstable Version](https://camo.githubusercontent.com/4d524e4c11ee03499ce829752acbd7f7a6ac1543fb46d1a904bda3d88ea5476b/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f762f756e737461626c65)](https://packagist.org/packages/martanlv/koki)[![License](https://camo.githubusercontent.com/5fb16b4f028582b143c23f6d721ee57288db9933094b5f8dd380904dddf3d0ed/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f6c6963656e7365)](https://packagist.org/packages/martanlv/koki)[![Monthly Downloads](https://camo.githubusercontent.com/682bff02ada53eb7e61d05d7156512ec631a92b3f9221c97c89f699910fdccb8/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f642f6d6f6e74686c79)](https://packagist.org/packages/martanlv/koki)[![Daily Downloads](https://camo.githubusercontent.com/18a268756627756b40f9e58af4d9de16418a4542e684795d03e3d6823b38b708/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f642f6461696c79)](https://packagist.org/packages/martanlv/koki)[![composer.lock](https://camo.githubusercontent.com/7a7bd6b90495cbc471b15ac6a7082439b8b3cb7a2cbf847110cc5f4de917dbca/68747470733a2f2f706f7365722e707567782e6f72672f6d617274616e6c762f6b6f6b692f636f6d706f7365726c6f636b)](https://packagist.org/packages/martanlv/koki)

[![Maintainability](https://camo.githubusercontent.com/a182fd0c4a9d5d95dd4c11d23aa9a7934c6656885fd46afa5df169c5a652645f/68747470733a2f2f6170692e636f6465636c696d6174652e636f6d2f76312f6261646765732f37643239636534363664393330393661386132332f6d61696e7461696e6162696c697479)](https://codeclimate.com/github/MartanLV/koki/maintainability)[![Test Coverage](https://camo.githubusercontent.com/bde0ad55ef2b6816d0fe70836a5c215bc13e7320bd5fa5f483c137e62dec2285/68747470733a2f2f6170692e636f6465636c696d6174652e636f6d2f76312f6261646765732f37643239636534363664393330393661386132332f746573745f636f766572616765)](https://codeclimate.com/github/MartanLV/koki/test_coverage)

\_\_

[![Code Coverage](https://camo.githubusercontent.com/adec2feadffaaa9a7436e97198631e2e79bfbc1b02d72679b4d668987a615299/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f4d617274616e4c562f6b6f6b692f6261646765732f636f7665726167652e706e673f623d6d6173746572)](https://scrutinizer-ci.com/g/MartanLV/koki/?branch=master)[![Build Status](https://camo.githubusercontent.com/815a9c492d9b5fcbc9dfbf5b842ad1fbc875bd1ffe524dee83a1cd76eda2c430/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f4d617274616e4c562f6b6f6b692f6261646765732f6275696c642e706e673f623d6d6173746572)](https://scrutinizer-ci.com/g/MartanLV/koki/build-status/master)[![Code Intelligence Status](https://camo.githubusercontent.com/355822b0c004216a25937e01e6e7de26a2542c098c8f40149d0cf4a5dd5c877c/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f4d617274616e4c562f6b6f6b692f6261646765732f636f64652d696e74656c6c6967656e63652e7376673f623d6d6173746572)](https://scrutinizer-ci.com/code-intelligence)

[![StyleCI](https://camo.githubusercontent.com/27f3ad2ca7b228dddeb5e557adaa219a1ed4bdb876af780faaed4bf7ba559c56/68747470733a2f2f7374796c6563692e696f2f7265706f732f3131333736373238332f736869656c643f6272616e63683d6d6173746572)](https://styleci.io/repos/113767283)

###  Health Score

30

—

LowBetter than 64% of packages

Maintenance20

Infrequent updates — may be unmaintained

Popularity17

Limited adoption so far

Community7

Small or concentrated contributor base

Maturity63

Established project with proven stability

 Bus Factor1

Top contributor holds 100% 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 ~9 days

Total

8

Last Release

3013d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/1ad2700439a590140f3cfb739eec9d4b0ac58a02230a84bcf57404813afb1fe7?d=identicon)[MartanLV](/maintainers/MartanLV)

---

Top Contributors

[![talbergs](https://avatars.githubusercontent.com/u/7649265?v=4)](https://github.com/talbergs "talbergs (9 commits)")

---

Tags

treeinterval

###  Code Quality

TestsPHPUnit

### Embed Badge

![Health badge](/badges/martanlv-koki/health.svg)

```
[![Health](https://phpackages.com/badges/martanlv-koki/health.svg)](https://phpackages.com/packages/martanlv-koki)
```

###  Alternatives

[gedmo/doctrine-extensions

Doctrine behavioral extensions

4.1k118.8M366](/packages/gedmo-doctrine-extensions)[stof/doctrine-extensions-bundle

Integration of the gedmo/doctrine-extensions with Symfony

1.9k85.3M381](/packages/stof-doctrine-extensions-bundle)[knplabs/knp-menu

An object oriented menu library

1.4k55.8M287](/packages/knplabs-knp-menu)[cuyz/valinor

Dependency free PHP library that helps to map any input into a strongly-typed structure.

1.5k9.2M108](/packages/cuyz-valinor)[knplabs/doctrine-behaviors

Doctrine Behavior Traits

92212.7M64](/packages/knplabs-doctrine-behaviors)[league/period

Time range API for PHP

7335.4M21](/packages/league-period)

PHPackages © 2026

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