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