htree.h

//
// Last modified by Yusuf Pisan on 2026-01-24
//

#ifndef HUFFMAN_HTREE_H
#define HUFFMAN_HTREE_H

#include <map>
#include <string>
#include <utility>

using namespace std;

class HTree {
public:
  // create HTree from Frequencies
  explicit HTree(map<char, double> &frequencies);

  // create HTree from file
  explicit HTree(const string &filename);

  // compress file (txt -> huff)
  bool compress(const string &in, const string &out);

  // uncompress file (huff -> txt)
  bool uncompress(const string &in, const string &out);

  // destructor
  ~HTree();

  // return encoding for a character, something like 0011
  string getEncoding(char ch);

  // return the average bit rate
  double getBitRate();

private:
  // NOTE:
  // You should not change the public interface of this class.
  // You CAN change private data members and methods as you see fit.
  //

  // Nodes of our Huffman tree
  struct HNode {
    // Bit string representing the path to this node
    string bitString;
    // children nodes
    HNode *left = nullptr;
    HNode *right = nullptr;
    // if leaf node, store character
    char character;
  };

  // store Frequencies of different letters
  map<char, double> frequencies;

  // store the Encodings of different letters
  map<char, string> encodings;

  // Root of the tree
  HNode *root = nullptr;

  // build tree once all information is entered
  void buildHTree();
};

#endif // HUFFMAN_HTREE_H