debug    equ   1
move$score     equ                     0
move$leftson   equ                     1
move$rightson  equ                     2
move$distance  equ                     3
         org   $1000
         page  Leftist Tree Implementation
* Discussion about Leftist Trees, summarized from Knuth, Vol 3, pages 150-152.
*    An efficient ways to represent priority queues as linked binary trees
*    requires two link fields and a small count field in every record,
*    and has the following advantages:
*    1) When priority queue is being treated as a stack (IDB: insert a largest
*       element, then delete the largest element), the insert/delete times
*       are a constant.
*    2) It is possible to merge two disjoint priority queues, having a
*       total of N elements, in O(log N) steps.
*
* Each node contains a KEY field, a DIST field, and two link fields LEFT and
*    RIGHT.  The DIST field is always set equal to the length of the shortest
*    path from that node to a leaf, with DIST(NIL) defined as 0.
*    Assuming that KEY(NIL)=-infinity, the following invariants are true:
*      KEY(P)>=KEY(LEFT(P)) and KEY(P)>=KEY(RIGHT(P))
*      DIST(P)=1+min(DIST(LEFT(P)),DIST(RIGHT(P)))
*      DIST(LEFT(P))>=DIST(RIGHT(P))
*    Thus the root of the tree has the largest key.
*    It is also the case that the tree tends to "lean" to the left, thus
*    the name "leftist tree".
*    An implication of DIST(P)=n is that there are at least 2^n leaf nodes
*    below P.
*
*    To delete the node with the largest key, we need merely merge its
*    two subtrees.  Merging two trees, P and Q, is conceptually simple:
*    If KEY(P)>=KEY(Q), we take P as the root and merge Q with P's right
*    subtree; then dist(P) is updated, and LEFT(P) is interchanged with
*    RIGHT(P) if necessary.  The algorithm is shown below:
*
* Stolen outright from Knuth, vol 3, page 619
*   "Let P, Q point to the given priority queue; for brevity, the following
*    algorithm uses the convention that DIST(NIL)=0.
*    M1. [Initialize.] Set R:=NIL.
*    M2. [List Merge.] If Q=NIL, set D:=DIST(P) and goto M3.
*        If P=NIL, set P:=Q, D:=DIST(P), and goto M3.
*        If KEY(P)>=KEY(Q), set T:=RIGHT(P),RIGHT(P):=R,R:=P,P:=T, goto M2.
*        If KEY(P)<KEY(Q), set T:=RIGHT(Q),RIGHT(Q):=R,R:=Q,Q:=T, goto M2.
*        (This step essentially merges the two "right lists" of the given
*         trees, temporarily inserting upward pointers into the RIGHT fields.)
*    M3. [Done?] If R=NIL, terminate the algorithm, P points to the answer.
*    M4. [Fix DISTs.] Set Q:=RIGHT(R).
*        If DIST(LEFT(R))<D then D:=DIST(LEFT(R))+1,RIGHT(R):=LEFT(R),
*                                LEFT(R):=P
*                           else D:=D+1,RIGHT(R):=P fi
*        DIST(R):=D,P:=R,R:=Q.
*        Goto M3.
*
*    To insert a node in the tree, treat it like a tree, and apply the
*    merge process above.  Specialized code can handle the frequent
*    conditions of null subtrees, making the insertion process somewhat
*    more efficient.
*
*    What we do in the code below is to bind P,Q and R to various
*    combinations of X,Y and U (leading to 6 possible bindings for
*    each step in the above algorithm).  This is done primarily
*    because Knuth's algorithm does lots of register shuffling;
*    by simply jumping to another piece of code with different
*    register bindings, we get the effect of register shuffling
*    at zero time cost (and you know how sensitive I am to code speed).
*    We also include with each set of bindings some conditions which
*    are known to be true, (like the status of null subtrees which
*    occurs frequently during the insertion process), which increases
*    the number of states for each step even further.  Fortunately,
*    simplifications and unused cases then remove much of the code.
         page
DeleteBestMove ; Remove best move node from move list (Y), return in (X)
         ldx   ,y                      fetch best node from tree
         beq   DeleteBestMoveNone      b/ no move to delete
         if    debug
         bsr   DeleteBestMove1         do the deletion
         bsr   verifysonszeroaddressok check node at (X) is suitably reset
         rts
