2017 © Pedro Peláez
 

library koki

Php data structures and utilities

image

martanlv/koki

Php data structures and utilities

  • Tuesday, February 13, 2018
  • by MartanLV
  • Repository
  • 1 Watchers
  • 0 Stars
  • 118 Installations
  • PHP
  • 0 Dependents
  • 0 Suggesters
  • 0 Forks
  • 0 Open issues
  • 11 Versions
  • 9 % Grown

The README.md


Scrutinizer Code Quality, (*1)

Todo: - [ ] ****Segment tree* stores intervals, and optimized for "which of these intervals contains a given point" queries. - [x] 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., (*2)

Performance / Space consumption for one dimension:, (*3)

  • [ ] Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space
  • [x] 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:, (*4)

  • [ ] 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):, (*5)

  • [ ] 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., (*6)

https://habrastorage.org/webt/lf/hw/dn/lfhwdnvjxlt9vrsbrd_ajpitubc.png, (*7)

--, (*8)

Latest Stable Version Total Downloads Latest Unstable Version License Monthly Downloads Daily Downloads composer.lock, (*9)

Maintainability Test Coverage, (*10)

__, (*11)

Code Coverage Build Status Code Intelligence Status, (*12)

StyleCI, (*13)

The Versions

13/02 2018

dev-master

9999999-dev

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

13/02 2018

1.0.6

1.0.6.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

13/02 2018

v1.0.7

1.0.7.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

13/02 2018

v1.0.5

1.0.5.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

13/02 2018

dev-analysis-q5D39y

dev-analysis-q5D39y

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

13/02 2018

v1.0.4

1.0.4.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

18/12 2017

dev-analysis-qB0Qm7

dev-analysis-qB0Qm7

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

18/12 2017

v1.0.3

1.0.3.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

12/12 2017

v1.0.2

1.0.2.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

12/12 2017

v1.0.1

1.0.1.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree

10/12 2017

v1.0.0

1.0.0.0

Php data structures and utilities

  Sources   Download

MIT

The Requires

  • php ^7.0

 

The Development Requires

interval tree