<?php
/**
* @copyright (c) 2013
* @package Diba
* @subpackage GenericTree
*/
namespace Diba\GenericTree;
use Diba\Tree\Node as INode;
use Diba\Tree\NodeList as INodeList;
/**
* Implementación genérica de un árbol, construída desde una tabla.
*/
class TableTree extends Node
{
/**
* Mapa de nodos por su id.
*
* @var array
*/
protected $nodes = [];
/**
* Opciones de entrada y salida.
*
* @var \Diba\GenericTree\TableTreeOptions
*/
protected $options;
/**
* Mapa de colección de nodos "huérfanos" por su id de padre, es decir,
* aquellos que deberían tener un padre pero no fue encontrado.
*
* @var array
*/
protected $orphans = [];
/**
* Constructor
*
* @param \Diba\GenericTree\TableTreeOptions $options
* Opciones de entrada y salida.
* @return \Diba\GenericTree\TableTree
*/
public function __construct(TableTreeOptions $options = null)
{
if ($options === null) {
$this->options = new TableTreeOptions();
} else {
$this->options = $options;
}
}
/**
* Construye el árbol desde una tabla.
*
* @todo Detectar errores recursivos.
* @todo Detectar multiples ubicaciones (en un mísmo grupo).
*
* @param array $table La tabla de datos.
* @param bool $sort Indica si los nodos deben ser ordenados.
* @return bool Verdadero si el árbol ha cambiado.
*/
public function build
(array $table, $sort = false) {
return false;
}
// Acceso corto a los nombres de las claves de los ids de entrada
$idKey = $this->options->getIdKey();
$parentIdKey = $this->options->getParentIdKey();
// Datos temporales
$onHold = []; // The "on hold" list
$onHoldChildren = []; // Children on hold nodes
$onHoldChildrenMap = []; // Children on hold map
$sortableChildren = []; // Children that should be sorted
// Agregar el árbol en sí, al mapa de nodos bajo el id "0"
$this->nodes[0] = $this;
// Construir árbol
foreach ($table as $index => $row) {
// Forzar fila hacia un array, para obtener los ids
$nodeId = $row[$idKey];
$nodeParentId = $row[$parentIdKey];
// Ignorar filas con clave "0"
if ((int) $nodeId === 0) {
continue;
}
// Crear nodo
$node = new Node($table[$index]);
// Indica si el nodo padre del nodo actual está en espera
$parentIsOnHold = false;
// ¿Se ha encontrado ya el nodo padre de este nodo?
if (isset($this->nodes[$nodeParentId])) { $parent = $this->nodes[$nodeParentId];
} elseif (isset($onHold[$nodeParentId])) { $onHoldKey = $onHold[$nodeParentId];
$parent = $onHoldChildrenMap[$onHoldKey][$nodeParentId];
$parentIsOnHold = true;
} elseif (isset($parent)) { }
// Dar nodo a su padre (si éste ha sido encontrado)
$parentChildren = $parent->getChildren();
// Establecer el nodo padre y agregar sus hijos
$node->setParent($parent);
$parentChildren->add($node);
if ($parentIsOnHold) {
// Agregar nodo al mapa de lista de espera
$onHold[$nodeId] = $onHold[$nodeParentId];
$onHoldChildrenMap[$onHold[$nodeId]][$nodeId] = $node;
} else {
// Agregar nodo al mapa final
$this->nodes[$nodeId] = $node;
}
// Agregar nodos hijos para ordenar, sólo si es necesario
if ($sort && $parentChildren->count() > 1 && !isset($sortableChildren[$nodeParentId])) { $sortableChildren[$nodeParentId] = $parentChildren;
}
} else {
// Agregar nodo a la lista de espera
$onHold[$nodeId] = $nodeParentId;
if (!isset($onHoldChildren[$nodeParentId])) { $onHoldChildren[$nodeParentId] = new NodeList();
}
if (!isset($onHoldChildrenMap[$nodeParentId])) { $onHoldChildrenMap[$nodeParentId] = [];
}
// Agregar el nodo al mapa de lista de espera
$onHoldChildren[$nodeParentId]->add($node);
$onHoldChildrenMap[$nodeParentId][$nodeId] = $node;
}
// ¿És este nodo el padre de alguno de los nodos en espera?
if (isset($onHoldChildren[$nodeId])) { $nodeChildren = $node->getChildren();
// Establecer el nodo padre, y agregar a sus hijos
$onHoldChildren[$nodeId]->setParent($node);
$nodeChildren->merge($onHoldChildren[$nodeId]);
// Agregar nodos al mapa final
$this->nodes+= $onHoldChildrenMap[$nodeId];
// Borrar referencias del nodo hacia la lista de espera
unset($onHoldChildren[$nodeId]); unset($onHoldChildrenMap[$nodeId]);
// Agregar nodos hijos para ordenar, sólo si es necesario
if ($sort && $nodeChildren->count() > 1 && !isset($sortableChildren[$nodeId])) { $sortableChildren[$nodeId] = $nodeChildren;
}
}
}
// Obtener los nodos "huérfanos", donde su parent_id != 0 pero de todas
// maneras no ha sido encontrado
if (!empty($onHoldChildren)) { $this->orphans = $onHoldChildren;
}
// Ordenar los nodos, sólo si es necesario
if (!empty($sortableChildren)) { foreach ($sortableChildren as $unsortedChildren) {
$unsortedChildren->setComparator(
$this->options->getComparator()
);
$unsortedChildren->sort(); }
}
return true;
}
/**
* Devuelve un nodo obtenido por su id.
*
* @param scalar $id El id del nodo a buscar.
* @return \Diba\Tree\Node|null
*/
public function getNodeById($id)
{
$id = (string) $id;
$node = null;
if (isset($this->nodes[$id])) { $node = $this->nodes[$id];
}
return $node;
}
/**
* Devuelve la instancia de las opciones de entrada y salida.
*
* @return \Diba\GenericTree\TableTreeOptions
*/
public function getOptions()
{
return $this->options;
}
/**
* Devuelve una colección de nodos "huérfanos", agrupados por el id de su
* padre (no encontrado).
*
* @return array
*/
public function getOrphans()
{
return $this->orphans;
}
/**
* Reestablece el árbol.
*
* @return void
* @override \Diba\GenericTree\Node::reset()
*/
{
$this->nodes = [];
$this->orphans = [];
}
/**
* Establece las opciones de entrada y salida, y devuelve las anteriores.
*
* @param \Diba\GenericTree\TableTreeOptions $options
* La nueva instancia de las opciones de entrada y salida.
* @return \Diba\GenericTree\TableTreeOptions
*/
public function setOptions(TableTreeOptions $options)
{
$previousOptions = $this->options;
$this->options = $options;
return $previousOptions;
}
}