/*************************************************************

 Huffman coding implementation

 Provides the encode and decode implementation
							     
 *************************************************************/

#include <iostream>
#include <queue>

#include "binary_tree.h"
#include "huffman_codec.h"
#include "bitio.h"


void huffman_codec::encode(std::istream & in, std::ostream & out) {
  int i;

  // Initialize character frequencies to zero

  // Read the plaintext and count the frequency of each character.

  // Make sure there are some characters to encode.
  // In other words, make sure there is at least one character to encode.

  // Define a priority queue to store a forest of (pointers to) binary trees.
  
  // Construct a binary tree for each character in the input file, 
  // and put them in the priority queue.

  // Keep an index of iterators to the node representing each character
  // for later use in constructing the character encodings.
  
  // Combine the trees to form a single tree representing the Huffman code.
  // Take two trees with the smallest frequency and combine them to 
  // form a new tree with frequency equal to the sum of the two tree.
  // Repeat this process until all the trees are combined into
  // one tree.

  // Determine the encoding for each character by using the index
  // of iterators. Start at a leaf a backtrack to the root.
  // Do this for every leaf.

  // Write out the tree and the length of the plaintext.

  // Write out the encoded plaintext.
  in.clear();
  in.seekg(0);
  bit_packer bp;
  while (in.get(b))
    bp.write(out, character_encoding[(unsigned char) b]);
  bp.flush(out);
}


void
huffman_codec::decode(std::istream & in, std::ostream & out)
{

  // Read the tree

  // Get the length of the plaintext

  // Write out the decoded plaintext
  bit_unpacker bup;
  tree_type::iterator i;
  while (count > 0)
  {
    i = encoding_tree->begin();
    while (!(i.is_leaf()))
    {
      bool bit = bup.read(in);	
      if (bit)
	i = i.right();
      else
	i = i.left();
    }

    out << (*i).character;
    --count;
  }
}