Device trees, or Implementing recursive tree descent in Priority (part three)

To recap, this series of blog entries is discussing device trees and how to turn simple one-level (father:son) data into hierarchical  (grandparent: parents: children, etc) data. Once again, here is the tree that I am using as the example:

Father	Son
A	B1
A	B2
A	B3
B1	B1C1
B1	B1C2
B2	B2C1
B2	B2C2
B3	B3C1
B3	B3C2
B1C1	B1C1D1

In the previous installment, I showed how one can write code to descend through the tree; the devices accessed were B1, B1C1 and B1C1D1. Now the code has come to an impasse and has to backtrack (i.e. ascend back up the tree) in order to continue. When :NODE is equal to B1C1D1,the following query will fail and so control passes to LABEL 20.

LABEL 10;                                                           
SELECT SON INTO :SON                                                
FROM TEST_SERNTREE                                                  
WHERE FATHER = :NODE                                                  
AND USER = 0;                                                       
GOTO 20 WHERE :RETVAL <= 0; 
.
.
.
LABEL 20;                                                                                               
DELETE FROM STACK2 WHERE ELEMENT = :NODE;                                                                                    
GOTO 30 WHERE NOT EXISTS (SELECT 1 FROM STACK2 WHERE ELEMENT > 0);  
SELECT MAX (TYPE) INTO :MAX FROM STACK2;                            
SELECT ELEMENT INTO :NODE FROM STACK2 WHERE TYPE = :MAX;            
:LEVEL = :MAX;                                                      
LOOP 10;                                                            
LABEL 30;                      

This is the kludgey part of the code. One of the final lines prior to LABEL 20 sets :NODE equal to :SON (not shown) before the code loops back to LABEL 10. So at the first statement after LABEL 20, the current device (B1C1D1) is removed from STACK2, the table that is serving as the recursion's memory. Then there is a check that there is still data in STACK2 - this is the terminating condition. Following this, the maximal value of TYPE  is obtained - at this stage, this should be 3. Having this value enables the value of the final element in STACK2 to be copied into :NODE (or as they say in computer science circles, the value is popped off the stack). This should be B1C1. As there are no more sons of this device, LABEL 20 will be reached again and B1 popped off the stack. The code at LABEL 10 will ensure that the new value of :SON will be B1C2.

Eventually the final value (:ANCESTOR) will be deleted from STACK2 and so the code will jump to LABEL 30. At this stage, if everything has gone correctly, STACK4 will look like the following

KEY	INTDATA	INTDATA2
1	B1	2
2	B1C1	3
3	B1C1D1	4
4	B1C2	3
5	B2	2
6	B2C1	3
7	B2C2	3
8	B3	2
9	B3C1	3
10	B3C2	3

So at this stage, we have indeed achieved the goal of turning simple one-level data into hierarchical data. This is equivalent to the output of the SONRAW program. But there is one more detail that needs to be added: B1 should be displayed with the level 1, B1C1 as 1.1, B1C1D1 as 1.1.1, B1C2 as 1.2, etc. Fortunately there is no need to reinvent the wheel: I figured out how to do this with SONRAW data here. Again, this is a recursive requirement, and is turned into an iterative solution by means of a stack, again STACK2.

Below is a screen shot from Priority with the tree displayed with the levels.

 

---

Since writing these blog entries, I've been having second thoughts about some of the code. There is definitely no need for the field 'ANCESTOR' in the table TEST_SERNTREE. In the procedure that displays the tree, there is no need to access the 'USER' field either. STACK has to be given an alias in the form trigger code otherwise this doesn't work (presumably there is use of STACK somewhere else in the SERNTREE form. The first part of the procedure is now

LINK STACK4 TO :$.STK;
ERRMSG 1 WHERE :RETVAL <= 0;
LINK STACK2 TO :$.ST2;
ERRMSG 1 WHERE :RETVAL <= 0;
LINK STACK SST TO :$.ST0;
ERRMSG 1 WHERE :RETVAL <= 0;
:LINE = 0;
:LEVEL = 1;
INSERT INTO STACK2 (ELEMENT, TYPE)
VALUES (:ANCESTOR, 1);
:NODE = :ANCESTOR;
/***************************************************/
LABEL 10;
SELECT SON INTO :SON
FROM GLOB_SERNTREE
WHERE FATHER = :NODE
AND NOT EXISTS (SELECT 1 FROM STACK SST
WHERE SST.ELEMENT = GLOB_SERNTREE.SON 
GOTO 20 WHERE :RETVAL <= 0;
INSERT INTO STACK2 (ELEMENT, TYPE)
VALUES (:SON, :LEVEL + 1);
INSERT INTO STACK SST (ELEMENT) VALUES (:SON);
:LINE = :LINE + 1;
INSERT INTO STACK4 (KEY, INTDATA, INTDATA2)
VALUES (:LINE, :SON, :LEVEL + 1);
:NODE = :SON;
:LEVEL = :LEVEL + 1;
LOOP 10;