DeleteBestMove1
         fin   debug
         ldu   move$rightson,x         see if right son exists
         bne   DeleteBestMoveR         b/ right son exists (less likely than left son existing)
;        lda   #1                      set distance to sons to unity
;        sta   move$distance,x         (RIGHT(P)=NIL --> DIST(P)=1 !
         ldu   move$leftson,x          no right son, left subtree becomes remaining tree
         stu   ,y                      remember pointer to rest of tree
         beq   DeleteBestMoveRts       b/ no "rest of tree" (V bit reset!)
         ldd   #0                      zero left son pointer of best node
         std   move$leftson,x          (resets V bit!)
DeleteBestMoveRts
         rts                           and exit

DeleteBestMoveR ; Right son exists.
; Because distance(left(X))>=distance(right(X)), and right son exists,
; then left son MUST exist.
; Merge two sub-trees to get result of deleting root.
         pshs  x,y                     save result and list pointer
         ldy   #0                      (M1: R:=0 in Knuth's algorithm)
         sty   move$leftson,x          make result son be canonical
         sty   move$rightson,x         by zeroing both sons
         ldx   move$leftson,x          fetch left sub tree
         bsr   MergeLeftistTreesM2.PuQxRy3 go merge two subtrees into one
         puls  x,y                     restore result and list pointer
         stu   ,y                      save pointer to merged subtrees
         lda   #1                      set distance to sons to unity (resets V bit)
         sta   move$distance,x
;        clv                           note that result is returned
         rts                           and exit

DeleteBestMoveNone ; no best move to delete
         sev                           signal "No move deleted" to caller
         rts
         page
InsertMoveIntoList ; Add Move node (X) to move list (Y)
;        Assert: move$leftson(X)=0
;        Assert: move$rightson(X)=0
;        Assert: move$distance(X)=1
         if    debug
         lda   move$distance,x         check that distance is unity
         cmpa  #1
         beq   *+3
         swi                           distance is wrong for singleton node
         bsr   verifysonszeroaddressok check node at (X) for pre-conditions
         fin   debug
         ldu   ,y                      fetch pointer to top node in move list
         beq   InsertMoveIntoList0     b/ move list is empty, handle special case
         pshs  y                       save pointer to move list storage slot
         bsr   MergeLeftistTreesM1.PuQx1 insert singleton into leftist tree
         stu   [,s++]                  update pointer to move list
         rts                           and exit

InsertMoveIntoList0 ; Add Move node (X) to empty move list (Y)
         stx   ,y                      make move list point to singleton node
         rts                           and exit

; Note on implementation of MergeLeftistTrees
; A label of form ...Mn.mPxQyRzd means:
;   "doing step [Mn] of Knuth's algorithm"
;   "this code is the m'th version of step [Mn], and is distinguished by:"
;   "P is in index register 'x'"
;   "Q is in index register 'y'"
;   "R is in index register 'z'"
;   "If a variable P, Q or R is not mentioned, it is not used/allocated at this instant."
;   "d is a digit splitting each of [Mn] into substates depending
;    on known state of registers (i.e., P=0, etc.)"

MergeLeftistTreesM1.PuQx1 ; Insert move (X) in non-empty tree with top node (U)
; Result of merging two trees is returned in (U)
; Assert: P<>0, Q<>0, DIST(Q)=1, LEFT(Q)=0, RIGHT(Q)=0
         ldy   #0                      set R:=0
;MergeLeftistTreesM2.1PuQx1
         ; IF Q=0 (false) THEN ...
         ; IF P=0 (false) THEN ...
         ldd   move$score,u            fetch KEY(P)
         subd  move$score,x            compare KEY(P) to KEY(Q)
         bgt   MergeLeftistTreesM2.PuQxRy3a b/ KEY(P)>KEY(Q), R=0
         ; Fast path for inserting single node with .ge. value into tree
         stx   move$leftson,u          KEY(P)<=KEY(Q), LEFT(Q):=P
         rts                           DIST(Q):=1, then exit
; Note that when inserting a single node into tree, we know more than if
; we are merging multiple lists, and therefore algorithm can run faster.
; Is it worth coding to take advantage of this ?
         page
;MergeLeftistTreesM2.PuQxRy0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpx  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PuQxRy1 b/ Q<>0
;        lda   move$distance,u         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PuRy1

;MergeLeftistTreesM2.PuQxRy1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpu  #0                      IF P=0...
;        bne   MergeLeftistTreesM2.PuQxRy3  b/ P<>0
;MergeLeftistTreesM2.PuQxRy2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in x, Q is in u)
;        lda   move$distance,x         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PxRy1 GOTO M3

