maxprefix.php

<?php
/**
 * This file is part of BehatIntro
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 *
 * @author Nicolò Martini <nicmartnic@gmail.com>
 */

namespace NicMart;

class MaxPrefix
{
    private $trie = array(
        "children" => array(),
        "names" => array()
    );

    private $tuples;

    public function __construct(array $tuples)
    {
        $this->tuples = $tuples;

        foreach ($tuples as $name => $tuple) {
            $this->indexTuple($name, $tuple);
        }
    }

    public function getTupleWithMaxPrefix(array $values)
    {
        $names = array();

        $this->recursiveGetTupleWithMaxPrefix($values, $this->trie, 0, $names);

        uasort($names, function ($a, $b) {
            list($aPrefixLength, $aTupleLength) = $a;
            list($bPrefixLength, $bTupleLength) = $b;

            if ($aPrefixLength < $bPrefixLength) {
                return 1;
            }
            if ($aPrefixLength > $bPrefixLength) {
                return -1;
            }
            if ($aTupleLength < $bTupleLength) {
                return -1;
            }
            if ($aTupleLength > $bTupleLength) {
                return 1;
            }
            return 0;
        });

        return key($names);
    }

    private function recursiveGetTupleWithMaxPrefix(array $values, $trie, $length, &$names)
    {
        foreach ($trie["names"] as $name => $_) {
            $names[$name] = array($length, count($this->tuples[$name]));
        }

        foreach ($trie["children"] as $value => $subtrie) {
            if (isset($values[$value])) {
                $this->recursiveGetTupleWithMaxPrefix($values, $subtrie, $length + 1, $names);
            }
        }
    }

    private function indexTuple($name, array $tuple)
    {
        $currentRoot =& $this->trie;
        $currentRoot["names"][$name] = true;

        foreach ($tuple as $value) {
            if (!isset($currentRoot["children"][$value])) {
                $currentRoot["children"][$value] = array(
                    "children" => array(),
                    "names" => array()
                );
            }

            $currentRoot =& $currentRoot["children"][$value];
            $currentRoot["names"][$name] = true;
        }
    }
}