<commit_before>package com.k13n.huffman;

import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Set;

public class HuffmanCoder {
  private final Letter[] alphabet;
  private final Set<Node> leaves;
  private final Node root;

  public HuffmanCoder(Letter[] alphabet) {
    this.alphabet = alphabet;
    leaves = createLeavesFromAlphabet();
    root = buildHuffmanTable();
  }

  private Set<Node> createLeavesFromAlphabet() {
    Set<Node> leaves = new HashSet<>();
    for (Letter letter : alphabet)
      leaves.add(new Node(letter));
    return leaves;
  }

  private Node buildHuffmanTable() {
    Set<Node> nodes = new HashSet<Node>(leaves);
    while (nodes.size() != 1) {
      Node rightChild = extractMinFrequencyNode(nodes);
      Node leftChild = extractMinFrequencyNode(nodes);
      Node parent = Node.merge(leftChild, rightChild);
      nodes.add(parent);
    }
    Node root = nodes.iterator().next();
    return root;
  }

  private Node extractMinFrequencyNode(Set<Node> nodes) {
    double minFrequency = Double.MAX_VALUE;
    Node smallestNode = null;
    for (Node node : nodes) {
      if (node.frequency < minFrequency) {
        minFrequency = node.frequency;
        smallestNode = node;
      }
    }
    nodes.remove(smallestNode);
    return smallestNode;
  }

  public String encode(String text) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < text.length(); i++)
      encodeLetter(text.charAt(i), builder);
    return builder.toString();
  }

  private void encodeLetter(char letter, StringBuilder builder) {
    int offset = builder.length();
    Node leaf = getLeafOfLetter(letter);
    while (leaf != root) {
      char digit = mapSideToDigit(leaf.side);
      builder.insert(offset, digit);
      leaf = leaf.parent;
    }
  }

  public String decode(String text) {
    StringBuilder builder = new StringBuilder();
    Node currentNode = root;
    for (int i = 0; i < text.length(); i++) {
      currentNode = traverseTreeToNextDeeperNode(currentNode, text.charAt(i));
      if (currentNode.isLeave()) {
        char letter = currentNode.letter.getLetter();
        builder.append(letter);<commit_msg>Refactor the minimum frequency node detection<commit_after>package com.k13n.huffman;

import java.util.Comparator;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class HuffmanCoder {
  private final Letter[] alphabet;
  private final Set<Node> leaves;
  private final Node root;

  public HuffmanCoder(Letter[] alphabet) {
    this.alphabet = alphabet;
    leaves = createLeavesFromAlphabet();
    root = buildHuffmanTable();
  }

  private Set<Node> createLeavesFromAlphabet() {
    Set<Node> leaves = new HashSet<>();
    for (Letter letter : alphabet)
      leaves.add(new Node(letter));
    return leaves;
  }

  private Node buildHuffmanTable() {
    Queue<Node> heap = newMinFrequencyHeapFromLeaves();
    while (heap.size() != 1) {
      Node rightChild = heap.poll();
      Node leftChild = heap.poll();
      Node parent = Node.merge(leftChild, rightChild);
      heap.add(parent);
    }
    Node root = heap.poll();
    return root;
  }

  private Queue<Node> newMinFrequencyHeapFromLeaves() {
    int size = leaves.size();
    PriorityQueue<Node> heap = new PriorityQueue<>(size, new Comparator<Node>() {
      @Override public int compare(Node node1, Node node2) {
        return Double.compare(node1.frequency, node2.frequency);
      }
    });
    heap.addAll(leaves);
    return heap;
  }

  public String encode(String text) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < text.length(); i++)
      encodeLetter(text.charAt(i), builder);
    return builder.toString();
  }

  private void encodeLetter(char letter, StringBuilder builder) {
    int offset = builder.length();
    Node leaf = getLeafOfLetter(letter);
    while (leaf != root) {
      char digit = mapSideToDigit(leaf.side);
      builder.insert(offset, digit);
      leaf = leaf.parent;
    }
  }

  public String decode(String text) {
    StringBuilder builder = new StringBuilder();
    Node currentNode = root;
    for (int i = 0; i < text.length(); i++) {
      currentNode = traverseTreeToNextDeeperNode(currentNode, text.charAt(i));
      if (currentNode.isLeave()) {
        char letter = currentNode.letter.getLetter();
        builder.append(letter);
{'fraction_non_alphanumeric': 0.11688311688311688, 'fraction_numerical': 0.003134796238244514, 'mean_word_length': 3.3623046875, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3100459', 'n_tokens_mistral': 1361, 'n_tokens_neox': 1312, 'n_words': 340}