MergeLeftistTreesM2.PuQxRy3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,u            fetch KEY(P)
         subd  move$score,x            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PuQxRy5 b/ KEY(P)<KEY(Q)
MergeLeftistTreesM2.PuQxRy3a ; entry point from MergeLeftistTreesM1.PuQx1
         ldd   move$rightson,u         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PuQxRy4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         sty   move$rightson,u         RIGHT(P):=R
         ; R:=P (rebind registers so R is in u, P is in y)
         tfr   d,y                     P:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PyQxRu3 GOTO M2

MergetLeftistTreesM2.PuQxRy4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         sty   move$rightson,u         RIGHT(P):=R
         ; R:=P (rebind registers), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in x, Q is in u)
         lda   move$distance,x         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PxRy1 GOTO M3

MergeLeftistTreesM2.PuQxRy5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,x         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PuQxRy6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         sty   move$rightson,x         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in x, Q is in y)
         tfr   d,y                     Q:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PuQyRx3 GOTO M2

MergetLeftistTreesM2.PuQxRy6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         sty   move$rightson,x         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in x, Q is in y), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,u         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM3.PuRx1 GOTO M2
         page
;MergeLeftistTreesM2.PyQxRu0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpx  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PyQxRu1 b/ Q<>0
;        lda   move$distance,y         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PyRu1

;MergeLeftistTreesM2.PyQxRu1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpy  #0                      IF P=0...
;         bne   MergeLeftistTreesM2.PyQxRu3  b/ P<>0
;MergeLeftistTreesM2.PyQxRu2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in x, Q is in y)
;        lda   move$distance,x         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PxRu1 GOTO M3

MergeLeftistTreesM2.PyQxRu3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,y            fetch KEY(P)
         subd  move$score,x            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PyQxRu5 b/ KEY(P)<KEY(Q)
         ldd   move$rightson,y         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PyQxRu4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         stu   move$rightson,y         RIGHT(P):=R
         ; R:=P (rebind registers so R is in y, P is in u)
         tfr   d,u                     P:=T
         bra   MergeLeftistTreesM2.PuQxRy3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PyQxRu4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stu   move$rightson,y         RIGHT(P):=R
         ; R:=P (rebind registers so R is in y, P is in u), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in x, Q is in u)
         lda   move$distance,x         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PxRy1 GOTO M3

MergeLeftistTreesM2.PyQxRu5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,x         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PyQxRu6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         stu   move$rightson,x         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in x, Q is in u)
         tfr   d,u                     Q:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PyQuRx3 GOTO M2

MergetLeftistTreesM2.PyQxRu6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stu   move$rightson,x         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in x, Q is in u), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,y         D:=DIST(P)
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PyRx1 GOTO M2
         page
;MergeLeftistTreesM2.PuQyRx0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpy  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PuQyRx1 b/ Q<>0
;        lda   move$distance,u         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PuRx1

;MergeLeftistTreesM2.PuQyRx1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpu  #0                      IF P=0...
;        bne   MergeLeftistTreesM2.PuQyRx3  b/ P<>0
;MergeLeftistTreesM2.PuQyRx2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in y, Q is in u)
;        lda   move$distance,y         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PyRx1 GOTO M3

MergeLeftistTreesM2.PuQyRx3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,u            fetch KEY(P)
         subd  move$score,y            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PuQyRx5 b/ KEY(P)<KEY(Q)
         ldd   move$rightson,u         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PuQyRx4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         stx   move$rightson,u         RIGHT(P):=R
         ; R:=P (rebind registers so R is in u, P is in x)
         tfr   d,x                     P:=T
         bra   MergeLeftistTreesM2.PxQyRu3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PuQyRx4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stx   move$rightson,u         RIGHT(P):=R
         ; R:=P (rebind registers so R is in u, P is in x), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in y, Q is in x)
         lda   move$distance,y         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PyRu1 GOTO M3

