huffman.js

function Huffman(text){
  this.text = text;
  this.coded = {};
  this.node = {
    right: null,
    left: null,
    freq: 0,
    code:""
  };
  this.encode = encode;
  this.createHuffmanTree = createHuffmanTree;
  this.sortByFrequency = sortByFrequency;
  this.createFrequencyHash = createFrequencyHash;
  this.createBitMap = createBitMap;
  this.buildHuffmanCode = buildHuffmanCode;
}

function encode(){
  this.textArray = this.text.split("");
  var sortedHash = sortByFrequency(this.createFrequencyHash());
  var tree = this.createHuffmanTree(sortedHash);
  
  
  this.createBitMap(tree);
  console.log(this.buildHuffmanCode());
}

function createHuffmanTree(elements){
  if(elements.length == 1)
    return elements[0];

  var parent = JSON.parse(JSON.stringify(this.node));

  parent.left = elements[0];
  parent.right = elements[1];

  parent.freq = parent.left.freq + parent.right.freq;

  elements.splice(0,2);
  elements.push(parent);

  return this.createHuffmanTree(this.sortByFrequency(elements));
}

function sortByFrequency(hash){
  for(var i = 1 ; i<hash.length ; i++){
    var temp = hash[i];
    var j = i;
    while(j>0 && temp.freq <= hash[j-1].freq){
      hash[j] = hash[j-1];
      j--;
    }
    hash[j] = temp;
  }
  //console.log(hash);
  return hash;
}

function createFrequencyHash(){
  var freq = [];
  var found = false;
  var index;
  
  for(var i = 0 ;i < this.textArray.length ; i++){
    for(var j = 0 ; j < freq.length ; j++){
      if(freq[j].value == this.textArray[i]){
        found = true;
        index = j;
      }
    }
    if(found){
      freq[index].freq += 1;
      found = false;
    } else{
      freq.push({value: this.textArray[i], freq: 1});
    }
  }
  
  return freq;
}

function createBitMap(tree){
   if(!(tree == null) && tree){
    if(tree.left != null && (typeof tree.left !== 'undefined')){
      tree.left.code = tree.code + "0";
      this.coded[tree.left.value] = tree.left.code;
    }
    if(tree.right != null && (typeof tree.right !== 'undefined')){
      tree.right.code = tree.code + "1";
      this.coded[tree.right.value] = tree.right.code;
    }
    this.createBitMap(tree.left);
    this.createBitMap(tree.right);
  }
}

function buildHuffmanCode(){
  for(var i = 0 ; i< this.textArray.length ; i++){
    this.textArray[i] = this.coded[this.textArray[i]];
  }
  return this.textArray.join("");
}


var huffman = new Huffman("omere");
huffman.encode();

module.exports = Huffman;