Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

/**
 * Representação do nó na árvore de Huffman
 */
public interface Node
{

}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

/**
 * Representação da folha na árvore de Huffman
 */
public class Leaf implements Node
{
  /**
   * Símbolo armazenado na folha
   */
  private int symbol;

  /**
   * Inicializar a folha na árvore de Huffman
   *
   * @param symbol símbolo armazenado na folha
   */
  public Leaf(int symbol)
  {
    if (symbol < 0)
    {
      throw new IllegalArgumentException("Symbol value must be non-negative");
    }

    this.symbol = symbol;
  }

  /**
   * Retornar o símbolo armazenado na folha
   *
   * @return símbolo armazenado na folha
   */
  public int getSymbol()
  {
    return symbol;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

/**
 * Representação do nó interno na árvore de Huffman
 */
public class InternalNode implements Node
{
  /**
   *  Nó esquerdo na árvore de Huffman
   */
  private final Node left;

  /**
   * Nó direito na árvore de Huffman
   */
  private final Node right;

  /**
   * Inicializar o nó interno na árvore de Huffman
   *
   * @param left nó esquerdo na árvore de Huffman
   * @param right nó direito na árvore de Huffman
   */
  public InternalNode(Node left, Node right)
  {
    this.left = left;

    this.right = right;
  }

  /**
   * Retornar o nó esquerdo na árvore de Huffman
   *
   * @return nó esquerdo na árvore de Huffman
   */
  public Node getLeft()
  {
    return left;
  }

  /**
   * Retornar o nó direito na árvore de Huffman
   *
   * @return nó direito na árvore de Huffman
   */
  public Node getRight()
  {
    return right;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.util.ArrayList;
import java.util.List;

/**
 * Representação da árvore de Huffman
 */
public class CodeTree
{
  /**
   * Armazena o código para cada símbolo 
   */
  private List<List<Integer>> codes;

  /**
   * Raiz da árvore de Huffman 
   */
  private final InternalNode root;

  /**
   * Inicializar a árvore de Huffman
   *
   * @param root raiz da árvore de Huffman
   * @param symbolLimit quantidade de símbolos
   */
  public CodeTree(InternalNode root, int symbolLimit)
  {
    if (symbolLimit < 2)
    {
      throw new IllegalArgumentException("At least 2 symbols needed");
    }

    this.root = root;

    codes = new ArrayList<>();

    for (int i = 0; i < symbolLimit; i++)
    {
      codes.add(null);
    }

    buildCodeList(root, new ArrayList<Integer>());
  }

  /**
   * Retornar o código de Huffman do símbolo especificado
   *
   * @param symbol símbolo especificado
   * @return código de Huffman do símbolo especificado
   */
  public List<Integer> getCode(int symbol)
  {
    if (symbol < 0)
    {
      throw new IllegalArgumentException("Illegal symbol");
    }

    if (codes.get(symbol) == null)
    {
      throw new IllegalArgumentException("No code for given symbol");
    }

    return codes.get(symbol);
  }

  /**
   * Retornar a raiz da árvore de Huffman
   *
   * @return raiz da árvore de Huffman
   */
  public InternalNode getRoot()
  {
    return root;
  }

  /**
   * Construção recursiva da árvore de Huffman
   *
   * @param node nó atual
   * @param prefix prefixo do código de Huffman
   */
  private void buildCodeList(Node node, List<Integer> prefix)
  {
    if (node instanceof InternalNode)
    {
      InternalNode internalNode = (InternalNode) node;

      prefix.add(0);
      buildCodeList(internalNode.getLeft(), prefix);
      prefix.remove(prefix.size() - 1);

      prefix.add(1);
      buildCodeList(internalNode.getRight(), prefix);
      prefix.remove(prefix.size() - 1);
    }
    else
    {
      Leaf leaf = (Leaf) node;

      if (leaf.getSymbol() >= codes.size())
      {
        throw new IllegalArgumentException("Symbol exceeds symbol limit");
      }

      if (codes.get(leaf.getSymbol()) != null)
      {
        throw new IllegalArgumentException("Symbol has more than one code");
      }

      codes.set(leaf.getSymbol(), new ArrayList<Integer>(prefix));
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Classe responsável pela representação canônica do código de Huffman,
 * descrevendo apenas o comprimento do código de cada símbolo
 */
public class CanonicalCode
{
  /**
   * Array com os comprimentos do código de cada símbolo
   */
  private int[] codeLengths;

  /**
   * Inicializar a representação canônica do código de Huffman, a partir da árvore de código especificada
   *
   * @param tree árvore de código a ser analizada
   * @param symbolLimit número máximo de símbolos presentes na árvore de código
   */
  public CanonicalCode(CodeTree tree, int symbolLimit)
  {
    if (symbolLimit < 2)
    {
      throw new IllegalArgumentException("At least 2 symbols needed");
    }

    codeLengths = new int[symbolLimit];

    buildCodeLengths(tree.getRoot(), 0);
  }

  /**
   * Inicializar a representação canônica do código de Huffman, a partir da matriz especificada de comprimentos de código
   *
   * @param codeLengths array of symbol code lengths
   */
  public CanonicalCode(int[] codeLengths)
  {
    validate(codeLengths);

    this.codeLengths = codeLengths.clone();

    Arrays.sort(this.codeLengths);

    int currentLevel = this.codeLengths[this.codeLengths.length - 1];

    int numNodesAtLevel = 0;

    for (int i = (this.codeLengths.length - 1); (i >= 0) && (this.codeLengths[i] > 0); i--)
    {
      int codeLength = this.codeLengths[i];

      while (codeLength < currentLevel)
      {
        if ((numNodesAtLevel % 2) != 0)
        {
          throw new IllegalArgumentException("Under-full Huffman code tree");
        }

        numNodesAtLevel = numNodesAtLevel / 2;

        currentLevel = currentLevel - 1;
      }

      numNodesAtLevel = numNodesAtLevel + 1;
    }

    while (currentLevel > 0)
    {
      if ((numNodesAtLevel % 2) != 0)
      {
        throw new IllegalArgumentException("Under-full Huffman code tree");
      }

      numNodesAtLevel = numNodesAtLevel / 2;

      currentLevel = currentLevel - 1;
    }

    if (numNodesAtLevel < 1)
    {
      throw new IllegalArgumentException("Under-full Huffman code tree");
    }

    if (numNodesAtLevel > 1)
    {
      throw new IllegalArgumentException("Over-full Huffman code tree");
    }

    System.arraycopy(codeLengths, 0, this.codeLengths, 0, codeLengths.length);
  }

  /**
   * Returns the code length of the specified symbol value
   *
   * @param symbol the symbol value to query
   * @return the code length of the symbol, which is non-negative
   */
  public int getCodeLength(int symbol)
  {
    if ((symbol < 0) || (symbol >= codeLengths.length))
    {
      throw new IllegalArgumentException("Symbol out of range");
    }

    return codeLengths[symbol];
  }

  /**
   * Returns the symbol limit for this canonical Huffman code
   *
   * @return the symbol limit, which is at least 2
   */
  public int getSymbolLimit()
  {
    return codeLengths.length;
  }

  /**
   * Returns the canonical code tree for this canonical Huffman code
   *
   * @return the canonical code tree
   */
  public CodeTree toCodeTree()
  {
    List<Node> nodes = new ArrayList<>();

    for (int i = max(codeLengths); i >= 0; i--)
    {
      List<Node> newNodes = new ArrayList<>();

      if (i > 0)
      {
        for (int j = 0; j < codeLengths.length; j++)
        {
          if (codeLengths[j] == i)
          {
            newNodes.add(new Leaf(j));
          }
        }
      }

      for (int j = 0; j < nodes.size(); j += 2)
      {
        newNodes.add(new InternalNode(nodes.get(j), nodes.get(j + 1)));
      }

      nodes = newNodes;
    }

    return new CodeTree((InternalNode) nodes.get(0), codeLengths.length);
  }

  /**
   * Recursive helper method for the above constructor
   *
   * @param node actual node
   * @param depth depth of the tree
   */
  private void buildCodeLengths(Node node, int depth)
  {
    if (node instanceof InternalNode)
    {
      InternalNode internalNode = (InternalNode) node;

      buildCodeLengths(internalNode.getLeft(), depth + 1);

      buildCodeLengths(internalNode.getRight(), depth + 1);
    }
    else
    {
      int symbol = ((Leaf) node).getSymbol();

      if (symbol >= codeLengths.length)
      {
        throw new IllegalArgumentException("Symbol exceeds symbol limit");
      }

      codeLengths[symbol] = depth;
    }
  }

  /**
   * Returns the maximum value in the given array, which must have at least 1 element
   *
   * @param array array
   * @return maximum value in the array
   */
  private int max(int[] array)
  {
    int result = array[0];

    for (int x : array)
    {
      result = Math.max(x, result);
    }

    return result;
  }

  /**
   * Validate the array of symbol code lengths
   *
   * @param codeLengths array of symbol code lengths
   */
  private void validate(int[] codeLengths)
  {
    if (codeLengths.length < 2)
    {
      throw new IllegalArgumentException("At least 2 symbols needed");
    }

    for (int codeLength : codeLengths)
    {
      if (codeLength < 0)
      {
        throw new IllegalArgumentException("Illegal code length");
      }
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Representação da tabela de frequência dos símbolos
 */
public class FrequencyTable
{
  /**
   * Representação do nó utilizado na construção da tabela de frequência
   */
  private class NodeWithFrequency implements Comparable<NodeWithFrequency>
  {
    /**
     * Valor da frequência
     */
    public final long frequency;

    /**
     * Símbolo
     */
    public final int lowestSymbol;

    /**
     * Nó
     */
    public final Node node;

    /**
     * Inicializar o nó auxiliar
     *
     * @param node nó
     * @param lowestSymbol símbolo
     * @param frequency frequência
     */
    public NodeWithFrequency(Node node, int lowestSymbol, long frequency)
    {
      this.node = node;

      this.lowestSymbol = lowestSymbol;

      this.frequency = frequency;
    }

    /* (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(NodeWithFrequency other)
    {
      if (frequency < other.frequency)
      {
        return -1;
      }

      if (frequency > other.frequency)
      {
        return 1;
      }

      if (lowestSymbol < other.lowestSymbol)
      {
        return -1;
      }

      if (lowestSymbol > other.lowestSymbol)
      {
        return 1;
      }

      return 0;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object object)
    {
      if (this == object)
      {
        return true;
      }

      if (object == null)
      {
        return false;
      }

      if (getClass() != object.getClass())
      {
        return false;
      }

      NodeWithFrequency other = (NodeWithFrequency) object;
      
      if (frequency != other.frequency)
      {
        return false;
      }

      if (lowestSymbol != other.lowestSymbol)
      {
        return false;
      }

      if (node == null)
      {
        if (other.node != null)
        {
          return false;
        }
      }
      else if (!node.equals(other.node))
      {
        return false;
      }

      return true;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode()
    {
      final int prime = 31;

      int result = 1;

      result = prime * result + (int) (frequency ^ (frequency >>> 32));
      result = prime * result + lowestSymbol;
      result = prime * result + ((node == null) ? 0 : node.hashCode());

      return result;
    }
  }

  /**
   * Frequências
   */
  private int[] frequencies;

  /**
   * Inicializar a tabela de frequência dos símbolos
   *
   * @param frequencies Frequências
   */
  public FrequencyTable(int[] frequencies)
  {
    if (frequencies.length < 2)
    {
      throw new IllegalArgumentException("At least 2 symbols needed");
    }

    this.frequencies = frequencies.clone();

    for (int frequency : this.frequencies)
    {
      if (frequency < 0)
      {
        throw new IllegalArgumentException("Negative frequency");
      }
    }
  }

  /**
   * Retorna a árvore de Huffman ideal para as freqüências de símbolos contidas na tabela
   *
   * @return árvore de Huffman ideal para as freqüências de símbolos contidas na tabela
   */
  public CodeTree buildCodeTree()
  {
    Queue<NodeWithFrequency> pqueue = new PriorityQueue<>();

    for (int i = 0; i < frequencies.length; i++)
    {
      if (frequencies[i] > 0)
      {
        pqueue.add(new NodeWithFrequency(new Leaf(i), i, frequencies[i]));
      }
    }

    for (int i = 0; i < frequencies.length && pqueue.size() < 2; i++)
    {
      if (frequencies[i] == 0)
      {
        pqueue.add(new NodeWithFrequency(new Leaf(i), i, 0));
      }
    }

    while (pqueue.size() > 1)
    {
      NodeWithFrequency x = pqueue.remove();

      NodeWithFrequency y = pqueue.remove();

      pqueue.add(
          new NodeWithFrequency(
              new InternalNode(x.node, y.node), Math.min(x.lowestSymbol, y.lowestSymbol),
              x.frequency + y.frequency));
    }

    return new CodeTree((InternalNode) pqueue.remove().node, frequencies.length);
  }

  /**
   * Retornar a freqüência do símbolo especificado nesta tabela de freqüência
   *
   * @param symbol símbolo especificado
   * @return freqüência do símbolo especificado nesta tabela de freqüência
   */
  public int get(int symbol)
  {
    checkSymbol(symbol);

    return frequencies[symbol];
  }

  /**
   * Retornar o número de símbolos nesta tabela de freqüência
   *
   * @return número de símbolos nesta tabela de freqüência
   */
  public int getSymbolLimit()
  {
    return frequencies.length;
  }

  /**
   * Aumentar a frequência do símbolo especificado nesta tabela de frequências
   *
   * @param symbol símbolo especificado
   */
  public void increment(int symbol)
  {
    checkSymbol(symbol);

    if (frequencies[symbol] == Integer.MAX_VALUE)
    {
      throw new IllegalStateException("Maximum frequency reached");
    }

    frequencies[symbol]++;
  }

  /**
   * Configurar a frequência do símbolo especificado nesta tabela de frequências para o valor especificado
   *
   * @param symbol símbolo especificado
   * @param frequency valor especificado
   */
  public void set(int symbol, int frequency)
  {
    checkSymbol(symbol);

    if (frequency < 0)
    {
      throw new IllegalArgumentException("Negative frequency");
    }

    frequencies[symbol] = frequency;
  }

  /**
   * Verificar se o símbolo especificado está contido no intervalo especificado
   *
   * @param symbol símbolo especificado
   */
  private void checkSymbol(int symbol)
  {
    if ((symbol < 0) || (symbol >= frequencies.length))
    {
      throw new IllegalArgumentException("Symbol out of range");
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.EOFException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Classe responsável pela leitura do fluxo de bits de entrada
 */
public class BitInputStream extends InputStream
{
  /**
   * Byte atual, no intervalo de 0x00 a 0xFF ou -1 se o fim do fluxo for atingido
   */
  private int currentByte;

  /**
   * Fluxo de bits de entrada
   */
  private final InputStream inputStream;

  /**
   * Número de bits restantes no byte atual, sempre entre 0 e 7 (inclusive)
   */
  private int numBitsRemaining;

  /**
   * Inicializar a leitura do fluxo de bits de entrada
   *
   * @param inputStream fluxo de bits de entrada
   */
  public BitInputStream(InputStream inputStream)
  {
    this.inputStream = inputStream;
  }

  /* (non-Javadoc)
   * @see java.io.InputStream#read()
   */
  @Override
  public int read() throws IOException
  {
    if (currentByte == -1)
    {
      throw new EOFException();
    }

    if (numBitsRemaining == 0)
    {
      currentByte = inputStream.read();

      if (currentByte == -1)
      {
        throw new EOFException();
      }

      numBitsRemaining = 8;
    }

    numBitsRemaining = numBitsRemaining - 1;

    return (currentByte >>> numBitsRemaining) & 1;
  }

  /* (non-Javadoc)
   * @see java.io.InputStream#close()
   */
  @Override
  public void close() throws IOException
  {
    inputStream.close();

    currentByte = -1;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.IOException;
import java.io.OutputStream;

/**
 * Classe responsável pela escrita do fluxo de bits de saída
 */
public class BitOutputStream extends OutputStream
{
  /**
   * Byte atual, no intervalo de 0x00 a 0xFF, onde os bits são acumulados
   */
  private int currentByte;

  /**
   * Número de bits acumulados no byte atual, sempre entre 0 e 7 (inclusive)
   */
  private int numBitsFilled;

  /**
   * Fluxo de bits de saída
   */
  private OutputStream outputStream;

  /**
   * Inicializar a escrita do fluxo de bits de saída
   *
   * @param outputStream fluxo de bits de saída
   */
  public BitOutputStream(OutputStream outputStream)
  {
    this.outputStream = outputStream;
  }

  /* (non-Javadoc)
   * @see java.io.OutputStream#write(int)
   */
  @Override
  public void write(int bit) throws IOException
  {
    if ((bit != 0) && (bit != 1))
    {
      throw new IllegalArgumentException("Argument must be 0 or 1");
    }

    currentByte = (currentByte << 1) | bit;

    numBitsFilled = numBitsFilled + 1;

    if (numBitsFilled == 8)
    {
      outputStream.write(currentByte);

      currentByte = 0;

      numBitsFilled = 0;
    }
  }

  /* (non-Javadoc)
   * @see java.io.OutputStream#close()
   */
  @Override
  public void close() throws IOException
  {
    while (numBitsFilled != 0)
    {
      write(0);
    }

    outputStream.close();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.IOException;
import java.io.OutputStream;

/**
 * Codificação da árvore de Huffman num fluxo de bits
 */
public class Encoder
{
  /**
   * Fluxo de bits de saída
   */
  private OutputStream outputStream;

  /**
   * Árvore de Huffman
   */
  private CodeTree codeTree;

  /**
   * Inicializar o codificador de Huffman
   *
   * @param codeTree árvore de Huffman
   * @param outputStream fluxo de bits de saída
   */
  public Encoder(CodeTree codeTree, OutputStream outputStream)
  {
    this.codeTree = codeTree;

    this.outputStream = outputStream;
  }

  /**
   * Codificar a árvore de Huffman num fluxo de bits
   *
   * @param symbol símbolo a ser codificado
   * @throws IOException problemas na gravação do fluxo de bits
   */
  public void write(int symbol) throws IOException
  {
    for (int code : codeTree.getCode(symbol))
    {
      outputStream.write(code);
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.IOException;
import java.io.InputStream;

/**
 * Decodificação do fluxo de bits numa árvore de Huffman
 */
public class Decoder
{
  /**
   * Fluxo de bits de entrada
   */
  private InputStream inputStream;

  /**
   * Árvore de Huffman
   */
  private CodeTree codeTree;

  /**
   * Inicializar a decodificação do fluxo de bits numa árvore de Huffman
   *
   * @param codeTree árvore de Huffman
   * @param inputStream fluxo de bits de entrada
   */
  public Decoder(CodeTree codeTree, InputStream inputStream)
  {
    this.codeTree = codeTree;

    this.inputStream = inputStream;
  }

  /**
   * Decodificar o fluxo de bits numa árvore de Huffman
   *
   * @return símbolo lido
   * @throws IOException problemas na leitura do fluxo de bits
   */
  public int read() throws IOException
  {
    InternalNode currentNode = codeTree.getRoot();

    while (true)
    {
      int bit = inputStream.read();

      Node nextNode;

      if (bit == 0)
      {
        nextNode = currentNode.getLeft();
      }
      else
      {
        nextNode = currentNode.getRight();
      }

      if (nextNode instanceof InternalNode)
      {
        currentNode = (InternalNode) nextNode;
      }
      else
      {
        return ((Leaf) nextNode).getSymbol();
      }
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

/**
 * Compressão de documentos utilizando a codificação de Huffman
 */
public class Huffman
{
  /**
   * Fluxo de entrada (arquivo de entrada)
   */
  private InputStream inputStream;
  
  /**
   * Fluxo de saída (arquivo de saída)
   */
  private OutputStream outputStream;
  
  /**
   * Construir a tabela de frequências dos caracteres contidos no arquivo de entrada
   *
   * @param file arquivo de entrada
   * @return tabela de frequências dos caracteres contidos no arquivo de entrada
   * @throws IOException problemas na leitura do arquivo de entrada
   */
  private FrequencyTable buildFrequencyTable(File file) throws IOException
  {
    FrequencyTable frequencies = new FrequencyTable(new int[257]);

    InputStream inputStream = new BufferedInputStream(new FileInputStream(file));

    try
    {
      while (true)
      {
        int bit = inputStream.read();

        if (bit == -1)
        {
          break;
        }

        frequencies.increment(bit);
      }
    }
    finally
    {
      inputStream.close();
    }

    return frequencies;
  }
  
  /**
   * Comprimir o arquivo de entrada no arquivo de saída
   *
   * @param inputFile arquivo de entrada
   * @param outputFile arquivo de saída
   * @throws HuffmanException problemas na execução do algoritmo de Huffman
   */
  public void compress(File inputFile, File outputFile) throws HuffmanException
  {
    FrequencyTable frequencyTable;

    try
    {
      frequencyTable = buildFrequencyTable(inputFile);
    }
    catch (IOException exception)
    {
      throw new HuffmanException(exception);
    }

    frequencyTable.increment(256);

    CodeTree code = frequencyTable.buildCodeTree();

    CanonicalCode canonicalCode = new CanonicalCode(code, 257);

    code = canonicalCode.toCodeTree();

    try
    {
      inputStream = new BufferedInputStream(new FileInputStream(inputFile));
    }
    catch (FileNotFoundException exception)
    {
      throw new HuffmanException(exception);
    }

    try
    {
      outputStream = new BitOutputStream(new BufferedOutputStream(new FileOutputStream(outputFile)));
    }
    catch (FileNotFoundException exception)
    {
      throw new HuffmanException(exception);
    }

    try
    {
      writeCodeLengthTable(canonicalCode);

      writeData(code);
    }
    catch (IOException exception)
    {
      throw new HuffmanException(exception);
    }
    finally
    {
      close();
    }
  }
  
  /**
   * Descomprimir o arquivo de entrada no arquivo de saída
   *
   * @param inputFile arquivo de entrada
   * @param outputFile arquivo de saída
   * @throws HuffmanException problemas na execução do algoritmo de Huffman
   */
  public void descompress(File inputFile, File outputFile) throws HuffmanException
  {
    try
    {
      inputStream = new BitInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
    }
    catch (FileNotFoundException exception)
    {
      throw new HuffmanException(exception);
    }

    try
    {
      outputStream = new BufferedOutputStream(new FileOutputStream(outputFile));
    }
    catch (FileNotFoundException exception)
    {
      throw new HuffmanException(exception);
    }

    try
    {
      CanonicalCode canonCode = readCodeLengthTable();

      readData(canonCode.toCodeTree());
    }
    catch (IOException exception)
    {
      throw new HuffmanException(exception);
    }
    finally
    {
      close();
    }
  }
  
  /**
   * Fechar os arquivos de entrada e saída
   * 
   * @throws HuffmanException problemas na execução do algoritmo de Huffman
   */
  private void close() throws HuffmanException
  {
    try
    {
      if(inputStream != null)
      {
        inputStream.close();
      }

      if(outputStream != null)
      {
        outputStream.close();
      }
    }
    catch (IOException exception)
    {
      throw new HuffmanException(exception);
    }
  }
  
  /**
   * Ler a tabela com os códigos de Huffman
   *
   * @return tabela com os códigos de Huffman
   * @throws IOException problemas com a leitura dos códigos de Huffman
   */
  private CanonicalCode readCodeLengthTable() throws IOException
  {
    int[] codeLengths = new int[257];

    for (int i = 0; i < codeLengths.length; i++)
    {
      int val = 0;

      for (int j = 0; j < 8; j++)
      {
        val = (val << 1) | inputStream.read();
      }

      codeLengths[i] = val;
    }

    return new CanonicalCode(codeLengths);
  }
  
  /**
   * Ler os dados compactados
   *
   * @param codeTree árvore de Huffman
   * @throws IOException problemas com a leitura dos dados compactados
   */
  private void readData(CodeTree codeTree) throws IOException
  {
    Decoder decoder = new Decoder(codeTree, inputStream);

    while (true)
    {
      int symbol = decoder.read();

      if (symbol == 256)
      {
        break;
      }

      outputStream.write(symbol);
    }
  }
  
  /**
   * Escrever a tabela de compressão utilizada no arquivo de entrada
   *
   * @param canonicalCode códigos de Huffman
   * @throws IOException problemas na escrita da tabela
   */
  private void writeCodeLengthTable(CanonicalCode canonicalCode) throws IOException
  {
    for (int i = 0; i < canonicalCode.getSymbolLimit(); i++)
    {
      int codeLength = canonicalCode.getCodeLength(i);

      if (codeLength >= 256)
      {
        throw new RuntimeException("The code for a symbol is too long");
      }

      for (int j = 7; j >= 0; j--)
      {
        outputStream.write((codeLength >>> j) & 1);
      }
    }
  }
  
  /**
   * Escrever os dados
   *
   * @param codeTree árvore de Huffman
   * @throws IOException problemas na escrita dos dados
   */
  private void writeData(CodeTree codeTree) throws IOException
  {
    Encoder encoder = new Encoder(codeTree, outputStream);

    while (true)
    {
      int bit = inputStream.read();

      if (bit == -1)
      {
        break;
      }

      encoder.write(bit);
    }

    encoder.write(256);
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

public class HuffmanException extends Exception
{
  /**
   * Identificador de serialização da classe
   */
  private static final long serialVersionUID = 1L;
  
  /**
   * Constructs a new exception with null as it's detail message
   */
  public HuffmanException()
  {
    super();
  }
  
  /**
   * Constructs a new exception with the specified detail message
   *
   * @param message the detail message
   */
  public HuffmanException(String message)
  {
    super(message);
  }
  
  /**
   * Constructs a new exception with the specified cause
   *
   * @param cause the cause
   */
  public HuffmanException(Throwable cause)
  {
    super(cause);
  }
  
  /**
   * Constructs a new exception with the specified detail message and cause
   *
   * @param message the detail message
   * @param cause the cause
   */
  public HuffmanException(String message, Throwable cause)
  {
    super(message, cause);
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial07.exercicio08;

import java.io.File;

/**
 * Classe responsável pela execução da compressão de Huffman
 */
public class Application
{
  /**
   * Método principal da linguagem de programação Java
   *
   * @param args argumentos da linha de comando
   */
  public static void main(String[] args)
  {
    if (args.length == 3)
    {
      if ("-x".equals(args[0]))
      {
        try
        {
          new Huffman().compress(new File(args[1]), new File(args[2]));
        }
        catch (HuffmanException exception)
        {
          exception.printStackTrace();
        }
        finally
        {
          System.exit(0);
        }
      }

      if ("-c".equals(args[0]))
      {
        try
        {
          new Huffman().descompress(new File(args[1]), new File(args[2]));
        }
        catch (HuffmanException exception)
        {
          exception.printStackTrace();
        }
        finally
        {
          System.exit(0);
        }
      }  
    }

    System.err.println("Usage: java Application -[x|c] inputFile outputFile");

    System.exit(1);
  }
}