MergeLeftistTreesM2.PuQyRx5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,y         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PuQyRx6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         stx   move$rightson,y         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in y, Q is in x)
         tfr   d,x                     Q:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PuQxRy3 GOTO M2

MergetLeftistTreesM2.PuQyRx6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stx   move$rightson,y         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in y, Q is in x), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,u         D:=DIST(P)
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PuRy1 GOTO M2
         page
;MergeLeftistTreesM2.PyQuRx0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpu  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PyQuRx1 b/ Q<>0
;        lda   move$distance,y         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PyRx1

;MergeLeftistTreesM2.PyQuRx1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpy  #0                      IF P=0...
;        bne   MergeLeftistTreesM2.PyQuRx3  b/ P<>0
;MergeLeftistTreesM2.PyQuRx2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in u, Q is in y)
;        lda   move$distance,u         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PuRx1 GOTO M3

MergeLeftistTreesM2.PyQuRx3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,y            fetch KEY(P)
         subd  move$score,u            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PyQuRx5 b/ KEY(P)<KEY(Q)
         ldd   move$rightson,y         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PyQuRx4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         stx   move$rightson,y         RIGHT(P):=R
         ; R:=P (rebind registers so R is in y, P is in x)
         tfr   d,x                     P:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PxQuRy3 GOTO M2

MergetLeftistTreesM2.PyQuRx4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stx   move$rightson,y         RIGHT(P):=R
         ; R:=P (rebind registers so R is in y, P is in x), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in u, Q is in x)
         lda   move$distance,x         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PuRy1 GOTO M3

MergeLeftistTreesM2.PyQuRx5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,u         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PyQuRx6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         stx   move$rightson,u         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in u, Q is in x)
         tfr   d,x                     Q:=T
         bra   MergeLeftistTreesM2.PyQxRu3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PyQuRx6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stx   move$rightson,u         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in u, Q is in x), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,y         D:=DIST(P)
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PyRu1 GOTO M2
         page
;MergeLeftistTreesM2.PxQyRu0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpy  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PxQyRu1 b/ Q<>0
;        lda   move$distance,x         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PxRu1

;MergeLeftistTreesM2.PxQyRu1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpx  #0                      IF P=0...
;        bne   MergeLeftistTreesM2.PxQyRu3  b/ P<>0
;MergeLeftistTreesM2.PxQyRu2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in y, Q is in x)
;        lda   move$distance,y         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PyRu1 GOTO M3

MergeLeftistTreesM2.PxQyRu3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,x            fetch KEY(P)
         subd  move$score,y            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PxQyRu5 b/ KEY(P)<KEY(Q)
         ldd   move$rightson,x         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PxQyRu4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         stu   move$rightson,x         RIGHT(P):=R
         ; R:=P (rebind registers so R is in x, P is in u)
         tfr   d,u                     P:=T
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0
         bra   MergeLeftistTreesM2.PuQyRx3 GOTO M2

MergetLeftistTreesM2.PxQyRu4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stu   move$rightson,x         RIGHT(P):=R
         ; R:=P (rebind registers so R is in x, P is in u), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in y, Q is in u)
         lda   move$distance,y         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PyRx1 GOTO M3

MergeLeftistTreesM2.PxQyRu5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,y         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PxQyRu6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         stu   move$rightson,y         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in y, Q is in u)
         tfr   d,u                     Q:=T
         bra   MergeLeftistTreesM2.PxQuRy3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PxQyRu6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         stu   move$rightson,y         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in y, Q is in u), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,x         D:=DIST(P)
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PxRy1 GOTO M2
         page
;MergeLeftistTreesM2.PxQuRy0 ; step M2 of Knuth
; Assert P=?, Q=?, R<>0, RIGHT(R)=0
;        cmpu  #0                      IF Q=0...
;        bne   MergeLeftistTreesM2.PxQuRy1 b/ Q<>0
;        lda   move$distance,x         D:=DIST(P)
;        ; Assert: P<>0, Q=0, R<>0, RIGHT(R)=0
;        bra   MergeLeftistTreesM3.PxRy1

