record huffnode(l,r,n,c)                        # internal and leaf nodes
record huffcode(c,n,b,i)                        # encoding table char, freq, bitstring, bits (int)

procedure main()

s := "this is an example for huffman encoding"

Count := huffcount(s)                           # frequency count
Tree := huffTree(Count)                         # heap and tree

Code := []                                      # extract encodings
CodeT := table()
every x := huffBits(Tree) do
   put( Code, CodeT[c] := huffcode( c := x[-1], Count[c].n, b := x[1:-1], integer("2r"||b) ) )


Code := sortf( Code, 1 )                        # show table in char order
write("Input String : ",image(s))
write(right("char",5), right("freq",5), " encoding" )
every write(right(image((x := !Code).c),5), right(x.n,5), " ", x.b )

end

procedure huffBits(N)                           # generates huffman bitcodes with trailing character
if \N.c then return N.c                         # . append leaf char code
suspend "0" || huffBits(N.l)                    # . left
suspend "1" || huffBits(N.r)                    # . right
end


procedure huffTree(T)                           # two queue huffman tree method
local Q1,Q2,x,n1,n2

Q1 := []                                        # queue of characters and weights
every x := !T do                                # ensure all are huffnodes
   if type(x) == "huffnode" then put(Q1,x) else runerr(205,x)
Q1 := sortf(Q1,3)                               # sort by weight ( 3 means by .n  )

if *Q1 > 1 then Q2 := []
while *Q1+*\Q2 > 1 do {                         # While there is more than one node ...

   n1 := if Q1[1] & ( ( Q1[1].n <= Q2[1].n ) | not Q2[1] ) then get(Q1) else get(Q2)  # lowest weight from Q1 or Q2
   n2 := if Q1[1] & ( ( Q1[1].n <= Q2[1].n ) | not Q2[1] ) then get(Q1) else get(Q2)  # lowest weight from Q1 or Q2

   put( Q2, huffnode( n1, n2, n1.n + n2.n ) )   # new weighted node to end of Q2
}

return (\Q2 | Q1)[1]                            # return the root node
end

procedure huffcount(s)                          # return characters and frequencies in a table of huffnodes by char
local c,T

T := table()
every c := !s do {
   /T[c] := huffnode(,,0,c)
   T[c].n +:= 1	
   }
return T
end