#ifndef HUFFMAN_TREE_H
#define HUFFMAN_TREE

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Node
{
private:
   char character;
   int frequency;
   Node* left;
   Node* right;
friend class HuffmanTree;   
};

/*
   Drzewo do dekodowania kodów Huffmana.
*/
class HuffmanTree
{
public:
   /**
      Konstruuje drzewo Huffmana na podstawie podanej częstości występowania znaków.
      @param frequencies mapa, której klucze są znakami do zakodowania,
      a wartości to częstości występowania tych znaków
   */
   HuffmanTree(const unordered_map<char, int>& frequencies);
   /**
      Dekoduje zakodowany ciąg.
      @param input ciąg złożony z zer i jedynek
   */
   string decode(string input) const;

   unordered_map<char, string> encoding_map() const;

private:
   Node* remove_min(vector<Node*>& nodes) const;
   void fill_encoding_map(unordered_map<char, string>& map,
      string prefix, Node* n) const;   
   
   Node* root;   
};

#endif