;MergeLeftistTreesM2.PxQuRy1 ; Assert: P=?, Q<>0, R<>0, RIGHT(R)=0
;        cmpx  #0                      IF P=0...
;        bne   MergeLeftistTreesM2.PxQuRy3  b/ P<>0
;MergeLeftistTreesM2.PxQuRy2 ; assert: P=0, Q<>0, R<>0, RIGHT(R)=0
;        ; P:=Q (rebind registers so P is in u, Q is in x)
;        lda   move$distance,u         D:=DIST(P)
;        bra   MergeLeftistTreesM3.PuRy1 GOTO M3

MergeLeftistTreesM2.PxQuRy3 ; P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$score,x            fetch KEY(P)
         subd  move$score,u            compare KEY(P) to KEY(Q)
         blt   MergeLeftistTreesM2.PxQuRy5 b/ KEY(P)<KEY(Q)
         ldd   move$rightson,x         T:=RIGHT(P)
         beq   MergetLeftistTreesM2.PxQuRy4 b/ RIGHT(P)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(P)<>0
         sty   move$rightson,x         RIGHT(P):=R
         ; R:=P (rebind registers so R is in x, P is in y)
         tfr   d,y                     P:=T
         bra   MergeLeftistTreesM2.PyQuRx3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PxQuRy4 ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         sty   move$rightson,x         RIGHT(P):=R
         ; R:=P (rebind registers so R is in x, P is in y), P:=T, GOTO M2
         ; assert: P=0, Q<>0, R<>0, RIGHT(R)<>0
         ; P:=Q (rebind registers so P is in u, Q is in y)
         lda   move$distance,u         D:=DIST(P)
         ; assert: P<>0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PuRx1 GOTO M3

MergeLeftistTreesM2.PxQuRy5 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0
         ldd   move$rightson,u         T:=RIGHT(Q)
         beq   MergetLeftistTreesM2.PxQuRy6 b/ RIGHT(Q)=0
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)=0, RIGHT(Q)<>0
         sty   move$rightson,u         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in u, Q is in y)
         tfr   d,y                     Q:=T
         bra   MergeLeftistTreesM2.PxQyRu3 GOTO M2
         ; assert: P<>0, Q<>0, R<>0, RIGHT(R)<>0

MergetLeftistTreesM2.PxQuRy6 ; KEY(P)<KEY(Q), P<>0, Q<>0, R<>0, RIGHT(R)=0, T=0
         sty   move$rightson,u         RIGHT(Q):=R
         ; R:=Q (rebind registers so R is in u, Q is in y), Q:=T, GOTO M2
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0
         lda   move$distance,x         D:=DIST(P)
         ; assert: P<>0, Q=0, R<>0, RIGHT(R)<>0, D=DIST(P)
         bra   MergeLeftistTreesM3.PxRu1 GOTO M2
         page
MergeLeftistTreesM3.PxRy1 ; D>0, R<>0
         ldu   move$leftson,y          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PxRy2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PxRy3 skip back into code

MergeLeftistTreesM3.PxRy2 ; LEFT(R)<>0
         cmpa  move$distance,u         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PxRy5 b/ ELSE case
         lda   move$distance,u         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PxRy3
         staa  move$distance,y         DIST(R):=D
         ldd   move$rightson,y         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PxRy4 b/ Q<>0, remember it
         stu   move$rightson,y         RIGHT(R):=LEFT(R)
         stx   move$leftson,y          LEFT(R):=P
         ; P:=R (rebind registers so P is in y, R is in x)
         ; R:=Q (assert: R=0)
         leau  0,y                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PxRy4 ; Q<>0, remember it
         stu   move$rightson,y         RIGHT(R):=LEFT(R)
         stx   move$leftson,y          LEFT(R):=P
         ; P:=R (rebind registers so P is in y, R is in x)
         tfr   d,x                     R:=Q (assert: R<>0)
         lda   move$distance,y         (restore D)
         bra   MergeLeftistTreesM3.PyRx1

