huffman-tree builder in coffeescript

huffman.coffee

class Node
   constructor: (@p, @value, @childs=[]) ->

class HuffmanTreeBuilder
  _nodes: []
  _rootNode: null
  # probabilities = value1: probability1, value2: probability2, ...
  constructor: (probabilities = {}) ->
    (@_add new Node p, value) for value, p of probabilities

  getRootNode: () ->
    @_rootNode = @_buildTree() if @_rootNode is null

    return @_rootNode

  debug: () ->
    console.group "Huffman tree"
    @_printNode @getRootNode()
    console.groupEnd()

  _buildTree: () ->
    @_combineNodes() until @_nodes.length == 1
    @_nodes.pop()

  _combineNodes: () ->
    a=@_nodes.pop()
    b=@_nodes.pop()

    @_add new Node( a.p + b.p, "[#{a.value},#{b.value}]", [a, b] )

  _add: (node) ->
    @_nodes.push(node)
    @_sort()

  _sort: () ->
    @_nodes.sort (a, b) -> b.p - a.p

  _printNode: (node, code='') ->
    str = "#{node.value} (p=#{node.p})"
    if not node.childs or node.childs.length == 0
      console.log "#{code} - #{str}"
    else
      console.group str
      @_printNode( n, code+i ) for n,i in node.childs
      console.groupEnd()


class HuffmanEncoder
  encodings: {}
  treeBuilder: null

  constructor: (probabilities) ->
    @outstream = new String
    @treeBuilder = new HuffmanTreeBuilder probabilities
    @_addEncodings @treeBuilder.getRootNode()

  # input 'abc
  encode: (bytes) ->
    writeBits = (bits, length)
    writeBits(encode byte) for byte in bytes
  

  _addEncodings: (node, encodingPrefix=0, bitLength=0) ->
    if not node.childs or node.childs.length == 0
      @encodings[node.value] = {
        code: encodingPrefix,
        mask: (Math.pow 2, bitLength)-1
        bitLength: bitLength
      }
    else
      @_addEncodings node, (encodingPrefix << 1) + i, bitLength+1 for node,i in node.childs
    return

  printEncodings: () ->
    console.group "Encodings"
    formatEntry = (value, e) -> "[#{(e.code).toString(2)}/#{e.bitLength}/{(e.mask).toString(2)}] - #{value}"

    (console.log formatEntry value, e) for value, e of @encodings
    console.groupEnd()
# ---- test ----

encoder=new HuffmanEncoder {
  'a': 0.1
  'b': 0.2
  'c': 0.15
  'd': 0.2
  'e': 0.05
  'x': 0.3
}

### resulting encodings

[00/2/11] - d
[01/2/11] - b
[10/2/11] - x
[110/3/111] - c
[1110/4/1111] - e
[1111/4/1111] - a

this needs to be packed into the bytes in a way that allows
for msb-first reading.

read 'a'
  ----a
  00001111/4 -  15 - 0x0f
read 'ab'
  --b a
  00011111/2
read 'abd'
  d b a
  00011111/0

read 'abdb'
  d b a
  00011111
  ------b
  00000001/6

read 'abdbx'
  d b a
  00011111
  ----b x
  00000110/4

read 'abdbx'
  d b a
  00011111
  -b x c
  00110110/1

###

encoder.treeBuilder.debug()
encoder.printEncodings()

console.log encoder.encodings