ANEW --HUFFMAN--  DECIMAL                     \  Wil Baden  2002-07-03

\  Build-Huffman
\     Knuth, TAOCP 2.3.4.5, Exercise 13.
\     Beginning with weights in ascending order, construct an
\     extended binary tree having minimum weighted path lengths.
\
\     Represent the final tree in three arrays where L[i] and R[i]
\     point to the left and right children of internal node i, the
\     root is node 1, and A[i] is the weight of node i.  The original
\     external weights should be in A after the internal weights.

TRUE 0<> [IF]  \  Comment out redundant definitions.

    : nth                          ( i "arrayname" -- addr )
        S" CELLS " EVALUATE
        BL WORD COUNT EVALUATE
        S" + " EVALUATE
        ; IMMEDIATE

    : ORIF  S" DUP 0= IF DROP " EVALUATE ; IMMEDIATE

[THEN]

CREATE  W

\  ***  Lay down weights in ascending order. ***

\  Example.
    1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 , 100 ,

HERE W - 1 CELLS / CONSTANT  M

CREATE  A  M 2* CELLS ALLOT
CREATE  L  M CELLS ALLOT
CREATE  R  M CELLS ALLOT

TRUE 1 RSHIFT CONSTANT  HUGE

VARIABLE  &x
VARIABLE  &y
VARIABLE  &i
VARIABLE  &j
VARIABLE  &k

: Build-Huffman             ( -- )
    \ H1.  Initialize.
    W  M 1- nth A  M CELLS  MOVE
    HUGE  M 2* 1- nth A !
    M 1- &x !  M &i !  M 2 - &j !  M 1- &k !
    BEGIN
        \ H2.  Find right pointer.
        &j @ &k @ <
        ORIF  &i @ nth A @  &j @ nth A @  > NOT THEN
        IF
            &i @ &y !  1 &i +!
        ELSE
            &j @ &y !  -1 &j +!
        THEN
        \ H3.  Create internal node.
        -1 &k +!
        &x @ &k @ nth L !
        &y @ &k @ nth R !
        &x @ nth A @  &y @ nth A @ +  &k @ nth A !
        \ H4.  Done?
        &k @
    WHILE
        \ H5.  Find left pointer.
        &i @ nth A @  &j @ nth A @  > NOT IF
            &i @ &x !  1 &i +!
        ELSE
            &j @ &x !  -1 &j +!
        THEN
    REPEAT ;

Build-Huffman

A M 2* IDUMP
L M 1- IDUMP
R M 1- IDUMP
\\  ************************  End of Huffman  *************************

 385  219  166  119   85   55   30   14    5    1    4    9   16   25   36   49 
  64   81  100 2147483647 
   2   18   17    5   14   13    7    8    9 
   1    3    4   16   15    6   12   11   10