MergeLeftistTreesM3.PxRy5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,y         DIST(R):=D
         ldu   move$rightson,y         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PxRyQu6 b/ Q<>0
         stx   move$rightson,y         RIGHT(R):=P
         ; P:=R (rebind registers so P is in y, R is in x)
         ; R:=Q (is zero, we're done!)
         leau  0,y                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PxRyQu6 ; Q<>0
         stx   move$rightson,y         RIGHT(R):=P
         ; P:=R (rebind registers so P is in y, R is in x)
         ; R:=Q (rebind registers so R is in u)
         bra   MergeLeftistTreesM3.PyRu1
         page
MergeLeftistTreesM3.PuRx1 ; R<>0
         ldy   move$leftson,x          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PuRx2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PuRx3 skip back into code

MergeLeftistTreesM3.PuRx2 ; LEFT(R)<>0
         cmpa  move$distance,x         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PuRx5 b/ ELSE case
         lda   move$distance,x         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PuRx3
         staa  move$distance,x         DIST(R):=D
         ldd   move$rightson,x         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PuRx4 b/ Q<>0, remember it
         sty   move$rightson,x         RIGHT(R):=LEFT(R)
         stu   move$leftson,x          LEFT(R):=P
         ; P:=R (rebind registers so P is in x, R is in u)
         ; R:=Q (assert: R=0)
         leau  0,x                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PuRx4 ; Q<>0, remember it
         sty   move$rightson,x         RIGHT(R):=LEFT(R)
         stu   move$leftson,x          LEFT(R):=P
         ; P:=R (rebind registers so P is in x, R is in u)
         tfr   d,u                     R:=Q (assert: R<>0)
         lda   move$distance,x         (restore D)
         bra   MergeLeftistTreesM3.PxRu1

MergeLeftistTreesM3.PuRx5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,x         DIST(R):=D
         ldy   move$rightson,x         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PuRxQy6 b/ Q<>0
         stu   move$rightson,x         RIGHT(R):=P
         ; P:=R (rebind registers so P is in x, R is in u)
         ; R:=Q (is zero, we're done!)
         leau  0,x                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PuRxQy6 ; Q<>0
         stu   move$rightson,x         RIGHT(R):=P
         ; P:=R (rebind registers so P is in x, R is in u)
         ; R:=Q (rebind registers so R is in y)
         bra   MergeLeftistTreesM3.PxRy1
         page
MergeLeftistTreesM3.PyRx1 ; R<>0
         ldu   move$leftson,x          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PyRx2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PyRx3 skip back into code

MergeLeftistTreesM3.PyRx2 ; LEFT(R)<>0
         cmpa  move$distance,u         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PyRx5 b/ ELSE case
         lda   move$distance,u         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PyRx3
         staa  move$distance,x         DIST(R):=D
         ldd   move$rightson,x         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PyRx4 b/ Q<>0, remember it
         stu   move$rightson,x         RIGHT(R):=LEFT(R)
         sty   move$leftson,x          LEFT(R):=P
         ; P:=R (rebind registers so P is in x, R is in y)
         ; R:=Q (assert: R=0)
         leau  0,x                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PyRx4 ; Q<>0, remember it
         stu   move$rightson,x         RIGHT(R):=LEFT(R)
         sty   move$leftson,x          LEFT(R):=P
         ; P:=R (rebind registers so P is in x, R is in y)
         tfr   d,y                     R:=Q (assert: R<>0)
         lda   move$distance,x         (restore D)
         bra   MergeLeftistTreesM3.PyRx1

MergeLeftistTreesM3.PyRx5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,x         DIST(R):=D
         ldu   move$rightson,x         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PyRxQu6 b/ Q<>0
         sty   move$rightson,x         RIGHT(R):=P
         ; P:=R (rebind registers so P is in x, R is in y)
         ; R:=Q (is zero, we're done!)
         leau  0,x                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PyRxQu6 ; Q<>0
         sty   move$rightson,x         RIGHT(R):=P
         ; P:=R (rebind registers so P is in x, R is in y)
         ; R:=Q (rebind registers so R is in u)
         bra   MergeLeftistTreesM3.PxRy1
         page
MergeLeftistTreesM3.PyRu1 ; R<>0
         ldx   move$leftson,u          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PyRu2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PyRu3 skip back into code

MergeLeftistTreesM3.PyRu2 ; LEFT(R)<>0
         cmpa  move$distance,x         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PyRu5 b/ ELSE case
         lda   move$distance,x         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PyRu3
         staa  move$distance,u         DIST(R):=D
         ldd   move$rightson,u         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PyRu4 b/ Q<>0, remember it
         stx   move$rightson,u         RIGHT(R):=LEFT(R)
         sty   move$leftson,u          LEFT(R):=P
         ; P:=R (rebind registers so P is in u, R is in y)
         ; R:=Q (assert: R=0)
;        leau  0,u                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PyRu4 ; Q<>0, remember it
         stx   move$rightson,u         RIGHT(R):=LEFT(R)
         sty   move$leftson,u          LEFT(R):=P
         ; P:=R (rebind registers so P is in u, R is in y)
         tfr   d,y                     R:=Q (assert: R<>0)
         lda   move$distance,u         (restore D)
         bra   MergeLeftistTreesM3.PuRy1

MergeLeftistTreesM3.PyRu5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,u         DIST(R):=D
         ldx   move$rightson,u         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PyRuQx6 b/ Q<>0
         sty   move$rightson,u         RIGHT(R):=P
         ; P:=R (rebind registers so P is in u, R is in y)
         ; R:=Q (is zero, we're done!)
;        leau  0,u                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PyRuQx6 ; Q<>0
         sty   move$rightson,u         RIGHT(R):=P
         ; P:=R (rebind registers so P is in u, R is in y)
         ; R:=Q (rebind registers so R is in x)
         bra   MergeLeftistTreesM3.PuRx1
         page
MergeLeftistTreesM3.PuRy1 ; R<>0
         ldx   move$leftson,y          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PuRy2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PuRy3 skip back into code

MergeLeftistTreesM3.PuRy2 ; LEFT(R)<>0
         cmpa  move$distance,x         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PuRy5 b/ ELSE case
         lda   move$distance,x         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PuRy3
         staa  move$distance,y         DIST(R):=D
         ldd   move$rightson,y         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PuRy4 b/ Q<>0, remember it
         stx   move$rightson,y         RIGHT(R):=LEFT(R)
         stu   move$leftson,y          LEFT(R):=P
         ; P:=R (rebind registers so P is in y, R is in u)
         ; R:=Q (assert: R=0)
         leau  0,y                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PuRy4 ; Q<>0, remember it
         stx   move$rightson,y         RIGHT(R):=LEFT(R)
         stu   move$leftson,y          LEFT(R):=P
         ; P:=R (rebind registers so P is in y, R is in u)
         tfr   d,u                     R:=Q (assert: R<>0)
         lda   move$distance,y         (restore D)
         bra   MergeLeftistTreesM3.PyRu1

MergeLeftistTreesM3.PuRy5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,y         DIST(R):=D
         ldx   move$rightson,y         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PuRyQx6 b/ Q<>0
         stu   move$rightson,y         RIGHT(R):=P
         ; P:=R (rebind registers so P is in y, R is in u)
         ; R:=Q (is zero, we're done!)
         leau  0,y                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PuRyQx6 ; Q<>0
         stu   move$rightson,y         RIGHT(R):=P
         ; P:=R (rebind registers so P is in y, R is in u)
         ; R:=Q (rebind registers so R is in x)
         bra   MergeLeftistTreesM3.PyRx1
         page
MergeLeftistTreesM3.PxRu1 ; R<>0
         ldy   move$leftson,u          T:=LEFT(R)
         bne   MergeLeftistTreesM3.PxRu2 b/ LEFT(R)<>0
         lda   #1                      D:=DIST(LEFT(R))+1 (=1 since LEFT(R)=0)
         bra   MergeLeftistTreesM3.PxRu3 skip back into code

MergeLeftistTreesM3.PxRu2 ; LEFT(R)<>0
         cmpa  move$distance,y         IF DIST(LEFT(R))<D...
         ble   MergeLeftistTreesM3.PxRu5 b/ ELSE case
         lda   move$distance,y         D:=DIST(LEFT(R))+1
         inca
MergeLeftistTreesM3.PxRu3
         staa  move$distance,u         DIST(R):=D
         ldd   move$rightson,u         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PxRu4 b/ Q<>0, remember it
         sty   move$rightson,u         RIGHT(R):=LEFT(R)
         stx   move$leftson,u          LEFT(R):=P
         ; P:=R (rebind registers so P is in u, R is in x)
         ; R:=Q (assert: R=0)
;        leau  0,u                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PxRu4 ; Q<>0, remember it
         sty   move$rightson,u         RIGHT(R):=LEFT(R)
         stx   move$leftson,u          LEFT(R):=P
         ; P:=R (rebind registers so P is in u, R is in x)
         tfr   d,x                     R:=Q (assert: R<>0)
         lda   move$distance,u         (restore D)
         bra   MergeLeftistTreesM3.PuRx1

MergeLeftistTreesM3.PxRu5 ; DIST(LEFT(R))>=D
         inca                          D:=D+1
         sta   move$distance,u         DIST(R):=D
         ldy   move$rightson,u         Q:=RIGHT(R)
         bne   MergeLeftistTreesM3.PxRuQy6 b/ Q<>0
         stx   move$rightson,u         RIGHT(R):=P
         ; P:=R (rebind registers so P is in u, R is in x)
         ; R:=Q (is zero, we're done!)
;        leau  0,u                     place result in U register
         rts                           done!

MergeLeftistTreesM3.PxRuQy6 ; Q<>0
         stx   move$rightson,u         RIGHT(R):=P
         ; P:=R (rebind registers so P is in u, R is in x)
         ; R:=Q (rebind registers so R is in y)
         bra   MergeLeftistTreesM3.PuRy1
         page
ValidateLeftistTree ; Check that leftist tree at (X) is valid
; Do Postorder tree walk (check leaves before checking parents of leaves)
         ldy   move$rightson,x         is there a right son ?
         bne   ValidateLeftistTreeRS   b/ right son
         lda   move$distance,x         no right son, move$distance MUST BE 1
         cmpa  #1
         beq   *+3
         swi
         ldu   move$leftson,x          fetch left son pointer
         bne   ValidateLeftistTreeLS   b/ left son, but no right son
         rts                           no sons, move$distance=1 --> valid.

ValidateLeftistTreeLS ; left son exists, but no right son, and move$distance=1
         ldd   move$score,x            get parent score
         cmpd  move$score,u            and compare to son score
         bge   *+3                     b/ score is OK
         swi
         tfr   u,x                     validate son
         bsr   ValidateLeftistTree
         rts

ValidateLeftistTreeRS ; right son exists
         ldu   move$leftson,x          make sure that left son exists
         bne   *+3                     b/ it does
         swi
         ldd   move$score,x            fetch score of parent
         cmpd  move$score,u            must be larger than score of left son
         bge   *+3
         swi
         cmpd  move$score,y            must be larger than score of right son
         bge   *+3
         swi
         lda   move$distance,y         get distance for right son
         cmpa  move$distance,u         must be .LE. than distance for left son
         ble   *+3
         swi
         inca                          gives distance for parent
         cmpa  move$distance,x
         bne   *+3
         swi
         pshs  y                       save pointer to right son
         tfr   u,x                     validate left son
         bsr   ValidateLeftistTree
         puls  x                       validate right son
         bsr   ValidateLeftistTree
         rts                           all done!
         page
Tree     fdb   0                       empty tree
FreeNodeCount fcb 0
FreeNodes fdb  0

Start    ldx   #NodePool               where to get nodes from
Loop     ldu   FreeNodes               add node to free node chain
         stu   move$leftson,x
         stx   FreeNodes
         leax  10,x                    allocate node space
         inc   FreeNodes
         bpl   Loop
TEST ; Test Leftist Tree Logic
         ldx   Tree                    get pointer to tree
         beq   Test1                   b/ tree is valid
         jsr   ValidateLeftistTree     make sure tree is sane
         jsr   Random
         bcs   TestDelete
TestInsert
         tst   FreeNodeCount
         beq   TestDelete
         ldx   FreeNodes               get a free node
         ldu   move$leftson,x          find next node
         stu   FreeNodes
         ldu   #0                      make node be canonical
         stu   move$leftson,x
         stu   move$rightson,x
         lda   #1
         sta   move$distance,x
         dec   FreeNodeCount
         ldd   RandomNumber
         std   move$score,x
         ldy   #Tree
         jsr   InsertMoveIntoList
         bra   Test

TestDelete
         ldx   Tree                    Node which gets deleted
         beq   Test                    b/ nothing to delete
         pshx                          remember node result
         ldy   #Tree                   pointer to list to delete node from
         jsr   DeleteBestMove          go do it
         cmpx  ,s++                    return the right node ?
         beq   *+3
         swi                           returned wrong node
         ldu   FreeNodes               add to free nodes list
         stu   move$leftson,x          put onto front of free node list
         stx   FreeNodes
         inc   FreeNodeCount
         bra   Test

NodePool rmb   10000

         END   start
