% Section 2.3.2, Exo.13 Program D / Copy Right Threaded Binary Tree
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 5th
% Refactored    2012 April 9th
% Refined       2012 April 19th
% Refined       2012 May   08th
%
% The Data Structure for one node is:
% 
%                 >|<-----OCTA----->|<
%                  +----------------+ 
%                  | RLINK/63 RTAG/1| BA+0
%                  +----------------+
%                  | LLINK/63 LTAG/1| BA+8
%                  +----------------+
%                  |        X       | BA+16
%                  +----------------+
%
% Notes:
% - octa-byte alignment when addressing allows storage of flags in addr
% - the content of X is irrelevant to this algorithm
%

        
% Copy a Right Threaded Binary Tree
%     COPY(from:node):node
%
% Calling Sequence:
%     $1 <- address of root node of tree to copy
%     PUSHJ $0,COPYRTBT
%
% Exit Conditions:
%     return address of root node of copy
%

        PREFIX COPYRTBT:

dRLINK  IS 8*0
dLLINK  IS 8*1
dX      IS 8*2
dNODE   IS 8*3
        
from    IS $0
copy    IS $1
P       IS $2
Q       IS $3
R       IS $4
t       IS $5              
:COPYRTBT IS @
        BZ    from,9F     % input check
        SET   P,from
        
        GET   t,:rJ
        PUSHJ t+1,:AGC:A
        SET   Q,t+1       % Q <= AVAIL
        PUT   :rJ,t

        STCO  0,Q,dRLINK  % thread to NULL
        STCO  0,Q,dLLINK
        
        SET   copy,Q
        
        % Prepare Right Path
C2      LDOU  t,P,dRLINK
        BOD   t,C3        % it's a right thread, no new node to setup
        GET   t,:rJ       % else create one
        PUSHJ t+1,:AGC:A
        SET   R,t+1       % R <= AVAIL
        PUT   :rJ,t
        LDOU  t,Q,dRLINK  % propagate down the parent's right thread
        STOU  t,R,dRLINK
        STOU  R,Q,dRLINK
        % Visit Node
C3      LDOU  t,P,dX
        STOU  t,Q,dX
        % Prepare Left Path
C4      LDOU  t,P,dLLINK
        BZ    t,4F        % left path empty, so advance to next h-link
        GET   t,:rJ       % else create left path in copy...
        PUSHJ t+1,:AGC:A
        SET   R,t+1       % R <= AVAIL
        PUT   :rJ,t
        STOU  R,Q,dLLINK
        ADDU  t,Q,1       % ...right threading to parent in copy...
        STOU  t,R,dRLINK
        SET   Q,R         % ...and preorder move on both sides
        LDOU  t,P,dLLINK
        SET   P,t
        JMP   C2
4H      STCO  0,Q,dLLINK
        % Advance
C5      LDOU  P,P,dRLINK
        LDOU  Q,Q,dRLINK
        BOD   Q,C5        % go upstream like a salmon, along the thread
        % Done: the last thread is not really a thread, links to NULL
        BNZ   Q,C2
        SET   $0,copy
9H      POP   1,0

        PREFIX :