% Section 2.3.2, Program D / Subroutine for Tree Construction
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 3rd
% Refactored    2012 April 9th
% Refined       2012 April 19th
% Refined       2012 May   08th
%
% Dependency:
% - module AGC
%
% This proposal focuses only on the subroutine for tree construction of
% Program D as specified in TAoCP, V1e3, page 340. The other
% subroutines of the aforementioned Program D will be aggregated later
% in order to have the complete program. The idea is just to test each
% subroutine in a not too lengthly readable mms file. Thus, a good
% proportion of lines of codes here are test related.
%
% The Data Structure for one node is:
% 
%                 >|<-----OCTA----->|<
%                  +----------------+ 
%                  | RLINK/63 RTAG/1| BA+0
%                  +----------------+
%                  | LLINK/63 LTAG/1| BA+8
%                  +----------------+
%                  |        X       | BA+16
%                  +----------------+
%
% Notes:
% - {R|L}LINKs are assumed to be correctly set from the start
% - in the scope of the DIFF program, X will store INFO/60 and TYPE/4,
%   however this is irrelevant for this TREE algorithm because it
%   doesn't add any process to that data
% 

        
% Tree Construction Function
%     TREE(x,U=NULL,V=NULL):W
%
% Calling Sequence:
%     $1 <- info to be stored
%     $2 <- U or NULL
%     $3 <- W or NULL
%     PUSHJ $0,TREE
%
% Exit Conditions:
%     Address of newly created tree is returned.
%
        PREFIX TREE:
        
dRLINK  IS 8*0
dLLINK  IS 8*1
dX      IS 8*2
dNODE   IS 8*3
        
x       IS $0
U       IS $1
V       IS $2
W       IS $3
TW      IS $4  % Threaded W
t       IS $5

:TREE0  SET   U,0                  % TREE(info)
:TREE1  SET   V,0                  % TREE(info,U)
:TREE2  GET   t,:rJ
        PUSHJ t+1,:AGC:A
        SET   W,t+1                % W <= AVAIL
        PUT   :rJ,t
        STCO  0,W,dRLINK           % Initialize node data
        STCO  0,W,dLLINK
        STOU  x,W,dX
        BZ    U,9F                 % leaf?  
        STO   U,W,dLLINK
        XOR   TW,W,1               % thread it
        BZ    V,1F                 % node+leaf?
        STO   V,U,dRLINK           % RLINK(U) <- V
        STO   TW,V,dRLINK          % RLINK(V) <- W (as thread)
        JMP   9F
1H      STO   TW,U,dRLINK          % RLINK(U) <- W (as thread)
9H      SET   $0,W
        POP   1,0
        
        PREFIX :