php - 如何使用 PHP 和 MySQL 将父子(邻接)表转换为嵌套集？

Question

过去几个小时我一直在尝试在网上找到这个问题的解决方案。我找到了很多关于如何从嵌套集合转换为邻接的例子......但很少有相反的例子。我发现的示例要么不起作用，要么使用 MySQL 过程。不幸的是，我不能为这个项目使用程序。我需要一个纯 PHP 解决方案。

我有一个使用以下邻接模型的表:

id          parent_id         category
1           0                 Books
2           0                 CD's
3           0                 Magazines
4           1                 Books/Hardcover
5           1                 Books/Large Format
6           3                 Magazines/Vintage

我想将其转换为下面的嵌套集表:

id    left    right          category
0     1       14             Root Node
1     2       7              Books
4     3       4              Books/Hardcover
5     5       6              Books/Large Format
2     8       9              CD's
3     10      13             Magazines
6     11      12             Magazines/Vintage

这是我需要的图片:

我有一个基于此论坛帖子 (http://www.sitepoint.com/forums/showthread.php?t=320444) 的伪代码的函数，但它不起作用。我得到多行具有相同的左侧值。这不应该发生。

<?php

/**

--
-- Table structure for table `adjacent_table`
--

CREATE TABLE IF NOT EXISTS `adjacent_table` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `father_id` int(11) DEFAULT NULL,
  `category` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;

--
-- Dumping data for table `adjacent_table`
--

INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
(1, 0, 'ROOT'),
(2, 1, 'Books'),
(3, 1, 'CD''s'),
(4, 1, 'Magazines'),
(5, 2, 'Hard Cover'),
(6, 2, 'Large Format'),
(7, 4, 'Vintage');

--
-- Table structure for table `nested_table`
--

CREATE TABLE IF NOT EXISTS `nested_table` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `lft` int(11) DEFAULT NULL,
  `rgt` int(11) DEFAULT NULL,
  `category` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;

*/

    mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
    mysql_select_db('DATABASE') or die(mysql_error());
    adjacent_to_nested(0);

    /**
     * adjacent_to_nested
     *
     * Reads a "adjacent model" table and converts it to a "Nested Set" table.
     * @param   integer     $i_id           Should be the id of the "root node" in the adjacent table;
     * @param   integer     $i_left         Should only be used on recursive calls.  Holds the current value for lft
     */
    function adjacent_to_nested($i_id, $i_left = 0)
    {

        // the right value of this node is the left value + 1
        $i_right = $i_left + 1;

        // get all children of this node
        $a_children = get_source_children($i_id);
        foreach  ($a_children as $a)
        {

            // recursive execution of this function for each child of this node
            // $i_right is the current right value, which is incremented by the 
            // import_from_dc_link_category method
            $i_right = adjacent_to_nested($a['id'], $i_right);

            // insert stuff into the our new "Nested Sets" table
            $s_query = "
                INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`) 
                VALUES(
                    NULL, 
                    '".$i_left."',
                    '".$i_right."',
                    '".mysql_real_escape_string($a['category'])."'
                )
            ";
            if (!mysql_query($s_query))
            {
                echo "<pre>$s_query</pre>\n";
                throw new Exception(mysql_error());  
            }
            echo "<p>$s_query</p>\n";

            // get the newly created row id
            $i_new_nested_id = mysql_insert_id();

        }

        return $i_right + 1;
    }



    /**
     * get_source_children
     *
     * Examines the "adjacent" table and finds all the immediate children of a node
     * @param   integer     $i_id           The unique id for a node in the adjacent_table table
     * @return  array                       Returns an array of results or an empty array if no results.
     */
    function get_source_children($i_id)
    {


        $a_return = array();
        $s_query = "SELECT * FROM `adjacent_table` WHERE `father_id` = '".$i_id."'";
        if (!$i_result = mysql_query($s_query))
        {
            echo "<pre>$s_query</pre>\n";
            throw new Exception(mysql_error());  
        }
        if (mysql_num_rows($i_result) > 0)
        {
            while($a = mysql_fetch_assoc($i_result))
            {
                $a_return[] = $a;
            }
        }

        return $a_return;
    }

?>

这是上面脚本的输出。

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '2', '5', 'Hard Cover' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '2', '7', 'Large Format' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '1', '8', 'Books' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '1', '10', 'CD\'s' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '10', '13', 'Vintage' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '1', '14', 'Magazines' )

INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, '0', '15', 'ROOT' )

如您所见，有多个行共享“1”的 lft 值，“2”也是如此。在嵌套集中，left 和 right 的值必须是唯一的。下面是一个如何手动为嵌套集合中的左右 ID 编号的示例:

图片来源:Gijs Van Tulder，ref article

Answer 1

我在网上找到了答案并更新了此页面上的问题以向其他人展示它是如何完成的。

更新 - 问题已解决

首先，我错误地认为需要更改源表(相邻列表格式的表)以包含源节点。不是这种情况。其次，我found a class通过 BING 就可以了。我已经为 PHP5 修改了它，并将原作者的 mysql 相关位转换为基本的 PHP。他正在使用一些数据库类。如果需要，您可以稍后将它们转换为您自己的数据库抽象类。

很明显，如果你的“源表”有其他列你想移动到嵌套集合表，你将不得不调整下面类中的write方法。

希望这会在将来避免其他人遇到同样的问题。

<?php

/**


--
-- Table structure for table `adjacent_table`
--

DROP TABLE IF EXISTS `adjacent_table`;
CREATE TABLE IF NOT EXISTS `adjacent_table` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `father_id` int(11) DEFAULT NULL,
  `category` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;

--
-- Dumping data for table `adjacent_table`
--

INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
(1, 0, 'Books'),
(2, 0, 'CD''s'),
(3, 0, 'Magazines'),
(4, 1, 'Hard Cover'),
(5, 1, 'Large Format'),
(6, 3, 'Vintage');

--
-- Table structure for table `nested_table`
--

DROP TABLE IF EXISTS `nested_table`;
CREATE TABLE IF NOT EXISTS `nested_table` (
  `lft` int(11) NOT NULL DEFAULT '0',
  `rgt` int(11) DEFAULT NULL,
  `id` int(11) DEFAULT NULL,
  `category` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`lft`),
  UNIQUE KEY `id` (`id`),
  UNIQUE KEY `rgt` (`rgt`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

*/

    /**
     * @class   tree_transformer
     * @author  Paul Houle, Matthew Toledo
     * @created 2008-11-04
     * @url     http://gen5.info/q/2008/11/04/nested-sets-php-verb-objects-and-noun-objects/
     */
    class tree_transformer 
    {

        private $i_count;
        private $a_link;

        public function __construct($a_link) 
        {
            if(!is_array($a_link)) throw new Exception("First parameter should be an array. Instead, it was type '".gettype($a_link)."'");
            $this->i_count = 1;
            $this->a_link= $a_link;
        }

        public function traverse($i_id) 
        {
            $i_lft = $this->i_count;
            $this->i_count++;

            $a_kid = $this->get_children($i_id);
            if ($a_kid) 
            {
                foreach($a_kid as $a_child) 
                {
                    $this->traverse($a_child);
                }
            }
            $i_rgt=$this->i_count;
            $this->i_count++;
            $this->write($i_lft,$i_rgt,$i_id);
        }   

        private function get_children($i_id) 
        {
            return $this->a_link[$i_id];
        }

        private function write($i_lft,$i_rgt,$i_id) 
        {

            // fetch the source column
            $s_query = "SELECT * FROM `adjacent_table` WHERE `id`  = '".$i_id."'";
            if (!$i_result = mysql_query($s_query))
            {
                echo "<pre>$s_query</pre>\n";
                throw new Exception(mysql_error());  
            }
            $a_source = array();
            if (mysql_num_rows($i_result))
            {
                $a_source = mysql_fetch_assoc($i_result);
            }

            // root node?  label it unless already labeled in source table
            if (1 == $i_lft && empty($a_source['category']))
            {
                $a_source['category'] = 'ROOT';
            }

            // insert into the new nested tree table
            // use mysql_real_escape_string because one value "CD's"  has a single '
            $s_query = "
                INSERT INTO `nested_table`
                (`id`,`lft`,`rgt`,`category`)
                VALUES (
                    '".$i_id."',
                    '".$i_lft."',
                    '".$i_rgt."',
                    '".mysql_real_escape_string($a_source['category'])."'
                )
            ";
            if (!$i_result = mysql_query($s_query))
            {
                echo "<pre>$s_query</pre>\n";
                throw new Exception(mysql_error());  
            }
            else
            {
                // success:  provide feedback
                echo "<p>$s_query</p>\n";
            }
        }
    }

    mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
    mysql_select_db('DATABASE') or die(mysql_error());

    // build a complete copy of the adjacency table in ram
    $s_query = "SELECT `id`,`father_id` FROM `adjacent_table`";
    $i_result = mysql_query($s_query);
    $a_rows = array();
    while ($a_rows[] = mysql_fetch_assoc($i_result));
    $a_link = array();
    foreach($a_rows as $a_row) 
    {
        $i_father_id = $a_row['father_id'];
        $i_child_id = $a_row['id'];
        if (!array_key_exists($i_father_id,$a_link)) 
        {
            $a_link[$i_father_id]=array();
        }
        $a_link[$i_father_id][]=$i_child_id;
    }

    $o_tree_transformer = new tree_transformer($a_link);
    $o_tree_transformer->traverse(0);

?> 

这是输出:

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '4', '3', '4', 'Hard Cover' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '5', '5', '6', 'Large Format' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '1', '2', '7', 'Books' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '2', '8', '9', 'CD\'s' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '6', '11', '12', 'Vintage' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '3', '10', '13', 'Magazines' )

INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '0', '1', '14', 'ROOT' )