Foros del Web - Ver Mensaje Individual - [APORTE] Estructura de árbol desde de base de datos

Nisrokh · #2 (**permalink**) 27/08/2013, 10:04

La función table_tree():

Código PHP:

Ver original<?php
 
/**
 * @author Diego P. M. Baltar <[email protected]>
 * @copyright (c) 2013
 */
 
/**
 * Construye una estructura de árbol desde una tabla, donde cada fila tiene un
 * campo con su id único, y un campo indicando el id de su padre.
 * 
 * La estructura de las opciones:
 * <pre>
 * array(
 *     // Claves de entrada
 *     'id_key'        => 'id',
 *     'parent_id_key' => 'parent_id',
 *     // Claves de salida
 *     'value_key'     => 'value',
 *     'parent_key'    => 'parent',
 *     'children_key'  => 'children',
 *     'nodes_key'     => 'nodes',
 *     'orphans_key'   => 'orphans',
 *     // Comparador para ordenar los nodos
 *     'comparator'    => SORT_REGULAR // O un "callable" usado por usort()
 * )
 * </pre>
 * 
 * @todo Detectar errores recursivos.
 * @todo Detectar ubicaciones múltiples (en un mísmo grupo).
 * 
 * @param array $table La tabla de datos.
 * @param bool $sort Indica si los nodos deben ser ordenados, o no.
 * @param array $options Opciones de entrada y salida.
 * @return array
 */
function table_tree($table, $sort = false, $options = array())
{
    if (!is_array($table) || empty($table)) {
        return array();
    }
    
    // Opciones por defecto
    static $default_options = array(
        'id_key'        => 'id',
        'parent_id_key' => 'parent_id',
        'value_key'     => 'value',
        'parent_key'    => 'parent',
        'children_key'  => 'children',
        'nodes_key'     => 'nodes',
        'orphans_key'   => 'orphans',
        'comparator'    => SORT_REGULAR
    );
    
    // Establecer opciones que no fueron especificadas
    if (empty($options)) {
        $options = $default_options;
    } else {
        foreach ($default_options as $name => $value) {
            if (!isset($options[$name])) {
                $options[$name] = $value;
            }
        }
    }
    
    // Acceso corto a las claves de entrada
    $id_key = $options['id_key'];
    $parent_id_key = $options['parent_id_key'];
    
    // Acceso corto a las claves de salida
    $value_key = $options['value_key'];
    $parent_key = $options['parent_key'];
    $children_key = $options['children_key'];
    $nodes_key = $options['nodes_key'];
    $orphans_key = $options['orphans_key'];
    
    // El árbol final (sigue la estructura de un nodo, más 2 items)
    $tree = array(
        $value_key    => null,
        $parent_key   => null,
        $children_key => array(),
        $nodes_key    => array(),
        $orphans_key  => array()
    );
    
    // Datos temporales
    $nodes = &$tree[$nodes_key];     // Mapa de nodos (ref. nodos en el árbol)
    $orphans = &$tree[$orphans_key]; // Nodos que no se encontro su padre
    $on_hold = array();              // Lista de nodos en espera de su padre
    $on_hold_children = array();     // Nodos en lista de espera
    $on_hold_children_map = array(); // Mapa de nodos en lista de espera
    $sortable_children = array();    // Nodos que deberían ser ordenados
    
    // Agregar el árbol al mapa de nodos bajo el id "0"
    $nodes[0] = &$tree;
    
    // Construír el árbol
    foreach ($table as $index => $row) {
        // Forzar los datos hacia un array, sólo para obtener los ids
        $row = (array) $row;
        $node_id = $row[$id_key];
        $node_parent_id = $row[$parent_id_key];
        
        // Ignorar filas con id = "0"
        if ((int) $node_id === 0) {
            continue;
        }
        
        // Crear nodo
        $new_node = array(
            $value_key => $table[$index],
            $parent_key => null,
            $children_key => array()
        );
        
        // Indica si el padre del nodo actual está en espera
        $parent_is_on_hold = false;
        
        // ¿Se ha encontrado ya el nodo padre de este nodo?
        if (isset($nodes[$node_parent_id])) {
            $parent = &$nodes[$node_parent_id];
        } elseif (isset($on_hold[$node_parent_id])) {
            $on_hold_key = $on_hold[$node_parent_id];
            $parent = &$on_hold_children_map[$on_hold_key][$node_parent_id];
            $parent_is_on_hold = true;
        } elseif (isset($parent)) {
            unset($parent);
        }
        
        // Dar nodo a su padre (si éste ha sido encontrado)
        if (isset($parent)) {
            $parent_children = &$parent[$children_key];
            $parent_children[] = $new_node;
            $parent_children_count = count($parent_children);
            $node = &$parent_children[$parent_children_count - 1];
            
            // Establecer el nodo padre
            $node[$parent_key] = &$parent;
            
            if ($parent_is_on_hold) {
                // Agregar nodo al mapa de nodos en espera
                $on_hold[$node_id] = $on_hold[$node_parent_id];
                $on_hold_children_map[$on_hold[$node_id]][$node_id] = &$node;
            } else {
                // Agregar nodo al mapa final
                $nodes[$node_id] = &$node;
            }
            
            // Agregar nodos hijos para ordenar, sólo si es necesario
            if ($sort && $parent_children_count > 1
                    && !isset($sortable_children[$node_parent_id])) {
                $sortable_children[$node_parent_id] = &$parent_children;
            }
        } else {
            // Agregar nodo a la lista de espera, hasta que aparezca su padre
            $on_hold[$node_id] = $node_parent_id;
            
            if (!isset($on_hold_children[$node_parent_id])) {
                $on_hold_children[$node_parent_id] = array();
            }
            
            // Poner el nodo en espera
            $on_hold_children[$node_parent_id][] = $new_node;
            $node = &$on_hold_children[$node_parent_id]
                [count($on_hold_children[$node_parent_id]) - 1];
            
            if (!isset($on_hold_children_map[$node_parent_id])) {
                $on_hold_children_map[$node_parent_id] = array();
            }
            
            // Agregar nodo al mapa de lista de espera
            $on_hold_children_map[$node_parent_id][$node_id] = &$node;
        }
        
        // ¿És este nodo el padre de alguno de los nodos en espera?
        if (isset($on_hold_children[$node_id])) {
            // Agregar nodo al árbol final, actualizar referencias, y establecer
            // su nodo padre (manipular 1 nodo manualmente)
            if (count($on_hold_children[$node_id]) < 2) {
                $on_hold_node = &$on_hold_children[$node_id][0];
                $on_hold_node[$parent_key] = &$node;
                $node[$children_key][] = $on_hold_node;
                $on_hold_node_value = (array) $on_hold_node[$value_key];
                $on_hold_node_id = $on_hold_node_value[$id_key];
                $on_hold_children_map[$node_id][$on_hold_node_id]
                    = &$node[$children_key][count($node[$children_key]) - 1];
            } else {
                foreach ($on_hold_children[$node_id] as &$on_hold_node) {
                    $on_hold_node[$parent_key] = &$node;
                    $node[$children_key][] = $on_hold_node;
                    $on_hold_node_value = (array) $on_hold_node[$value_key];
                    $on_hold_node_id = $on_hold_node_value[$id_key];
                    $on_hold_children_map[$node_id][$on_hold_node_id]
                        = &$node[$children_key]
                            [count($node[$children_key]) - 1];
                }
            }
            
            // Agregar nodos al mapa final
            $tree[$nodes_key]+= $on_hold_children_map[$node_id];
            
            // Borrar referencias hacia la lista de espera
            unset($on_hold_children[$node_id]);
            unset($on_hold_children_map[$node_id]);
            
            // Agregar nodos hijos para ordenar, sólo si es necesario
            if ($sort && count($node[$children_key]) > 1
                    && !isset($sortable_children[$node_id])) {
                $sortable_children[$node_id] = &$node[$children_key];
            }
        }
    }
    
    // Obtener los nodos "huérfanos", donde su parent_id != 0 pero de todas
    // maneras no ha sido encontrado
    if (!empty($on_hold_children)) {
        $orphans = $on_hold_children;
    }
    
    // Ordernar los nodos, sólo si es necesario
    if (!empty($sortable_children)) {
        // Obtener el comparador establecido
        $comparator = $options['comparator'];
        
        foreach ($sortable_children as &$unsorted_children) {
            if (is_callable($comparator)) {
                usort($unsorted_children, $comparator);
            } else {
                sort($unsorted_children, $comparator);
            }
        }
    }
    
    return $tree;
}

