// takes: String; returns: [ [String,Int] ] (Strings in return value are single characters)
function frequencies(s) {
  const rd = new Map();
  for(const c of s) {
    rd.set(c, rd.has(c) ? rd.get(c) + 1 : 1);
  }
  return Array.from(rd);
}

// takes: [ [String,Int] ], String; returns: String (with "0" and "1")
function encode(freqs,s) {
  
    if(freqs.length <= 1) return null;
  
    const huff = new Huffman(freqs);
  
    return huff.encode(s);
}

// takes [ [String, Int] ], String (with "0" and "1"); returns: String
function decode(freqs,bits) {
  
    if(freqs.length <= 1) return null;
    const huff = new Huffman(freqs);
    
    return huff.decode(bits);
}

// implement a Human Class
class Huffman {
  constructor(freqs) {
    // tree: [....] 
    // {name, type, left, right, freq}
    this.root = this.create(freqs);
    this.charToBits = this.calculateCharToBits();
  }
  create(f) {
    const nodes = f.map(e => this.createNode(e[0], "leaf", null, null, e[1]));
    //console.log("nodes: ", nodes);
    const heap = createHeap(nodes, (a, b) => a.freq - b.freq);
    
    //console.log("create heap complete!!!")
    
    while(heap.getLength() > 1) {
      const left = heap.findMin();
      const right = heap.findMin();
      const newNode = this.createNode('', 'inner', left, right, left.freq + right.freq);
      heap.add(newNode);
    }
    
    /* return the root of the huffman tree */
    return heap.findMin();
  }
  
  /*
    calculateCharToBits
    return a Map, char as key, encoded bits as value
    {
      'a': '0001'
      ....
    }
  */
  calculateCharToBits() {
    const res = new Map();
    /*
      by pre traveling,to calculate 
    */
    function preOrder(root, prebits) {
      if(root.left === null && root.right === null) {
        res.set(root.name, prebits);
        return;
      }
      
      root.left != null && preOrder(root.left, prebits + '0');
      root.right != null && preOrder(root.right, prebits + '1');
    }
    
    preOrder(this.root, '');
    return res;
  }
  
  createNode(name, type, left, right, freq) {
    return {
      name, 
      type,
      left,
      right,
      freq
    };
  }
  /*  
    string  => 0001111
  */
  encode(s) {
    const res = [];
    for(const c of s) {
      res.push(this.charToBits.get(c));
    }
    return res.join('');
  }
  
  /*
    00001111 => string
  */
  decode(s) {
    const res = [];
    
    let cur = this.root;
    for(const c of s) {
      if(cur.left === null && cur.right === null) {
        /* 
          leaf node
        */
        
        res.push(cur.name);
        cur = this.root;
        
      }
      if(c === '0') {
        cur = cur.left;
      }else {
        cur = cur.right;
      }
    }
    if(cur.left === null && cur.right === null) {
      /* 
        leaf node
      */
      res.push(cur.name);
    }
    return res.join("");
    
  }
}

/*
  Node
  {
    name: 'a',
    type: 'leaf'|'inner',
    left: obj,
    right: obj
    freq: number
  }
  
  push all iniital Node created base on freqs to heap,
  1. if heap.length <= 1, end
  2. find two smallest freq Node
  3. remove from heap
  4. create a new Node base on these two Node and push it to head.
  3. go to 1
*/



/*
  test createHeap function
*/
function createHeap(nodes, compare) {


  /*
    utility functions
  */
  function parent(i) {
    return Math.floor((i-1)/2);
  }

  function left(i) {
    return 2 * i + 1;
  }
  function right(i) {
    return 2 * i + 2;
  }
  /*
    core functions
  */
  function topToDown(i) {
    //console.log("topToDown:", i);
    /*
      use to tiny the tree after removing the min node
    */
    let cur = i;
    let rightIdx = right(i);
    let leftIdx = left(i);
    while(leftIdx < nodes.length && (rightIdx < nodes.length && compare(nodes[cur], nodes[rightIdx]) > 0 || compare(nodes[cur], nodes[leftIdx]) > 0)) {
      //console.log("rightIdx: ", rightIdx,rightIdx < nodes.length ? nodes[rightIdx] : 'not have right');
      //console.log("leftIdx,", leftIdx, nodes[leftIdx]);
      const minIdx = rightIdx >= nodes.length || compare(nodes[leftIdx], nodes[rightIdx]) < 0 ? leftIdx : rightIdx;
      const tmp = nodes[minIdx];
      nodes[minIdx] = nodes[cur];
      nodes[cur] = tmp;

      cur = minIdx;
      rightIdx = right(cur);
      leftIdx = left(cur);
      
      //console.log("minIdx: ", minIdx);
    }
  }
  function downToTop(i) {
    /*
      use to create initial tree and add a new Node
    */
    let cur = i, parentIdx = parent(cur);
    while(cur != 0 && compare(nodes[parentIdx], nodes[cur]) > 0) {
      const tmp = nodes[parentIdx];
      nodes[parentIdx] = nodes[cur];
      nodes[cur] = tmp;

      cur = parentIdx;
      parentIdx = parent(cur);
    }

  }

  /*
    inital heap

    from (n-1 - 1)/2 node to 0 node
      top => down to generate a valid heap
  */
   let n = parent(nodes.length - 1);

   for(let i = n; i >= 0; --i) {
    topToDown(i);
   } 
  
  /*
    return obj
     {
       getLength: () => {}
       findMin: () => {}
       add: () => {}
     }
  */

  return {
    getLength: () => nodes.length,
    add: (node) => {
       nodes.push(node);
       downToTop(nodes.length - 1);
    },
    findMin: () => {
      //console.log("findMin: ");
      const res = nodes[0];
      nodes[0] = nodes[nodes.length - 1];
      nodes.pop();
      topToDown(0);
      return res;
    }
  }
}