Re: Adjacency list to Nested set model statement
Date: Thu, 28 Feb 2002 00:40:44 -0800
Message-ID: <u7rr8d15fc76df_at_news.supernews.com>
In article <c0d87ec0.0202271438.12a87592_at_posting.google.com>, "--CELKO--" <71062.1056_at_compuserve.com> wrote:
> Here is the code; can you make it better?
>
> /* Stack holds the nested sets model; it is the push down stack for the
> tree traversal. Would an index or key help here? */
>
>
Do you really need a stack here? Traversing a tree consists of iteratively taking one of three moves, in this order of priority: down, right, up. Given the last node visited, it seems simple enough to figure out what the next one should be.
Maybe something like this:
create table node(
node_id integer primary key, -- unique id parent_id integer null, -- null only at root nodenum integer null -- traversal ordinal, initially null maxchild null -- the max. nodenum for subtree )
/*
The traversal order will be depth first, ordering siblings by node_id.
Each node will be given a nodenum when first encountered (on the way down/across). On the way up, nodenum's are already set, but maxchild can be brought up from below (although it's redundant IMHO).
*/
declare _at_last_node_visited integer;
declare _at_last_nodenum integer;
set _at_last_node_visited = @root_node -- assume this is passed in
set _at_last_nodenum = 1
update node set nodenum = 1 where node_id = _at_root_node
set _at_did_something = 1;
while ( _at_did_something = 1 ) /* 0 if no more moves */ begin
set _at_did_something = 0
/* down - look for unvisited child */ if exists (select * from tree where parent_id = _at_last_node_visited
and nodenum is null ) begin set _at_did_something = 1; /* get leftmost child */ set _at_next_node = (select min(node_id) from node c where c.parent_id = _at_last_nodenum ) set _at_last_nodenum = @last_nodenum + 1; update node set nodenum = _at_last_nodenum where node_id = _at_next_node; set _at_last_node_visited = @next_node; end /* down */
/* across - look for right sibling */ else if exists (select * from node c, node c2
where c.node_id = _at_last_node_visited and c.parent_id = c2.parent_id and c2.node_id > c.node_id ) begin set _at_did_something = 1; set _at_next_node = (select min(c2.node_id) from node c, node c2 where c.node_id = _at_last_node_visited and c.parent_id = c2.parent_id and c2.node_id > c.node_id ) set _at_last_nodenum = @last_nodenum + 1; update node set nodenum = _at_last_nodenum where node_id = _at_next_node; set _at_last_node_visited = @next_node; end /* across */ /* up - set maxchild */ else if exists (select * from node c where c.node_id = _at_last_node_visited and c.parent_id is not null ) begin set _at_did_something = 1; set _at_next_node = (select parent_id from node c where c.node_id = _at_last_node_visited and c.parent_id is not null ) /* don't increment _at_last_nodenum */ /* set maxchild for node; nodenum should already be set */ update node set maxchild = _at_last_nodenum where node_id = _at_next_node; set _at_last_node_visited = @next_node; end /* up */
end /* while */
This is pretty brutal, untested coding, but I think the idea is visible somewhere in there. I could probably get it a lot cleaner with a bit of rework, but I'm sleepy.
Feedback *is* appreciated.
Thanks,
Kendall Received on Thu Feb 28 2002 - 09:40:44 CET