Ahora, un simple ejemplo de como utilizarlo con una base de datos:

Código PHP:

Ver original// MySQL info.
define('MYSQL_HOSTNAME', 'localhost');
define('MYSQL_USERNAME', 'root');
define('MYSQL_PASSWORD', '123456');
define('MYSQL_DATABASE', 'test');
 
// Crear conexión
$sql_connection = mysqli_connect(
    MYSQL_HOSTNAME,
    MYSQL_USERNAME,
    MYSQL_PASSWORD,
    MYSQL_DATABASE
);
 
if (!$sql_connection) {
    exit(sprintf(
        'Database connection error: (%s) %s',
        mysqli_connect_errno(),
        mysqli_connect_error()
    ));
} else {
    mysqli_query($sql_connection, 'SET NAMES \'utf8\'');
}
 
// Obtener los datos del grupo "0"
$sql_query = '
    SELECT
        links.id,
        links.name,
        links_hierarchy.group_id,
        links_hierarchy.parent_id,
        links_hierarchy.order_no
    FROM links
    INNER JOIN links_hierarchy
        ON links_hierarchy.link_id = links.id
    WHERE links_hierarchy.group_id = 0
        AND links.id > 0
';
 
// Ejecutar consulta
$sql_query_result = mysqli_query($sql_connection, $sql_query);
$table = array();
 
while ($row = mysqli_fetch_assoc($sql_query_result)) {
    $table[] = $row;
}
 
mysqli_free_result($sql_query_result);
mysqli_close($sql_connection);
 
// Aplicar shuffle() sólo para demostrarles que no importa el orden, el árbol
// siempre se construirá normalmente
shuffle($table);
 
// Función para el ordenamiento por el campo "name"
function compare_nodes($a, $b) {
    $a = $a['value']['name'];
    $b = $b['value']['name'];
    
    return strcasecmp($a, $b);
}
 
// Crear árbol
$tree = table_tree(
    $table,
    true,
    array(
        'comparator' => 'compare_nodes'
    )
);
 
// Obtener el nodo con el id "24"
$node = $tree['nodes'][24];
// Obtener la referencia al nodo padre
$parent_node = $node['parent'];
// Obtener el nodo hijo no. 3, suponiendo que existe
$child_node_3 = $node['children'][2];
// Obtener el valor del nodo (la fila original, obtenida de la consulta SQL)
$node_value = $node['value'];
 
// Los nombres de las claves, serán distintas si las especificamos en el
// parámetro $options, pero estas son utilizadas por defecto

(Continúa en comentarios)