ANTree vs NTree

antree.php

<?php
declare(strict_types = 1);

class ANTree
{
    const TERMINAL_NODE = 'LEAF';
    private $routeTree = [];

    public function add(array $segments): void
    {
        $this->routeTree = self::mergeRouteIntoTree(self::createRoute($segments), $this->routeTree);
    }

    public function getTree()
    {
        return $this->routeTree;
    }

    public function reset()
    {
        $this->routeTree = [];
    }

    private static function createRoute(array $segments, int $i = 0): array
    {
        if ($i === count($segments)) {
            return [self::TERMINAL_NODE => 'callback'];
        }
        $route[$segments[$i]] = self::createRoute($segments, ++$i);
        return $route;
    }

    private static function mergeRouteIntoTree(array $route, array $routeTree): array
    {
        $rKey = key($route);
        $routeTree[$rKey] = array_key_exists($rKey, $routeTree)
            ? self::mergeRouteIntoTree($route[$rKey], $routeTree[$rKey])
            : $route[$rKey];
        return $routeTree;
    }

    public function dispatch(array $segments)
    {
        $routeTree = $this->routeTree;
        foreach ($segments as $segment) {
            if (! isset($routeTree[$segment])) {
                return false;
            }
            $routeTree = $routeTree[$segment];
        }
        return $routeTree[self::TERMINAL_NODE];
    }
}

// Example usage

$tree = new ANTree();

$nRoutes = 100;
$nMatches = 30000;

$start = microtime(true);
for ($i = 0, $str = 'a'; $i < $nRoutes; $i++, $str++) {
    $a = explode('/', $str.'/{arg}');
    $tree->add($a);
    $lastStr = $str;
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->dispatch(explode('/', 'a/foo'));
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->dispatch(explode('/', $lastStr.'/foo'));
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->dispatch(explode('/', 'foobar/foo'));
}
echo (microtime(true) - $start).PHP_EOL;

ntree.php

<?php
declare(strict_types = 1);

class Node
{
    private $key;
    private $data;
    private $parent;
    private $children = [];

    public function __construct(string $key, $data = null)
    {
        $this->key = $key;
        $this->data = $data;
    }

    public function getKey(): string
    {
        return $this->key;
    }

    public function getData()
    {
        return $this->data;
    }

    public function setParent(Node $node): void
    {
        $this->parent = $node;
    }

    public function getParent(): ?Node
    {
        return $this->parent;
    }

    public function setChild(Node $node, string $key): void
    {
        $this->children[$key] = $node;
    }

    public function getChild(string $key): ?Node
    {
        return $this->children[$key] ?? null;
    }

    public function getFirstChild(): ?Node
    {
        return count($this->children) > 0
            ? current($this->children)
            : null;
    }
}

class NTree
{
    public const ROOT_KEY = 'ROOT';

    private $root;

    public function __construct()
    {
        $this->root = new Node(self::ROOT_KEY);
    }

    public function addPath(array $nodes): void
    {
        $path = new self();
        $head = $path->root;
        foreach ($nodes as $node) {
            $head->setChild($node, $node->getKey());
            $node->setParent($head);
            $head = $node;
        }
        $this->mergePath($path);
    }

    public function getRoot(): Node
    {
        return $this->root;
    }

    public function reset(): void
    {
        $this->root = new Node(self::ROOT_KEY);
    }

    public function traverseToNode(array $nodeKeys): ?Node
    {
        $treeNode = $this->getRoot();
        while($treeNode instanceof Node) {
            if (count($nodeKeys) === 0) {
                return $treeNode;
            }
            if ($treeNode->getFirstChild()->getKey() === '*') {
                array_shift($nodeKeys);
                $treeNode = $treeNode->getChild('*');
            } else {
                $treeNode = $treeNode->getChild(array_shift($nodeKeys));
            }
        }
        return null;
    }

    private function mergePath(self $path): void
    {
        $pathNode = $path->getRoot();
        $treeNode = $this->getRoot();
        $treeParent = $treeNode;
        while ($treeNode instanceof Node) {
            $pathNode = $pathNode->getFirstChild();
            if (! $pathNode instanceof Node) { // path is already a subset of a tree branch => discard
                return;
            }
            $treeParent = $treeNode;
            $treeNode = $treeNode->getChild($pathNode->getKey());
        }

        $pathNode->setParent($treeParent);
        $treeParent->setChild($pathNode, $pathNode->getKey());

        while ($treeParent->getKey() !== self::ROOT_KEY) { // backtrack to root
            $treeParent = $treeParent->getParent();
        }
        $this->root = $treeParent;
    }
}

function f(array $a) {
    return array_map(function (string $key): Node {
        return preg_match('#^{.+}$#', $key, $data)
            ? new Node('*', $data[0])
            : new Node($key);
    }, $a);
}

function g(NTree $tree, array $uri) {
    $node = $tree->traverseToNode($uri);
    while ($node instanceof Node) {
        echo $node->getKey().' - '.$node->getData().PHP_EOL;
        $node = $node->getParent();
    }
    echo PHP_EOL;
}

// Example usage

$tree = new NTree();

$nRoutes = 100;
$nMatches = 30000;

$start = microtime(true);
for ($i = 0, $str = 'a'; $i < $nRoutes; $i++, $str++) {
    $a = explode('/', $str.'/{arg}');
    $tree->addPath(f($a));
    $lastStr = $str;
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->traverseToNode(explode('/', 'a/foo'));
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->traverseToNode(explode('/', $lastStr.'/foo'));
}
echo (microtime(true) - $start).PHP_EOL;

$start = microtime(true);
for ($i = 0; $i < $nMatches; ++$i) {
    $node = $tree->traverseToNode(explode('/', 'foobar/foo'));
}
echo (microtime(true) - $start).PHP_EOL;