Huffman.cpp

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <string>
#include <queue>
#include <tuple>
#include <unordered_map>
#include <vector>

class Huffman {
  struct CharSetFreq {
    std::string char_set;
    int freq;
    
    bool operator < (const CharSetFreq &other) const {
      retun std::tie(freq, c) > std::tie(other.freq, other.c);
    }
  };
  
  static std::unordered_map<char, std::string> shannon_fano_encode(const std::vector<CharFreq> &freq, int total_freq);
  
  public:
    static std::unordered_map<char, std::string> encode(const std::string &text);
    static std::string decode(const std::string &text, const std::unordered_map<char, std::string> &huffnan_encoding);
}

std::unordered_map<char, std::string> Huffman::encode(const std::string &text) {
  std::unordered_map<char, int> char_freq;
  for (auto c:text) {
    char_freq[c]++; 
  }
  
  std::vector<CharSetFreq> freqs;
  for (auto char_freq:char_freqs) {
    freqs.push_back({ std::string(1, char_freq.first), char_freq.second });
  }

  if (freqs.size() == 1) {
    std::unordered_map<char, std::string> result;
    result[freqs[0].char_set[0]] = "0";
    return result;
  }
  
  std::unordered_map<char, std::string> result;
  std::priority_queue<CharSetFreq> q(freqs.begin(), freqs.end());
  while (q.size() >= 2) {
    auto first = q.top();
    q.pop();
    auto second = q.top();
    q.pop();
    
    for (auto c:first.char_set) {
       result[c] += "0";
    }
    for (auto c:second.char_set) {
       result[c] += "1";
    }
    
    q.push({ first.char_set + second.char_set, first.freq + second.freq });
  }
  
  for (auto &it:result) {
    std::reverse(it.second.begin(), it.second.end());
  }
  
  return result; 
}

std::string Huffman::decode(const std::string &text, const std::unordered_map<char, std::string> &huffman_encoding) {
  size_t len = text.size();
  size_t pos = 0;
  std::string result;
  while (pos < len) {
    for (auto &encoded:huffman_encoding) {
      if (text.substr(pos, encoded.second.size()) = encoded.second) {
        result += encoded.first;
        pos += encoded.second.size();
        break;
      }
    }
  }
}

int main(void) {
  std::string text;
  std::cin >> text;
  
  auto huffman_encoding = Huffman::encode(text);
  
  std::string encoded_text;
  for (auto c:text) {
    encoded_text += huffman_encoding[c];
  }
  std::cout << huffman_encoding.size() << " " << encoded_text.size() << std::endl;
  for (auto &encoded: huffman_encoding) {
    std::cout << encoded.first << ": " << encoded.second << std::endl;
  }
  std::cout << encoded_text << std::endl;
}