N-мерное дерево, любой ОО язык

Мне нужно N-мерное (ограничено N потомков на узел) дерево с заполнением слева направо.

Нечто подобное (псевдо-vardump):

// before
TreeNode {
children [
TreeNode {
children [TreeNode {}, TreeNode {}, TreeNode {}]
},
TreeNode {
children [null, null, null]
},
TreeNode {
children [null, null, null]
}
]
}

Затем добавьте узел, и я должен иметь после этого:

// after
TreeNode {
children [
TreeNode {
children [TreeNode {}, TreeNode {}, TreeNode {}]
},
TreeNode {
children [TreeNode {}, null, null]
},
TreeNode {
children [null, null, null]
}
]
}

Вещи, которые я сделал:

<?php

class TreeNode
{
const NODE_CHILDREN_MAX = 3;
const NODE_CHILD_LEVELS_MAX = 6;

protected $id;

private $data;

private $parent;

private $children = [];

private $weight = 0;

/**
* Get id
*
* @return integer
*/
public function getId()
{
return $this->id;
}

/**
* Set weight
*
* @param integer $weight
* @return TreeNode
*/
public function setWeight($weight)
{
$this->weight = $weight;

return $this;
}

/**
* Get weight
*
* @return integer
*/
public function getWeight()
{
return $this->weight;
}

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

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

/**
* Set parent
*
* @param TreeNode $parent
* @return TreeNode
*/
public function setParent(TreeNode $parent = null)
{
$this->parent = $parent;

return $this;
}

/**
* Get parent
*
* @return TreeNode
*/
public function getParent()
{
return $this->parent;
}

/**
* Add children
*
* @param TreeNode $node
* @return TreeNode[]
*/
public function addChild(TrinarNode $node)
{
if (count($this->children) < static::NODE_CHILDREN_MAX) {
$this->children[] = $node;
$node->setParent($this);
$this->weight++;
return [$this, $node];
} else {

$children = $this->children;
/** @var TreeNode[] $children */
$children = $this->children;
usort($children, function (TreeNode $node1, TreeNode $node2) {
$levelDifference = $node1->subtractLevel($node2);
$sorting = ($node1->weight - $node2->weight) % 2;
if (abs($levelDifference) == 1) {
$sorting = -$sorting;
}
if ($sorting === 0) {
$sorting = ($node1->id - $node2->id) % 2;
}
return $sorting;
});
foreach ($children as $childNode) {
$this->weight++;
return array_merge($childNode->addChild($node), [$this]);
}
return [];
}
}

private function subtractLevel(TreeNode $node)
{
return $this->getChildLevelCount() - $node->getChildLevelCount();
}

private function getMaxDifference()
{
$logs = array_map(function (TreeNode $node) {
return floor(log($node->getWeight() === 0 ? 1 : $node->getWeight(), self::NODE_CHILDREN_MAX));
}, $this->children);
return pow(
self::NODE_CHILDREN_MAX,
min($logs) + 1
);
}

public static function getLevelCount($level)
{
if ($level === 0) {
return 0;
}
return pow(self::NODE_CHILDREN_MAX, $level) + self::getLevelCount($level - 1);
}

public function hasEmptyNodes()
{
return count($this->children) < self::NODE_CHILDREN_MAX;
}

/**
* Get children
*
* @return TreeNode[]
*/
public function getChildren()
{
return $this->children;
}

public function getChildLevelCount()
{
$weight = $this->weight;
if (!$weight) {
return 0;
}
return floor(log($weight, self::NODE_CHILDREN_MAX)) + 1;
}

private function getLevelBreakCount()
{
return count(array_unique(array_map(function (TreeNode $node) {
return $node->getChildLevelCount();
}, $this->children)));
}
}

В настоящее время проблема в том, что я не знаю, как решить, какой узел должен быть выбран при добавлении … В предыдущей версии узлы были добавлены на основе веса (наименьший вес должен быть выбран), но это не то, что мне нужно. Мне нужно добавить узлы слева направо, пока «уровень» не закончился, и если «уровень» заполнен, создать новый. Где «уровень» — группа узлов, находящихся на одинаковом расстоянии от корневого узла.

Предыдущая версия (для ясности):

// before
TreeNode {
children [
TreeNode {
children [TreeNode {}, null, null]
},
TreeNode {
children [null, null, null]
},
TreeNode {
children [null, null, null]
}
]
}

Затем добавьте узел:

// after
TreeNode {
children [
TreeNode {
children [TreeNode {}, null, null]
},
TreeNode {
children [TreeNode {}, null, null]
},
TreeNode {
children [null, null, null]
}
]
}

И юнит-тест, который TreeNode должен пройти (PHPUnit требуется):

<?php

class TestableTreeNode extends TreeNode
{
private $name;

public function setId($id)
{
$this->id = $id;
return $this;
}

/**
* @return mixed
*/
public function getName()
{
return $this->name;
}

/**
* @param mixed $name
* @return $this
*/
public function setName($name)
{
$this->name = $name;
return $this;
}
}

class TreeNodeTest extends \PHPUnit_Framework_TestCase
{
private $flatStorage = [];

public function test()
{
$this->iniSet('memory_limit', -1);
$data = $this->generateTestData(3);
$testable = $this->flatten($data->real);
$this->dump('expected.dump', $data->flat);
$this->dump('real.dump', $data->real);
$this->dump('converted.dump', $testable);
foreach ($data->flat as $levelNumber => $level) {
$this->assertArrayHasKey($levelNumber, $testable, 'Searched level doesn\'t exists!');
$testableLevel = $testable[$levelNumber];
foreach ($level as $nodeId => $node) {
$this->assertArrayHasKey($nodeId, $testableLevel, 'Searched node doesn\'t exists!');
$testableNode = $testableLevel[$nodeId];
$this->assertEquals($node->getName(), $testableNode->getName(), 'Tree is not valid!');
}
}
}

protected function generateTestData($levels = TestableTreeNode::NODE_CHILD_LEVELS_MAX)
{
$tree = new TestableTreeNode();
$flatTree = [];
$id = 0;
for ($level = 0; $level < $levels; $level++) {
$treeLevel = [];
$max = pow(TestableTreeNode::NODE_CHILDREN_MAX, $level+1);
for ($nodeId = 0; $nodeId < $max; $nodeId++) {
$treeNode = (new TestableTreeNode())
->setId($id++)
->setName($level . ':' . $nodeId);
$tree->addChild($treeNode);
$treeLevel[] = $treeNode;
}
$flatTree[] = $treeLevel;
}
return (object)['flat' => $flatTree, 'real' => $tree];
}

protected function flatten(TestableTreeNode $treeNode, $level = 0)
{
if (!$level) {
$this->flatStorage = [];
}
foreach ($treeNode->getChildren() as $child) {
$this->setRendered($level, $child);
$this->flatten($child, $level+1);
}
return $this->flatStorage;
}

protected function setRendered($level, $child)
{
if (!isset($this->flatStorage[$level])) {
$this->flatStorage[$level] = [];
}
$this->flatStorage[$level][] = $child;
}

private function dump($fileName, $data)
{
ob_start();
var_dump($data);
file_put_contents($fileName, ob_get_contents());
ob_end_clean();
}

}

Код в действии (с юнит-тестом)