lib/HuffmanAllocator.js
function(array, nodesToMove,
                                                   insertDepth) {
    var firstNode = array.length - 2;
    var nextNode = array.length - 1;
    var currentDepth = (insertDepth == 1) ? 2 : 1;
    var nodesLeftToMove = (insertDepth == 1) ? nodesToMove - 2 : nodesToMove;
    var availableNodes, lastNode, offset, i;

    for (availableNodes = currentDepth << 1;
         availableNodes > 0;
         currentDepth++) {
      lastNode = firstNode;
      firstNode = (firstNode <= nodesToMove) ? firstNode : first (array, lastNode - 1, nodesToMove);

      offset = 0;
      if (currentDepth >= insertDepth) {
        offset = Math.min (nodesLeftToMove, 1 << (currentDepth - insertDepth));
      } else if (currentDepth == (insertDepth - 1)) {
        offset = 1;
        if ((array[firstNode]) == lastNode) {
          firstNode++;
        }
      }

      for (i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
        array[nextNode--] = currentDepth;
      }

      nodesLeftToMove -= offset;
      availableNodes = (lastNode - firstNode + offset) << 1;
    }
  }
function(array, nodesToMove,
                                                   insertDepth) {
    var firstNode = array.length - 2;
    var nextNode = array.length - 1;
    var currentDepth = (insertDepth == 1) ? 2 : 1;
    var nodesLeftToMove = (insertDepth == 1) ? nodesToMove - 2 : nodesToMove;
    var availableNodes, lastNode, offset, i;

    for (availableNodes = currentDepth << 1;
         availableNodes > 0;
         currentDepth++) {
      lastNode = firstNode;
      firstNode = (firstNode <= nodesToMove) ? firstNode : first (array, lastNode - 1, nodesToMove);

      offset = 0;
      if (currentDepth >= insertDepth) {
        offset = Math.min (nodesLeftToMove, 1 << (currentDepth - insertDepth));
      } else if (currentDepth == (insertDepth - 1)) {
        offset = 1;
        if ((array[firstNode]) == lastNode) {
          firstNode++;
        }
      }

      for (i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
        array[nextNode--] = currentDepth;
      }

      nodesLeftToMove -= offset;
      availableNodes = (lastNode - firstNode + offset) << 1;
    }
  }
function ( array , nodesToMove , insertDepth ) { var firstNode = array . length - 2 ; var nextNode = array . length - 1 ; var currentDepth = ( insertDepth == 1 ) ? 2 : 1 ; var nodesLeftToMove = ( insertDepth == 1 ) ? nodesToMove - 2 : nodesToMove ; var availableNodes , lastNode , offset , i ; for ( availableNodes = currentDepth << 1 ; availableNodes > 0 ; currentDepth ++ ) { lastNode = firstNode ; firstNode = ( firstNode <= nodesToMove ) ? firstNode : first ( array , lastNode - 1 , nodesToMove ) ; offset = 0 ; if ( currentDepth >= insertDepth ) { offset = Math . min ( nodesLeftToMove , 1 << ( currentDepth - insertDepth ) ) ; } else if ( currentDepth == ( insertDepth - 1 ) ) { offset = 1 ; if ( ( array [ firstNode ] ) == lastNode ) { firstNode ++ ; } } for ( i = availableNodes - ( lastNode - firstNode + offset ) ; i > 0 ; i -- ) { array [ nextNode -- ] = currentDepth ; } nodesLeftToMove -= offset ; availableNodes = ( lastNode - firstNode + offset ) << 1 ; } }
A final allocation pass that relocates nodes in order to achieve a
maximum code length limit
@param array The code length array
@param nodesToMove The number of internal nodes to be relocated
@param insertDepth The depth at which to insert relocated nodes
A final allocation pass that relocates nodes in order to achieve a maximum code length limit