Regenerate a Nested Set using parent_id structure

Hello,

I've got a Nested Set structure in MySQL 4 here with
- id
- lft
- rgt
- parent_id
- root_id

I wrote some test scripts and i discovered that the Nested Set (the
structure with lft and rgt nodes) is broken, there are some duplicate
nodes and other really bad stuff.

Luckily, the dude who developed the system has a parent_id-Structure
in the database too, and I'm pretty sure that the parent_id-
relationships are correct.

So, now my question: I'd need a Query or a PHP Script to generate a
correct node structure out of the parent_id-relationships. Any tips or
links?

Thanks guys!

Regards

Re: Regenerate a Nested Set using parent_id structure

This from the guru himself (see http://tinyurl.com/2ufnrb):

To convert an adjacency list model into a nested set model, use a push
down stack algorithm. Assume that we have these tables:

-- Tree holds the adjacency model

CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
boss CHAR(10));

INSERT INTO Tree
SELECT emp, boss FROM Personnel;

-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
emp CHAR(10) NOT NULL,
lft INTEGER,
rgt INTEGER);

BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;

SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;

INSERT INTO Stack
SELECT 1, emp, 1, NULL
FROM Tree
WHERE boss IS NULL;

DELETE FROM Tree
WHERE boss IS NULL;

WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
FROM Stack AS S1, Tree AS T1
WHERE S1.emp = T1.boss
AND S1.stack_top = current_top)
THEN
BEGIN -- push when top has subordinates, set lft value
INSERT INTO Stack
SELECT (current_top + 1), MIN(T1.emp), counter, NULL
FROM Stack AS S1, Tree AS T1
WHERE S1.emp = T1.boss
AND S1.stack_top = current_top;

DELETE FROM Tree
WHERE emp = (SELECT emp
FROM Stack
WHERE stack_top = current_top + 1);

SET counter = counter + 1;
SET current_top = current_top + 1;
END
ELSE
BEGIN -- pop the stack and set rgt value
UPDATE Stack
SET rgt = counter,
stack_top = -stack_top -- pops the stack
WHERE stack_top = current_top
SET counter = counter + 1;
SET current_top = current_top - 1;
END IF;
END LOOP;
END;

HIH