extension/packages/mode-hints/huffman.coffee

   1 # `originalElements` should be an array of objects. Each object is expected to
   2 # have a `weight` property which represents the _weight_ of the object, which is
   3 # a positive number. Each object will be given a _code word_. The larger the
   4 # weight, the shorter the code word. A weight of 0 means that the element should
   5 # not get a code word at all. The code words will use the `alphabet` provided.
   6 # The function runs `callback(element, codeWord)` for each object in
   7 # `originalElements` and returns `undefined`.
   8 exports.addHuffmanCodeWordsTo = (originalElements, { alphabet }, callback) ->
   9   unless typeof alphabet == 'string'
  10     throw new TypeError('`alphabet` must be provided and be a string.')
  11
  12   nonUnique = /([\s\S])[\s\S]*\1/.exec(alphabet)
  13   if nonUnique
  14     throw new Error("`alphabet` must consist of unique letters. Found
  15       '#{ nonUnique[1] }' more than once.")
  16
  17   if alphabet.length < 2
  18     throw new Error('`alphabet` must consist of at least 2 characters.')
  19
  20   unless typeof callback == "function"
  21     throw new TypeError("`callback` must be provided and be a function.")
  22
  23
  24   # Shallow working copy.
  25   elements = originalElements[..]
  26
  27
  28   # The algorithm is so optimized, that it does not produce a code word at all
  29   # if there is only one element! We still need a code word even if there is
  30   # only one link, though.
  31   if elements.length == 1
  32     callback(elements[0], alphabet[0])
  33     return
  34
  35
  36   numBranches = alphabet.length
  37   numElements = elements.length
  38
  39   # The Huffman algorithm needs to create a `numBranches`-ary tree (one branch
  40   # for each character in the `alphabet`). Such a tree can be formed by `1 +
  41   # (numBranches - 1) * n` elements: There is the root of the tree (`1`), and
  42   # each branching adds `numBranches` elements to the total number or elements,
  43   # but replaces itself (`numBranches - 1`). `n` is the number of points where
  44   # the tree branches. In order to create the tree using `numElements` elements,
  45   # we need to find an `n` such that `1 + (numBranches - 1) * n >= numElements`
  46   # (1), and then pad `numElements`, such that `1 + (numBranches - 1) * n ==
  47   # numElements + padding` (2).
  48   #
  49   # Solving for `n = numBranchPoints` in (1) gives:
  50   numBranchPoints = Math.ceil((numElements - 1) / (numBranches - 1))
  51   # Solving for `padding` in (2) gives:
  52   padding = 1 + (numBranches - 1) * numBranchPoints - numElements
  53
  54   # Sort the elements after their weights, in descending order, so that the last
  55   # ones will be the ones with lowest weight.
  56   elements.sort((a, b) -> b.weight - a.weight)
  57
  58   # Pad with zero-weights to be able to form a `numBranches`-ary tree.
  59   for i in [0...padding] by 1
  60     elements.push({weight: 0})
  61
  62   # Construct the Huffman tree.
  63   for i in [0...numBranchPoints] by 1
  64     # Replace `numBranches` of the lightest weights with their sum.
  65     sum = new BranchingPoint
  66     for i in [0...numBranches] by 1
  67       lowestWeight = elements.pop()
  68       sum.weight += lowestWeight.weight
  69       sum.children.unshift(lowestWeight)
  70
  71     # Find the index to insert the sum so that the sorting is maintained. That
  72     # is faster than sorting the elements in each iteration.
  73     break for element, index in elements by -1 when sum.weight <= element.weight
  74     elements.splice(index + 1, 0, sum)
  75
  76   [ root ] = elements # `elements.length == 1` by now.
  77
  78   # Create the code words by walking the tree. Store them using `callback`.
  79   do walk = (node = root, codeWord = '') ->
  80     if node instanceof BranchingPoint
  81       for childNode, index in node.children
  82         walk(childNode, codeWord + alphabet[index])
  83     else
  84       callback(node, codeWord) unless node.weight == 0
  85     return
  86
  87
  88 class BranchingPoint
  89   constructor: ->
  90     @weight = 0
  91     @children = []