/*

nodecnt, calcdfs -
	procedures to set
	depth-first search sequence numbers
	in parallel, or at least not in
	one-node-at-a-time procedural code.

Author:	Kendall Willets (kendall at willets org)
	http://willets.org

Revision History:

	3/8/2	khw	created

nodecnt sets desc_count for each node - the number
of descendants below a node, including the node itself.
Usage:  exec nodecnt

calcdfs uses desc_count to find each node's depth first search
nodenum.  Usage:  exec calcdfs( root_id )

These could be one procedure but it was useful to run one at a time
 and check intermediate results.

The update statement in the calcdfs loop is kludgey - would like to
use a join to restrict update (move p out of subquery), but Oracle
seems to have other ideas.

*/

/* base table */
drop table tree;

create table tree(
 node_id 	integer 	primary key,
 parent_id 	integer 	null,
 desc_count 	integer 	null,
 ready_flg 	integer 	null,
 nodenum 	integer 	null );

/* sample tree, root_id = 1 */
/* id's are in dfs order - should match nodenum */
insert into tree(node_id, parent_id) values (1, null);
insert into tree(node_id, parent_id) values (2,1);
insert into tree(node_id, parent_id) values (3,1);
insert into tree(node_id, parent_id) values (4,3);
insert into tree(node_id, parent_id) values (5,3);
insert into tree(node_id, parent_id) values (6,1);
insert into tree(node_id, parent_id) values (7,6);

create or replace procedure nodecnt as
begin

update tree set desc_count = NULL;

/* set leaf nodes first */
update tree p set
	desc_count = 1
where not exists (select * from tree c
		  where c.parent_id = p.node_id);

loop

  /* sum counts from children to parent
  NULL result signifies a null in one or more child nodes -
   try again next loop
  */
 update tree p
 set (desc_count) =
	(select 1 + sum(c.desc_count)
	  from tree c
	  where p.node_id = c.parent_id )
 where p.desc_count is NULL;

 exit when( sql%rowcount = 0 );  /* done when root is reached */

end loop;

end;  /* nodecnt */
/

create or replace procedure calcdfs( root_id in integer)
as
begin
update tree set nodenum = NULL;

/* start with root's nodenum = 1 */
update tree set nodenum = 1 where node_id = root_id;

loop

  /* loop:  for parents with nodenum set, calculate each
  child node's nodenum using parent nodenum
   and left sibling desc_counts

   null result means parent not set yet

   */
  update tree c
  set nodenum =
	(select 1 + min(p.nodenum) +
		sum(s.desc_count)  /* sibling counts */
		- c.desc_count     /* included c - take out */
	 from tree s, tree p
	 where p.node_id =  s.parent_id
	 and   p.node_id =  c.parent_id
	 and c.parent_id = s.parent_id
	 and   s.node_id <= c.node_id  /* includes c so group not empty */
	)
  where c.nodenum is NULL;

  exit when( sql%rowcount = 0 );  /* done when no more rows updated */

end loop;
end;  /* calcdfs */
/