Skip to content

Instantly share code, notes, and snippets.

@Muqsit
Last active April 21, 2021 22:23
Show Gist options
  • Save Muqsit/94c0fa1a6b74b6948ff841251641172a to your computer and use it in GitHub Desktop.
Save Muqsit/94c0fa1a6b74b6948ff841251641172a to your computer and use it in GitHub Desktop.
B-Tree in PHP test implementation
<?php
declare(strict_types=1);
final class Node{
public static function buildTree(int $size, ?Node $node = null) : self{
$node ??= new Node();
$node->entries[0] = new Node();
$node->entries[1] = new Node();
if($size <= 2){
static $i = 0;
$node->entries[0] = $i++;
$node->entries[1] = $i++;
return $node;
}
$size /= 2;
self::buildTree($size, $node->entries[0]);
self::buildTree($size, $node->entries[1]);
return $node;
}
public array $entries;
public function __construct(array $entries = []){
$this->entries = $entries;
}
}
final class Inventory{
public int $size;
public Node $slots_tree;
public function __construct(int $size){
$this->size = $size;
$this->slots_tree = Node::buildTree($this->size);
}
private function getNode(int $slot) : Node{
$node = $this->slots_tree;
$size = $this->size;
for($i = $this->size / 2; $i >= 2; $i /= 2){
$node = $node->entries[($slot & $i) > 0 ? 1 : 0];
}
return $node;
}
public function get(int $slot){
return $this->getNode($slot)->entries[$slot & 1];
}
public function set(int $slot, $value) : void{
$this->getNode($slot)->entries[$slot & 1] = $value;
}
}
$inventory = new Inventory(64);
var_dump($inventory->get(55));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment