locr-company / splay-tree
Fast splay-tree data structure
Requires
- php: >=8.1
Requires (Dev)
- captainhook/captainhook: ^5.23
- captainhook/hook-installer: ^1.0
- phpstan/extension-installer: ^1.4
- phpstan/phpstan: ^2.0
- phpstan/phpstan-deprecation-rules: ^2.0
- phpunit/phpunit: ^10.5
- squizlabs/php_codesniffer: ^3.11
This package is auto-updated.
Last update: 2024-12-23 21:26:15 UTC
README
Splay-tree: fast(non-recursive) and simple(< 1000 lines of code) Implementation is adapted directly from this GitHub Repository.
This tree is based on top-down splaying algorithm by D.Sleator. It supports
- splitting, merging
- updating of the keys
- bulk loading of the items into an empty or non-empty tree
- insertion with duplicates or no duplicates
- lookup without splaying
Install
composer require locr-company/splay-tree
<?php use Locr\Lib\SplayTree\SplayTree; $tree = new SplayTree();
API
new SplayTree(callable $comparator = null)
, where$comparator
is optional comparison function$tree->insert(int|array $key, mixed $data = null): Node
- Insert item, allow duplicate keys$tree->add(int|float $key, mixed $data = null): Node
- Insert item if it is not present$tree->remove(int|float $key): void
- Remove item$tree->find(int $key): ?Node
- Return node by its key$tree->findStatic(int $key): ?Node
- Return node by its key (doesn't re-balance the tree)$tree->at(int $index): ?Node
- Return node by its index in sorted order of keys$tree->contains(int $key): bool
- Whether a node with the given key is in the tree$tree->forEach(callable $visitor): self
In-order traversal$tree->keys(): array
- Returns the array of keys in order$tree->values(): array
- Returns the array of data fields in order$tree->range(int $low, int $high, callable $fn): self
- Walks the range of keys in order. Stops, if the visitor function returns a non-zero value.$tree->pop(): array
- Removes smallest node$tree->min(): int|float|array|null
- Returns min key$tree->max(): int|float|array|null
- Returns max key$tree->minNode(?Node $t = null): ?Node
- Returns the node with smallest key$tree->maxNode(?Node $t = null): ?Node
- Returns the node with highest key$tree->previousNode(Node $d): ?Node
- Predecessor node$tree->nextNode(Node $d): ?Node
- Successor node$tree->load(array $keys, array $values = [], bool $presort = false): self
- Bulk-load items. It expects values and keys to be sorted, but ifpresort
istrue
, it will sort keys and values using the comparator(in-place, your arrays are going to be altered).
Comparator
function(int|float $a, int|float $b): int
- Comparator function between two keys, it returns
0
if the keys are equal<0
ifa < b
>0
ifa > b
The comparator function is extremely important, in case of errors you might end
up with a wrongly constructed tree or would not be able to retrieve your items.
It is crucial to test the return values of your comparator(a, b)
and comparator(b, a)
to make sure it's working correctly, otherwise you may have bugs that are very
unpredictable and hard to catch.
Duplicate keys
insert()
method allows duplicate keys. This can be useful in certain applications (example: overlapping points in 2D).add()
method will not allow duplicate keys - if key is already present in the tree, no new node is created
Example
<?php use Locr\Lib\SplayTree\SplayTree; $t = new SplayTree(); $t->insert(5); $t->insert(-10); $t->insert(0); $t->insert(33); $t->insert(2); print_r($t->keys()); /** * Array( * [0] => -10 * [1] => 0 * [2] => 2 * [3] => 5 * [4] => 33 * ) */ print $t->size; // 5 print $t->min(); // -10 print $t->max(); // 33 $t->remove(0); print $t->size; // 4
Custom comparator (reverse sort)
<?php use Locr\Lib\SplayTree\SplayTree; $t = new SplayTree(function ($a, $b) { return $b - $a; }); $t->insert(5); $t->insert(-10); $t->insert(0); $t->insert(33); $t->insert(2); print_r($t->keys()); /** * Array *( * [0] => 33 * [1] => 5 * [2] => 2 * [3] => 0 * [4] => -10 *) */
Bulk insert
<?php use Locr\Lib\SplayTree\SplayTree; $t = new SplayTree(); $t->load([3, 2, -10, 20], ['C', 'B', 'A', 'D']); print_r($t->keys()); /** * Array *( * [0] => 3 * [1] => 2 * [2] => -10 * [3] => 20 *) */ print_r($t->values()); /** * Array *( * [0] => C * [1] => B * [2] => A * [3] => D *) */
Develop
composer install